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) {
@@ skipping 220 matching lines @@
 
   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);
   }
+
+  V getMinimum() {

[sra1, 2012/02/24 22:21:14]

Can we avoid the use of 'get' in the name of methods?
I know we have getKeys above but I think that is a mistake.

I expect the 'minimum' of an ordered collection to be the minimum key.
That way the minimum would also work when the tree is thought of as a set of
keys.

Since your expectation of what the constitutes a minumum is different to mine,
perhaps it should be made explicit.
minValue() would make it clear that the returned value is a map value and not a
key.
minKey() might also be a useful operation.

K minKey() => root == null ? null : _minNode().key;
V minValue() => root == null ? null : _minNode().value;

Java's SortedMap uses firstKey / lastKey.

Using firstKey might avoid the potential confusion that minKey might also mean
the lowest legal key.

I don't know if optional arguments would be useful in your application:

K firstKey([ifEmpty]) => root == null ? ifEmpty : _minNode().key;
V firstValue([ifEmpty]) => root == null ? ifEmpty : _minNode().value;

var v1 = tree.firstValue();
var v2 = tree.firstValue(ifEmpty: 0);


Please add DartDoc comments since these operations are not described elsewhere.
(It might be nice to add an interface for these operations, since all ordered
Maps could potentially implement them.)

[Anders Johnsen, 2012/02/27 06:22:27]

I agree, firstKey/lastKey is way better. The user can then always perform a
lookup then, to extract the value.

+    if (_root === null) return null;
+    SplayTreeNode<K, V> node = _root;

[sra1, 2012/02/24 22:21:14]

Should min and max splay the tree?

I.e. do you consider them as being in the set of operations with guarantee on
amortized time, or are you OK with worst-case O(N) for repeated min and/or max?

[Anders Johnsen, 2012/02/27 06:22:27]

I'm fine with splaying the tree, makes sense! Added.

+    while (node.left !== null) {
+      node = node.left;
+    }
+    return node.value;
+  }
+
+  V getMaximum() {
+    if (_root === null) return null;
+    SplayTreeNode<K, V> node = _root;
+    while (node.right !== null) {
+      node = node.right;
+    }
+    return node.value;
+  }
+
+  V getPreceding(K key) {

[sra1, 2012/02/24 22:21:14]

It feels slightly wrong that preceding and succeeding return a different type
than the argument - I think of 'preceding' as comparing two things of the same
type as in 'the preceding element'.
Again, it might be useful to have these operations for keys too.
Adding 'value' and 'key' to the name would help with that slightly wrong
feeling.
('following' might be better than 'succeeding' since succeeding could be
confused with success.)
On balance, I would prefer shorter names if they are of equal clarity:

K keyBefore(K key) => ...
V valueAfter(K key) => ...

Compare:
  var x = tree.getSucceeding('100');
  var x = tree.valueSucceeding('100');
  var x = tree.valueFollowing('100');
  var x = tree.valueAfter('100');

[Anders Johnsen, 2012/02/27 06:22:27]

Again, yes, this should be keys. I was using the values directly in my use-case,
but this is a lot more useful. Changed!

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