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) {

[kasperl, 2012/02/27 06:50:03]

Use this.key and this.value?

[Anders Johnsen, 2012/02/27 09:06:51]

Done.

     key = k;
     value = v;
   }
 
   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> {

[kasperl, 2012/02/27 06:50:03]

Long term, it would be great with both a map and a set variant of this. It seems
fairly easy to abstract out the creation of the internal nodes. Maybe we should
rename this to SplayTreeMap right away?

[Anders Johnsen, 2012/02/27 09:06:51]

Yep, renamed!

 
   // 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;
 
@@ skipping 171 matching lines @@
       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; });

[kasperl, 2012/02/27 06:50:03]

I guess there's no need to do containsValue in order so a much simpler
implementation than the one in forEach should work fine.

[Anders Johnsen, 2012/02/27 09:06:51]

Done.

     return found;
   }
 
   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 firstKey([K ifEmpty]) {

[kasperl, 2012/02/27 06:50:03]

Have you considered making ifEmpty a closure instead (like putIfAbsent)? At
least it is something we should consider in general.

[Søren Gjesse, 2012/02/27 07:53:16]

Why not just return null if the splay tree is empty? As far as I can see null is
not a valid key anyway. The this function can also become a getter. Same for the
other methods with ifEmpty and ifInvalid arguments.

[kasperl, 2012/02/27 08:53:17]

I think we should go with Søren's proposal for now (just returning null). It
fits better with the other methods in map (like []).

[Anders Johnsen, 2012/02/27 09:06:51]

If we return null, then map[] should support null index as well. Otherwise we
will not be able to do 

  var firstValue = map[map.firstKey()];

I have the option of doing 

  var firstValue = map[map.firstKey(-1)];

with the current implementation.

Is that okay with you guys?

[kasperl, 2012/02/27 09:18:45]

I actually find it hard to read the line:

  var firstValue = map[map.firstKey(-1)];

I guess it returns null if the key doesn't exist and there is no mapping for -1?
Seems pretty brittle to me. I'd prefer something like:

  var firstValue = map.isEmpty() 
      : null 
      ? map[map.firstKey()];

[Anders Johnsen, 2012/02/27 11:49:59]

Yeah, I've turned them into a getter. Thank you!

+    if (_root === null) return ifEmpty;
+    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 lastKey([K ifEmpty]) {
+    if (_root === null) return ifEmpty;
+    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 then [key]. Returns

[kasperl, 2012/02/27 06:50:03]

then -> than

[Anders Johnsen, 2012/02/27 09:06:51]

Done.

+   * [ifInvalid] if [key] was not found.
+   */
+  K keyBefore(K key, [K ifInvalid]) {

[kasperl, 2012/02/27 06:50:03]

lastKeyBefore?

[Anders Johnsen, 2012/02/27 09:06:51]

Hmm, to me this sort of implies I could give any key, even one that is not in
the map. That is not true. So,

1) rename and change implementation
2) keep name and implementation.

What you think?

[kasperl, 2012/02/27 09:18:45]

To me the term 'keyBefore' is almost the same as 'anyKeyBefore' which is
definitely not what you want, but I could be the only one who reads it that way.
In terms of the requirement that the key has to be present in the map, I don't
think there is any different between keyBefore and lastKeyBefore (at least not
in how I interpret them).

[Anders Johnsen, 2012/02/27 11:49:59]

I agree, and it makes a lot more sense the more I think about it. I've updated
my implementation.

+    splay_(key);
+    if (_root === null || key.compareTo(_root.key) != 0) return ifInvalid;
+    SplayTreeNode<K, V> node = _root;
+    if (node.left === null) return ifInvalid;
+    node = node.left;
+    while (node.right !== null) {
+      node = node.right;
+    }
+    return node.key;
+  }
+
+  /**
+   * Get the first key in the map that is strictly larger then [key]. Returns

[kasperl, 2012/02/27 06:50:03]

then -> than

[Anders Johnsen, 2012/02/27 09:06:51]

Done.

+   * [ifInvalid] if [key] was not found.
+   */
+  K keyAfter(K key, [K ifInvalid]) {

[kasperl, 2012/02/27 06:50:03]

firstKeyAfter?

[Anders Johnsen, 2012/02/27 09:06:51]

Same as above.

+    splay_(key);
+    if (_root === null || key.compareTo(_root.key) != 0) return ifInvalid;
+    SplayTreeNode<K, V> node = _root;
+    if (node.right === null) return ifInvalid;
+    node = node.right;
+    while (node.left !== null) {
+      node = node.left;
+    }
+    return node.key;
+  }
 }