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