Reapply "New implementation of {,Linked}Hash{Set,Map}."

Reapply "New implementation of {,Linked}Hash{Set,Map}."

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

[Lasse Reichstein Nielsen, 2013-02-13 14:04:47]

Still investigating the dart2dart problem.

[floitsch, 2013-02-13 15:54:06]

LGTM.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_se...
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:34: _table._put(object);
just call "add" ?

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:47: _table._remove(object);
just call "remove"?

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:87: int _nextProbe(int previousIndex, int
probeCount, int capacity) {
Add comment that this will hit every index eventually.
Maybe even with a pointer to an explanation. But that's not necessary.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:142: // If entry is _TOMBSTONE, it matches
nothing.
I would prefer if "_TOMBSTONE" didn't escape to "_equals". If I make a "IntMap",
I could then type my _equals function as (int,int)->bool.
It would also get rid of the polymorphic case.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:273: void _clear() {
Should we also shrink the table?

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:328: E get single {
Why this special case? You still allocate an iterator with "first".

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_map.dart (right):

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_map.dart:57: int offset = _hashTable._put(key);
just use this[key] = value;

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_set.dart (right):

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:73: _table._put(object);
add.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:90: _table._checkCapacity();
wait with the capacity check?

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:106: bool remove = (removeMatching ==
test(key));
shouldRemove

https://codereview.chromium.org/12254006/diff/2001/tests/corelib/map_from_tes...
File tests/corelib/map_from_test.dart (right):

https://codereview.chromium.org/12254006/diff/2001/tests/corelib/map_from_tes...
tests/corelib/map_from_test.dart:74: Expect.isTrue(otherMap is !HashMap);
we usually put the "!" with the "is".

[Lasse Reichstein Nielsen, 2013-02-14 10:18:12]

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_se...
File sdk/lib/collection/hash_set.dart (right):

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:34: _table._put(object);
Generally a class that can be extended should not call its own public methods.
Classic example: Someone wants a set that counts all additions, so they
overwrite "add" and "addAll" to increment counters and then call the
super-version. If "addAll" then calls "add", it will double-count.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_se...
sdk/lib/collection/hash_set.dart:47: _table._remove(object);
Same.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
File sdk/lib/collection/hash_table.dart (right):

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:87: int _nextProbe(int previousIndex, int
probeCount, int capacity) {
On 2013/02/13 15:54:06, floitsch wrote:
> Add comment that this will hit every index eventually.
> Maybe even with a pointer to an explanation. But that's not necessary.

Done.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:142: // If entry is _TOMBSTONE, it matches
nothing.
Good argument, done.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:273: void _clear() {
Let's not do that now. If you reuse a set that grew big, it might be very likely
to grow big again.
It's worth running some tests to see, though. We can also shrink in the case
where most of the entries are deleted.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/hash_ta...
sdk/lib/collection/hash_table.dart:328: E get single {

True. It changes the behavior so you only need to look at half the elements on
average, but it's asymptotically the same. I'll remove it.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_map.dart (right):

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_map.dart:57: int offset = _hashTable._put(key);
Again I prefer to not use a public, overridable method as part of the
implementation of another.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
File sdk/lib/collection/linked_hash_set.dart (right):

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:73: _table._put(object);
Same.

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:90: _table._checkCapacity();
Doesn't work if objectsToRemove's iterator tries to add an element to this that
is already there (which should be safe, but may trigger a table rebuild if we
removed something and haven't checked yet).

Maybe if I had two checks, on for after put and one for after remove. I'll see
if that makes life simpler (and checks faster!).

https://codereview.chromium.org/12254006/diff/2001/sdk/lib/collection/linked_...
sdk/lib/collection/linked_hash_set.dart:106: bool remove = (removeMatching ==
test(key));
On 2013/02/13 15:54:06, floitsch wrote:
> shouldRemove

Done.

https://codereview.chromium.org/12254006/diff/2001/tests/corelib/map_from_tes...
File tests/corelib/map_from_test.dart (right):

https://codereview.chromium.org/12254006/diff/2001/tests/corelib/map_from_tes...
tests/corelib/map_from_test.dart:74: Expect.isTrue(otherMap is !HashMap);
On 2013/02/13 15:54:06, floitsch wrote:
> we usually put the "!" with the "is".

Done.

[floitsch, 2013-02-14 15:54:38]

Still LGTM.

https://chromiumcodereview.appspot.com/12254006/diff/3023/tests/corelib/hash_...
File tests/corelib/hash_map2_test.dart (right):

https://chromiumcodereview.appspot.com/12254006/diff/3023/tests/corelib/hash_...
tests/corelib/hash_map2_test.dart:176: // ForEach-iteartion.
iteration

[Lasse Reichstein Nielsen, 2013-02-15 09:18:12]

https://chromiumcodereview.appspot.com/12254006/diff/3023/tests/corelib/hash_...
File tests/corelib/hash_map2_test.dart (right):

https://chromiumcodereview.appspot.com/12254006/diff/3023/tests/corelib/hash_...
tests/corelib/hash_map2_test.dart:176: // ForEach-iteartion.
On 2013/02/14 15:54:38, floitsch wrote:
> iteration

Done.