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

Side by Side Diff: sdk/lib/collection_dev/sort.dart

Issue 11938036: Hide collection-dev library. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Allow dart:_collection-dev in dartc. Other fixes. Created 7 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 unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « sdk/lib/collection_dev/list.dart ('k') | sdk/lib/collection_dev/to_string.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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 part of dart.collection.dev;
6
7 /**
8 * Dual-Pivot Quicksort algorithm.
9 *
10 * This class implements the dual-pivot quicksort algorithm as presented in
11 * Vladimir Yaroslavskiy's paper.
12 *
13 * Some improvements have been copied from Android's implementation.
14 */
15 class Sort {
16 // When a list has less then [:_INSERTION_SORT_THRESHOLD:] elements it will
17 // be sorted by an insertion sort.
18 static const int _INSERTION_SORT_THRESHOLD = 32;
19
20 /**
21 * Sorts all elements of the given list [:a:] according to the given
22 * [:compare:] function.
23 *
24 * The [:compare:] function takes two arguments [:x:] and [:y:] and returns
25 * -1 if [:x < y:],
26 * 0 if [:x == y:], and
27 * 1 if [:x > y:].
28 *
29 * The function's behavior must be consistent. It must not return different
30 * results for the same values.
31 */
32 static void sort(List a, int compare(a, b)) {
33 _doSort(a, 0, a.length - 1, compare);
34 }
35
36 /**
37 * Sorts all elements in the range [:from:] (inclusive) to [:to:] (exclusive)
38 * of the given list [:a:].
39 *
40 * If the given range is invalid an "OutOfRange" error is raised.
41 * TODO(floitsch): do we want an error?
42 *
43 * See [:sort:] for requirements of the [:compare:] function.
44 */
45 static void sortRange(List a, int from, int to, int compare(a, b)) {
46 if ((from < 0) || (to > a.length) || (to < from)) {
47 throw "OutOfRange";
48 }
49 _doSort(a, from, to - 1, compare);
50 }
51
52 /**
53 * Sorts the list in the interval [:left:] to [:right:] (both inclusive).
54 */
55 static void _doSort(List a, int left, int right, int compare(a, b)) {
56 if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
57 insertionSort_(a, left, right, compare);
58 } else {
59 _dualPivotQuicksort(a, left, right, compare);
60 }
61 }
62
63 static void insertionSort_(List a, int left, int right, int compare(a, b)) {
64 for (int i = left + 1; i <= right; i++) {
65 var el = a[i];
66 int j = i;
67 while ((j > left) && (compare(a[j - 1], el) > 0)) {
68 a[j] = a[j - 1];
69 j--;
70 }
71 a[j] = el;
72 }
73 }
74
75 static void _dualPivotQuicksort(List a,
76 int left, int right,
77 int compare(a, b)) {
78 assert(right - left > _INSERTION_SORT_THRESHOLD);
79
80 // Compute the two pivots by looking at 5 elements.
81 int sixth = (right - left + 1) ~/ 6;
82 int index1 = left + sixth;
83 int index5 = right - sixth;
84 int index3 = (left + right) ~/ 2; // The midpoint.
85 int index2 = index3 - sixth;
86 int index4 = index3 + sixth;
87
88 var el1 = a[index1];
89 var el2 = a[index2];
90 var el3 = a[index3];
91 var el4 = a[index4];
92 var el5 = a[index5];
93
94 // Sort the selected 5 elements using a sorting network.
95 if (compare(el1, el2) > 0) { var t = el1; el1 = el2; el2 = t; }
96 if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; }
97 if (compare(el1, el3) > 0) { var t = el1; el1 = el3; el3 = t; }
98 if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; }
99 if (compare(el1, el4) > 0) { var t = el1; el1 = el4; el4 = t; }
100 if (compare(el3, el4) > 0) { var t = el3; el3 = el4; el4 = t; }
101 if (compare(el2, el5) > 0) { var t = el2; el2 = el5; el5 = t; }
102 if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; }
103 if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; }
104
105 var pivot1 = el2;
106 var pivot2 = el4;
107
108 // el2 and el4 have been saved in the pivot variables. They will be written
109 // back, once the partioning is finished.
110 a[index1] = el1;
111 a[index3] = el3;
112 a[index5] = el5;
113
114 a[index2] = a[left];
115 a[index4] = a[right];
116
117 int less = left + 1; // First element in the middle partition.
118 int great = right - 1; // Last element in the middle partition.
119
120 bool pivots_are_equal = (compare(pivot1, pivot2) == 0);
121 if (pivots_are_equal) {
122 var pivot = pivot1;
123 // Degenerated case where the partioning becomes a dutch national flag
124 // problem.
125 //
126 // [ | < pivot | == pivot | unpartitioned | > pivot | ]
127 // ^ ^ ^ ^ ^
128 // left less k great right
129 //
130 // a[left] and a[right] are undefined and are filled after the
131 // partitioning.
132 //
133 // Invariants:
134 // 1) for x in ]left, less[ : x < pivot.
135 // 2) for x in [less, k[ : x == pivot.
136 // 3) for x in ]great, right[ : x > pivot.
137 for (int k = less; k <= great; k++) {
138 var ak = a[k];
139 int comp = compare(ak, pivot);
140 if (comp == 0) continue;
141 if (comp < 0) {
142 if (k != less) {
143 a[k] = a[less];
144 a[less] = ak;
145 }
146 less++;
147 } else {
148 // comp > 0.
149 //
150 // Find the first element <= pivot in the range [k - 1, great] and
151 // put [:ak:] there. We know that such an element must exist:
152 // When k == less, then el3 (which is equal to pivot) lies in the
153 // interval. Otherwise a[k - 1] == pivot and the search stops at k-1.
154 // Note that in the latter case invariant 2 will be violated for a
155 // short amount of time. The invariant will be restored when the
156 // pivots are put into their final positions.
157 while (true) {
158 comp = compare(a[great], pivot);
159 if (comp > 0) {
160 great--;
161 // This is the only location in the while-loop where a new
162 // iteration is started.
163 continue;
164 } else if (comp < 0) {
165 // Triple exchange.
166 a[k] = a[less];
167 a[less++] = a[great];
168 a[great--] = ak;
169 break;
170 } else {
171 // comp == 0;
172 a[k] = a[great];
173 a[great--] = ak;
174 // Note: if great < k then we will exit the outer loop and fix
175 // invariant 2 (which we just violated).
176 break;
177 }
178 }
179 }
180 }
181 } else {
182 // We partition the list into three parts:
183 // 1. < pivot1
184 // 2. >= pivot1 && <= pivot2
185 // 3. > pivot2
186 //
187 // During the loop we have:
188 // [ | < pivot1 | >= pivot1 && <= pivot2 | unpartitioned | > pivot2 | ]
189 // ^ ^ ^ ^ ^
190 // left less k great right
191 //
192 // a[left] and a[right] are undefined and are filled after the
193 // partitioning.
194 //
195 // Invariants:
196 // 1. for x in ]left, less[ : x < pivot1
197 // 2. for x in [less, k[ : pivot1 <= x && x <= pivot2
198 // 3. for x in ]great, right[ : x > pivot2
199 for (int k = less; k <= great; k++) {
200 var ak = a[k];
201 int comp_pivot1 = compare(ak, pivot1);
202 if (comp_pivot1 < 0) {
203 if (k != less) {
204 a[k] = a[less];
205 a[less] = ak;
206 }
207 less++;
208 } else {
209 int comp_pivot2 = compare(ak, pivot2);
210 if (comp_pivot2 > 0) {
211 while (true) {
212 int comp = compare(a[great], pivot2);
213 if (comp > 0) {
214 great--;
215 if (great < k) break;
216 // This is the only location inside the loop where a new
217 // iteration is started.
218 continue;
219 } else {
220 // a[great] <= pivot2.
221 comp = compare(a[great], pivot1);
222 if (comp < 0) {
223 // Triple exchange.
224 a[k] = a[less];
225 a[less++] = a[great];
226 a[great--] = ak;
227 } else {
228 // a[great] >= pivot1.
229 a[k] = a[great];
230 a[great--] = ak;
231 }
232 break;
233 }
234 }
235 }
236 }
237 }
238 }
239
240 // Move pivots into their final positions.
241 // We shrunk the list from both sides (a[left] and a[right] have
242 // meaningless values in them) and now we move elements from the first
243 // and third partition into these locations so that we can store the
244 // pivots.
245 a[left] = a[less - 1];
246 a[less - 1] = pivot1;
247 a[right] = a[great + 1];
248 a[great + 1] = pivot2;
249
250 // The list is now partitioned into three partitions:
251 // [ < pivot1 | >= pivot1 && <= pivot2 | > pivot2 ]
252 // ^ ^ ^ ^
253 // left less great right
254
255 // Recursive descent. (Don't include the pivot values.)
256 _doSort(a, left, less - 2, compare);
257 _doSort(a, great + 2, right, compare);
258
259 if (pivots_are_equal) {
260 // All elements in the second partition are equal to the pivot. No
261 // need to sort them.
262 return;
263 }
264
265 // In theory it should be enough to call _doSort recursively on the second
266 // partition.
267 // The Android source however removes the pivot elements from the recursive
268 // call if the second partition is too large (more than 2/3 of the list).
269 if (less < index1 && great > index5) {
270 while (compare(a[less], pivot1) == 0) { less++; }
271 while (compare(a[great], pivot2) == 0) { great--; }
272
273 // Copy paste of the previous 3-way partitioning with adaptions.
274 //
275 // We partition the list into three parts:
276 // 1. == pivot1
277 // 2. > pivot1 && < pivot2
278 // 3. == pivot2
279 //
280 // During the loop we have:
281 // [ == pivot1 | > pivot1 && < pivot2 | unpartitioned | == pivot2 ]
282 // ^ ^ ^
283 // less k great
284 //
285 // Invariants:
286 // 1. for x in [ *, less[ : x == pivot1
287 // 2. for x in [less, k[ : pivot1 < x && x < pivot2
288 // 3. for x in ]great, * ] : x == pivot2
289 for (int k = less; k <= great; k++) {
290 var ak = a[k];
291 int comp_pivot1 = compare(ak, pivot1);
292 if (comp_pivot1 == 0) {
293 if (k != less) {
294 a[k] = a[less];
295 a[less] = ak;
296 }
297 less++;
298 } else {
299 int comp_pivot2 = compare(ak, pivot2);
300 if (comp_pivot2 == 0) {
301 while (true) {
302 int comp = compare(a[great], pivot2);
303 if (comp == 0) {
304 great--;
305 if (great < k) break;
306 // This is the only location inside the loop where a new
307 // iteration is started.
308 continue;
309 } else {
310 // a[great] < pivot2.
311 comp = compare(a[great], pivot1);
312 if (comp < 0) {
313 // Triple exchange.
314 a[k] = a[less];
315 a[less++] = a[great];
316 a[great--] = ak;
317 } else {
318 // a[great] == pivot1.
319 a[k] = a[great];
320 a[great--] = ak;
321 }
322 break;
323 }
324 }
325 }
326 }
327 }
328 // The second partition has now been cleared of pivot elements and looks
329 // as follows:
330 // [ * | > pivot1 && < pivot2 | * ]
331 // ^ ^
332 // less great
333 // Sort the second partition using recursive descent.
334 _doSort(a, less, great, compare);
335 } else {
336 // The second partition looks as follows:
337 // [ * | >= pivot1 && <= pivot2 | * ]
338 // ^ ^
339 // less great
340 // Simply sort it by recursive descent.
341 _doSort(a, less, great, compare);
342 }
343 }
344 }
OLDNEW
« no previous file with comments | « sdk/lib/collection_dev/list.dart ('k') | sdk/lib/collection_dev/to_string.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698