Hide collection-dev library.

sdk/lib/collection_dev/sort.dart

Index: sdk/lib/collection_dev/sort.dart
diff --git a/sdk/lib/collection_dev/sort.dart b/sdk/lib/collection_dev/sort.dart
deleted file mode 100644
index 9b89e638ff089472e18ec056b2d2f6ac8d985946..0000000000000000000000000000000000000000
--- a/sdk/lib/collection_dev/sort.dart
+++ /dev/null
@@ -1,344 +0,0 @@
-// Copyright (c) 2011, 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.
-
-part of dart.collection.dev;
-
-/**
- * Dual-Pivot Quicksort algorithm.
- *
- * This class implements the dual-pivot quicksort algorithm as presented in
- * Vladimir Yaroslavskiy's paper.
- *
- * Some improvements have been copied from Android's implementation.
- */
-class Sort {
-  // When a list has less then [:_INSERTION_SORT_THRESHOLD:] elements it will
-  // be sorted by an insertion sort.
-  static const int _INSERTION_SORT_THRESHOLD = 32;
-
-  /**
-   * Sorts all elements of the given list [:a:] according to the given
-   * [:compare:] function.
-   *
-   * The [:compare:] function takes two arguments [:x:] and [:y:] and returns
-   *  -1 if [:x < y:],
-   *   0 if [:x == y:], and
-   *   1 if [:x > y:].
-   *
-   * The function's behavior must be consistent. It must not return different
-   * results for the same values.
-   */
-  static void sort(List a, int compare(a, b)) {
-    _doSort(a, 0, a.length - 1, compare);
-  }
-
-  /**
-   * Sorts all elements in the range [:from:] (inclusive) to [:to:] (exclusive)
-   * of the given list [:a:].
-   *
-   * If the given range is invalid an "OutOfRange" error is raised.
-   * TODO(floitsch): do we want an error?
-   *
-   * See [:sort:] for requirements of the [:compare:] function.
-   */
-  static void sortRange(List a, int from, int to, int compare(a, b)) {
-    if ((from < 0) || (to > a.length) || (to < from)) {
-      throw "OutOfRange";
-    }
-    _doSort(a, from, to - 1, compare);
-  }
-
-  /**
-   * Sorts the list in the interval [:left:] to [:right:] (both inclusive).
-   */
-  static void _doSort(List a, int left, int right, int compare(a, b)) {
-    if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
-      insertionSort_(a, left, right, compare);
-    } else {
-      _dualPivotQuicksort(a, left, right, compare);
-    }
-  }
-
-  static void insertionSort_(List a, int left, int right, int compare(a, b)) {
-    for (int i = left + 1; i <= right; i++) {
-      var el = a[i];
-      int j = i;
-      while ((j > left) && (compare(a[j - 1], el) > 0)) {
-        a[j] = a[j - 1];
-        j--;
-      }
-      a[j] = el;
-    }
-  }
-
-  static void _dualPivotQuicksort(List a,
-                                  int left, int right,
-                                  int compare(a, b)) {
-    assert(right - left > _INSERTION_SORT_THRESHOLD);
-
-    // Compute the two pivots by looking at 5 elements.
-    int sixth = (right - left + 1) ~/ 6;
-    int index1 = left + sixth;
-    int index5 = right - sixth;
-    int index3 = (left + right) ~/ 2;  // The midpoint.
-    int index2 = index3 - sixth;
-    int index4 = index3 + sixth;
-
-    var el1 = a[index1];
-    var el2 = a[index2];
-    var el3 = a[index3];
-    var el4 = a[index4];
-    var el5 = a[index5];
-
-    // Sort the selected 5 elements using a sorting network.
-    if (compare(el1, el2) > 0) { var t = el1; el1 = el2; el2 = t; }
-    if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; }
-    if (compare(el1, el3) > 0) { var t = el1; el1 = el3; el3 = t; }
-    if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; }
-    if (compare(el1, el4) > 0) { var t = el1; el1 = el4; el4 = t; }
-    if (compare(el3, el4) > 0) { var t = el3; el3 = el4; el4 = t; }
-    if (compare(el2, el5) > 0) { var t = el2; el2 = el5; el5 = t; }
-    if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; }
-    if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; }
-
-    var pivot1 = el2;
-    var pivot2 = el4;
-
-    // el2 and el4 have been saved in the pivot variables. They will be written
-    // back, once the partioning is finished.
-    a[index1] = el1;
-    a[index3] = el3;
-    a[index5] = el5;
-
-    a[index2] = a[left];
-    a[index4] = a[right];
-
-    int less = left + 1;    // First element in the middle partition.
-    int great = right - 1;  // Last element in the middle partition.
-
-    bool pivots_are_equal = (compare(pivot1, pivot2) == 0);
-    if (pivots_are_equal) {
-      var pivot = pivot1;
-      // Degenerated case where the partioning becomes a dutch national flag
-      // problem.
-      //
-      // [ |  < pivot  | == pivot | unpartitioned | > pivot  | ]
-      //  ^             ^          ^             ^            ^
-      // left         less         k           great         right
-      //
-      // a[left] and a[right] are undefined and are filled after the
-      // partitioning.
-      //
-      // Invariants:
-      //   1) for x in ]left, less[ : x < pivot.
-      //   2) for x in [less, k[ : x == pivot.
-      //   3) for x in ]great, right[ : x > pivot.
-      for (int k = less; k <= great; k++) {
-        var ak = a[k];
-        int comp = compare(ak, pivot);
-        if (comp == 0) continue;
-        if (comp < 0) {
-          if (k != less) {
-            a[k] = a[less];
-            a[less] = ak;
-          }
-          less++;
-        } else {
-          // comp > 0.
-          //
-          // Find the first element <= pivot in the range [k - 1, great] and
-          // put [:ak:] there. We know that such an element must exist:
-          // When k == less, then el3 (which is equal to pivot) lies in the
-          // interval. Otherwise a[k - 1] == pivot and the search stops at k-1.
-          // Note that in the latter case invariant 2 will be violated for a
-          // short amount of time. The invariant will be restored when the
-          // pivots are put into their final positions.
-          while (true) {
-            comp = compare(a[great], pivot);
-            if (comp > 0) {
-              great--;
-              // This is the only location in the while-loop where a new
-              // iteration is started.
-              continue;
-            } else if (comp < 0) {
-              // Triple exchange.
-              a[k] = a[less];
-              a[less++] = a[great];
-              a[great--] = ak;
-              break;
-            } else {
-              // comp == 0;
-              a[k] = a[great];
-              a[great--] = ak;
-              // Note: if great < k then we will exit the outer loop and fix
-              // invariant 2 (which we just violated).
-              break;
-            }
-          }
-        }
-      }
-    } else {
-      // We partition the list into three parts:
-      //  1. < pivot1
-      //  2. >= pivot1 && <= pivot2
-      //  3. > pivot2
-      //
-      // During the loop we have:
-      // [ | < pivot1 | >= pivot1 && <= pivot2 | unpartitioned  | > pivot2  | ]
-      //  ^            ^                        ^              ^             ^
-      // left         less                     k              great        right
-      //
-      // a[left] and a[right] are undefined and are filled after the
-      // partitioning.
-      //
-      // Invariants:
-      //   1. for x in ]left, less[ : x < pivot1
-      //   2. for x in [less, k[ : pivot1 <= x && x <= pivot2
-      //   3. for x in ]great, right[ : x > pivot2
-      for (int k = less; k <= great; k++) {
-        var ak = a[k];
-        int comp_pivot1 = compare(ak, pivot1);
-        if (comp_pivot1 < 0) {
-          if (k != less) {
-            a[k] = a[less];
-            a[less] = ak;
-          }
-          less++;
-        } else {
-          int comp_pivot2 = compare(ak, pivot2);
-          if (comp_pivot2 > 0) {
-            while (true) {
-              int comp = compare(a[great], pivot2);
-              if (comp > 0) {
-                great--;
-                if (great < k) break;
-                // This is the only location inside the loop where a new
-                // iteration is started.
-                continue;
-              } else {
-                // a[great] <= pivot2.
-                comp = compare(a[great], pivot1);
-                if (comp < 0) {
-                  // Triple exchange.
-                  a[k] = a[less];
-                  a[less++] = a[great];
-                  a[great--] = ak;
-                } else {
-                  // a[great] >= pivot1.
-                  a[k] = a[great];
-                  a[great--] = ak;
-                }
-                break;
-              }
-            }
-          }
-        }
-      }
-    }
-
-    // Move pivots into their final positions.
-    // We shrunk the list from both sides (a[left] and a[right] have
-    // meaningless values in them) and now we move elements from the first
-    // and third partition into these locations so that we can store the
-    // pivots.
-    a[left] = a[less - 1];
-    a[less - 1] = pivot1;
-    a[right] = a[great + 1];
-    a[great + 1] = pivot2;
-
-    // The list is now partitioned into three partitions:
-    // [ < pivot1   | >= pivot1 && <= pivot2   |  > pivot2   ]
-    //  ^            ^                        ^             ^
-    // left         less                     great        right
-
-    // Recursive descent. (Don't include the pivot values.)
-    _doSort(a, left, less - 2, compare);
-    _doSort(a, great + 2, right, compare);
-
-    if (pivots_are_equal) {
-      // All elements in the second partition are equal to the pivot. No
-      // need to sort them.
-      return;
-    }
-
-    // In theory it should be enough to call _doSort recursively on the second
-    // partition.
-    // The Android source however removes the pivot elements from the recursive
-    // call if the second partition is too large (more than 2/3 of the list).
-    if (less < index1 && great > index5) {
-      while (compare(a[less], pivot1) == 0) { less++; }
-      while (compare(a[great], pivot2) == 0) { great--; }
-
-      // Copy paste of the previous 3-way partitioning with adaptions.
-      //
-      // We partition the list into three parts:
-      //  1. == pivot1
-      //  2. > pivot1 && < pivot2
-      //  3. == pivot2
-      //
-      // During the loop we have:
-      // [ == pivot1 | > pivot1 && < pivot2 | unpartitioned  | == pivot2 ]
-      //              ^                      ^              ^
-      //            less                     k              great
-      //
-      // Invariants:
-      //   1. for x in [ *, less[ : x == pivot1
-      //   2. for x in [less, k[ : pivot1 < x && x < pivot2
-      //   3. for x in ]great, * ] : x == pivot2
-      for (int k = less; k <= great; k++) {
-        var ak = a[k];
-        int comp_pivot1 = compare(ak, pivot1);
-        if (comp_pivot1 == 0) {
-          if (k != less) {
-            a[k] = a[less];
-            a[less] = ak;
-          }
-          less++;
-        } else {
-          int comp_pivot2 = compare(ak, pivot2);
-          if (comp_pivot2 == 0) {
-            while (true) {
-              int comp = compare(a[great], pivot2);
-              if (comp == 0) {
-                great--;
-                if (great < k) break;
-                // This is the only location inside the loop where a new
-                // iteration is started.
-                continue;
-              } else {
-                // a[great] < pivot2.
-                comp = compare(a[great], pivot1);
-                if (comp < 0) {
-                  // Triple exchange.
-                  a[k] = a[less];
-                  a[less++] = a[great];
-                  a[great--] = ak;
-                } else {
-                  // a[great] == pivot1.
-                  a[k] = a[great];
-                  a[great--] = ak;
-                }
-                break;
-              }
-            }
-          }
-        }
-      }
-      // The second partition has now been cleared of pivot elements and looks
-      // as follows:
-      // [  *  |  > pivot1 && < pivot2  | * ]
-      //        ^                      ^
-      //       less                  great
-      // Sort the second partition using recursive descent.
-      _doSort(a, less, great, compare);
-    } else {
-      // The second partition looks as follows:
-      // [  *  |  >= pivot1 && <= pivot2  | * ]
-      //        ^                        ^
-      //       less                    great
-      // Simply sort it by recursive descent.
-      _doSort(a, less, great, compare);
-    }
-  }
-}