Cleanups in collection.

sdk/lib/collection/splay_tree.dart

Index: sdk/lib/collection/splay_tree.dart
diff --git a/sdk/lib/collection/splay_tree.dart b/sdk/lib/collection/splay_tree.dart
index 53707f13b3d78a43051960c4937987ccbaa6da1b..d3a6076d67b74179f6e2b19335641f43622b5b13 100644
--- a/sdk/lib/collection/splay_tree.dart
+++ b/sdk/lib/collection/splay_tree.dart
@@ -36,13 +36,11 @@ class _SplayTreeMapNode<K, V> extends _SplayTreeNode<K> {
  */
 abstract class _SplayTree<K> {
   // The root node of the splay tree. It will contain either the last
-  // element inserted, or the last element looked up.
+  // element inserted or the last element looked up.
   _SplayTreeNode<K> _root;
 
-  // The dummy node used when performing a splay on the tree. It is a
-  // local field of the class to avoid allocating a node each time a
-  // splay is performed.
-  // TODO(lrn); Should it be a getter backed by a static instead?
+  // The dummy node used when performing a splay on the tree. Reusing it
+  // avoids allocating a node each time a splay is performed.
   _SplayTreeNode<K> _dummy = new _SplayTreeNode<K>(null);
 
   // Number of elements in the splay tree.
@@ -136,6 +134,34 @@ abstract class _SplayTree<K> {
     return comp;
   }
 
+  // Emulates splaying with a key that is smaller than any in the tree.
+  // After this, the least element in the tree is the root.

[floitsch, 2013/03/11 13:34:28]

smallest

[Lasse Reichstein Nielsen, 2013/03/12 12:01:06]

Done.

+  void _splayMin() {
+    if (_root == null) return;
+    _SplayTreeNode current = _root;
+    while (current.left != null) {
+      _SplayTreeNode left = current.left;
+      current.left = left.right;
+      left.right = current;
+      current = left;
+    }
+    _root = current;
+  }
+
+  // Emulates splaying with a key that is greater than any in the tree.
+  // After this, the largest element in the tree is the root.
+  void _splayMax() {
+    if (_root == null) return;
+    _SplayTreeNode current = _root;
+    while (current.right != null) {
+      _SplayTreeNode right = current.right;
+      current.right = right.left;
+      right.left = current;
+      current = right;
+    }
+    _root = current;
+  }
+
   _SplayTreeNode _remove(K key) {
     if (_root == null) return null;
     int comp = _splay(key);
@@ -186,26 +212,14 @@ abstract class _SplayTree<K> {
 
   _SplayTreeNode get _first {
     if (_root == null) return null;
-    _SplayTreeNode<K> node = _root;
-    while (node.left != null) {
-      node = node.left;
-    }
-    // Maybe implement a splay-method that can splay the minimum without
-    // performing comparisons.
-    _splay(node.key);
-    return node;
+    _splayMin();
+    return _root;
   }
 
   _SplayTreeNode get _last {
     if (_root == null) return null;
-    _SplayTreeNode<K> node = _root;
-    while (node.right != null) {
-      node = node.right;
-    }
-    // Maybe implement a splay-method that can splay the minimum without
-    // performing comparisons.
-    _splay(node.key);
-    return node;
+    _splayMax();
+    return _root;
   }
 
   void _clear() {
@@ -224,11 +238,11 @@ abstract class _SplayTree<K> {
  * Keys of the map are compared using the `compare` function passed in
  * the constructor. If that is omitted, the objects are assumed to be
  * [Comparable], and are compared using their [Comparable.compareTo]
- * method.
+ * method. This also means that `null` is *not* allowed as a key.
  */
 class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
   // TODO(ngeoffray): Restore type when feature is implemented in dart2js
-  // checked mode. http://dartbug.com/7733  
+  // checked mode. http://dartbug.com/7733
   Function /* Comparator<K> */_comparator;
 
   SplayTreeMap([int compare(K key1, K key2)])
@@ -239,6 +253,7 @@ class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
   SplayTreeMap._internal();
 
   V operator [](K key) {
+    if (key == null) throw new ArgumentError(key);
     if (_root != null) {
       int comp = _splay(key);
       if (comp == 0) return _root.value;
@@ -246,13 +261,15 @@ class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
     return null;
   }
 
-  V remove(K key) {
+  V remove(Object key) {
+    if (key is! K) return null;
     _SplayTreeMapNode root = _remove(key);
     if (root != null) return root.value;
     return null;
   }
 
   void operator []=(K key, V value) {
+    if (key == null) throw new ArgumentError(key);
     // Splay on the key to move the last node on the search path for
     // the key to the root of the tree.
     int comp = _splay(key);
@@ -265,6 +282,7 @@ class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
 
 
   V putIfAbsent(K key, V ifAbsent()) {
+    if (key == null) throw new ArgumentError(key);
     int comp = _splay(key);
     if (comp == 0) return _root.value;
     int modificationCount = _modificationCount;
@@ -311,12 +329,17 @@ class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
 
   bool containsValue(V value) {
     bool found = false;
+    int initialSplayCount = _splayCount;
     bool visit(_SplayTreeNode node) {
-      if (node == null) return false;
-      if (node.value == value) return true;
-      // TODO(lrn): Do we want to handle the case where node.value.operator==
-      // modifies the map?
-      return visit(node.left) || visit(node.right);
+      while (node != null) {
+        if (node.value == value) return true;
+        if (initialSplayCount != _splayCount) {
+          throw new ConcurrentModificationError(this);
+        }
+        if (node.right != null && visit(node.right)) return true;
+        node = node.left;
+      }
+      return false;
     }
     return visit(_root);
   }
@@ -333,16 +356,16 @@ class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
    * Get the first key in the map. Returns [null] if the map is empty.
    */
   K firstKey() {
-    _SplayTreeNode node = _first;
-    return (node == null) ? null : node.key;
+    if (_root == null) return null;
+    return _first.key;
   }
 
   /**
    * Get the last key in the map. Returns [null] if the map is empty.
    */
   K lastKey() {
-    _SplayTreeNode node = _last;
-    return (node == null) ? null : node.key;
+    if (_root == null) return null;
+    return _last.key;
   }
 
   /**
@@ -350,6 +373,7 @@ class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
    * [null] if no key was not found.
    */
   K lastKeyBefore(K key) {
+    if (key == null) throw new ArgumentError(key);
     if (_root == null) return null;
     int comp = _splay(key);
     if (comp < 0) return _root.key;
@@ -366,6 +390,7 @@ class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
    * [null] if no key was not found.
    */
   K firstKeyAfter(K key) {
+    if (key == null) throw new ArgumentError(key);
     if (_root == null) return null;
     int comp = _splay(key);
     if (comp > 0) return _root.key;