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