Modernize the package's style.
This moves the package to new-style doc comments, deprecates separate
top-level libraries, and removes library tags.
There's more that could be done, but this fixes most of the low-hanging
fruit.
R=lrn@google.com
Review URL: https://codereview.chromium.org//1638163002 .
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 13b41f8..1ab3393 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -3,6 +3,9 @@
* Add a `new PriorityQueue()` constructor that forwards to `new
HeapPriorityQueue()`.
+* Deprecate top-level libraries other than `package:collection/collection.dart`,
+ which exports these libraries' interfaces.
+
## 1.3.0
* Add `lowerBound` to binary search for values that might not be present.
diff --git a/README.md b/README.md
index 8772e65..a7985fa 100644
--- a/README.md
+++ b/README.md
@@ -1,47 +1,26 @@
-Contains a number 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:
-
-```dart
-import 'package:collection/algorithms.dart';
-import 'package:collection/equality.dart';
-import 'package:collection/iterable_zip.dart';
-import 'package:collection/priority_queue.dart';
-import 'package:collection/wrappers.dart';
-```
-
-or
-
-```dart
-import 'package:collection/collection.dart';
-```
+Contains utility functions and classes in the style of `dart:collection` to make
+working with collections easier.
## Algorithms
-The algorithms library contains functions that operate on lists.
+The package contains functions that operate on lists.
It contains ways to shuffle a `List`, do binary search on a sorted `List`, and
various sorting algorithms.
-
## Equality
-The equality library gives a way to specify equality of elements and
-collections.
+The package provides a way to specify the 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
+The `Equality` interface 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:
+Equalities are provided for `Iterable`s, `List`s, `Set`s, and `Map`s, as well as
+combinations of these, such as:
```dart
const MapEquality(const IdentityEquality(), const ListEquality());
@@ -50,20 +29,17 @@
This equality considers maps equal if they have identical keys, and the
corresponding values are lists with equal (`operator==`) values.
-
## Iterable Zip
Utilities for "zipping" a list of iterables into an iterable of lists.
-
## Priority Queue
An interface and implementation of a priority queue.
-
## Wrappers
-The wrappers library contains classes that "wrap" a collection.
+The package 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.
diff --git a/lib/algorithms.dart b/lib/algorithms.dart
index 80f0107..4d3ae8b 100644
--- a/lib/algorithms.dart
+++ b/lib/algorithms.dart
@@ -2,347 +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.
-/**
- * Operations on collections.
- */
+/// Import `collection.dart` instead.
+@Deprecated("Will be removed in collection 2.0.0.")
library dart.pkg.collection.algorithms;
-import "dart:math" show Random;
-
-/** Version of [binarySearch] optimized for comparable keys */
-int _comparableBinarySearch(List<Comparable> list, Comparable value) {
- int min = 0;
- int max = list.length;
- while (min < max) {
- int mid = min + ((max - min) >> 1);
- var element = list[mid];
- int comp = element.compareTo(value);
- if (comp == 0) return mid;
- if (comp < 0) {
- min = mid + 1;
- } else {
- max = mid;
- }
- }
- return -1;
-}
-
-/**
- * Returns a position of the [value] 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 [value] is not in the list by default.
- */
-int binarySearch(List sortedList, value, { int compare(a, b) }) {
- if (compare == null) {
- return _comparableBinarySearch(sortedList, value);
- }
- int min = 0;
- int max = sortedList.length;
- while (min < max) {
- int mid = min + ((max - min) >> 1);
- var element = sortedList[mid];
- int comp = compare(element, value);
- if (comp == 0) return mid;
- if (comp < 0) {
- min = mid + 1;
- } else {
- max = mid;
- }
- }
- return -1;
-}
-
-/** Version of [lowerBound] optimized for comparable keys */
-int _comparableLowerBound(List<Comparable> list, Comparable value) {
- int min = 0;
- int max = list.length;
- while (min < max) {
- int mid = min + ((max - min) >> 1);
- var element = list[mid];
- int comp = element.compareTo(value);
- if (comp < 0) {
- min = mid + 1;
- } else {
- max = mid;
- }
- }
- return min;
-}
-
-/**
- * Returns the first position in [sortedList] that does not compare less than
- * [value].
- *
- * 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 [sortedList.length] if all the items in [sortedList] compare less
- * than [value].
- */
-int lowerBound(List sortedList, value, { int compare(a, b) }) {
- if (compare == null) {
- return _comparableLowerBound(sortedList, value);
- }
- int min = 0;
- int max = sortedList.length;
- while (min < max) {
- int mid = min + ((max - min) >> 1);
- var element = sortedList[mid];
- int comp = compare(element, value);
- if (comp < 0) {
- min = mid + 1;
- } else {
- max = mid;
- }
- }
- return min;
-}
-
-/**
- * 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);
-}
+export "src/algorithms.dart";
diff --git a/lib/collection.dart b/lib/collection.dart
index 6d451b8..b2c7e73 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -2,26 +2,12 @@
// 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.
- * - `priority_queue.dart`: Priority queue type and implementations.
- * - `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 "priority_queue.dart";
+export "src/algorithms.dart";
export "src/canonicalized_map.dart";
export "src/comparators.dart";
+export "src/equality.dart";
+export "src/iterable_zip.dart";
+export "src/priority_queue.dart";
export "src/queue_list.dart";
-export "wrappers.dart";
+export "src/unmodifiable_wrappers.dart";
+export "src/wrappers.dart";
diff --git a/lib/equality.dart b/lib/equality.dart
index 5911863..0f5b51d 100644
--- a/lib/equality.dart
+++ b/lib/equality.dart
@@ -2,418 +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.
-/**
- * Defines equality relations on collections.
- */
+/// Import `collection.dart` instead.
+@Deprecated("Will be removed in collection 2.0.0.")
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 important.
- *
- * 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);
-}
+export "src/equality.dart";
diff --git a/lib/iterable_zip.dart b/lib/iterable_zip.dart
index 772b07e..34e18ef 100644
--- a/lib/iterable_zip.dart
+++ b/lib/iterable_zip.dart
@@ -2,58 +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.
-/**
- * Zipping multiple iterables into one iterable of tuples of values.
- */
+/// Import `collection.dart` instead.
+@Deprecated("Will be removed in collection 2.0.0.")
library dart.pkg.collection.iterable_zip;
-import "dart:collection" show IterableBase;
-
-/**
- * Iterable that iterates over lists of values from other iterables.
- *
- * When [iterator] is read, an [Iterator] is created for each [Iterable] in
- * the [Iterable] passed to the constructor.
- *
- * As long as all these iterators have a next value, those next values are
- * combined into a single list, which becomes the next value of this
- * [Iterable]'s [Iterator]. As soon as any of the iterators run out,
- * the zipped iterator also stops.
- */
-class IterableZip extends IterableBase<List> {
- final Iterable<Iterable> _iterables;
- IterableZip(Iterable<Iterable> iterables)
- : this._iterables = iterables;
-
- /**
- * Returns an iterator that combines values of the iterables' iterators
- * as long as they all have values.
- */
- Iterator<List> get iterator {
- List iterators = _iterables.map((x) => x.iterator).toList(growable: false);
- // TODO(lrn): Return an empty iterator directly if iterators is empty?
- return new _IteratorZip(iterators);
- }
-}
-
-class _IteratorZip implements Iterator<List> {
- final List<Iterator> _iterators;
- List _current;
- _IteratorZip(List iterators) : _iterators = iterators;
- bool moveNext() {
- if (_iterators.isEmpty) return false;
- for (int i = 0; i < _iterators.length; i++) {
- if (!_iterators[i].moveNext()) {
- _current = null;
- return false;
- }
- }
- _current = new List(_iterators.length);
- for (int i = 0; i < _iterators.length; i++) {
- _current[i] = _iterators[i].current;
- }
- return true;
- }
-
- List get current => _current;
-}
+export "src/iterable_zip.dart";
diff --git a/lib/priority_queue.dart b/lib/priority_queue.dart
index 6272445..f2a4703 100644
--- a/lib/priority_queue.dart
+++ b/lib/priority_queue.dart
@@ -2,408 +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.
+/// Import `collection.dart` instead.
+@Deprecated("Will be removed in collection 2.0.0.")
library dart.pkg.collection.priority_queue;
-import "dart:collection" show SplayTreeSet;
-
-/**
- * A priority queue is a priority based work-list of elements.
- *
- * The queue allows adding elements, and removing them again in priority order.
- */
-abstract class PriorityQueue<E> {
- /**
- * Creates an empty [PriorityQueue].
- *
- * The created [PriorityQueue] is a plain [HeapPriorityQueue].
- *
- * The [comparison] is a [Comparator] used to compare the priority of
- * elements. An element that compares as less than another element has
- * a higher priority.
- *
- * If [comparison] is omitted, it defaults to [Comparable.compare].
- */
- factory PriorityQueue([int comparison(E e1, E e2)]) = HeapPriorityQueue<E>;
-
- /**
- * Number of elements in the queue.
- */
- int get length;
-
- /**
- * Whether the queue is empty.
- */
- bool get isEmpty;
-
- /**
- * Whether the queue has any elements.
- */
- bool get isNotEmpty;
-
- /**
- * Checks if [object] is in the queue.
- *
- * Returns true if the element is found.
- */
- bool contains(E object);
-
- /**
- * Adds element to the queue.
- *
- * The element will become the next to be removed by [removeFirst]
- * when all elements with higher priority have been removed.
- */
- void add(E element);
-
- /**
- * Adds all [elements] to the queue.
- */
- void addAll(Iterable<E> elements);
-
- /**
- * Returns the next element that will be returned by [removeFirst].
- *
- * The element is not removed from the queue.
- *
- * The queue must not be empty when this method is called.
- */
- E get first;
-
- /**
- * Removes and returns the element with the highest priority.
- *
- * Repeatedly calling this method, without adding element in between,
- * is guaranteed to return elements in non-decreasing order as, specified by
- * [comparison].
- *
- * The queue must not be empty when this method is called.
- */
- E removeFirst();
-
- /**
- * Removes an element that compares equal to [element] in the queue.
- *
- * Returns true if an element is found and removed,
- * and false if no equal element is found.
- */
- bool remove(E element);
-
- /**
- * Removes all the elements from this queue and returns them.
- *
- * The returned iterable has no specified order.
- */
- Iterable<E> removeAll();
-
- /**
- * Removes all the elements from this queue.
- */
- void clear();
-
- /**
- * Returns a list of the elements of this queue in priority order.
- *
- * The queue is not modified.
- *
- * The order is the order that the elements would be in if they were
- * removed from this queue using [removeFirst].
- */
- List<E> toList();
-
- /**
- * Return a comparator based set using the comparator of this queue.
- *
- * The queue is not modified.
- *
- * The returned [Set] is currently a [SplayTreeSet],
- * but this may change as other ordered sets are implemented.
- *
- * The set contains all the elements of this queue.
- * If an element occurs more than once in the queue,
- * the set will contain it only once.
- */
- Set<E> toSet();
-}
-
-/**
- * Heap based priority queue.
- *
- * The elements are kept in a heap structure,
- * where the element with the highest priority is immediately accessible,
- * and modifying a single element takes
- * logarithmic time in the number of elements on average.
- *
- * * The [add] and [removeFirst] operations take amortized logarithmic time,
- * O(log(n)), but may occasionally take linear time when growing the capacity
- * of the heap.
- * * The [addAll] operation works as doing repeated [add] operations.
- * * The [first] getter takes constant time, O(1).
- * * The [clear] and [removeAll] methods also take constant time, O(1).
- * * The [contains] and [remove] operations may need to search the entire
- * queue for the elements, taking O(n) time.
- * * The [toList] operation effectively sorts the elements, taking O(n*log(n))
- * time.
- * * The [toSet] operation effectively adds each element to the new set, taking
- * an expected O(n*log(n)) time.
- */
-class HeapPriorityQueue<E> implements PriorityQueue<E> {
- /**
- * Initial capacity of a queue when created, or when added to after a [clear].
- *
- * Number can be any positive value. Picking a size that gives a whole
- * number of "tree levels" in the heap is only done for aesthetic reasons.
- */
- static const int _INITIAL_CAPACITY = 7;
-
- /**
- * The comparison being used to compare the priority of elements.
- */
- final Comparator comparison;
-
- /**
- * List implementation of a heap.
- */
- List<E> _queue = new List<E>(_INITIAL_CAPACITY);
-
- /**
- * Number of elements in queue.
- *
- * The heap is implemented in the first [_length] entries of [_queue].
- */
- int _length = 0;
-
- /**
- * Create a new priority queue.
- *
- * The [comparison] is a [Comparator] used to compare the priority of
- * elements. An element that compares as less than another element has
- * a higher priority.
- *
- * If [comparison] is omitted, it defaults to [Comparable.compare].
- */
- HeapPriorityQueue([int comparison(E e1, E e2)])
- : comparison = (comparison != null) ? comparison : Comparable.compare;
-
- void add(E element) {
- _add(element);
- }
-
- void addAll(Iterable<E> elements) {
- for (E element in elements) {
- _add(element);
- }
- }
-
- void clear() {
- _queue = const [];
- _length = 0;
- }
-
- bool contains(E object) {
- return _locate(object) >= 0;
- }
-
- E get first {
- if (_length == 0) throw new StateError("No such element");
- return _queue[0];
- }
-
- bool get isEmpty => _length == 0;
-
- bool get isNotEmpty => _length != 0;
-
- int get length => _length;
-
- bool remove(E element) {
- int index = _locate(element);
- if (index < 0) return false;
- E last = _removeLast();
- if (index < _length) {
- int comp = comparison(last, element);
- if (comp <= 0) {
- _bubbleUp(last, index);
- } else {
- _bubbleDown(last, index);
- }
- }
- return true;
- }
-
- Iterable<E> removeAll() {
- List<E> result = _queue;
- int length = _length;
- _queue = const [];
- _length = 0;
- return result.take(length);
- }
-
- E removeFirst() {
- if (_length == 0) throw new StateError("No such element");
- E result = _queue[0];
- E last = _removeLast();
- if (_length > 0) {
- _bubbleDown(last, 0);
- }
- return result;
- }
-
- List<E> toList() {
- List<E> list = new List<E>()..length = _length;
- list.setRange(0, _length, _queue);
- list.sort(comparison);
- return list;
- }
-
- Set<E> toSet() {
- Set<E> set = new SplayTreeSet<E>(comparison);
- for (int i = 0; i < _length; i++) {
- set.add(_queue[i]);
- }
- return set;
- }
-
- /**
- * Returns some representation of the queue.
- *
- * The format isn't significant, and may change in the future.
- */
- String toString() {
- return _queue.take(_length).toString();
- }
-
- /**
- * Add element to the queue.
- *
- * Grows the capacity if the backing list is full.
- */
- void _add(E element) {
- if (_length == _queue.length) _grow();
- _bubbleUp(element, _length++);
- }
-
- /**
- * Find the index of an object in the heap.
- *
- * Returns -1 if the object is not found.
- */
- int _locate(E object) {
- if (_length == 0) return -1;
- // Count positions from one instead of zero. This gives the numbers
- // some nice properties. For example, all right children are odd,
- // their left sibling is even, and the parent is found by shifting
- // right by one.
- // Valid range for position is [1.._length], inclusive.
- int position = 1;
- // Pre-order depth first search, omit child nodes if the current
- // node has lower priority than [object], because all nodes lower
- // in the heap will also have lower priority.
- do {
- int index = position - 1;
- E element = _queue[index];
- int comp = comparison(element, object);
- if (comp == 0) return index;
- if (comp < 0) {
- // Element may be in subtree.
- // Continue with the left child, if it is there.
- int leftChildPosition = position * 2;
- if (leftChildPosition <= _length) {
- position = leftChildPosition;
- continue;
- }
- }
- // Find the next right sibling or right ancestor sibling.
- do {
- while (position.isOdd) {
- // While position is a right child, go to the parent.
- position >>= 1;
- }
- // Then go to the right sibling of the left-child.
- position += 1;
- } while (position > _length); // Happens if last element is a left child.
- } while (position != 1); // At root again. Happens for right-most element.
- return -1;
- }
-
- E _removeLast() {
- int newLength = _length - 1;
- E last = _queue[newLength];
- _queue[newLength] = null;
- _length = newLength;
- return last;
- }
-
- /**
- * Place [element] in heap at [index] or above.
- *
- * Put element into the empty cell at `index`.
- * While the `element` has higher priority than the
- * parent, swap it with the parent.
- */
- void _bubbleUp(E element, int index) {
- while (index > 0) {
- int parentIndex = (index - 1) ~/ 2;
- E parent = _queue[parentIndex];
- if (comparison(element, parent) > 0) break;
- _queue[index] = parent;
- index = parentIndex;
- }
- _queue[index] = element;
- }
-
- /**
- * Place [element] in heap at [index] or above.
- *
- * Put element into the empty cell at `index`.
- * While the `element` has lower priority than either child,
- * swap it with the highest priority child.
- */
- void _bubbleDown(E element, int index) {
- int rightChildIndex = index * 2 + 2;
- while (rightChildIndex < _length) {
- int leftChildIndex = rightChildIndex - 1;
- E leftChild = _queue[leftChildIndex];
- E rightChild = _queue[rightChildIndex];
- int comp = comparison(leftChild, rightChild);
- int minChildIndex;
- E minChild;
- if (comp < 0) {
- minChild = leftChild;
- minChildIndex = leftChildIndex;
- } else {
- minChild = rightChild;
- minChildIndex = rightChildIndex;
- }
- comp = comparison(element, minChild);
- if (comp <= 0) {
- _queue[index] = element;
- return;
- }
- _queue[index] = minChild;
- index = minChildIndex;
- rightChildIndex = index * 2 + 2;
- }
- int leftChildIndex = rightChildIndex - 1;
- if (leftChildIndex < _length) {
- E child = _queue[leftChildIndex];
- int comp = comparison(element, child);
- if (comp > 0) {
- _queue[index] = child;
- index = leftChildIndex;
- }
- }
- _queue[index] = element;
- }
-
- /**
- * Grows the capacity of the list holding the heap.
- *
- * Called when the list is full.
- */
- void _grow() {
- int newCapacity = _queue.length * 2 + 1;
- if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY;
- List<E> newQueue = new List<E>(newCapacity);
- newQueue.setRange(0, _length, _queue);
- _queue = newQueue;
- }
-}
+export "src/priority_queue.dart";
diff --git a/lib/src/algorithms.dart b/lib/src/algorithms.dart
new file mode 100644
index 0000000..2b66d7d
--- /dev/null
+++ b/lib/src/algorithms.dart
@@ -0,0 +1,323 @@
+// 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 "dart:math" as math;
+
+/// Version of [binarySearch] optimized for comparable keys
+int _comparableBinarySearch(List<Comparable> list, Comparable value) {
+ int min = 0;
+ int max = list.length;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ var element = list[mid];
+ int comp = element.compareTo(value);
+ if (comp == 0) return mid;
+ if (comp < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ return -1;
+}
+
+/// Returns a position of the [value] 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 [value] is not in the list by default.
+int binarySearch(List sortedList, value, { int compare(a, b) }) {
+ if (compare == null) {
+ return _comparableBinarySearch(sortedList, value);
+ }
+ int min = 0;
+ int max = sortedList.length;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ var element = sortedList[mid];
+ int comp = compare(element, value);
+ if (comp == 0) return mid;
+ if (comp < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ return -1;
+}
+
+/// Version of [lowerBound] optimized for comparable keys
+int _comparableLowerBound(List<Comparable> list, Comparable value) {
+ int min = 0;
+ int max = list.length;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ var element = list[mid];
+ int comp = element.compareTo(value);
+ if (comp < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ return min;
+}
+
+/// Returns the first position in [sortedList] that does not compare less than
+/// [value].
+///
+/// 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 [sortedList.length] if all the items in [sortedList] compare less
+/// than [value].
+int lowerBound(List sortedList, value, { int compare(a, b) }) {
+ if (compare == null) {
+ return _comparableLowerBound(sortedList, value);
+ }
+ int min = 0;
+ int max = sortedList.length;
+ while (min < max) {
+ int mid = min + ((max - min) >> 1);
+ var element = sortedList[mid];
+ int comp = compare(element, value);
+ if (comp < 0) {
+ min = mid + 1;
+ } else {
+ max = mid;
+ }
+ }
+ return min;
+}
+
+/// 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]) {
+ var random = new math.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/src/canonicalized_map.dart b/lib/src/canonicalized_map.dart
index 21fb83d..d967f70 100644
--- a/lib/src/canonicalized_map.dart
+++ b/lib/src/canonicalized_map.dart
@@ -2,22 +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.
-library dart.pkg.collection.canonicalized_map;
-
import 'dart:collection';
import 'utils.dart';
-/**
- * A map whose keys are converted to canonical values of type `C`.
- *
- * This is useful for using case-insensitive String keys, for example. It's more
- * efficient than a [LinkedHashMap] with a custom equality operator because it
- * only canonicalizes each key once, rather than doing so for each comparison.
- *
- * By default, `null` is allowed as a key. It can be forbidden via the
- * `isValidKey` parameter.
- */
+/// A map whose keys are converted to canonical values of type `C`.
+///
+/// This is useful for using case-insensitive String keys, for example. It's
+/// more efficient than a [LinkedHashMap] with a custom equality operator
+/// because it only canonicalizes each key once, rather than doing so for each
+/// comparison.
+///
+/// By default, `null` is allowed as a key. It can be forbidden via the
+/// `isValidKey` parameter.
class CanonicalizedMap<C, K, V> implements Map<K, V> {
final Function _canonicalize;
@@ -25,31 +22,27 @@
final _base = new Map<C, Pair<K, V>>();
- /**
- * Creates an empty canonicalized map.
- *
- * The [canonicalize] function should return the canonical value for the given
- * key. Keys with the same canonical value are considered equivalent.
- *
- * The [isValidKey] function is called before calling [canonicalize] for
- * methods that take arbitrary objects. It can be used to filter out keys that
- * can't be canonicalized.
- */
+ /// Creates an empty canonicalized map.
+ ///
+ /// The [canonicalize] function should return the canonical value for the
+ /// given key. Keys with the same canonical value are considered equivalent.
+ ///
+ /// The [isValidKey] function is called before calling [canonicalize] for
+ /// methods that take arbitrary objects. It can be used to filter out keys
+ /// that can't be canonicalized.
CanonicalizedMap(C canonicalize(K key), {bool isValidKey(Object key)})
: _canonicalize = canonicalize,
_isValidKeyFn = isValidKey;
- /**
- * Creates a canonicalized map that is initialized with the key/value pairs of
- * [other].
- *
- * The [canonicalize] function should return the canonical value for the given
- * key. Keys with the same canonical value are considered equivalent.
- *
- * The [isValidKey] function is called before calling [canonicalize] for
- * methods that take arbitrary objects. It can be used to filter out keys that
- * can't be canonicalized.
- */
+ /// Creates a canonicalized map that is initialized with the key/value pairs
+ /// of [other].
+ ///
+ /// The [canonicalize] function should return the canonical value for the
+ /// given key. Keys with the same canonical value are considered equivalent.
+ ///
+ /// The [isValidKey] function is called before calling [canonicalize] for
+ /// methods that take arbitrary objects. It can be used to filter out keys
+ /// that can't be canonicalized.
CanonicalizedMap.from(Map<K, V> other, C canonicalize(K key),
{bool isValidKey(Object key)})
: _canonicalize = canonicalize,
diff --git a/lib/src/comparators.dart b/lib/src/comparators.dart
index 05615ba..4995100 100644
--- a/lib/src/comparators.dart
+++ b/lib/src/comparators.dart
@@ -2,8 +2,6 @@
// 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.
-library dart.pkg.collection.comparators;
-
// Character constants.
const int _zero = 0x30;
const int _upperCaseA = 0x41;
diff --git a/lib/src/equality.dart b/lib/src/equality.dart
new file mode 100644
index 0000000..5a0d074
--- /dev/null
+++ b/lib/src/equality.dart
@@ -0,0 +1,384 @@
+// 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 "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 important.
+///
+/// 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/iterable_zip.dart b/lib/src/iterable_zip.dart
new file mode 100644
index 0000000..30acb0e
--- /dev/null
+++ b/lib/src/iterable_zip.dart
@@ -0,0 +1,50 @@
+// 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 "dart:collection";
+
+/// Iterable that iterates over lists of values from other iterables.
+///
+/// When [iterator] is read, an [Iterator] is created for each [Iterable] in
+/// the [Iterable] passed to the constructor.
+///
+/// As long as all these iterators have a next value, those next values are
+/// combined into a single list, which becomes the next value of this
+/// [Iterable]'s [Iterator]. As soon as any of the iterators run out,
+/// the zipped iterator also stops.
+class IterableZip extends IterableBase<List> {
+ final Iterable<Iterable> _iterables;
+ IterableZip(Iterable<Iterable> iterables)
+ : this._iterables = iterables;
+
+ /// Returns an iterator that combines values of the iterables' iterators
+ /// as long as they all have values.
+ Iterator<List> get iterator {
+ List iterators = _iterables.map((x) => x.iterator).toList(growable: false);
+ // TODO(lrn): Return an empty iterator directly if iterators is empty?
+ return new _IteratorZip(iterators);
+ }
+}
+
+class _IteratorZip implements Iterator<List> {
+ final List<Iterator> _iterators;
+ List _current;
+ _IteratorZip(List iterators) : _iterators = iterators;
+ bool moveNext() {
+ if (_iterators.isEmpty) return false;
+ for (int i = 0; i < _iterators.length; i++) {
+ if (!_iterators[i].moveNext()) {
+ _current = null;
+ return false;
+ }
+ }
+ _current = new List(_iterators.length);
+ for (int i = 0; i < _iterators.length; i++) {
+ _current[i] = _iterators[i].current;
+ }
+ return true;
+ }
+
+ List get current => _current;
+}
diff --git a/lib/src/priority_queue.dart b/lib/src/priority_queue.dart
new file mode 100644
index 0000000..64fd84f
--- /dev/null
+++ b/lib/src/priority_queue.dart
@@ -0,0 +1,354 @@
+// Copyright (c) 2014, 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:collection";
+
+/// A priority queue is a priority based work-list of elements.
+///
+/// The queue allows adding elements, and removing them again in priority order.
+abstract class PriorityQueue<E> {
+ /// Creates an empty [PriorityQueue].
+ ///
+ /// The created [PriorityQueue] is a plain [HeapPriorityQueue].
+ ///
+ /// The [comparison] is a [Comparator] used to compare the priority of
+ /// elements. An element that compares as less than another element has
+ /// a higher priority.
+ ///
+ /// If [comparison] is omitted, it defaults to [Comparable.compare].
+ factory PriorityQueue([int comparison(E e1, E e2)]) = HeapPriorityQueue<E>;
+
+ /// Number of elements in the queue.
+ int get length;
+
+ /// Whether the queue is empty.
+ bool get isEmpty;
+
+ /// Whether the queue has any elements.
+ bool get isNotEmpty;
+
+ /// Checks if [object] is in the queue.
+ ///
+ /// Returns true if the element is found.
+ bool contains(E object);
+
+ /// Adds element to the queue.
+ ///
+ /// The element will become the next to be removed by [removeFirst]
+ /// when all elements with higher priority have been removed.
+ void add(E element);
+
+ /// Adds all [elements] to the queue.
+ void addAll(Iterable<E> elements);
+
+ /// Returns the next element that will be returned by [removeFirst].
+ ///
+ /// The element is not removed from the queue.
+ ///
+ /// The queue must not be empty when this method is called.
+ E get first;
+
+ /// Removes and returns the element with the highest priority.
+ ///
+ /// Repeatedly calling this method, without adding element in between,
+ /// is guaranteed to return elements in non-decreasing order as, specified by
+ /// [comparison].
+ ///
+ /// The queue must not be empty when this method is called.
+ E removeFirst();
+
+ /// Removes an element that compares equal to [element] in the queue.
+ ///
+ /// Returns true if an element is found and removed,
+ /// and false if no equal element is found.
+ bool remove(E element);
+
+ /// Removes all the elements from this queue and returns them.
+ ///
+ /// The returned iterable has no specified order.
+ Iterable<E> removeAll();
+
+ /// Removes all the elements from this queue.
+ void clear();
+
+ /// Returns a list of the elements of this queue in priority order.
+ ///
+ /// The queue is not modified.
+ ///
+ /// The order is the order that the elements would be in if they were
+ /// removed from this queue using [removeFirst].
+ List<E> toList();
+
+ /// Return a comparator based set using the comparator of this queue.
+ ///
+ /// The queue is not modified.
+ ///
+ /// The returned [Set] is currently a [SplayTreeSet],
+ /// but this may change as other ordered sets are implemented.
+ ///
+ /// The set contains all the elements of this queue.
+ /// If an element occurs more than once in the queue,
+ /// the set will contain it only once.
+ Set<E> toSet();
+}
+
+/// Heap based priority queue.
+///
+/// The elements are kept in a heap structure,
+/// where the element with the highest priority is immediately accessible,
+/// and modifying a single element takes
+/// logarithmic time in the number of elements on average.
+///
+/// * The [add] and [removeFirst] operations take amortized logarithmic time,
+/// O(log(n)), but may occasionally take linear time when growing the capacity
+/// of the heap.
+/// * The [addAll] operation works as doing repeated [add] operations.
+/// * The [first] getter takes constant time, O(1).
+/// * The [clear] and [removeAll] methods also take constant time, O(1).
+/// * The [contains] and [remove] operations may need to search the entire
+/// queue for the elements, taking O(n) time.
+/// * The [toList] operation effectively sorts the elements, taking O(n*log(n))
+/// time.
+/// * The [toSet] operation effectively adds each element to the new set, taking
+/// an expected O(n*log(n)) time.
+class HeapPriorityQueue<E> implements PriorityQueue<E> {
+ /// Initial capacity of a queue when created, or when added to after a
+ /// [clear].
+ ///
+ /// Number can be any positive value. Picking a size that gives a whole
+ /// number of "tree levels" in the heap is only done for aesthetic reasons.
+ static const int _INITIAL_CAPACITY = 7;
+
+ /// The comparison being used to compare the priority of elements.
+ final Comparator comparison;
+
+ /// List implementation of a heap.
+ List<E> _queue = new List<E>(_INITIAL_CAPACITY);
+
+ /// Number of elements in queue.
+ ///
+ /// The heap is implemented in the first [_length] entries of [_queue].
+ int _length = 0;
+
+ /// Create a new priority queue.
+ ///
+ /// The [comparison] is a [Comparator] used to compare the priority of
+ /// elements. An element that compares as less than another element has
+ /// a higher priority.
+ ///
+ /// If [comparison] is omitted, it defaults to [Comparable.compare].
+ HeapPriorityQueue([int comparison(E e1, E e2)])
+ : comparison = (comparison != null) ? comparison : Comparable.compare;
+
+ void add(E element) {
+ _add(element);
+ }
+
+ void addAll(Iterable<E> elements) {
+ for (E element in elements) {
+ _add(element);
+ }
+ }
+
+ void clear() {
+ _queue = const [];
+ _length = 0;
+ }
+
+ bool contains(E object) {
+ return _locate(object) >= 0;
+ }
+
+ E get first {
+ if (_length == 0) throw new StateError("No such element");
+ return _queue[0];
+ }
+
+ bool get isEmpty => _length == 0;
+
+ bool get isNotEmpty => _length != 0;
+
+ int get length => _length;
+
+ bool remove(E element) {
+ int index = _locate(element);
+ if (index < 0) return false;
+ E last = _removeLast();
+ if (index < _length) {
+ int comp = comparison(last, element);
+ if (comp <= 0) {
+ _bubbleUp(last, index);
+ } else {
+ _bubbleDown(last, index);
+ }
+ }
+ return true;
+ }
+
+ Iterable<E> removeAll() {
+ List<E> result = _queue;
+ int length = _length;
+ _queue = const [];
+ _length = 0;
+ return result.take(length);
+ }
+
+ E removeFirst() {
+ if (_length == 0) throw new StateError("No such element");
+ E result = _queue[0];
+ E last = _removeLast();
+ if (_length > 0) {
+ _bubbleDown(last, 0);
+ }
+ return result;
+ }
+
+ List<E> toList() {
+ List<E> list = new List<E>()..length = _length;
+ list.setRange(0, _length, _queue);
+ list.sort(comparison);
+ return list;
+ }
+
+ Set<E> toSet() {
+ Set<E> set = new SplayTreeSet<E>(comparison);
+ for (int i = 0; i < _length; i++) {
+ set.add(_queue[i]);
+ }
+ return set;
+ }
+
+ /// Returns some representation of the queue.
+ ///
+ /// The format isn't significant, and may change in the future.
+ String toString() {
+ return _queue.take(_length).toString();
+ }
+
+ /// Add element to the queue.
+ ///
+ /// Grows the capacity if the backing list is full.
+ void _add(E element) {
+ if (_length == _queue.length) _grow();
+ _bubbleUp(element, _length++);
+ }
+
+ /// Find the index of an object in the heap.
+ ///
+ /// Returns -1 if the object is not found.
+ int _locate(E object) {
+ if (_length == 0) return -1;
+ // Count positions from one instead of zero. This gives the numbers
+ // some nice properties. For example, all right children are odd,
+ // their left sibling is even, and the parent is found by shifting
+ // right by one.
+ // Valid range for position is [1.._length], inclusive.
+ int position = 1;
+ // Pre-order depth first search, omit child nodes if the current
+ // node has lower priority than [object], because all nodes lower
+ // in the heap will also have lower priority.
+ do {
+ int index = position - 1;
+ E element = _queue[index];
+ int comp = comparison(element, object);
+ if (comp == 0) return index;
+ if (comp < 0) {
+ // Element may be in subtree.
+ // Continue with the left child, if it is there.
+ int leftChildPosition = position * 2;
+ if (leftChildPosition <= _length) {
+ position = leftChildPosition;
+ continue;
+ }
+ }
+ // Find the next right sibling or right ancestor sibling.
+ do {
+ while (position.isOdd) {
+ // While position is a right child, go to the parent.
+ position >>= 1;
+ }
+ // Then go to the right sibling of the left-child.
+ position += 1;
+ } while (position > _length); // Happens if last element is a left child.
+ } while (position != 1); // At root again. Happens for right-most element.
+ return -1;
+ }
+
+ E _removeLast() {
+ int newLength = _length - 1;
+ E last = _queue[newLength];
+ _queue[newLength] = null;
+ _length = newLength;
+ return last;
+ }
+
+ /// Place [element] in heap at [index] or above.
+ ///
+ /// Put element into the empty cell at `index`.
+ /// While the `element` has higher priority than the
+ /// parent, swap it with the parent.
+ void _bubbleUp(E element, int index) {
+ while (index > 0) {
+ int parentIndex = (index - 1) ~/ 2;
+ E parent = _queue[parentIndex];
+ if (comparison(element, parent) > 0) break;
+ _queue[index] = parent;
+ index = parentIndex;
+ }
+ _queue[index] = element;
+ }
+
+ /// Place [element] in heap at [index] or above.
+ ///
+ /// Put element into the empty cell at `index`.
+ /// While the `element` has lower priority than either child,
+ /// swap it with the highest priority child.
+ void _bubbleDown(E element, int index) {
+ int rightChildIndex = index * 2 + 2;
+ while (rightChildIndex < _length) {
+ int leftChildIndex = rightChildIndex - 1;
+ E leftChild = _queue[leftChildIndex];
+ E rightChild = _queue[rightChildIndex];
+ int comp = comparison(leftChild, rightChild);
+ int minChildIndex;
+ E minChild;
+ if (comp < 0) {
+ minChild = leftChild;
+ minChildIndex = leftChildIndex;
+ } else {
+ minChild = rightChild;
+ minChildIndex = rightChildIndex;
+ }
+ comp = comparison(element, minChild);
+ if (comp <= 0) {
+ _queue[index] = element;
+ return;
+ }
+ _queue[index] = minChild;
+ index = minChildIndex;
+ rightChildIndex = index * 2 + 2;
+ }
+ int leftChildIndex = rightChildIndex - 1;
+ if (leftChildIndex < _length) {
+ E child = _queue[leftChildIndex];
+ int comp = comparison(element, child);
+ if (comp > 0) {
+ _queue[index] = child;
+ index = leftChildIndex;
+ }
+ }
+ _queue[index] = element;
+ }
+
+ /// Grows the capacity of the list holding the heap.
+ ///
+ /// Called when the list is full.
+ void _grow() {
+ int newCapacity = _queue.length * 2 + 1;
+ if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY;
+ List<E> newQueue = new List<E>(newCapacity);
+ newQueue.setRange(0, _length, _queue);
+ _queue = newQueue;
+ }
+}
diff --git a/lib/src/queue_list.dart b/lib/src/queue_list.dart
index 0ef888f..a12f0b4 100644
--- a/lib/src/queue_list.dart
+++ b/lib/src/queue_list.dart
@@ -4,9 +4,7 @@
import 'dart:collection';
-/**
- * A class that efficiently implements both [Queue] and [List].
- */
+/// A class that efficiently implements both [Queue] and [List].
// TODO(nweiz): Currently this code is copied almost verbatim from
// dart:collection. The only changes are to implement List and to remove methods
// that are redundant with ListMixin. Remove or simplify it when issue 21330 is
@@ -17,12 +15,10 @@
int _head;
int _tail;
- /**
- * Create an empty queue.
- *
- * If [initialCapacity] is given, prepare the queue for at least that many
- * elements.
- */
+ /// Create an empty queue.
+ ///
+ /// If [initialCapacity] is given, prepare the queue for at least that many
+ /// elements.
QueueList([int initialCapacity]) : _head = 0, _tail = 0 {
if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) {
initialCapacity = _INITIAL_CAPACITY;
@@ -33,9 +29,7 @@
_table = new List<E>(initialCapacity);
}
- /**
- * Create a queue initially containing the elements of [source].
- */
+ /// Create a queue initially containing the elements of [source].
factory QueueList.from(Iterable<E> source) {
if (source is List) {
int length = source.length;
@@ -157,20 +151,16 @@
// Internal helper functions.
- /**
- * Whether [number] is a power of two.
- *
- * Only works for positive numbers.
- */
+ /// Whether [number] is a power of two.
+ ///
+ /// Only works for positive numbers.
static bool _isPowerOf2(int number) => (number & (number - 1)) == 0;
- /**
- * Rounds [number] up to the nearest power of 2.
- *
- * If [number] is a power of 2 already, it is returned.
- *
- * Only works for positive numbers.
- */
+ /// Rounds [number] up to the nearest power of 2.
+ ///
+ /// If [number] is a power of 2 already, it is returned.
+ ///
+ /// Only works for positive numbers.
static int _nextPowerOf2(int number) {
assert(number > 0);
number = (number << 1) - 1;
@@ -181,16 +171,14 @@
}
}
- /** Adds element at end of queue. Used by both [add] and [addAll]. */
+ /// Adds element at end of queue. Used by both [add] and [addAll].
void _add(E element) {
_table[_tail] = element;
_tail = (_tail + 1) & (_table.length - 1);
if (_head == _tail) _grow();
}
- /**
- * Grow the table when full.
- */
+ /// Grow the table when full.
void _grow() {
List<E> newTable = new List<E>(_table.length * 2);
int split = _table.length - _head;
@@ -215,7 +203,7 @@
}
}
- /** Grows the table even if it is not full. */
+ /// Grows the table even if it is not full.
void _preGrow(int newElementCount) {
assert(newElementCount >= length);
diff --git a/lib/src/unmodifiable_wrappers.dart b/lib/src/unmodifiable_wrappers.dart
index efe3c9d..1f78470 100644
--- a/lib/src/unmodifiable_wrappers.dart
+++ b/lib/src/unmodifiable_wrappers.dart
@@ -2,236 +2,163 @@
// 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.
- */
-library collection.unmodifiable_wrappers;
-
-import '../wrappers.dart';
-
export "dart:collection" show UnmodifiableListView, UnmodifiableMapView;
-/**
- * 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.
- */
+import 'wrappers.dart';
+
+/// 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.
- */
+/// 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 _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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+/// 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.
- */
+/// Mixin class that implements a throwing version of all set operations that
+/// change the Set.
abstract class UnmodifiableSetMixin<E> implements Set<E> {
_throw() {
throw new UnsupportedError("Cannot modify an unmodifiable Set");
}
- /**
- * Throws an [UnsupportedError];
- * operations that change the set are disallowed.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// Throws an [UnsupportedError];
+ /// operations that change the set are disallowed.
void clear() => _throw();
}
-/**
- * Mixin class that implements a throwing version of all map operations that
- * change the Map.
- */
+/// 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 _throw() {
throw new UnsupportedError("Cannot modify an unmodifiable Map");
}
- /**
- * Throws an [UnsupportedError];
- * operations that change the map are disallowed.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// 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.
- */
+ /// Throws an [UnsupportedError];
+ /// operations that change the map are disallowed.
V remove(Object key) => _throw();
- /**
- * Throws an [UnsupportedError];
- * operations that change the map are disallowed.
- */
+ /// Throws an [UnsupportedError];
+ /// operations that change the map are disallowed.
void clear() => _throw();
}
diff --git a/lib/src/utils.dart b/lib/src/utils.dart
index c9c7537..51a80b2 100644
--- a/lib/src/utils.dart
+++ b/lib/src/utils.dart
@@ -2,8 +2,6 @@
// 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.
-library dart.pkg.collection.utils;
-
/// A pair of values.
class Pair<E, F> {
E first;
diff --git a/lib/src/wrappers.dart b/lib/src/wrappers.dart
new file mode 100644
index 0000000..ee03b5f
--- /dev/null
+++ b/lib/src/wrappers.dart
@@ -0,0 +1,524 @@
+// 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 "dart:collection";
+import "dart:math" as math;
+
+import "unmodifiable_wrappers.dart";
+
+/// A base class for delegating iterables.
+///
+/// Subclasses can provide a [_base] that should be delegated to. Unlike
+/// [DelegatingIterable], this allows the base to be created on demand.
+abstract class _DelegatingIterableBase<E> implements Iterable<E> {
+ Iterable<E> get _base;
+
+ const _DelegatingIterableBase();
+
+ 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);
+
+ String toString() => _base.toString();
+}
+
+/// 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> extends _DelegatingIterableBase<E> {
+ final Iterable<E> _base;
+
+ /// Create a wrapper that forwards operations to [base].
+ const DelegatingIterable(Iterable<E> base) : _base = base;
+}
+
+
+/// 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> {
+ const 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([math.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> {
+ const 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(Object 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);
+
+ Set<E> toSet() => new DelegatingSet<E>(_setBase.toSet());
+}
+
+/// 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> {
+ const 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> {
+ final Map<K, V> _base;
+
+ const 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;
+
+ String toString() => _base.toString();
+}
+
+/// An unmodifiable [Set] view of the keys of a [Map].
+///
+/// The set delegates all operations to the underlying map.
+///
+/// A `Map` can only contain each key once, so its keys can always
+/// be viewed as a `Set` without any loss, even if the [Map.keys]
+/// getter only shows an [Iterable] view of the keys.
+///
+/// Note that [lookup] is not supported for this set.
+class MapKeySet<E> extends _DelegatingIterableBase<E>
+ with UnmodifiableSetMixin<E> {
+ final Map<E, dynamic> _baseMap;
+
+ MapKeySet(Map<E, dynamic> base) : _baseMap = base;
+
+ Iterable<E> get _base => _baseMap.keys;
+
+ bool contains(Object element) => _baseMap.containsKey(element);
+
+ bool get isEmpty => _baseMap.isEmpty;
+
+ bool get isNotEmpty => _baseMap.isNotEmpty;
+
+ int get length => _baseMap.length;
+
+ String toString() => "{${_base.join(', ')}}";
+
+ bool containsAll(Iterable<Object> other) => other.every(contains);
+
+ /// Returns a new set with the the elements of [this] that are not in [other].
+ ///
+ /// That is, the returned set contains all the elements of this [Set] that are
+ /// not elements of [other] according to `other.contains`.
+ ///
+ /// Note that the returned set will use the default equality operation, which
+ /// may be different than the equality operation [this] uses.
+ Set<E> difference(Set<E> other) =>
+ where((element) => !other.contains(element)).toSet();
+
+ /// Returns a new set which is the intersection between [this] and [other].
+ ///
+ /// That is, the returned set contains all the elements of this [Set] that are
+ /// also elements of [other] according to `other.contains`.
+ ///
+ /// Note that the returned set will use the default equality operation, which
+ /// may be different than the equality operation [this] uses.
+ Set<E> intersection(Set<Object> other) => where(other.contains).toSet();
+
+ /// Throws an [UnsupportedError] since there's no corresponding method for
+ /// [Map]s.
+ E lookup(E element) => throw new UnsupportedError(
+ "MapKeySet doesn't support lookup().");
+
+ /// Returns a new set which contains all the elements of [this] and [other].
+ ///
+ /// That is, the returned set contains all the elements of this [Set] and all
+ /// the elements of [other].
+ ///
+ /// Note that the returned set will use the default equality operation, which
+ /// may be different than the equality operation [this] uses.
+ Set<E> union(Set<E> other) => toSet()..addAll(other);
+}
+
+/// Creates a modifiable [Set] view of the values of a [Map].
+///
+/// The `Set` view assumes that the keys of the `Map` can be uniquely determined
+/// from the values. The `keyForValue` function passed to the constructor finds
+/// the key for a single value. The `keyForValue` function should be consistent
+/// with equality. If `value1 == value2` then `keyForValue(value1)` and
+/// `keyForValue(value2)` should be considered equal keys by the underlying map,
+/// and vice versa.
+///
+/// Modifying the set will modify the underlying map based on the key returned
+/// by `keyForValue`.
+///
+/// If the `Map` contents are not compatible with the `keyForValue` function,
+/// the set will not work consistently, and may give meaningless responses or do
+/// inconsistent updates.
+///
+/// This set can, for example, be used on a map from database record IDs to the
+/// records. It exposes the records as a set, and allows for writing both
+/// `recordSet.add(databaseRecord)` and `recordMap[id]`.
+///
+/// Effectively, the map will act as a kind of index for the set.
+class MapValueSet<K, V> extends _DelegatingIterableBase<V> implements Set<V> {
+ final Map<K, V> _baseMap;
+ final Function _keyForValue;
+
+ /// Creates a new [MapValueSet] based on [base].
+ ///
+ /// [keyForValue] returns the key in the map that should be associated with
+ /// the given value. The set's notion of equality is identical to the equality
+ /// of the return values of [keyForValue].
+ MapValueSet(Map<K, V> base, K keyForValue(V value))
+ : _baseMap = base,
+ _keyForValue = keyForValue;
+
+ Iterable<V> get _base => _baseMap.values;
+
+ bool contains(Object element) {
+ if (element != null && element is! V) return false;
+ return _baseMap.containsKey(_keyForValue(element));
+ }
+
+ bool get isEmpty => _baseMap.isEmpty;
+
+ bool get isNotEmpty => _baseMap.isNotEmpty;
+
+ int get length => _baseMap.length;
+
+ String toString() => toSet().toString();
+
+ bool add(V value) {
+ K key = _keyForValue(value);
+ bool result = false;
+ _baseMap.putIfAbsent(key, () {
+ result = true;
+ return value;
+ });
+ return result;
+ }
+
+ void addAll(Iterable<V> elements) => elements.forEach(add);
+
+ void clear() => _baseMap.clear();
+
+ bool containsAll(Iterable<Object> other) => other.every(contains);
+
+ /// Returns a new set with the the elements of [this] that are not in [other].
+ ///
+ /// That is, the returned set contains all the elements of this [Set] that are
+ /// not elements of [other] according to `other.contains`.
+ ///
+ /// Note that the returned set will use the default equality operation, which
+ /// may be different than the equality operation [this] uses.
+ Set<V> difference(Set<V> other) =>
+ where((element) => !other.contains(element)).toSet();
+
+ /// Returns a new set which is the intersection between [this] and [other].
+ ///
+ /// That is, the returned set contains all the elements of this [Set] that are
+ /// also elements of [other] according to `other.contains`.
+ ///
+ /// Note that the returned set will use the default equality operation, which
+ /// may be different than the equality operation [this] uses.
+ Set<V> intersection(Set<Object> other) => where(other.contains).toSet();
+
+ V lookup(Object element) => _baseMap[_keyForValue(element)];
+
+ bool remove(Object value) {
+ if (value != null && value is! V) return false;
+ var key = _keyForValue(value);
+ if (!_baseMap.containsKey(key)) return false;
+ _baseMap.remove(key);
+ return true;
+ }
+
+ void removeAll(Iterable<Object> elements) => elements.forEach(remove);
+
+ void removeWhere(bool test(V element)) {
+ var toRemove = [];
+ _baseMap.forEach((key, value) {
+ if (test(value)) toRemove.add(key);
+ });
+ toRemove.forEach(_baseMap.remove);
+ }
+
+ void retainAll(Iterable<Object> elements) {
+ var valuesToRetain = new Set<V>.identity();
+ for (var element in elements) {
+ if (element != null && element is! V) continue;
+ var key = _keyForValue(element);
+ if (!_baseMap.containsKey(key)) continue;
+ valuesToRetain.add(_baseMap[key]);
+ }
+
+ var keysToRemove = [];
+ _baseMap.forEach((k, v) {
+ if (!valuesToRetain.contains(v)) keysToRemove.add(k);
+ });
+ keysToRemove.forEach(_baseMap.remove);
+ }
+
+ void retainWhere(bool test(V element)) =>
+ removeWhere((element) => !test(element));
+
+ /// Returns a new set which contains all the elements of [this] and [other].
+ ///
+ /// That is, the returned set contains all the elements of this [Set] and all
+ /// the elements of [other].
+ ///
+ /// Note that the returned set will use the default equality operation, which
+ /// may be different than the equality operation [this] uses.
+ Set<V> union(Set<V> other) => toSet()..addAll(other);
+}
diff --git a/lib/wrappers.dart b/lib/wrappers.dart
index 30c736e..541456e 100644
--- a/lib/wrappers.dart
+++ b/lib/wrappers.dart
@@ -2,569 +2,11 @@
// 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 unmodifiable list view from `dart:collection` is
- * exported as well, just for completeness.
- */
+/// Import `collection.dart` instead.
+@Deprecated("Will be removed in collection 2.0.0.")
library dart.pkg.collection.wrappers;
-import "dart:collection";
-import "dart:math" show Random;
-
-import "src/unmodifiable_wrappers.dart";
-
export "src/canonicalized_map.dart";
export "src/unmodifiable_wrappers.dart";
-
-/**
- * A base class for delegating iterables.
- *
- * Subclasses can provide a [_base] that should be delegated to. Unlike
- * [DelegatingIterable], this allows the base to be created on demand.
- */
-abstract class _DelegatingIterableBase<E> implements Iterable<E> {
- Iterable<E> get _base;
-
- const _DelegatingIterableBase();
-
- 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);
-
- String toString() => _base.toString();
-}
-
-/**
- * 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> extends _DelegatingIterableBase<E> {
- final Iterable<E> _base;
-
- /**
- * Create a wrapper that forwards operations to [base].
- */
- const DelegatingIterable(Iterable<E> base) : _base = base;
-}
-
-
-/**
- * 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> {
- const 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> {
- const 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(Object 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);
-
- Set<E> toSet() => new DelegatingSet<E>(_setBase.toSet());
-}
-
-/**
- * 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> {
- const 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> {
- final Map<K, V> _base;
-
- const 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;
-
- String toString() => _base.toString();
-}
-
-/**
- * An unmodifiable [Set] view of the keys of a [Map].
- *
- * The set delegates all operations to the underlying map.
- *
- * A `Map` can only contain each key once, so its keys can always
- * be viewed as a `Set` without any loss, even if the [Map.keys]
- * getter only shows an [Iterable] view of the keys.
- *
- * Note that [lookup] is not supported for this set.
- */
-class MapKeySet<E> extends _DelegatingIterableBase<E>
- with UnmodifiableSetMixin<E> {
- final Map<E, dynamic> _baseMap;
-
- MapKeySet(Map<E, dynamic> base) : _baseMap = base;
-
- Iterable<E> get _base => _baseMap.keys;
-
- bool contains(Object element) => _baseMap.containsKey(element);
-
- bool get isEmpty => _baseMap.isEmpty;
-
- bool get isNotEmpty => _baseMap.isNotEmpty;
-
- int get length => _baseMap.length;
-
- String toString() => "{${_base.join(', ')}}";
-
- bool containsAll(Iterable<Object> other) => other.every(contains);
-
- /**
- * Returns a new set with the the elements of [this] that are not in [other].
- *
- * That is, the returned set contains all the elements of this [Set] that are
- * not elements of [other] according to `other.contains`.
- *
- * Note that the returned set will use the default equality operation, which
- * may be different than the equality operation [this] uses.
- */
- Set<E> difference(Set<E> other) =>
- where((element) => !other.contains(element)).toSet();
-
- /**
- * Returns a new set which is the intersection between [this] and [other].
- *
- * That is, the returned set contains all the elements of this [Set] that are
- * also elements of [other] according to `other.contains`.
- *
- * Note that the returned set will use the default equality operation, which
- * may be different than the equality operation [this] uses.
- */
- Set<E> intersection(Set<Object> other) => where(other.contains).toSet();
-
- /**
- * Throws an [UnsupportedError] since there's no corresponding method for
- * [Map]s.
- */
- E lookup(E element) => throw new UnsupportedError(
- "MapKeySet doesn't support lookup().");
-
- /**
- * Returns a new set which contains all the elements of [this] and [other].
- *
- * That is, the returned set contains all the elements of this [Set] and all
- * the elements of [other].
- *
- * Note that the returned set will use the default equality operation, which
- * may be different than the equality operation [this] uses.
- */
- Set<E> union(Set<E> other) => toSet()..addAll(other);
-}
-
-/**
- * Creates a modifiable [Set] view of the values of a [Map].
- *
- * The `Set` view assumes that the keys of the `Map` can be uniquely determined
- * from the values. The `keyForValue` function passed to the constructor finds
- * the key for a single value. The `keyForValue` function should be consistent
- * with equality. If `value1 == value2` then `keyForValue(value1)` and
- * `keyForValue(value2)` should be considered equal keys by the underlying map,
- * and vice versa.
- *
- * Modifying the set will modify the underlying map based on the key returned by
- * `keyForValue`.
- *
- * If the `Map` contents are not compatible with the `keyForValue` function, the
- * set will not work consistently, and may give meaningless responses or do
- * inconsistent updates.
- *
- * This set can, for example, be used on a map from database record IDs to the
- * records. It exposes the records as a set, and allows for writing both
- * `recordSet.add(databaseRecord)` and `recordMap[id]`.
- *
- * Effectively, the map will act as a kind of index for the set.
- */
-class MapValueSet<K, V> extends _DelegatingIterableBase<V> implements Set<V> {
- final Map<K, V> _baseMap;
- final Function _keyForValue;
-
- /**
- * Creates a new [MapValueSet] based on [base].
- *
- * [keyForValue] returns the key in the map that should be associated with the
- * given value. The set's notion of equality is identical to the equality of
- * the return values of [keyForValue].
- */
- MapValueSet(Map<K, V> base, K keyForValue(V value))
- : _baseMap = base,
- _keyForValue = keyForValue;
-
- Iterable<V> get _base => _baseMap.values;
-
- bool contains(Object element) {
- if (element != null && element is! V) return false;
- return _baseMap.containsKey(_keyForValue(element));
- }
-
- bool get isEmpty => _baseMap.isEmpty;
-
- bool get isNotEmpty => _baseMap.isNotEmpty;
-
- int get length => _baseMap.length;
-
- String toString() => toSet().toString();
-
- bool add(V value) {
- K key = _keyForValue(value);
- bool result = false;
- _baseMap.putIfAbsent(key, () {
- result = true;
- return value;
- });
- return result;
- }
-
- void addAll(Iterable<V> elements) => elements.forEach(add);
-
- void clear() => _baseMap.clear();
-
- bool containsAll(Iterable<Object> other) => other.every(contains);
-
- /**
- * Returns a new set with the the elements of [this] that are not in [other].
- *
- * That is, the returned set contains all the elements of this [Set] that are
- * not elements of [other] according to `other.contains`.
- *
- * Note that the returned set will use the default equality operation, which
- * may be different than the equality operation [this] uses.
- */
- Set<V> difference(Set<V> other) =>
- where((element) => !other.contains(element)).toSet();
-
- /**
- * Returns a new set which is the intersection between [this] and [other].
- *
- * That is, the returned set contains all the elements of this [Set] that are
- * also elements of [other] according to `other.contains`.
- *
- * Note that the returned set will use the default equality operation, which
- * may be different than the equality operation [this] uses.
- */
- Set<V> intersection(Set<Object> other) => where(other.contains).toSet();
-
- V lookup(Object element) => _baseMap[_keyForValue(element)];
-
- bool remove(Object value) {
- if (value != null && value is! V) return false;
- var key = _keyForValue(value);
- if (!_baseMap.containsKey(key)) return false;
- _baseMap.remove(key);
- return true;
- }
-
- void removeAll(Iterable<Object> elements) => elements.forEach(remove);
-
- void removeWhere(bool test(V element)) {
- var toRemove = [];
- _baseMap.forEach((key, value) {
- if (test(value)) toRemove.add(key);
- });
- toRemove.forEach(_baseMap.remove);
- }
-
- void retainAll(Iterable<Object> elements) {
- var valuesToRetain = new Set<V>.identity();
- for (var element in elements) {
- if (element != null && element is! V) continue;
- var key = _keyForValue(element);
- if (!_baseMap.containsKey(key)) continue;
- valuesToRetain.add(_baseMap[key]);
- }
-
- var keysToRemove = [];
- _baseMap.forEach((k, v) {
- if (!valuesToRetain.contains(v)) keysToRemove.add(k);
- });
- keysToRemove.forEach(_baseMap.remove);
- }
-
- void retainWhere(bool test(V element)) =>
- removeWhere((element) => !test(element));
+export "src/wrappers.dart";
- /**
- * Returns a new set which contains all the elements of [this] and [other].
- *
- * That is, the returned set contains all the elements of this [Set] and all
- * the elements of [other].
- *
- * Note that the returned set will use the default equality operation, which
- * may be different than the equality operation [this] uses.
- */
- Set<V> union(Set<V> other) => toSet()..addAll(other);
-}
diff --git a/pubspec.yaml b/pubspec.yaml
index a2ca5d6..ff2607e 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 1.4.0-dev
+version: 1.4.0
author: Dart Team <misc@dartlang.org>
description: Collections and utilities functions and classes related to collections.
homepage: https://www.github.com/dart-lang/collection
diff --git a/test/iterable_zip_test.dart b/test/iterable_zip_test.dart
index cc8ac76..0679171 100644
--- a/test/iterable_zip_test.dart
+++ b/test/iterable_zip_test.dart
@@ -3,9 +3,11 @@
// BSD-style license that can be found in the LICENSE file.
import "dart:collection";
-import "package:collection/iterable_zip.dart";
+
import "package:test/test.dart";
+import "package:collection/collection.dart";
+
/// Iterable like [base] except that it throws when value equals [errorValue].
Iterable iterError(Iterable base, int errorValue) {
return base.map((x) => x == errorValue ? throw "BAD" : x);
diff --git a/test/priority_queue_test.dart b/test/priority_queue_test.dart
index cda0748..c6966d6 100644
--- a/test/priority_queue_test.dart
+++ b/test/priority_queue_test.dart
@@ -4,9 +4,10 @@
/// Tests priority queue implementations utilities.
-import "package:collection/priority_queue.dart";
import "package:test/test.dart";
+import "package:collection/priority_queue.dart";
+
void main() {
testDefault();
testInt(() => new HeapPriorityQueue<int>());
@@ -48,11 +49,9 @@
}
}
-/**
- * Test that a queue behaves correctly.
- *
- * The elements must be in priority order, from highest to lowest.
- */
+/// Test that a queue behaves correctly.
+///
+/// The elements must be in priority order, from highest to lowest.
void testQueue(String name, PriorityQueue create(), List elements, notElement) {
test(name, () => testQueueBody(create, elements, notElement));
}
diff --git a/test/unmodifiable_collection_test.dart b/test/unmodifiable_collection_test.dart
index 6c722d0..682a406 100644
--- a/test/unmodifiable_collection_test.dart
+++ b/test/unmodifiable_collection_test.dart
@@ -2,9 +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 "package:collection/wrappers.dart";
import "package:test/test.dart";
+import "package:collection/collection.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.
diff --git a/test/wrapper_test.dart b/test/wrapper_test.dart
index e3043a2..f0ac7fa 100644
--- a/test/wrapper_test.dart
+++ b/test/wrapper_test.dart
@@ -23,10 +23,8 @@
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.
- */
+/// 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
