| Index: test/dart_codegen/expect/_internal/sort.dart
|
| diff --git a/test/dart_codegen/expect/_internal/sort.dart b/test/dart_codegen/expect/_internal/sort.dart
|
| deleted file mode 100644
|
| index 46dc9bbb3077671d798db44435fc35da1e356a55..0000000000000000000000000000000000000000
|
| --- a/test/dart_codegen/expect/_internal/sort.dart
|
| +++ /dev/null
|
| @@ -1,230 +0,0 @@
|
| -part of dart._internal;
|
| - class Sort {static const int _INSERTION_SORT_THRESHOLD = 32;
|
| - static void sort(List a, int compare(a, b)) {
|
| - _doSort(a, 0, a.length - 1, compare);
|
| - }
|
| - 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);
|
| - }
|
| - 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); int sixth = (right - left + 1) ~/ 6;
|
| - int index1 = left + sixth;
|
| - int index5 = right - sixth;
|
| - int index3 = (left + right) ~/ 2;
|
| - 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];
|
| - 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;
|
| - a[index1] = el1;
|
| - a[index3] = el3;
|
| - a[index5] = el5;
|
| - a[index2] = a[left];
|
| - a[index4] = a[right];
|
| - int less = left + 1;
|
| - int great = right - 1;
|
| - bool pivots_are_equal = (compare(pivot1, pivot2) == 0);
|
| - if (pivots_are_equal) {
|
| - var pivot = pivot1;
|
| - 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 {
|
| - while (true) {
|
| - comp = compare(a[great], pivot);
|
| - if (comp > 0) {
|
| - great--;
|
| - continue;
|
| - }
|
| - else if (comp < 0) {
|
| - a[k] = a[less];
|
| - a[less++] = a[great];
|
| - a[great--] = ak;
|
| - break;
|
| - }
|
| - else {
|
| - a[k] = a[great];
|
| - a[great--] = ak;
|
| - break;
|
| - }
|
| - }
|
| - }
|
| - }
|
| - }
|
| - else {
|
| - 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;
|
| - continue;
|
| - }
|
| - else {
|
| - comp = compare(a[great], pivot1);
|
| - if (comp < 0) {
|
| - a[k] = a[less];
|
| - a[less++] = a[great];
|
| - a[great--] = ak;
|
| - }
|
| - else {
|
| - a[k] = a[great];
|
| - a[great--] = ak;
|
| - }
|
| - break;
|
| - }
|
| - }
|
| - }
|
| - }
|
| - }
|
| - }
|
| - a[left] = a[less - 1];
|
| - a[less - 1] = pivot1;
|
| - a[right] = a[great + 1];
|
| - a[great + 1] = pivot2;
|
| - _doSort(a, left, less - 2, compare);
|
| - _doSort(a, great + 2, right, compare);
|
| - if (pivots_are_equal) {
|
| - return;}
|
| - if (less < index1 && great > index5) {
|
| - while (compare(a[less], pivot1) == 0) {
|
| - less++;
|
| - }
|
| - while (compare(a[great], pivot2) == 0) {
|
| - great--;
|
| - }
|
| - 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;
|
| - continue;
|
| - }
|
| - else {
|
| - comp = compare(a[great], pivot1);
|
| - if (comp < 0) {
|
| - a[k] = a[less];
|
| - a[less++] = a[great];
|
| - a[great--] = ak;
|
| - }
|
| - else {
|
| - a[k] = a[great];
|
| - a[great--] = ak;
|
| - }
|
| - break;
|
| - }
|
| - }
|
| - }
|
| - }
|
| - }
|
| - _doSort(a, less, great, compare);
|
| - }
|
| - else {
|
| - _doSort(a, less, great, compare);
|
| - }
|
| - }
|
| -}
|
|
|