Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(32)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: pkg/dev_compiler/tool/input_sdk/lib/internal/sort.dart

Issue 2698353003: unfork DDC's copy of most SDK libraries (Closed)
Patch Set: revert core_patch Created 3 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « pkg/dev_compiler/tool/input_sdk/lib/internal/print.dart ('k') | pkg/dev_compiler/tool/input_sdk/lib/internal/symbol.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: pkg/dev_compiler/tool/input_sdk/lib/internal/sort.dart
diff --git a/pkg/dev_compiler/tool/input_sdk/lib/internal/sort.dart b/pkg/dev_compiler/tool/input_sdk/lib/internal/sort.dart
deleted file mode 100644
index 63037ea4d6388bad057aec257d0db30247540ddc..0000000000000000000000000000000000000000
--- a/pkg/dev_compiler/tool/input_sdk/lib/internal/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._internal;
-
-/**
- * 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/*<E>*/(List/*<E>*/ a, int compare(dynamic /*=E*/ a, dynamic /*=E*/ 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/*<E>*/(List/*<E>*/ a, int from, int to, int compare(dynamic /*=E*/ a, dynamic /*=E*/ 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/*<E>*/(List/*<E>*/ a, int left, int right, int compare(dynamic /*=E*/ a, dynamic /*=E*/ b)) {
- if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
- _insertionSort(a, left, right, compare);
- } else {
- _dualPivotQuicksort(a, left, right, compare);
- }
- }
-
- static void _insertionSort/*<E>*/(List/*<E>*/ a, int left, int right, int compare(dynamic /*=E*/ a, dynamic /*=E*/ 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/*<E>*/(List/*<E>*/ a,
- int left, int right,
- int compare(dynamic /*=E*/ a, dynamic /*=E*/ 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);
- }
- }
-}
« no previous file with comments | « pkg/dev_compiler/tool/input_sdk/lib/internal/print.dart ('k') | pkg/dev_compiler/tool/input_sdk/lib/internal/symbol.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698