Create associated packages for the dart:collection and dart:async libs.
R=sgjesse@google.com
Review URL: https://codereview.chromium.org//113883002
git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart/pkg/collection@31260 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..bb392fd
--- /dev/null
+++ b/README.md
@@ -0,0 +1,55 @@
+Helper libraries for working with collections.
+
+The `collection` package contains a number of separate libraries
+with utility functions and classes that makes working with collections easier.
+
+## Using
+
+The `collection` package can be imported as separate libraries, or
+in totality:
+
+ import 'package:collection/equality.dart';
+ import 'package:collection/algorithms.dart';
+ import 'package:collection/wrappers.dart';
+
+or
+
+ import 'package:collection/collection.dart';
+
+## Equality
+
+The equality library gives a way to specify equality of elements and
+collections.
+
+Collections in Dart have no inherent equality. Two sets are not equal, even
+if they contain exactly the same objects as elements.
+
+The equality library provides a way to say define such an equality. In this
+case, for example, `const SetEquality(const IdentityEquality())` is an equality
+that considers two sets equal exactly if they contain identical elements.
+
+The library provides ways to define equalities on `Iterable`s, `List`s, `Set`s, and
+`Map`s, as well as combinations of these, such as:
+
+ const MapEquality(const IdentityEquality(), const ListEquality());
+
+This equality considers maps equal if they have identical keys, and the corresponding values are lists with equal (`operator==`) values.
+
+## Algorithms
+
+The algorithms library contains functions that operate on lists.
+
+It contains ways to shuffle a `List`, do binary search on a sorted `List`, and
+some different sorting algorithms.
+
+
+## Wrappers
+
+The wrappers library contains classes that "wrap" a collection.
+
+A wrapper class contains an object of the same type, and it forwards all
+methods to the wrapped object.
+
+Wrapper classes can be used in various ways, for example to restrict the type
+of an object to that of a supertype, or to change the behavior of selected
+functions on an existing object.
diff --git a/lib/algorithms.dart b/lib/algorithms.dart
new file mode 100644
index 0000000..5ff0bb3
--- /dev/null
+++ b/lib/algorithms.dart
@@ -0,0 +1,301 @@
+// Copyright (c) 2013, 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.
+
+/**
+ * Operations on collections.
+ */
+library dart.pkg.collection.algorithms;
+
+import "dart:math" show Random;
+
+/** Version of [binarySearch] optimized for comparable keys */
+int _comparableBinarySearch(List<Comparable> list, Comparable key) {
+ int min = 0;
+ int max = list.length;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ var element = list[mid];
+ int comp = element.compareTo(key);
+ if (comp == 0) return mid;
+ if (comp < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ return -1;
+}
+
+/**
+ * Returns a position of the [key] in [sortedList], if it is there.
+ *
+ * If the list isn't sorted according to the [compare] function, the result
+ * is unpredictable.
+ *
+ * If [compare] is omitted, it defaults to calling [Comparable.compareTo] on
+ * the objects.
+ *
+ * Returns -1 if [key] is not in the list by default.
+ */
+int binarySearch(List sortedList, var key,
+ { int compare(var a, var b) }) {
+ if (compare == null) {
+ return _comparableBinarySearch(sortedList, key);
+ }
+ int min = 0;
+ int max = sortedList.length;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ var element = sortedList[mid];
+ int comp = compare(element, key);
+ if (comp == 0) return mid;
+ if (comp < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ return -1;
+}
+
+
+/**
+ * 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 = null]) {
+ Random random = new Random();
+ if (end == null) end = list.length;
+ int length = end - start;
+ while (length > 1) {
+ int pos = random.nextInt(length);
+ length--;
+ var tmp1 = list[start + pos];
+ list[start + pos] = list[start + length];
+ list[start + length] = tmp1;
+ }
+}
+
+
+/**
+ * Reverses a list, or a part of a list, in-place.
+ */
+void reverse(List list, [int start = 0, int end = null]) {
+ if (end == null) end = list.length;
+ _reverse(list, start, end);
+}
+
+// Internal helper function that assumes valid arguments.
+void _reverse(List list, int start, int end) {
+ for (int i = start, j = end - 1; i < j; i++, j--) {
+ var tmp = list[i];
+ list[i] = list[j];
+ list[j] = tmp;
+ }
+}
+
+/**
+ * Sort a list using insertion sort.
+ *
+ * Insertion sort is a simple sorting algorithm. For `n` elements it does on
+ * the order of `n * log(n)` comparisons but up to `n` squared moves. The
+ * sorting is performed in-place, without using extra memory.
+ *
+ * For short lists the many moves have less impact than the simple algorithm,
+ * and it is often the favored sorting algorithm for short lists.
+ *
+ * This insertion sort is stable: Equal elements end up in the same order
+ * as they started in.
+ */
+void insertionSort(List list,
+ { int compare(a, b),
+ int start: 0,
+ int end: null }) {
+ // If the same method could have both positional and named optional
+ // parameters, this should be (list, [start, end], {compare}).
+ if (end == null) end = list.length;
+ if (compare == null) compare = Comparable.compare;
+ _insertionSort(list, compare, start, end, start + 1);
+}
+
+/**
+ * Internal helper function that assumes arguments correct.
+ *
+ * Assumes that the elements up to [sortedUntil] (not inclusive) are
+ * already sorted. The [sortedUntil] values should always be at least
+ * `start + 1`.
+ */
+void _insertionSort(List list, int compare(a, b), int start, int end,
+ int sortedUntil) {
+ for (int pos = sortedUntil; pos < end; pos++) {
+ int min = start;
+ int max = pos;
+ var element = list[pos];
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ int comparison = compare(element, list[mid]);
+ if (comparison < 0) {
+ max = mid;
+ } else {
+ min = mid + 1;
+ }
+ }
+ list.setRange(min + 1, pos + 1, list, min);
+ list[min] = element;
+ }
+}
+
+/** Limit below which merge sort defaults to insertion sort. */
+const int _MERGE_SORT_LIMIT = 32;
+
+/**
+ * Sorts a list, or a range of a list, using the merge sort algorithm.
+ *
+ * Merge-sorting works by splitting the job into two parts, sorting each
+ * recursively, and then merging the two sorted parts.
+ *
+ * This takes on the order of `n * log(n)` comparisons and moves to sort
+ * `n` elements, but requires extra space of about the same size as the list
+ * being sorted.
+ *
+ * This merge sort is stable: Equal elements end up in the same order
+ * as they started in.
+ */
+void mergeSort(List list, {int start: 0, int end: null, int compare(a, b)}) {
+ if (end == null) end = list.length;
+ if (compare == null) compare = Comparable.compare;
+ int length = end - start;
+ if (length < 2) return;
+ if (length < _MERGE_SORT_LIMIT) {
+ _insertionSort(list, compare, start, end, start + 1);
+ return;
+ }
+ // Special case the first split instead of directly calling
+ // _mergeSort, because the _mergeSort requires its target to
+ // be different from its source, and it requires extra space
+ // of the same size as the list to sort.
+ // This split allows us to have only half as much extra space,
+ // and it ends up in the original place.
+ int middle = start + ((end - start) >> 1);
+ int firstLength = middle - start;
+ int secondLength = end - middle;
+ // secondLength is always the same as firstLength, or one greater.
+ List scratchSpace = new List(secondLength);
+ _mergeSort(list, compare, middle, end, scratchSpace, 0);
+ int firstTarget = end - firstLength;
+ _mergeSort(list, compare, start, middle, list, firstTarget);
+ _merge(compare,
+ list, firstTarget, end,
+ scratchSpace, 0, secondLength,
+ list, 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(List list, int compare(a, b), int start, int end,
+ List target, int targetOffset) {
+ int length = end - start;
+ if (length == 0) return;
+ target[targetOffset] = list[start];
+ for (int i = 1; i < length; i++) {
+ var element = list[start + i];
+ int min = targetOffset;
+ int max = targetOffset + i;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ if (compare(element, target[mid]) < 0) {
+ max = mid;
+ } else {
+ min = mid + 1;
+ }
+ }
+ target.setRange(min + 1, targetOffset + i + 1,
+ target, min);
+ target[min] = element;
+ }
+}
+
+/**
+ * Sorts [list] from [start] to [end] into [target] at [targetOffset].
+ *
+ * The `target` list must be able to contain the range from `start` to `end`
+ * after `targetOffset`.
+ *
+ * Allows target to be the same list as [list], as long as it's not
+ * overlapping the `start..end` range.
+ */
+void _mergeSort(List list, int compare(a, b), int start, int end,
+ List target, int targetOffset) {
+ int length = end - start;
+ if (length < _MERGE_SORT_LIMIT) {
+ _movingInsertionSort(list, compare, start, end, target, targetOffset);
+ return;
+ }
+ int middle = start + (length >> 1);
+ int firstLength = middle - start;
+ int secondLength = end - middle;
+ // Here secondLength >= firstLength (differs by at most one).
+ int targetMiddle = targetOffset + firstLength;
+ // Sort the second half into the end of the target area.
+ _mergeSort(list, compare, middle, end,
+ target, targetMiddle);
+ // Sort the first half into the end of the source area.
+ _mergeSort(list, compare, start, middle,
+ list, middle);
+ // Merge the two parts into the target area.
+ _merge(compare,
+ list, middle, middle + firstLength,
+ target, targetMiddle, targetMiddle + secondLength,
+ target, targetOffset);
+}
+
+/**
+ * Merges two lists into a target list.
+ *
+ * One of the input lists may be positioned at the end of the target
+ * list.
+ *
+ * For equal object, elements from [firstList] are always preferred.
+ * This allows the merge to be stable if the first list contains elements
+ * that started out earlier than the ones in [secondList]
+ */
+void _merge(int compare(a, b),
+ List firstList, int firstStart, int firstEnd,
+ List secondList, int secondStart, int secondEnd,
+ List target, int targetOffset) {
+ // No empty lists reaches here.
+ assert(firstStart < firstEnd);
+ assert(secondStart < secondEnd);
+ int cursor1 = firstStart;
+ int cursor2 = secondStart;
+ var firstElement = firstList[cursor1++];
+ var secondElement = secondList[cursor2++];
+ while (true) {
+ if (compare(firstElement, secondElement) <= 0) {
+ target[targetOffset++] = firstElement;
+ if (cursor1 == firstEnd) break; // Flushing second list after loop.
+ firstElement = firstList[cursor1++];
+ } else {
+ target[targetOffset++] = secondElement;
+ if (cursor2 != secondEnd) {
+ secondElement = secondList[cursor2++];
+ continue;
+ }
+ // Second list empties first. Flushing first list here.
+ target[targetOffset++] = firstElement;
+ target.setRange(targetOffset, targetOffset + (firstEnd - cursor1),
+ firstList, cursor1);
+ return;
+ }
+ }
+ // First list empties first. Reached by break above.
+ target[targetOffset++] = secondElement;
+ target.setRange(targetOffset, targetOffset + (secondEnd - cursor2),
+ secondList, cursor2);
+}
diff --git a/lib/collection.dart b/lib/collection.dart
new file mode 100644
index 0000000..a6f192d
--- /dev/null
+++ b/lib/collection.dart
@@ -0,0 +1,22 @@
+// Copyright (c) 2013, 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.
+
+/**
+ * Exports all the individual parts of the collection-helper library.
+ *
+ * The sub-libraries of this package are:
+ *
+ * - `algorithms.dart`: Algorithms that work on lists (shuffle, binary search
+ * and various sorting algorithms).
+ * - `equality.dart`: Different notions of equality of collections.
+ * - `iterable_zip.dart`: Combining multiple iterables into one.
+ * - `wrappers.dart`: Wrapper classes that delegate to a collection object.
+ * Includes unmodifiable views of collections.
+ */
+library dart.pkg.collection;
+
+export "algorithms.dart";
+export "equality.dart";
+export "iterable_zip.dart";
+export "wrappers.dart";
diff --git a/lib/equality.dart b/lib/equality.dart
new file mode 100644
index 0000000..c6fdafa
--- /dev/null
+++ b/lib/equality.dart
@@ -0,0 +1,419 @@
+// Copyright (c) 2013, 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.
+
+/**
+ * Defines equality relations on collections.
+ */
+library dart.pkg.collection.equality;
+
+import "dart:collection";
+
+const int _HASH_MASK = 0x7fffffff;
+
+/**
+ * A generic equality relation on objects.
+ */
+abstract class Equality<E> {
+ const factory Equality() = DefaultEquality;
+
+ /**
+ * Compare two elements for being equal.
+ *
+ * This should be a proper equality relation.
+ */
+ bool equals(E e1, E e2);
+
+ /**
+ * Get a hashcode of an element.
+ *
+ * The hashcode should be compatible with [equals], so that if
+ * `equals(a, b)` then `hash(a) == hash(b)`.
+ */
+ int hash(E e);
+
+ /**
+ * Test whether an object is a valid argument to [equals] and [hash].
+ *
+ * Some implementations may be restricted to only work on specific types
+ * of objects.
+ */
+ bool isValidKey(Object o);
+}
+
+/**
+ * Equality of objects that compares only the natural equality of the objects.
+ *
+ * This equality uses the objects' own [Object.==] and [Object.hashCode] for
+ * the equality.
+ */
+class DefaultEquality implements Equality {
+ const DefaultEquality();
+ bool equals(Object e1, Object e2) => e1 == e2;
+ int hash(Object e) => e.hashCode;
+ bool isValidKey(Object o) => true;
+}
+
+/**
+ * Equality of objects that compares only the identity of the objects.
+ */
+class IdentityEquality implements Equality {
+ const IdentityEquality();
+ bool equals(Object e1, Object e2) => identical(e1, e2);
+ int hash(Object e) => identityHashCode(e);
+ bool isValidKey(Object o) => true;
+}
+
+/**
+ * Equality on iterables.
+ *
+ * Two iterables are equal if they have the same elements in the same order.
+ */
+class IterableEquality<E> implements Equality<Iterable<E>> {
+ final Equality<E> _elementEquality;
+ const IterableEquality([Equality<E> elementEquality =
+ const DefaultEquality()])
+ : _elementEquality = elementEquality;
+
+ bool equals(Iterable<E> elements1, Iterable<E> elements2) {
+ if (identical(elements1, elements2)) return true;
+ if (elements1 == null || elements2 == null) return false;
+ Iterator it1 = elements1.iterator;
+ Iterator it2 = elements2.iterator;
+ while (true) {
+ bool hasNext = it1.moveNext();
+ if (hasNext != it2.moveNext()) return false;
+ if (!hasNext) return true;
+ if (!_elementEquality.equals(it1.current, it2.current)) return false;
+ }
+ }
+
+ int hash(Iterable<E> elements) {
+ // Jenkins's one-at-a-time hash function.
+ int hash = 0;
+ for (E element in elements) {
+ int c = _elementEquality.hash(element);
+ hash = (hash + c) & _HASH_MASK;
+ hash = (hash + (hash << 10)) & _HASH_MASK;
+ hash ^= (hash >> 6);
+ }
+ hash = (hash + (hash << 3)) & _HASH_MASK;
+ hash ^= (hash >> 11);
+ hash = (hash + (hash << 15)) & _HASH_MASK;
+ return hash;
+ }
+
+ bool isValidKey(Object o) => o is Iterable<E>;
+}
+
+/**
+ * Equality on lists.
+ *
+ * Two lists are equal if they have the same length and their elements
+ * at each index are equal.
+ *
+ * This is effectively the same as [IterableEquality] except that it
+ * accesses elements by index instead of through iteration.
+ */
+class ListEquality<E> implements Equality<List<E>> {
+ final Equality<E> _elementEquality;
+ const ListEquality([Equality<E> elementEquality = const DefaultEquality()])
+ : _elementEquality = elementEquality;
+
+ bool equals(List<E> e1, List<E> e2) {
+ if (identical(e1, e2)) return true;
+ if (e1 == null || e2 == null) return false;
+ int length = e1.length;
+ if (length != e2.length) return false;
+ for (int i = 0; i < length; i++) {
+ if (!_elementEquality.equals(e1[i], e2[i])) return false;
+ }
+ return true;
+ }
+
+ int hash(List<E> e) {
+ // Jenkins's one-at-a-time hash function.
+ // This code is almost identical to the one in IterableEquality, except
+ // that it uses indexing instead of iterating to get the elements.
+ int hash = 0;
+ for (int i = 0; i < e.length; i++) {
+ int c = _elementEquality.hash(e[i]);
+ hash = (hash + c) & _HASH_MASK;
+ hash = (hash + (hash << 10)) & _HASH_MASK;
+ hash ^= (hash >> 6);
+ }
+ hash = (hash + (hash << 3)) & _HASH_MASK;
+ hash ^= (hash >> 11);
+ hash = (hash + (hash << 15)) & _HASH_MASK;
+ return hash;
+ }
+
+ bool isValidKey(Object o) => o is List<E>;
+}
+
+abstract class _UnorderedEquality<E, T extends Iterable<E>>
+ implements Equality<T> {
+ final Equality<E> _elementEquality;
+
+ const _UnorderedEquality(this._elementEquality);
+
+ bool equals(T e1, T e2) {
+ if (identical(e1, e2)) return true;
+ if (e1 == null || e2 == null) return false;
+ HashMap<E, int> counts = new HashMap(
+ equals: _elementEquality.equals,
+ hashCode: _elementEquality.hash,
+ isValidKey: _elementEquality.isValidKey);
+ int length = 0;
+ for (var e in e1) {
+ int count = counts[e];
+ if (count == null) count = 0;
+ counts[e] = count + 1;
+ length++;
+ }
+ for (var e in e2) {
+ int count = counts[e];
+ if (count == null || count == 0) return false;
+ counts[e] = count - 1;
+ length--;
+ }
+ return length == 0;
+ }
+
+ int hash(T e) {
+ int hash = 0;
+ for (E element in e) {
+ int c = _elementEquality.hash(element);
+ hash = (hash + c) & _HASH_MASK;
+ }
+ hash = (hash + (hash << 3)) & _HASH_MASK;
+ hash ^= (hash >> 11);
+ hash = (hash + (hash << 15)) & _HASH_MASK;
+ return hash;
+ }
+}
+
+/**
+ * Equality of the elements of two iterables without considering order.
+ *
+ * Two iterables are considered equal if they have the same number of elements,
+ * and the elements of one set can be paired with the elements
+ * of the other iterable, so that each pair are equal.
+ */
+class UnorderedIterableEquality<E> extends _UnorderedEquality<E, Iterable<E>> {
+ const UnorderedIterableEquality(
+ [Equality<E> elementEquality = const DefaultEquality()])
+ : super(elementEquality);
+
+ bool isValidKey(Object o) => o is Iterable<E>;
+}
+
+/**
+ * Equality of sets.
+ *
+ * Two sets are considered equal if they have the same number of elements,
+ * and the elements of one set can be paired with the elements
+ * of the other set, so that each pair are equal.
+ *
+ * This equality behaves the same as [UnorderedIterableEquality] except that
+ * it expects sets instead of iterables as arguments.
+ */
+class SetEquality<E> extends _UnorderedEquality<E, Set<E>> {
+ const SetEquality(
+ [Equality<E> elementEquality = const DefaultEquality()])
+ : super(elementEquality);
+
+ bool isValidKey(Object o) => o is Set<E>;
+}
+
+/**
+ * Internal class used by [MapEquality].
+ *
+ * The class represents a map entry as a single object,
+ * using a combined hashCode and equality of the key and value.
+ */
+class _MapEntry {
+ final MapEquality equality;
+ final key;
+ final value;
+ _MapEntry(this.equality, this.key, this.value);
+
+ int get hashCode =>
+ (3 * equality._keyEquality.hash(key) +
+ 7 * equality._valueEquality.hash(value)) & _HASH_MASK;
+
+ bool operator==(Object other) {
+ if (other is! _MapEntry) return false;
+ _MapEntry otherEntry = other;
+ return equality._keyEquality.equals(key, otherEntry.key) &&
+ equality._valueEquality.equals(value, otherEntry.value);
+
+ }
+}
+
+/**
+ * Equality on maps.
+ *
+ * Two maps are equal if they have the same number of entries, and if the
+ * entries of the two maps are pairwise equal on both key and value.
+ */
+class MapEquality<K, V> implements Equality<Map<K, V>> {
+ final Equality<K> _keyEquality;
+ final Equality<V> _valueEquality;
+ const MapEquality({ Equality<K> keys : const DefaultEquality(),
+ Equality<V> values : const DefaultEquality() })
+ : _keyEquality = keys, _valueEquality = values;
+
+ bool equals(Map<K, V> e1, Map<K, V> e2) {
+ if (identical(e1, e2)) return true;
+ if (e1 == null || e2 == null) return false;
+ int length = e1.length;
+ if (length != e2.length) return false;
+ Map<_MapEntry, int> equalElementCounts = new HashMap();
+ for (K key in e1.keys) {
+ _MapEntry entry = new _MapEntry(this, key, e1[key]);
+ int count = equalElementCounts[entry];
+ if (count == null) count = 0;
+ equalElementCounts[entry] = count + 1;
+ }
+ for (K key in e2.keys) {
+ _MapEntry entry = new _MapEntry(this, key, e2[key]);
+ int count = equalElementCounts[entry];
+ if (count == null || count == 0) return false;
+ equalElementCounts[entry] = count - 1;
+ }
+ return true;
+ }
+
+ int hash(Map<K, V> map) {
+ int hash = 0;
+ for (K key in map.keys) {
+ int keyHash = _keyEquality.hash(key);
+ int valueHash = _valueEquality.hash(map[key]);
+ hash = (hash + 3 * keyHash + 7 * valueHash) & _HASH_MASK;
+ }
+ hash = (hash + (hash << 3)) & _HASH_MASK;
+ hash ^= (hash >> 11);
+ hash = (hash + (hash << 15)) & _HASH_MASK;
+ return hash;
+ }
+
+ bool isValidKey(Object o) => o is Map<K, V>;
+}
+
+/**
+ * Combines several equalities into a single equality.
+ *
+ * Tries each equality in order, using [Equality.isValidKey], and returns
+ * the result of the first equality that applies to the argument or arguments.
+ *
+ * For `equals`, the first equality that matches the first argument is used,
+ * and if the second argument of `equals` is not valid for that equality,
+ * it returns false.
+ *
+ * Because the equalities are tried in order, they should generally work on
+ * disjoint types. Otherwise the multi-equality may give inconsistent results
+ * for `equals(e1, e2)` and `equals(e2, e1)`. This can happen if one equality
+ * considers only `e1` a valid key, and not `e2`, but an equality which is
+ * checked later, allows both.
+ */
+class MultiEquality<E> implements Equality<E> {
+ final Iterable<Equality<E>> _equalities;
+
+ const MultiEquality(Iterable<Equality<E>> equalities)
+ : _equalities = equalities;
+
+ bool equals(E e1, E e2) {
+ for (Equality<E> eq in _equalities) {
+ if (eq.isValidKey(e1)) return eq.isValidKey(e2) && eq.equals(e1, e2);
+ }
+ return false;
+ }
+
+ int hash(E e) {
+ for (Equality<E> eq in _equalities) {
+ if (eq.isValidKey(e)) return eq.hash(e);
+ }
+ return -1;
+ }
+
+ bool isValidKey(Object o) {
+ for (Equality<E> eq in _equalities) {
+ if (eq.isValidKey(o)) return true;
+ }
+ return false;
+ }
+}
+
+/**
+ * Deep equality on collections.
+ *
+ * Recognizes lists, sets, iterables and maps and compares their elements using
+ * deep equality as well.
+ *
+ * Non-iterable/map objects are compared using a configurable base equality.
+ *
+ * Works in one of two modes: ordered or unordered.
+ *
+ * In ordered mode, lists and iterables are required to have equal elements
+ * in the same order. In unordered mode, the order of elements in iterables
+ * and lists are not importan.
+ *
+ * A list is only equal to another list, likewise for sets and maps. All other
+ * iterables are compared as iterables only.
+ */
+class DeepCollectionEquality implements Equality {
+ final Equality _base;
+ final bool _unordered;
+ const DeepCollectionEquality([Equality base = const DefaultEquality()])
+ : _base = base, _unordered = false;
+
+ /**
+ * Creates a deep equality on collections where the order of lists and
+ * iterables are not considered important. That is, lists and iterables are
+ * treated as unordered iterables.
+ */
+ const DeepCollectionEquality.unordered(
+ [Equality base = const DefaultEquality()])
+ : _base = base, _unordered = true;
+
+ bool equals(e1, e2) {
+ if (e1 is Set) {
+ if (e2 is! Set) return false;
+ return new SetEquality(this).equals(e1, e2);
+ }
+ if (e1 is Map) {
+ if (e2 is! Map) return false;
+ return new MapEquality(keys: this, values: this).equals(e1, e2);
+ }
+ if (!_unordered) {
+ if (e1 is List) {
+ if (e2 is! List) return false;
+ return new ListEquality(this).equals(e1, e2);
+ }
+ if (e1 is Iterable) {
+ if (e2 is! Iterable) return false;
+ return new IterableEquality(this).equals(e1, e2);
+ }
+ } else if (e1 is Iterable) {
+ if (e2 is! Iterable) return false;
+ if (e1 is List != e2 is List) return false;
+ return new UnorderedIterableEquality(this).equals(e1, e2);
+ }
+ return _base.equals(e1, e2);
+ }
+
+ int hash(Object o) {
+ if (o is Set) return new SetEquality(this).hash(o);
+ if (o is Map) return new MapEquality(keys: this, values: this).hash(o);
+ if (!_unordered) {
+ if (o is List) return new ListEquality(this).hash(o);
+ if (o is Iterable) return new IterableEquality(this).hash(o);
+ } else if (o is Iterable) {
+ return new UnorderedIterableEquality(this).hash(o);
+ }
+ return _base.hash(o);
+ }
+
+ bool isValidKey(Object o) => o is Iterable || o is Map || _base.isValidKey(o);
+}
diff --git a/lib/src/unmodifiable_wrappers.dart b/lib/src/unmodifiable_wrappers.dart
new file mode 100644
index 0000000..022bbfe
--- /dev/null
+++ b/lib/src/unmodifiable_wrappers.dart
@@ -0,0 +1,251 @@
+// Copyright (c) 2013, 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.
+
+/**
+ * Wrappers that prevent a List, Set, or Map object from being modified.
+ *
+ * The [Set] and [Map] wrappers allow reading from the wrapped collection,
+ * but prohibit writing.
+ *
+ * The [List] wrapper prevents changes to the length of the wrapped list,
+ * but allows changes to the contents.
+ */
+part of dart.pkg.collection.wrappers;
+
+/**
+ * A fixed-length list.
+ *
+ * A `NonGrowableListView` contains a [List] object and ensures that
+ * its length does not change.
+ * Methods that would change the length of the list,
+ * such as [add] and [remove], throw an [UnsupportedError].
+ * All other methods work directly on the underlying list.
+ *
+ * This class _does_ allow changes to the contents of the wrapped list.
+ * You can, for example, [sort] the list.
+ * Permitted operations defer to the wrapped list.
+ */
+class NonGrowableListView<E> extends DelegatingList<E>
+ with NonGrowableListMixin<E> {
+ NonGrowableListView(List<E> listBase) : super(listBase);
+}
+
+/**
+ * Mixin class that implements a throwing version of all list operations that
+ * change the List's length.
+ */
+abstract class NonGrowableListMixin<E> implements List<E> {
+ static void _throw() {
+ throw new UnsupportedError(
+ "Cannot change the length of a fixed-length list");
+ }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void set length(int newLength) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ bool add(E value) {
+ _throw();
+ }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void addAll(Iterable<E> iterable) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void insert(int index, E element) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void insertAll(int index, Iterable<E> iterable) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ bool remove(Object value) { _throw(); }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ E removeAt(int index) { _throw(); }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ E removeLast() { _throw(); }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void removeWhere(bool test(E element)) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void retainWhere(bool test(E element)) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void removeRange(int start, int end) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void replaceRange(int start, int end, Iterable<E> iterable) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the length of the list are disallowed.
+ */
+ void clear() => _throw();
+}
+
+/**
+ * An unmodifiable set.
+ *
+ * An UnmodifiableSetView contains a [Set] object and ensures
+ * that it does not change.
+ * Methods that would change the set,
+ * such as [add] and [remove], throw an [UnsupportedError].
+ * Permitted operations defer to the wrapped set.
+ */
+class UnmodifiableSetView<E> extends DelegatingSet<E>
+ with UnmodifiableSetMixin<E> {
+ UnmodifiableSetView(Set<E> setBase) : super(setBase);
+}
+
+/**
+ * Mixin class that implements a throwing version of all set operations that
+ * change the Set.
+ */
+abstract class UnmodifiableSetMixin<E> implements Set<E> {
+ void _throw() {
+ throw new UnsupportedError("Cannot modify an unmodifiable Set");
+ }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the set are disallowed.
+ */
+ bool add(E value) {
+ _throw();
+ }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the set are disallowed.
+ */
+ void addAll(Iterable<E> elements) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the set are disallowed.
+ */
+ bool remove(Object value) { _throw(); }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the set are disallowed.
+ */
+ void removeAll(Iterable elements) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the set are disallowed.
+ */
+ void retainAll(Iterable elements) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the set are disallowed.
+ */
+ void removeWhere(bool test(E element)) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the set are disallowed.
+ */
+ void retainWhere(bool test(E element)) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the set are disallowed.
+ */
+ void clear() => _throw();
+}
+
+/**
+ * An unmodifiable map.
+ *
+ * An UnmodifiableMapView contains a [Map] object and ensures
+ * that it does not change.
+ * Methods that would change the map,
+ * such as [addAll] and [remove], throw an [UnsupportedError].
+ * Permitted operations defer to the wrapped map.
+ */
+class UnmodifiableMapView<K, V> extends DelegatingMap<K, V>
+ with UnmodifiableMapMixin<K, V> {
+ UnmodifiableMapView(Map<K, V> baseMap) : super(baseMap);
+}
+
+/**
+ * Mixin class that implements a throwing version of all map operations that
+ * change the Map.
+ */
+abstract class UnmodifiableMapMixin<K, V> implements Map<K, V> {
+ static void _throw() {
+ throw new UnsupportedError("Cannot modify an unmodifiable Map");
+ }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the map are disallowed.
+ */
+ void operator []=(K key, V value) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the map are disallowed.
+ */
+ V putIfAbsent(K key, V ifAbsent()) { _throw(); }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the map are disallowed.
+ */
+ void addAll(Map<K, V> other) => _throw();
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the map are disallowed.
+ */
+ V remove(K key) { _throw(); }
+
+ /**
+ * Throws an [UnsupportedError];
+ * operations that change the map are disallowed.
+ */
+ void clear() => _throw();
+}
diff --git a/lib/wrappers.dart b/lib/wrappers.dart
new file mode 100644
index 0000000..ec78f5c
--- /dev/null
+++ b/lib/wrappers.dart
@@ -0,0 +1,334 @@
+// Copyright (c) 2013, 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.
+
+/**
+ * Delegating wrappers for [Iterable], [List], [Set], [Queue] and [Map].
+ *
+ * Also adds unmodifiable views for `Set` and `Map`, and a fixed length
+ * view for `List`. The unmodifable list view from `dart:collection` is exported
+ * as well, just for completeness.
+ */
+library dart.pkg.collection.wrappers;
+
+import "dart:collection";
+import "dart:math" show Random;
+
+export "dart:collection" show UnmodifiableListView;
+
+part "src/unmodifiable_wrappers.dart";
+
+/**
+ * Creates an [Iterable] that delegates all operations to a base iterable.
+ *
+ * This class can be used hide non-`Iterable` methods of an iterable object,
+ * or it can be extended to add extra functionality on top of an existing
+ * iterable object.
+ */
+class DelegatingIterable<E> implements Iterable<E> {
+ Iterable<E> _base;
+
+ /**
+ * Create a wrapper that forwards operations to [base].
+ */
+ DelegatingIterable(Iterable<E> base) : _base = base;
+
+ bool any(bool test(E element)) => _base.any(test);
+
+ bool contains(Object element) => _base.contains(element);
+
+ E elementAt(int index) => _base.elementAt(index);
+
+ bool every(bool test(E element)) => _base.every(test);
+
+ Iterable expand(Iterable f(E element)) => _base.expand(f);
+
+ E get first => _base.first;
+
+ E firstWhere(bool test(E element), {E orElse()}) =>
+ _base.firstWhere(test, orElse: orElse);
+
+ fold(initialValue, combine(previousValue, E element)) =>
+ _base.fold(initialValue, combine);
+
+ void forEach(void f(E element)) => _base.forEach(f);
+
+ bool get isEmpty => _base.isEmpty;
+
+ bool get isNotEmpty => _base.isNotEmpty;
+
+ Iterator<E> get iterator => _base.iterator;
+
+ String join([String separator = ""]) => _base.join(separator);
+
+ E get last => _base.last;
+
+ E lastWhere(bool test(E element), {E orElse()}) =>
+ _base.lastWhere(test, orElse: orElse);
+
+ int get length => _base.length;
+
+ Iterable map(f(E element)) => _base.map(f);
+
+ E reduce(E combine(E value, E element)) => _base.reduce(combine);
+
+ E get single => _base.single;
+
+ E singleWhere(bool test(E element)) => _base.singleWhere(test);
+
+ Iterable<E> skip(int n) => _base.skip(n);
+
+ Iterable<E> skipWhile(bool test(E value)) => _base.skipWhile(test);
+
+ Iterable<E> take(int n) => _base.take(n);
+
+ Iterable<E> takeWhile(bool test(E value)) => _base.takeWhile(test);
+
+ List<E> toList({bool growable: true}) => _base.toList(growable: growable);
+
+ Set<E> toSet() => _base.toSet();
+
+ Iterable<E> where(bool test(E element)) => _base.where(test);
+}
+
+
+/**
+ * Creates a [List] that delegates all operations to a base list.
+ *
+ * This class can be used hide non-`List` methods of a list object,
+ * or it can be extended to add extra functionality on top of an existing
+ * list object.
+ */
+class DelegatingList<E> extends DelegatingIterable<E> implements List<E> {
+ DelegatingList(List<E> base) : super(base);
+
+ List<E> get _listBase => _base;
+
+ E operator [](int index) => _listBase[index];
+
+ void operator []=(int index, E value) {
+ _listBase[index] = value;
+ }
+
+ void add(E value) {
+ _listBase.add(value);
+ }
+
+ void addAll(Iterable<E> iterable) {
+ _listBase.addAll(iterable);
+ }
+
+ Map<int, E> asMap() => _listBase.asMap();
+
+ void clear() {
+ _listBase.clear();
+ }
+
+ void fillRange(int start, int end, [E fillValue]) {
+ _listBase.fillRange(start, end, fillValue);
+ }
+
+ Iterable<E> getRange(int start, int end) => _listBase.getRange(start, end);
+
+ int indexOf(E element, [int start = 0]) => _listBase.indexOf(element, start);
+
+ void insert(int index, E element) {
+ _listBase.insert(index, element);
+ }
+
+ void insertAll(int index, Iterable<E> iterable) {
+ _listBase.insertAll(index, iterable);
+ }
+
+ int lastIndexOf(E element, [int start]) =>
+ _listBase.lastIndexOf(element, start);
+
+ void set length(int newLength) {
+ _listBase.length = newLength;
+ }
+
+ bool remove(Object value) => _listBase.remove(value);
+
+ E removeAt(int index) => _listBase.removeAt(index);
+
+ E removeLast() => _listBase.removeLast();
+
+ void removeRange(int start, int end) {
+ _listBase.removeRange(start, end);
+ }
+
+ void removeWhere(bool test(E element)) {
+ _listBase.removeWhere(test);
+ }
+
+ void replaceRange(int start, int end, Iterable<E> iterable) {
+ _listBase.replaceRange(start, end, iterable);
+ }
+
+ void retainWhere(bool test(E element)) {
+ _listBase.retainWhere(test);
+ }
+
+ Iterable<E> get reversed => _listBase.reversed;
+
+ void setAll(int index, Iterable<E> iterable) {
+ _listBase.setAll(index, iterable);
+ }
+
+ void setRange(int start, int end, Iterable<E> iterable, [int skipCount = 0]) {
+ _listBase.setRange(start, end, iterable, skipCount);
+ }
+
+ void shuffle([Random random]) {
+ _listBase.shuffle(random);
+ }
+
+ void sort([int compare(E a, E b)]) {
+ _listBase.sort(compare);
+ }
+
+ List<E> sublist(int start, [int end]) => _listBase.sublist(start, end);
+}
+
+
+/**
+ * Creates a [Set] that delegates all operations to a base set.
+ *
+ * This class can be used hide non-`Set` methods of a set object,
+ * or it can be extended to add extra functionality on top of an existing
+ * set object.
+ */
+class DelegatingSet<E> extends DelegatingIterable<E> implements Set<E> {
+ DelegatingSet(Set<E> base) : super(base);
+
+ Set<E> get _setBase => _base;
+
+ bool add(E value) => _setBase.add(value);
+
+ void addAll(Iterable<E> elements) {
+ _setBase.addAll(elements);
+ }
+
+ void clear() {
+ _setBase.clear();
+ }
+
+ bool containsAll(Iterable<Object> other) => _setBase.containsAll(other);
+
+ Set<E> difference(Set<E> other) => _setBase.difference(other);
+
+ Set<E> intersection(Set<Object> other) => _setBase.intersection(other);
+
+ E lookup(E element) => _setBase.lookup(element);
+
+ bool remove(Object value) => _setBase.remove(value);
+
+ void removeAll(Iterable<Object> elements) {
+ _setBase.removeAll(elements);
+ }
+
+ void removeWhere(bool test(E element)) {
+ _setBase.removeWhere(test);
+ }
+
+ void retainAll(Iterable<Object> elements) {
+ _setBase.retainAll(elements);
+ }
+
+ void retainWhere(bool test(E element)) {
+ _setBase.retainWhere(test);
+ }
+
+ Set<E> union(Set<E> other) => _setBase.union(other);
+}
+
+/**
+ * Creates a [Queue] that delegates all operations to a base queue.
+ *
+ * This class can be used hide non-`Queue` methods of a queue object,
+ * or it can be extended to add extra functionality on top of an existing
+ * queue object.
+ */
+class DelegatingQueue<E> extends DelegatingIterable<E> implements Queue<E> {
+ DelegatingQueue(Queue<E> queue) : super(queue);
+
+ Queue<E> get _baseQueue => _base;
+
+ void add(E value) {
+ _baseQueue.add(value);
+ }
+
+ void addAll(Iterable<E> iterable) {
+ _baseQueue.addAll(iterable);
+ }
+
+ void addFirst(E value) {
+ _baseQueue.addFirst(value);
+ }
+
+ void addLast(E value) {
+ _baseQueue.addLast(value);
+ }
+
+ void clear() {
+ _baseQueue.clear();
+ }
+
+ bool remove(Object object) => _baseQueue.remove(object);
+
+ void removeWhere(bool test(E element)) { _baseQueue.removeWhere(test); }
+
+ void retainWhere(bool test(E element)) { _baseQueue.retainWhere(test); }
+
+ E removeFirst() => _baseQueue.removeFirst();
+
+ E removeLast() => _baseQueue.removeLast();
+}
+
+/**
+ * Creates a [Map] that delegates all operations to a base map.
+ *
+ * This class can be used hide non-`Map` methods of an object that extends
+ * `Map`, or it can be extended to add extra functionality on top of an existing
+ * map object.
+ */
+class DelegatingMap<K, V> implements Map<K, V> {
+ Map<K, V> _base;
+ DelegatingMap(Map<K, V> base) : _base = base;
+
+ V operator [](Object key) => _base[key];
+
+ void operator []=(K key, V value) {
+ _base[key] = value;
+ }
+
+ void addAll(Map<K, V> other) {
+ _base.addAll(other);
+ }
+
+ void clear() {
+ _base.clear();
+ }
+
+ bool containsKey(Object key) => _base.containsKey(key);
+
+ bool containsValue(Object value) => _base.containsValue(value);
+
+ void forEach(void f(K key, V value)) {
+ _base.forEach(f);
+ }
+
+ bool get isEmpty => _base.isEmpty;
+
+ bool get isNotEmpty => _base.isNotEmpty;
+
+ Iterable<K> get keys => _base.keys;
+
+ int get length => _base.length;
+
+ V putIfAbsent(K key, V ifAbsent()) => _base.putIfAbsent(key, ifAbsent);
+
+ V remove(Object key) => _base.remove(key);
+
+ Iterable<V> get values => _base.values;
+}
diff --git a/pubspec.yaml b/pubspec.yaml
new file mode 100644
index 0000000..cdcbe88
--- /dev/null
+++ b/pubspec.yaml
@@ -0,0 +1,9 @@
+name: collection
+version: 0.9.0
+author: '"Dart Team <misc@dartlang.org>"'
+description: Collections and utilities functions and classes related to collections.
+homepage: http://www.dartlang.org
+dev_dependencies:
+ unittest: ">=0.9.0 <0.10.0"
+environment:
+ sdk: ">=1.0.0 <2.0.0"
diff --git a/test/algorithms_test.dart b/test/algorithms_test.dart
new file mode 100644
index 0000000..933e268
--- /dev/null
+++ b/test/algorithms_test.dart
@@ -0,0 +1,271 @@
+// Copyright (c) 2013, 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.
+
+/// Tests algorithm utilities.
+
+import "package:collection/collection.dart";
+import "package:unittest/unittest.dart";
+import 'dart:math';
+
+void main() {
+ void testShuffle(List list) {
+ List copy = list.toList();
+ shuffle(list);
+ expect(new UnorderedIterableEquality().equals(list, copy), isTrue);
+ }
+
+ test("Shuffle 0", () {
+ testShuffle([]);
+ });
+ test("Shuffle 1", () {
+ testShuffle([1]);
+ });
+ test("Shuffle 3", () {
+ testShuffle([1, 2, 3]);
+ });
+ test("Shuffle 10", () {
+ testShuffle([1, 2, 3, 4, 5, 1, 3, 5, 7, 9]);
+ });
+ test("Shuffle shuffles", () {
+ List l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
+ List c = l.toList();
+ int count = 0;
+ do {
+ shuffle(l);
+ if (!const ListEquality().equals(c, l)) return;
+ // Odds of not changing the order should be one in ~ 16! ~= 2e+13.
+ // Repeat this 10 times, and the odds of accidentally shuffling to the
+ // same result every time is disappearingly tiny.
+ count++;
+ // If this happens even once, it's ok to report it.
+ print("Failed shuffle $count times");
+ if (count == 10) fail("Shuffle didn't change order.");
+ } while (true);
+ });
+ test("Shuffle sublist", (){
+ List l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
+ List c = l.toList();
+ shuffle(l, 4, 12);
+ expect(const IterableEquality().equals(l.getRange(0, 4),
+ c.getRange(0, 4)), isTrue);
+ expect(const IterableEquality().equals(l.getRange(12, 16),
+ c.getRange(12, 16)), isTrue);
+ expect(const UnorderedIterableEquality().equals(l.getRange(4, 12),
+ c.getRange(4, 12)),
+ isTrue);
+
+ });
+
+ test("binsearch0", () {
+ expect(binarySearch([], 2), equals(-1));
+ });
+
+ test("binsearch1", () {
+ expect(binarySearch([5], 2), equals(-1));
+ expect(binarySearch([5], 5), equals(0));
+ expect(binarySearch([5], 7), equals(-1));
+ });
+
+ test("binsearch3", () {
+ expect(binarySearch([0, 5, 10], -1), equals(-1));
+ expect(binarySearch([0, 5, 10], 0), equals(0));
+ expect(binarySearch([0, 5, 10], 2), equals(-1));
+ expect(binarySearch([0, 5, 10], 5), equals(1));
+ expect(binarySearch([0, 5, 10], 7), equals(-1));
+ expect(binarySearch([0, 5, 10], 10), equals(2));
+ expect(binarySearch([0, 5, 10], 12), equals(-1));
+ });
+
+ test("binsearchCompare0", () {
+ expect(binarySearch([], new C(2), compare: compareC), equals(-1));
+ });
+
+ test("binsearchCompare1", () {
+ var l1 = [new C(5)];
+ expect(binarySearch(l1, new C(2), compare: compareC), equals(-1));
+ expect(binarySearch(l1, new C(5), compare: compareC), equals(0));
+ expect(binarySearch(l1, new C(7), compare: compareC), equals(-1));
+ });
+
+ test("binsearchCompare3", () {
+ var l3 = [new C(0), new C(5), new C(10)];
+ expect(binarySearch(l3, new C(-1), compare: compareC), equals(-1));
+ expect(binarySearch(l3, new C(0), compare: compareC), equals(0));
+ expect(binarySearch(l3, new C(2), compare: compareC), equals(-1));
+ expect(binarySearch(l3, new C(5), compare: compareC), equals(1));
+ expect(binarySearch(l3, new C(7), compare: compareC), equals(-1));
+ expect(binarySearch(l3, new C(10), compare: compareC), equals(2));
+ expect(binarySearch(l3, new C(12), compare: compareC), equals(-1));
+ });
+
+ test("insertionSortRandom", () {
+ Random random = new Random();
+ for (int i = 0; i < 25; i++) {
+ List list = new List(i);
+ for (int j = 0; j < i; j++) {
+ list[j] = random.nextInt(25); // Expect some equal elements.
+ }
+ insertionSort(list);
+ for (int j = 1; j < i; j++) {
+ expect(list[j - 1], lessThanOrEqualTo(list[j]));
+ }
+ }
+ });
+
+ test("insertionSortSubRanges", () {
+ List 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]));
+ });
+
+ test("insertionSortSpecialCases", () {
+ List 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]));
+ });
+
+ test("MergeSortRandom", () {
+ Random random = new Random();
+ for (int i = 0; i < 250; i += 1) {
+ List list = new List(i);
+ for (int j = 0; j < i; j++) {
+ list[j] = random.nextInt(i); // Expect some equal elements.
+ }
+ mergeSort(list);
+ for (int j = 1; j < i; j++) {
+ expect(list[j - 1], lessThanOrEqualTo(list[j]));
+ }
+ }
+ });
+
+ test("MergeSortPreservesOrder", () {
+ Random random = new Random();
+ // Small case where only insertion call is called,
+ // larger case where the internal moving insertion sort is used
+ // larger cases with multiple splittings, numbers just around a power of 2.
+ for (int size in [8, 50, 511, 512, 513]) {
+ List list = new List(size);
+ // Class OC compares using id.
+ // With size elements with id's in the range 0..size/4, a number of
+ // collisions are guaranteed. These should be sorted so that the "order"
+ // part of the objects are still in order.
+ for (int i = 0; i < size; i++) {
+ list[i] = new OC(random.nextInt(size >> 2), i);
+ }
+ mergeSort(list);
+ OC prev = list[0];
+ for (int i = 1; i < size; i++) {
+ OC next = list[i];
+ expect(prev.id, lessThanOrEqualTo(next.id));
+ if (next.id == prev.id) {
+ expect(prev.order, lessThanOrEqualTo(next.order));
+ }
+ prev = next;
+ }
+ // Reverse compare on part of list.
+ List copy = list.toList();
+ int min = size >> 2;
+ int max = size - min;
+ mergeSort(list, start: min, end: max, compare: (a, b) => b.compareTo(a));
+ prev = list[min];
+ for (int i = min + 1; i < max; i++) {
+ OC next = list[i];
+ expect(prev.id, greaterThanOrEqualTo(next.id));
+ if (next.id == prev.id) {
+ expect(prev.order, lessThanOrEqualTo(next.order));
+ }
+ prev = next;
+ }
+ // Equals on OC objects is identity, so this means the parts before min,
+ // and the parts after max, didn't change at all.
+ expect(list.sublist(0, min), equals(copy.sublist(0, min)));
+ expect(list.sublist(max), equals(copy.sublist(max)));
+ }
+ });
+
+ test("MergeSortSpecialCases", () {
+ for (int size in [511, 512, 513]) {
+ // All equal.
+ List list = new List(size);
+ for (int i = 0; i < size; i++) {
+ list[i] = new OC(0, i);
+ }
+ mergeSort(list);
+ for (int i = 0; i < size; i++) {
+ expect(list[i].order, equals(i));
+ }
+ // All but one equal, first.
+ list[0] = new OC(1, 0);
+ for (int i = 1; i < size; i++) {
+ list[i] = new OC(0, i);
+ }
+ mergeSort(list);
+ for (int i = 0; i < size - 1; i++) {
+ expect(list[i].order, equals(i + 1));
+ }
+ expect(list[size - 1].order, equals(0));
+
+ // All but one equal, last.
+ for (int i = 0; i < size - 1; i++) {
+ list[i] = new OC(0, i);
+ }
+ list[size - 1] = new OC(-1, size - 1);
+ mergeSort(list);
+ expect(list[0].order, equals(size - 1));
+ for (int i = 1; i < size; i++) {
+ expect(list[i].order, equals(i - 1));
+ }
+
+ // Reversed.
+ for (int i = 0; i < size; i++) {
+ list[i] = new OC(size - 1 - i, i);
+ }
+ mergeSort(list);
+ for (int i = 0; i < size; i++) {
+ expect(list[i].id, equals(i));
+ expect(list[i].order, equals(size - 1 - i));
+ }
+ }
+ });
+
+ test("Reverse", () {
+ List l = [6, 5, 4, 3, 2, 1];
+ reverse(l, 2, 4);
+ expect(l, equals([6, 5, 3, 4, 2, 1]));
+ reverse(l, 1, 1);
+ expect(l, equals([6, 5, 3, 4, 2, 1]));
+ reverse(l, 4, 6);
+ expect(l, equals([6, 5, 3, 4, 1, 2]));
+ reverse(l, 0, 2);
+ expect(l, equals([5, 6, 3, 4, 1, 2]));
+ reverse(l, 0, 6);
+ expect(l, equals([2, 1, 4, 3, 6, 5]));
+ });
+}
+
+class C {
+ final int id;
+ C(this.id);
+}
+int compareC(C one, C other) => one.id - other.id;
+
+class OC implements Comparable<OC> {
+ final int id;
+ final int order;
+ OC(this.id, this.order);
+ int compareTo(OC other) => id - other.id;
+ String toString() => "OC[$id,$order]";
+}
diff --git a/test/equality_test.dart b/test/equality_test.dart
new file mode 100644
index 0000000..edabfd5
--- /dev/null
+++ b/test/equality_test.dart
@@ -0,0 +1,164 @@
+// Copyright (c) 2013, 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.
+
+// Tests equality utilities.
+
+import "dart:collection";
+import "package:collection/collection.dart";
+import "package:unittest/unittest.dart";
+
+main() {
+ test("IterableEquality - List", () {
+ var l1 = [1, 2, 3, 4, 5];
+ var l2 = [1.0, 2.0, 3.0, 4.0, 5.0];
+ expect(const IterableEquality().equals(l1, l2), isTrue);
+ Equality iterId = const IterableEquality(const IdentityEquality());
+ expect(iterId.equals(l1, l2), isFalse); /// 01: ok
+ });
+
+ test("IterableEquality - LinkedSet", () {
+ var l1 = new LinkedHashSet.from([1, 2, 3, 4, 5]);
+ var l2 = new LinkedHashSet.from([1.0, 2.0, 3.0, 4.0, 5.0]);
+ expect(const IterableEquality().equals(l1, l2), isTrue);
+ Equality iterId = const IterableEquality(const IdentityEquality());
+ expect(iterId.equals(l1, l2), isFalse); /// 02: ok
+ });
+
+ test("ListEquality", () {
+ var l1 = [1, 2, 3, 4, 5];
+ var l2 = [1.0, 2.0, 3.0, 4.0, 5.0];
+ expect(const ListEquality().equals(l1, l2),
+ isTrue);
+ Equality listId = const ListEquality(const IdentityEquality());
+ expect(listId.equals(l1, l2), isFalse); /// 03: ok
+ });
+
+ test("ListInequality length", () {
+ var l1 = [1, 2, 3, 4, 5];
+ var l2 = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
+ expect(const ListEquality().equals(l1, l2),
+ isFalse);
+ expect(const ListEquality(const IdentityEquality()).equals(l1, l2),
+ isFalse);
+ });
+
+ test("ListInequality value", () {
+ var l1 = [1, 2, 3, 4, 5];
+ var l2 = [1.0, 2.0, 3.0, 4.0, 6.0];
+ expect(const ListEquality().equals(l1, l2),
+ isFalse);
+ expect(const ListEquality(const IdentityEquality()).equals(l1, l2),
+ isFalse);
+ });
+
+ test("UnorderedIterableEquality", () {
+ var l1 = [1, 2, 3, 4, 5];
+ var l2 = [1.0, 3.0, 5.0, 4.0, 2.0];
+ expect(const UnorderedIterableEquality().equals(l1, l2),
+ isTrue);
+ Equality uniterId =
+ const UnorderedIterableEquality(const IdentityEquality());
+ expect(uniterId.equals(l1, l2), isFalse); /// 04: ok
+ });
+
+ test("UnorderedIterableInequality length", () {
+ var l1 = [1, 2, 3, 4, 5];
+ var l2 = [1.0, 3.0, 5.0, 4.0, 2.0, 1.0];
+ expect(const UnorderedIterableEquality().equals(l1, l2),
+ isFalse);
+ expect(const UnorderedIterableEquality(const IdentityEquality())
+ .equals(l1, l2),
+ isFalse);
+ });
+
+ test("UnorderedIterableInequality values", () {
+ var l1 = [1, 2, 3, 4, 5];
+ var l2 = [1.0, 3.0, 5.0, 4.0, 6.0];
+ expect(const UnorderedIterableEquality().equals(l1, l2),
+ isFalse);
+ expect(const UnorderedIterableEquality(const IdentityEquality())
+ .equals(l1, l2),
+ isFalse);
+ });
+
+ test("SetEquality", () {
+ var l1 = new HashSet.from([1, 2, 3, 4, 5]);
+ var l2 = new LinkedHashSet.from([1.0, 3.0, 5.0, 4.0, 2.0]);
+ expect(const SetEquality().equals(l1, l2),
+ isTrue);
+ Equality setId = const SetEquality(const IdentityEquality());
+ expect(setId.equals(l1, l2), isFalse); /// 05: ok
+ });
+
+ test("SetInequality length", () {
+ var l1 = new HashSet.from([1, 2, 3, 4, 5]);
+ var l2 = new LinkedHashSet.from([1.0, 3.0, 5.0, 4.0, 2.0, 6.0]);
+ expect(const SetEquality().equals(l1, l2),
+ isFalse);
+ expect(const SetEquality(const IdentityEquality()).equals(l1, l2),
+ isFalse);
+ });
+
+ test("SetInequality value", () {
+ var l1 = new HashSet.from([1, 2, 3, 4, 5]);
+ var l2 = new LinkedHashSet.from([1.0, 3.0, 5.0, 4.0, 6.0]);
+ expect(const SetEquality().equals(l1, l2),
+ isFalse);
+ expect(const SetEquality(const IdentityEquality()).equals(l1, l2),
+ isFalse);
+ });
+
+ var map1a = {"x": [1, 2, 3], "y": [true, false, null]};
+ var map1b = {"x": [4.0, 5.0, 6.0], "y": [false, true, null]};
+ var map2a = {"x": [3.0, 2.0, 1.0], "y": [false, true, null]};
+ var map2b = {"x": [6, 5, 4], "y": [null, false, true]};
+ var l1 = [map1a, map1b];
+ var l2 = [map2a, map2b];
+ var s1 = new Set.from(l1);
+ var s2 = new Set.from([map2b, map2a]);
+
+ test("RecursiveEquality", () {
+ const unordered = const UnorderedIterableEquality();
+ expect(unordered.equals(map1a["x"], map2a["x"]),
+ isTrue);
+ expect(unordered.equals(map1a["y"], map2a["y"]),
+ isTrue);
+ expect(unordered.equals(map1b["x"], map2b["x"]),
+ isTrue);
+ expect(unordered.equals(map1b["y"], map2b["y"]),
+ isTrue);
+ const mapval = const MapEquality(values: unordered);
+ expect(
+ mapval.equals(map1a, map2a),
+ isTrue);
+ expect(mapval.equals(map1b, map2b),
+ isTrue);
+ const listmapval = const ListEquality(mapval);
+ expect(listmapval.equals(l1, l2),
+ isTrue);
+ const setmapval = const SetEquality(mapval);
+ expect(setmapval.equals(s1, s2),
+ isTrue);
+ });
+
+ test("DeepEquality", () {
+ var colleq = const DeepCollectionEquality.unordered();
+ expect(colleq.equals(map1a["x"], map2a["x"]),
+ isTrue);
+ expect(colleq.equals(map1a["y"], map2a["y"]),
+ isTrue);
+ expect(colleq.equals(map1b["x"], map2b["x"]),
+ isTrue);
+ expect(colleq.equals(map1b["y"], map2b["y"]),
+ isTrue);
+ expect(colleq.equals(map1a, map2a),
+ isTrue);
+ expect(colleq.equals(map1b, map2b),
+ isTrue);
+ expect(colleq.equals(l1, l2),
+ isTrue);
+ expect(colleq.equals(s1, s2),
+ isTrue);
+ });
+}
diff --git a/test/unmodifiable_collection_test.dart b/test/unmodifiable_collection_test.dart
new file mode 100644
index 0000000..d810b75
--- /dev/null
+++ b/test/unmodifiable_collection_test.dart
@@ -0,0 +1,629 @@
+// Copyright (c) 2013, 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/wrappers.dart";
+import "package:unittest/unittest.dart";
+
+// Test unmodifiable collection views.
+// The collections should pass through the operations that are allowed,
+// an throw on the ones that aren't without affecting the original.
+
+main() {
+ List list = [];
+ testUnmodifiableList(list, new UnmodifiableListView(list), "empty");
+ list = [42];
+ testUnmodifiableList(list, new UnmodifiableListView(list), "single-42");
+ list = [7];
+ testUnmodifiableList(list, new UnmodifiableListView(list), "single!42");
+ list = [1, 42, 10];
+ testUnmodifiableList(list, new UnmodifiableListView(list), "three-42");
+ list = [1, 7, 10];
+ testUnmodifiableList(list, new UnmodifiableListView(list), "three!42");
+
+ list = [];
+ testNonGrowableList(list, new NonGrowableListView(list), "empty");
+ list = [42];
+ testNonGrowableList(list, new NonGrowableListView(list), "single-42");
+ list = [7];
+ testNonGrowableList(list, new NonGrowableListView(list), "single!42");
+ list = [1, 42, 10];
+ testNonGrowableList(list, new NonGrowableListView(list), "three-42");
+ list = [1, 7, 10];
+ testNonGrowableList(list, new NonGrowableListView(list), "three!42");
+
+ Set aSet = new Set();
+ testUnmodifiableSet(aSet, new UnmodifiableSetView(aSet), "empty");
+ aSet = new Set.from([42]);
+ testUnmodifiableSet(aSet, new UnmodifiableSetView(aSet), "single-42");
+ aSet = new Set.from([7]);
+ testUnmodifiableSet(aSet, new UnmodifiableSetView(aSet), "single!42");
+ aSet = new Set.from([1, 42, 10]);
+ testUnmodifiableSet(aSet, new UnmodifiableSetView(aSet), "three-42");
+ aSet = new Set.from([1, 7, 10]);
+ testUnmodifiableSet(aSet, new UnmodifiableSetView(aSet), "three!42");
+
+ Map map = new Map();
+ testUnmodifiableMap(map, new UnmodifiableMapView(map), "empty");
+ map = new Map()..[0] = 2;
+ testUnmodifiableMap(map, new UnmodifiableMapView(map), "single-0");
+ map = new Map()..[3] = 2;
+ testUnmodifiableMap(map, new UnmodifiableMapView(map), "single!0");
+ map = new Map()..[0] = 2
+ ..[1] = 1
+ ..[2] = 0;
+ testUnmodifiableMap(map, new UnmodifiableMapView(map), "three-0");
+ map = new Map()..[3] = 2
+ ..[1] = 1
+ ..[2] = 3;
+ testUnmodifiableMap(map, new UnmodifiableMapView(map), "three!0");
+}
+
+void testUnmodifiableList(List original, List wrapped, String name) {
+ name = "unmodifiable-list-$name";
+ testIterable(original, wrapped, name);
+ testReadList(original, wrapped, name);
+ testNoWriteList(original, wrapped, name);
+ testNoChangeLengthList(original, wrapped, name);
+}
+
+void testNonGrowableList(List original, List wrapped, String name) {
+ name = "nongrowable-list-$name";
+ testIterable(original, wrapped, name);
+ testReadList(original, wrapped, name);
+ testWriteList(original, wrapped, name);
+ testNoChangeLengthList(original, wrapped, name);
+}
+
+void testUnmodifiableSet(Set original, Set wrapped, String name) {
+ name = "unmodifiable-set-$name";
+ testIterable(original, wrapped, name);
+ testReadSet(original, wrapped, name);
+ testNoChangeSet(original, wrapped, name);
+}
+
+void testUnmodifiableMap(Map original, Map wrapped, name) {
+ name = "unmodifiable-map-$name";
+ testReadMap(original, wrapped, name);
+ testNoChangeMap(original, wrapped, name);
+}
+
+void testIterable(Iterable original, Iterable wrapped, String name) {
+ test("$name - any", () {
+ expect(wrapped.any((x) => true), equals(original.any((x) => true)));
+ expect(wrapped.any((x) => false), equals(original.any((x) => false)));
+ });
+
+ test("$name - contains", () {
+ expect(wrapped.contains(0), equals(original.contains(0)));
+ });
+
+ test("$name - elementAt", () {
+ if (original.isEmpty) {
+ expect(() => wrapped.elementAt(0), throws);
+ } else {
+ expect(wrapped.elementAt(0), equals(original.elementAt(0)));
+ }
+ });
+
+ test("$name - every", () {
+ expect(wrapped.every((x) => true), equals(original.every((x) => true)));
+ expect(wrapped.every((x) => false), equals(original.every((x) => false)));
+ });
+
+ test("$name - expand", () {
+ expect(wrapped.expand((x) => [x, x]),
+ equals(original.expand((x) => [x, x])));
+ });
+
+ test("$name - first", () {
+ if (original.isEmpty) {
+ expect(() => wrapped.first, throws);
+ } else {
+ expect(wrapped.first, equals(original.first));
+ }
+ });
+
+ test("$name - firstWhere", () {
+ if (original.isEmpty) {
+ expect(() => wrapped.firstWhere((_) => true), throws);
+ } else {
+ expect(wrapped.firstWhere((_) => true),
+ equals(original.firstWhere((_) => true)));
+ }
+ expect(() => wrapped.firstWhere((_) => false), throws);
+ });
+
+ test("$name - fold", () {
+ expect(wrapped.fold(0, (x, y) => x + y),
+ equals(original.fold(0, (x, y) => x + y)));
+ });
+
+ test("$name - forEach", () {
+ int wrapCtr = 0;
+ int origCtr = 0;
+ wrapped.forEach((x) { wrapCtr += x; });
+ original.forEach((x) { origCtr += x; });
+ expect(wrapCtr, equals(origCtr));
+ });
+
+ test("$name - isEmpty", () {
+ expect(wrapped.isEmpty, equals(original.isEmpty));
+ });
+
+ test("$name - isNotEmpty", () {
+ expect(wrapped.isNotEmpty, equals(original.isNotEmpty));
+ });
+
+ test("$name - iterator", () {
+ Iterator wrapIter = wrapped.iterator;
+ Iterator origIter = original.iterator;
+ while (origIter.moveNext()) {
+ expect(wrapIter.moveNext(), equals(true));
+ expect(wrapIter.current, equals(origIter.current));
+ }
+ expect(wrapIter.moveNext(), equals(false));
+ });
+
+ test("$name - join", () {
+ expect(wrapped.join(""), equals(original.join("")));
+ expect(wrapped.join("-"), equals(original.join("-")));
+ });
+
+ test("$name - last", () {
+ if (original.isEmpty) {
+ expect(() => wrapped.last, throws);
+ } else {
+ expect(wrapped.last, equals(original.last));
+ }
+ });
+
+ test("$name - lastWhere", () {
+ if (original.isEmpty) {
+ expect(() => wrapped.lastWhere((_) => true), throws);
+ } else {
+ expect(wrapped.lastWhere((_) => true),
+ equals(original.lastWhere((_) => true)));
+ }
+ expect(() => wrapped.lastWhere((_) => false), throws);
+ });
+
+ test("$name - length", () {
+ expect(wrapped.length, equals(original.length));
+ });
+
+ test("$name - map", () {
+ expect(wrapped.map((x) => "[$x]"),
+ equals(original.map((x) => "[$x]")));
+ });
+
+ test("$name - reduce", () {
+ if (original.isEmpty) {
+ expect(() => wrapped.reduce((x, y) => x + y), throws);
+ } else {
+ expect(wrapped.reduce((x, y) => x + y),
+ equals(original.reduce((x, y) => x + y)));
+ }
+ });
+
+ test("$name - single", () {
+ if (original.length != 1) {
+ expect(() => wrapped.single, throws);
+ } else {
+ expect(wrapped.single, equals(original.single));
+ }
+ });
+
+ test("$name - singleWhere", () {
+ if (original.length != 1) {
+ expect(() => wrapped.singleWhere((_) => true), throws);
+ } else {
+ expect(wrapped.singleWhere((_) => true),
+ equals(original.singleWhere((_) => true)));
+ }
+ expect(() => wrapped.singleWhere((_) => false), throws);
+ });
+
+ test("$name - skip", () {
+ expect(wrapped.skip(0), orderedEquals(original.skip(0)));
+ expect(wrapped.skip(1), orderedEquals(original.skip(1)));
+ expect(wrapped.skip(5), orderedEquals(original.skip(5)));
+ });
+
+ test("$name - skipWhile", () {
+ expect(wrapped.skipWhile((x) => true),
+ orderedEquals(original.skipWhile((x) => true)));
+ expect(wrapped.skipWhile((x) => false),
+ orderedEquals(original.skipWhile((x) => false)));
+ expect(wrapped.skipWhile((x) => x != 42),
+ orderedEquals(original.skipWhile((x) => x != 42)));
+ });
+
+ test("$name - take", () {
+ expect(wrapped.take(0), orderedEquals(original.take(0)));
+ expect(wrapped.take(1), orderedEquals(original.take(1)));
+ expect(wrapped.take(5), orderedEquals(original.take(5)));
+ });
+
+ test("$name - takeWhile", () {
+ expect(wrapped.takeWhile((x) => true),
+ orderedEquals(original.takeWhile((x) => true)));
+ expect(wrapped.takeWhile((x) => false),
+ orderedEquals(original.takeWhile((x) => false)));
+ expect(wrapped.takeWhile((x) => x != 42),
+ orderedEquals(original.takeWhile((x) => x != 42)));
+ });
+
+ test("$name - toList", () {
+ expect(wrapped.toList(), orderedEquals(original.toList()));
+ expect(wrapped.toList(growable: false),
+ orderedEquals(original.toList(growable: false)));
+ });
+
+ test("$name - toSet", () {
+ expect(wrapped.toSet(), unorderedEquals(original.toSet()));
+ });
+
+ test("$name - where", () {
+ expect(wrapped.where((x) => true),
+ orderedEquals(original.where((x) => true)));
+ expect(wrapped.where((x) => false),
+ orderedEquals(original.where((x) => false)));
+ expect(wrapped.where((x) => x != 42),
+ orderedEquals(original.where((x) => x != 42)));
+ });
+}
+
+void testReadList(List original, List wrapped, String name) {
+ test("$name - length", () {
+ expect(wrapped.length, equals(original.length));
+ });
+
+ test("$name - isEmpty", () {
+ expect(wrapped.isEmpty, equals(original.isEmpty));
+ });
+
+ test("$name - isNotEmpty", () {
+ expect(wrapped.isNotEmpty, equals(original.isNotEmpty));
+ });
+
+ test("$name - []", () {
+ if (original.isEmpty) {
+ expect(() { wrapped[0]; }, throwsRangeError);
+ } else {
+ expect(wrapped[0], equals(original[0]));
+ }
+ });
+
+ test("$name - indexOf", () {
+ expect(wrapped.indexOf(42), equals(original.indexOf(42)));
+ });
+
+ test("$name - lastIndexOf", () {
+ expect(wrapped.lastIndexOf(42), equals(original.lastIndexOf(42)));
+ });
+
+ test("$name - getRange", () {
+ int len = original.length;
+ expect(wrapped.getRange(0, len), equals(original.getRange(0, len)));
+ expect(wrapped.getRange(len ~/ 2, len),
+ equals(original.getRange(len ~/ 2, len)));
+ expect(wrapped.getRange(0, len ~/ 2),
+ equals(original.getRange(0, len ~/ 2)));
+ });
+
+ test("$name - sublist", () {
+ int len = original.length;
+ expect(wrapped.sublist(0), equals(original.sublist(0)));
+ expect(wrapped.sublist(len ~/ 2), equals(original.sublist(len ~/ 2)));
+ expect(wrapped.sublist(0, len ~/ 2),
+ equals(original.sublist(0, len ~/ 2)));
+ });
+
+ test("$name - asMap", () {
+ expect(wrapped.asMap(), equals(original.asMap()));
+ });
+}
+
+void testNoWriteList(List original, List wrapped, String name) {
+ List copy = new List.from(original);
+
+ testThrows(name, thunk) {
+ test(name, () {
+ expect(thunk, throwsUnsupportedError);
+ // No modifications happened.
+ expect(original, equals(copy));
+ });
+ }
+
+ testThrows("$name - []= throws", () { wrapped[0] = 42; });
+
+ testThrows("$name - sort throws", () { wrapped.sort(); });
+
+ testThrows("$name - fillRange throws", () {
+ wrapped.fillRange(0, wrapped.length, 42);
+ });
+
+ testThrows("$name - setRange throws", () {
+ wrapped.setRange(0, wrapped.length,
+ new Iterable.generate(wrapped.length, (i) => i));
+ });
+
+ testThrows("$name - setAll throws", () {
+ wrapped.setAll(0, new Iterable.generate(wrapped.length, (i) => i));
+ });
+}
+
+void testWriteList(List original, List wrapped, String name) {
+ List copy = new List.from(original);
+
+ test("$name - []=", () {
+ if (original.isNotEmpty) {
+ int originalFirst = original[0];
+ wrapped[0] = originalFirst + 1;
+ expect(original[0], equals(originalFirst + 1));
+ original[0] = originalFirst;
+ } else {
+ expect(() { wrapped[0] = 42; }, throws);
+ }
+ });
+
+ test("$name - sort", () {
+ List sortCopy = new List.from(original);
+ sortCopy.sort();
+ wrapped.sort();
+ expect(original, orderedEquals(sortCopy));
+ original.setAll(0, copy);
+ });
+
+ test("$name - fillRange", () {
+ wrapped.fillRange(0, wrapped.length, 37);
+ for (int i = 0; i < original.length; i++) {
+ expect(original[i], equals(37));
+ }
+ original.setAll(0, copy);
+ });
+
+ test("$name - setRange", () {
+ List reverseList = original.reversed.toList();
+ wrapped.setRange(0, wrapped.length, reverseList);
+ expect(original, equals(reverseList));
+ original.setAll(0, copy);
+ });
+
+ test("$name - setAll", () {
+ List reverseList = original.reversed.toList();
+ wrapped.setAll(0, reverseList);
+ expect(original, equals(reverseList));
+ original.setAll(0, copy);
+ });
+}
+
+void testNoChangeLengthList(List original, List wrapped, String name) {
+ List copy = new List.from(original);
+
+ testThrows(name, thunk) {
+ test(name, () {
+ expect(thunk, throwsUnsupportedError);
+ // No modifications happened.
+ expect(original, equals(copy));
+ });
+ }
+
+ testThrows("$name - length= throws", () {
+ wrapped.length = 100;
+ });
+
+ testThrows("$name - add throws", () {
+ wrapped.add(42);
+ });
+
+ testThrows("$name - addAll throws", () {
+ wrapped.addAll([42]);
+ });
+
+ testThrows("$name - insert throws", () {
+ wrapped.insert(0, 42);
+ });
+
+ testThrows("$name - insertAll throws", () {
+ wrapped.insertAll(0, [42]);
+ });
+
+ testThrows("$name - remove throws", () {
+ wrapped.remove(42);
+ });
+
+ testThrows("$name - removeAt throws", () {
+ wrapped.removeAt(0);
+ });
+
+ testThrows("$name - removeLast throws", () {
+ wrapped.removeLast();
+ });
+
+ testThrows("$name - removeWhere throws", () {
+ wrapped.removeWhere((element) => false);
+ });
+
+ testThrows("$name - retainWhere throws", () {
+ wrapped.retainWhere((element) => true);
+ });
+
+ testThrows("$name - removeRange throws", () {
+ wrapped.removeRange(0, wrapped.length);
+ });
+
+ testThrows("$name - replaceRange throws", () {
+ wrapped.replaceRange(0, wrapped.length, [42]);
+ });
+
+ testThrows("$name - clear throws", () {
+ wrapped.clear();
+ });
+}
+
+void testReadSet(Set original, Set wrapped, String name) {
+ Set copy = new Set.from(original);
+
+ test("$name - containsAll", () {
+ expect(wrapped.containsAll(copy), isTrue);
+ expect(wrapped.containsAll(copy.toList()), isTrue);
+ expect(wrapped.containsAll([]), isTrue);
+ expect(wrapped.containsAll([42]), equals(original.containsAll([42])));
+ });
+
+ test("$name - intersection", () {
+ expect(wrapped.intersection(new Set()), isEmpty);
+ expect(wrapped.intersection(copy), unorderedEquals(original));
+ expect(wrapped.intersection(new Set.from([42])),
+ new Set.from(original.contains(42) ? [42] : []));
+ });
+
+ test("$name - union", () {
+ expect(wrapped.union(new Set()), unorderedEquals(original));
+ expect(wrapped.union(copy), unorderedEquals(original));
+ expect(wrapped.union(new Set.from([42])),
+ equals(original.union(new Set.from([42]))));
+ });
+
+ test("$name - difference", () {
+ expect(wrapped.difference(new Set()), unorderedEquals(original));
+ expect(wrapped.difference(copy), isEmpty);
+ expect(wrapped.difference(new Set.from([42])),
+ equals(original.difference(new Set.from([42]))));
+ });
+}
+
+void testNoChangeSet(Set original, Set wrapped, String name) {
+ List originalElements = original.toList();
+
+ testThrows(name, thunk) {
+ test(name, () {
+ expect(thunk, throwsUnsupportedError);
+ // No modifications happened.
+ expect(original.toList(), equals(originalElements));
+ });
+ }
+
+ testThrows("$name - add throws", () {
+ wrapped.add(42);
+ });
+
+ testThrows("$name - addAll throws", () {
+ wrapped.addAll([42]);
+ });
+
+ testThrows("$name - addAll empty throws", () {
+ wrapped.addAll([]);
+ });
+
+ testThrows("$name - remove throws", () {
+ wrapped.remove(42);
+ });
+
+ testThrows("$name - removeAll throws", () {
+ wrapped.removeAll([42]);
+ });
+
+ testThrows("$name - removeAll empty throws", () {
+ wrapped.removeAll([]);
+ });
+
+ testThrows("$name - retainAll throws", () {
+ wrapped.retainAll([42]);
+ });
+
+ testThrows("$name - removeWhere throws", () {
+ wrapped.removeWhere((_) => false);
+ });
+
+ testThrows("$name - retainWhere throws", () {
+ wrapped.retainWhere((_) => true);
+ });
+
+ testThrows("$name - clear throws", () {
+ wrapped.clear();
+ });
+}
+
+void testReadMap(Map original, Map wrapped, String name) {
+ test("$name length", () {
+ expect(wrapped.length, equals(original.length));
+ });
+
+ test("$name isEmpty", () {
+ expect(wrapped.isEmpty, equals(original.isEmpty));
+ });
+
+ test("$name isNotEmpty", () {
+ expect(wrapped.isNotEmpty, equals(original.isNotEmpty));
+ });
+
+ test("$name operator[]", () {
+ expect(wrapped[0], equals(original[0]));
+ expect(wrapped[999], equals(original[999]));
+ });
+
+ test("$name containsKey", () {
+ expect(wrapped.containsKey(0), equals(original.containsKey(0)));
+ expect(wrapped.containsKey(999), equals(original.containsKey(999)));
+ });
+
+ test("$name containsValue", () {
+ expect(wrapped.containsValue(0), equals(original.containsValue(0)));
+ expect(wrapped.containsValue(999), equals(original.containsValue(999)));
+ });
+
+ test("$name forEach", () {
+ int origCnt = 0;
+ int wrapCnt = 0;
+ wrapped.forEach((k, v) { wrapCnt += 1 << k + 3 * v; });
+ original.forEach((k, v) { origCnt += 1 << k + 3 * v; });
+ expect(wrapCnt, equals(origCnt));
+ });
+
+ test("$name keys", () {
+ expect(wrapped.keys, orderedEquals(original.keys));
+ });
+
+ test("$name values", () {
+ expect(wrapped.values, orderedEquals(original.values));
+ });
+}
+
+testNoChangeMap(Map original, Map wrapped, String name) {
+ Map copy = new Map.from(original);
+
+ testThrows(name, thunk) {
+ test(name, () {
+ expect(thunk, throwsUnsupportedError);
+ // No modifications happened.
+ expect(original, equals(copy));
+ });
+ }
+
+ testThrows("$name operator[]= throws", () {
+ wrapped[0] = 42;
+ });
+
+ testThrows("$name putIfAbsent throws", () {
+ wrapped.putIfAbsent(0, () => 42);
+ });
+
+ testThrows("$name addAll throws", () {
+ wrapped.addAll(new Map()..[42] = 42);
+ });
+
+ testThrows("$name addAll empty throws", () {
+ wrapped.addAll(new Map());
+ });
+
+ testThrows("$name remove throws", () {
+ wrapped.remove(0);
+ });
+
+ testThrows("$name clear throws", () {
+ wrapped.clear();
+ });
+}
diff --git a/test/wrapper_test.dart b/test/wrapper_test.dart
new file mode 100644
index 0000000..875a70a
--- /dev/null
+++ b/test/wrapper_test.dart
@@ -0,0 +1,255 @@
+// Copyright (c) 2013, 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.
+
+/// Tests wrapper utilities.
+
+import "dart:collection";
+import "package:collection/collection.dart";
+import "package:unittest/unittest.dart";
+
+// Test that any member access/call on the wrapper object is equal to
+// an expected access on the wrapped object.
+// This is implemented by capturing accesses using noSuchMethod and comparing
+// them to expected accesses captured previously.
+
+// Compare two Invocations for having equal type and arguments.
+void testInvocations(Invocation i1, Invocation i2) {
+ String name = "${i1.memberName}";
+ expect(i1.isGetter, equals(i2.isGetter), reason: name);
+ expect(i1.isSetter, equals(i2.isSetter), reason: name);
+ expect(i1.memberName, equals(i2.memberName), reason: name);
+ expect(i1.positionalArguments, equals(i2.positionalArguments), reason: name);
+ expect(i1.namedArguments, equals(i2.namedArguments), reason: name);
+}
+
+/**
+ * Utility class to record a member access and a member access on a wrapped
+ * object, and compare them for equality.
+ */
+abstract class Expector {
+ getWrappedObject(action(Invocation i));
+ // Hack to test assignment ([]=) because it doesn't return the result
+ // of the member call. Instead use (expect..[4]=5).equal[4]=5 where
+ // you would normally use expect[4].equals[4] for non-assignments.
+ var equals;
+
+ noSuchMethod(Invocation m) => new _Equals(equals = getWrappedObject((m2) {
+ testInvocations(m, m2);
+ }));
+}
+
+// An object with a field called "equals", only introduced into the
+// flow to allow writing expect.xxx.equals.xxx.
+class _Equals {
+ final equals;
+ _Equals(this.equals);
+}
+
+// Parameterization of noSuchMethod.
+class NSM {
+ Function _action;
+ NSM(this._action);
+ noSuchMethod(Invocation i) => _action(i);
+}
+
+// LikeNSM, but has types Iterable, Set and List to allow it as
+// argument to DelegatingIterable/Set/List.
+class IterableNSM extends NSM implements Iterable, Set, List, Queue {
+ IterableNSM(action(Invocation i)) : super(action);
+ noSuchMethod(Invocation i) => super.noSuchMethod(i); // Silence warnings
+}
+
+// Expector that wraps in DelegatingIterable.
+class IterableExpector extends Expector {
+ getWrappedObject(void action(Invocation i)) {
+ return new DelegatingIterable(new IterableNSM(action));
+ }
+}
+
+// Expector that wraps in DelegatingList.
+class ListExpector extends Expector {
+ getWrappedObject(void action(Invocation i)) {
+ return new DelegatingList(new IterableNSM(action));
+ }
+}
+
+// Expector that wraps in DelegatingSet.
+class SetExpector extends Expector {
+ getWrappedObject(void action(Invocation i)) {
+ return new DelegatingSet(new IterableNSM(action));
+ }
+}
+
+// Expector that wraps in DelegatingSet.
+class QueueExpector extends Expector {
+ getWrappedObject(void action(Invocation i)) {
+ return new DelegatingQueue(new IterableNSM(action));
+ }
+}
+
+// Like NSM but implements Map to allow as argument for DelegatingMap.
+class MapNSM extends NSM implements Map {
+ MapNSM(action(Invocation i)) : super(action);
+ noSuchMethod(Invocation i) => super.noSuchMethod(i);
+}
+
+// Expector that wraps in DelegatingMap.
+class MapExpector extends Expector {
+ getWrappedObject(void action(Invocation i)) {
+ return new DelegatingMap(new MapNSM(action));
+ }
+}
+
+// Utility values to use as arguments in calls.
+func0() {}
+func1(x) {}
+func2(x, y) {}
+var val = new Object();
+
+void main() {
+ testIterable(var expect) {
+ expect.any(func1).equals.any(func1);
+ expect.contains(val).equals.contains(val);
+ expect.elementAt(0).equals.elementAt(0);
+ expect.every(func1).equals.every(func1);
+ expect.expand(func1).equals.expand(func1);
+ expect.first.equals.first;
+ // Default values of the Iterable interface will be added in the
+ // second call to firstWhere, so we must record them in our
+ // expectation (which doesn't have the interface implementat or
+ // its default values).
+ expect.firstWhere(func1, orElse: null).equals.firstWhere(func1);
+ expect.firstWhere(func1, orElse: func0).equals.
+ firstWhere(func1, orElse: func0);
+ expect.fold(null, func2).equals.fold(null, func2);
+ expect.forEach(func1).equals.forEach(func1);
+ expect.isEmpty.equals.isEmpty;
+ expect.isNotEmpty.equals.isNotEmpty;
+ expect.iterator.equals.iterator;
+ expect.join('').equals.join();
+ expect.join("X").equals.join("X");
+ expect.last.equals.last;
+ expect.lastWhere(func1, orElse: null).equals.lastWhere(func1);
+ expect.lastWhere(func1, orElse: func0).equals.
+ lastWhere(func1, orElse: func0);
+ expect.length.equals.length;
+ expect.map(func1).equals.map(func1);
+ expect.reduce(func2).equals.reduce(func2);
+ expect.single.equals.single;
+ expect.singleWhere(func1).equals.singleWhere(func1);
+ expect.skip(5).equals.skip(5);
+ expect.skipWhile(func1).equals.skipWhile(func1);
+ expect.take(5).equals.take(5);
+ expect.takeWhile(func1).equals.takeWhile(func1);
+ expect.toList(growable: true).equals.toList();
+ expect.toList(growable: true).equals.toList(growable: true);
+ expect.toList(growable: false).equals.toList(growable: false);
+ expect.toSet().equals.toSet();
+ expect.where(func1).equals.where(func1);
+ }
+
+ void testList(var expect) {
+ testIterable(expect);
+
+ expect[4].equals[4];
+ (expect..[4] = 5).equals[4] = 5;
+
+ expect.add(val).equals.add(val);
+ expect.addAll([val]).equals.addAll([val]);
+ expect.asMap().equals.asMap();
+ expect.clear().equals.clear();
+ expect.fillRange(4, 5, null).equals.fillRange(4, 5);
+ expect.fillRange(4, 5, val).equals.fillRange(4, 5, val);
+ expect.getRange(4, 5).equals.getRange(4, 5);
+ expect.indexOf(val, 0).equals.indexOf(val);
+ expect.indexOf(val, 4).equals.indexOf(val, 4);
+ expect.insert(4, val).equals.insert(4, val);
+ expect.insertAll(4, [val]).equals.insertAll(4, [val]);
+ expect.lastIndexOf(val, null).equals.lastIndexOf(val);
+ expect.lastIndexOf(val, 4).equals.lastIndexOf(val, 4);
+ (expect..length = 4).equals.length = 4;
+ expect.remove(val).equals.remove(val);
+ expect.removeAt(4).equals.removeAt(4);
+ expect.removeLast().equals.removeLast();
+ expect.removeRange(4, 5).equals.removeRange(4, 5);
+ expect.removeWhere(func1).equals.removeWhere(func1);
+ expect.replaceRange(4, 5, [val]).equals.replaceRange(4, 5, [val]);
+ expect.retainWhere(func1).equals.retainWhere(func1);
+ expect.reversed.equals.reversed;
+ expect.setAll(4, [val]).equals.setAll(4, [val]);
+ expect.setRange(4, 5, [val], 0).equals.setRange(4, 5, [val]);
+ expect.setRange(4, 5, [val], 3).equals.setRange(4, 5, [val], 3);
+ expect.sort(null).equals.sort();
+ expect.sort(func2).equals.sort(func2);
+ expect.sublist(4, null).equals.sublist(4);
+ expect.sublist(4, 5).equals.sublist(4, 5);
+ }
+
+ void testSet(var expect) {
+ testIterable(expect);
+ Set set = new Set();
+ expect.add(val).equals.add(val);
+ expect.addAll([val]).equals.addAll([val]);
+ expect.clear().equals.clear();
+ expect.containsAll([val]).equals.containsAll([val]);
+ expect.difference(set).equals.difference(set);
+ expect.intersection(set).equals.intersection(set);
+ expect.remove(val).equals.remove(val);
+ expect.removeAll([val]).equals.removeAll([val]);
+ expect.removeWhere(func1).equals.removeWhere(func1);
+ expect.retainAll([val]).equals.retainAll([val]);
+ expect.retainWhere(func1).equals.retainWhere(func1);
+ expect.union(set).equals.union(set);
+ }
+
+ void testQueue(var expect) {
+ testIterable(expect);
+ expect.add(val).equals.add(val);
+ expect.addAll([val]).equals.addAll([val]);
+ expect.addFirst(val).equals.addFirst(val);
+ expect.addLast(val).equals.addLast(val);
+ expect.clear().equals.clear();
+ expect.remove(val).equals.remove(val);
+ expect.removeFirst().equals.removeFirst();
+ expect.removeLast().equals.removeLast();
+ }
+
+ void testMap(var expect) {
+ Map map = new Map();
+ expect[val].equals[val];
+ (expect..[val] = val).equals[val] = val;
+ expect.addAll(map).equals.addAll(map);
+ expect.clear().equals.clear();
+ expect.containsKey(val).equals.containsKey(val);
+ expect.containsValue(val).equals.containsValue(val);
+ expect.forEach(func2).equals.forEach(func2);
+ expect.isEmpty.equals.isEmpty;
+ expect.isNotEmpty.equals.isNotEmpty;
+ expect.keys.equals.keys;
+ expect.length.equals.length;
+ expect.putIfAbsent(val, func0).equals.putIfAbsent(val, func0);
+ expect.remove(val).equals.remove(val);
+ expect.values.equals.values;
+ }
+
+ test("Iterable", () {
+ testIterable(new IterableExpector());
+ });
+
+ test("List", () {
+ testList(new ListExpector());
+ });
+
+ test("Set", () {
+ testSet(new SetExpector());
+ });
+
+ test("Queue", () {
+ testQueue(new QueueExpector());
+ });
+
+ test("Map", () {
+ testMap(new MapExpector());
+ });
+}
