Add getMinimum, getMaximum, getPreceding and getSucceeding to SplayTree.

corelib/src/implementation/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.
 
 /**
  * A node in a splay tree. It holds the key, the value and the left
  * and right children in the tree.
  */
 class SplayTreeNode<K, V> {
-  SplayTreeNode(K k, V v) {
-    key = k;
-    value = v;
-  }
+  SplayTreeNode(K this.key, V this.value);
 
   K key;
   V value;
   SplayTreeNode<K, V> left;
   SplayTreeNode<K, V> right;
 }
 
 /**
  * A splay tree is a self-balancing binary
  * search tree with 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.
  *
  * This implementation is a Dart version of the JavaScript
  * implementation in the V8 project.
  */
-class SplayTree<K extends Comparable, V> implements Map<K, V> {
+class SplayTreeMap<K extends Comparable, V> implements Map<K, V> {
 
   // The root node of the splay tree. It will contain either the last
   // element inserted, or the last element looked up.
   SplayTreeNode<K, V> _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.
   SplayTreeNode<K, V> _dummy;
 
   // Number of elements in the splay tree.
   int _count;
 
-  SplayTree() {
+  SplayTreeMap() {
     _dummy = new SplayTreeNode<K, V>(null, null);
     _count = 0;
   }
 
   /**
    * Perform the splay operation for the given key. Moves the node with
    * the given key to the top of the tree.  If no node has the given
    * key, the last node on the search path is moved to the top of the
    * tree. This is the simplified top-down splaying algorithm from:
    * "Self-adjusting Binary Search Trees" by Sleator and Tarjan.
@@ skipping 16 matching lines @@
           SplayTreeNode<K, V> tmp = current.left;
           current.left = tmp.right;
           tmp.right = current;
           current = tmp;
           if (current.left === null) break;
         }
         // Link right.
         right.left = current;
         right = current;
         current = current.left;
       } else if (key.compareTo(current.key) > 0) {

[sra1, 2012/02/27 23:46:04]

You could improve this by caching the value returned by
key.compareTo(current.key) in a local.

[Anders Johnsen, 2012/02/28 12:25:18]

I don't expect this to be a huge improvement, but done.

         if (current.right === null) break;
         if (key.compareTo(current.right.key) > 0) {
           // Rotate left.
           SplayTreeNode<K, V> tmp = current.right;
           current.right = tmp.left;
           tmp.left = current;
           current = tmp;
           if (current.right === null) break;
         }
         // Link left.
@@ skipping 117 matching lines @@
   bool containsKey(K key) {
     if (!isEmpty()) {
       splay_(key);
       if (_root.key.compareTo(key) == 0) return true;
     }
     return false;
   }
 
   bool containsValue(V value) {
     bool found = false;
-    // Note: Worst performance you can get because we don't have
-    // non-local return.
-    // TODO: optimize this method with a similar code than forEach.
-    forEach((Object k, Object v) { if (value == v) found = true; });
-    return found;
+    bool visit(SplayTreeNode node) {
+      if (node === null) return false;
+      if (node.value == value) return true;
+      return visit(node.left) || visit(node.right);
+    }
+    return visit(_root);
   }
 
   Collection<K> getKeys() {
     List<K> list = new List<K>();
     forEach((K k, V v) { list.add(k); });
     return list;
   }
 
   Collection<V> getValues() {
     List<V> list = new List<V>();
     forEach((K k, V v) { list.add(v); });
     return list;
   }
 
   String toString() {
     return Maps.mapToString(this);
   }
+
+  /**
+   * Get the first key in the map. Returns [ifEmpty] if the map is empty.

[sra1, 2012/02/27 23:46:04]

There is no ifEmpty parameter.  Since it is a key and null is not comparable,
just fix the doc.

[Anders Johnsen, 2012/02/28 12:25:18]

Ah yes, ty!

+   */
+  K firstKey() {
+    if (_root === null) return null;
+    SplayTreeNode<K, V> node = _root;
+    while (node.left !== null) {
+      node = node.left;
+    }
+    splay_(node.key);

[sra1, 2012/02/27 23:46:04]

One does wonder if there is a concise specialization of splay that can do the
splaying with no comparisons since they key is the minimum.  Add a comment?

+    return node.key;
+  }
+
+  /**
+   * Get the last key in the map. Returns [ifEmpty] if the map is empty.

[sra1, 2012/02/27 23:46:04]

Ditto.

[Anders Johnsen, 2012/02/28 12:25:18]

Done.

+   */
+  V lastKey() {
+    if (_root === null) return null;
+    SplayTreeNode<K, V> node = _root;
+    while (node.right !== null) {
+      node = node.right;
+    }
+    splay_(node.key);
+    return node.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) {
+    splay_(key);
+    K visit(SplayTreeNode node, [K ifEmpty]) {
+      if (node === null) return ifEmpty;
+      if (node.key.compareTo(key) >= 0) {
+        return visit(node.left, ifEmpty);
+      }
+      if (node.key.compareTo(key) < 0) {
+        return visit(node.right, node.key);
+      }
+    }
+    return visit(_root);
+  }
+
+  /**
+   * 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) {
+    splay_(key);
+    K visit(SplayTreeNode node, [K ifEmpty]) {
+      if (node === null) return ifEmpty;
+      if (node.key.compareTo(key) > 0) {
+        return visit(node.left, node.key);
+      }
+      if (node.key.compareTo(key) <= 0) {
+        return visit(node.right, ifEmpty);
+      }
+    }
+    return visit(_root);
+  }
 }