Update SplayTreeMap implementation.

Update SplayTreeMap implementation.

Make keys and values getters lazy.

Update iteration to not serialize the keys first.
Iteration attempts to traverse the tree without modifying it, but
recovers if someone modifies the tree structure while iterating,
which a simple lookup will do.
It throws, as other maps, if keys are added or removed during iteration.
Add concurrent modification catching for iteration and putIfAbsent.

Make _splay actually private.

BUG=http://dartbug.com/4421

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

[floitsch, 2013-02-15 10:04:48]

LGTM.
I don't really like that the iterator splays his current node to the top, but
that's not for this CL.
We might want to switch to a different sorted map anyways.

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
File sdk/lib/collection/splay_tree.dart (right):

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:52: * Used to detect that an in-place
traversal
unfinished sentence.

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:222: if (comp == 0) {
Can this happen?
We didn't find the comp before, and the modfification-count didn't change.
Afaics we cannot have a comp==0 now.

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:264: // TODO(lrn): Do we want to handle the
case where node.value.operator==
I guess we need to eventually.

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:366: * If the splay count on [_map]
increases, [_path] becomes invalid.
_workList

[Lasse Reichstein Nielsen, 2013-02-15 13:46:37]

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
File sdk/lib/collection/splay_tree.dart (right):

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:52: * Used to detect that an in-place
traversal
Finished.

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:222: if (comp == 0) {
Good catch.

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:264: // TODO(lrn): Do we want to handle the
case where node.value.operator==
We have to do the same for compareTo in _splay. That's going to get ugly. Maybe
just make _splay non-reentrant.

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:366: * If the splay count on [_map]
increases, [_path] becomes invalid.
On 2013/02/15 10:04:49, floitsch wrote:
> _workList

Done.

[floitsch, 2013-02-15 13:58:25]

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
File sdk/lib/collection/splay_tree.dart (right):

https://codereview.chromium.org/12260058/diff/1/sdk/lib/collection/splay_tree...
sdk/lib/collection/splay_tree.dart:264: // TODO(lrn): Do we want to handle the
case where node.value.operator==
On 2013/02/15 13:46:37, Lasse Reichstein Nielsen wrote:
> We have to do the same for compareTo in _splay. That's going to get ugly.
Maybe
> just make _splay non-reentrant.

Let's look at that later.