Add extension methods to package:collection. (#135)
Add a number of useful extension methods to `List` and `Iterable`, and to a few other types.
A good part of these extensions are backed by the algorithms of `algorithms.dart`, which is expanded to support them:
* Added `quickSort`.
* Add extra optional `Random` argument to `shuffle`.
* Generalize some of the functions in algorithms.dart to work on specific properties of the objects (`binarySearchBy`,
`lowerBoundBy`, `insertionSortBy`, `quickSortBy`, `mergeSortBy`).
The new methods are not exported from the library yet, they are intended to be used through the extension.
diff --git a/.travis.yml b/.travis.yml
index 82091ab..4e550df 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -20,7 +20,7 @@
- stage: test
name: "Vm Tests"
os: linux
- script: pub run --enable-experiment=non-nullable test -p vm
+ script: pub run --enable-experiment=non-nullable test -p vm
- stage: test
name: "Web Tests"
os: linux
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 1695647..e99669f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -3,6 +3,14 @@
* Remove the unusable setter `UnionSetController.set=`. This was mistakenly
added to the public API but could never be called.
+* Add extra optional `Random` argument to `shuffle`.
+
+* Add a large number of extension methods on `Iterable` and `List` types,
+ and on a few other types.
+ These either provide easy access to the operations from `algorithms.dart`,
+ or provide convenience variants of existing `Iterable` and `List` methods
+ like `singleWhereOrNull` or `forEachIndexed`.
+
## 1.15.0-nullsafety.3
* Allow 2.10 stable and 2.11.0 dev SDK versions.
diff --git a/analysis_options.yaml b/analysis_options.yaml
index 5adddb1..d813ed9 100644
--- a/analysis_options.yaml
+++ b/analysis_options.yaml
@@ -1,4 +1,4 @@
-include: package:pedantic/analysis_options.yaml
+include: package:pedantic/analysis_options.1.9.0.yaml
analyzer:
errors:
unused_element: error
@@ -7,39 +7,21 @@
dead_code: error
enable-experiment:
- non-nullable
-
linter:
rules:
# Errors
- - avoid_empty_else
- control_flow_in_finally
- empty_statements
- hash_and_equals
- implementation_imports
- test_types_in_equals
- throw_in_finally
- - unrelated_type_equality_checks
- - valid_regexps
# Style
- - avoid_init_to_null
- avoid_private_typedef_functions
- avoid_renaming_method_parameters
- - avoid_return_types_on_setters
- await_only_futures
- camel_case_types
- directives_ordering
- - empty_catches
- - empty_constructor_bodies
- - library_names
- - library_prefixes
- non_constant_identifier_names
- only_throw_errors
- - prefer_equal_for_default_values
- - prefer_final_fields
- - prefer_generic_function_type_aliases
- - prefer_is_not_empty
- - slash_for_doc_comments
- - type_init_formals
- - unnecessary_const
- - unnecessary_new
diff --git a/lib/algorithms.dart b/lib/algorithms.dart
index df0d712..7054141 100644
--- a/lib/algorithms.dart
+++ b/lib/algorithms.dart
@@ -6,4 +6,5 @@
@Deprecated('Will be removed in collection 2.0.0.')
library dart.pkg.collection.algorithms;
-export 'src/algorithms.dart';
+export 'src/algorithms.dart'
+ show binarySearch, insertionSort, lowerBound, mergeSort, shuffle, reverse;
diff --git a/lib/collection.dart b/lib/collection.dart
index 282d60f..27a75c8 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -2,7 +2,8 @@
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
-export 'src/algorithms.dart';
+export 'src/algorithms.dart'
+ show binarySearch, insertionSort, lowerBound, mergeSort, shuffle, reverse;
export 'src/canonicalized_map.dart';
export 'src/combined_wrappers/combined_iterable.dart';
export 'src/combined_wrappers/combined_list.dart';
@@ -12,7 +13,9 @@
export 'src/equality_map.dart';
export 'src/equality_set.dart';
export 'src/functions.dart';
+export 'src/iterable_extensions.dart';
export 'src/iterable_zip.dart';
+export 'src/list_extensions.dart';
export 'src/priority_queue.dart';
export 'src/queue_list.dart';
export 'src/union_set.dart';
diff --git a/lib/src/algorithms.dart b/lib/src/algorithms.dart
index 44a2b3b..d589e1e 100644
--- a/lib/src/algorithms.dart
+++ b/lib/src/algorithms.dart
@@ -2,7 +2,10 @@
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
-import 'dart:math' as math;
+/// A selection of data manipulation algorithms.
+library pkg.collection.algorithms;
+
+import 'dart:math' show Random;
import 'utils.dart';
@@ -12,19 +15,35 @@
/// is unpredictable.
///
/// If [compare] is omitted, this defaults to calling [Comparable.compareTo] on
-/// the objects. If any object is not [Comparable], this throws a [TypeError]
-/// (`CastError` on some SDK versions).
+/// the objects. In this case, the objects must be [Comparable].
+///
+/// Returns -1 if [value] is not in the list.
+int binarySearch<E>(List<E> sortedList, E value,
+ {int Function(E, E)? compare}) {
+ compare ??= defaultCompare;
+ return binarySearchBy<E, E>(sortedList, identity, compare, value);
+}
+
+/// Returns a position of the [value] in [sortedList], if it is there.
+///
+/// If the list isn't sorted according to the [compare] function on the [keyOf]
+/// property of the elements, the result is unpredictable.
///
/// Returns -1 if [value] is not in the list by default.
-int binarySearch<T>(List<T> sortedList, T value,
- {int Function(T, T)? compare}) {
- compare ??= defaultCompare();
- var min = 0;
- var max = sortedList.length;
+///
+/// If [start] and [end] are supplied, only that range is searched,
+/// and only that range need to be sorted.
+int binarySearchBy<E, K>(List<E> sortedList, K Function(E element) keyOf,
+ int Function(K, K) compare, E value,
+ [int start = 0, int? end]) {
+ end = RangeError.checkValidRange(start, end, sortedList.length);
+ var min = start;
+ var max = end;
+ var key = keyOf(value);
while (min < max) {
var mid = min + ((max - min) >> 1);
var element = sortedList[mid];
- var comp = compare(element, value);
+ var comp = compare(keyOf(element), key);
if (comp == 0) return mid;
if (comp < 0) {
min = mid + 1;
@@ -42,19 +61,36 @@
/// is unpredictable.
///
/// If [compare] is omitted, this defaults to calling [Comparable.compareTo] on
-/// the objects. If any object is not [Comparable], this throws a [TypeError]
-/// (`CastError` on some SDK versions).
+/// the objects. In this case, the objects must be [Comparable].
///
/// Returns [sortedList.length] if all the items in [sortedList] compare less
/// than [value].
-int lowerBound<T>(List<T> sortedList, T value, {int Function(T, T)? compare}) {
- compare ??= defaultCompare();
- var min = 0;
- var max = sortedList.length;
+int lowerBound<E>(List<E> sortedList, E value, {int Function(E, E)? compare}) {
+ compare ??= defaultCompare;
+ return lowerBoundBy<E, E>(sortedList, identity, compare, value);
+}
+
+/// Returns the first position in [sortedList] that is not before [value].
+///
+/// Elements are compared using the [compare] function of the [keyOf] property of
+/// the elements.
+/// If the list isn't sorted according to this order, the result is unpredictable.
+///
+/// Returns [sortedList.length] if all the items in [sortedList] are before [value].
+///
+/// If [start] and [end] are supplied, only that range is searched,
+/// and only that range need to be sorted.
+int lowerBoundBy<E, K>(List<E> sortedList, K Function(E element) keyOf,
+ int Function(K, K) compare, E value,
+ [int start = 0, int? end]) {
+ end = RangeError.checkValidRange(start, end, sortedList.length);
+ var min = start;
+ var max = end;
+ var key = keyOf(value);
while (min < max) {
var mid = min + ((max - min) >> 1);
var element = sortedList[mid];
- var comp = compare(element, value);
+ var comp = compare(keyOf(element), key);
if (comp < 0) {
min = mid + 1;
} else {
@@ -67,31 +103,36 @@
/// Shuffles a list randomly.
///
/// A sub-range of a list can be shuffled by providing [start] and [end].
-void shuffle(List list, [int start = 0, int? end]) {
- var random = math.Random();
- end ??= list.length;
+///
+/// If [start] or [end] are omitted,
+/// they default to the start and end of the list.
+///
+/// If [random] is omitted, it defaults to a new instance of [Random].
+void shuffle(List elements, [int start = 0, int? end, Random? random]) {
+ random ??= Random();
+ end ??= elements.length;
var length = end - start;
while (length > 1) {
var pos = random.nextInt(length);
length--;
- var tmp1 = list[start + pos];
- list[start + pos] = list[start + length];
- list[start + length] = tmp1;
+ var tmp1 = elements[start + pos];
+ elements[start + pos] = elements[start + length];
+ elements[start + length] = tmp1;
}
}
/// Reverses a list, or a part of a list, in-place.
-void reverse(List list, [int start = 0, int? end]) {
- end ??= list.length;
- _reverse(list, start, end);
+void reverse<E>(List<E> elements, [int start = 0, int? end]) {
+ end = RangeError.checkValidRange(start, end, elements.length);
+ _reverse<E>(elements, start, end);
}
/// Internal helper function that assumes valid arguments.
-void _reverse(List list, int start, int end) {
+void _reverse<E>(List<E> elements, int start, int end) {
for (var i = start, j = end - 1; i < j; i++, j--) {
- var tmp = list[i];
- list[i] = list[j];
- list[j] = tmp;
+ var tmp = elements[i];
+ elements[i] = elements[j];
+ elements[j] = tmp;
}
}
@@ -99,8 +140,7 @@
/// 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]
-/// (`CastError` on some SDK versions).
+/// the objects. In this case, the objects must be [Comparable].
///
/// 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
@@ -111,40 +151,50 @@
///
/// 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}) {
+void insertionSort<E>(List<E> elements,
+ {int Function(E, E)? 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();
- end ??= list.length;
+ compare ??= defaultCompare;
+ end ??= elements.length;
for (var pos = start + 1; pos < end; pos++) {
var min = start;
var max = pos;
- var element = list[pos];
+ var element = elements[pos];
while (min < max) {
var mid = min + ((max - min) >> 1);
- var comparison = compare(element, list[mid]);
+ var comparison = compare(element, elements[mid]);
if (comparison < 0) {
max = mid;
} else {
min = mid + 1;
}
}
- list.setRange(min + 1, pos + 1, list, min);
- list[min] = element;
+ elements.setRange(min + 1, pos + 1, elements, min);
+ elements[min] = element;
}
}
+/// Generalized insertion sort.
+///
+/// Performs insertion sort on the [elements] range from [start] to [end].
+/// Ordering is the [compare] of the [keyOf] of the elements.
+void insertionSortBy<E, K>(List<E> elements, K Function(E element) keyOf,
+ int Function(K a, K b) compare,
+ [int start = 0, int? end]) {
+ end = RangeError.checkValidRange(start, end, elements.length);
+ _movingInsertionSort(elements, keyOf, compare, start, end, elements, start);
+}
+
/// Limit below which merge sort defaults to insertion sort.
-const int _MERGE_SORT_LIMIT = 32;
+const int _mergeSortLimit = 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]
-/// (`CastError` on some SDK versions).
+/// the objects. If any object is not [Comparable], that throws a [TypeError].
///
/// Merge-sorting works by splitting the job into two parts, sorting each
/// recursively, and then merging the two sorted parts.
@@ -155,15 +205,53 @@
///
/// This merge sort is stable: Equal elements end up in the same order
/// as they started in.
-void mergeSort<T>(List<T> list,
- {int start = 0, int? end, int Function(T, T)? compare}) {
- end = RangeError.checkValidRange(start, end, list.length);
- compare ??= defaultCompare();
+void mergeSort<E>(List<E> elements,
+ {int start = 0, int? end, int Function(E, E)? compare}) {
+ end = RangeError.checkValidRange(start, end, elements.length);
+ compare ??= defaultCompare;
var length = end - start;
if (length < 2) return;
- if (length < _MERGE_SORT_LIMIT) {
- insertionSort(list, compare: compare, start: start, end: end);
+ if (length < _mergeSortLimit) {
+ insertionSort(elements, 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 allows the sorted elements to end up in the original list.
+ var firstLength = (end - start) >> 1;
+ 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]);
+ // TODO(linter/2097): Remove ignore when no longer required by linter.
+ // See: https://github.com/dart-lang/linter/issues/2097
+ E Function(E) id = identity; // ignore: omit_local_variable_types
+ _mergeSort(elements, id, compare, middle, end, scratchSpace, 0);
+ var firstTarget = end - firstLength;
+ _mergeSort(elements, id, compare, start, middle, elements, firstTarget);
+ _merge(id, compare, elements, firstTarget, end, scratchSpace, 0, secondLength,
+ elements, start);
+}
+
+/// Sort [elements] using a merge-sort algorithm.
+///
+/// The elements are compared using [compare] on the value provided by [keyOf]
+/// on the element.
+/// If [start] and [end] are provided, only that range is sorted.
+///
+/// Uses insertion sort for smaller sublists.
+void mergeSortBy<E, K>(List<E> elements, K Function(E element) keyOf,
+ int Function(K a, K b) compare,
+ [int start = 0, int? end]) {
+ end = RangeError.checkValidRange(start, end, elements.length);
+ var length = end - start;
+ if (length < 2) return;
+ if (length < _mergeSortLimit) {
+ _movingInsertionSort(elements, keyOf, compare, start, end, elements, start);
return;
}
// Special case the first split instead of directly calling
@@ -172,34 +260,41 @@
// 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.
- var middle = start + ((end - start) >> 1);
+ var middle = start + (length >> 1);
var firstLength = middle - start;
var secondLength = end - middle;
// secondLength is always the same as firstLength, or one greater.
- var scratchSpace = List<T>.filled(secondLength, list[start]);
- _mergeSort(list, compare, middle, end, scratchSpace, 0);
+ var scratchSpace = List<E>.filled(secondLength, elements[start]);
+ _mergeSort(elements, keyOf, compare, middle, end, scratchSpace, 0);
var firstTarget = end - firstLength;
- _mergeSort(list, compare, start, middle, list, firstTarget);
- _merge(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list,
- start);
+ _mergeSort(elements, keyOf, compare, start, middle, elements, firstTarget);
+ _merge(keyOf, compare, elements, firstTarget, end, scratchSpace, 0,
+ secondLength, elements, start);
}
/// 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) {
+void _movingInsertionSort<E, K>(
+ List<E> list,
+ K Function(E element) keyOf,
+ int Function(K, K) compare,
+ int start,
+ int end,
+ List<E> target,
+ int targetOffset) {
var length = end - start;
if (length == 0) return;
target[targetOffset] = list[start];
for (var i = 1; i < length; i++) {
var element = list[start + i];
+ var elementKey = keyOf(element);
var min = targetOffset;
var max = targetOffset + i;
while (min < max) {
var mid = min + ((max - min) >> 1);
- if (compare(element, target[mid]) < 0) {
+ if (compare(elementKey, keyOf(target[mid])) < 0) {
max = mid;
} else {
min = mid + 1;
@@ -210,18 +305,25 @@
}
}
-/// Sorts [list] from [start] to [end] into [target] at [targetOffset].
+/// Sorts [elements] 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
+/// Allows target to be the same list as [elements], 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) {
+void _mergeSort<E, K>(
+ List<E> elements,
+ K Function(E element) keyOf,
+ int Function(K, K) compare,
+ int start,
+ int end,
+ List<E> target,
+ int targetOffset) {
var length = end - start;
- if (length < _MERGE_SORT_LIMIT) {
- _movingInsertionSort(list, compare, start, end, target, targetOffset);
+ if (length < _mergeSortLimit) {
+ _movingInsertionSort<E, K>(
+ elements, keyOf, compare, start, end, target, targetOffset);
return;
}
var middle = start + (length >> 1);
@@ -230,12 +332,12 @@
// Here secondLength >= firstLength (differs by at most one).
var targetMiddle = targetOffset + firstLength;
// Sort the second half into the end of the target area.
- _mergeSort(list, compare, middle, end, target, targetMiddle);
+ _mergeSort(elements, keyOf, compare, middle, end, target, targetMiddle);
// Sort the first half into the end of the source area.
- _mergeSort(list, compare, start, middle, list, middle);
+ _mergeSort(elements, keyOf, compare, start, middle, elements, middle);
// Merge the two parts into the target area.
- _merge(compare, list, middle, middle + firstLength, target, targetMiddle,
- targetMiddle + secondLength, target, targetOffset);
+ _merge(keyOf, compare, elements, middle, middle + firstLength, target,
+ targetMiddle, targetMiddle + secondLength, target, targetOffset);
}
/// Merges two lists into a target list.
@@ -246,15 +348,16 @@
/// 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,
+void _merge<E, K>(
+ K Function(E element) keyOf,
+ int Function(K, K) compare,
+ List<E> firstList,
int firstStart,
int firstEnd,
- List<T> secondList,
+ List<E> secondList,
int secondStart,
int secondEnd,
- List<T> target,
+ List<E> target,
int targetOffset) {
// No empty lists reaches here.
assert(firstStart < firstEnd);
@@ -262,16 +365,20 @@
var cursor1 = firstStart;
var cursor2 = secondStart;
var firstElement = firstList[cursor1++];
+ var firstKey = keyOf(firstElement);
var secondElement = secondList[cursor2++];
+ var secondKey = keyOf(secondElement);
while (true) {
- if (compare(firstElement, secondElement) <= 0) {
+ if (compare(firstKey, secondKey) <= 0) {
target[targetOffset++] = firstElement;
if (cursor1 == firstEnd) break; // Flushing second list after loop.
firstElement = firstList[cursor1++];
+ firstKey = keyOf(firstElement);
} else {
target[targetOffset++] = secondElement;
if (cursor2 != secondEnd) {
secondElement = secondList[cursor2++];
+ secondKey = keyOf(secondElement);
continue;
}
// Second list empties first. Flushing first list here.
@@ -286,3 +393,71 @@
target.setRange(
targetOffset, targetOffset + (secondEnd - cursor2), secondList, cursor2);
}
+
+/// Sort [elements] using a quick-sort algorithm.
+///
+/// The elements are compared using [compare] on the elements.
+/// If [start] and [end] are provided, only that range is sorted.
+///
+/// Uses insertion sort for smaller sublists.
+void quickSort<E>(List<E> elements, int Function(E a, E b) compare,
+ [int start = 0, int? end]) {
+ end = RangeError.checkValidRange(start, end, elements.length);
+ _quickSort<E, E>(elements, identity, compare, Random(), start, end);
+}
+
+/// Sort [elements] using a quick-sort algorithm.
+///
+/// The elements are compared using [compare] on the value provided by [keyOf]
+/// on the element.
+/// If [start] and [end] are provided, only that range is sorted.
+///
+/// Uses insertion sort for smaller sublists.
+void quickSortBy<E, K>(
+ List<E> list, K Function(E element) keyOf, int Function(K a, K b) compare,
+ [int start = 0, int? end]) {
+ end = RangeError.checkValidRange(start, end, list.length);
+ _quickSort(list, keyOf, compare, Random(), start, end);
+}
+
+void _quickSort<E, K>(List<E> list, K Function(E element) keyOf,
+ int Function(K a, K b) compare, Random random, int start, int end) {
+ const minQuickSortLength = 24;
+ var length = end - start;
+ while (length >= minQuickSortLength) {
+ var pivotIndex = random.nextInt(length) + start;
+ var pivot = list[pivotIndex];
+ var pivotKey = keyOf(pivot);
+ var endSmaller = start;
+ var startGreater = end;
+ var startPivots = end - 1;
+ list[pivotIndex] = list[startPivots];
+ list[startPivots] = pivot;
+ while (endSmaller < startPivots) {
+ var current = list[endSmaller];
+ var relation = compare(keyOf(current), pivotKey);
+ if (relation < 0) {
+ endSmaller++;
+ } else {
+ startPivots--;
+ var currentTarget = startPivots;
+ list[endSmaller] = list[startPivots];
+ if (relation > 0) {
+ startGreater--;
+ currentTarget = startGreater;
+ list[startPivots] = list[startGreater];
+ }
+ list[currentTarget] = current;
+ }
+ }
+ if (endSmaller - start < end - startGreater) {
+ _quickSort(list, keyOf, compare, random, start, endSmaller);
+ start = startGreater;
+ } else {
+ _quickSort(list, keyOf, compare, random, startGreater, end);
+ end = endSmaller;
+ }
+ length = end - start;
+ }
+ _movingInsertionSort<E, K>(list, keyOf, compare, start, end, list, start);
+}
diff --git a/lib/src/functions.dart b/lib/src/functions.dart
index 07c8d4b..8e73f16 100644
--- a/lib/src/functions.dart
+++ b/lib/src/functions.dart
@@ -64,7 +64,7 @@
/// Returns `null` if [values] is empty.
S? minBy<S, T>(Iterable<S> values, T Function(S) orderBy,
{int Function(T, T)? compare}) {
- compare ??= defaultCompare<T>();
+ compare ??= defaultCompare;
S? minValue;
T? minOrderBy;
@@ -88,7 +88,7 @@
/// Returns `null` if [values] is empty.
S? maxBy<S, T>(Iterable<S> values, T Function(S?) orderBy,
{int? Function(T, T)? compare}) {
- compare ??= defaultCompare<T>();
+ compare ??= defaultCompare;
S? maxValue;
T? maxOrderBy;
diff --git a/lib/src/iterable_extensions.dart b/lib/src/iterable_extensions.dart
new file mode 100644
index 0000000..728c1ec
--- /dev/null
+++ b/lib/src/iterable_extensions.dart
@@ -0,0 +1,762 @@
+// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import 'package:collection/src/utils.dart';
+
+import 'algorithms.dart';
+
+/// Extensions that apply to all iterables.
+///
+/// These extensions provide direct access to some of the
+/// algorithms expose by this package,
+/// as well as some generally useful convenience methods.
+///
+/// More specialized extension methods that only apply to
+/// iterables with specific element types include those of
+/// [IterableComparableExtension] and [IterableNullableExtension].
+extension IterableExtension<T> on Iterable<T> {
+ /// The elements that do not satisfy [test].
+ Iterable<T> whereNot(bool Function(T element) test) =>
+ where((element) => !test(element));
+
+ /// Creates a sorted list of the elements of the iterable.
+ ///
+ /// The elements are ordered by the [compare] [Comparator].
+ List<T> sorted(Comparator<T> compare) => [...this]..sort(compare);
+
+ /// Creates a sorted list of the elements of the iterable.
+ ///
+ /// The elements are ordered by the natural ordering of the
+ /// property [keyOf] of the element.
+ List<T> sortedBy<K extends Comparable<K>>(K Function(T element) keyOf) {
+ var elements = [...this];
+ quickSortBy<T, K>(elements, keyOf, compareComparable);
+ return elements;
+ }
+
+ /// Creates a sorted list of the elements of the iterable.
+ ///
+ /// The elements are ordered by the [compare] [Comparator] of the
+ /// property [keyOf] of the element.
+ List<T> sortedByCompare<K>(
+ K Function(T element) keyOf, Comparator<K> compare) {
+ var elements = [...this];
+ quickSortBy<T, K>(elements, keyOf, compare);
+ return elements;
+ }
+
+ /// Whether the elements are sorted by the [compare] ordering.
+ ///
+ /// Compares pairs of elements using `compare` to check that
+ /// the elements of this iterable to check
+ /// that earlier elements always compare
+ /// smaller than or equal to later elements.
+ ///
+ /// An single-element or empty iterable is trivially in sorted order.
+ bool isSorted(Comparator<T> compare) {
+ var iterator = this.iterator;
+ if (!iterator.moveNext()) return true;
+ var previousElement = iterator.current;
+ while (iterator.moveNext()) {
+ var element = iterator.current;
+ if (compare(previousElement, element) > 0) return false;
+ previousElement = element;
+ }
+ return true;
+ }
+
+ /// Whether the elements are sorted by their [keyOf] property.
+ ///
+ /// Applies [keyOf] to each element in iteration order,
+ /// then checks whether the results are in non-decreasing [Comparable] order.
+ bool isSortedBy<K extends Comparable<K>>(K Function(T element) keyOf) {
+ var iterator = this.iterator;
+ if (!iterator.moveNext()) return true;
+ var previousKey = keyOf(iterator.current);
+ while (iterator.moveNext()) {
+ var key = keyOf(iterator.current);
+ if (previousKey.compareTo(key) > 0) return false;
+ previousKey = key;
+ }
+ return true;
+ }
+
+ /// Whether the elements are [compare]-sorted by their [keyOf] property.
+ ///
+ /// Applies [keyOf] to each element in iteration order,
+ /// then checks whether the results are in non-decreasing order
+ /// using the [compare] [Comparator]..
+ bool isSortedByCompare<K>(
+ K Function(T element) keyOf, Comparator<K> compare) {
+ var iterator = this.iterator;
+ if (!iterator.moveNext()) return true;
+ var previousKey = keyOf(iterator.current);
+ while (iterator.moveNext()) {
+ var key = keyOf(iterator.current);
+ if (compare(previousKey, key) > 0) return false;
+ previousKey = key;
+ }
+ return true;
+ }
+
+ /// Takes an action for each element.
+ ///
+ /// Calls [action] for each element along with the index in the
+ /// iteration order.
+ void forEachIndexed(void Function(int index, T element) action) {
+ var index = 0;
+ for (var element in this) {
+ action(index++, element);
+ }
+ }
+
+ /// Takes an action for each element as long as desired.
+ ///
+ /// Calls [action] for each element.
+ /// Stops iteration if [action] returns `false`.
+ void forEachWhile(bool Function(T element) action) {
+ for (var element in this) {
+ if (!action(element)) break;
+ }
+ }
+
+ /// Takes an action for each element and index as long as desired.
+ ///
+ /// Calls [action] for each element along with the index in the
+ /// iteration order.
+ /// Stops iteration if [action] returns `false`.
+ void forEachIndexedWhile(bool Function(int index, T element) action) {
+ var index = 0;
+ for (var element in this) {
+ if (!action(index++, element)) break;
+ }
+ }
+
+ /// Maps each element and its index to a new value.
+ Iterable<R> mapIndexed<R>(R Function(int index, T element) convert) sync* {
+ var index = 0;
+ for (var element in this) {
+ yield convert(index++, element);
+ }
+ }
+
+ /// The elements whose value and index satisfies [test].
+ Iterable<T> whereIndexed(bool Function(int index, T element) test) sync* {
+ var index = 0;
+ for (var element in this) {
+ if (test(index++, element)) yield element;
+ }
+ }
+
+ /// The elements whose value and index do not satisfy [test].
+ Iterable<T> whereNotIndexed(bool Function(int index, T element) test) sync* {
+ var index = 0;
+ for (var element in this) {
+ if (!test(index++, element)) yield element;
+ }
+ }
+
+ /// Expands each element and index to a number of elements in a new iterable.
+ Iterable<R> expandIndexed<R>(
+ Iterable<R> Function(int index, T element) expend) sync* {
+ var index = 0;
+ for (var element in this) {
+ yield* expend(index++, element);
+ }
+ }
+
+ /// Combine the elements with each other and the current index.
+ ///
+ /// Calls [combine] for each element except the first.
+ /// The call passes the index of the current element, the result of the
+ /// previous call, or the first element for the first call, and
+ /// the current element.
+ ///
+ /// Returns the result of the last call, or the first element if
+ /// there is only one element.
+ /// There must be at least one element.
+ T reduceIndexed(T Function(int index, T previous, T element) combine) {
+ var iterator = this.iterator;
+ if (!iterator.moveNext()) {
+ throw StateError('no elements');
+ }
+ var index = 1;
+ var result = iterator.current;
+ while (iterator.moveNext()) {
+ result = combine(index++, result, iterator.current);
+ }
+ return result;
+ }
+
+ /// Combine the elements with a value and the current index.
+ ///
+ /// Calls [combine] for each element with the current index,
+ /// the result of the previous call, or [initialValue] for the first element,
+ /// and the current element.
+ ///
+ /// Returns the result of the last call to [combine],
+ /// or [initialValue] if there are no elements.
+ R foldIndexed<R>(
+ R initialValue, R Function(int index, R previous, T element) combine) {
+ var result = initialValue;
+ var index = 0;
+ for (var element in this) {
+ result = combine(index++, result, element);
+ }
+ return result;
+ }
+
+ /// The first element satisfying [test], or `null` if there are none.
+ T? firstWhereOrNull(bool Function(T element) test) {
+ for (var element in this) {
+ if (test(element)) return element;
+ }
+ return null;
+ }
+
+ /// The first element whose value and index satisfies [test].
+ ///
+ /// Returns `null` if there are no element and index satisfying [test].
+ T? firstWhereIndexedOrNull(bool Function(int index, T element) test) {
+ var index = 0;
+ for (var element in this) {
+ if (test(index++, element)) return element;
+ }
+ return null;
+ }
+
+ /// The first element, or `null` if the iterable is empty.
+ T? get firstOrNull {
+ var iterator = this.iterator;
+ if (iterator.moveNext()) return iterator.current;
+ return null;
+ }
+
+ /// The last element satisfying [test], or `null` if there are none.
+ T? lastWhereOrNull(bool Function(T element) test) {
+ T? result;
+ for (var element in this) {
+ if (test(element)) result = element;
+ }
+ return result;
+ }
+
+ /// The last element whose index and value satisfies [test].
+ ///
+ /// Returns `null` if no element and index satisfies [test].
+ T? lastWhereIndexedOrNull(bool Function(int index, T element) test) {
+ T? result;
+ var index = 0;
+ for (var element in this) {
+ if (test(index++, element)) result = element;
+ }
+ return result;
+ }
+
+ /// The last element, or `null` if the iterable is empty.
+ T? get lastOrNull {
+ if (isEmpty) return null;
+ return last;
+ }
+
+ /// The single element satisfying [test].
+ ///
+ /// Returns `null` if there are either no elements
+ /// or more than one element satisfying [test].
+ ///
+ /// **Notice**: This behavior differs from [Iterable.singleWhere]
+ /// which always throws if there are more than one match,
+ /// and only calls the `orElse` function on zero matchs.
+ T? singleWhereOrNull(bool Function(T element) test) {
+ T? result;
+ var found = false;
+ for (var element in this) {
+ if (test(element)) {
+ if (!found) {
+ result = element;
+ found = true;
+ } else {
+ return null;
+ }
+ }
+ }
+ return result;
+ }
+
+ /// The single element satisfying [test].
+ ///
+ /// Returns `null` if there are either none
+ /// or more than one element and index satisfying [test].
+ T? singleWhereIndexedOrNull(bool Function(int index, T element) test) {
+ T? result;
+ var found = false;
+ var index = 0;
+ for (var element in this) {
+ if (test(index++, element)) {
+ if (!found) {
+ result = element;
+ found = true;
+ } else {
+ return null;
+ }
+ }
+ }
+ return result;
+ }
+
+ /// The single element of the iterable, or `null`.
+ ///
+ /// The value is `null` if the iterable is empty
+ /// or it contains more than one element.
+ T? get singleOrNull {
+ var iterator = this.iterator;
+ if (iterator.moveNext()) {
+ var result = iterator.current;
+ if (!iterator.moveNext()) {
+ return result;
+ }
+ }
+ return null;
+ }
+
+ /// Groups elements by [keyOf] then folds the elements in each group.
+ ///
+ /// A key is found for each element using [keyOf].
+ /// Then the elements with the same key are all folded using [combine].
+ /// The first call to [combine] for a particular key receives [null] as
+ /// the previous value, the remaining ones receive the result of the previous call.
+ ///
+ /// Can be used to _group_ elements into arbitrary collections.
+ /// For example [groupSetsBy] could be written as:
+ /// ```dart
+ /// iterable.groupFoldBy(keyOf,
+ /// (Set<T>? previous, T element) => (previous ?? <T>{})..add(element));
+ /// ````
+ Map<K, G> groupFoldBy<K, G>(
+ K Function(T element) keyOf, G Function(G? previous, T element) combine) {
+ var result = <K, G>{};
+ for (var element in this) {
+ var key = keyOf(element);
+ result[key] = combine(result[key], element);
+ }
+ return result;
+ }
+
+ /// Groups elements into sets by [keyOf].
+ Map<K, Set<T>> groupSetsBy<K>(K Function(T element) keyOf) {
+ var result = <K, Set<T>>{};
+ for (var element in this) {
+ (result[keyOf(element)] ??= <T>{})..add(element);
+ }
+ return result;
+ }
+
+ /// Groups elements into lists by [keyOf].
+ Map<K, List<T>> groupListsBy<K>(K Function(T element) keyOf) {
+ var result = <K, List<T>>{};
+ for (var element in this) {
+ (result[keyOf(element)] ??= [])..add(element);
+ }
+ return result;
+ }
+
+ /// Splits the elements into chunks before some elements.
+ ///
+ /// Each element except the first is checked using [test]
+ /// for whether it should start a new chunk.
+ /// If so, the elements since the previous chunk-starting element
+ /// are emitted as a list.
+ /// Any final elements are emitted at the end.
+ ///
+ /// Example:
+ /// Example:
+ /// ```dart
+ /// var parts = [1, 2, 3, 4, 5, 6, 7, 8, 9].split(isPrime);
+ /// print(parts); // ([1], [2], [3, 4], [5, 6], [7, 8, 9])
+ /// ```
+ Iterable<List<T>> splitBefore(bool Function(T element) test) =>
+ splitBeforeIndexed((_, element) => test(element));
+
+ /// Splits the elements into chunks before some elements.
+ ///
+ /// Each element is checked using [test] for whether it should start a new chunk.
+ /// If so, the elements since the previous chunk-starting element
+ /// are emitted as a list.
+ /// Any final elements are emitted at the end.
+ ///
+ /// Example:
+ /// ```dart
+ /// var parts = [1, 0, 2, 1, 5, 7, 6, 8, 9].splitAfter(isPrime);
+ /// print(parts); // ([1, 0, 2], [1, 5], [7], [6, 8, 9])
+ /// ```
+ Iterable<List<T>> splitAfter(bool Function(T element) test) =>
+ splitAfterIndexed((_, element) => test(element));
+
+ /// Splits the elements into chunks between some elements.
+ ///
+ /// Each pair of adjacent elements are checked using [test]
+ /// for whether a chunk should end between them.
+ /// If so, the elements since the previous chunk-splitting elements
+ /// are emitted as a list.
+ /// Any final elements are emitted at the end.
+ ///
+ /// Example:
+ /// ```dart
+ /// var parts = [1, 0, 2, 1, 5, 7, 6, 8, 9].splitBetween((i, v1, v2) => v1 > v2);
+ /// print(parts); // ([1], [0, 2], [1, 5, 7], [6, 8, 9])
+ /// ```
+ Iterable<List<T>> splitBetween(bool Function(T first, T second) test) =>
+ splitBetweenIndexed((_, first, second) => test(first, second));
+
+ /// Splits the elements into chunks before some elements and indices.
+ ///
+ /// Each element and index except the first is checked using [test]
+ /// for whether it should start a new chunk.
+ /// If so, the elements since the previous chunk-starting element
+ /// are emitted as a list.
+ /// Any final elements are emitted at the end.
+ ///
+ /// Example:
+ /// ```dart
+ /// var parts = [1, 0, 2, 1, 5, 7, 6, 8, 9]
+ /// .splitBeforeIndexed((i, v) => i < v);
+ /// print(parts); // ([1], [0, 2], [1, 5, 7], [6, 8, 9])
+ /// ```
+ Iterable<List<T>> splitBeforeIndexed(
+ bool Function(int index, T element) test) sync* {
+ var iterator = this.iterator;
+ if (!iterator.moveNext()) {
+ return;
+ }
+ var index = 1;
+ var chunk = [iterator.current];
+ while (iterator.moveNext()) {
+ var element = iterator.current;
+ if (test(index++, element)) {
+ yield chunk;
+ chunk = [];
+ }
+ chunk.add(element);
+ }
+ yield chunk;
+ }
+
+ /// Splits the elements into chunks after some elements and indices.
+ ///
+ /// Each element and index is checked using [test]
+ /// for whether it should end the current chunk.
+ /// If so, the elements since the previous chunk-ending element
+ /// are emitted as a list.
+ /// Any final elements are emitted at the end, whether the last
+ /// element should be split after or not.
+ ///
+ /// Example:
+ /// ```dart
+ /// var parts = [1, 0, 2, 1, 5, 7, 6, 8, 9].splitAfterIndexed((i, v) => i < v);
+ /// print(parts); // ([1, 0], [2, 1], [5, 7, 6], [8, 9])
+ /// ```
+ Iterable<List<T>> splitAfterIndexed(
+ bool Function(int index, T element) test) sync* {
+ var index = 0;
+ List<T>? chunk;
+ for (var element in this) {
+ (chunk ??= []).add(element);
+ if (test(index++, element)) {
+ yield chunk;
+ chunk = null;
+ }
+ }
+ if (chunk != null) yield chunk;
+ }
+
+ /// Splits the elements into chunks between some elements and indices.
+ ///
+ /// Each pair of adjacent elements and the index of the latter are
+ /// checked using [test] for whether a chunk should end between them.
+ /// If so, the elements since the previous chunk-splitting elements
+ /// are emitted as a list.
+ /// Any final elements are emitted at the end.
+ ///
+ /// Example:
+ /// ```dart
+ /// var parts = [1, 0, 2, 1, 5, 7, 6, 8, 9]
+ /// .splitBetweenIndexed((i, v1, v2) => v1 > v2);
+ /// print(parts); // ([1], [0, 2], [1, 5, 7], [6, 8, 9])
+ /// ```
+ Iterable<List<T>> splitBetweenIndexed(
+ bool Function(int index, T first, T second) test) sync* {
+ var iterator = this.iterator;
+ if (!iterator.moveNext()) return;
+ var previous = iterator.current;
+ var chunk = <T>[previous];
+ var index = 1;
+ while (iterator.moveNext()) {
+ var element = iterator.current;
+ if (test(index++, previous, element)) {
+ yield chunk;
+ chunk = [];
+ }
+ chunk.add(element);
+ previous = element;
+ }
+ yield chunk;
+ }
+
+ /// Whether no element satisfies [test].
+ ///
+ /// Returns true if no element satisfies [test],
+ /// and false if at least one does.
+ ///
+ /// Equivalent to `iterable.every((x) => !test(x))` or
+ /// `!iterable.any(test)`.
+ bool none(bool Function(T) test) {
+ for (var element in this) {
+ if (test(element)) return false;
+ }
+ return true;
+ }
+}
+
+/// Extensions that apply to iterables with a nullable element type.
+extension IterableNullableExtension<T extends Object> on Iterable<T?> {
+ /// The non-`null` elements of this `Iterable`.
+ ///
+ /// Returns an iterable which emits all the non-`null` elements
+ /// of this iterable, in their original iteration order.
+ ///
+ /// For an `Iterable<X?>`, this method is equivalent to `.whereType<X>()`.
+ Iterable<T> whereNotNull() sync* {
+ for (var element in this) {
+ if (element != null) yield element;
+ }
+ }
+}
+
+/// Extensions that apply to iterables of numbers.
+extension IterableNumberExtension on Iterable<num> {
+ /// The sum of the elements.
+ ///
+ /// The sum is zero if the iterable is empty.
+ num get sum {
+ num result = 0;
+ for (var value in this) {
+ result += value;
+ }
+ return result;
+ }
+
+ /// The arithmetic mean of the elements of a non-empty iterable.
+ ///
+ /// The arithmetic mean is the sum of the elements
+ /// divided by the number of elements.
+ ///
+ /// The iterable must not be empty.
+ double get average {
+ var result = 0.0;
+ var count = 0;
+ for (var value in this) {
+ count += 1;
+ result += (value - result) / count;
+ }
+ if (count == 0) throw StateError('No elements');
+ return result;
+ }
+}
+
+/// Extension on iterables of integers.
+///
+/// Specialized version of some extensions of [IterableNumberExtension].
+extension IterableIntegerExtension on Iterable<int> {
+ /// The sum of the elements.
+ ///
+ /// The sum is zero if the iterable is empty.
+ int get sum {
+ var result = 0;
+ for (var value in this) {
+ result += value;
+ }
+ return result;
+ }
+
+ /// The arithmetic mean of the elements of a non-empty iterable.
+ ///
+ /// The arithmetic mean is the sum of the elements
+ /// divided by the number of elements.
+ /// This method is specialized for integers,
+ /// and may give a different result than [IterableNumberExtension.average]
+ /// for the same values, because the the number algorithm
+ /// converts all numbers to doubles.
+ ///
+ /// The iterable must not be empty.
+ double get average {
+ var average = 0;
+ var remainder = 0;
+ var count = 0;
+ for (var value in this) {
+ // Invariant: Sum of values so far = average * count + remainder.
+ // (Unless overflow has occurred).
+ count += 1;
+ var delta = value - average + remainder;
+ average += delta ~/ count;
+ remainder = delta.remainder(count);
+ }
+ if (count == 0) throw StateError('No elements');
+ return average + remainder / count;
+ }
+}
+
+/// Extension on iterables of double.
+///
+/// Specialized version of some extensions of [IterableNumberExtension].
+extension IterableDoubleExtension on Iterable<double> {
+ /// The sum of the elements.
+ ///
+ /// The sum is zero if the iterable is empty.
+ double get sum {
+ var result = 0.0;
+ for (var value in this) {
+ result += value;
+ }
+ return result;
+ }
+}
+
+/// Extensions on iterables whose elements are also iterables.
+extension IterableIterableExtension<T> on Iterable<Iterable<T>> {
+ /// The sequential elements of each iterable in this iterable.
+ ///
+ /// Iterates the elements of this iterable.
+ /// For each one, which is itself an iterable,
+ /// all the elements of that are emitted
+ /// on the returned iterable, before moving on to the next element.
+ Iterable<T> get flattened sync* {
+ for (var elements in this) {
+ yield* elements;
+ }
+ }
+}
+
+/// Extensions that apply to iterables of [Comparable] elements.
+///
+/// These operations can assume that the elements have a natural ordering,
+/// and can therefore omit, or make it optional, for the user to provide
+/// a [Comparator].
+extension IterableComparableExtension<T extends Comparable<T>> on Iterable<T> {
+ /// A minimal element of the iterable, or `null` it the iterable is empty.
+ T? get minOrNull {
+ var iterator = this.iterator;
+ if (iterator.moveNext()) {
+ var value = iterator.current;
+ while (iterator.moveNext()) {
+ var newValue = iterator.current;
+ if (value.compareTo(newValue) > 0) {
+ value = newValue;
+ }
+ }
+ return value;
+ }
+ return null;
+ }
+
+ /// A minimal element of the iterable.
+ ///
+ /// The iterable must not be empty.
+ T get min {
+ var iterator = this.iterator;
+ if (iterator.moveNext()) {
+ var value = iterator.current;
+ while (iterator.moveNext()) {
+ var newValue = iterator.current;
+ if (value.compareTo(newValue) > 0) {
+ value = newValue;
+ }
+ }
+ return value;
+ }
+ throw StateError('No element');
+ }
+
+ /// A maximal element of the iterable, or `null` if the iterable is empty.
+ T? get maxOrNull {
+ var iterator = this.iterator;
+ if (iterator.moveNext()) {
+ var value = iterator.current;
+ while (iterator.moveNext()) {
+ var newValue = iterator.current;
+ if (value.compareTo(newValue) < 0) {
+ value = newValue;
+ }
+ }
+ return value;
+ }
+ return null;
+ }
+
+ /// A maximal element of the iterable.
+ ///
+ /// The iterable must not be empty.
+ T get max {
+ var iterator = this.iterator;
+ if (iterator.moveNext()) {
+ var value = iterator.current;
+ while (iterator.moveNext()) {
+ var newValue = iterator.current;
+ if (value.compareTo(newValue) < 0) {
+ value = newValue;
+ }
+ }
+ return value;
+ }
+ throw StateError('No element');
+ }
+
+ /// Creates a sorted list of the elements of the iterable.
+ ///
+ /// If the [compare] function is not supplied, the sorting uses the
+ /// natural [Comparable] ordering of the elements.
+ List<T> sorted([Comparator<T>? compare]) => [...this]..sort(compare);
+
+ /// Whether the elements are sorted by the [compare] ordering.
+ ///
+ /// If [compare] is omitted, it defaults to comparing the
+ /// elements using their natural [Comparable] ordering.
+ bool isSorted([Comparator<T>? compare]) {
+ if (compare != null) {
+ return IterableExtension(this).isSorted(compare);
+ }
+ var iterator = this.iterator;
+ if (!iterator.moveNext()) return true;
+ var previousElement = iterator.current;
+ while (iterator.moveNext()) {
+ var element = iterator.current;
+ if (previousElement.compareTo(element) > 0) return false;
+ previousElement = element;
+ }
+ return true;
+ }
+}
+
+/// Extensions on comparator functions.
+extension ComparatorExtension<T> on Comparator<T> {
+ /// The inverse ordering of this comparator.
+ int Function(T, T) get inverse => (T a, T b) => this(b, a);
+
+ /// Makes a comparator on [R] values using this comparator.
+ ///
+ /// Compares [R] values by comparing their [keyOf] value
+ /// using this comparator.
+ Comparator<R> compareBy<R>(T Function(R) keyOf) =>
+ (R a, R b) => this(keyOf(a), keyOf(b));
+
+ /// Combine comparators sequentially.
+ ///
+ /// Creates a comparator which orders elements the same way as
+ /// this comparator, except that when two elements are considered
+ /// equal, the [tieBreaker] comparator is used instead.
+ Comparator<T> then(Comparator<T> tieBreaker) => (T a, T b) {
+ var result = this(a, b);
+ if (result == 0) result = tieBreaker(a, b);
+ return result;
+ };
+}
diff --git a/lib/src/list_extensions.dart b/lib/src/list_extensions.dart
new file mode 100644
index 0000000..c1f4af0
--- /dev/null
+++ b/lib/src/list_extensions.dart
@@ -0,0 +1,482 @@
+// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+// Extension methods on common collection types.
+import 'dart:collection';
+import 'dart:math';
+
+import 'algorithms.dart';
+import 'algorithms.dart' as algorithms;
+import 'equality.dart';
+import 'utils.dart';
+
+/// Various extensions on lists of arbitrary elements.
+extension ListExtensions<E> on List<E> {
+ /// Returns the index of [element] in this sorted list.
+ ///
+ /// Uses binary search to find the location of [element].
+ /// The list *must* be sorted according to [compare],
+ /// otherwise the result is unspecified
+ ///
+ /// Returns -1 if [element] does not occur in this list.
+ int binarySearch(E element, int Function(E, E) compare) =>
+ algorithms.binarySearchBy<E, E>(this, identity, compare, element);
+
+ /// Returns the index of [element] in this sorted list.
+ ///
+ /// Uses binary search to find the location of [element].
+ /// The list *must* be sorted according to [compare] on the [keyOf] of elements,
+ /// otherwise the result is unspecified.
+ ///
+ /// Returns -1 if [element] does not occur in this list.
+ ///
+ /// If [start] and [end] are supplied, only the list range from [start] to [end]
+ /// is searched, and only that range needs to be sorted.
+ int binarySearchByCompare<K>(
+ E element, K Function(E element) keyOf, int Function(K, K) compare,
+ [int start = 0, int? end]) =>
+ algorithms.binarySearchBy<E, K>(
+ this, keyOf, compare, element, start, end);
+
+ /// Returns the index of [element] in this sorted list.
+ ///
+ /// Uses binary search to find the location of [element].
+ /// The list *must* be sorted according to the natural ordering of
+ /// the [keyOf] of elements, otherwise the result is unspecified.
+ ///
+ /// Returns -1 if [element] does not occur in this list.
+ ///
+ /// If [start] and [end] are supplied, only the list range from [start] to [end]
+ /// is searched, and only that range needs to be sorted.
+ int binarySearchBy<K extends Comparable<K>>(
+ E element, K Function(E element) keyOf, [int start = 0, int? end]) =>
+ algorithms.binarySearchBy<E, K>(
+ this, keyOf, (a, b) => a.compareTo(b), element, start, end);
+
+ /// Returns the index where [element] should be in this sorted list.
+ ///
+ /// Uses binary search to find the location of [element].
+ /// The list *must* be sorted according to [compare],
+ /// otherwise the result is unspecified.
+ ///
+ /// If [element] is in the list, its index is returned,
+ /// otherwise returns the first position where adding [element]
+ /// would keep the list sorted. This may be the [length] of
+ /// the list if all elements of the list compare less than
+ /// [element].
+ int lowerBound(E element, int Function(E, E) compare) =>
+ algorithms.lowerBoundBy<E, E>(this, identity, compare, element);
+
+ /// Returns the index where [element] should be in this sorted list.
+ ///
+ /// Uses binary search to find the location of [element].
+ /// The list *must* be sorted according to [compare] of
+ /// the [keyOf] of the elements, otherwise the result is unspecified.
+ ///
+ /// If [element] is in the list, its index is returned,
+ /// otherwise returns the first position where adding [element]
+ /// would keep the list sorted. This may be the [length] of
+ /// the list if all elements of the list compare less than
+ /// [element].
+ ///
+ /// If [start] and [end] are supplied, only that range is searched,
+ /// and only that range need to be sorted.
+ int lowerBoundByCompare<K>(
+ E element, K Function(E) keyOf, int Function(K, K) compare,
+ [int start = 0, int? end]) =>
+ algorithms.lowerBoundBy(this, keyOf, compare, element, start, end);
+
+ /// Returns the index where [element] should be in this sorted list.
+ ///
+ /// Uses binary search to find the location of [element].
+ /// The list *must* be sorted according to the
+ /// natural ordering of the [keyOf] of the elements,
+ /// otherwise the result is unspecified.
+ ///
+ /// If [element] is in the list, its index is returned,
+ /// otherwise returns the first position where adding [element]
+ /// would keep the list sorted. This may be the [length] of
+ /// the list if all elements of the list compare less than
+ /// [element].
+ ///
+ /// If [start] and [end] are supplied, only that range is searched,
+ /// and only that range need to be sorted.
+ int lowerBoundBy<K extends Comparable<K>>(E element, K Function(E) keyOf,
+ [int start = 0, int? end]) =>
+ algorithms.lowerBoundBy<E, K>(
+ this, keyOf, compareComparable, element, start, end);
+
+ /// Takes an action for each element.
+ ///
+ /// Calls [action] for each element along with the index in the
+ /// iteration order.
+ void forEachIndexed(void Function(int index, E element) action) {
+ for (var index = 0; index < length; index++) {
+ action(index, this[index]);
+ }
+ }
+
+ /// Takes an action for each element as long as desired.
+ ///
+ /// Calls [action] for each element.
+ /// Stops iteration if [action] returns `false`.
+ void forEachWhile(bool Function(E element) action) {
+ for (var index = 0; index < length; index++) {
+ if (!action(this[index])) break;
+ }
+ }
+
+ /// Takes an action for each element and index as long as desired.
+ ///
+ /// Calls [action] for each element along with the index in the
+ /// iteration order.
+ /// Stops iteration if [action] returns `false`.
+ void forEachIndexedWhile(bool Function(int index, E element) action) {
+ for (var index = 0; index < length; index++) {
+ if (!action(index, this[index])) break;
+ }
+ }
+
+ /// Maps each element and its index to a new value.
+ Iterable<R> mapIndexed<R>(R Function(int index, E element) convert) sync* {
+ for (var index = 0; index < length; index++) {
+ yield convert(index, this[index]);
+ }
+ }
+
+ /// The elements whose value and index satisfies [test].
+ Iterable<E> whereIndexed(bool Function(int index, E element) test) sync* {
+ for (var index = 0; index < length; index++) {
+ var element = this[index];
+ if (test(index, element)) yield element;
+ }
+ }
+
+ /// The elements whose value and index do not satisfy [test].
+ Iterable<E> whereNotIndexed(bool Function(int index, E element) test) sync* {
+ for (var index = 0; index < length; index++) {
+ var element = this[index];
+ if (!test(index, element)) yield element;
+ }
+ }
+
+ /// Expands each element and index to a number of elements in a new iterable.
+ ///
+ /// Like [Iterable.expand] except that the callback function is supplied with
+ /// both the index and the element.
+ Iterable<R> expendIndexed<R>(
+ Iterable<R> Function(int index, E element) expand) sync* {
+ for (var index = 0; index < length; index++) {
+ yield* expand(index, this[index]);
+ }
+ }
+
+ /// Sort a range of elements by [compare].
+ void sortRange(int start, int end, int Function(E a, E b) compare) {
+ quickSortBy<E, E>(this, identity, compare, start, end);
+ }
+
+ /// Sorts elements by the [compare] of their [keyOf] property.
+ ///
+ /// Sorts elements from [start] to [end], defaulting to the entire list.
+ void sortByCompare<K>(
+ K Function(E element) keyOf, int Function(K a, K b) compare,
+ [int start = 0, int? end]) {
+ quickSortBy(this, keyOf, compare, start, end);
+ }
+
+ /// Sorts elements by the natural order of their [keyOf] property.
+ ///
+ /// Sorts elements from [start] to [end], defaulting to the entire list.
+ void sortBy<K extends Comparable<K>>(K Function(E element) keyOf,
+ [int start = 0, int? end]) {
+ quickSortBy<E, K>(this, keyOf, compareComparable, start, end);
+ }
+
+ /// Shuffle a range of elements.
+ void shuffleRange(int start, int end, [Random? random]) {
+ RangeError.checkValidRange(start, end, length);
+ shuffle(this, start, end, random);
+ }
+
+ /// Reverses the elements in a range of the list.
+ void reverseRange(int start, int end) {
+ RangeError.checkValidRange(start, end, length);
+ while (start < --end) {
+ var tmp = this[start];
+ this[start] = this[end];
+ this[end] = tmp;
+ start += 1;
+ }
+ }
+
+ /// Swaps two elements of this list.
+ void swap(int index1, int index2) {
+ RangeError.checkValidIndex(index1, this, 'index1');
+ RangeError.checkValidIndex(index2, this, 'index2');
+ var tmp = this[index1];
+ this[index1] = this[index2];
+ this[index2] = tmp;
+ }
+
+ /// A fixed length view of a range of this list.
+ ///
+ /// The view is backed by this this list, which must not
+ /// change its length while the view is being used.
+ ///
+ /// The view can be used to perform specific whole-list
+ /// actions on a part of the list.
+ /// For example, to see if a list contains more than one
+ /// "marker" element, you can do:
+ /// ```dart
+ /// someList.slice(someList.indexOf(marker) + 1).contains(marker)
+ /// ```
+ ListSlice<E> slice(int start, [int? end]) {
+ end = RangeError.checkValidRange(start, end, length);
+ var self = this;
+ if (self is ListSlice) return self.slice(start, end);
+ return ListSlice<E>(this, start, end);
+ }
+
+ /// Whether [other] has the same elements as this list.
+ ///
+ /// Returns true iff [other] has the same [length]
+ /// as this list, and the elemets of this list and [other]
+ /// at the same indices are equal according to [equality],
+ /// which defaults to using `==`.
+ bool equals(List<E> other, [Equality<E> equality = const DefaultEquality()]) {
+ if (length != other.length) return false;
+ for (var i = 0; i < length; i++) {
+ if (!equality.equals(this[i], other[i])) return false;
+ }
+ return true;
+ }
+}
+
+/// Various extensions on lists of comparable elements.
+extension ListComparableExtensions<E extends Comparable<E>> on List<E> {
+ /// Returns the index of [element] in this sorted list.
+ ///
+ /// Uses binary search to find the location of [element].
+ /// The list *must* be sorted according to [compare],
+ /// otherwise the result is unspecified.
+ /// If [compare] is omitted, it uses the natural order of the elements.
+ ///
+ /// Returns -1 if [element] does not occur in this list.
+ int binarySearch(E element, [int Function(E, E)? compare]) =>
+ algorithms.binarySearchBy<E, E>(
+ this, identity, compare ?? compareComparable, element);
+
+ /// Returns the index where [element] should be in this sorted list.
+ ///
+ /// Uses binary search to find the location of where [element] should be.
+ /// The list *must* be sorted according to [compare],
+ /// otherwise the result is unspecified.
+ /// If [compare] is omitted, it uses the natural order of the elements.
+ ///
+ /// If [element] does not occur in this list, the returned index is
+ /// the first index where inserting [element] would keep the list
+ /// sorted.
+ int lowerBound(E element, [int Function(E, E)? compare]) =>
+ algorithms.lowerBoundBy<E, E>(
+ this, identity, compare ?? compareComparable, element);
+
+ /// Sort a range of elements by [compare].
+ ///
+ /// If [compare] is omitted, the range is sorted according to the
+ /// natural ordering of the elements.
+ void sortRange(int start, int end, [int Function(E a, E b)? compare]) {
+ RangeError.checkValidRange(start, end, length);
+ algorithms.quickSortBy<E, E>(
+ this, identity, compare ?? compareComparable, start, end);
+ }
+}
+
+/// A list view of a range of another list.
+///
+/// Wraps the range of the [source] list from [start] to [end]
+/// and acts like a fixed-length list view of that range.
+/// The source list must not change length while a list slice is being used.
+class ListSlice<E> extends ListBase<E> {
+ /// Original length of [source].
+ ///
+ /// Used to detect modifications to [source] which may invalidate
+ /// the slice.
+ final int _initialSize;
+
+ /// The original list backing this slice.
+ final List<E> source;
+
+ /// The start index of the slice.
+ final int start;
+
+ @override
+ final int length;
+
+ /// Creates a slice of [source] from [start] to [end].
+ ListSlice(this.source, this.start, int end)
+ : length = end - start,
+ _initialSize = source.length {
+ RangeError.checkValidRange(start, end, source.length);
+ }
+
+ // No argument checking, for internal use.
+ ListSlice._(this._initialSize, this.source, this.start, this.length);
+
+ /// The end index of the slice.
+ int get end => start + length;
+
+ @override
+ E operator [](int index) {
+ if (source.length != _initialSize) {
+ throw ConcurrentModificationError(source);
+ }
+ RangeError.checkValidIndex(index, this, null, length);
+ return source[start + index];
+ }
+
+ @override
+ void operator []=(int index, E value) {
+ if (source.length != _initialSize) {
+ throw ConcurrentModificationError(source);
+ }
+ RangeError.checkValidIndex(index, this, null, length);
+ source[start + index] = value;
+ }
+
+ @override
+ void setRange(int start, int end, Iterable<E> iterable, [int skipCount = 0]) {
+ if (source.length != _initialSize) {
+ throw ConcurrentModificationError(source);
+ }
+ RangeError.checkValidRange(start, end, length);
+ source.setRange(start + start, start + end, iterable, skipCount);
+ }
+
+ /// A fixed length view of a range of this list.
+ ///
+ /// The view is backed by this this list, which must not
+ /// change its length while the view is being used.
+ ///
+ /// The view can be used to perform specific whole-list
+ /// actions on a part of the list.
+ /// For example, to see if a list contains more than one
+ /// "marker" element, you can do:
+ /// ```dart
+ /// someList.slice(someList.indexOf(marker) + 1).contains(marker)
+ /// ```
+ ListSlice<E> slice(int start, [int? end]) {
+ end = RangeError.checkValidRange(start, end, length);
+ return ListSlice._(_initialSize, source, start + start, end - start);
+ }
+
+ @override
+ void shuffle([Random? random]) {
+ if (source.length != _initialSize) {
+ throw ConcurrentModificationError(source);
+ }
+ algorithms.shuffle(source, start, end, random);
+ }
+
+ @override
+ void sort([int Function(E a, E b)? compare]) {
+ if (source.length != _initialSize) {
+ throw ConcurrentModificationError(source);
+ }
+ compare ??= defaultCompare;
+ quickSort(source, compare, start, start + length);
+ }
+
+ /// Sort a range of elements by [compare].
+ void sortRange(int start, int end, int Function(E a, E b) compare) {
+ if (source.length != _initialSize) {
+ throw ConcurrentModificationError(source);
+ }
+ source.sortRange(start, end, compare);
+ }
+
+ /// Shuffles a range of elements.
+ ///
+ /// If [random] is omitted, a new instance of [Random] is used.
+ void shuffleRange(int start, int end, [Random? random]) {
+ if (source.length != _initialSize) {
+ throw ConcurrentModificationError(source);
+ }
+ RangeError.checkValidRange(start, end, length);
+ algorithms.shuffle(source, this.start + start, this.start + end, random);
+ }
+
+ /// Reverses a range of elements.
+ void reverseRange(int start, int end) {
+ RangeError.checkValidRange(start, end, length);
+ source.reverseRange(this.start + start, this.start + end);
+ }
+
+ // Act like a fixed-length list.
+
+ @override
+ set length(int newLength) {
+ throw UnsupportedError('Cannot change the length of a fixed-length list');
+ }
+
+ @override
+ void add(E element) {
+ throw UnsupportedError('Cannot add to a fixed-length list');
+ }
+
+ @override
+ void insert(int index, E element) {
+ throw UnsupportedError('Cannot add to a fixed-length list');
+ }
+
+ @override
+ void insertAll(int index, Iterable<E> iterable) {
+ throw UnsupportedError('Cannot add to a fixed-length list');
+ }
+
+ @override
+ void addAll(Iterable<E> iterable) {
+ throw UnsupportedError('Cannot add to a fixed-length list');
+ }
+
+ @override
+ bool remove(Object? element) {
+ throw UnsupportedError('Cannot remove from a fixed-length list');
+ }
+
+ @override
+ void removeWhere(bool Function(E element) test) {
+ throw UnsupportedError('Cannot remove from a fixed-length list');
+ }
+
+ @override
+ void retainWhere(bool Function(E element) test) {
+ throw UnsupportedError('Cannot remove from a fixed-length list');
+ }
+
+ @override
+ void clear() {
+ throw UnsupportedError('Cannot clear a fixed-length list');
+ }
+
+ @override
+ E removeAt(int index) {
+ throw UnsupportedError('Cannot remove from a fixed-length list');
+ }
+
+ @override
+ E removeLast() {
+ throw UnsupportedError('Cannot remove from a fixed-length list');
+ }
+
+ @override
+ void removeRange(int start, int end) {
+ throw UnsupportedError('Cannot remove from a fixed-length list');
+ }
+
+ @override
+ void replaceRange(int start, int end, Iterable<E> newContents) {
+ throw UnsupportedError('Cannot remove from a fixed-length list');
+ }
+}
diff --git a/lib/src/priority_queue.dart b/lib/src/priority_queue.dart
index 6952a81..345d6f7 100644
--- a/lib/src/priority_queue.dart
+++ b/lib/src/priority_queue.dart
@@ -202,7 +202,7 @@
/// is the case, `E` must implement [Comparable], and this is checked at
/// runtime for every comparison.
HeapPriorityQueue([int Function(E, E)? comparison])
- : comparison = comparison ?? defaultCompare<E>();
+ : comparison = comparison ?? defaultCompare;
E _elementAt(int index) => _queue[index] ?? (null as E);
diff --git a/lib/src/utils.dart b/lib/src/utils.dart
index 00ea932..64088f0 100644
--- a/lib/src/utils.dart
+++ b/lib/src/utils.dart
@@ -2,6 +2,19 @@
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
-/// Returns a [Comparator] that asserts that its first argument is comparable.
-Comparator<T> defaultCompare<T>() =>
- (value1, value2) => (value1 as Comparable).compareTo(value2);
+/// A [Comparator] that asserts that its first argument is comparable.
+///
+/// The function behaves just like [List.sort]'s
+/// default comparison function. It is entirely dynamic in its testing.
+///
+/// Should be used when optimistically comparing object that are assumed
+/// to be comparable.
+/// If the elements are known to be comparable, use [compareComparable].
+int defaultCompare(Object? value1, Object? value2) =>
+ (value1 as Comparable<Object?>).compareTo(value2);
+
+/// A reusable identity function at any type.
+T identity<T>(T value) => value;
+
+/// A reusable typed comparable comparator.
+int compareComparable<T extends Comparable<T>>(T a, T b) => a.compareTo(b);
diff --git a/pubspec.yaml b/pubspec.yaml
index e256638..b94841d 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -8,7 +8,7 @@
sdk: '>=2.10.0-78 <2.11.0'
dev_dependencies:
- pedantic: ^1.0.0
+ pedantic: ^1.9.0
test: ^1.0.0
dependency_overrides:
diff --git a/test/algorithms_test.dart b/test/algorithms_test.dart
index 7ab096f..0c60463 100644
--- a/test/algorithms_test.dart
+++ b/test/algorithms_test.dart
@@ -6,6 +6,7 @@
import 'dart:math';
import 'package:collection/collection.dart';
+import 'package:collection/src/algorithms.dart';
import 'package:test/test.dart';
void main() {
@@ -154,58 +155,159 @@
expect(lowerBound(l2, C(5), compare: compareC), equals(1));
});
- test('insertionSortRandom', () {
- var random = Random();
- for (var i = 0; i < 25; i++) {
- var list = [
- for (var j = 0; j < i; j++)
- random.nextInt(25) // Expect some equal elements.
- ];
- insertionSort(list);
- for (var j = 1; j < i; j++) {
- expect(list[j - 1], lessThanOrEqualTo(list[j]));
+ void testSort(String name,
+ void Function(List<int> elements, [int? start, int? end]) sort) {
+ test('${name}Random', () {
+ var random = Random();
+ for (var i = 0; i < 250; i += 10) {
+ var list = [
+ for (var j = 0; j < i; j++)
+ random.nextInt(25) // Expect some equal elements.
+ ];
+ sort(list);
+ for (var j = 1; j < i; j++) {
+ expect(list[j - 1], lessThanOrEqualTo(list[j]));
+ }
}
- }
+ });
+
+ test('${name}SubRanges', () {
+ var l = [6, 5, 4, 3, 2, 1];
+ sort(l, 2, 4);
+ expect(l, equals([6, 5, 3, 4, 2, 1]));
+ sort(l, 1, 1);
+ expect(l, equals([6, 5, 3, 4, 2, 1]));
+ sort(l, 4, 6);
+ expect(l, equals([6, 5, 3, 4, 1, 2]));
+ sort(l, 0, 2);
+ expect(l, equals([5, 6, 3, 4, 1, 2]));
+ sort(l, 0, 6);
+ expect(l, equals([1, 2, 3, 4, 5, 6]));
+ });
+
+ test('$name insertionSortSpecialCases', () {
+ var l = [6, 6, 6, 6, 6, 6];
+ sort(l);
+ expect(l, equals([6, 6, 6, 6, 6, 6]));
+
+ l = [6, 6, 3, 3, 0, 0];
+ sort(l);
+ expect(l, equals([0, 0, 3, 3, 6, 6]));
+ });
+ }
+
+ int intId(int x) => x;
+ int intCompare(int a, int b) => a - b;
+ testSort('insertionSort', (list, [start, end]) {
+ insertionSortBy(list, intId, intCompare, start ?? 0, end ?? list.length);
});
-
- test('insertionSortSubRanges', () {
- var l = [6, 5, 4, 3, 2, 1];
- insertionSort(l, start: 2, end: 4);
- expect(l, equals([6, 5, 3, 4, 2, 1]));
- insertionSort(l, start: 1, end: 1);
- expect(l, equals([6, 5, 3, 4, 2, 1]));
- insertionSort(l, start: 4, end: 6);
- expect(l, equals([6, 5, 3, 4, 1, 2]));
- insertionSort(l, start: 0, end: 2);
- expect(l, equals([5, 6, 3, 4, 1, 2]));
- insertionSort(l, start: 0, end: 6);
- expect(l, equals([1, 2, 3, 4, 5, 6]));
+ testSort('mergeSort compare', (list, [start, end]) {
+ mergeSort(list,
+ start: start ?? 0, end: end ?? list.length, compare: intCompare);
});
-
- test('insertionSortSpecialCases', () {
- var l = [6, 6, 6, 6, 6, 6];
- insertionSort(l);
- expect(l, equals([6, 6, 6, 6, 6, 6]));
-
- l = [6, 6, 3, 3, 0, 0];
- insertionSort(l);
- expect(l, equals([0, 0, 3, 3, 6, 6]));
+ testSort('mergeSort comparable', (list, [start, end]) {
+ mergeSort(list, start: start ?? 0, end: end ?? list.length);
});
-
- test('MergeSortRandom', () {
- var random = Random();
- for (var i = 0; i < 250; i += 1) {
- var list = [
- for (var j = 0; j < i; j++)
- random.nextInt(i) // Expect some equal elements.
- ];
+ testSort('mergeSortBy', (list, [start, end]) {
+ mergeSortBy(list, intId, intCompare, start ?? 0, end ?? list.length);
+ });
+ testSort('quickSort', (list, [start, end]) {
+ quickSort(list, intCompare, start ?? 0, end ?? list.length);
+ });
+ testSort('quickSortBy', (list, [start, end]) {
+ quickSortBy(list, intId, intCompare, start ?? 0, end ?? list.length);
+ });
+ test('MergeSortSpecialCases', () {
+ for (var size in [511, 512, 513]) {
+ // All equal.
+ var list = List<OC>.generate(size, (i) => OC(0, i));
mergeSort(list);
- for (var j = 1; j < i; j++) {
- expect(list[j - 1], lessThanOrEqualTo(list[j]));
+ for (var i = 0; i < size; i++) {
+ expect(list[i].order, equals(i));
+ }
+ // All but one equal, first.
+ list[0] = OC(1, 0);
+ for (var i = 1; i < size; i++) {
+ list[i] = OC(0, i);
+ }
+ mergeSort(list);
+ for (var 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 (var i = 0; i < size - 1; i++) {
+ list[i] = OC(0, i);
+ }
+ list[size - 1] = OC(-1, size - 1);
+ mergeSort(list);
+ expect(list[0].order, equals(size - 1));
+ for (var i = 1; i < size; i++) {
+ expect(list[i].order, equals(i - 1));
+ }
+
+ // Reversed.
+ for (var i = 0; i < size; i++) {
+ list[i] = OC(size - 1 - i, i);
+ }
+ mergeSort(list);
+ for (var i = 0; i < size; i++) {
+ expect(list[i].id, equals(i));
+ expect(list[i].order, equals(size - 1 - i));
}
}
});
+ void testSortBy(
+ String name,
+ void Function<T, K>(List<T> elements, K Function(T element) keyOf,
+ int Function(K a, K b) compare,
+ [int start, int end])
+ sort) {
+ for (var n in [0, 1, 2, 10, 75, 250]) {
+ var name2 = name;
+ test('$name2: Same #$n', () {
+ var list = List<OC>.generate(n, (i) => OC(i, 0));
+ // Should succeed. Bad implementations of, e.g., quicksort can diverge.
+ sort(list, ocOrder, compareInt);
+ });
+ test('$name: Pre-sorted #$n', () {
+ var list = List<OC>.generate(n, (i) => OC(-i, i));
+ var expected = list.toList();
+ sort(list, ocOrder, compareInt);
+ // Elements have not moved.
+ expect(list, expected);
+ });
+ test('$name: Reverse-sorted #$n', () {
+ var list = List<OC>.generate(n, (i) => OC(i, -i));
+ sort(list, ocOrder, compareInt);
+ expectSorted(list, ocOrder, compareInt);
+ });
+ test('$name: Random #$n', () {
+ var random = Random();
+ var list = List<OC>.generate(n, (i) => OC(i, random.nextInt(n)));
+ sort(list, ocOrder, compareInt);
+ expectSorted(list, ocOrder, compareInt);
+ });
+ test('$name: Sublist #$n', () {
+ var random = Random();
+ var list = List<OC>.generate(n, (i) => OC(i, random.nextInt(n)));
+ var original = list.toList();
+ var start = n ~/ 4;
+ var end = start * 3;
+ sort(list, ocOrder, compareInt, start, end);
+ expectSorted(list, ocOrder, compareInt, start, end);
+ expect(list.sublist(0, start), original.sublist(0, start));
+ expect(list.sublist(end), original.sublist(end));
+ });
+ }
+ }
+
+ testSortBy('insertionSort', insertionSortBy);
+ testSortBy('mergeSort', mergeSortBy);
+ testSortBy('quickSortBy', quickSortBy);
+
test('MergeSortPreservesOrder', () {
var random = Random();
// Small case where only insertion call is called,
@@ -251,48 +353,6 @@
}
});
- test('MergeSortSpecialCases', () {
- for (var size in [511, 512, 513]) {
- // All equal.
- var list = [for (var i = 0; i < size; i++) OC(0, i)];
- mergeSort(list);
- for (var i = 0; i < size; i++) {
- expect(list[i].order, equals(i));
- }
- // All but one equal, first.
- list[0] = OC(1, 0);
- for (var i = 1; i < size; i++) {
- list[i] = OC(0, i);
- }
- mergeSort(list);
- for (var 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 (var i = 0; i < size - 1; i++) {
- list[i] = OC(0, i);
- }
- list[size - 1] = OC(-1, size - 1);
- mergeSort(list);
- expect(list[0].order, equals(size - 1));
- for (var i = 1; i < size; i++) {
- expect(list[i].order, equals(i - 1));
- }
-
- // Reversed.
- for (var i = 0; i < size; i++) {
- list[i] = OC(size - 1 - i, i);
- }
- mergeSort(list);
- for (var i = 0; i < size; i++) {
- expect(list[i].id, equals(i));
- expect(list[i].order, equals(size - 1 - i));
- }
- }
- });
-
test('Reverse', () {
var l = [6, 5, 4, 3, 2, 1];
reverse(l, 2, 4);
@@ -314,13 +374,36 @@
}
int compareC(C one, C other) => one.id - other.id;
+int cId(C c) => c.id;
+/// Class naturally ordered by its first constructor argument.
class OC implements Comparable<OC> {
final int id;
final int order;
OC(this.id, this.order);
+
@override
int compareTo(OC other) => id - other.id;
+
@override
String toString() => 'OC[$id,$order]';
}
+
+int ocId(OC oc) => oc.id;
+int ocOrder(OC oc) => oc.order;
+
+int compareInt(int a, int b) => a - b;
+
+/// Check that a list is sorted according to [compare] of [keyOf] of elements.
+void expectSorted<T, K>(
+ List<T> list, K Function(T element) keyOf, int Function(K a, K b) compare,
+ [int start = 0, int? end]) {
+ end ??= list.length;
+ if (start == end) return;
+ var prev = keyOf(list[start]);
+ for (var i = start + 1; i < end; i++) {
+ var next = keyOf(list[i]);
+ expect(compare(prev, next), isNonPositive);
+ prev = next;
+ }
+}
diff --git a/test/extensions_test.dart b/test/extensions_test.dart
new file mode 100644
index 0000000..3289757
--- /dev/null
+++ b/test/extensions_test.dart
@@ -0,0 +1,1659 @@
+// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import 'dart:math' show pow;
+
+import 'package:test/test.dart';
+
+import 'package:collection/collection.dart';
+
+void main() {
+ group('Iterable', () {
+ group('of any', () {
+ group('.whereNot', () {
+ test('empty', () {
+ expect(iterable([]).whereNot(unreachable), isEmpty);
+ });
+ test('none', () {
+ expect(iterable([1, 3, 5]).whereNot((e) => e.isOdd), isEmpty);
+ });
+ test('all', () {
+ expect(iterable([1, 3, 5]).whereNot((e) => e.isEven),
+ iterable([1, 3, 5]));
+ });
+ test('some', () {
+ expect(iterable([1, 2, 3, 4]).whereNot((e) => e.isEven),
+ iterable([1, 3]));
+ });
+ });
+ group('.sorted', () {
+ test('empty', () {
+ expect(iterable(<int>[]).sorted(unreachable), []);
+ });
+ test('singleton', () {
+ expect(iterable([1]).sorted(unreachable), [1]);
+ });
+ test('multiple', () {
+ expect(iterable([5, 2, 4, 3, 1]).sorted(cmpInt), [1, 2, 3, 4, 5]);
+ });
+ });
+ group('.sortedBy', () {
+ test('empty', () {
+ expect(iterable(<int>[]).sortedBy(unreachable), []);
+ });
+ test('singleton', () {
+ expect(iterable(<int>[1]).sortedBy(unreachable), [1]);
+ });
+ test('multiple', () {
+ expect(iterable(<int>[3, 20, 100]).sortedBy(toString), [100, 20, 3]);
+ });
+ });
+ group('.sortedByCompare', () {
+ test('empty', () {
+ expect(
+ iterable(<int>[]).sortedByCompare(unreachable, unreachable), []);
+ });
+ test('singleton', () {
+ expect(iterable(<int>[2]).sortedByCompare(unreachable, unreachable),
+ [2]);
+ });
+ test('multiple', () {
+ expect(
+ iterable(<int>[30, 2, 100])
+ .sortedByCompare(toString, cmpParseInverse),
+ [100, 30, 2]);
+ });
+ });
+ group('isSorted', () {
+ test('empty', () {
+ expect(iterable(<int>[]).isSorted(unreachable), true);
+ });
+ test('single', () {
+ expect(iterable([1]).isSorted(unreachable), true);
+ });
+ test('same', () {
+ expect(iterable([1, 1, 1, 1]).isSorted(cmpInt), true);
+ expect(iterable([1, 0, 1, 0]).isSorted(cmpMod(2)), true);
+ });
+ test('multiple', () {
+ expect(iterable([1, 2, 3, 4]).isSorted(cmpInt), true);
+ expect(iterable([4, 3, 2, 1]).isSorted(cmpIntInverse), true);
+ expect(iterable([1, 2, 3, 0]).isSorted(cmpInt), false);
+ expect(iterable([4, 1, 2, 3]).isSorted(cmpInt), false);
+ expect(iterable([4, 3, 2, 1]).isSorted(cmpInt), false);
+ });
+ });
+ group('.isSortedBy', () {
+ test('empty', () {
+ expect(iterable(<int>[]).isSortedBy(unreachable), true);
+ });
+ test('single', () {
+ expect(iterable([1]).isSortedBy(toString), true);
+ });
+ test('same', () {
+ expect(iterable([1, 1, 1, 1]).isSortedBy(toString), true);
+ });
+ test('multiple', () {
+ expect(iterable([1, 2, 3, 4]).isSortedBy(toString), true);
+ expect(iterable([4, 3, 2, 1]).isSortedBy(toString), false);
+ expect(iterable([1000, 200, 30, 4]).isSortedBy(toString), true);
+ expect(iterable([1, 2, 3, 0]).isSortedBy(toString), false);
+ expect(iterable([4, 1, 2, 3]).isSortedBy(toString), false);
+ expect(iterable([4, 3, 2, 1]).isSortedBy(toString), false);
+ });
+ });
+ group('.isSortedByCompare', () {
+ test('empty', () {
+ expect(iterable(<int>[]).isSortedByCompare(unreachable, unreachable),
+ true);
+ });
+ test('single', () {
+ expect(iterable([1]).isSortedByCompare(toString, unreachable), true);
+ });
+ test('same', () {
+ expect(iterable([1, 1, 1, 1]).isSortedByCompare(toString, cmpParse),
+ true);
+ });
+ test('multiple', () {
+ expect(iterable([1, 2, 3, 4]).isSortedByCompare(toString, cmpParse),
+ true);
+ expect(
+ iterable([4, 3, 2, 1])
+ .isSortedByCompare(toString, cmpParseInverse),
+ true);
+ expect(
+ iterable([1000, 200, 30, 4])
+ .isSortedByCompare(toString, cmpString),
+ true);
+ expect(iterable([1, 2, 3, 0]).isSortedByCompare(toString, cmpParse),
+ false);
+ expect(iterable([4, 1, 2, 3]).isSortedByCompare(toString, cmpParse),
+ false);
+ expect(iterable([4, 3, 2, 1]).isSortedByCompare(toString, cmpParse),
+ false);
+ });
+ });
+ group('.forEachIndexed', () {
+ test('empty', () {
+ iterable([]).forEachIndexed(unreachable);
+ });
+ test('single', () {
+ var log = [];
+ iterable(['a']).forEachIndexed((i, s) {
+ log..add(i)..add(s);
+ });
+ expect(log, [0, 'a']);
+ });
+ test('multiple', () {
+ var log = [];
+ iterable(['a', 'b', 'c']).forEachIndexed((i, s) {
+ log..add(i)..add(s);
+ });
+ expect(log, [0, 'a', 1, 'b', 2, 'c']);
+ });
+ });
+ group('.forEachWhile', () {
+ test('empty', () {
+ iterable([]).forEachWhile(unreachable);
+ });
+ test('single true', () {
+ var log = [];
+ iterable(['a']).forEachWhile((s) {
+ log.add(s);
+ return true;
+ });
+ expect(log, ['a']);
+ });
+ test('single false', () {
+ var log = [];
+ iterable(['a']).forEachWhile((s) {
+ log.add(s);
+ return false;
+ });
+ expect(log, ['a']);
+ });
+ test('multiple one', () {
+ var log = [];
+ iterable(['a', 'b', 'c']).forEachWhile((s) {
+ log.add(s);
+ return false;
+ });
+ expect(log, ['a']);
+ });
+ test('multiple all', () {
+ var log = [];
+ iterable(['a', 'b', 'c']).forEachWhile((s) {
+ log.add(s);
+ return true;
+ });
+ expect(log, ['a', 'b', 'c']);
+ });
+ test('multiple some', () {
+ var log = [];
+ iterable(['a', 'b', 'c']).forEachWhile((s) {
+ log.add(s);
+ return s != 'b';
+ });
+ expect(log, ['a', 'b']);
+ });
+ });
+ group('.forEachIndexedWhile', () {
+ test('empty', () {
+ iterable([]).forEachIndexedWhile(unreachable);
+ });
+ test('single true', () {
+ var log = [];
+ iterable(['a']).forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return true;
+ });
+ expect(log, [0, 'a']);
+ });
+ test('single false', () {
+ var log = [];
+ iterable(['a']).forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return false;
+ });
+ expect(log, [0, 'a']);
+ });
+ test('multiple one', () {
+ var log = [];
+ iterable(['a', 'b', 'c']).forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return false;
+ });
+ expect(log, [0, 'a']);
+ });
+ test('multiple all', () {
+ var log = [];
+ iterable(['a', 'b', 'c']).forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return true;
+ });
+ expect(log, [0, 'a', 1, 'b', 2, 'c']);
+ });
+ test('multiple some', () {
+ var log = [];
+ iterable(['a', 'b', 'c']).forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return s != 'b';
+ });
+ expect(log, [0, 'a', 1, 'b']);
+ });
+ });
+ group('.mapIndexed', () {
+ test('empty', () {
+ expect(iterable(<String>[]).mapIndexed(unreachable), isEmpty);
+ });
+ test('multiple', () {
+ expect(iterable(<String>['a', 'b']).mapIndexed((i, s) => [i, s]), [
+ [0, 'a'],
+ [1, 'b']
+ ]);
+ });
+ });
+ group('.whereIndexed', () {
+ test('empty', () {
+ expect(iterable(<String>[]).whereIndexed(unreachable), isEmpty);
+ });
+ test('none', () {
+ var trace = [];
+ int log(int a, int b) {
+ trace..add(a)..add(b);
+ return b;
+ }
+
+ expect(
+ iterable(<int>[1, 3, 5, 7])
+ .whereIndexed((i, x) => log(i, x).isEven),
+ isEmpty);
+ expect(trace, [0, 1, 1, 3, 2, 5, 3, 7]);
+ });
+ test('all', () {
+ expect(iterable(<int>[1, 3, 5, 7]).whereIndexed((i, x) => x.isOdd),
+ [1, 3, 5, 7]);
+ });
+ test('some', () {
+ expect(iterable(<int>[1, 3, 5, 7]).whereIndexed((i, x) => i.isOdd),
+ [3, 7]);
+ });
+ });
+ group('.whereNotIndexed', () {
+ test('empty', () {
+ expect(iterable(<int>[]).whereNotIndexed(unreachable), isEmpty);
+ });
+ test('none', () {
+ var trace = [];
+ int log(int a, int b) {
+ trace..add(a)..add(b);
+ return b;
+ }
+
+ expect(
+ iterable(<int>[1, 3, 5, 7])
+ .whereNotIndexed((i, x) => log(i, x).isOdd),
+ isEmpty);
+ expect(trace, [0, 1, 1, 3, 2, 5, 3, 7]);
+ });
+ test('all', () {
+ expect(
+ iterable(<int>[1, 3, 5, 7]).whereNotIndexed((i, x) => x.isEven),
+ [1, 3, 5, 7]);
+ });
+ test('some', () {
+ expect(iterable(<int>[1, 3, 5, 7]).whereNotIndexed((i, x) => i.isOdd),
+ [1, 5]);
+ });
+ });
+ group('.expandIndexed', () {
+ test('empty', () {
+ expect(iterable(<int>[]).expandIndexed(unreachable), isEmpty);
+ });
+ test('empty result', () {
+ expect(iterable(['a', 'b']).expandIndexed((i, v) => []), isEmpty);
+ });
+ test('larger result', () {
+ expect(iterable(['a', 'b']).expandIndexed((i, v) => ['$i', v]),
+ ['0', 'a', '1', 'b']);
+ });
+ test('varying result', () {
+ expect(
+ iterable(['a', 'b'])
+ .expandIndexed((i, v) => i.isOdd ? ['$i', v] : []),
+ ['1', 'b']);
+ });
+ });
+ group('.reduceIndexed', () {
+ test('empty', () {
+ expect(() => iterable([]).reduceIndexed((i, a, b) => a),
+ throwsStateError);
+ });
+ test('single', () {
+ expect(iterable([1]).reduceIndexed(unreachable), 1);
+ });
+ test('multiple', () {
+ expect(
+ iterable([1, 4, 2])
+ .reduceIndexed((i, p, v) => p + (pow(i + 1, v) as int)),
+ 1 + 16 + 9);
+ });
+ });
+ group('.foldIndexed', () {
+ test('empty', () {
+ expect(iterable([]).foldIndexed(0, unreachable), 0);
+ });
+ test('single', () {
+ expect(
+ iterable([1]).foldIndexed('x', (i, a, b) => '$a:$i:$b'), 'x:0:1');
+ });
+ test('mulitple', () {
+ expect(iterable([1, 3, 9]).foldIndexed('x', (i, a, b) => '$a:$i:$b'),
+ 'x:0:1:1:3:2:9');
+ });
+ });
+ group('.firstWhereOrNull', () {
+ test('empty', () {
+ expect(iterable([]).firstWhereOrNull(unreachable), null);
+ });
+ test('none', () {
+ expect(iterable([1, 3, 7]).firstWhereOrNull(isEven), null);
+ });
+ test('single', () {
+ expect(iterable([0, 1, 2]).firstWhereOrNull(isOdd), 1);
+ });
+ test('first of multiple', () {
+ expect(iterable([0, 1, 3]).firstWhereOrNull(isOdd), 1);
+ });
+ });
+ group('.firstWhereIndexedOrNull', () {
+ test('empty', () {
+ expect(iterable([]).firstWhereIndexedOrNull(unreachable), null);
+ });
+ test('none', () {
+ expect(
+ iterable([1, 3, 7]).firstWhereIndexedOrNull((i, x) => x.isEven),
+ null);
+ expect(iterable([1, 3, 7]).firstWhereIndexedOrNull((i, x) => i < 0),
+ null);
+ });
+ test('single', () {
+ expect(iterable([0, 3, 6]).firstWhereIndexedOrNull((i, x) => x.isOdd),
+ 3);
+ expect(
+ iterable([0, 3, 6]).firstWhereIndexedOrNull((i, x) => i == 1), 3);
+ });
+ test('first of multiple', () {
+ expect(iterable([0, 3, 7]).firstWhereIndexedOrNull((i, x) => x.isOdd),
+ 3);
+ expect(
+ iterable([0, 3, 7]).firstWhereIndexedOrNull((i, x) => i.isEven),
+ 0);
+ });
+ });
+ group('.firstOrNull', () {
+ test('empty', () {
+ expect(iterable([]).firstOrNull, null);
+ });
+ test('single', () {
+ expect(iterable([1]).firstOrNull, 1);
+ });
+ test('first of multiple', () {
+ expect(iterable([1, 3, 5]).firstOrNull, 1);
+ });
+ });
+ group('.lastWhereOrNull', () {
+ test('empty', () {
+ expect(iterable([]).lastWhereOrNull(unreachable), null);
+ });
+ test('none', () {
+ expect(iterable([1, 3, 7]).lastWhereOrNull(isEven), null);
+ });
+ test('single', () {
+ expect(iterable([0, 1, 2]).lastWhereOrNull(isOdd), 1);
+ });
+ test('last of multiple', () {
+ expect(iterable([0, 1, 3]).lastWhereOrNull(isOdd), 3);
+ });
+ });
+ group('.lastWhereIndexedOrNull', () {
+ test('empty', () {
+ expect(iterable([]).lastWhereIndexedOrNull(unreachable), null);
+ });
+ test('none', () {
+ expect(iterable([1, 3, 7]).lastWhereIndexedOrNull((i, x) => x.isEven),
+ null);
+ expect(iterable([1, 3, 7]).lastWhereIndexedOrNull((i, x) => i < 0),
+ null);
+ });
+ test('single', () {
+ expect(
+ iterable([0, 3, 6]).lastWhereIndexedOrNull((i, x) => x.isOdd), 3);
+ expect(
+ iterable([0, 3, 6]).lastWhereIndexedOrNull((i, x) => i == 1), 3);
+ });
+ test('last of multiple', () {
+ expect(
+ iterable([0, 3, 7]).lastWhereIndexedOrNull((i, x) => x.isOdd), 7);
+ expect(iterable([0, 3, 7]).lastWhereIndexedOrNull((i, x) => i.isEven),
+ 7);
+ });
+ });
+ group('.lastOrNull', () {
+ test('empty', () {
+ expect(iterable([]).lastOrNull, null);
+ });
+ test('single', () {
+ expect(iterable([1]).lastOrNull, 1);
+ });
+ test('last of multiple', () {
+ expect(iterable([1, 3, 5]).lastOrNull, 5);
+ });
+ });
+ group('.singleWhereOrNull', () {
+ test('empty', () {
+ expect(iterable([]).singleWhereOrNull(unreachable), null);
+ });
+ test('none', () {
+ expect(iterable([1, 3, 7]).singleWhereOrNull(isEven), null);
+ });
+ test('single', () {
+ expect(iterable([0, 1, 2]).singleWhereOrNull(isOdd), 1);
+ });
+ test('multiple', () {
+ expect(iterable([0, 1, 3]).singleWhereOrNull(isOdd), null);
+ });
+ });
+ group('.singleWhereIndexedOrNull', () {
+ test('empty', () {
+ expect(iterable([]).singleWhereIndexedOrNull(unreachable), null);
+ });
+ test('none', () {
+ expect(
+ iterable([1, 3, 7]).singleWhereIndexedOrNull((i, x) => x.isEven),
+ null);
+ expect(iterable([1, 3, 7]).singleWhereIndexedOrNull((i, x) => i < 0),
+ null);
+ });
+ test('single', () {
+ expect(
+ iterable([0, 3, 6]).singleWhereIndexedOrNull((i, x) => x.isOdd),
+ 3);
+ expect(iterable([0, 3, 6]).singleWhereIndexedOrNull((i, x) => i == 1),
+ 3);
+ });
+ test('multiple', () {
+ expect(
+ iterable([0, 3, 7]).singleWhereIndexedOrNull((i, x) => x.isOdd),
+ null);
+ expect(
+ iterable([0, 3, 7]).singleWhereIndexedOrNull((i, x) => i.isEven),
+ null);
+ });
+ });
+ group('.singleOrNull', () {
+ test('empty', () {
+ expect(iterable([]).singleOrNull, null);
+ });
+ test('single', () {
+ expect(iterable([1]).singleOrNull, 1);
+ });
+ test('multiple', () {
+ expect(iterable([1, 3, 5]).singleOrNull, null);
+ });
+ });
+ group('.groupFoldBy', () {
+ test('empty', () {
+ expect(iterable([]).groupFoldBy(unreachable, unreachable), {});
+ });
+ test('single', () {
+ expect(iterable([1]).groupFoldBy(toString, (p, v) => [p, v]), {
+ '1': [null, 1]
+ });
+ });
+ test('multiple', () {
+ expect(
+ iterable([1, 2, 3, 4, 5]).groupFoldBy<bool, String>(
+ (x) => x.isEven, (p, v) => p == null ? '$v' : '$p:$v'),
+ {true: '2:4', false: '1:3:5'});
+ });
+ });
+ group('.groupSetsBy', () {
+ test('empty', () {
+ expect(iterable([]).groupSetsBy(unreachable), {});
+ });
+ test('multiple same', () {
+ expect(iterable([1, 1]).groupSetsBy(toString), {
+ '1': {1}
+ });
+ });
+ test('multiple', () {
+ expect(iterable([1, 2, 3, 4, 5, 1]).groupSetsBy((x) => x % 3), {
+ 1: {1, 4},
+ 2: {2, 5},
+ 0: {3}
+ });
+ });
+ });
+ group('.groupListsBy', () {
+ test('empty', () {
+ expect(iterable([]).groupListsBy(unreachable), {});
+ });
+ test('multiple saame', () {
+ expect(iterable([1, 1]).groupListsBy(toString), {
+ '1': [1, 1]
+ });
+ });
+ test('multiple', () {
+ expect(iterable([1, 2, 3, 4, 5, 1]).groupListsBy((x) => x % 3), {
+ 1: [1, 4, 1],
+ 2: [2, 5],
+ 0: [3]
+ });
+ });
+ });
+ group('.splitBefore', () {
+ test('empty', () {
+ expect(iterable([]).splitBefore(unreachable), []);
+ });
+ test('single', () {
+ expect(iterable([1]).splitBefore(unreachable), [
+ [1]
+ ]);
+ });
+ test('no split', () {
+ var trace = [];
+ bool log(x) {
+ trace.add(x);
+ return false;
+ }
+
+ expect(iterable([1, 2, 3]).splitBefore(log), [
+ [1, 2, 3]
+ ]);
+ expect(trace, [2, 3]);
+ });
+ test('all splits', () {
+ expect(iterable([1, 2, 3]).splitBefore((x) => true), [
+ [1],
+ [2],
+ [3]
+ ]);
+ });
+ test('some splits', () {
+ expect(iterable([1, 2, 3]).splitBefore((x) => x.isEven), [
+ [1],
+ [2, 3]
+ ]);
+ });
+ });
+ group('.splitBeforeIndexed', () {
+ test('empty', () {
+ expect(iterable([]).splitBeforeIndexed(unreachable), []);
+ });
+ test('single', () {
+ expect(iterable([1]).splitBeforeIndexed(unreachable), [
+ [1]
+ ]);
+ });
+ test('no split', () {
+ var trace = [];
+ bool log(i, x) {
+ trace..add('$i')..add(x);
+ return false;
+ }
+
+ expect(iterable([1, 2, 3]).splitBeforeIndexed(log), [
+ [1, 2, 3]
+ ]);
+ expect(trace, ['1', 2, '2', 3]);
+ });
+ test('all splits', () {
+ expect(iterable([1, 2, 3]).splitBeforeIndexed((i, x) => true), [
+ [1],
+ [2],
+ [3]
+ ]);
+ });
+ test('some splits', () {
+ expect(iterable([1, 2, 3]).splitBeforeIndexed((i, x) => x.isEven), [
+ [1],
+ [2, 3]
+ ]);
+ expect(iterable([1, 2, 3]).splitBeforeIndexed((i, x) => i.isEven), [
+ [1, 2],
+ [3]
+ ]);
+ });
+ });
+ group('.splitAfter', () {
+ test('empty', () {
+ expect(iterable([]).splitAfter(unreachable), []);
+ });
+ test('single', () {
+ expect(iterable([1]).splitAfter((x) => false), [
+ [1]
+ ]);
+ expect(iterable([1]).splitAfter((x) => true), [
+ [1]
+ ]);
+ });
+ test('no split', () {
+ var trace = [];
+ bool log(x) {
+ trace.add(x);
+ return false;
+ }
+
+ expect(iterable([1, 2, 3]).splitAfter(log), [
+ [1, 2, 3]
+ ]);
+ expect(trace, [1, 2, 3]);
+ });
+ test('all splits', () {
+ expect(iterable([1, 2, 3]).splitAfter((x) => true), [
+ [1],
+ [2],
+ [3]
+ ]);
+ });
+ test('some splits', () {
+ expect(iterable([1, 2, 3]).splitAfter((x) => x.isEven), [
+ [1, 2],
+ [3]
+ ]);
+ });
+ });
+ group('.splitAfterIndexed', () {
+ test('empty', () {
+ expect(iterable([]).splitAfterIndexed(unreachable), []);
+ });
+ test('single', () {
+ expect(iterable([1]).splitAfterIndexed((i, x) => true), [
+ [1]
+ ]);
+ expect(iterable([1]).splitAfterIndexed((i, x) => false), [
+ [1]
+ ]);
+ });
+ test('no split', () {
+ var trace = [];
+ bool log(i, x) {
+ trace..add('$i')..add(x);
+ return false;
+ }
+
+ expect(iterable([1, 2, 3]).splitAfterIndexed(log), [
+ [1, 2, 3]
+ ]);
+ expect(trace, ['0', 1, '1', 2, '2', 3]);
+ });
+ test('all splits', () {
+ expect(iterable([1, 2, 3]).splitAfterIndexed((i, x) => true), [
+ [1],
+ [2],
+ [3]
+ ]);
+ });
+ test('some splits', () {
+ expect(iterable([1, 2, 3]).splitAfterIndexed((i, x) => x.isEven), [
+ [1, 2],
+ [3]
+ ]);
+ expect(iterable([1, 2, 3]).splitAfterIndexed((i, x) => i.isEven), [
+ [1],
+ [2, 3]
+ ]);
+ });
+ });
+ group('.splitBetween', () {
+ test('empty', () {
+ expect(iterable([]).splitBetween(unreachable), []);
+ });
+ test('single', () {
+ expect(iterable([1]).splitBetween(unreachable), [
+ [1]
+ ]);
+ });
+ test('no split', () {
+ var trace = [];
+ bool log(x, y) {
+ trace.add([x, y]);
+ return false;
+ }
+
+ expect(iterable([1, 2, 3]).splitBetween(log), [
+ [1, 2, 3]
+ ]);
+ expect(trace, [
+ [1, 2],
+ [2, 3]
+ ]);
+ });
+ test('all splits', () {
+ expect(iterable([1, 2, 3]).splitBetween((x, y) => true), [
+ [1],
+ [2],
+ [3]
+ ]);
+ });
+ test('some splits', () {
+ expect(iterable([1, 2, 4]).splitBetween((x, y) => (x ^ y).isEven), [
+ [1, 2],
+ [4]
+ ]);
+ });
+ });
+ group('.splitBetweenIndexed', () {
+ test('empty', () {
+ expect(iterable([]).splitBetweenIndexed(unreachable), []);
+ });
+ test('single', () {
+ expect(iterable([1]).splitBetweenIndexed(unreachable), [
+ [1]
+ ]);
+ });
+ test('no split', () {
+ var trace = [];
+ bool log(i, x, y) {
+ trace.add([i, x, y]);
+ return false;
+ }
+
+ expect(iterable([1, 2, 3]).splitBetweenIndexed(log), [
+ [1, 2, 3]
+ ]);
+ expect(trace, [
+ [1, 1, 2],
+ [2, 2, 3]
+ ]);
+ });
+ test('all splits', () {
+ expect(iterable([1, 2, 3]).splitBetweenIndexed((i, x, y) => true), [
+ [1],
+ [2],
+ [3]
+ ]);
+ });
+ test('some splits', () {
+ expect(
+ iterable([1, 2, 4])
+ .splitBetweenIndexed((i, x, y) => (x ^ y).isEven),
+ [
+ [1, 2],
+ [4]
+ ]);
+ expect(
+ iterable([1, 2, 4])
+ .splitBetweenIndexed((i, x, y) => (i ^ y).isEven),
+ [
+ [1, 2],
+ [4]
+ ]);
+ });
+ });
+ group('none', () {
+ test('empty', () {
+ expect(iterable([]).none(unreachable), true);
+ });
+ test('single', () {
+ expect(iterable([1]).none(isEven), true);
+ expect(iterable([1]).none(isOdd), false);
+ });
+ test('multiple', () {
+ expect(iterable([1, 3, 5, 7, 9, 11]).none(isEven), true);
+ expect(iterable([1, 3, 5, 7, 9, 10]).none(isEven), false);
+ expect(iterable([0, 3, 5, 7, 9, 11]).none(isEven), false);
+ expect(iterable([0, 2, 4, 6, 8, 10]).none(isEven), false);
+ });
+ });
+ });
+ group('of nullable', () {
+ group('.whereNotNull', () {
+ test('empty', () {
+ expect(iterable(<int?>[]).whereNotNull(), isEmpty);
+ });
+ test('single', () {
+ expect(iterable(<int?>[null]).whereNotNull(), isEmpty);
+ expect(iterable(<int?>[1]).whereNotNull(), [1]);
+ });
+ test('multiple', () {
+ expect(iterable(<int?>[1, 3, 5]).whereNotNull(), [1, 3, 5]);
+ expect(iterable(<int?>[null, null, null]).whereNotNull(), isEmpty);
+ expect(
+ iterable(<int?>[1, null, 3, null, 5]).whereNotNull(), [1, 3, 5]);
+ });
+ });
+ });
+ group('of number', () {
+ group('.sum', () {
+ test('empty', () {
+ expect(iterable(<int>[]).sum, same(0));
+ expect(iterable(<double>[]).sum, same(0.0));
+ expect(iterable(<num>[]).sum, same(0));
+ });
+ test('single', () {
+ expect(iterable(<int>[1]).sum, same(1));
+ expect(iterable(<double>[1.2]).sum, same(1.2));
+ expect(iterable(<num>[1]).sum, same(1));
+ expect(iterable(<num>[1.2]).sum, same(1.2));
+ });
+ test('multiple', () {
+ expect(iterable(<int>[1, 2, 4]).sum, 7);
+ expect(iterable(<double>[1.2, 3.5]).sum, 4.7);
+ expect(iterable(<num>[1, 3, 5]).sum, same(9));
+ expect(iterable(<num>[1.2, 3.5]).sum, 4.7);
+ expect(iterable(<num>[1.2, 2, 3.5]).sum, 6.7);
+ });
+ });
+ group('average', () {
+ test('empty', () {
+ expect(() => iterable(<int>[]).average, throwsStateError);
+ expect(() => iterable(<double>[]).average, throwsStateError);
+ expect(() => iterable(<num>[]).average, throwsStateError);
+ });
+ test('single', () {
+ expect(iterable(<int>[4]).average, same(4.0));
+ expect(iterable(<double>[3.5]).average, 3.5);
+ expect(iterable(<num>[4]).average, same(4.0));
+ expect(iterable(<num>[3.5]).average, 3.5);
+ });
+ test('multiple', () {
+ expect(iterable(<int>[1, 3, 5]).average, same(3.0));
+ expect(iterable(<int>[1, 3, 5, 9]).average, 4.5);
+ expect(iterable(<double>[1.0, 3.0, 5.0, 9.0]).average, 4.5);
+ expect(iterable(<num>[1, 3, 5, 9]).average, 4.5);
+ });
+ });
+ });
+ group('of iterable', () {
+ group('.flattened', () {
+ var empty = iterable(<int>[]);
+ test('empty', () {
+ expect(iterable(<Iterable<int>>[]).flattened, []);
+ });
+ test('multiple empty', () {
+ expect(iterable([empty, empty, empty]).flattened, []);
+ });
+ test('single value', () {
+ expect(
+ iterable(<Iterable>[
+ iterable([1])
+ ]).flattened,
+ [1]);
+ });
+ test('multiple', () {
+ expect(
+ iterable(<Iterable>[
+ iterable([1, 2]),
+ empty,
+ iterable([3, 4])
+ ]).flattened,
+ [1, 2, 3, 4]);
+ });
+ });
+ });
+ group('of comparable', () {
+ group('.min', () {
+ test('empty', () {
+ expect(() => iterable(<String>[]).min, throwsStateError);
+ });
+ test('single', () {
+ expect(iterable(<String>['a']).min, 'a');
+ });
+ test('multiple', () {
+ expect(iterable(<String>['c', 'a', 'b']).min, 'a');
+ });
+ });
+ group('.minOrNull', () {
+ test('empty', () {
+ expect(iterable(<String>[]).minOrNull, null);
+ });
+ test('single', () {
+ expect(iterable(<String>['a']).minOrNull, 'a');
+ });
+ test('multiple', () {
+ expect(iterable(<String>['c', 'a', 'b']).minOrNull, 'a');
+ });
+ });
+ group('.max', () {
+ test('empty', () {
+ expect(() => iterable(<String>[]).max, throwsStateError);
+ });
+ test('single', () {
+ expect(iterable(<String>['a']).max, 'a');
+ });
+ test('multiple', () {
+ expect(iterable(<String>['b', 'c', 'a']).max, 'c');
+ });
+ });
+ group('.maxOrNull', () {
+ test('empty', () {
+ expect(iterable(<String>[]).maxOrNull, null);
+ });
+ test('single', () {
+ expect(iterable(<String>['a']).maxOrNull, 'a');
+ });
+ test('multiple', () {
+ expect(iterable(<String>['b', 'c', 'a']).maxOrNull, 'c');
+ });
+ });
+ });
+ group('.sorted', () {
+ test('empty', () {
+ expect(iterable(<String>[]).sorted(unreachable), []);
+ expect(iterable(<String>[]).sorted(), []);
+ });
+ test('singleton', () {
+ expect(iterable(['a']).sorted(unreachable), ['a']);
+ expect(iterable(['a']).sorted(), ['a']);
+ });
+ test('multiple', () {
+ expect(iterable(<String>['5', '2', '4', '3', '1']).sorted(cmpParse),
+ ['1', '2', '3', '4', '5']);
+ expect(
+ iterable(<String>['5', '2', '4', '3', '1']).sorted(cmpParseInverse),
+ ['5', '4', '3', '2', '1']);
+ expect(iterable(<String>['5', '2', '4', '3', '1']).sorted(),
+ ['1', '2', '3', '4', '5']);
+ // Large enough to trigger quicksort.
+ var i256 = Iterable<int>.generate(256, (i) => i ^ 0x55);
+ var sorted256 = [...i256]..sort();
+ expect(i256.sorted(cmpInt), sorted256);
+ });
+ });
+ group('.isSorted', () {
+ test('empty', () {
+ expect(iterable(<String>[]).isSorted(unreachable), true);
+ expect(iterable(<String>[]).isSorted(), true);
+ });
+ test('single', () {
+ expect(iterable(['1']).isSorted(unreachable), true);
+ expect(iterable(['1']).isSorted(), true);
+ });
+ test('same', () {
+ expect(iterable(['1', '1', '1', '1']).isSorted(cmpParse), true);
+ expect(iterable(['1', '2', '0', '3']).isSorted(cmpStringLength), true);
+ expect(iterable(['1', '1', '1', '1']).isSorted(), true);
+ });
+ test('multiple', () {
+ expect(iterable(['1', '2', '3', '4']).isSorted(cmpParse), true);
+ expect(iterable(['1', '2', '3', '4']).isSorted(), true);
+ expect(iterable(['4', '3', '2', '1']).isSorted(cmpParseInverse), true);
+ expect(iterable(['1', '2', '3', '0']).isSorted(cmpParse), false);
+ expect(iterable(['1', '2', '3', '0']).isSorted(), false);
+ expect(iterable(['4', '1', '2', '3']).isSorted(cmpParse), false);
+ expect(iterable(['4', '1', '2', '3']).isSorted(), false);
+ expect(iterable(['4', '3', '2', '1']).isSorted(cmpParse), false);
+ expect(iterable(['4', '3', '2', '1']).isSorted(), false);
+ });
+ });
+ });
+
+ group('Comparator', () {
+ test('.inverse', () {
+ var cmpStringInv = cmpString.inverse;
+ expect(cmpString('a', 'b'), isNegative);
+ expect(cmpStringInv('a', 'b'), isPositive);
+ expect(cmpString('aa', 'a'), isPositive);
+ expect(cmpStringInv('aa', 'a'), isNegative);
+ expect(cmpString('a', 'a'), isZero);
+ expect(cmpStringInv('a', 'a'), isZero);
+ });
+ test('.compareBy', () {
+ var cmpByLength = cmpInt.compareBy((String s) => s.length);
+ expect(cmpByLength('a', 'b'), 0);
+ expect(cmpByLength('aa', 'b'), isPositive);
+ expect(cmpByLength('b', 'aa'), isNegative);
+ var cmpByInverseLength = cmpIntInverse.compareBy((String s) => s.length);
+ expect(cmpByInverseLength('a', 'b'), 0);
+ expect(cmpByInverseLength('aa', 'b'), isNegative);
+ expect(cmpByInverseLength('b', 'aa'), isPositive);
+ });
+
+ test('.then', () {
+ var cmpLengthFirst = cmpStringLength.then(cmpString);
+ var strings = ['a', 'aa', 'ba', 'ab', 'b', 'aaa'];
+ strings.sort(cmpString);
+ expect(strings, ['a', 'aa', 'aaa', 'ab', 'b', 'ba']);
+ strings.sort(cmpLengthFirst);
+ expect(strings, ['a', 'b', 'aa', 'ab', 'ba', 'aaa']);
+
+ int cmpFirstLetter(String s1, String s2) =>
+ s1.runes.first - s2.runes.first;
+ var cmpLetterLength = cmpFirstLetter.then(cmpStringLength);
+ var cmpLengthLetter = cmpStringLength.then(cmpFirstLetter);
+ strings = ['a', 'ab', 'b', 'ba', 'aaa'];
+ strings.sort(cmpLetterLength);
+ expect(strings, ['a', 'ab', 'aaa', 'b', 'ba']);
+ strings.sort(cmpLengthLetter);
+ expect(strings, ['a', 'b', 'ab', 'ba', 'aaa']);
+ });
+ });
+
+ group('List', () {
+ group('of any', () {
+ group('.binarySearch', () {
+ test('empty', () {
+ expect(<int>[].binarySearch(1, unreachable), -1);
+ });
+ test('single', () {
+ expect([0].binarySearch(1, cmpInt), -1);
+ expect([1].binarySearch(1, cmpInt), 0);
+ expect([2].binarySearch(1, cmpInt), -1);
+ });
+ test('multiple', () {
+ expect([1, 2, 3, 4, 5, 6].binarySearch(3, cmpInt), 2);
+ expect([6, 5, 4, 3, 2, 1].binarySearch(3, cmpIntInverse), 3);
+ });
+ });
+ group('.binarySearchByCompare', () {
+ test('empty', () {
+ expect(<int>[].binarySearchByCompare(1, toString, cmpParse), -1);
+ });
+ test('single', () {
+ expect([0].binarySearchByCompare(1, toString, cmpParse), -1);
+ expect([1].binarySearchByCompare(1, toString, cmpParse), 0);
+ expect([2].binarySearchByCompare(1, toString, cmpParse), -1);
+ });
+ test('multiple', () {
+ expect(
+ [1, 2, 3, 4, 5, 6].binarySearchByCompare(3, toString, cmpParse),
+ 2);
+ expect(
+ [6, 5, 4, 3, 2, 1]
+ .binarySearchByCompare(3, toString, cmpParseInverse),
+ 3);
+ });
+ });
+ group('.binarySearchBy', () {
+ test('empty', () {
+ expect(<int>[].binarySearchBy(1, toString), -1);
+ });
+ test('single', () {
+ expect([0].binarySearchBy(1, toString), -1);
+ expect([1].binarySearchBy(1, toString), 0);
+ expect([2].binarySearchBy(1, toString), -1);
+ });
+ test('multiple', () {
+ expect([1, 2, 3, 4, 5, 6].binarySearchBy(3, toString), 2);
+ });
+ });
+
+ group('.lowerBound', () {
+ test('empty', () {
+ expect(<int>[].lowerBound(1, unreachable), 0);
+ });
+ test('single', () {
+ expect([0].lowerBound(1, cmpInt), 1);
+ expect([1].lowerBound(1, cmpInt), 0);
+ expect([2].lowerBound(1, cmpInt), 0);
+ });
+ test('multiple', () {
+ expect([1, 2, 3, 4, 5, 6].lowerBound(3, cmpInt), 2);
+ expect([6, 5, 4, 3, 2, 1].lowerBound(3, cmpIntInverse), 3);
+ expect([1, 2, 4, 5, 6].lowerBound(3, cmpInt), 2);
+ expect([6, 5, 4, 2, 1].lowerBound(3, cmpIntInverse), 3);
+ });
+ });
+ group('.lowerBoundByCompare', () {
+ test('empty', () {
+ expect(<int>[].lowerBoundByCompare(1, toString, cmpParse), 0);
+ });
+ test('single', () {
+ expect([0].lowerBoundByCompare(1, toString, cmpParse), 1);
+ expect([1].lowerBoundByCompare(1, toString, cmpParse), 0);
+ expect([2].lowerBoundByCompare(1, toString, cmpParse), 0);
+ });
+ test('multiple', () {
+ expect(
+ [1, 2, 3, 4, 5, 6].lowerBoundByCompare(3, toString, cmpParse), 2);
+ expect(
+ [6, 5, 4, 3, 2, 1]
+ .lowerBoundByCompare(3, toString, cmpParseInverse),
+ 3);
+ expect([1, 2, 4, 5, 6].lowerBoundByCompare(3, toString, cmpParse), 2);
+ expect(
+ [6, 5, 4, 2, 1].lowerBoundByCompare(3, toString, cmpParseInverse),
+ 3);
+ });
+ });
+ group('.lowerBoundBy', () {
+ test('empty', () {
+ expect(<int>[].lowerBoundBy(1, toString), 0);
+ });
+ test('single', () {
+ expect([0].lowerBoundBy(1, toString), 1);
+ expect([1].lowerBoundBy(1, toString), 0);
+ expect([2].lowerBoundBy(1, toString), 0);
+ });
+ test('multiple', () {
+ expect([1, 2, 3, 4, 5, 6].lowerBoundBy(3, toString), 2);
+ expect([1, 2, 4, 5, 6].lowerBoundBy(3, toString), 2);
+ });
+ });
+ group('sortRange', () {
+ test('errors', () {
+ expect(() => [1].sortRange(-1, 1, cmpInt), throwsArgumentError);
+ expect(() => [1].sortRange(0, 2, cmpInt), throwsArgumentError);
+ expect(() => [1].sortRange(1, 0, cmpInt), throwsArgumentError);
+ });
+ test('empty range', () {
+ <int>[].sortRange(0, 0, unreachable);
+ var list = [3, 2, 1];
+ list.sortRange(0, 0, unreachable);
+ list.sortRange(3, 3, unreachable);
+ expect(list, [3, 2, 1]);
+ });
+ test('single', () {
+ [1].sortRange(0, 1, unreachable);
+ var list = [3, 2, 1];
+ list.sortRange(0, 1, unreachable);
+ list.sortRange(1, 2, unreachable);
+ list.sortRange(2, 3, unreachable);
+ });
+ test('multiple', () {
+ var list = [9, 8, 7, 6, 5, 4, 3, 2, 1];
+ list.sortRange(2, 5, cmpInt);
+ expect(list, [9, 8, 5, 6, 7, 4, 3, 2, 1]);
+ list.sortRange(4, 8, cmpInt);
+ expect(list, [9, 8, 5, 6, 2, 3, 4, 7, 1]);
+ list.sortRange(3, 6, cmpIntInverse);
+ expect(list, [9, 8, 5, 6, 3, 2, 4, 7, 1]);
+ });
+ });
+ group('.sortBy', () {
+ test('empty', () {
+ expect(<int>[]..sortBy(unreachable), []);
+ });
+ test('singleton', () {
+ expect([1]..sortBy(unreachable), [1]);
+ });
+ test('multiple', () {
+ expect([3, 20, 100]..sortBy(toString), [100, 20, 3]);
+ });
+ group('range', () {
+ test('errors', () {
+ expect(() => [1].sortBy(toString, -1, 1), throwsArgumentError);
+ expect(() => [1].sortBy(toString, 0, 2), throwsArgumentError);
+ expect(() => [1].sortBy(toString, 1, 0), throwsArgumentError);
+ });
+ test('empty', () {
+ expect([5, 7, 4, 2, 3]..sortBy(unreachable, 2, 2), [5, 7, 4, 2, 3]);
+ });
+ test('singleton', () {
+ expect([5, 7, 4, 2, 3]..sortBy(unreachable, 2, 3), [5, 7, 4, 2, 3]);
+ });
+ test('multiple', () {
+ expect(
+ [5, 7, 40, 2, 3]..sortBy((a) => '$a', 1, 4), [5, 2, 40, 7, 3]);
+ });
+ });
+ });
+ group('.sortByCompare', () {
+ test('empty', () {
+ expect(<int>[]..sortByCompare(unreachable, unreachable), []);
+ });
+ test('singleton', () {
+ expect([2]..sortByCompare(unreachable, unreachable), [2]);
+ });
+ test('multiple', () {
+ expect([30, 2, 100]..sortByCompare(toString, cmpParseInverse),
+ [100, 30, 2]);
+ });
+ group('range', () {
+ test('errors', () {
+ expect(() => [1].sortByCompare(toString, cmpParse, -1, 1),
+ throwsArgumentError);
+ expect(() => [1].sortByCompare(toString, cmpParse, 0, 2),
+ throwsArgumentError);
+ expect(() => [1].sortByCompare(toString, cmpParse, 1, 0),
+ throwsArgumentError);
+ });
+ test('empty', () {
+ expect(
+ [3, 5, 7, 3, 1]..sortByCompare(unreachable, unreachable, 2, 2),
+ [3, 5, 7, 3, 1]);
+ });
+ test('singleton', () {
+ expect(
+ [3, 5, 7, 3, 1]..sortByCompare(unreachable, unreachable, 2, 3),
+ [3, 5, 7, 3, 1]);
+ });
+ test('multiple', () {
+ expect(
+ [3, 5, 7, 30, 1]
+ ..sortByCompare(toString, cmpParseInverse, 1, 4),
+ [3, 30, 7, 5, 1]);
+ });
+ });
+ });
+ group('.shuffleRange', () {
+ test('errors', () {
+ expect(() => [1].shuffleRange(-1, 1), throwsArgumentError);
+ expect(() => [1].shuffleRange(0, 2), throwsArgumentError);
+ expect(() => [1].shuffleRange(1, 0), throwsArgumentError);
+ });
+ test('empty range', () {
+ expect(<int>[]..shuffleRange(0, 0), []);
+ expect([1, 2, 3, 4]..shuffleRange(0, 0), [1, 2, 3, 4]);
+ expect([1, 2, 3, 4]..shuffleRange(4, 4), [1, 2, 3, 4]);
+ });
+ test('singleton range', () {
+ expect([1, 2, 3, 4]..shuffleRange(0, 1), [1, 2, 3, 4]);
+ expect([1, 2, 3, 4]..shuffleRange(3, 4), [1, 2, 3, 4]);
+ });
+ test('multiple', () {
+ var list = [1, 2, 3, 4, 5];
+ do {
+ list.shuffleRange(0, 3);
+ expect(list.getRange(3, 5), [4, 5]);
+ expect(list.getRange(0, 3), unorderedEquals([1, 2, 3]));
+ } while (ListEquality().equals(list.sublist(0, 3), [1, 2, 3]));
+ // Won't terminate if shuffle *never* moves a value.
+ });
+ });
+ group('.reverseRange', () {
+ test('errors', () {
+ expect(() => [1].reverseRange(-1, 1), throwsArgumentError);
+ expect(() => [1].reverseRange(0, 2), throwsArgumentError);
+ expect(() => [1].reverseRange(1, 0), throwsArgumentError);
+ });
+ test('empty range', () {
+ expect(<int>[]..reverseRange(0, 0), []);
+ expect([1, 2, 3, 4]..reverseRange(0, 0), [1, 2, 3, 4]);
+ expect([1, 2, 3, 4]..reverseRange(4, 4), [1, 2, 3, 4]);
+ });
+ test('singleton range', () {
+ expect([1, 2, 3, 4]..reverseRange(0, 1), [1, 2, 3, 4]);
+ expect([1, 2, 3, 4]..reverseRange(3, 4), [1, 2, 3, 4]);
+ });
+ test('multiple', () {
+ var list = [1, 2, 3, 4, 5];
+ list.reverseRange(0, 3);
+ expect(list, [3, 2, 1, 4, 5]);
+ list.reverseRange(3, 5);
+ expect(list, [3, 2, 1, 5, 4]);
+ list.reverseRange(0, 5);
+ expect(list, [4, 5, 1, 2, 3]);
+ });
+ });
+ group('.swap', () {
+ test('errors', () {
+ expect(() => [1].swap(0, 1), throwsArgumentError);
+ expect(() => [1].swap(1, 1), throwsArgumentError);
+ expect(() => [1].swap(1, 0), throwsArgumentError);
+ expect(() => [1].swap(-1, 0), throwsArgumentError);
+ });
+ test('self swap', () {
+ expect([1]..swap(0, 0), [1]);
+ expect([1, 2, 3]..swap(1, 1), [1, 2, 3]);
+ });
+ test('actual swap', () {
+ expect([1, 2, 3]..swap(0, 2), [3, 2, 1]);
+ expect([1, 2, 3]..swap(2, 0), [3, 2, 1]);
+ expect([1, 2, 3]..swap(2, 1), [1, 3, 2]);
+ expect([1, 2, 3]..swap(1, 2), [1, 3, 2]);
+ expect([1, 2, 3]..swap(0, 1), [2, 1, 3]);
+ expect([1, 2, 3]..swap(1, 0), [2, 1, 3]);
+ });
+ });
+ group('.slice', () {
+ test('errors', () {
+ expect(() => [1].slice(-1, 1), throwsArgumentError);
+ expect(() => [1].slice(0, 2), throwsArgumentError);
+ expect(() => [1].slice(1, 0), throwsArgumentError);
+ var l = <int>[1];
+ var slice = l.slice(0, 1);
+ l.removeLast();
+ expect(() => slice.first, throwsConcurrentModificationError);
+ });
+ test('empty', () {
+ expect([].slice(0, 0), isEmpty);
+ });
+ test('modify', () {
+ var list = [1, 2, 3, 4, 5, 6, 7, 8, 9];
+ var slice = list.slice(2, 6);
+ expect(slice, [3, 4, 5, 6]);
+ slice.sort(cmpIntInverse);
+ expect(slice, [6, 5, 4, 3]);
+ expect(list, [1, 2, 6, 5, 4, 3, 7, 8, 9]);
+ });
+ });
+ group('equals', () {
+ test('empty', () {
+ expect(<Object>[].equals(<int>[]), true);
+ });
+ test('non-empty', () {
+ expect([1, 2.5, 'a'].equals([1.0, 2.5, 'a']), true);
+ expect([1, 2.5, 'a'].equals([1.0, 2.5, 'b']), false);
+ expect(
+ [
+ [1]
+ ].equals([
+ [1]
+ ]),
+ false);
+ expect(
+ [
+ [1]
+ ].equals([
+ [1]
+ ], const ListEquality()),
+ true);
+ });
+ });
+ group('.forEachIndexed', () {
+ test('empty', () {
+ [].forEachIndexed(unreachable);
+ });
+ test('single', () {
+ var log = [];
+ ['a'].forEachIndexed((i, s) {
+ log..add(i)..add(s);
+ });
+ expect(log, [0, 'a']);
+ });
+ test('multiple', () {
+ var log = [];
+ ['a', 'b', 'c'].forEachIndexed((i, s) {
+ log..add(i)..add(s);
+ });
+ expect(log, [0, 'a', 1, 'b', 2, 'c']);
+ });
+ });
+ group('.forEachWhile', () {
+ test('empty', () {
+ [].forEachWhile(unreachable);
+ });
+ test('single true', () {
+ var log = [];
+ ['a'].forEachWhile((s) {
+ log.add(s);
+ return true;
+ });
+ expect(log, ['a']);
+ });
+ test('single false', () {
+ var log = [];
+ ['a'].forEachWhile((s) {
+ log.add(s);
+ return false;
+ });
+ expect(log, ['a']);
+ });
+ test('multiple one', () {
+ var log = [];
+ ['a', 'b', 'c'].forEachWhile((s) {
+ log.add(s);
+ return false;
+ });
+ expect(log, ['a']);
+ });
+ test('multiple all', () {
+ var log = [];
+ ['a', 'b', 'c'].forEachWhile((s) {
+ log.add(s);
+ return true;
+ });
+ expect(log, ['a', 'b', 'c']);
+ });
+ test('multiple some', () {
+ var log = [];
+ ['a', 'b', 'c'].forEachWhile((s) {
+ log.add(s);
+ return s != 'b';
+ });
+ expect(log, ['a', 'b']);
+ });
+ });
+ group('.forEachIndexedWhile', () {
+ test('empty', () {
+ [].forEachIndexedWhile(unreachable);
+ });
+ test('single true', () {
+ var log = [];
+ ['a'].forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return true;
+ });
+ expect(log, [0, 'a']);
+ });
+ test('single false', () {
+ var log = [];
+ ['a'].forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return false;
+ });
+ expect(log, [0, 'a']);
+ });
+ test('multiple one', () {
+ var log = [];
+ ['a', 'b', 'c'].forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return false;
+ });
+ expect(log, [0, 'a']);
+ });
+ test('multiple all', () {
+ var log = [];
+ ['a', 'b', 'c'].forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return true;
+ });
+ expect(log, [0, 'a', 1, 'b', 2, 'c']);
+ });
+ test('multiple some', () {
+ var log = [];
+ ['a', 'b', 'c'].forEachIndexedWhile((i, s) {
+ log..add(i)..add(s);
+ return s != 'b';
+ });
+ expect(log, [0, 'a', 1, 'b']);
+ });
+ });
+ group('.mapIndexed', () {
+ test('empty', () {
+ expect(<String>[].mapIndexed(unreachable), isEmpty);
+ });
+ test('multiple', () {
+ expect(<String>['a', 'b'].mapIndexed((i, s) => [i, s]), [
+ [0, 'a'],
+ [1, 'b']
+ ]);
+ });
+ });
+ group('.whereIndexed', () {
+ test('empty', () {
+ expect(<String>[].whereIndexed(unreachable), isEmpty);
+ });
+ test('none', () {
+ var trace = [];
+ int log(int a, int b) {
+ trace..add(a)..add(b);
+ return b;
+ }
+
+ expect(<int>[1, 3, 5, 7].whereIndexed((i, x) => log(i, x).isEven),
+ isEmpty);
+ expect(trace, [0, 1, 1, 3, 2, 5, 3, 7]);
+ });
+ test('all', () {
+ expect(
+ <int>[1, 3, 5, 7].whereIndexed((i, x) => x.isOdd), [1, 3, 5, 7]);
+ });
+ test('some', () {
+ expect(<int>[1, 3, 5, 7].whereIndexed((i, x) => i.isOdd), [3, 7]);
+ });
+ });
+ group('.whereNotIndexed', () {
+ test('empty', () {
+ expect(<int>[].whereNotIndexed(unreachable), isEmpty);
+ });
+ test('none', () {
+ var trace = [];
+ int log(int a, int b) {
+ trace..add(a)..add(b);
+ return b;
+ }
+
+ expect(<int>[1, 3, 5, 7].whereNotIndexed((i, x) => log(i, x).isOdd),
+ isEmpty);
+ expect(trace, [0, 1, 1, 3, 2, 5, 3, 7]);
+ });
+ test('all', () {
+ expect(<int>[1, 3, 5, 7].whereNotIndexed((i, x) => x.isEven),
+ [1, 3, 5, 7]);
+ });
+ test('some', () {
+ expect(<int>[1, 3, 5, 7].whereNotIndexed((i, x) => i.isOdd), [1, 5]);
+ });
+ });
+ group('.expandIndexed', () {
+ test('empty', () {
+ expect(<int>[].expandIndexed(unreachable), isEmpty);
+ });
+ test('empty result', () {
+ expect(['a', 'b'].expandIndexed((i, v) => []), isEmpty);
+ });
+ test('larger result', () {
+ expect(['a', 'b'].expandIndexed((i, v) => ['$i', v]),
+ ['0', 'a', '1', 'b']);
+ });
+ test('varying result', () {
+ expect(['a', 'b'].expandIndexed((i, v) => i.isOdd ? ['$i', v] : []),
+ ['1', 'b']);
+ });
+ });
+ });
+ group('on comparable', () {
+ group('.binarySearch', () {
+ test('empty', () {
+ expect(<String>[].binarySearch('1', unreachable), -1);
+ expect(<String>[].binarySearch('1'), -1);
+ });
+ test('single', () {
+ expect(['0'].binarySearch('1', cmpString), -1);
+ expect(['1'].binarySearch('1', cmpString), 0);
+ expect(['2'].binarySearch('1', cmpString), -1);
+ expect(
+ ['0'].binarySearch(
+ '1',
+ ),
+ -1);
+ expect(
+ ['1'].binarySearch(
+ '1',
+ ),
+ 0);
+ expect(
+ ['2'].binarySearch(
+ '1',
+ ),
+ -1);
+ });
+ test('multiple', () {
+ expect(
+ ['1', '2', '3', '4', '5', '6'].binarySearch('3', cmpString), 2);
+ expect(['1', '2', '3', '4', '5', '6'].binarySearch('3'), 2);
+ expect(
+ ['6', '5', '4', '3', '2', '1'].binarySearch('3', cmpParseInverse),
+ 3);
+ });
+ });
+ });
+ group('.lowerBound', () {
+ test('empty', () {
+ expect(<String>[].lowerBound('1', unreachable), 0);
+ });
+ test('single', () {
+ expect(['0'].lowerBound('1', cmpString), 1);
+ expect(['1'].lowerBound('1', cmpString), 0);
+ expect(['2'].lowerBound('1', cmpString), 0);
+ expect(['0'].lowerBound('1'), 1);
+ expect(['1'].lowerBound('1'), 0);
+ expect(['2'].lowerBound('1'), 0);
+ });
+ test('multiple', () {
+ expect(['1', '2', '3', '4', '5', '6'].lowerBound('3', cmpParse), 2);
+ expect(['1', '2', '3', '4', '5', '6'].lowerBound('3'), 2);
+ expect(
+ ['6', '5', '4', '3', '2', '1'].lowerBound('3', cmpParseInverse), 3);
+ expect(['1', '2', '4', '5', '6'].lowerBound('3', cmpParse), 2);
+ expect(['1', '2', '4', '5', '6'].lowerBound('3'), 2);
+ expect(['6', '5', '4', '2', '1'].lowerBound('3', cmpParseInverse), 3);
+ });
+ });
+ group('sortRange', () {
+ test('errors', () {
+ expect(() => [1].sortRange(-1, 1, cmpInt), throwsArgumentError);
+ expect(() => [1].sortRange(0, 2, cmpInt), throwsArgumentError);
+ expect(() => [1].sortRange(1, 0, cmpInt), throwsArgumentError);
+ });
+ test('empty range', () {
+ <int>[].sortRange(0, 0, unreachable);
+ var list = [3, 2, 1];
+ list.sortRange(0, 0, unreachable);
+ list.sortRange(3, 3, unreachable);
+ expect(list, [3, 2, 1]);
+ });
+ test('single', () {
+ [1].sortRange(0, 1, unreachable);
+ var list = [3, 2, 1];
+ list.sortRange(0, 1, unreachable);
+ list.sortRange(1, 2, unreachable);
+ list.sortRange(2, 3, unreachable);
+ });
+ test('multiple', () {
+ var list = [9, 8, 7, 6, 5, 4, 3, 2, 1];
+ list.sortRange(2, 5, cmpInt);
+ expect(list, [9, 8, 5, 6, 7, 4, 3, 2, 1]);
+ list.sortRange(4, 8, cmpInt);
+ expect(list, [9, 8, 5, 6, 2, 3, 4, 7, 1]);
+ list.sortRange(3, 6, cmpIntInverse);
+ expect(list, [9, 8, 5, 6, 3, 2, 4, 7, 1]);
+ });
+ });
+ });
+}
+
+/// Creates a plain iterable not implementing any other class.
+Iterable<T> iterable<T>(Iterable<T> values) sync* {
+ yield* values;
+}
+
+Never unreachable([_, __, ___]) => fail('Unreachable');
+
+String toString(Object? o) => '$o';
+
+/// Compares values equal if they have the same remainder mod [mod].
+int Function(int, int) cmpMod(int mod) => (a, b) => a ~/ mod - b ~/ mod;
+
+/// Compares strings lexically.
+int cmpString(String a, String b) => a.compareTo(b);
+
+/// Compares strings inverse lexically.
+int cmpStringInverse(String a, String b) => b.compareTo(a);
+
+/// Compares strings by length.
+int cmpStringLength(String a, String b) => a.length - b.length;
+
+/// Compares strings by their integer numeral content.
+int cmpParse(String s1, String s2) => cmpInt(int.parse(s1), int.parse(s2));
+
+/// Compares strings inversely by their integer numeral content.
+int cmpParseInverse(String s1, String s2) =>
+ cmpIntInverse(int.parse(s1), int.parse(s2));
+
+/// Compares integers by size.
+int cmpInt(int a, int b) => a - b;
+
+/// Compares integers by inverse size.
+int cmpIntInverse(int a, int b) => b - a;
+
+/// Tests an integer for being even.
+bool isEven(int x) => x.isEven;
+
+/// Tests an integer for being odd.
+bool isOdd(int x) => x.isOdd;
