Make LinkedHashMap also have a factory constructor and be customizable

Make LinkedHashMap also have a factory constructor and be customizable

R=floitsch@google.com

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

[floitsch, 2013-09-05 13:24:05]

Adding Konstantin for the editor changes.

[ricow1, 2013-09-05 13:43:38]

DBC: testing rietveld

[floitsch, 2013-09-05 13:44:28]

LGTM with comments.

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
File runtime/lib/collection_patch.dart (right):

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:664: implements LinkedHashMap<K, V> {
nit: indentation.

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:713: entry._previousEntry._nextEntry =
entry._nextEntry;
As usual: I prefer temporary variables:
previous = entry._previousEntry;
next = entry._nextEntry;
previous.next = next;
next.previous = previous;
entry.next = entry.previous = null;
...

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:713: entry._previousEntry._nextEntry =
entry._nextEntry;
Starting at this line this code is the same for all implementations.
Maybe add TODO for refactoring to share at least some code.

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:732: void _addEntry(List buckets, int index,
int length,
same code too. right?

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:800: entry._previousEntry._nextEntry =
entry._nextEntry;
temporary variables.

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:888: entry._previousEntry._nextEntry =
entry._nextEntry;
ditto.

https://codereview.chromium.org/23494027/diff/1/sdk/lib/collection/linked_has...
File sdk/lib/collection/linked_hash_map.dart (right):

https://codereview.chromium.org/23494027/diff/1/sdk/lib/collection/linked_has...
sdk/lib/collection/linked_hash_map.dart:22: external factory LinkedHashMap({
bool equals(K key1, K key2),
If we require key1 and key2 to be of type K we might violate our requirements
(allowing lookup of super class).
Please add test, that we don't run into that problem.
Ditto for hashCode.
Alternatively we need to have an is-check in the lookup-functions.

[scheglov, 2013-09-05 15:41:35]

LGTM

[Lasse Reichstein Nielsen, 2013-09-06 08:49:24]

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
File runtime/lib/collection_patch.dart (right):

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:664: implements LinkedHashMap<K, V> {
On 2013/09/05 13:44:28, floitsch wrote:
> nit: indentation.

Done.

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:713: entry._previousEntry._nextEntry =
entry._nextEntry;
On 2013/09/05 13:44:28, floitsch wrote:
> Starting at this line this code is the same for all implementations.

Similar code. It may differ on equality and hashcode computations.
I want to make a version that doesn't duplicate the code unnecessarily, and see
if it's much slower.

> Maybe add TODO for refactoring to share at least some code.

Will do.

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:732: void _addEntry(List buckets, int index,
int length,
Exactly same code in all three sub-classes, yes.

I'll make it a mixin (and hope that won't break anything, including
performance).
In fact, I'll refactory remove to call a _removeEntry that can be specialized in
linked hash maps. That should make all the linked hash maps just one mixin.

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:800: entry._previousEntry._nextEntry =
entry._nextEntry;
On 2013/09/05 13:44:28, floitsch wrote:
> temporary variables.

Done.

https://codereview.chromium.org/23494027/diff/1/runtime/lib/collection_patch....
runtime/lib/collection_patch.dart:888: entry._previousEntry._nextEntry =
entry._nextEntry;
On 2013/09/05 13:44:28, floitsch wrote:
> ditto.

Done.

https://codereview.chromium.org/23494027/diff/1/sdk/lib/collection/linked_has...
File sdk/lib/collection/linked_hash_map.dart (right):

https://codereview.chromium.org/23494027/diff/1/sdk/lib/collection/linked_has...
sdk/lib/collection/linked_hash_map.dart:22: external factory LinkedHashMap({
bool equals(K key1, K key2),
I thought about this and decided that this was the signature to require here. It
will allow more general equalities as well, but won't require them.

That means that you *can* use an equality that only works on E, and then you
better makes sure that you don't *ever* use your map on something that is not E
(but that's the same as SplayTreeMap if your comparator doesn't handle anything
else). But then, we did have a test in the lookup there. I'm not sure we want
that.

[floitsch, 2013-09-06 12:33:19]

LGTM with comments.

https://codereview.chromium.org/23494027/diff/13001/runtime/lib/collection_pa...
File runtime/lib/collection_patch.dart (right):

https://codereview.chromium.org/23494027/diff/13001/runtime/lib/collection_pa...
runtime/lib/collection_patch.dart:720: _HashMapEntry previous,
What's "previous" ?
Add comments.

https://codereview.chromium.org/23494027/diff/13001/sdk/lib/collection/hash_m...
File sdk/lib/collection/hash_map.dart (right):

https://codereview.chromium.org/23494027/diff/13001/sdk/lib/collection/hash_m...
sdk/lib/collection/hash_map.dart:52: * The [isValidKey] method is ignored if
`equals` and `hashCode`
Let's not do that. If supplied it should be called. No user-visible special
cases.

[Lasse Reichstein Nielsen, 2013-09-06 12:52:11]

https://codereview.chromium.org/23494027/diff/13001/runtime/lib/collection_pa...
File runtime/lib/collection_patch.dart (right):

https://codereview.chromium.org/23494027/diff/13001/runtime/lib/collection_pa...
runtime/lib/collection_patch.dart:720: _HashMapEntry previous,
Renamed to "previousInBucket".

https://codereview.chromium.org/23494027/diff/13001/sdk/lib/collection/hash_m...
File sdk/lib/collection/hash_map.dart (right):

https://codereview.chromium.org/23494027/diff/13001/sdk/lib/collection/hash_m...
sdk/lib/collection/hash_map.dart:52: * The [isValidKey] method is ignored if
`equals` and `hashCode`
On 2013/09/06 12:33:20, floitsch wrote:
> Let's not do that. If supplied it should be called. No user-visible special
> cases.

Done.

[Lasse Reichstein Nielsen, 2013-09-06 13:02:14]

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