Add collection-helpers library.

Add collection-helpers library.

Library contains:
- Delegating wrappers for Iterable, List, Set, Queue, Map.
- Equality abstraction, with ordered and unordered equality of
  collections, and a deep equality.
- Algorithms on collections (List only so far) with
  - shuffle
  - binary search
  - insertion-sort
  - merge-sort
Planning to add Tim-sort eventually.

R=floitsch@google.com

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

[Lasse Reichstein Nielsen, 2013-09-18 13:39:25]

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
File pkg/collection_helpers/lib/algorithms.dart (right):

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:48: bool location: false
Consider having three different versions:
- plain - finds the element, any version, if it's there.
- for insertion, first: finds the index where all preceding elements are less
than (at first matching element in list).
- for insertion, last: finds the index where all preceding elements are less
than or equal (after last matching element in list).

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:50: if (compare == null) return
_comparableBinarySearch(sortedList, key, location);
Whoops, long line.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:107: * Sort a list using insertion
sort.
Should document the behavior of insertion sort (low overhead, n-log(n)
comparisons, n^2 element moves worst case).

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:150: void mergeSort(List list, {int
start: 0, int end: null, int compare(a, b)}) {
Should have documentation.

[justinfagnani, 2013-09-19 17:57:52]

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/wr...
File pkg/collection_helpers/lib/wrappers.dart (right):

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/wr...
pkg/collection_helpers/lib/wrappers.dart:25: DelegatingIterable(Iterable<E>
base) : _base = base;
FYI, we had a decent debate about constructor vs. abstract methods to get the
delegate when we added delegating collections to Quiver (A Guava-like library,
see:
https://github.com/google/quiver-dart/blob/master/lib/src/collection/delegate...)

I argued for an abstract getter named 'delegate' mainly because it allows the
subclass to swap out the delegated collection or provide it lazily, one of the
reasons you might want a wrapper, also it allows the wrapper to be used as a mix
in.

For what it's worth, this is how Guava's forwarding collections work, but there
they have protected methods.

[Lasse Reichstein Nielsen, 2013-09-20 07:59:03]

On 2013/09/19 17:57:52, justinfagnani wrote:

> I argued for an abstract getter named 'delegate' mainly because it allows the
> subclass to swap out the delegated collection or provide it lazily, one of the
> reasons you might want a wrapper, also it allows the wrapper to be used as a
mix
> in.
> 
> For what it's worth, this is how Guava's forwarding collections work, but
there
> they have protected methods.

It's a good point, and if I had protected methods, I would probably have done it
that way, 
and with a specialized version that has a constructor, so it's immediately
useful too.

I so miss protected members!

[kevmoo-old, 2013-09-20 21:34:35]

DBR

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
File pkg/collection_helpers/lib/algorithms.dart (right):

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:74: void shuffle(List list, [int
start = 0, int end = null]) {
Optional argument for Random impl.

[floitsch, 2013-09-21 18:12:37]

FYI.
I couldn't see equality.dart. seems like an upload error.

We should see if we can merge with other existing packages (potentially
deprecating them or removing functionality here).

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
File pkg/collection_helpers/lib/algorithms.dart (right):

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:18: int mid = min + ((max - min) >>
1);
~/ 2

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:48: bool location: false
location is not a boolean name.
returnLocation?
negativeWhenAbsent ?

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:74: void shuffle(List list, [int
start = 0, int end = null]) {
This should be moved as member method on List.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:133: while (min < max) {
I'm not convinced that binary search really is worth it.
The setRange below needs to run through the list anyway. Could be, of course,
that compare is really slow, but I wouldn't design the insertion sort on it.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:134: int mid = min + ((max - min) >>
1);
~/ 2

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:165: int middle = start + ((end -
start) >> 1);
~/ 2

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:168: List scratchSpace = new
List(secondLength);
assert(secondLength >= firstLength);

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:194: int mid = min + ((max - min) >>
1);
~/ 2

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:223: int middle = start + (length >>
1);
~/ 2

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:230: // sort the first half into the
end of the source area.
Start with capital letter.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:233: // merge the two parts into the
target area.
ditto.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:272: if (cursor2 == secondEnd) break
secondEmpty;
I think it's cleaner to have a restList, restOffset, restCursor that is set
before breaking.
Alternatively simply switching firstList and secondList before the second break.

[Lasse Reichstein Nielsen, 2013-09-24 20:23:53]

Odd about equality.dart - the patch file is there, but side-by-side view is
broken (and it's a new file, so it's not like it's valuable).

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
File pkg/collection_helpers/lib/algorithms.dart (right):

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:18: int mid = min + ((max - min) >>
1);
All done.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:74: void shuffle(List list, [int
start = 0, int end = null]) {
I'd prefer to keep this as simple as possible. No need to confuse users with the
ability to pass in a different Random implementation.

If you know enough to use a different Random, you can write this in eighth lines
yourself too.

Especially if it's put on ListBase.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:133: while (min < max) {
I'm planning to use this insertionSort for TimSort as well, and that typically
uses binary insertion sort (original implementation and Java implementation
both).

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:168: List scratchSpace = new
List(secondLength);
Why assert? Documentation should be enough.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:230: // sort the first half into the
end of the source area.
On 2013/09/21 18:12:37, floitsch wrote:
> Start with capital letter.

Done.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:233: // merge the two parts into the
target area.
On 2013/09/21 18:12:37, floitsch wrote:
> ditto.

Done.

https://codereview.chromium.org/23567044/diff/1/pkg/collection_helpers/lib/al...
pkg/collection_helpers/lib/algorithms.dart:272: if (cursor2 == secondEnd) break
secondEmpty;
If I have to do more than a single line of work to make that work, I could just
as well inline the three lines below. This is only done to keep the loop
smaller.

I think I can do a rewrite that avoids the extra labels, and gets the same
result with a single break and a continue.

[Lasse Reichstein Nielsen, 2013-09-27 09:22:25]

https://codereview.chromium.org/23567044/diff/12001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/equality.dart (right):

https://codereview.chromium.org/23567044/diff/12001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:31: * `equals(a, b)` then `hash(a) ==
hashCodeOf(b)`.
hashCodeOf(b) -> hash(b)

https://codereview.chromium.org/23567044/diff/12001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:67: int hash(Object e) => e.hashCode; 
// TODO: use Object.identityHashCode.
Possible now, so do it.

https://codereview.chromium.org/23567044/diff/12001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:219: class SetEquality<E> implements
Equality<Set<E>> {
Just extend UnorderedIterableEquality and have the methods expecting Set call
the super method expecting iterable.

[Lasse Reichstein Nielsen, 2013-10-03 11:17:32]

Equality is here now, PTAL.

https://codereview.chromium.org/23567044/diff/12001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/algorithms.dart (right):

https://codereview.chromium.org/23567044/diff/12001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/algorithms.dart:48: bool location: false
I'll remove the location parameter and just return the first encountered match,
or -1 if there isn't any. The other cases are too speculative.

Should I make `compare` an optional positional parameter?

[Lasse Reichstein Nielsen, 2013-10-08 08:56:55]

https://codereview.chromium.org/23567044/diff/18001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/algorithms.dart (right):

https://codereview.chromium.org/23567044/diff/18001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/algorithms.dart:66: * A sub-range of a list can be
shuffled by providing [start] and [end].319
I'll remove the spurious "319".

https://codereview.chromium.org/23567044/diff/18001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/algorithms.dart:181: int middle = start + ((end -
start) ~/ 2);
I tested the speed of >> vs ~/. In a pure micro-benchmark, it's about the same
on the VM (with a marginal advantage to shift), but in dart2js code, shift is
~25 times faster than division. 
In an implementation of binary search, it halves the performance to use ~/
instead of shift in dart2js, and it reduces it by 25% on the VM.

Let's just use shift?

[floitsch, 2013-10-17 12:17:52]

LGTM.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/algorithms.dart (right):

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/algorithms.dart:34: * is unpredicatable.
unpredictable

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/algorithms.dart:66: * A sub-range of a list can be
shuffled by providing [start] and [end].
If the optional arguments [start] and [end] are provided, the function only
shuffles the specified sub-range.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/equality.dart (right):

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:60: * This equality uses the objects'
own [Object.hashCode] for the equality.
not true anymore. Looks like you switched to identityHashCode.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:79: const DefaultEquality()])
weird indentation.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:139: // Jenkins's one-at-a-time hash
function.
at least add a TODO that there is duplicated code.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:160: * and the elements of one set can
be paired with the elements
no sets here.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:268: bool equals(Map<K, V> e1, Map<K,
V> e2) {
new line before.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:273: Map<_MapEntry, int> counts = new
HashMap();
Add comment or rename variable.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:311: * For `equals`, the first equality
that maches the first argument is used,
matches

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:315: * The equalities should generally
work on disjoint types, otherwise it may
not clear.
I guess it refers to line 327 where we look at e1 only before deciding that this
is the equality we want to use.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/te...
File pkg/collection_helpers/test/equality_test.dart (right):

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/te...
pkg/collection_helpers/test/equality_test.dart:18: isFalse);
This won't work for dart2js.
Here and in all other tests.

[Lasse Reichstein Nielsen, 2013-10-23 11:42:39]

I had to mark a test as failing in the analyzer. I couldn't find any good reason
for the failure - it looks like an analyzer bug (to me) - especially because it
fails for /none of a multitest and not for /01 etc.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/algorithms.dart (right):

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/algorithms.dart:34: * is unpredicatable.
On 2013/10/17 12:17:53, floitsch wrote:
> unpredictable

Done.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/algorithms.dart:66: * A sub-range of a list can be
shuffled by providing [start] and [end].
On 2013/10/17 12:17:53, floitsch wrote:
> If the optional arguments [start] and [end] are provided, the function only
> shuffles the specified sub-range.

Done.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/equality.dart (right):

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:60: * This equality uses the objects'
own [Object.hashCode] for the equality.
Good catch, removed.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:79: const DefaultEquality()])
Indented for from the start of "elementEquality". Proabably a little too weird.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:139: // Jenkins's one-at-a-time hash
function.
Added a comment.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:160: * and the elements of one set can
be paired with the elements
On 2013/10/17 12:17:53, floitsch wrote:
> no sets here.

Done.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:268: bool equals(Map<K, V> e1, Map<K,
V> e2) {
On 2013/10/17 12:17:53, floitsch wrote:
> new line before.

Done.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:273: Map<_MapEntry, int> counts = new
HashMap();
On 2013/10/17 12:17:53, floitsch wrote:
> Add comment or rename variable.

Done.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:311: * For `equals`, the first equality
that maches the first argument is used,
On 2013/10/17 12:17:53, floitsch wrote:
> matches

Done.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/equality.dart:315: * The equalities should generally
work on disjoint types, otherwise it may
reworded.

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/te...
File pkg/collection_helpers/test/equality_test.dart (right):

https://codereview.chromium.org/23567044/diff/22001/pkg/collection_helpers/te...
pkg/collection_helpers/test/equality_test.dart:18: isFalse);
Ack. Will mark as failing.

[Lasse Reichstein Nielsen, 2013-10-23 11:43:01]

Committed patchset #5 manually as r29072 (presubmit successful).