Add priority queue to package:collection.
R=ajohnsen@google.com, sgjesse@google.com
Review URL: https://codereview.chromium.org//110483006
git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart/pkg/collection@31532 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/README.md b/README.md
index bb392fd..7ebd62a 100644
--- a/README.md
+++ b/README.md
@@ -8,14 +8,24 @@
The `collection` package can be imported as separate libraries, or
in totality:
- import 'package:collection/equality.dart';
import 'package:collection/algorithms.dart';
+ import 'package:collection/equality.dart';
+ import 'package:collection/iterable_zip.dart';
+ import 'package:collection/priority_queue.dart';
import 'package:collection/wrappers.dart';
or
import 'package:collection/collection.dart';
+## Algorithms
+
+The algorithms library contains functions that operate on lists.
+
+It contains ways to shuffle a `List`, do binary search on a sorted `List`, and
+various sorting algorithms.
+
+
## Equality
The equality library gives a way to specify equality of elements and
@@ -28,19 +38,23 @@
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:
+The library provides ways to define equalities on `Iterable`s, `List`s, `Set`s,
+and `Map`s, as well as combinations of these, such as:
const MapEquality(const IdentityEquality(), const ListEquality());
-This equality considers maps equal if they have identical keys, and the corresponding values are lists with equal (`operator==`) values.
+This equality considers maps equal if they have identical keys, and the
+corresponding values are lists with equal (`operator==`) values.
-## Algorithms
-The algorithms library contains functions that operate on lists.
+## Iterable Zip
-It contains ways to shuffle a `List`, do binary search on a sorted `List`, and
-some different sorting algorithms.
+Utilities for "zipping" a list of iterables into an iterable of lists.
+
+
+## Priority Queue
+
+An interface and implemention of a priority queue.
## Wrappers
diff --git a/lib/collection.dart b/lib/collection.dart
index a6f192d..d640071 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -11,6 +11,7 @@
* 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.
*/
@@ -19,4 +20,5 @@
export "algorithms.dart";
export "equality.dart";
export "iterable_zip.dart";
+export "priority_queue.dart";
export "wrappers.dart";
diff --git a/lib/priority_queue.dart b/lib/priority_queue.dart
new file mode 100644
index 0000000..eb0cda3
--- /dev/null
+++ b/lib/priority_queue.dart
@@ -0,0 +1,383 @@
+// 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.
+
+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> {
+ /**
+ * 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);
+
+ /**
+ * 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 not 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 instad 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/pubspec.yaml b/pubspec.yaml
index 0fec04b..09c07a7 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 0.9.0
+version: 0.9.1-dev
author: Dart Team <misc@dartlang.org>
description: Collections and utilities functions and classes related to collections.
homepage: http://www.dartlang.org
diff --git a/test/priority_queue_test.dart b/test/priority_queue_test.dart
new file mode 100644
index 0000000..3d9c9fd
--- /dev/null
+++ b/test/priority_queue_test.dart
@@ -0,0 +1,167 @@
+// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/// Tests priority queue implementations utilities.
+
+import "dart:collection";
+import "package:collection/priority_queue.dart";
+import "package:unittest/unittest.dart";
+
+void main() {
+ testInt(() => new HeapPriorityQueue<int>());
+ testCustom((comparator) => new HeapPriorityQueue<C>(comparator));
+}
+
+void testInt(PriorityQueue<int> create()) {
+ for (int count in [1, 5, 127, 128, 400]) {
+ testQueue("int:$count",
+ create,
+ new List<int>.generate(count, (x) => x),
+ count);
+ }
+}
+
+void testCustom(PriorityQueue<C> create(comparator)) {
+ for (int count in [1, 5, 127, 128, 400]) {
+ testQueue("Custom:$count/null",
+ () => create(null),
+ new List<C>.generate(count, (x) => new C(x)),
+ new C(count));
+ testQueue("Custom:$count/compare",
+ () => create(compare),
+ new List<C>.generate(count, (x) => new C(x)),
+ new C(count));
+ testQueue("Custom:$count/compareNeg",
+ () => create(compareNeg),
+ new List<C>.generate(count, (x) => new C(count - x)),
+ new C(0));
+ }
+}
+
+/**
+ * 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));
+}
+
+void testQueueBody(PriorityQueue create(), List elements, notElement) {
+ PriorityQueue q = create();
+ expect(q.isEmpty, isTrue);
+ expect(q, hasLength(0));
+ expect(() { q.first; }, throwsStateError);
+ expect(() { q.removeFirst(); }, throwsStateError);
+
+ // Tests removeFirst, first, contains, toList and toSet.
+ void testElements() {
+ expect(q.isNotEmpty, isTrue);
+ expect(q, hasLength(elements.length));
+
+ expect(q.toList(), equals(elements));
+ expect(q.toSet().toList(), equals(elements));
+
+ for (int i = 0; i < elements.length; i++) {
+ expect(q.contains(elements[i]), isTrue);
+ }
+ expect(q.contains(notElement), isFalse);
+
+ List all = [];
+ while (!q.isEmpty) {
+ var expected = q.first;
+ var actual = q.removeFirst();
+ expect(actual, same(expected));
+ all.add(actual);
+ }
+
+ expect(all.length, elements.length);
+ for (int i = 0; i < all.length; i++) {
+ expect(all[i], same(elements[i]));
+ }
+
+ expect(q.isEmpty, isTrue);
+ }
+
+ q.addAll(elements);
+ testElements();
+
+ q.addAll(elements.reversed);
+ testElements();
+
+ // Add elements in a non-linear order (gray order).
+ for (int i = 0, j = 0; i < elements.length; i++) {
+ int gray;
+ do {
+ gray = j ^ (j >> 1);
+ j++;
+ } while (gray >= elements.length);
+ q.add(elements[gray]);
+ }
+ testElements();
+
+ // Add elements by picking the middle element first, and then recursing
+ // on each side.
+ void addRec(int min, int max) {
+ int mid = min + ((max - min) >> 1);
+ q.add(elements[mid]);
+ if (mid + 1 < max) addRec(mid + 1, max);
+ if (mid > min) addRec(min, mid);
+ }
+ addRec(0, elements.length);
+ testElements();
+
+ // Test removeAll.
+ q.addAll(elements);
+ expect(q, hasLength(elements.length));
+ Iterable all = q.removeAll();
+ expect(q.isEmpty, isTrue);
+ expect(all, hasLength(elements.length));
+ for (int i = 0; i < elements.length; i++) {
+ expect(all, contains(elements[i]));
+ }
+
+ // Test the same element more than once in queue.
+ q.addAll(elements);
+ q.addAll(elements.reversed);
+ expect(q, hasLength(elements.length * 2));
+ for (int i = 0; i < elements.length; i++) {
+ var element = elements[i];
+ expect(q.contains(element), isTrue);
+ expect(q.removeFirst(), element);
+ expect(q.removeFirst(), element);
+ }
+
+ // Test queue with all same element.
+ var a = elements[0];
+ for (int i = 0; i < elements.length; i++) {
+ q.add(a);
+ }
+ expect(q, hasLength(elements.length));
+ expect(q.contains(a), isTrue);
+ expect(q.contains(notElement), isFalse);
+ q.removeAll().forEach((x) => expect(x, same(a)));
+
+ // Test remove.
+ q.addAll(elements);
+ for (var element in elements.reversed) {
+ expect(q.remove(element), isTrue);
+ }
+ expect(q.isEmpty, isTrue);
+}
+
+
+// Custom class.
+// Class is comparable, comparators match normal and inverse order.
+int compare(C c1, C c2) => c1.value - c2.value;
+int compareNeg(C c1, C c2) => c2.value - c1.value;
+
+class C implements Comparable {
+ final int value;
+ const C(this.value);
+ int get hashCode => value;
+ bool operator==(Object other) => other is C && value == other.value;
+ int compareTo(C other) => value - other.value;
+ String toString() => "C($value)";
+}
