Skip to content

Commit c5527dc

Browse files
gspencergooggspencergoog
authored
Remove dependency on package:collection by moving mergeSort into foundation/collections.dart (flutter#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.
1 parent 56a7dac commit c5527dc

File tree

4 files changed

+357
-4
lines changed

4 files changed

+357
-4
lines changed

‎packages/flutter/lib/src/foundation/collections.dart

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

‎packages/flutter/lib/src/widgets/focus_traversal.dart

-1
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,6 @@
66

77
import 'dart:ui';
88

9-
import 'package:collection/collection.dart';
109
import 'package:flutter/foundation.dart';
1110
import 'package:flutter/painting.dart';
1211

‎packages/flutter/lib/src/widgets/shortcuts.dart

+2-3
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,6 @@
66

77
import 'dart:collection';
88

9-
import 'package:collection/collection.dart';
109
import 'package:flutter/foundation.dart';
1110
import 'package:flutter/services.dart';
1211

@@ -79,8 +78,8 @@ class KeySet<T extends KeyboardKey> {
7978
assert(!keys.contains(null)),
8079
_keys = HashSet<T>.from(keys);
8180

82-
/// Returns an unmodifiable view of the [KeyboardKey]s in this [KeySet].
83-
Set<T> get keys => UnmodifiableSetView<T>(_keys);
81+
/// Returns a copy of the [KeyboardKey]s in this [KeySet].
82+
Set<T> get keys => _keys.toSet();
8483
final HashSet<T> _keys;
8584

8685
@override

‎packages/flutter/test/foundation/collections_test.dart

+117
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
// found in the LICENSE file.
44

55
// @dart = 2.8
6+
import 'dart:math';
67

78
import 'package:flutter/src/foundation/collections.dart';
89
import 'package:flutter_test/flutter_test.dart';
@@ -60,4 +61,120 @@ void main() {
6061
expect(binarySearch(items, 3), 2);
6162
expect(binarySearch(items, 12), -1);
6263
});
64+
test('MergeSortRandom', () {
65+
final Random random = Random();
66+
for (int i = 0; i < 250; i += 1) {
67+
final List<int> list = List<int>(i);
68+
for (int j = 0; j < i; j++) {
69+
list[j] = random.nextInt(i); // Expect some equal elements.
70+
}
71+
mergeSort(list);
72+
for (int j = 1; j < i; j++) {
73+
expect(list[j - 1], lessThanOrEqualTo(list[j]));
74+
}
75+
}
76+
});
77+
test('MergeSortPreservesOrder', () {
78+
final Random random = Random();
79+
// Small case where only insertion call is called,
80+
// larger case where the internal moving insertion sort is used
81+
// larger cases with multiple splittings, numbers just around a power of 2.
82+
for (final int size in <int>[8, 50, 511, 512, 513]) {
83+
final List<OrderedComparable> list = List<OrderedComparable>(size);
84+
// Class OC compares using id.
85+
// With size elements with id's in the range 0..size/4, a number of
86+
// collisions are guaranteed. These should be sorted so that the 'order'
87+
// part of the objects are still in order.
88+
for (int i = 0; i < size; i++) {
89+
list[i] = OrderedComparable(random.nextInt(size >> 2), i);
90+
}
91+
mergeSort(list);
92+
OrderedComparable prev = list[0];
93+
for (int i = 1; i < size; i++) {
94+
final OrderedComparable next = list[i];
95+
expect(prev.id, lessThanOrEqualTo(next.id));
96+
if (next.id == prev.id) {
97+
expect(prev.order, lessThanOrEqualTo(next.order));
98+
}
99+
prev = next;
100+
}
101+
// Reverse compare on part of list.
102+
final List<OrderedComparable> copy = list.toList();
103+
final int min = size >> 2;
104+
final int max = size - min;
105+
mergeSort<OrderedComparable>(
106+
list,
107+
start: min,
108+
end: max,
109+
compare: (OrderedComparable a, OrderedComparable b) => b.compareTo(a),
110+
);
111+
prev = list[min];
112+
for (int i = min + 1; i < max; i++) {
113+
final OrderedComparable next = list[i];
114+
expect(prev.id, greaterThanOrEqualTo(next.id));
115+
if (next.id == prev.id) {
116+
expect(prev.order, lessThanOrEqualTo(next.order));
117+
}
118+
prev = next;
119+
}
120+
// Equals on OC objects is identity, so this means the parts before min,
121+
// and the parts after max, didn't change at all.
122+
expect(list.sublist(0, min), equals(copy.sublist(0, min)));
123+
expect(list.sublist(max), equals(copy.sublist(max)));
124+
}
125+
});
126+
test('MergeSortSpecialCases', () {
127+
for (final int size in <int>[511, 512, 513]) {
128+
// All equal.
129+
final List<OrderedComparable> list = List<OrderedComparable>(size);
130+
for (int i = 0; i < size; i++) {
131+
list[i] = OrderedComparable(0, i);
132+
}
133+
mergeSort(list);
134+
for (int i = 0; i < size; i++) {
135+
expect(list[i].order, equals(i));
136+
}
137+
// All but one equal, first.
138+
list[0] = OrderedComparable(1, 0);
139+
for (int i = 1; i < size; i++) {
140+
list[i] = OrderedComparable(0, i);
141+
}
142+
mergeSort(list);
143+
for (int i = 0; i < size - 1; i++) {
144+
expect(list[i].order, equals(i + 1));
145+
}
146+
expect(list[size - 1].order, equals(0));
147+
148+
// All but one equal, last.
149+
for (int i = 0; i < size - 1; i++) {
150+
list[i] = OrderedComparable(0, i);
151+
}
152+
list[size - 1] = OrderedComparable(-1, size - 1);
153+
mergeSort(list);
154+
expect(list[0].order, equals(size - 1));
155+
for (int i = 1; i < size; i++) {
156+
expect(list[i].order, equals(i - 1));
157+
}
158+
159+
// Reversed.
160+
for (int i = 0; i < size; i++) {
161+
list[i] = OrderedComparable(size - 1 - i, i);
162+
}
163+
mergeSort(list);
164+
for (int i = 0; i < size; i++) {
165+
expect(list[i].id, equals(i));
166+
expect(list[i].order, equals(size - 1 - i));
167+
}
168+
}
169+
});
170+
}
171+
172+
class OrderedComparable implements Comparable<OrderedComparable> {
173+
OrderedComparable(this.id, this.order);
174+
final int id;
175+
final int order;
176+
@override
177+
int compareTo(OrderedComparable other) => id - other.id;
178+
@override
179+
String toString() => 'OverrideComparable[$id,$order]';
63180
}

0 commit comments

Comments
 (0)