Add priority queue to package:collection.

Add priority queue to package:collection.

R=ajohnsen@google.com, sgjesse@google.com

Committed: https://code.google.com/p/dart/source/detail?r=31532

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

LGTM - nice one! :)

https://codereview.chromium.org/110483006/diff/1/pkg/collection/README.md
File pkg/collection/README.md (right):

https://codereview.chromium.org/110483006/diff/1/pkg/collection/README.md#new...
pkg/collection/README.md:26: some different sorting algorithms.
some different -> various.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
File pkg/collection/lib/priority_queue.dart (right):

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:1: // Copyright (c) 2013, the Dart
project authors.  Please see the AUTHORS file
2014 :)

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:36: * This operation is not efficient. It
may need to look through all elements
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?)

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:95: * The returned [Set] is a
[SplayTreeSet], but this may change.
How will that work with a priority-queue of [4, 4, 4, 4] ?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:104: * The elements are kept in a heap
structure, where the least element
least -> `first` ?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:106: * at logarithmic time on average
(but occasionally linear when growing
amortized?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:146: void _add(E element) {
Move privates below non-private.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:151: /** Find the index of an object in
the heap. Returns -1 if not found. */
Multi-line or //.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:180: position >>= 1;
  // Go to parent.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:182: position += 1;
  // Go to right sibling.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:197: int comp = comparison(last,
element);
no need to store as comp?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:208: int newLength = _length - 1;
Start out by saying `--_length;` and use _length instead of newLength?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:215: void add(E element) {
=>

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:226: if (_length == 0) throw new
StateError("No such element");
if (isEmpty), and below in removeFirst.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:227: return _queue[0];
.first

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:232: E result = _queue[0];
.first

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:333: if (newCapacity < _INITIAL_CAPACITY)
newCapacity = _INITIAL_CAPACITY;
Emm... Why? :)

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:340: return
_queue.take(_length).toString();
.toList().sort(comparison)?

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

LGTM, with comments.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
File pkg/collection/lib/priority_queue.dart (right):

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:12: * It is optimized for adding elements
Should this be the performance characteristics for the default implementation,
and have a factory constructor for a HeapPriorityQueue?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:46: * The queue must not be empty when
this method is called.
Say what happen in this case?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:75: * The returned iterable has no
specified order.
Why is the priority order not used in the returned iterable?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:85: * Returns a list of the elements of
this queue in priority order.
I assume the elements are not removed by this operation. Maybe state that
directly.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:115: /** The comparison being used to
compare the priority of elements. */
Multiline or ///.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:135: * a higher priority.
Add some information about the default value for comparison. Maybe we also need
to expand the comment on Comparable.compare.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:151: /** Find the index of an object in
the heap. Returns -1 if not found. */
This should not be a dartdoc comment.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:203: }
Should there be a shrink policy as well to shrink the backing store?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/test/priority...
File pkg/collection/test/priority_queue_test.dart (right):

https://codereview.chromium.org/110483006/diff/1/pkg/collection/test/priority...
pkg/collection/test/priority_queue_test.dart:20: new List<int>.generate(count,
(x)=>x),
Spaces on both sides of =>.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/test/priority...
pkg/collection/test/priority_queue_test.dart:29: new List<C>.generate(count,
(x)=> new C(x)),
Space before => (two more below).

https://codereview.chromium.org/110483006/diff/1/pkg/collection/test/priority...
pkg/collection/test/priority_queue_test.dart:64: expect(q.toSet().toList(),
equals(elements));
Why is the toList on the set always ordered?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/test/priority...
pkg/collection/test/priority_queue_test.dart:79: expect(all.length,
elements.length);
Is this not just expect(all, equals(elements))?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/test/priority...
pkg/collection/test/priority_queue_test.dart:131: }
Test toSet in this case?

https://codereview.chromium.org/110483006/diff/1/pkg/collection/test/priority...
pkg/collection/test/priority_queue_test.dart:154: // Class is comparable,
comparators match normal and inverse order.
Make these two comparators static members of C?

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

https://codereview.chromium.org/110483006/diff/1/pkg/collection/README.md
File pkg/collection/README.md (right):

https://codereview.chromium.org/110483006/diff/1/pkg/collection/README.md#new...
pkg/collection/README.md:26: some different sorting algorithms.
On 2014/01/05 20:37:12, Anders Johnsen wrote:
> some different -> various.

Done.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
File pkg/collection/lib/priority_queue.dart (right):

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:1: // Copyright (c) 2013, the Dart
project authors.  Please see the AUTHORS file
I'm still in the "academic quarter" - three months where you can still write the
old year :)

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:12: * It is optimized for adding elements
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.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:36: * This operation is not efficient. It
may need to look through all elements
On 2014/01/05 20:37:12, Anders Johnsen wrote:
> 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?)

Done.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:46: * The queue must not be empty when
this method is called.
This is how we write it when the implementation throws (or may throw).

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:75: * The returned iterable has no
specified order.
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)).

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:85: * Returns a list of the elements of
this queue in priority order.
On 2014/01/06 08:05:21, Søren Gjesse wrote:
> I assume the elements are not removed by this operation. Maybe state that
> directly.

Done.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:95: * The returned [Set] is a
[SplayTreeSet], but this may change.
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.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:104: * The elements are kept in a heap
structure, where the least element
-> the element with the highest priority

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:106: * at logarithmic time on average
(but occasionally linear when growing
On 2014/01/05 20:37:12, Anders Johnsen wrote:
> amortized?

Done.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:115: /** The comparison being used to
compare the priority of elements. */
But why?!?
Ok, multiline.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:135: * a higher priority.
On 2014/01/06 08:05:21, Søren Gjesse wrote:
> Add some information about the default value for comparison. Maybe we also
need
> to expand the comment on Comparable.compare.

Done.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:146: void _add(E element) {
Hmm. Ok, grudgingly.

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

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:151: /** Find the index of an object in
the heap. Returns -1 if not found. */
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.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:180: position >>= 1;
On 2014/01/05 20:37:12, Anders Johnsen wrote:
>   // Go to parent.

Done.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:182: position += 1;
On 2014/01/05 20:37:12, Anders Johnsen wrote:
>   // Go to right sibling.

Done.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:197: int comp = comparison(last,
element);
On 2014/01/05 20:37:12, Anders Johnsen wrote:
> no need to store as comp?

Done.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:203: }
Probably not.
The complexity is unlikely to be worth it.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:208: int newLength = _length - 1;
I dislike having an element in _queue[_length], so I reduce _length and set
_queue[newLength] to null after doing all the updates.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:215: void add(E element) {
Not for a void function.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:226: if (_length == 0) throw new
StateError("No such element");
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.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:227: return _queue[0];
No in general, and ... this is the definition of `first` :)

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:232: E result = _queue[0];
And no.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:333: if (newCapacity < _INITIAL_CAPACITY)
newCapacity = _INITIAL_CAPACITY;
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.

https://codereview.chromium.org/110483006/diff/1/pkg/collection/lib/priority_...
pkg/collection/lib/priority_queue.dart:340: return
_queue.take(_length).toString();
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.

[Lasse Reichstein Nielsen, 2014-01-07 07:59:38]

Committed patchset #4 manually as r31532 (presubmit successful).