// Copyright 2014 The Flutter Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. // TODO(ianh): These should be on the Set and List classes themselves. /// Compares two sets for deep equality. /// /// Returns true if the sets are both null, or if they are both non-null, have /// the same length, and contain the same members. Returns false otherwise. /// Order is not compared. /// /// The term "deep" above refers to the first level of equality: if the elements /// are maps, lists, sets, or other collections/composite objects, then the /// values of those elements are not compared element by element unless their /// equality operators ([Object.==]) do so. /// /// See also: /// /// * [listEquals], which does something similar for lists. /// * [mapEquals], which does something similar for maps. bool setEquals<T>(Set<T>? a, Set<T>? b) { if (a == null) return b == null; if (b == null || a.length != b.length) return false; if (identical(a, b)) return true; for (final T value in a) { if (!b.contains(value)) return false; } return true; } /// Compares two lists for deep equality. /// /// Returns true if the lists are both null, or if they are both non-null, have /// the same length, and contain the same members in the same order. Returns /// false otherwise. /// /// The term "deep" above refers to the first level of equality: if the elements /// are maps, lists, sets, or other collections/composite objects, then the /// values of those elements are not compared element by element unless their /// equality operators ([Object.==]) do so. /// /// See also: /// /// * [setEquals], which does something similar for sets. /// * [mapEquals], which does something similar for maps. bool listEquals<T>(List<T>? a, List<T>? b) { if (a == null) return b == null; if (b == null || a.length != b.length) return false; if (identical(a, b)) return true; for (int index = 0; index < a.length; index += 1) { if (a[index] != b[index]) return false; } return true; } /// Compares two maps for deep equality. /// /// Returns true if the maps are both null, or if they are both non-null, have /// the same length, and contain the same keys associated with the same values. /// Returns false otherwise. /// /// The term "deep" above refers to the first level of equality: if the elements /// are maps, lists, sets, or other collections/composite objects, then the /// values of those elements are not compared element by element unless their /// equality operators ([Object.==]) do so. /// /// See also: /// /// * [setEquals], which does something similar for sets. /// * [listEquals], which does something similar for lists. bool mapEquals<T, U>(Map<T, U>? a, Map<T, U>? b) { if (a == null) return b == null; if (b == null || a.length != b.length) return false; if (identical(a, b)) return true; for (final T key in a.keys) { if (!b.containsKey(key) || b[key] != a[key]) { return false; } } return true; } /// Returns the position of `value` in the `sortedList`, if it exists. /// /// Returns `-1` if the `value` is not in the list. Requires the list items /// to implement [Comparable] and the `sortedList` to already be ordered. int binarySearch<T extends Comparable<Object>>(List<T> sortedList, T value) { int min = 0; int max = sortedList.length; while (min < max) { final int mid = min + ((max - min) >> 1); final T element = sortedList[mid]; final int comp = element.compareTo(value); if (comp == 0) { return mid; } if (comp < 0) { min = mid + 1; } else { max = mid; } } return -1; } /// Limit below which merge sort defaults to insertion sort. const int _kMergeSortLimit = 32; /// Sorts a list between `start` (inclusive) and `end` (exclusive) using the /// merge sort algorithm. /// /// If `compare` is omitted, this defaults to calling [Comparable.compareTo] on /// the objects. If any object is not [Comparable], this throws a [TypeError] /// (The stack trace may call it `_CastError` or `_TypeError`, but to catch it, /// use [TypeError]). /// /// Merge-sorting works by splitting the job into two parts, sorting each /// recursively, and then merging the two sorted parts. /// /// This takes on the order of `n * log(n)` comparisons and moves to sort `n` /// elements, but requires extra space of about the same size as the list being /// sorted. /// /// This merge sort is stable: Equal elements end up in the same order as they /// started in. /// /// For small lists (less than 32 elements), `mergeSort` automatically uses an /// insertion sort instead, as that is more efficient for small lists. The /// insertion sort is also stable. void mergeSort<T>( List<T> list, { int start = 0, int? end, int Function(T, T)? compare, }) { end ??= list.length; compare ??= _defaultCompare<T>(); final int length = end - start; if (length < 2) { return; } if (length < _kMergeSortLimit) { _insertionSort<T>(list, compare: compare, start: start, end: end); return; } // Special case the first split instead of directly calling _mergeSort, // because the _mergeSort requires its target to be different from its source, // and it requires extra space of the same size as the list to sort. This // split allows us to have only half as much extra space, and it ends up in // the original place. final int middle = start + ((end - start) >> 1); final int firstLength = middle - start; final int secondLength = end - middle; // secondLength is always the same as firstLength, or one greater. final List<T> scratchSpace = List<T>.filled(secondLength, list[start]); _mergeSort<T>(list, compare, middle, end, scratchSpace, 0); final int firstTarget = end - firstLength; _mergeSort<T>(list, compare, start, middle, list, firstTarget); _merge<T>(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start); } /// Returns a [Comparator] that asserts that its first argument is comparable. Comparator<T> _defaultCompare<T>() { // If we specify Comparable<T> here, it fails if the type is an int, because // int isn't a subtype of comparable. Leaving out the type implicitly converts // it to a num, which is a comparable. return (T value1, T value2) => (value1 as Comparable<dynamic>).compareTo(value2); } /// Sort a list between `start` (inclusive) and `end` (exclusive) using /// insertion sort. /// /// If `compare` is omitted, this defaults to calling [Comparable.compareTo] on /// the objects. If any object is not [Comparable], this throws a [TypeError] /// (The stack trace may call it `_CastError` or `_TypeError`, but to catch it, /// use [TypeError]). /// /// Insertion sort is a simple sorting algorithm. For `n` elements it does on /// the order of `n * log(n)` comparisons but up to `n` squared moves. The /// sorting is performed in-place, without using extra memory. /// /// For short lists the many moves have less impact than the simple algorithm, /// and it is often the favored sorting algorithm for short lists. /// /// This insertion sort is stable: Equal elements end up in the same order as /// they started in. void _insertionSort<T>( List<T> list, { int Function(T, T)? compare, int start = 0, int? end, }) { // If the same method could have both positional and named optional // parameters, this should be (list, [start, end], {compare}). compare ??= _defaultCompare<T>(); end ??= list.length; for (int pos = start + 1; pos < end; pos++) { int min = start; int max = pos; final T element = list[pos]; while (min < max) { final int mid = min + ((max - min) >> 1); final int comparison = compare(element, list[mid]); if (comparison < 0) { max = mid; } else { min = mid + 1; } } list.setRange(min + 1, pos + 1, list, min); list[min] = element; } } /// Performs an insertion sort into a potentially different list than the one /// containing the original values. /// /// It will work in-place as well. void _movingInsertionSort<T>( List<T> list, int Function(T, T) compare, int start, int end, List<T?> target, int targetOffset, ) { final int length = end - start; if (length == 0) { return; } target[targetOffset] = list[start]; for (int i = 1; i < length; i++) { final T element = list[start + i]; int min = targetOffset; int max = targetOffset + i; while (min < max) { final int mid = min + ((max - min) >> 1); if (compare(element, target[mid] as T) < 0) { max = mid; } else { min = mid + 1; } } target.setRange(min + 1, targetOffset + i + 1, target, min); target[min] = element; } } /// Sorts `list` from `start` to `end` into `target` at `targetOffset`. /// /// The `target` list must be able to contain the range from `start` to `end` /// after `targetOffset`. /// /// Allows target to be the same list as `list`, as long as it's not overlapping /// the `start..end` range. void _mergeSort<T>( List<T> list, int Function(T, T) compare, int start, int end, List<T> target, int targetOffset, ) { final int length = end - start; if (length < _kMergeSortLimit) { _movingInsertionSort<T>(list, compare, start, end, target, targetOffset); return; } final int middle = start + (length >> 1); final int firstLength = middle - start; final int secondLength = end - middle; // Here secondLength >= firstLength (differs by at most one). final int targetMiddle = targetOffset + firstLength; // Sort the second half into the end of the target area. _mergeSort<T>(list, compare, middle, end, target, targetMiddle); // Sort the first half into the end of the source area. _mergeSort<T>(list, compare, start, middle, list, middle); // Merge the two parts into the target area. _merge<T>( compare, list, middle, middle + firstLength, target, targetMiddle, targetMiddle + secondLength, target, targetOffset, ); } /// Merges two lists into a target list. /// /// One of the input lists may be positioned at the end of the target list. /// /// For equal object, elements from `firstList` are always preferred. This /// allows the merge to be stable if the first list contains elements that /// started out earlier than the ones in `secondList`. void _merge<T>( int Function(T, T) compare, List<T> firstList, int firstStart, int firstEnd, List<T> secondList, int secondStart, int secondEnd, List<T> target, int targetOffset, ) { // No empty lists reaches here. assert(firstStart < firstEnd); assert(secondStart < secondEnd); int cursor1 = firstStart; int cursor2 = secondStart; T firstElement = firstList[cursor1++]; T secondElement = secondList[cursor2++]; while (true) { if (compare(firstElement, secondElement) <= 0) { target[targetOffset++] = firstElement; if (cursor1 == firstEnd) { // Flushing second list after loop. break; } firstElement = firstList[cursor1++]; } else { target[targetOffset++] = secondElement; if (cursor2 != secondEnd) { secondElement = secondList[cursor2++]; continue; } // Second list empties first. Flushing first list here. target[targetOffset++] = firstElement; target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), firstList, cursor1); return; } } // First list empties first. Reached by break above. target[targetOffset++] = secondElement; target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), secondList, cursor2); }