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.
22bool 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.
55bool 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.
88bool 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.
110int 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.
130const 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.
153void 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.
187Comparator<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.
211void _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.
244void _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.
281void _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`.
324void _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