Cleanups in collection.

sdk/lib/collection/splay_tree.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of dart.collection;
 
 /**
  * A node in a splay tree. It holds the sorting key and the left
  * and right children in the tree.
  */
@@ skipping 18 matching lines @@
 /**
  * A splay tree is a self-balancing binary search tree.
  *
  * It has the additional property that recently accessed elements
  * are quick to access again.
  * It performs basic operations such as insertion, look-up and
  * removal, in O(log(n)) amortized time.
  */
 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.
   int _count = 0;
 
   /**
    * Counter incremented whenever the keys in the map changes.
    *
    * Used to detect concurrent modifications.
    */
@@ skipping 73 matching lines @@
     current.left = _dummy.right;
     current.right = _dummy.left;
     _root = current;
 
     _dummy.right = null;
     _dummy.left = null;
     _splayCount++;
     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);
     if (comp != 0) return null;
     _SplayTreeNode result = _root;
     _count--;
     // assert(_count >= 0);
     if (_root.left == null) {
       _root = _root.right;
     } else {
@@ skipping 30 matching lines @@
     } else {
       node.right = _root;
       node.left = _root.left;
       _root.left = null;
     }
     _root = node;
   }
 
   _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() {
     _root = null;
     _count = 0;
     _modificationCount++;
   }
 }
 
 /*
  * A [Map] of objects that can be ordered relative to each other.
  *
  * The map is based on a self-balancing binary tree. It allows most operations
  * in amortized logarithmic time.
  *
  * 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)])
       : _comparator = (compare == null) ? Comparable.compare : compare;
 
   int _compare(K key1, K key2) => _comparator(key1, key2);
 
   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;
     }
     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);
     if (comp == 0) {
       _root.value = value;
       return;
     }
     _addNewRoot(new _SplayTreeMapNode(key, value), comp);
   }
 
 
   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;
     int splayCount = _splayCount;
     V value = ifAbsent();
     if (modificationCount != _modificationCount) {
       throw new ConcurrentModificationError(this);
     }
     if (splayCount != _splayCount) {
       comp = _splay(key);
@@ skipping 26 matching lines @@
   void clear() {
     _clear();
   }
 
   bool containsKey(K key) {
     return _splay(key) == 0;
   }
 
   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);
   }
 
   Iterable<K> get keys => new _SplayTreeKeyIterable<K>(this);
 
   Iterable<V> get values => new _SplayTreeValueIterable<K, V>(this);
 
   String toString() {
     return Maps.mapToString(this);
   }
 
   /**
    * 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;
   }
 
   /**
    * Get the last key in the map that is strictly smaller than [key]. Returns
    * [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;
     _SplayTreeNode<K> node = _root.left;
     if (node == null) return null;
     while (node.right != null) {
       node = node.right;
     }
     return node.key;
   }
 
   /**
    * Get the first key in the map that is strictly larger than [key]. Returns
    * [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;
     _SplayTreeNode<K> node = _root.right;
     if (node == null) return null;
     while (node.left != null) {
       node = node.left;
     }
     return node.key;
   }
@@ skipping 118 matching lines @@
 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> {
   _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map);
   V _getValue(_SplayTreeMapNode node) => node.value;
 }
 
 class _SplayTreeNodeIterator<K>
     extends _SplayTreeIterator<_SplayTreeNode<K>> {
   _SplayTreeNodeIterator(_SplayTree<K> map): super(map);
   _SplayTreeNode<K> _getValue(_SplayTreeNode node) => node;
 }