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 154 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.
+   */
+  K get firstKey() {

[kasperl, 2012/02/27 11:52:34]

I don't think these should be getters. Last/first on List are methods -- so
these should be methods too.

[Anders Johnsen, 2012/02/27 11:58:50]

I would raise the question if last/first on List maybe should be getters then?
Bob's description of a getter fits this description very well. However, we can
always discuss this at a later point in time, so if there are no further
comments, I'll remove 'get' and commit.

[kasperl, 2012/02/27 12:04:32]

Yeah, it's a long discussion. I'm definitely in the camp that only want to use
getters/setters for emulating fields.

+    if (_root === null) return null;
+    SplayTreeNode<K, V> node = _root;
+    while (node.left !== null) {
+      node = node.left;
+    }
+    splay_(node.key);
+    return node.key;
+  }
+
+  /**
+   * Get the last key in the map. Returns [ifEmpty] if the map is empty.
+   */
+  V get 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);
+  }
 }