1 | // Copyright 2014 The Flutter Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. |
4 | |
5 | // TODO(ianh): These should be on the Set and List classes themselves. |
6 | |
7 | /// Compares two sets for element-by-element equality. |
8 | /// |
9 | /// Returns true if the sets are both null, or if they are both non-null, have |
10 | /// the same length, and contain the same members. Returns false otherwise. |
11 | /// Order is not compared. |
12 | /// |
13 | /// If the elements are maps, lists, sets, or other collections/composite |
14 | /// objects, then the contents of those elements are not compared element by |
15 | /// element unless their equality operators ([Object.==]) do so. For checking |
16 | /// deep equality, consider using the [DeepCollectionEquality] class. |
17 | /// |
18 | /// See also: |
19 | /// |
20 | /// * [listEquals], which does something similar for lists. |
21 | /// * [mapEquals], which does something similar for maps. |
22 | bool setEquals<T>(Set<T>? a, Set<T>? b) { |
23 | if (a == null) { |
24 | return b == null; |
25 | } |
26 | if (b == null || a.length != b.length) { |
27 | return false; |
28 | } |
29 | if (identical(a, b)) { |
30 | return true; |
31 | } |
32 | for (final T value in a) { |
33 | if (!b.contains(value)) { |
34 | return false; |
35 | } |
36 | } |
37 | return true; |
38 | } |
39 | |
40 | /// Compares two lists for element-by-element equality. |
41 | /// |
42 | /// Returns true if the lists are both null, or if they are both non-null, have |
43 | /// the same length, and contain the same members in the same order. Returns |
44 | /// false otherwise. |
45 | /// |
46 | /// If the elements are maps, lists, sets, or other collections/composite |
47 | /// objects, then the contents of those elements are not compared element by |
48 | /// element unless their equality operators ([Object.==]) do so. For checking |
49 | /// deep equality, consider using the [DeepCollectionEquality] class. |
50 | /// |
51 | /// See also: |
52 | /// |
53 | /// * [setEquals], which does something similar for sets. |
54 | /// * [mapEquals], which does something similar for maps. |
55 | bool listEquals<T>(List<T>? a, List<T>? b) { |
56 | if (a == null) { |
57 | return b == null; |
58 | } |
59 | if (b == null || a.length != b.length) { |
60 | return false; |
61 | } |
62 | if (identical(a, b)) { |
63 | return true; |
64 | } |
65 | for (int index = 0; index < a.length; index += 1) { |
66 | if (a[index] != b[index]) { |
67 | return false; |
68 | } |
69 | } |
70 | return true; |
71 | } |
72 | |
73 | /// Compares two maps for element-by-element equality. |
74 | /// |
75 | /// Returns true if the maps are both null, or if they are both non-null, have |
76 | /// the same length, and contain the same keys associated with the same values. |
77 | /// Returns false otherwise. |
78 | /// |
79 | /// If the elements are maps, lists, sets, or other collections/composite |
80 | /// objects, then the contents of those elements are not compared element by |
81 | /// element unless their equality operators ([Object.==]) do so. For checking |
82 | /// deep equality, consider using the [DeepCollectionEquality] class. |
83 | /// |
84 | /// See also: |
85 | /// |
86 | /// * [setEquals], which does something similar for sets. |
87 | /// * [listEquals], which does something similar for lists. |
88 | bool mapEquals<T, U>(Map<T, U>? a, Map<T, U>? b) { |
89 | if (a == null) { |
90 | return b == null; |
91 | } |
92 | if (b == null || a.length != b.length) { |
93 | return false; |
94 | } |
95 | if (identical(a, b)) { |
96 | return true; |
97 | } |
98 | for (final T key in a.keys) { |
99 | if (!b.containsKey(key) || b[key] != a[key]) { |
100 | return false; |
101 | } |
102 | } |
103 | return true; |
104 | } |
105 | |
106 | /// Returns the position of `value` in the `sortedList`, if it exists. |
107 | /// |
108 | /// Returns `-1` if the `value` is not in the list. Requires the list items |
109 | /// to implement [Comparable] and the `sortedList` to already be ordered. |
110 | int binarySearch<T extends Comparable<Object>>(List<T> sortedList, T value) { |
111 | int min = 0; |
112 | int max = sortedList.length; |
113 | while (min < max) { |
114 | final int mid = min + ((max - min) >> 1); |
115 | final T element = sortedList[mid]; |
116 | final int comp = element.compareTo(value); |
117 | if (comp == 0) { |
118 | return mid; |
119 | } |
120 | if (comp < 0) { |
121 | min = mid + 1; |
122 | } else { |
123 | max = mid; |
124 | } |
125 | } |
126 | return -1; |
127 | } |
128 | |
129 | /// Limit below which merge sort defaults to insertion sort. |
130 | const int _kMergeSortLimit = 32; |
131 | |
132 | /// Sorts a list between `start` (inclusive) and `end` (exclusive) using the |
133 | /// merge sort algorithm. |
134 | /// |
135 | /// If `compare` is omitted, this defaults to calling [Comparable.compareTo] on |
136 | /// the objects. If any object is not [Comparable], this throws a [TypeError] |
137 | /// (The stack trace may call it `_CastError` or `_TypeError`, but to catch it, |
138 | /// use [TypeError]). |
139 | /// |
140 | /// Merge-sorting works by splitting the job into two parts, sorting each |
141 | /// recursively, and then merging the two sorted parts. |
142 | /// |
143 | /// This takes on the order of `n * log(n)` comparisons and moves to sort `n` |
144 | /// elements, but requires extra space of about the same size as the list being |
145 | /// sorted. |
146 | /// |
147 | /// This merge sort is stable: Equal elements end up in the same order as they |
148 | /// started in. |
149 | /// |
150 | /// For small lists (less than 32 elements), [mergeSort] automatically uses an |
151 | /// insertion sort instead, as that is more efficient for small lists. The |
152 | /// insertion sort is also stable. |
153 | void mergeSort<T>( |
154 | List<T> list, { |
155 | int start = 0, |
156 | int? end, |
157 | int Function(T, T)? compare, |
158 | }) { |
159 | end ??= list.length; |
160 | compare ??= _defaultCompare<T>(); |
161 | |
162 | final int length = end - start; |
163 | if (length < 2) { |
164 | return; |
165 | } |
166 | if (length < _kMergeSortLimit) { |
167 | _insertionSort<T>(list, compare: compare, start: start, end: end); |
168 | return; |
169 | } |
170 | // Special case the first split instead of directly calling _mergeSort, |
171 | // because the _mergeSort requires its target to be different from its source, |
172 | // and it requires extra space of the same size as the list to sort. This |
173 | // split allows us to have only half as much extra space, and it ends up in |
174 | // the original place. |
175 | final int middle = start + ((end - start) >> 1); |
176 | final int firstLength = middle - start; |
177 | final int secondLength = end - middle; |
178 | // secondLength is always the same as firstLength, or one greater. |
179 | final List<T> scratchSpace = List<T>.filled(secondLength, list[start]); |
180 | _mergeSort<T>(list, compare, middle, end, scratchSpace, 0); |
181 | final int firstTarget = end - firstLength; |
182 | _mergeSort<T>(list, compare, start, middle, list, firstTarget); |
183 | _merge<T>(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start); |
184 | } |
185 | |
186 | /// Returns a [Comparator] that asserts that its first argument is comparable. |
187 | Comparator<T> _defaultCompare<T>() { |
188 | // If we specify Comparable here, it fails if the type is an int, because |
189 | // int isn't a subtype of comparable. Leaving out the type implicitly converts |
190 | // it to a num, which is a comparable. |
191 | return (T value1, T value2) => (value1 as Comparable<dynamic>).compareTo(value2); |
192 | } |
193 | |
194 | /// Sort a list between `start` (inclusive) and `end` (exclusive) using |
195 | /// insertion sort. |
196 | /// |
197 | /// If `compare` is omitted, this defaults to calling [Comparable.compareTo] on |
198 | /// the objects. If any object is not [Comparable], this throws a [TypeError] |
199 | /// (The stack trace may call it `_CastError` or `_TypeError`, but to catch it, |
200 | /// use [TypeError]). |
201 | /// |
202 | /// Insertion sort is a simple sorting algorithm. For `n` elements it does on |
203 | /// the order of `n * log(n)` comparisons but up to `n` squared moves. The |
204 | /// sorting is performed in-place, without using extra memory. |
205 | /// |
206 | /// For short lists the many moves have less impact than the simple algorithm, |
207 | /// and it is often the favored sorting algorithm for short lists. |
208 | /// |
209 | /// This insertion sort is stable: Equal elements end up in the same order as |
210 | /// they started in. |
211 | void _insertionSort<T>( |
212 | List<T> list, { |
213 | int Function(T, T)? compare, |
214 | int start = 0, |
215 | int? end, |
216 | }) { |
217 | // If the same method could have both positional and named optional |
218 | // parameters, this should be (list, [start, end], {compare}). |
219 | compare ??= _defaultCompare<T>(); |
220 | end ??= list.length; |
221 | |
222 | for (int pos = start + 1; pos < end; pos++) { |
223 | int min = start; |
224 | int max = pos; |
225 | final T element = list[pos]; |
226 | while (min < max) { |
227 | final int mid = min + ((max - min) >> 1); |
228 | final int comparison = compare(element, list[mid]); |
229 | if (comparison < 0) { |
230 | max = mid; |
231 | } else { |
232 | min = mid + 1; |
233 | } |
234 | } |
235 | list.setRange(min + 1, pos + 1, list, min); |
236 | list[min] = element; |
237 | } |
238 | } |
239 | |
240 | /// Performs an insertion sort into a potentially different list than the one |
241 | /// containing the original values. |
242 | /// |
243 | /// It will work in-place as well. |
244 | void _movingInsertionSort<T>( |
245 | List<T> list, |
246 | int Function(T, T) compare, |
247 | int start, |
248 | int end, |
249 | List<T> target, |
250 | int targetOffset, |
251 | ) { |
252 | final int length = end - start; |
253 | if (length == 0) { |
254 | return; |
255 | } |
256 | target[targetOffset] = list[start]; |
257 | for (int i = 1; i < length; i++) { |
258 | final T element = list[start + i]; |
259 | int min = targetOffset; |
260 | int max = targetOffset + i; |
261 | while (min < max) { |
262 | final int mid = min + ((max - min) >> 1); |
263 | if (compare(element, target[mid]) < 0) { |
264 | max = mid; |
265 | } else { |
266 | min = mid + 1; |
267 | } |
268 | } |
269 | target.setRange(min + 1, targetOffset + i + 1, target, min); |
270 | target[min] = element; |
271 | } |
272 | } |
273 | |
274 | /// Sorts `list` from `start` to `end` into `target` at `targetOffset`. |
275 | /// |
276 | /// The `target` list must be able to contain the range from `start` to `end` |
277 | /// after `targetOffset`. |
278 | /// |
279 | /// Allows target to be the same list as `list`, as long as it's not overlapping |
280 | /// the `start..end` range. |
281 | void _mergeSort<T>( |
282 | List<T> list, |
283 | int Function(T, T) compare, |
284 | int start, |
285 | int end, |
286 | List<T> target, |
287 | int targetOffset, |
288 | ) { |
289 | final int length = end - start; |
290 | if (length < _kMergeSortLimit) { |
291 | _movingInsertionSort<T>(list, compare, start, end, target, targetOffset); |
292 | return; |
293 | } |
294 | final int middle = start + (length >> 1); |
295 | final int firstLength = middle - start; |
296 | final int secondLength = end - middle; |
297 | // Here secondLength >= firstLength (differs by at most one). |
298 | final int targetMiddle = targetOffset + firstLength; |
299 | // Sort the second half into the end of the target area. |
300 | _mergeSort<T>(list, compare, middle, end, target, targetMiddle); |
301 | // Sort the first half into the end of the source area. |
302 | _mergeSort<T>(list, compare, start, middle, list, middle); |
303 | // Merge the two parts into the target area. |
304 | _merge<T>( |
305 | compare, |
306 | list, |
307 | middle, |
308 | middle + firstLength, |
309 | target, |
310 | targetMiddle, |
311 | targetMiddle + secondLength, |
312 | target, |
313 | targetOffset, |
314 | ); |
315 | } |
316 | |
317 | /// Merges two lists into a target list. |
318 | /// |
319 | /// One of the input lists may be positioned at the end of the target list. |
320 | /// |
321 | /// For equal object, elements from `firstList` are always preferred. This |
322 | /// allows the merge to be stable if the first list contains elements that |
323 | /// started out earlier than the ones in `secondList`. |
324 | void _merge<T>( |
325 | int Function(T, T) compare, |
326 | List<T> firstList, |
327 | int firstStart, |
328 | int firstEnd, |
329 | List<T> secondList, |
330 | int secondStart, |
331 | int secondEnd, |
332 | List<T> target, |
333 | int targetOffset, |
334 | ) { |
335 | // No empty lists reaches here. |
336 | assert(firstStart < firstEnd); |
337 | assert(secondStart < secondEnd); |
338 | int cursor1 = firstStart; |
339 | int cursor2 = secondStart; |
340 | T firstElement = firstList[cursor1++]; |
341 | T secondElement = secondList[cursor2++]; |
342 | while (true) { |
343 | if (compare(firstElement, secondElement) <= 0) { |
344 | target[targetOffset++] = firstElement; |
345 | if (cursor1 == firstEnd) { |
346 | // Flushing second list after loop. |
347 | break; |
348 | } |
349 | firstElement = firstList[cursor1++]; |
350 | } else { |
351 | target[targetOffset++] = secondElement; |
352 | if (cursor2 != secondEnd) { |
353 | secondElement = secondList[cursor2++]; |
354 | continue; |
355 | } |
356 | // Second list empties first. Flushing first list here. |
357 | target[targetOffset++] = firstElement; |
358 | target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), firstList, cursor1); |
359 | return; |
360 | } |
361 | } |
362 | // First list empties first. Reached by break above. |
363 | target[targetOffset++] = secondElement; |
364 | target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), secondList, cursor2); |
365 | } |
366 | |