Avoid setRange with potentially incompatible types (#320)
Fixes #317
Use `sublist` on the input to get a list with the same runtime generic
as the input instead of constructing a new list with the static generic.
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 05b0899..e38e1a8 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,6 +2,8 @@
- Adds `shuffled` to `IterableExtension`.
- Shuffle `IterableExtension.sample` results.
+- Fix `mergeSort` when the runtime iterable generic is a subtype of the static
+ generic.
- Require Dart `^3.1.0`
- Mark "mixin" classes as `mixin`.
diff --git a/lib/src/algorithms.dart b/lib/src/algorithms.dart
index 5833bbd..f5ea8d3 100644
--- a/lib/src/algorithms.dart
+++ b/lib/src/algorithms.dart
@@ -232,7 +232,7 @@
var middle = start + firstLength;
var secondLength = end - middle;
// secondLength is always the same as firstLength, or one greater.
- var scratchSpace = List<E>.filled(secondLength, elements[start]);
+ var scratchSpace = elements.sublist(0, secondLength);
_mergeSort(elements, identity<E>, compare, middle, end, scratchSpace, 0);
var firstTarget = end - firstLength;
_mergeSort(
@@ -268,7 +268,7 @@
var firstLength = middle - start;
var secondLength = end - middle;
// secondLength is always the same as firstLength, or one greater.
- var scratchSpace = List<E>.filled(secondLength, elements[start]);
+ var scratchSpace = elements.sublist(0, secondLength);
_mergeSort(elements, keyOf, compare, middle, end, scratchSpace, 0);
var firstTarget = end - firstLength;
_mergeSort(elements, keyOf, compare, start, middle, elements, firstTarget);
diff --git a/test/algorithms_test.dart b/test/algorithms_test.dart
index 41603dd..4bc1d54 100644
--- a/test/algorithms_test.dart
+++ b/test/algorithms_test.dart
@@ -368,6 +368,19 @@
reverse(l, 0, 6);
expect(l, equals([2, 1, 4, 3, 6, 5]));
});
+
+ test('mergeSort works when runtime generic is a subtype of the static type',
+ () {
+ // Regression test for https://github.com/dart-lang/collection/issues/317
+ final length = 1000; // Larger than _mergeSortLimit
+ // Out of order list, with first half guaranteed to empty first during
+ // merge.
+ final list = [
+ for (var i = 0; i < length / 2; i++) -i,
+ for (var i = 0; i < length / 2; i++) i + length,
+ ];
+ expect(() => mergeSort<num>(list), returnsNormally);
+ });
}
class C {
