OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 /** | 5 /// Import `collection.dart` instead. |
6 * Operations on collections. | 6 @Deprecated("Will be removed in collection 2.0.0.") |
7 */ | |
8 library dart.pkg.collection.algorithms; | 7 library dart.pkg.collection.algorithms; |
9 | 8 |
10 import "dart:math" show Random; | 9 export "src/algorithms.dart"; |
11 | |
12 /** Version of [binarySearch] optimized for comparable keys */ | |
13 int _comparableBinarySearch(List<Comparable> list, Comparable value) { | |
14 int min = 0; | |
15 int max = list.length; | |
16 while (min < max) { | |
17 int mid = min + ((max - min) >> 1); | |
18 var element = list[mid]; | |
19 int comp = element.compareTo(value); | |
20 if (comp == 0) return mid; | |
21 if (comp < 0) { | |
22 min = mid + 1; | |
23 } else { | |
24 max = mid; | |
25 } | |
26 } | |
27 return -1; | |
28 } | |
29 | |
30 /** | |
31 * Returns a position of the [value] in [sortedList], if it is there. | |
32 * | |
33 * If the list isn't sorted according to the [compare] function, the result | |
34 * is unpredictable. | |
35 * | |
36 * If [compare] is omitted, it defaults to calling [Comparable.compareTo] on | |
37 * the objects. | |
38 * | |
39 * Returns -1 if [value] is not in the list by default. | |
40 */ | |
41 int binarySearch(List sortedList, value, { int compare(a, b) }) { | |
42 if (compare == null) { | |
43 return _comparableBinarySearch(sortedList, value); | |
44 } | |
45 int min = 0; | |
46 int max = sortedList.length; | |
47 while (min < max) { | |
48 int mid = min + ((max - min) >> 1); | |
49 var element = sortedList[mid]; | |
50 int comp = compare(element, value); | |
51 if (comp == 0) return mid; | |
52 if (comp < 0) { | |
53 min = mid + 1; | |
54 } else { | |
55 max = mid; | |
56 } | |
57 } | |
58 return -1; | |
59 } | |
60 | |
61 /** Version of [lowerBound] optimized for comparable keys */ | |
62 int _comparableLowerBound(List<Comparable> list, Comparable value) { | |
63 int min = 0; | |
64 int max = list.length; | |
65 while (min < max) { | |
66 int mid = min + ((max - min) >> 1); | |
67 var element = list[mid]; | |
68 int comp = element.compareTo(value); | |
69 if (comp < 0) { | |
70 min = mid + 1; | |
71 } else { | |
72 max = mid; | |
73 } | |
74 } | |
75 return min; | |
76 } | |
77 | |
78 /** | |
79 * Returns the first position in [sortedList] that does not compare less than | |
80 * [value]. | |
81 * | |
82 * If the list isn't sorted according to the [compare] function, the result | |
83 * is unpredictable. | |
84 * | |
85 * If [compare] is omitted, it defaults to calling [Comparable.compareTo] on | |
86 * the objects. | |
87 * | |
88 * Returns [sortedList.length] if all the items in [sortedList] compare less | |
89 * than [value]. | |
90 */ | |
91 int lowerBound(List sortedList, value, { int compare(a, b) }) { | |
92 if (compare == null) { | |
93 return _comparableLowerBound(sortedList, value); | |
94 } | |
95 int min = 0; | |
96 int max = sortedList.length; | |
97 while (min < max) { | |
98 int mid = min + ((max - min) >> 1); | |
99 var element = sortedList[mid]; | |
100 int comp = compare(element, value); | |
101 if (comp < 0) { | |
102 min = mid + 1; | |
103 } else { | |
104 max = mid; | |
105 } | |
106 } | |
107 return min; | |
108 } | |
109 | |
110 /** | |
111 * Shuffles a list randomly. | |
112 * | |
113 * A sub-range of a list can be shuffled by providing [start] and [end]. | |
114 */ | |
115 void shuffle(List list, [int start = 0, int end = null]) { | |
116 Random random = new Random(); | |
117 if (end == null) end = list.length; | |
118 int length = end - start; | |
119 while (length > 1) { | |
120 int pos = random.nextInt(length); | |
121 length--; | |
122 var tmp1 = list[start + pos]; | |
123 list[start + pos] = list[start + length]; | |
124 list[start + length] = tmp1; | |
125 } | |
126 } | |
127 | |
128 | |
129 /** | |
130 * Reverses a list, or a part of a list, in-place. | |
131 */ | |
132 void reverse(List list, [int start = 0, int end = null]) { | |
133 if (end == null) end = list.length; | |
134 _reverse(list, start, end); | |
135 } | |
136 | |
137 // Internal helper function that assumes valid arguments. | |
138 void _reverse(List list, int start, int end) { | |
139 for (int i = start, j = end - 1; i < j; i++, j--) { | |
140 var tmp = list[i]; | |
141 list[i] = list[j]; | |
142 list[j] = tmp; | |
143 } | |
144 } | |
145 | |
146 /** | |
147 * Sort a list using insertion sort. | |
148 * | |
149 * Insertion sort is a simple sorting algorithm. For `n` elements it does on | |
150 * the order of `n * log(n)` comparisons but up to `n` squared moves. The | |
151 * sorting is performed in-place, without using extra memory. | |
152 * | |
153 * For short lists the many moves have less impact than the simple algorithm, | |
154 * and it is often the favored sorting algorithm for short lists. | |
155 * | |
156 * This insertion sort is stable: Equal elements end up in the same order | |
157 * as they started in. | |
158 */ | |
159 void insertionSort(List list, | |
160 { int compare(a, b), | |
161 int start: 0, | |
162 int end: null }) { | |
163 // If the same method could have both positional and named optional | |
164 // parameters, this should be (list, [start, end], {compare}). | |
165 if (end == null) end = list.length; | |
166 if (compare == null) compare = Comparable.compare; | |
167 _insertionSort(list, compare, start, end, start + 1); | |
168 } | |
169 | |
170 /** | |
171 * Internal helper function that assumes arguments correct. | |
172 * | |
173 * Assumes that the elements up to [sortedUntil] (not inclusive) are | |
174 * already sorted. The [sortedUntil] values should always be at least | |
175 * `start + 1`. | |
176 */ | |
177 void _insertionSort(List list, int compare(a, b), int start, int end, | |
178 int sortedUntil) { | |
179 for (int pos = sortedUntil; pos < end; pos++) { | |
180 int min = start; | |
181 int max = pos; | |
182 var element = list[pos]; | |
183 while (min < max) { | |
184 int mid = min + ((max - min) >> 1); | |
185 int comparison = compare(element, list[mid]); | |
186 if (comparison < 0) { | |
187 max = mid; | |
188 } else { | |
189 min = mid + 1; | |
190 } | |
191 } | |
192 list.setRange(min + 1, pos + 1, list, min); | |
193 list[min] = element; | |
194 } | |
195 } | |
196 | |
197 /** Limit below which merge sort defaults to insertion sort. */ | |
198 const int _MERGE_SORT_LIMIT = 32; | |
199 | |
200 /** | |
201 * Sorts a list, or a range of a list, using the merge sort algorithm. | |
202 * | |
203 * Merge-sorting works by splitting the job into two parts, sorting each | |
204 * recursively, and then merging the two sorted parts. | |
205 * | |
206 * This takes on the order of `n * log(n)` comparisons and moves to sort | |
207 * `n` elements, but requires extra space of about the same size as the list | |
208 * being sorted. | |
209 * | |
210 * This merge sort is stable: Equal elements end up in the same order | |
211 * as they started in. | |
212 */ | |
213 void mergeSort(List list, {int start: 0, int end: null, int compare(a, b)}) { | |
214 if (end == null) end = list.length; | |
215 if (compare == null) compare = Comparable.compare; | |
216 int length = end - start; | |
217 if (length < 2) return; | |
218 if (length < _MERGE_SORT_LIMIT) { | |
219 _insertionSort(list, compare, start, end, start + 1); | |
220 return; | |
221 } | |
222 // Special case the first split instead of directly calling | |
223 // _mergeSort, because the _mergeSort requires its target to | |
224 // be different from its source, and it requires extra space | |
225 // of the same size as the list to sort. | |
226 // This split allows us to have only half as much extra space, | |
227 // and it ends up in the original place. | |
228 int middle = start + ((end - start) >> 1); | |
229 int firstLength = middle - start; | |
230 int secondLength = end - middle; | |
231 // secondLength is always the same as firstLength, or one greater. | |
232 List scratchSpace = new List(secondLength); | |
233 _mergeSort(list, compare, middle, end, scratchSpace, 0); | |
234 int firstTarget = end - firstLength; | |
235 _mergeSort(list, compare, start, middle, list, firstTarget); | |
236 _merge(compare, | |
237 list, firstTarget, end, | |
238 scratchSpace, 0, secondLength, | |
239 list, start); | |
240 } | |
241 | |
242 /** | |
243 * Performs an insertion sort into a potentially different list than the | |
244 * one containing the original values. | |
245 * | |
246 * It will work in-place as well. | |
247 */ | |
248 void _movingInsertionSort(List list, int compare(a, b), int start, int end, | |
249 List target, int targetOffset) { | |
250 int length = end - start; | |
251 if (length == 0) return; | |
252 target[targetOffset] = list[start]; | |
253 for (int i = 1; i < length; i++) { | |
254 var element = list[start + i]; | |
255 int min = targetOffset; | |
256 int max = targetOffset + i; | |
257 while (min < max) { | |
258 int mid = min + ((max - min) >> 1); | |
259 if (compare(element, target[mid]) < 0) { | |
260 max = mid; | |
261 } else { | |
262 min = mid + 1; | |
263 } | |
264 } | |
265 target.setRange(min + 1, targetOffset + i + 1, | |
266 target, min); | |
267 target[min] = element; | |
268 } | |
269 } | |
270 | |
271 /** | |
272 * Sorts [list] from [start] to [end] into [target] at [targetOffset]. | |
273 * | |
274 * The `target` list must be able to contain the range from `start` to `end` | |
275 * after `targetOffset`. | |
276 * | |
277 * Allows target to be the same list as [list], as long as it's not | |
278 * overlapping the `start..end` range. | |
279 */ | |
280 void _mergeSort(List list, int compare(a, b), int start, int end, | |
281 List target, int targetOffset) { | |
282 int length = end - start; | |
283 if (length < _MERGE_SORT_LIMIT) { | |
284 _movingInsertionSort(list, compare, start, end, target, targetOffset); | |
285 return; | |
286 } | |
287 int middle = start + (length >> 1); | |
288 int firstLength = middle - start; | |
289 int secondLength = end - middle; | |
290 // Here secondLength >= firstLength (differs by at most one). | |
291 int targetMiddle = targetOffset + firstLength; | |
292 // Sort the second half into the end of the target area. | |
293 _mergeSort(list, compare, middle, end, | |
294 target, targetMiddle); | |
295 // Sort the first half into the end of the source area. | |
296 _mergeSort(list, compare, start, middle, | |
297 list, middle); | |
298 // Merge the two parts into the target area. | |
299 _merge(compare, | |
300 list, middle, middle + firstLength, | |
301 target, targetMiddle, targetMiddle + secondLength, | |
302 target, targetOffset); | |
303 } | |
304 | |
305 /** | |
306 * Merges two lists into a target list. | |
307 * | |
308 * One of the input lists may be positioned at the end of the target | |
309 * list. | |
310 * | |
311 * For equal object, elements from [firstList] are always preferred. | |
312 * This allows the merge to be stable if the first list contains elements | |
313 * that started out earlier than the ones in [secondList] | |
314 */ | |
315 void _merge(int compare(a, b), | |
316 List firstList, int firstStart, int firstEnd, | |
317 List secondList, int secondStart, int secondEnd, | |
318 List target, int targetOffset) { | |
319 // No empty lists reaches here. | |
320 assert(firstStart < firstEnd); | |
321 assert(secondStart < secondEnd); | |
322 int cursor1 = firstStart; | |
323 int cursor2 = secondStart; | |
324 var firstElement = firstList[cursor1++]; | |
325 var secondElement = secondList[cursor2++]; | |
326 while (true) { | |
327 if (compare(firstElement, secondElement) <= 0) { | |
328 target[targetOffset++] = firstElement; | |
329 if (cursor1 == firstEnd) break; // Flushing second list after loop. | |
330 firstElement = firstList[cursor1++]; | |
331 } else { | |
332 target[targetOffset++] = secondElement; | |
333 if (cursor2 != secondEnd) { | |
334 secondElement = secondList[cursor2++]; | |
335 continue; | |
336 } | |
337 // Second list empties first. Flushing first list here. | |
338 target[targetOffset++] = firstElement; | |
339 target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), | |
340 firstList, cursor1); | |
341 return; | |
342 } | |
343 } | |
344 // First list empties first. Reached by break above. | |
345 target[targetOffset++] = secondElement; | |
346 target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), | |
347 secondList, cursor2); | |
348 } | |
OLD | NEW |