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