Merge pull request #2119 from JamesIry/master_SI-6642

SI-6642 Adds iteratorFrom, keysIteratorFrom, and valuesIteratorFrom

13 files changed, 411 insertions, 97 deletions

diff --git a/src/library/scala/Enumeration.scala b/src/library/scala/Enumeration.scala
index 21f0c8fd3e..d522539e83 100644
--- a/src/library/scala/Enumeration.scala
+++ b/src/library/scala/Enumeration.scala
@@ -254,7 +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))
+    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/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 99f8d95517..1cd0128c05 100644
--- a/src/library/scala/collection/immutable/RedBlackTree.scala
+++ b/src/library/scala/collection/immutable/RedBlackTree.scala
@@ -24,13 +24,13 @@ import scala.annotation.meta.getter
  *
  *  @since 2.10
  */
-private[immutable]
+private[collection]
 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)
   }
@@ -44,8 +44,27 @@ object RedBlackTree {
   }
 
   def count(tree: Tree[_, _]) = if (tree eq null) 0 else tree.count
-  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))
+  /**
+   * 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: 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)
@@ -91,9 +110,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: 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] = {
@@ -425,32 +444,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], start: Option[A])(implicit ordering: Ordering[A]) 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 +477,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,22 +496,45 @@ 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] = 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 eq 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)
+      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) {
+  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]) extends TreeIterator[A, B, A](tree) {
+  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]) extends TreeIterator[A, B, B](tree) {
+  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
   }
 }
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/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 5197af1b04..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,95 +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
+    }
 
-  override def iterator: Iterator[A] = resolve.avl.iterator
-    .dropWhile(e => !isLeftAcceptable(from, ordering)(e))
-      .takeWhile(e => isRightAcceptable(until, ordering)(e))
+    def rightAcceptable: Boolean = until match {
+      case Some(ub) => ordering.lt(elem, ub)
+      case _ => true
+    }    
+    
+    (notProjection || (leftAcceptable && rightAcceptable)) &&
+      RB.contains(treeRef.elem, elem)
+  }
 
+  override def iterator: Iterator[A] = iteratorFrom(None)
+  
+  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/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)})
+  }
+}
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
+}