OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. |
| 4 |
| 5 library sort_helper; |
| 6 import "package:expect/expect.dart"; |
| 7 |
| 8 class SortHelper { |
| 9 |
| 10 SortHelper(this.sortFunction, this.compareFunction) {} |
| 11 |
| 12 void run() { |
| 13 testSortIntLists(); |
| 14 testSortDoubleLists(); |
| 15 } |
| 16 |
| 17 bool isSorted(List a) { |
| 18 for (int i = 1; i < a.length; i++) { |
| 19 if (compareFunction(a[i - 1], a[i]) > 0) { |
| 20 return false; |
| 21 } |
| 22 } |
| 23 return true; |
| 24 } |
| 25 |
| 26 void testSortIntLists() { |
| 27 List a = new List(40); |
| 28 |
| 29 for (int i = 0; i < a.length; i++) { |
| 30 a[i] = i; |
| 31 } |
| 32 testSort(a); |
| 33 |
| 34 for (int i = 0; i < a.length; i++) { |
| 35 a[a.length - i - 1] = i; |
| 36 } |
| 37 testSort(a); |
| 38 |
| 39 for (int i = 0; i < 21; i++) { |
| 40 a[i] = 1; |
| 41 } |
| 42 for (int i = 21; i < a.length; i++) { |
| 43 a[i] = 2; |
| 44 } |
| 45 testSort(a); |
| 46 |
| 47 // Same with bad pivot-choices. |
| 48 for (int i = 0; i < 21; i++) { |
| 49 a[i] = 1; |
| 50 } |
| 51 for (int i = 21; i < a.length; i++) { |
| 52 a[i] = 2; |
| 53 } |
| 54 a[6] = 1; |
| 55 a[13] = 1; |
| 56 a[19] = 1; |
| 57 a[25] = 1; |
| 58 a[33] = 2; |
| 59 testSort(a); |
| 60 |
| 61 for (int i = 0; i < 21; i++) { |
| 62 a[i] = 2; |
| 63 } |
| 64 for (int i = 21; i < a.length; i++) { |
| 65 a[i] = 1; |
| 66 } |
| 67 testSort(a); |
| 68 |
| 69 // Same with bad pivot-choices. |
| 70 for (int i = 0; i < 21; i++) { |
| 71 a[i] = 2; |
| 72 } |
| 73 for (int i = 21; i < a.length; i++) { |
| 74 a[i] = 1; |
| 75 } |
| 76 a[6] = 2; |
| 77 a[13] = 2; |
| 78 a[19] = 2; |
| 79 a[25] = 2; |
| 80 a[33] = 1; |
| 81 testSort(a); |
| 82 |
| 83 var a2 = new List(0); |
| 84 testSort(a2); |
| 85 |
| 86 var a3 = new List(1); |
| 87 a3[0] = 1; |
| 88 testSort(a3); |
| 89 |
| 90 // -------- |
| 91 // Test insertion sort. |
| 92 testInsertionSort(0, 1, 2, 3); |
| 93 testInsertionSort(0, 1, 3, 2); |
| 94 testInsertionSort(0, 3, 2, 1); |
| 95 testInsertionSort(0, 3, 1, 2); |
| 96 testInsertionSort(0, 2, 1, 3); |
| 97 testInsertionSort(0, 2, 3, 1); |
| 98 testInsertionSort(1, 0, 2, 3); |
| 99 testInsertionSort(1, 0, 3, 2); |
| 100 testInsertionSort(1, 2, 3, 0); |
| 101 testInsertionSort(1, 2, 0, 3); |
| 102 testInsertionSort(1, 3, 2, 0); |
| 103 testInsertionSort(1, 3, 0, 2); |
| 104 testInsertionSort(2, 0, 1, 3); |
| 105 testInsertionSort(2, 0, 3, 1); |
| 106 testInsertionSort(2, 1, 3, 0); |
| 107 testInsertionSort(2, 1, 0, 3); |
| 108 testInsertionSort(2, 3, 1, 0); |
| 109 testInsertionSort(2, 3, 0, 1); |
| 110 testInsertionSort(3, 0, 1, 2); |
| 111 testInsertionSort(3, 0, 2, 1); |
| 112 testInsertionSort(3, 1, 2, 0); |
| 113 testInsertionSort(3, 1, 0, 2); |
| 114 testInsertionSort(3, 2, 1, 0); |
| 115 testInsertionSort(3, 2, 0, 1); |
| 116 } |
| 117 |
| 118 void testSort(List a) { |
| 119 sortFunction(a); |
| 120 Expect.isTrue(isSorted(a)); |
| 121 } |
| 122 |
| 123 void testInsertionSort(int i1, int i2, int i3, int i4) { |
| 124 var a = new List(4); |
| 125 a[0] = i1; |
| 126 a[1] = i2; |
| 127 a[2] = i3; |
| 128 a[3] = i4; |
| 129 testSort(a); |
| 130 } |
| 131 |
| 132 void testSortDoubleLists() { |
| 133 List a = new List(40); |
| 134 for (int i = 0; i < a.length; i++) { |
| 135 a[i] = 1.0 * i + 0.5; |
| 136 } |
| 137 testSort(a); |
| 138 |
| 139 for (int i = 0; i < a.length; i++) { |
| 140 a[i] = 1.0 * (a.length - i) + 0.5; |
| 141 } |
| 142 testSort(a); |
| 143 |
| 144 for (int i = 0; i < a.length; i++) { |
| 145 a[i] = 1.5; |
| 146 } |
| 147 testSort(a); |
| 148 } |
| 149 |
| 150 Function sortFunction; |
| 151 Function compareFunction; |
| 152 } |
OLD | NEW |