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>(List<T> list, {int start = 0, int? end, int Function(T, T)? compare}) {
157 end ??= list.length;
158 compare ??= _defaultCompare<T>();
159
160 final int length = end - start;
161 if (length < 2) {
162 return;
163 }
164 if (length < _kMergeSortLimit) {
165 _insertionSort<T>(list, compare: compare, start: start, end: end);
166 return;
167 }
168 // Special case the first split instead of directly calling _mergeSort,
169 // because the _mergeSort requires its target to be different from its source,
170 // and it requires extra space of the same size as the list to sort. This
171 // split allows us to have only half as much extra space, and it ends up in
172 // the original place.
173 final int middle = start + ((end - start) >> 1);
174 final int firstLength = middle - start;
175 final int secondLength = end - middle;
176 // secondLength is always the same as firstLength, or one greater.
177 final List<T> scratchSpace = List<T>.filled(secondLength, list[start]);
178 _mergeSort<T>(list, compare, middle, end, scratchSpace, 0);
179 final int firstTarget = end - firstLength;
180 _mergeSort<T>(list, compare, start, middle, list, firstTarget);
181 _merge<T>(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start);
182}
183
184/// Returns a [Comparator] that asserts that its first argument is comparable.
185Comparator<T> _defaultCompare<T>() {
186 // If we specify Comparable here, it fails if the type is an int, because
187 // int isn't a subtype of comparable. Leaving out the type implicitly converts
188 // it to a num, which is a comparable.
189 return (T value1, T value2) => (value1 as Comparable<dynamic>).compareTo(value2);
190}
191
192/// Sort a list between `start` (inclusive) and `end` (exclusive) using
193/// insertion sort.
194///
195/// If `compare` is omitted, this defaults to calling [Comparable.compareTo] on
196/// the objects. If any object is not [Comparable], this throws a [TypeError]
197/// (The stack trace may call it `_CastError` or `_TypeError`, but to catch it,
198/// use [TypeError]).
199///
200/// Insertion sort is a simple sorting algorithm. For `n` elements it does on
201/// the order of `n * log(n)` comparisons but up to `n` squared moves. The
202/// sorting is performed in-place, without using extra memory.
203///
204/// For short lists the many moves have less impact than the simple algorithm,
205/// and it is often the favored sorting algorithm for short lists.
206///
207/// This insertion sort is stable: Equal elements end up in the same order as
208/// they started in.
209void _insertionSort<T>(List<T> list, {int Function(T, T)? compare, int start = 0, int? end}) {
210 // If the same method could have both positional and named optional
211 // parameters, this should be (list, [start, end], {compare}).
212 compare ??= _defaultCompare<T>();
213 end ??= list.length;
214
215 for (int pos = start + 1; pos < end; pos++) {
216 int min = start;
217 int max = pos;
218 final T element = list[pos];
219 while (min < max) {
220 final int mid = min + ((max - min) >> 1);
221 final int comparison = compare(element, list[mid]);
222 if (comparison < 0) {
223 max = mid;
224 } else {
225 min = mid + 1;
226 }
227 }
228 list.setRange(min + 1, pos + 1, list, min);
229 list[min] = element;
230 }
231}
232
233/// Performs an insertion sort into a potentially different list than the one
234/// containing the original values.
235///
236/// It will work in-place as well.
237void _movingInsertionSort<T>(
238 List<T> list,
239 int Function(T, T) compare,
240 int start,
241 int end,
242 List<T> target,
243 int targetOffset,
244) {
245 final int length = end - start;
246 if (length == 0) {
247 return;
248 }
249 target[targetOffset] = list[start];
250 for (int i = 1; i < length; i++) {
251 final T element = list[start + i];
252 int min = targetOffset;
253 int max = targetOffset + i;
254 while (min < max) {
255 final int mid = min + ((max - min) >> 1);
256 if (compare(element, target[mid]) < 0) {
257 max = mid;
258 } else {
259 min = mid + 1;
260 }
261 }
262 target.setRange(min + 1, targetOffset + i + 1, target, min);
263 target[min] = element;
264 }
265}
266
267/// Sorts `list` from `start` to `end` into `target` at `targetOffset`.
268///
269/// The `target` list must be able to contain the range from `start` to `end`
270/// after `targetOffset`.
271///
272/// Allows target to be the same list as `list`, as long as it's not overlapping
273/// the `start..end` range.
274void _mergeSort<T>(
275 List<T> list,
276 int Function(T, T) compare,
277 int start,
278 int end,
279 List<T> target,
280 int targetOffset,
281) {
282 final int length = end - start;
283 if (length < _kMergeSortLimit) {
284 _movingInsertionSort<T>(list, compare, start, end, target, targetOffset);
285 return;
286 }
287 final int middle = start + (length >> 1);
288 final int firstLength = middle - start;
289 final int secondLength = end - middle;
290 // Here secondLength >= firstLength (differs by at most one).
291 final int targetMiddle = targetOffset + firstLength;
292 // Sort the second half into the end of the target area.
293 _mergeSort<T>(list, compare, middle, end, target, targetMiddle);
294 // Sort the first half into the end of the source area.
295 _mergeSort<T>(list, compare, start, middle, list, middle);
296 // Merge the two parts into the target area.
297 _merge<T>(
298 compare,
299 list,
300 middle,
301 middle + firstLength,
302 target,
303 targetMiddle,
304 targetMiddle + secondLength,
305 target,
306 targetOffset,
307 );
308}
309
310/// Merges two lists into a target list.
311///
312/// One of the input lists may be positioned at the end of the target list.
313///
314/// For equal object, elements from `firstList` are always preferred. This
315/// allows the merge to be stable if the first list contains elements that
316/// started out earlier than the ones in `secondList`.
317void _merge<T>(
318 int Function(T, T) compare,
319 List<T> firstList,
320 int firstStart,
321 int firstEnd,
322 List<T> secondList,
323 int secondStart,
324 int secondEnd,
325 List<T> target,
326 int targetOffset,
327) {
328 // No empty lists reaches here.
329 assert(firstStart < firstEnd);
330 assert(secondStart < secondEnd);
331 int cursor1 = firstStart;
332 int cursor2 = secondStart;
333 T firstElement = firstList[cursor1++];
334 T secondElement = secondList[cursor2++];
335 while (true) {
336 if (compare(firstElement, secondElement) <= 0) {
337 target[targetOffset++] = firstElement;
338 if (cursor1 == firstEnd) {
339 // Flushing second list after loop.
340 break;
341 }
342 firstElement = firstList[cursor1++];
343 } else {
344 target[targetOffset++] = secondElement;
345 if (cursor2 != secondEnd) {
346 secondElement = secondList[cursor2++];
347 continue;
348 }
349 // Second list empties first. Flushing first list here.
350 target[targetOffset++] = firstElement;
351 target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), firstList, cursor1);
352 return;
353 }
354 }
355 // First list empties first. Reached by break above.
356 target[targetOffset++] = secondElement;
357 target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), secondList, cursor2);
358}
359

Provided by KDAB

Privacy Policy
Learn more about Flutter for embedded and desktop on industrialflutter.com