From a0b1db4ce72e2f449de9ce2da2b6b0958bc33579 Mon Sep 17 00:00:00 2001
From: James Iry <jamesiry@gmail.com>
Date: Mon, 11 Feb 2013 12:44:21 -0800
Subject: SI-6642 Code cleanup on RedBlackTree#TreeIterator

In anticipation of some work needed to implement iteratorFrom, this
commit does some variable renaming and general code clean up on
RedBlackTree's TreeIterator.
---
 .../scala/collection/immutable/RedBlackTree.scala  | 45 ++++++++++++----------
 1 file changed, 24 insertions(+), 21 deletions(-)

diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala
index 99f8d95517..004c0ae8c6 100644
--- a/src/library/scala/collection/immutable/RedBlackTree.scala
+++ b/src/library/scala/collection/immutable/RedBlackTree.scala
@@ -425,32 +425,28 @@ object RedBlackTree {
     def unapply[A, B](t: BlackTree[A, B]) = Some((t.key, t.value, t.left, t.right))
   }
 
-  private[this] abstract class TreeIterator[A, B, R](tree: Tree[A, B]) extends Iterator[R] {
+  private[this] abstract class TreeIterator[A, B, R](root: Tree[A, B]) extends Iterator[R] {
     protected[this] def nextResult(tree: Tree[A, B]): R
 
-    override def hasNext: Boolean = next ne null
+    override def hasNext: Boolean = lookahead ne null
 
-    override def next: R = next match {
+    override def next: R = lookahead match {
       case null =>
         throw new NoSuchElementException("next on empty iterator")
       case tree =>
-        next = findNext(tree.right)
+        lookahead = findLeftMostOrPopOnEmpty(goRight(tree))
         nextResult(tree)
     }
 
     @tailrec
-    private[this] def findNext(tree: Tree[A, B]): Tree[A, B] = {
-      if (tree eq null) popPath()
+    private[this] def findLeftMostOrPopOnEmpty(tree: Tree[A, B]): Tree[A, B] =
+      if (tree eq null) popNext()
       else if (tree.left eq null) tree
-      else {
-        pushPath(tree)
-        findNext(tree.left)
-      }
-    }
+      else findLeftMostOrPopOnEmpty(goLeft(tree))
 
-    private[this] def pushPath(tree: Tree[A, B]) {
+    private[this] def pushNext(tree: Tree[A, B]) {
       try {
-        path(index) = tree
+        stackOfNexts(index) = tree
         index += 1
       } catch {
         case _: ArrayIndexOutOfBoundsException =>
@@ -462,17 +458,17 @@ object RedBlackTree {
            * An exception handler is used instead of an if-condition to optimize the normal path.
            * This makes a large difference in iteration speed!
            */
-          assert(index >= path.length)
-          path :+= null
-          pushPath(tree)
+          assert(index >= stackOfNexts.length)
+          stackOfNexts :+= null
+          pushNext(tree)
       }
     }
-    private[this] def popPath(): Tree[A, B] = if (index == 0) null else {
+    private[this] def popNext(): Tree[A, B] = if (index == 0) null else {
       index -= 1
-      path(index)
+      stackOfNexts(index)
     }
 
-    private[this] var path = if (tree eq null) null else {
+    private[this] var stackOfNexts = if (root eq null) null else {
       /*
        * According to "Ralf Hinze. Constructing red-black trees" [http://www.cs.ox.ac.uk/ralf.hinze/publications/#P5]
        * the maximum height of a red-black tree is 2*log_2(n + 2) - 2.
@@ -481,11 +477,18 @@ object RedBlackTree {
        *
        * We also don't store the deepest nodes in the path so the maximum path length is further reduced by one.
        */
-      val maximumHeight = 2 * (32 - Integer.numberOfLeadingZeros(tree.count + 2 - 1)) - 2 - 1
+      val maximumHeight = 2 * (32 - Integer.numberOfLeadingZeros(root.count + 2 - 1)) - 2 - 1
       new Array[Tree[A, B]](maximumHeight)
     }
     private[this] var index = 0
-    private[this] var next: Tree[A, B] = findNext(tree)
+    private[this] var lookahead: Tree[A, B] = findLeftMostOrPopOnEmpty(root)
+   
+    private[this] def goLeft(tree: Tree[A, B]) = {
+      pushNext(tree)
+      tree.left
+    }
+    
+    private[this] def goRight(tree: Tree[A, B]) = tree.right
   }
 
   private[this] class EntriesIterator[A, B](tree: Tree[A, B]) extends TreeIterator[A, B, (A, B)](tree) {
-- 
cgit v1.2.3


From 62bc99d3b20a7b37a977b19a6202cdac474eb5f6 Mon Sep 17 00:00:00 2001
From: James Iry <jamesiry@gmail.com>
Date: Mon, 11 Feb 2013 12:55:06 -0800
Subject: SI-6642 Adds iteratorFrom, keysIteratorFrom, and valuesIteratorFrom

Adds the ability to efficiently create an iterator that starts at a
given key or element of a sorted set or map. Similar work is done for
key and value only iterators on maps.

The bulk of the work is in RedBlackTree. Most of the rest is pushing
the new api methods throughout the appropriate spots in the collection
API.

This commit leaves undone some similar work possible on mutable TreeSets
---
 src/library/scala/Enumeration.scala                |  1 +
 src/library/scala/collection/BitSetLike.scala      |  6 +-
 src/library/scala/collection/SortedMapLike.scala   | 29 +++++++++
 src/library/scala/collection/SortedSetLike.scala   | 10 ++++
 src/library/scala/collection/generic/Sorted.scala  | 12 ++++
 .../scala/collection/immutable/RedBlackTree.scala  | 32 +++++++---
 .../scala/collection/immutable/SortedMap.scala     |  6 ++
 .../scala/collection/immutable/TreeMap.scala       |  4 ++
 .../scala/collection/immutable/TreeSet.scala       |  1 +
 src/library/scala/collection/mutable/TreeSet.scala | 17 ++++++
 test/files/run/iterator-from.scala                 | 69 ++++++++++++++++++++++
 11 files changed, 177 insertions(+), 10 deletions(-)
 create mode 100644 test/files/run/iterator-from.scala

diff --git a/src/library/scala/Enumeration.scala b/src/library/scala/Enumeration.scala
index 21f0c8fd3e..e7ce21b229 100644
--- a/src/library/scala/Enumeration.scala
+++ b/src/library/scala/Enumeration.scala
@@ -255,6 +255,7 @@ abstract class Enumeration (initial: Int) extends Serializable {
     def + (value: Value) = new ValueSet(nnIds + (value.id - bottomId))
     def - (value: Value) = new ValueSet(nnIds - (value.id - bottomId))
     def iterator = nnIds.iterator map (id => thisenum.apply(id + bottomId))
+    override def keysIteratorFrom(start: Value) = nnIds keysIteratorFrom start.id  map (id => thisenum.apply(id + bottomId))
     override def stringPrefix = thisenum + ".ValueSet"
     /** Creates a bit mask for the zero-adjusted ids in this set as a
      *  new array of longs */
diff --git a/src/library/scala/collection/BitSetLike.scala b/src/library/scala/collection/BitSetLike.scala
index d0f4e323c7..bf05331cb1 100644
--- a/src/library/scala/collection/BitSetLike.scala
+++ b/src/library/scala/collection/BitSetLike.scala
@@ -98,8 +98,10 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
     fromBitMaskNoCopy(a)
   }
 
-  def iterator: Iterator[Int] = new AbstractIterator[Int] {
-    private var current = 0
+  def iterator: Iterator[Int] = iteratorFrom(0)
+  
+  override def keysIteratorFrom(start: Int) = new AbstractIterator[Int] {
+    private var current = start
     private val end = nwords * WordLength
     def hasNext: Boolean = {
       while (current < end && !self.contains(current)) current += 1
diff --git a/src/library/scala/collection/SortedMapLike.scala b/src/library/scala/collection/SortedMapLike.scala
index 57ad3497c7..3c3e6095df 100644
--- a/src/library/scala/collection/SortedMapLike.scala
+++ b/src/library/scala/collection/SortedMapLike.scala
@@ -42,6 +42,7 @@ self =>
       val map = self.rangeImpl(from, until)
       new map.DefaultKeySortedSet
     }
+    override def keysIteratorFrom(start: A) = self.keysIteratorFrom(start)
   }
 
   /** Add a key/value pair to this map.
@@ -76,11 +77,17 @@ self =>
   override def filterKeys(p: A => Boolean): SortedMap[A, B] = new FilteredKeys(p) with SortedMap.Default[A, B] {
     implicit def ordering: Ordering[A] = self.ordering
     override def rangeImpl(from : Option[A], until : Option[A]): SortedMap[A, B] = self.rangeImpl(from, until).filterKeys(p)
+    override def iteratorFrom(start: A) = self iteratorFrom start filter {case (k, _) => p(k)}
+    override def keysIteratorFrom(start: A) = self keysIteratorFrom start filter p
+    override def valuesIteratorFrom(start: A) = self iteratorFrom start collect {case (k,v) if p(k) => v}
   }
   
   override def mapValues[C](f: B => C): SortedMap[A, C] = new MappedValues(f) with SortedMap.Default[A, C] {
     implicit def ordering: Ordering[A] = self.ordering
     override def rangeImpl(from : Option[A], until : Option[A]): SortedMap[A, C] = self.rangeImpl(from, until).mapValues(f)
+    override def iteratorFrom(start: A) = (self iteratorFrom start) map {case (k,v) => (k, f(v))}
+    override def keysIteratorFrom(start: A) = self keysIteratorFrom start
+    override def valuesIteratorFrom(start: A) = self valuesIteratorFrom start map f
   }
   
   /** Adds a number of elements provided by a traversable object
@@ -91,6 +98,28 @@ self =>
   override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): SortedMap[A, B1] =
     ((repr: SortedMap[A, B1]) /: xs.seq) (_ + _)
   
+  /**
+   * Creates an iterator over all the key/value pairs
+   * contained in this map having a key greater than or
+   * equal to `start` according to the ordering of
+   * this map. x.iteratorFrom(y) is equivalent
+   * to but often more efficient than x.from(y).iterator.
+   * 
+   * @param start The lower bound (inclusive)
+   * on the keys to be returned
+   */
+  def iteratorFrom(start: A): Iterator[(A, B)]
+  /**
+   * Creates an iterator over all the values contained in this
+   * map that are associated with a key greater than or equal to `start`
+   * according to the ordering of this map. x.valuesIteratorFrom(y) is
+   * equivalent to but often more efficient than 
+   * x.from(y).valuesIterator.
+   * 
+   * @param start The lower bound (inclusive)
+   * on the keys to be returned
+   */
+  def valuesIteratorFrom(start: A): Iterator[B]
 }
 
 
diff --git a/src/library/scala/collection/SortedSetLike.scala b/src/library/scala/collection/SortedSetLike.scala
index 71b45c72ff..6d1d1ac111 100644
--- a/src/library/scala/collection/SortedSetLike.scala
+++ b/src/library/scala/collection/SortedSetLike.scala
@@ -40,4 +40,14 @@ self =>
     case that: SortedSet[_] if that.ordering == ordering => that.hasAll(this.iterator)
     case that => super.subsetOf(that)
   }
+
+  /**
+   * Creates an iterator that contains all values from this collection
+   * greater than or equal to `start` according to the ordering of
+   * this collection. x.iteratorFrom(y) is equivalent to but will usually
+   * be more efficient than x.from(y).iterator
+   * 
+   * @param start The lower-bound (inclusive) of the iterator
+   */
+  def iteratorFrom(start: A): Iterator[A] = keysIteratorFrom(start)
 }
diff --git a/src/library/scala/collection/generic/Sorted.scala b/src/library/scala/collection/generic/Sorted.scala
index f962b26bd3..b3847fffc9 100644
--- a/src/library/scala/collection/generic/Sorted.scala
+++ b/src/library/scala/collection/generic/Sorted.scala
@@ -78,6 +78,18 @@ trait Sorted[K, +This <: Sorted[K, This]] {
     else
       until(next)
   }
+  
+  /**
+   * Creates an iterator over all the keys(or elements)  contained in this
+   * collection greater than or equal to `start`
+   * according to the ordering of this collection. x.keysIteratorFrom(y) 
+   * is equivalent to but often more efficient than 
+   * x.from(y).keysIterator.
+   * 
+   * @param start The lower bound (inclusive)
+   * on the keys to be returned
+   */
+  def keysIteratorFrom(start: K): Iterator[K]
 
   protected def hasAll(j: Iterator[K]): Boolean = {
     val i = keySet.iterator
diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala
index 004c0ae8c6..c0d46765be 100644
--- a/src/library/scala/collection/immutable/RedBlackTree.scala
+++ b/src/library/scala/collection/immutable/RedBlackTree.scala
@@ -91,9 +91,9 @@ object RedBlackTree {
     if (tree.right ne null) _foreachKey(tree.right, f)
   }
 
-  def iterator[A, B](tree: Tree[A, B]): Iterator[(A, B)] = new EntriesIterator(tree)
-  def keysIterator[A, _](tree: Tree[A, _]): Iterator[A] = new KeysIterator(tree)
-  def valuesIterator[_, B](tree: Tree[_, B]): Iterator[B] = new ValuesIterator(tree)
+  def iterator[A, B](tree: Tree[A, B], start: Option[A] = None)(implicit ordering: Ordering[A]): Iterator[(A, B)] = new EntriesIterator(tree, start)
+  def keysIterator[A, _](tree: Tree[A, _], start: Option[A] = None)(implicit ordering: Ordering[A]): Iterator[A] = new KeysIterator(tree, start)
+  def valuesIterator[A, B](tree: Tree[A, B], start: Option[A] = None)(implicit ordering: Ordering[A]): Iterator[B] = new ValuesIterator(tree, start)
 
   @tailrec
   def nth[A, B](tree: Tree[A, B], n: Int): Tree[A, B] = {
@@ -425,7 +425,7 @@ object RedBlackTree {
     def unapply[A, B](t: BlackTree[A, B]) = Some((t.key, t.value, t.left, t.right))
   }
 
-  private[this] abstract class TreeIterator[A, B, R](root: Tree[A, B]) extends Iterator[R] {
+  private[this] abstract class TreeIterator[A, B, R](root: Tree[A, B], start: Option[A])(implicit ordering: Ordering[A]) extends Iterator[R] {
     protected[this] def nextResult(tree: Tree[A, B]): R
 
     override def hasNext: Boolean = lookahead ne null
@@ -481,7 +481,23 @@ object RedBlackTree {
       new Array[Tree[A, B]](maximumHeight)
     }
     private[this] var index = 0
-    private[this] var lookahead: Tree[A, B] = findLeftMostOrPopOnEmpty(root)
+    private[this] var lookahead: Tree[A, B] = start map startFrom getOrElse findLeftMostOrPopOnEmpty(root)
+    
+    /**
+     * Find the leftmost subtree whose key is equal to the given key, or if no such thing, 
+     * the leftmost subtree with the key that would be "next" after it according
+     * to the ordering. Along the way build up the iterator's path stack so that "next"
+     * functionality works.
+     */
+    private[this] def startFrom(key: A) : Tree[A,B] = if (root eq null) null else {
+      @tailrec def find(tree: Tree[A, B]): Tree[A, B] = 
+        if (tree == null) popNext
+        else find(
+          if (ordering.lteq(key, tree.key)) goLeft(tree)
+          else goRight(tree)
+        )      
+      find(root)
+    }
    
     private[this] def goLeft(tree: Tree[A, B]) = {
       pushNext(tree)
@@ -491,15 +507,15 @@ object RedBlackTree {
     private[this] def goRight(tree: Tree[A, B]) = tree.right
   }
 
-  private[this] class EntriesIterator[A, B](tree: Tree[A, B]) extends TreeIterator[A, B, (A, B)](tree) {
+  private[this] class EntriesIterator[A, B](tree: Tree[A, B], focus: Option[A])(implicit ordering: Ordering[A]) extends TreeIterator[A, B, (A, B)](tree, focus) {
     override def nextResult(tree: Tree[A, B]) = (tree.key, tree.value)
   }
 
-  private[this] class KeysIterator[A, B](tree: Tree[A, B]) extends TreeIterator[A, B, A](tree) {
+  private[this] class KeysIterator[A, B](tree: Tree[A, B], focus: Option[A])(implicit ordering: Ordering[A]) extends TreeIterator[A, B, A](tree, focus) {
     override def nextResult(tree: Tree[A, B]) = tree.key
   }
 
-  private[this] class ValuesIterator[A, B](tree: Tree[A, B]) extends TreeIterator[A, B, B](tree) {
+  private[this] class ValuesIterator[A, B](tree: Tree[A, B], focus: Option[A])(implicit ordering: Ordering[A]) extends TreeIterator[A, B, B](tree, focus) {
     override def nextResult(tree: Tree[A, B]) = tree.value
   }
 }
diff --git a/src/library/scala/collection/immutable/SortedMap.scala b/src/library/scala/collection/immutable/SortedMap.scala
index eb04231c55..5e833f87af 100644
--- a/src/library/scala/collection/immutable/SortedMap.scala
+++ b/src/library/scala/collection/immutable/SortedMap.scala
@@ -82,11 +82,17 @@ self =>
   override def filterKeys(p: A => Boolean): SortedMap[A, B] = new FilteredKeys(p) with SortedMap.Default[A, B] {
     implicit def ordering: Ordering[A] = self.ordering
     override def rangeImpl(from : Option[A], until : Option[A]): SortedMap[A, B] = self.rangeImpl(from, until).filterKeys(p)
+    override def iteratorFrom(start: A) = self iteratorFrom start filter {case (k, _) => p(k)} 
+    override def keysIteratorFrom(start : A) = self keysIteratorFrom start filter p
+    override def valuesIteratorFrom(start : A) = self iteratorFrom start collect {case (k,v) if p(k) => v}
   }
 
   override def mapValues[C](f: B => C): SortedMap[A, C] = new MappedValues(f) with SortedMap.Default[A, C] {
     implicit def ordering: Ordering[A] = self.ordering
     override def rangeImpl(from : Option[A], until : Option[A]): SortedMap[A, C] = self.rangeImpl(from, until).mapValues(f)
+    override def iteratorFrom(start: A) = self iteratorFrom start map {case (k, v) => (k, f(v))} 
+    override def keysIteratorFrom(start : A) = self keysIteratorFrom start
+    override def valuesIteratorFrom(start : A) = self valuesIteratorFrom start map f
   }
 
 }
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index 9a87d8636b..a6a6b75c32 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -189,9 +189,13 @@ class TreeMap[A, +B] private (tree: RB.Tree[A, B])(implicit val ordering: Orderi
    *  @return the new iterator
    */
   override def iterator: Iterator[(A, B)] = RB.iterator(tree)
+  override def iteratorFrom(start: A): Iterator[(A, B)] = RB.iterator(tree, Some(start))
 
   override def keysIterator: Iterator[A] = RB.keysIterator(tree)
+  override def keysIteratorFrom(start: A): Iterator[A] = RB.keysIterator(tree, Some(start))
+  
   override def valuesIterator: Iterator[B] = RB.valuesIterator(tree)
+  override def valuesIteratorFrom(start: A): Iterator[B] = RB.valuesIterator(tree, Some(start))
 
   override def contains(key: A): Boolean = RB.contains(tree, key)
   override def isDefinedAt(key: A): Boolean = RB.contains(tree, key)
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 8bceb936aa..67668b3bef 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -144,6 +144,7 @@ class TreeSet[A] private (tree: RB.Tree[A, Unit])(implicit val ordering: Orderin
    *  @return the new iterator
    */
   def iterator: Iterator[A] = RB.keysIterator(tree)
+  override def keysIteratorFrom(start: A): Iterator[A] = RB.keysIterator(tree, Some(start))
 
   override def foreach[U](f: A =>  U) = RB.foreachKey(tree, f)
 
diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala
index 5197af1b04..4fd35658fa 100644
--- a/src/library/scala/collection/mutable/TreeSet.scala
+++ b/src/library/scala/collection/mutable/TreeSet.scala
@@ -116,8 +116,25 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S
     resolve.avl.contains(elem, ordering)
   }
 
+  // TODO see the discussion on keysIteratorFrom
   override def iterator: Iterator[A] = resolve.avl.iterator
     .dropWhile(e => !isLeftAcceptable(from, ordering)(e))
       .takeWhile(e => isRightAcceptable(until, ordering)(e))
+  
+  // TODO because TreeSets are potentially ranged views into other TreeSets
+  // what this really needs to do is walk the whole stack of tree sets, find
+  // the highest "from", and then do a tree walk of the underlying avl tree
+  // to find that spot in max(O(stack depth), O(log tree.size)) time which
+  // should effectively be O(log size) since ranged views are rare and
+  // even more rarely deep. With the following implementation it's
+  // O(N log N) to get an iterator from a start point.  
+  // But before engaging that endeavor I think mutable.TreeSet should be
+  // based on the same immutable RedBlackTree that immutable.TreeSet is
+  // based on. There's no good reason to have these two collections based
+  // on two different balanced binary trees. That'll save
+  // having to duplicate logic for finding the starting point of a
+  // sorted binary tree iterator, logic that has already been
+  // baked into RedBlackTree.
+  override def keysIteratorFrom(start: A) = from(start).iterator
 
 }
diff --git a/test/files/run/iterator-from.scala b/test/files/run/iterator-from.scala
new file mode 100644
index 0000000000..8dc6ae4e51
--- /dev/null
+++ b/test/files/run/iterator-from.scala
@@ -0,0 +1,69 @@
+// This file tests iteratorFrom, keysIteratorFrom, and valueIteratorFrom on various sorted sets and maps
+
+import scala.util.{Random => R}
+import scala.collection._
+import scala.math.Ordered
+
+object Test extends App {
+  val maxLength = 25
+  val maxKey = 50
+  val maxValue = 50
+
+  def testSet[A <% Ordered[A]](set: SortedSet[A], list: List[A]) {
+    val distinctSorted = list.distinct.sorted
+    assertEquals("Set size wasn't the same as list sze", set.size, distinctSorted.size)
+
+    for(key <- distinctSorted) {
+      val clazz = set.getClass
+      val iteratorFrom = (set iteratorFrom key).toList
+      check(clazz, list, s"set iteratorFrom $key", s"(set from $key).iterator", iteratorFrom, (set from key).iterator.toList)
+      check(clazz, list, s"set.iteratorFrom $key", s"distinctSorted dropWhile (_ < $key)", iteratorFrom, distinctSorted dropWhile (_ < key))
+      check(clazz, list, s"set iteratorFrom $key", s"set keysIterator from $key", iteratorFrom, (set keysIteratorFrom key).toList)
+    }
+  }
+
+  def testMap[A <% Ordered[A], B](map: SortedMap[A, B], list: List[(A, B)]) {
+    val distinctSorted = distinctByKey(list).sortBy(_._1) 
+    assertEquals("Map size wasn't the same as list sze", map.size, distinctSorted.size)
+
+    for(keyValue <- distinctSorted) {
+      val key = keyValue._1
+      val clazz = map.getClass
+      val iteratorFrom = (map iteratorFrom key).toList
+      check(clazz, list, s"map iteratorFrom $key", s"(map from $key).iterator", iteratorFrom, (map from key).iterator.toList)
+      check(clazz, list, s"map iteratorFrom $key", s"distinctSorted dropWhile (_._1 < $key)", iteratorFrom, distinctSorted dropWhile (_._1 < key))
+      check(clazz, list, s"map iteratorFrom $key map (_._1)", s"map keysIteratorFrom $key", iteratorFrom map (_._1), (map keysIteratorFrom key).toList)
+      check(clazz, list, s"map iteratorFrom $key map (_._2)", s"map valuesIteratorFrom $key", iteratorFrom map (_._2), (map valuesIteratorFrom key).toList)     
+    }
+  }
+
+  def check[A](clazz: Class[_], list: List[_], m1: String, m2: String, l1: List[A], l2: List[A]) {
+    assertEquals(s"$clazz: `$m1` didn't match `$m2` on list $list", l1, l2)
+  }
+
+  def assertEquals[A](msg: String, x: A, y: A) {
+    assert(x == y, s"$msg\n1: $x\n2: $y")
+  }
+
+  def distinctByKey[A,B](list: List[(A, B)]) : List[(A,B)] = list.groupBy(_._1).map(_._2.last).toList
+
+  object Weekday extends Enumeration {
+    type Weekday = Value
+    val Mon, Tue, Wed, Thu, Fri, Sat, Sun = Value
+  }
+
+  0 until maxLength foreach {length => 
+    val keyValues = (0 until length map {_ => (R nextInt maxKey, R nextInt maxValue)}).toList
+    val keys = keyValues map (_._2)
+    testSet(immutable.BitSet(keys:_*), keys)
+    testSet(immutable.TreeSet(keys:_*), keys)
+    testSet(mutable.TreeSet(keys:_*), keys)
+    val days = keys map {n => Weekday(n % Weekday.values.size)}
+    testSet(Weekday.ValueSet(days:_*), days)
+
+    val treeMap = immutable.TreeMap(keyValues:_*)
+    testMap(treeMap, keyValues)
+    testMap(treeMap.filterKeys(_ % 2 == 0), keyValues  filter (_._1 % 2 == 0))
+    testMap(treeMap mapValues (_ + 1), keyValues map {case (k,v) => (k, v + 1)})
+  }
+}
-- 
cgit v1.2.3


From 39037798c94e6e862f39dacffc5e65bb08b78d6a Mon Sep 17 00:00:00 2001
From: James Iry <jamesiry@gmail.com>
Date: Tue, 12 Feb 2013 15:30:50 -0800
Subject: SI-6642 Refactor mutable.TreeSet to use RedBlackTree instead of AVL

There was no reason to have mutable.TreeSet use AVLTree while
immutable.TreeSet and immutable.HashSet used RedBlackTree. In
particular that would have meant duplicating the iteratorFrom logic
unnecessarily. So this commit refactors mutable.TreeSet to use
RedBlackTree for everything, including iteratorFrom. It also adds
a test to make sure TreeSet works as expected.

AVLTree should be dead code since it's private[scala.collection.mutable]
and only used by mutable.TreeSet, but to be safe it's only deprecated
in this commit.
---
 .../scala/collection/immutable/RedBlackTree.scala  |  21 ++-
 src/library/scala/collection/mutable/AVLTree.scala |  11 +-
 src/library/scala/collection/mutable/TreeSet.scala | 125 +++++++-----------
 test/files/run/mutable-treeset.scala               | 145 +++++++++++++++++++++
 4 files changed, 223 insertions(+), 79 deletions(-)
 create mode 100644 test/files/run/mutable-treeset.scala

diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala
index c0d46765be..d8c69f026b 100644
--- a/src/library/scala/collection/immutable/RedBlackTree.scala
+++ b/src/library/scala/collection/immutable/RedBlackTree.scala
@@ -24,7 +24,7 @@ import scala.annotation.meta.getter
  *
  *  @since 2.10
  */
-private[immutable]
+private[collection]
 object RedBlackTree {
 
   def isEmpty(tree: Tree[_, _]): Boolean = tree eq null
@@ -44,6 +44,25 @@ object RedBlackTree {
   }
 
   def count(tree: Tree[_, _]) = if (tree eq null) 0 else tree.count
+  /**
+   * Count all the nodes with keys greater than or equal to the lower bound and less than the upper bound.
+   * The two bounds are optional.
+   */
+  def countInRange[A, _](tree: Tree[A, _], from: Option[A], to:Option[A])(implicit ordering: Ordering[A]) : Int = 
+    if (tree eq null) 0 else
+    (from, to) match {
+      // with no bounds use this node's count
+      case (None, None) => tree.count
+      // if node is less than the lower bound, try the tree on the right, it might be in range
+      case (Some(lb), _) if ordering.lt(tree.key, lb) => countInRange(tree.right, from, to)
+      // if node is greater than or equal to the upper bound, try the tree on the left, it might be in range
+      case (_, Some(ub)) if ordering.gteq(tree.key, ub) => countInRange(tree.left, from, to)
+      // node is in range so the tree on the left will all be less than the upper bound and the tree on the
+      // right will all be greater than or equal to the lower bound. So 1 for this node plus
+      // count the subtrees by stripping off the bounds that we don't need any more
+      case _ => 1 + countInRange(tree.left, from, None) + countInRange(tree.right, None, to)
+    
+    }
   def update[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1, overwrite: Boolean)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(tree, k, v, overwrite))
   def delete[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = blacken(del(tree, k))
   def rangeImpl[A: Ordering, B](tree: Tree[A, B], from: Option[A], until: Option[A]): Tree[A, B] = (from, until) match {
diff --git a/src/library/scala/collection/mutable/AVLTree.scala b/src/library/scala/collection/mutable/AVLTree.scala
index 157e5dae62..da63778fcc 100644
--- a/src/library/scala/collection/mutable/AVLTree.scala
+++ b/src/library/scala/collection/mutable/AVLTree.scala
@@ -15,7 +15,7 @@ package mutable
  * An immutable AVL Tree implementation used by mutable.TreeSet
  *
  * @author Lucien Pereira
- *
+ * @deprecated("AVLTree and its related classes are being removed from the standard library since they're not different enough from RedBlackTree to justify keeping them.", "2.11")
  */
 private[mutable] sealed trait AVLTree[+A] extends Serializable {
   def balance: Int
@@ -65,12 +65,18 @@ private[mutable] sealed trait AVLTree[+A] extends Serializable {
   def doubleRightRotation[B >: A]: Node[B] = sys.error("Should not happen.")
 }
 
+/**
+ * @deprecated("AVLTree and its related classes are being removed from the standard library since they're not different enough from RedBlackTree to justify keeping them.", "2.11")
+ */
 private case object Leaf extends AVLTree[Nothing] {
   override val balance: Int = 0
 
   override val depth: Int = -1
 }
 
+/**
+ * @deprecated("AVLTree and its related classes are being removed from the standard library since they're not different enough from RedBlackTree to justify keeping them.", "2.11")
+ */
 private case class Node[A](val data: A, val left: AVLTree[A], val right: AVLTree[A]) extends AVLTree[A] {
   override val balance: Int = right.depth - left.depth
 
@@ -205,6 +211,9 @@ private case class Node[A](val data: A, val left: AVLTree[A], val right: AVLTree
   }
 }
 
+/**
+ * @deprecated("AVLTree and its related classes are being removed from the standard library since they're not different enough from RedBlackTree to justify keeping them.", "2.11")
+ */
 private class AVLIterator[A](root: Node[A]) extends Iterator[A] {
   val stack = mutable.ArrayStack[Node[A]](root)
   diveLeft()
diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala
index 4fd35658fa..9113d8221b 100644
--- a/src/library/scala/collection/mutable/TreeSet.scala
+++ b/src/library/scala/collection/mutable/TreeSet.scala
@@ -10,6 +10,8 @@ package scala.collection
 package mutable
 
 import generic._
+import scala.collection.immutable.{RedBlackTree => RB}
+import scala.runtime.ObjectRef
 
 /**
  * @define Coll `mutable.TreeSet`
@@ -29,112 +31,81 @@ object TreeSet extends MutableSortedSetFactory[TreeSet] {
 }
 
 /**
- * A mutable SortedSet using an immutable AVL Tree as underlying data structure.
+ * A mutable SortedSet using an immutable RedBlack Tree as underlying data structure.
  *
  * @author Lucien Pereira
  *
  */
-class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with SetLike[A, TreeSet[A]]
+class TreeSet[A] private (treeRef: ObjectRef[RB.Tree[A, Null]], from: Option[A], until: Option[A])(implicit val ordering: Ordering[A]) 
+  extends SortedSet[A] with SetLike[A, TreeSet[A]]
   with SortedSetLike[A, TreeSet[A]] with Set[A] with Serializable {
 
-  // Projection constructor
-  private def this(base: Option[TreeSet[A]], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]) {
-    this();
-    this.base = base
-    this.from = from
-    this.until = until
-  }
-
-  private var base: Option[TreeSet[A]] = None
-
-  private var from: Option[A] = None
-
-  private var until: Option[A] = None
-
-  private var avl: AVLTree[A] = Leaf
-
-  private var cardinality: Int = 0
+  def this()(implicit ordering: Ordering[A]) = this(new ObjectRef(null), None, None)
 
-  def resolve: TreeSet[A] = base.getOrElse(this)
-
-  private def isLeftAcceptable(from: Option[A], ordering: Ordering[A])(a: A): Boolean =
-    from.map(x => ordering.gteq(a, x)).getOrElse(true)
-
-  private def isRightAcceptable(until: Option[A], ordering: Ordering[A])(a: A): Boolean =
-    until.map(x => ordering.lt(a, x)).getOrElse(true)
-
-  /**
-   * Cardinality store the set size, unfortunately a
-   * set view (given by rangeImpl)
-   * cannot take advantage of this optimisation
-   *
-   */
-  override def size: Int = base.map(_ => super.size).getOrElse(cardinality)
+  override def size: Int = RB.countInRange(treeRef.elem, from, until)
 
   override def stringPrefix = "TreeSet"
 
   override def empty: TreeSet[A] = TreeSet.empty
 
-  override def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] = new TreeSet(Some(this), from, until)
+  private def pickBound(comparison: (A, A) => A, oldBound: Option[A], newBound: Option[A]) = (newBound, oldBound) match {
+    case (Some(newB), Some(oldB)) => Some(comparison(newB, oldB))
+    case (None, _) => oldBound
+    case _ => newBound
+  }      
+    
+  override def rangeImpl(fromArg: Option[A], untilArg: Option[A]): TreeSet[A] = {
+    val newFrom = pickBound(ordering.max, fromArg, from)
+    val newUntil = pickBound(ordering.min, untilArg, until)
+    
+    new TreeSet(treeRef, newFrom, newUntil) 
+  }
 
   override def -=(elem: A): this.type = {
-    try {
-      resolve.avl = resolve.avl.remove(elem, ordering)
-      resolve.cardinality = resolve.cardinality - 1
-    } catch {
-      case e: NoSuchElementException => ()
-    }
+    treeRef.elem = RB.delete(treeRef.elem, elem)
     this
   }
 
   override def +=(elem: A): this.type = {
-    try {
-      resolve.avl = resolve.avl.insert(elem, ordering)
-      resolve.cardinality = resolve.cardinality + 1
-    } catch {
-      case e: IllegalArgumentException => ()
-    }
+    treeRef.elem = RB.update(treeRef.elem, elem, null, false)
     this
   }
 
   /**
    * Thanks to the immutable nature of the
-   * underlying AVL Tree, we can share it with
+   * underlying Tree, we can share it with
    * the clone. So clone complexity in time is O(1).
    *
    */
-  override def clone(): TreeSet[A] = {
-    val clone = new TreeSet[A](base, from, until)
-    clone.avl = resolve.avl
-    clone.cardinality = resolve.cardinality
-    clone
-  }
+  override def clone(): TreeSet[A] = 
+    new TreeSet[A](new ObjectRef(treeRef.elem), from, until)
+    
+  private val notProjection = !(from.isDefined || until.isDefined)
 
   override def contains(elem: A): Boolean = {
-    isLeftAcceptable(from, ordering)(elem) &&
-    isRightAcceptable(until, ordering)(elem) &&
-    resolve.avl.contains(elem, ordering)
+    def leftAcceptable: Boolean = from match {
+      case Some(lb) => ordering.gteq(elem, lb)
+      case _ => true
+    }
+
+    def rightAcceptable: Boolean = until match {
+      case Some(ub) => ordering.lt(elem, ub)
+      case _ => true
+    }    
+    
+    (notProjection || (leftAcceptable && rightAcceptable)) &&
+      RB.contains(treeRef.elem, elem)
   }
 
-  // TODO see the discussion on keysIteratorFrom
-  override def iterator: Iterator[A] = resolve.avl.iterator
-    .dropWhile(e => !isLeftAcceptable(from, ordering)(e))
-      .takeWhile(e => isRightAcceptable(until, ordering)(e))
+  override def iterator: Iterator[A] = iteratorFrom(None)
   
-  // TODO because TreeSets are potentially ranged views into other TreeSets
-  // what this really needs to do is walk the whole stack of tree sets, find
-  // the highest "from", and then do a tree walk of the underlying avl tree
-  // to find that spot in max(O(stack depth), O(log tree.size)) time which
-  // should effectively be O(log size) since ranged views are rare and
-  // even more rarely deep. With the following implementation it's
-  // O(N log N) to get an iterator from a start point.  
-  // But before engaging that endeavor I think mutable.TreeSet should be
-  // based on the same immutable RedBlackTree that immutable.TreeSet is
-  // based on. There's no good reason to have these two collections based
-  // on two different balanced binary trees. That'll save
-  // having to duplicate logic for finding the starting point of a
-  // sorted binary tree iterator, logic that has already been
-  // baked into RedBlackTree.
-  override def keysIteratorFrom(start: A) = from(start).iterator
-
+  override def keysIteratorFrom(start: A) = iteratorFrom(Some(start))
+  
+  private def iteratorFrom(start: Option[A]) = {
+    val it = RB.keysIterator(treeRef.elem, pickBound(ordering.max, from, start))
+    until match {
+      case None => it
+      case Some(ub) => it takeWhile (k => ordering.lt(k, ub))
+    }
+  }
 }
diff --git a/test/files/run/mutable-treeset.scala b/test/files/run/mutable-treeset.scala
new file mode 100644
index 0000000000..c9918cba96
--- /dev/null
+++ b/test/files/run/mutable-treeset.scala
@@ -0,0 +1,145 @@
+import scala.collection.mutable.TreeSet
+
+object Test extends App {
+  val list = List(6,5,4,3,2,1,1,2,3,4,5,6,6,5,4,3,2,1)
+  val distinct = list.distinct
+  val sorted = distinct.sorted
+
+  // sublist stuff for a single level of slicing
+  val min = list.min
+  val max = list.max
+  val nonlist = ((min - 10) until (max + 20) filterNot list.contains).toList
+  val sublist = list filter {x => x >=(min + 1) && x < max} 
+  val distinctSublist = sublist.distinct 
+  val subnonlist = min :: max :: nonlist
+  val subsorted = distinctSublist.sorted
+
+  // subsublist for a 2nd level of slicing
+  val almostmin = sublist.min
+  val almostmax = sublist.max
+  val subsublist = sublist filter {x => x >=(almostmin + 1) && x < almostmax} 
+  val distinctSubsublist = subsublist.distinct 
+  val subsubnonlist = almostmin :: almostmax :: subnonlist
+  val subsubsorted = distinctSubsublist.sorted
+
+  def testSize {
+    def check(set : TreeSet[Int], list: List[Int]) { 
+      assert(set.size == list.size, s"$set had size ${set.size} while $list had size ${list.size}")
+    }
+
+    check(TreeSet[Int](), List[Int]())
+    val set = TreeSet(list:_*)
+    check(set, distinct)
+    check(set.clone, distinct)
+
+    val subset = set from (min + 1) until max
+    check(subset, distinctSublist)
+    check(subset.clone, distinctSublist)
+
+    val subsubset = subset from (almostmin + 1) until almostmax
+    check(subsubset, distinctSubsublist)
+    check(subsubset.clone, distinctSubsublist)
+  }
+
+  def testContains {
+    def check(set : TreeSet[Int], list: List[Int], nonlist: List[Int]) {
+      assert(list forall set.apply, s"$set did not contain all elements of $list using apply")
+      assert(list forall set.contains, s"$set did not contain all elements of $list using contains")
+      assert(!(nonlist exists set.apply), s"$set had an element from $nonlist using apply")
+      assert(!(nonlist exists set.contains), s"$set had an element from $nonlist using contains")      
+    }
+
+    val set = TreeSet(list:_*)
+    check(set, list, nonlist)
+    check(set.clone, list, nonlist)
+
+    val subset = set from (min + 1) until max
+    check(subset, sublist, subnonlist)
+    check(subset.clone, sublist, subnonlist)
+
+    val subsubset = subset from (almostmin + 1) until almostmax
+    check(subsubset, subsublist, subsubnonlist)
+    check(subsubset.clone, subsublist, subsubnonlist)
+  }
+
+  def testAdd {
+    def check(set : TreeSet[Int], list: List[Int], nonlist: List[Int]) {
+      var builtList = List[Int]()
+      for (x <- list) {
+        set += x
+        builtList = (builtList :+ x).distinct.sorted filterNot nonlist.contains
+        assert(builtList forall set.apply, s"$set did not contain all elements of $builtList using apply")
+        assert(builtList.size == set.size, s"$set had size ${set.size} while $builtList had size ${builtList.size}")
+      }
+      assert(!(nonlist exists set.apply), s"$set had an element from $nonlist using apply")
+      assert(!(nonlist exists set.contains), s"$set had an element from $nonlist using contains")      
+    }
+
+    val set = TreeSet[Int]()
+    val clone = set.clone    
+    val subset = set.clone from (min + 1) until max
+    val subclone = subset.clone
+    val subsubset = subset.clone from (almostmin + 1) until almostmax
+    val subsubclone = subsubset.clone
+
+    check(set, list, nonlist)
+    check(clone, list, nonlist)
+
+    check(subset, list, subnonlist)
+    check(subclone, list, subnonlist)
+
+    check(subsubset, list, subsubnonlist)
+    check(subsubclone, list, subsubnonlist)
+  }
+
+  def testRemove {
+    def check(set: TreeSet[Int], sorted: List[Int]) {
+      var builtList = sorted
+      for (x <- list) {
+        set remove x
+        builtList = builtList filterNot (_ == x)
+        assert(builtList forall set.apply, s"$set did not contain all elements of $builtList using apply")
+        assert(builtList.size == set.size, s"$set had size $set.size while $builtList had size $builtList.size")
+      }   
+    }
+    val set = TreeSet(list:_*)
+    val clone = set.clone    
+    val subset = set.clone from (min + 1) until max
+    val subclone = subset.clone
+    val subsubset = subset.clone from (almostmin + 1) until almostmax
+    val subsubclone = subsubset.clone
+
+    check(set, sorted)
+    check(clone, sorted)
+
+    check(subset, subsorted)
+    check(subclone, subsorted)
+    
+    check(subsubset, subsubsorted)
+    check(subsubclone, subsubsorted)
+  }
+
+  def testIterator {
+    def check(set: TreeSet[Int], list: List[Int]) {
+      val it = set.iterator.toList
+      assert(it == list, s"$it did not equal $list")
+    }
+    val set = TreeSet(list: _*)
+    check(set, sorted)
+    check(set.clone, sorted)
+
+    val subset = set from (min + 1) until max
+    check(subset, subsorted)
+    check(subset.clone, subsorted)
+
+    val subsubset = subset from (almostmin + 1) until almostmax
+    check(subsubset, subsubsorted)
+    check(subsubset.clone, subsubsorted)
+  }
+
+  testSize
+  testContains
+  testAdd
+  testRemove
+  testIterator
+}
-- 
cgit v1.2.3


From 07ba1f8002b5f81bd3849ba38144efdabc8ef4a4 Mon Sep 17 00:00:00 2001
From: James Iry <jamesiry@gmail.com>
Date: Wed, 13 Feb 2013 21:23:04 -0800
Subject: SI-6642 Code cleanup from review of iteratorFrom
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This commit is code cleanup from the review on
https://github.com/scala/scala/pull/2119

* Changes several instances of
    def f[A, ]… to
    def f[A]…
* Changes several instances of
    def f[A](…)(implicit ordering : Ordering[A])… to
    def f[A: Ordering](…)…
* Changes one instance of
    x == null to
    x eq null
* Changes two instances of
    id + bottomid to
    bottomid + id
---
 src/library/scala/Enumeration.scala                |  4 ++--
 .../scala/collection/immutable/RedBlackTree.scala  | 24 +++++++++++-----------
 2 files changed, 14 insertions(+), 14 deletions(-)

diff --git a/src/library/scala/Enumeration.scala b/src/library/scala/Enumeration.scala
index e7ce21b229..d522539e83 100644
--- a/src/library/scala/Enumeration.scala
+++ b/src/library/scala/Enumeration.scala
@@ -254,8 +254,8 @@ abstract class Enumeration (initial: Int) extends Serializable {
     def contains(v: Value) = nnIds contains (v.id - bottomId)
     def + (value: Value) = new ValueSet(nnIds + (value.id - bottomId))
     def - (value: Value) = new ValueSet(nnIds - (value.id - bottomId))
-    def iterator = nnIds.iterator map (id => thisenum.apply(id + bottomId))
-    override def keysIteratorFrom(start: Value) = nnIds keysIteratorFrom start.id  map (id => thisenum.apply(id + bottomId))
+    def iterator = nnIds.iterator map (id => thisenum.apply(bottomId + id))
+    override def keysIteratorFrom(start: Value) = nnIds keysIteratorFrom start.id  map (id => thisenum.apply(bottomId + id))
     override def stringPrefix = thisenum + ".ValueSet"
     /** Creates a bit mask for the zero-adjusted ids in this set as a
      *  new array of longs */
diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala
index d8c69f026b..1cd0128c05 100644
--- a/src/library/scala/collection/immutable/RedBlackTree.scala
+++ b/src/library/scala/collection/immutable/RedBlackTree.scala
@@ -29,8 +29,8 @@ object RedBlackTree {
 
   def isEmpty(tree: Tree[_, _]): Boolean = tree eq null
 
-  def contains[A](tree: Tree[A, _], x: A)(implicit ordering: Ordering[A]): Boolean = lookup(tree, x) ne null
-  def get[A, B](tree: Tree[A, B], x: A)(implicit ordering: Ordering[A]): Option[B] = lookup(tree, x) match {
+  def contains[A: Ordering](tree: Tree[A, _], x: A): Boolean = lookup(tree, x) ne null
+  def get[A: Ordering, B](tree: Tree[A, B], x: A): Option[B] = lookup(tree, x) match {
     case null => None
     case tree => Some(tree.value)
   }
@@ -48,7 +48,7 @@ object RedBlackTree {
    * Count all the nodes with keys greater than or equal to the lower bound and less than the upper bound.
    * The two bounds are optional.
    */
-  def countInRange[A, _](tree: Tree[A, _], from: Option[A], to:Option[A])(implicit ordering: Ordering[A]) : Int = 
+  def countInRange[A](tree: Tree[A, _], from: Option[A], to:Option[A])(implicit ordering: Ordering[A]) : Int = 
     if (tree eq null) 0 else
     (from, to) match {
       // with no bounds use this node's count
@@ -63,8 +63,8 @@ object RedBlackTree {
       case _ => 1 + countInRange(tree.left, from, None) + countInRange(tree.right, None, to)
     
     }
-  def update[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1, overwrite: Boolean)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(tree, k, v, overwrite))
-  def delete[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = blacken(del(tree, k))
+  def update[A: Ordering, B, B1 >: B](tree: Tree[A, B], k: A, v: B1, overwrite: Boolean): Tree[A, B1] = blacken(upd(tree, k, v, overwrite))
+  def delete[A: Ordering, B](tree: Tree[A, B], k: A): Tree[A, B] = blacken(del(tree, k))
   def rangeImpl[A: Ordering, B](tree: Tree[A, B], from: Option[A], until: Option[A]): Tree[A, B] = (from, until) match {
     case (Some(from), Some(until)) => this.range(tree, from, until)
     case (Some(from), None)        => this.from(tree, from)
@@ -110,9 +110,9 @@ object RedBlackTree {
     if (tree.right ne null) _foreachKey(tree.right, f)
   }
 
-  def iterator[A, B](tree: Tree[A, B], start: Option[A] = None)(implicit ordering: Ordering[A]): Iterator[(A, B)] = new EntriesIterator(tree, start)
-  def keysIterator[A, _](tree: Tree[A, _], start: Option[A] = None)(implicit ordering: Ordering[A]): Iterator[A] = new KeysIterator(tree, start)
-  def valuesIterator[A, B](tree: Tree[A, B], start: Option[A] = None)(implicit ordering: Ordering[A]): Iterator[B] = new ValuesIterator(tree, start)
+  def iterator[A: Ordering, B](tree: Tree[A, B], start: Option[A] = None): Iterator[(A, B)] = new EntriesIterator(tree, start)
+  def keysIterator[A: Ordering](tree: Tree[A, _], start: Option[A] = None): Iterator[A] = new KeysIterator(tree, start)
+  def valuesIterator[A: Ordering, B](tree: Tree[A, B], start: Option[A] = None): Iterator[B] = new ValuesIterator(tree, start)
 
   @tailrec
   def nth[A, B](tree: Tree[A, B], n: Int): Tree[A, B] = {
@@ -510,7 +510,7 @@ object RedBlackTree {
      */
     private[this] def startFrom(key: A) : Tree[A,B] = if (root eq null) null else {
       @tailrec def find(tree: Tree[A, B]): Tree[A, B] = 
-        if (tree == null) popNext
+        if (tree eq null) popNext
         else find(
           if (ordering.lteq(key, tree.key)) goLeft(tree)
           else goRight(tree)
@@ -526,15 +526,15 @@ object RedBlackTree {
     private[this] def goRight(tree: Tree[A, B]) = tree.right
   }
 
-  private[this] class EntriesIterator[A, B](tree: Tree[A, B], focus: Option[A])(implicit ordering: Ordering[A]) extends TreeIterator[A, B, (A, B)](tree, focus) {
+  private[this] class EntriesIterator[A: Ordering, B](tree: Tree[A, B], focus: Option[A]) extends TreeIterator[A, B, (A, B)](tree, focus) {
     override def nextResult(tree: Tree[A, B]) = (tree.key, tree.value)
   }
 
-  private[this] class KeysIterator[A, B](tree: Tree[A, B], focus: Option[A])(implicit ordering: Ordering[A]) extends TreeIterator[A, B, A](tree, focus) {
+  private[this] class KeysIterator[A: Ordering, B](tree: Tree[A, B], focus: Option[A]) extends TreeIterator[A, B, A](tree, focus) {
     override def nextResult(tree: Tree[A, B]) = tree.key
   }
 
-  private[this] class ValuesIterator[A, B](tree: Tree[A, B], focus: Option[A])(implicit ordering: Ordering[A]) extends TreeIterator[A, B, B](tree, focus) {
+  private[this] class ValuesIterator[A: Ordering, B](tree: Tree[A, B], focus: Option[A]) extends TreeIterator[A, B, B](tree, focus) {
     override def nextResult(tree: Tree[A, B]) = tree.value
   }
 }
-- 
cgit v1.2.3