Add priority queue to package:collection.

pkg/collection/lib/priority_queue.dart

+// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file

[Anders Johnsen, 2014/01/05 20:37:12]

2014 :)

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

I'm still in the "academic quarter" - three months where you can still write the
old year :)

+// 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.
+ *
+ * It is optimized for adding elements

[Søren Gjesse, 2014/01/06 08:05:21]

Should this be the performance characteristics for the default implementation,
and have a factory constructor for a HeapPriorityQueue?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Let's postpone having a default implementation until we have more than one
implementation. It's a not a fair choice to pick one before that, and changing
performance characteristics afterwards isn't a good idea.

I'll remove references to performance from the interface, and explain it for the
implementation.

+ * and removing them again in order of highest priority.
+ */
+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.
+   *
+   * This operation is not efficient. It may need to look through all elements

[Anders Johnsen, 2014/01/05 20:37:12]

Don't talk about efficiency in the interface. That should be in the impl. Also,
use O(n) instead of 'not efficient'. It's much easier to quickly scan through
and find these, than reading about how it works.

Same goes for:

 first
 removeFirst
 remove
 add/insert (why is it not in interface?)

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Done.

+   * in order see if an element is there.
+   */
+  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.

[Søren Gjesse, 2014/01/06 08:05:21]

Say what happen in this case?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

This is how we write it when the implementation throws (or may throw).

+   */
+  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.
+   *
+   * This operation is not efficient. It may need to look through all elements
+   * in order see if an element is there.
+   */
+  bool remove(E element);
+
+  /**
+   * Removes all the elements from this queue and returns them.
+   *
+   * The returned iterable has no specified order.

[Søren Gjesse, 2014/01/06 08:05:21]

Why is the priority order not used in the returned iterable?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Because you can use toList to do that.
This is an efficient way of removing the elements *without* sorting them.
This is an O(1) operation, where toList is O(n*log(n)).

+   */
+  Iterable<E> removeAll();
+
+  /**
+   * Removes all the elements from this queue.
+   */
+  void clear();
+
+  /**
+   * Returns a list of the elements of this queue in priority order.

[Søren Gjesse, 2014/01/06 08:05:21]

I assume the elements are not removed by this operation. Maybe state that
directly.

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Done.

+   *
+   * 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 returned [Set] is a [SplayTreeSet], but this may change.

[Anders Johnsen, 2014/01/05 20:37:12]

How will that work with a priority-queue of [4, 4, 4, 4] ?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

The same way [4,4,4,4].toSet() works - it returns a set with one element.
I'll add a comment that multiple elements in the queue only generates one
element in the returned set.

+   * The set contains all the elements of this queue.
+   */
+  Set<E> toSet();
+}
+
+/**
+ * Heap based priority queue.
+ *
+ * The elements are kept in a heap structure, where the least element

[Anders Johnsen, 2014/01/05 20:37:12]

least -> `first` ?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

-> the element with the highest priority

+ * is immediately accessible, and adding or removing an element takes
+ * at logarithmic time on average (but occasionally linear when growing

[Anders Johnsen, 2014/01/05 20:37:12]

amortized?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Done.

+ * the heap capacity).
+ */
+class HeapPriorityQueue<E> implements PriorityQueue<E> {
+  // Keep capacity as a power of 2 minus one. Any odd number will work,
+  // but bubbling down assumes an odd length so either both children of a
+  // node is inside the queue, or both are not.
+  static const int _INITIAL_CAPACITY = 7;
+
+  /** The comparison being used to compare the priority of elements. */

[Søren Gjesse, 2014/01/06 08:05:21]

Multiline or ///.

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

But why?!?
Ok, multiline.

+  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.

[Søren Gjesse, 2014/01/06 08:05:21]

Add some information about the default value for comparison. Maybe we also need
to expand the comment on Comparable.compare.

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Done.

+   */
+  HeapPriorityQueue([int comparison(E e1, E e2)])
+      : comparison = (comparison != null) ? comparison : Comparable.compare;
+
+  int get length => _length;
+
+  bool get isEmpty => _length == 0;
+
+  bool get isNotEmpty => _length != 0;
+
+  void _add(E element) {

[Anders Johnsen, 2014/01/05 20:37:12]

Move privates below non-private.

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Hmm. Ok, grudgingly.

I sorted the public methods by name too, just for good measure.

+    if (_length == _queue.length) _grow();
+    _bubbleUp(element, _length++);
+  }
+
+  /** Find the index of an object in the heap. Returns -1 if not found. */

[Anders Johnsen, 2014/01/05 20:37:12]

Multi-line or //.

[Søren Gjesse, 2014/01/06 08:05:21]

This should not be a dartdoc comment.

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Multi-line done.

Why should it not be a dart-doc comment.
It doesn't hurt, and it means that you get help when you are editing this code.

Personally I think *all* members should have dart-doc comments, inherited or
explicit.

+  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) {
+          position >>= 1;

[Anders Johnsen, 2014/01/05 20:37:12]

  // Go to parent.

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Done.

+        }
+        position += 1;

[Anders Johnsen, 2014/01/05 20:37:12]

  // Go to right sibling.

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Done.

+      } while (position > _length);
+    } while (position != 1);  // This happens for the right-most element.
+    return -1;
+  }
+
+  bool contains(E object) {
+    return _locate(object) >= 0;
+  }
+
+  bool remove(E element) {
+    int index = _locate(element);
+    if (index < 0) return false;
+    E last = _removeLast();
+    if (index < _length) {
+      int comp = comparison(last, element);

[Anders Johnsen, 2014/01/05 20:37:12]

no need to store as comp?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Done.

+      if (comp <= 0) {
+        _bubbleUp(last, index);
+      } else {
+        _bubbleDown(last, index);
+      }
+    }

[Søren Gjesse, 2014/01/06 08:05:21]

Should there be a shrink policy as well to shrink the backing store?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Probably not.
The complexity is unlikely to be worth it.

+    return true;
+  }
+
+  E _removeLast() {
+    int newLength = _length - 1;

[Anders Johnsen, 2014/01/05 20:37:12]

Start out by saying `--_length;` and use _length instead of newLength?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

I dislike having an element in _queue[_length], so I reduce _length and set
_queue[newLength] to null after doing all the updates.

+    E last = _queue[newLength];
+    _queue[newLength] = null;
+    _length = newLength;
+    return last;
+  }
+
+  void add(E element) {

[Anders Johnsen, 2014/01/05 20:37:12]

=>

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Not for a void function.

+    _add(element);
+  }
+
+  void addAll(Iterable<E> elements) {
+    for (E element in elements) {
+      _add(element);
+    }
+  }
+
+  E get first {
+    if (_length == 0) throw new StateError("No such element");

[Anders Johnsen, 2014/01/05 20:37:12]

if (isEmpty), and below in removeFirst.

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

No.
I try to avoid defining methods in terms of other public and overridable
methods. That makes it harder for someone extending the class to break stuff
that he doesn't know about.

That is also why I have an '_add' that is called from both 'add' and 'addAll'.

If we defined removeFirst in terms of first, it should be documented, and we
would be stuck with it. Or not documented, and someone wanting to log the uses
of 'first' would suddenly get more hits than expected.

+    return _queue[0];

[Anders Johnsen, 2014/01/05 20:37:12]

.first

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

No in general, and ... this is the definition of `first` :)

+  }
+
+  E removeFirst() {
+    if (_length == 0) throw new StateError("No such element");
+    E result = _queue[0];

[Anders Johnsen, 2014/01/05 20:37:12]

.first

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

And no.

+    E last = _removeLast();
+    if (_length > 0) {
+      _bubbleDown(last, 0);
+    }
+    return result;
+  }
+
+  Iterable<E> removeAll() {
+    List<E> result = _queue;
+    int length = _length;
+    _queue = const [];
+    _length = 0;
+    return result.take(length);
+  }
+
+  void clear() {
+    _queue = const [];
+    _length = 0;
+  }
+
+  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;
+  }
+
+  /**
+   * 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];
+      int comp = comparison(element, parent);
+      if (comp > 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;
+  }
+
+  void _grow() {
+    int newCapacity = _queue.length * 2 + 1;
+    if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY;

[Anders Johnsen, 2014/01/05 20:37:12]

Emm... Why? :)

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

Because `clear` and `removeAll` sets the _queue to the empty list.

The assumption is that if you create a queue, you are going to use it, so we
give it useful initial capacity.

If you clear a queue, you are probably done using it, so we set it to the
"const[]" list to not waste space. If you decide to use it again anyway, you hit
this line.

+    List<E> newQueue = new List<E>(newCapacity);
+    newQueue.setRange(0, _length, _queue);
+    _queue = newQueue;
+  }
+
+  String toString() {
+    return _queue.take(_length).toString();

[Anders Johnsen, 2014/01/05 20:37:12]

.toList().sort(comparison)?

[Lasse Reichstein Nielsen, 2014/01/06 12:53:01]

That would be wasteful. 
I could live with:
   "HeapPriorityQueue:$first${isEmpty?'':',...'}(#$length)"
but I only added it to be able to debug the test cases anyway.
Let's not specify what it does.

+  }
+}