Merge pull request #16 from abarth/lowerBound
Add lowerBound
diff --git a/CHANGELOG.md b/CHANGELOG.md
index a39a2b5..04f883f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,7 @@
+## 1.2.1
+
+* Add lowerBound to binary search for values that might not be present.
+
## 1.2.0
* Add string comparators that ignore ASCII case and sort numbers numerically.
diff --git a/lib/algorithms.dart b/lib/algorithms.dart
index 5ff0bb3..80f0107 100644
--- a/lib/algorithms.dart
+++ b/lib/algorithms.dart
@@ -10,13 +10,13 @@
import "dart:math" show Random;
/** Version of [binarySearch] optimized for comparable keys */
-int _comparableBinarySearch(List<Comparable> list, Comparable key) {
+int _comparableBinarySearch(List<Comparable> list, Comparable value) {
int min = 0;
int max = list.length;
while (min < max) {
int mid = min + ((max - min) >> 1);
var element = list[mid];
- int comp = element.compareTo(key);
+ int comp = element.compareTo(value);
if (comp == 0) return mid;
if (comp < 0) {
min = mid + 1;
@@ -28,7 +28,7 @@
}
/**
- * Returns a position of the [key] in [sortedList], if it is there.
+ * Returns a position of the [value] in [sortedList], if it is there.
*
* If the list isn't sorted according to the [compare] function, the result
* is unpredictable.
@@ -36,19 +36,18 @@
* If [compare] is omitted, it defaults to calling [Comparable.compareTo] on
* the objects.
*
- * Returns -1 if [key] is not in the list by default.
+ * Returns -1 if [value] is not in the list by default.
*/
-int binarySearch(List sortedList, var key,
- { int compare(var a, var b) }) {
+int binarySearch(List sortedList, value, { int compare(a, b) }) {
if (compare == null) {
- return _comparableBinarySearch(sortedList, key);
+ return _comparableBinarySearch(sortedList, value);
}
int min = 0;
int max = sortedList.length;
while (min < max) {
int mid = min + ((max - min) >> 1);
var element = sortedList[mid];
- int comp = compare(element, key);
+ int comp = compare(element, value);
if (comp == 0) return mid;
if (comp < 0) {
min = mid + 1;
@@ -59,6 +58,54 @@
return -1;
}
+/** Version of [lowerBound] optimized for comparable keys */
+int _comparableLowerBound(List<Comparable> list, Comparable value) {
+ int min = 0;
+ int max = list.length;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ var element = list[mid];
+ int comp = element.compareTo(value);
+ if (comp < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ return min;
+}
+
+/**
+ * Returns the first position in [sortedList] that does not compare less than
+ * [value].
+ *
+ * If the list isn't sorted according to the [compare] function, the result
+ * is unpredictable.
+ *
+ * If [compare] is omitted, it defaults to calling [Comparable.compareTo] on
+ * the objects.
+ *
+ * Returns [sortedList.length] if all the items in [sortedList] compare less
+ * than [value].
+ */
+int lowerBound(List sortedList, value, { int compare(a, b) }) {
+ if (compare == null) {
+ return _comparableLowerBound(sortedList, value);
+ }
+ int min = 0;
+ int max = sortedList.length;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ var element = sortedList[mid];
+ int comp = compare(element, value);
+ if (comp < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ return min;
+}
/**
* Shuffles a list randomly.
diff --git a/pubspec.yaml b/pubspec.yaml
index 3642321..3595f9c 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 1.2.0
+version: 1.2.1-dev
author: Dart Team <misc@dartlang.org>
description: Collections and utilities functions and classes related to collections.
homepage: https://www.github.com/dart-lang/collection
diff --git a/test/algorithms_test.dart b/test/algorithms_test.dart
index 61fbf5b..a639106 100644
--- a/test/algorithms_test.dart
+++ b/test/algorithms_test.dart
@@ -99,6 +99,60 @@
expect(binarySearch(l3, new C(12), compare: compareC), equals(-1));
});
+ test("lowerbound0", () {
+ expect(lowerBound([], 2), equals(0));
+ });
+
+ test("lowerbound1", () {
+ expect(lowerBound([5], 2), equals(0));
+ expect(lowerBound([5], 5), equals(0));
+ expect(lowerBound([5], 7), equals(1));
+ });
+
+ test("lowerbound3", () {
+ expect(lowerBound([0, 5, 10], -1), equals(0));
+ expect(lowerBound([0, 5, 10], 0), equals(0));
+ expect(lowerBound([0, 5, 10], 2), equals(1));
+ expect(lowerBound([0, 5, 10], 5), equals(1));
+ expect(lowerBound([0, 5, 10], 7), equals(2));
+ expect(lowerBound([0, 5, 10], 10), equals(2));
+ expect(lowerBound([0, 5, 10], 12), equals(3));
+ });
+
+ test("lowerboundRepeat", () {
+ expect(lowerBound([5, 5, 5], 5), equals(0));
+ expect(lowerBound([0, 5, 5, 5, 10], 5), equals(1));
+ });
+
+ test("lowerboundCompare0", () {
+ expect(lowerBound([], new C(2), compare: compareC), equals(0));
+ });
+
+ test("lowerboundCompare1", () {
+ var l1 = [new C(5)];
+ expect(lowerBound(l1, new C(2), compare: compareC), equals(0));
+ expect(lowerBound(l1, new C(5), compare: compareC), equals(0));
+ expect(lowerBound(l1, new C(7), compare: compareC), equals(1));
+ });
+
+ test("lowerboundCompare3", () {
+ var l3 = [new C(0), new C(5), new C(10)];
+ expect(lowerBound(l3, new C(-1), compare: compareC), equals(0));
+ expect(lowerBound(l3, new C(0), compare: compareC), equals(0));
+ expect(lowerBound(l3, new C(2), compare: compareC), equals(1));
+ expect(lowerBound(l3, new C(5), compare: compareC), equals(1));
+ expect(lowerBound(l3, new C(7), compare: compareC), equals(2));
+ expect(lowerBound(l3, new C(10), compare: compareC), equals(2));
+ expect(lowerBound(l3, new C(12), compare: compareC), equals(3));
+ });
+
+ test("lowerboundCompareRepeat", () {
+ var l1 = [new C(5), new C(5), new C(5)];
+ var l2 = [new C(0), new C(5), new C(5), new C(5), new C(10)];
+ expect(lowerBound(l1, new C(5), compare: compareC), equals(0));
+ expect(lowerBound(l2, new C(5), compare: compareC), equals(1));
+ });
+
test("insertionSortRandom", () {
Random random = new Random();
for (int i = 0; i < 25; i++) {
