Remove dependency on package:collection by moving mergeSort into foundation/collections.dart (#59521)
This removes a dependency from Flutter (package:collection) by copying the implementation of mergeSort into Flutter's foundation/collections.dart.
Also, removed a reference to UnmodifiableSetView from the shortcuts code by just returning a copy instead.
diff --git a/packages/flutter/lib/src/foundation/collections.dart b/packages/flutter/lib/src/foundation/collections.dart
index 09b5f4f..e37fad0 100644
--- a/packages/flutter/lib/src/foundation/collections.dart
+++ b/packages/flutter/lib/src/foundation/collections.dart
@@ -117,3 +117,241 @@
}
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(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>(secondLength);
+ _mergeSort(list, compare, middle, end, scratchSpace, 0);
+ final int firstTarget = end - firstLength;
+ _mergeSort(list, compare, start, middle, list, firstTarget);
+ _merge(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]) < 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(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(list, compare, middle, end, target, targetMiddle);
+ // Sort the first half into the end of the source area.
+ _mergeSort(list, compare, start, middle, list, middle);
+ // Merge the two parts into the target area.
+ _merge(
+ 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);
+}
diff --git a/packages/flutter/lib/src/widgets/focus_traversal.dart b/packages/flutter/lib/src/widgets/focus_traversal.dart
index 1366134..d4180ad 100644
--- a/packages/flutter/lib/src/widgets/focus_traversal.dart
+++ b/packages/flutter/lib/src/widgets/focus_traversal.dart
@@ -6,7 +6,6 @@
import 'dart:ui';
-import 'package:collection/collection.dart';
import 'package:flutter/foundation.dart';
import 'package:flutter/painting.dart';
diff --git a/packages/flutter/lib/src/widgets/shortcuts.dart b/packages/flutter/lib/src/widgets/shortcuts.dart
index 74e56d6..7e4e239 100644
--- a/packages/flutter/lib/src/widgets/shortcuts.dart
+++ b/packages/flutter/lib/src/widgets/shortcuts.dart
@@ -6,7 +6,6 @@
import 'dart:collection';
-import 'package:collection/collection.dart';
import 'package:flutter/foundation.dart';
import 'package:flutter/services.dart';
@@ -79,8 +78,8 @@
assert(!keys.contains(null)),
_keys = HashSet<T>.from(keys);
- /// Returns an unmodifiable view of the [KeyboardKey]s in this [KeySet].
- Set<T> get keys => UnmodifiableSetView<T>(_keys);
+ /// Returns a copy of the [KeyboardKey]s in this [KeySet].
+ Set<T> get keys => _keys.toSet();
final HashSet<T> _keys;
@override
diff --git a/packages/flutter/test/foundation/collections_test.dart b/packages/flutter/test/foundation/collections_test.dart
index d9f03be..056d20c 100644
--- a/packages/flutter/test/foundation/collections_test.dart
+++ b/packages/flutter/test/foundation/collections_test.dart
@@ -3,6 +3,7 @@
// found in the LICENSE file.
// @dart = 2.8
+import 'dart:math';
import 'package:flutter/src/foundation/collections.dart';
import 'package:flutter_test/flutter_test.dart';
@@ -60,4 +61,120 @@
expect(binarySearch(items, 3), 2);
expect(binarySearch(items, 12), -1);
});
+ test('MergeSortRandom', () {
+ final Random random = Random();
+ for (int i = 0; i < 250; i += 1) {
+ final List<int> list = List<int>(i);
+ for (int j = 0; j < i; j++) {
+ list[j] = random.nextInt(i); // Expect some equal elements.
+ }
+ mergeSort(list);
+ for (int j = 1; j < i; j++) {
+ expect(list[j - 1], lessThanOrEqualTo(list[j]));
+ }
+ }
+ });
+ test('MergeSortPreservesOrder', () {
+ final Random random = Random();
+ // Small case where only insertion call is called,
+ // larger case where the internal moving insertion sort is used
+ // larger cases with multiple splittings, numbers just around a power of 2.
+ for (final int size in <int>[8, 50, 511, 512, 513]) {
+ final List<OrderedComparable> list = List<OrderedComparable>(size);
+ // Class OC compares using id.
+ // With size elements with id's in the range 0..size/4, a number of
+ // collisions are guaranteed. These should be sorted so that the 'order'
+ // part of the objects are still in order.
+ for (int i = 0; i < size; i++) {
+ list[i] = OrderedComparable(random.nextInt(size >> 2), i);
+ }
+ mergeSort(list);
+ OrderedComparable prev = list[0];
+ for (int i = 1; i < size; i++) {
+ final OrderedComparable next = list[i];
+ expect(prev.id, lessThanOrEqualTo(next.id));
+ if (next.id == prev.id) {
+ expect(prev.order, lessThanOrEqualTo(next.order));
+ }
+ prev = next;
+ }
+ // Reverse compare on part of list.
+ final List<OrderedComparable> copy = list.toList();
+ final int min = size >> 2;
+ final int max = size - min;
+ mergeSort<OrderedComparable>(
+ list,
+ start: min,
+ end: max,
+ compare: (OrderedComparable a, OrderedComparable b) => b.compareTo(a),
+ );
+ prev = list[min];
+ for (int i = min + 1; i < max; i++) {
+ final OrderedComparable next = list[i];
+ expect(prev.id, greaterThanOrEqualTo(next.id));
+ if (next.id == prev.id) {
+ expect(prev.order, lessThanOrEqualTo(next.order));
+ }
+ prev = next;
+ }
+ // Equals on OC objects is identity, so this means the parts before min,
+ // and the parts after max, didn't change at all.
+ expect(list.sublist(0, min), equals(copy.sublist(0, min)));
+ expect(list.sublist(max), equals(copy.sublist(max)));
+ }
+ });
+ test('MergeSortSpecialCases', () {
+ for (final int size in <int>[511, 512, 513]) {
+ // All equal.
+ final List<OrderedComparable> list = List<OrderedComparable>(size);
+ for (int i = 0; i < size; i++) {
+ list[i] = OrderedComparable(0, i);
+ }
+ mergeSort(list);
+ for (int i = 0; i < size; i++) {
+ expect(list[i].order, equals(i));
+ }
+ // All but one equal, first.
+ list[0] = OrderedComparable(1, 0);
+ for (int i = 1; i < size; i++) {
+ list[i] = OrderedComparable(0, i);
+ }
+ mergeSort(list);
+ for (int i = 0; i < size - 1; i++) {
+ expect(list[i].order, equals(i + 1));
+ }
+ expect(list[size - 1].order, equals(0));
+
+ // All but one equal, last.
+ for (int i = 0; i < size - 1; i++) {
+ list[i] = OrderedComparable(0, i);
+ }
+ list[size - 1] = OrderedComparable(-1, size - 1);
+ mergeSort(list);
+ expect(list[0].order, equals(size - 1));
+ for (int i = 1; i < size; i++) {
+ expect(list[i].order, equals(i - 1));
+ }
+
+ // Reversed.
+ for (int i = 0; i < size; i++) {
+ list[i] = OrderedComparable(size - 1 - i, i);
+ }
+ mergeSort(list);
+ for (int i = 0; i < size; i++) {
+ expect(list[i].id, equals(i));
+ expect(list[i].order, equals(size - 1 - i));
+ }
+ }
+ });
+}
+
+class OrderedComparable implements Comparable<OrderedComparable> {
+ OrderedComparable(this.id, this.order);
+ final int id;
+ final int order;
+ @override
+ int compareTo(OrderedComparable other) => id - other.id;
+ @override
+ String toString() => 'OverrideComparable[$id,$order]';
}
