Add collection-helpers library.

pkg/collection_helpers/lib/algorithms.dart

+// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/** 
+ * Operations on collections.
+ */
+library dart.collection_helper.algorithms;
+
+import "dart:math" show Random;
+
+/** Version of [binarySearch] optimized for comparable keys */
+int _comparableBinarySearch(List<Comparable> list, Comparable key, 
+                            bool location) {
+  int min = 0;
+  int max = list.length;
+  while (min < max) {
+    int mid = min + ((max - min) >> 1);

[floitsch, 2013/09/21 18:12:37]

~/ 2

[Lasse Reichstein Nielsen, 2013/09/24 20:23:53]

All done.

+    var element = list[mid];
+    int comp = element.compareTo(key);
+    if (comp == 0) return mid;
+    if (comp < 0) {
+      min = mid + 1;
+    } else {
+      max = mid;
+    }
+  }
+  if (location) return min;
+  return -1;
+}
+
+/** 
+ * Returns the position of the [key] in [sortedList], if it is there.
+ * 
+ * If the list isn't sorted according to the [compare] function, the result
+ * is unpredicatable.
+ *  
+ * If [compare] is omitted, it defaults to calling [Comparable.compareTo] on 
+ * the objects.
+ *  
+ * Returns -1 if [key] is not in the list by default.
+ * If [location] is true, instead returns the index where [key] would have
+ * been. That is, where inserting the key at the returned position would keep
+ * the list sorted. 
+ */
+int binarySearch(List sortedList, var key, 
+                 { int compare(var a, var b),
+                   bool location: false

[Lasse Reichstein Nielsen, 2013/09/18 13:39:25]

Consider having three different versions:
- plain - finds the element, any version, if it's there.
- for insertion, first: finds the index where all preceding elements are less
than (at first matching element in list).
- for insertion, last: finds the index where all preceding elements are less
than or equal (after last matching element in list).

[floitsch, 2013/09/21 18:12:37]

location is not a boolean name.
returnLocation?
negativeWhenAbsent ?

+                 }) {
+  if (compare == null) return _comparableBinarySearch(sortedList, key, location);

[Lasse Reichstein Nielsen, 2013/09/18 13:39:25]

Whoops, long line.

+  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);
+    if (comp == 0) return mid;
+    if (comp < 0) {
+      min = mid + 1;
+    } else {
+      max = mid;
+    }
+  }
+  if (location) return max;
+  return -1;
+}
+
+
+/**
+ * Shuffles a list randomly.
+ * 
+ * A sub-range of a list can be shuffled by providing [start] and [end].319
+ */
+void shuffle(List list, [int start = 0, int end = null]) {

[kevmoo-old, 2013/09/20 21:34:35]

Optional argument for Random impl.

[floitsch, 2013/09/21 18:12:37]

This should be moved as member method on List.

[Lasse Reichstein Nielsen, 2013/09/24 20:23:53]

I'd prefer to keep this as simple as possible. No need to confuse users with the
ability to pass in a different Random implementation.

If you know enough to use a different Random, you can write this in eighth lines
yourself too.

Especially if it's put on ListBase.

+  Random random = new Random();
+  if (end == null) end = list.length;
+  int length = end - start;
+  while (length > 1) {
+    int pos = random.nextInt(length); 
+    var tmp1 = list[start + pos];
+    var tmp2 = list[start + length - 1];
+    list[start + length - 1] = tmp1;
+    list[start + pos] = tmp2;
+    length--;
+  }
+}
+
+
+/**
+ * Reverses a list, or a part of a list, in-place.
+ */
+void reverse(List list, [int start = 0, int end = null]) {
+  if (end == null) end = list.length;
+  _reverse(list, start, end);
+}
+
+// Internal helper function that assumes valid arguments.
+void _reverse(List list, int start, int end) {
+  for (int i = start, j = end - 1; i < j; i++, j--) {
+    var tmp = list[i];
+    list[i] = list[j];
+    list[j] = tmp;
+  } 
+}
+
+/**
+ * Sort a list using insertion sort. 

[Lasse Reichstein Nielsen, 2013/09/18 13:39:25]

Should document the behavior of insertion sort (low overhead, n-log(n)
comparisons, n^2 element moves worst case).

+ */
+void insertionSort(List list, 
+                   { int compare(a, b), 
+                     int start: 0, 
+                     int end: null }) {
+  // If the same method could have both positional and named optional 
+  // parameters, this should be (list, [start, end], {compare}).
+  if (end == null) end = list.length;
+  if (compare == null) compare = Comparable.compare;
+  _insertionSort(list, compare, start, end, start + 1);
+}
+
+/** 
+ * Internal helper function that assumes arguments correct.
+ * 
+ * Assumes that the elements up to [sortedUntil] (not inclusive) are 
+ * already sorted. The [sortedUntil] values should always be at least
+ * `start + 1`.
+ */
+void _insertionSort(List list, int compare(a, b), int start, int end, 
+                    int sortedUntil) {
+  for (int pos = sortedUntil; pos < end; pos++) {
+    int min = start;
+    int max = pos;
+    var element = list[pos];
+    while (min < max) {

[floitsch, 2013/09/21 18:12:37]

I'm not convinced that binary search really is worth it.
The setRange below needs to run through the list anyway. Could be, of course,
that compare is really slow, but I wouldn't design the insertion sort on it.

[Lasse Reichstein Nielsen, 2013/09/24 20:23:53]

I'm planning to use this insertionSort for TimSort as well, and that typically
uses binary insertion sort (original implementation and Java implementation
both).

+      int mid = min + ((max - min) >> 1);

[floitsch, 2013/09/21 18:12:37]

~/ 2

+      int comparison = compare(element, list[mid]);
+      if (comparison < 0) {
+        max = mid;
+      } else {
+        min = mid + 1;
+      }
+    }
+    list.setRange(min + 1, pos + 1, list, min);
+    list[min] = element;
+  }
+}
+
+/** Limit below which merge sort defaults to insertion sort. */
+const int _MERGE_SORT_LIMIT = 32;
+
+void mergeSort(List list, {int start: 0, int end: null, int compare(a, b)}) {

[Lasse Reichstein Nielsen, 2013/09/18 13:39:25]

Should have documentation.

+  if (end == null) end = list.length;
+  if (compare == null) compare = Comparable.compare;
+  int length = end - start;
+  if (length < 2) return;
+  if (length < _MERGE_SORT_LIMIT) {
+    _insertionSort(list, compare, start, end, start + 1);
+    return;
+  }
+  // Special case the first split instead of directly calling 
+  // _mergeSort, because the _mergeSort requires its target to 
+  // be different from its source, and it requires extra space
+  // of the same size as the list to sort.
+  // This split allows us to have only half as much extra space,
+  // and it ends up in the original place.
+  int middle = start + ((end - start) >> 1);

[floitsch, 2013/09/21 18:12:37]

~/ 2

+  int firstLength = middle - start;
+  int secondLength = end - middle;
+  List scratchSpace = new List(secondLength);

[floitsch, 2013/09/21 18:12:37]

assert(secondLength >= firstLength);

[Lasse Reichstein Nielsen, 2013/09/24 20:23:53]

Why assert? Documentation should be enough.

+  _mergeSort(list, compare, middle, end, scratchSpace, 0);
+  int firstTarget = end - firstLength;
+  _mergeSort(list, compare, start, middle, list, firstTarget);
+  _merge(compare, 
+         list, firstTarget, end,
+         scratchSpace, 0, secondLength,
+         list, start);
+}
+
+/**
+ * Performs an insertion sort into a potentially different list than the
+ * one containing the original values.
+ * 
+ * It will work in-place as well.
+ */
+void _movingInsertionSort(List list, int compare(a, b), int start, int end,
+                          List target, int targetOffset) {
+  int length = end - start;
+  if (length == 0) return;
+  target[targetOffset] = list[start];
+  for (int i = 1; i < length; i++) {
+    var element = list[start + i];
+    int min = targetOffset;
+    int max = targetOffset + i;
+    while (min < max) {
+      int mid = min + ((max - min) >> 1);

[floitsch, 2013/09/21 18:12:37]

~/ 2

+      if (compare(element, target[mid]) < 0) {
+        max = mid;
+      } else {
+        min = mid + 1;
+      }
+    }
+    target.setRange(min + 1, targetOffset + i + 1, 
+                    target, min);
+    target[min] = element;
+  }
+}
+
+/**
+ * Sorts [list] from [start] to [end] into [target] at [targetOffset].
+ * 
+ * The `target` list must be able to contain the range from `start` to `end`
+ * after `targetOffset`.
+ * 
+ * Allows target to be the same list as [list], as long as it's not
+ * overlapping the `start..end` range.
+ */
+void _mergeSort(List list, int compare(a, b), int start, int end,
+                List target, int targetOffset) {
+  int length = end - start;
+  if (length < _MERGE_SORT_LIMIT) {
+    _movingInsertionSort(list, compare, start, end, target, targetOffset);
+    return;
+  }
+  int middle = start + (length >> 1);

[floitsch, 2013/09/21 18:12:37]

~/ 2

+  int firstLength = middle - start;
+  int secondLength = end - middle;
+  int targetMiddle = targetOffset + firstLength;
+  // Sort the second half into the end of the target area.
+  _mergeSort(list, compare, middle, end, 
+             target, targetMiddle);
+  // sort the first half into the end of the source area.

[floitsch, 2013/09/21 18:12:37]

Start with capital letter.

[Lasse Reichstein Nielsen, 2013/09/24 20:23:53]

Done.

+  _mergeSort(list, compare, start, middle, 
+             list, middle);
+  // merge the two parts into the target area.

[floitsch, 2013/09/21 18:12:37]

ditto.

[Lasse Reichstein Nielsen, 2013/09/24 20:23:53]

Done.

+  _merge(compare,
+         list, middle, middle + firstLength,
+         target, targetMiddle, targetMiddle + secondLength,
+         target, targetOffset); 
+}
+
+/**
+ * Mergest two lists into a target list.
+ * 
+ * One of the input lists may be positioned at the end of the target
+ * list.
+ * 
+ * For equal object, elements from [firstList] are always preferred.
+ * This allows the merge to be stable if the first list contains elements
+ * that started out earlier than the ones in [secondList]
+ */
+void _merge(int compare(a, b), 
+            List firstList, int firstStart, int firstEnd,
+            List secondList, int secondStart, int secondEnd,
+            List target, int targetOffset) {
+  // No empty lists reaches here.
+  assert(firstStart < firstEnd);
+  assert(secondStart < secondEnd);
+  int cursor1 = firstStart;
+  int cursor2 = secondStart;
+  var firstElement = firstList[cursor1++];
+  var secondElement = secondList[cursor2++];
+  // Two nested breakable statements is a hack to allow moving two different
+  // finishing conditions outside the loop without having to retest the
+  // exit conditions. This is just to keep the loop short.
+  firstEmpty: {  
+    secondEmpty: while (true) {
+      if (compare(firstElement, secondElement) <= 0) {
+        target[targetOffset++] = firstElement;
+        if (cursor1 == firstEnd) break firstEmpty;
+        firstElement = firstList[cursor1++];
+      } else {
+        target[targetOffset++] = secondElement;
+        if (cursor2 == secondEnd) break secondEmpty;

[floitsch, 2013/09/21 18:12:37]

I think it's cleaner to have a restList, restOffset, restCursor that is set
before breaking.
Alternatively simply switching firstList and secondList before the second break.

[Lasse Reichstein Nielsen, 2013/09/24 20:23:53]

If I have to do more than a single line of work to make that work, I could just
as well inline the three lines below. This is only done to keep the loop
smaller.

I think I can do a rewrite that avoids the extra labels, and gets the same
result with a single break and a continue.

+        secondElement = secondList[cursor2++];
+      }
+    }
+    // Second list empties first.
+    target[targetOffset++] = firstElement;
+    target.setRange(targetOffset, targetOffset + (firstEnd - cursor1),
+        firstList, cursor1);
+    return;
+  }
+  // First list empties first.
+  target[targetOffset++] = secondElement;
+  target.setRange(targetOffset, targetOffset + (secondEnd - cursor2),
+      secondList, cursor2);
+}