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)
@@ -238,4 +238,62 @@
   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;
+  }
 }