Add getMinimum, getMaximum, getPreceding and getSucceeding to SplayTree.

corelib/src/implementation/splay_tree.dart

Index: corelib/src/implementation/splay_tree.dart
===================================================================
--- corelib/src/implementation/splay_tree.dart	(revision 4598)
+++ corelib/src/implementation/splay_tree.dart	(working copy)
@@ -7,10 +7,7 @@
  * 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;
@@ -27,7 +24,7 @@
  * 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.
@@ -41,7 +38,7 @@
   // Number of elements in the splay tree.
   int _count;
 
-  SplayTree() {
+  SplayTreeMap() {
     _dummy = new SplayTreeNode<K, V>(null, null);
     _count = 0;
   }
@@ -216,11 +213,12 @@
 
   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() {
@@ -238,4 +236,66 @@
   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);
+  }
 }