16 files changed, 412 insertions, 21 deletions

diff --git a/src/library/scala/collection/Ranged.scala b/src/library/scala/collection/Ranged.scala
new file mode 100644
index 0000000000..efcaaf5ba1
--- /dev/null
+++ b/src/library/scala/collection/Ranged.scala
@@ -0,0 +1,49 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2006-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Sorted.scala 9621 2007-01-17 14:29:25Z michelou $
+
+package scala.collection;
+
+/** Any collection (including maps) whose keys (or elements) are ordered.
+ *
+ *  @author Sean McDirmid
+ */
+trait Ranged[K,+A] extends Iterable[A] {
+  //protected type SortedSelf <: Ranged[K,A];
+  /** Returns the first key of the collection. */
+  def first: K;
+  /** Returns the last key of the collection. */
+  def last: K;
+  /** Comparison function that orders keys. */
+  def compare(k0: K, k1: K): Int;
+  /** Creates a ranged projection of this collection. Any mutations in the
+   *  ranged projection will update this collection and vice versa.  Note: keys
+   *  are not garuanteed to be consistent between this collection and the projection.
+   *  This is the case for buffers where indexing is relative to the projection.
+   *
+   *  @param from  The lower-bound (inclusive) of the ranged projection.
+   *               <code>None</code> if there is no lower bound.
+   *  @param until The upper-bound (exclusive) of the ranged projection.
+   *               <code>None</code> if there is no upper bound.
+   */
+  def rangeImpl(from: Option[K], until: Option[K]) : Ranged[K,A];
+  /** Creates a ranged projection of this collection with no upper-bound.
+   ** @param from The lower-bound (inclusive) of the ranged projection.
+   **/
+  def from(from: K) = rangeImpl(Some(from), None);
+  /** Creates a ranged projection of this collection with no lower-bound.
+   ** @param until The upper-bound (exclusive) of the ranged projection.
+   **/
+  def until(until: K) = rangeImpl(None, Some(until));
+
+  /** Creates a ranged projection of this collection with both a lower-bound and an upper-bound.
+   ** @param from The upper-bound (exclusive) of the ranged projection.
+   **/
+  def range(from: K, until: K) = rangeImpl(Some(from),Some(until));
+}
diff --git a/src/library/scala/collection/Sorted.scala b/src/library/scala/collection/Sorted.scala
new file mode 100644
index 0000000000..8e7e2f0c6d
--- /dev/null
+++ b/src/library/scala/collection/Sorted.scala
@@ -0,0 +1,64 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2006-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Sorted.scala 9621 2007-01-17 14:29:25Z michelou $
+
+package scala.collection;
+
+/** Any collection (including maps) whose keys (or elements) are ordered.
+ *
+ *  @author Sean McDirmid
+ */
+trait Sorted[K,+A] extends Ranged[K,A] {
+  /** return as a projection the set of keys in this collection */
+  def keySet : SortedSet[K];
+
+  /** Creates a ranged projection of this collection. Any mutations in the
+   *  ranged projection will update this collection and vice versa.  Keys
+   *  are garuanteed to be consistent between the collection and its projection.
+   *
+   *  @param from  The lower-bound (inclusive) of the ranged projection.
+   *               <code>None</code> if there is no lower bound.
+   *  @param until The upper-bound (exclusive) of the ranged projection.
+   *               <code>None</code> if there is no upper bound.
+   */
+  override def rangeImpl(from: Option[K], until: Option[K]) : Sorted[K,A];
+  override def from(from: K) = rangeImpl(Some(from), None);
+  override def until(until: K) = rangeImpl(None, Some(until));
+  override def range(from: K, until: K) = rangeImpl(Some(from),Some(until));
+
+  /** Create a range projection of this collection with no lower-bound.
+   ** @param to The upper-bound (inclusive) of the ranged projection.
+   **/
+  def to(to : K): Sorted[K,A] = {
+    // tough!
+    val i = keySet.from(to).elements;
+    if (!i.hasNext) return this;
+    val next = i.next;
+    if (next == to) {
+      if (!i.hasNext) return this;
+      else return until(i.next);
+    } else return until(next);
+  }
+  protected def hasAll(j : Iterator[K]) : Boolean = {
+    val i = keySet.elements;
+    if (!i.hasNext) return !j.hasNext;
+    var in = i.next;
+    while (j.hasNext) {
+      val jn = j.next;
+      while ({
+        val n = compare(jn, in);
+        if (n == 0) false;
+        else if (n < 0) return false;
+        else if (!i.hasNext) return false;
+        else true;
+      }) in = i.next;
+    }
+    return true;
+  }
+}
diff --git a/src/library/scala/collection/SortedMap.scala b/src/library/scala/collection/SortedMap.scala
new file mode 100644
index 0000000000..06411050c4
--- /dev/null
+++ b/src/library/scala/collection/SortedMap.scala
@@ -0,0 +1,44 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2006-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: SortedMap.scala 9621 2007-01-17 14:29:25Z michelou $
+
+package scala.collection;
+
+/** A map whose keys are sorted.
+ *
+ *  @author Sean McDirmid
+ */
+trait SortedMap[K,+E] extends Map[K,E] with Sorted[K,Tuple2[K,E]] {
+  override def first : K = elements.next._1;
+  override def last : K = {
+    val i = elements;
+    var last : K = i.next._1;
+    while (i.hasNext) last = i.next._1;
+    last;
+  }
+
+  // XXX: implement default version
+  override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap[K,E];
+  override def from(from: K) = rangeImpl(Some(from), None);
+  override def until(until: K) = rangeImpl(None, Some(until));
+  override def range(from: K, until: K) = rangeImpl(Some(from),Some(until));
+
+  protected class DefaultKeySet extends SortedSet[K] {
+    def size = SortedMap.this.size
+    def contains(key : K) = SortedMap.this.contains(key)
+    def elements = SortedMap.this.elements.map(._1)
+    def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0, k1);
+    override def rangeImpl(from : Option[K], until : Option[K]) : SortedSet[K] = {
+      val map = SortedMap.this.rangeImpl(from,until);
+      new map.DefaultKeySet;
+    }
+  }
+  // XXX: implement default version
+  override def keySet : SortedSet[K] = new DefaultKeySet;
+}
diff --git a/src/library/scala/collection/SortedSet.scala b/src/library/scala/collection/SortedSet.scala
new file mode 100644
index 0000000000..2200b761fd
--- /dev/null
+++ b/src/library/scala/collection/SortedSet.scala
@@ -0,0 +1,41 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2006-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: SortedSet.scala 9621 2007-01-17 14:29:25Z michelou $
+
+package scala.collection;
+
+/** Analogous to a Java sorted set.
+ *
+ *  @author Sean McDirmid
+ */
+trait SortedSet[A] extends Set[A] with Sorted[A,A] {
+  override def keySet = this;
+  override def first : A = {
+    val i = elements;
+    if (i.hasNext) i.next;
+    else throw new NoSuchElementException;
+  }
+  override def last  : A = {
+    var last : A = null.asInstanceOf[A];
+    val i = elements;
+    while (i.hasNext) last = i.next;
+    if (last == null) throw new NoSuchElementException;
+    else last;
+  }
+  override def rangeImpl(from : Option[A], until : Option[A]) : SortedSet[A];
+  override def from(from: A) = rangeImpl(Some(from), None);
+  override def until(until: A) = rangeImpl(None, Some(until));
+  override def range(from: A, until: A) = rangeImpl(Some(from),Some(until));
+
+  override def subsetOf(that: Set[A]): Boolean = that match {
+  case that : SortedSet[A] => that.hasAll(elements);
+  case that => super.subsetOf(that);
+  }
+
+}
diff --git a/src/library/scala/collection/TreeWalker.scala b/src/library/scala/collection/TreeWalker.scala
new file mode 100644
index 0000000000..64200a4288
--- /dev/null
+++ b/src/library/scala/collection/TreeWalker.scala
@@ -0,0 +1,58 @@
+package scala.collection;
+
+object TreeWalker {
+  object Empty extends TreeWalker[Nothing] {
+    def hasNext = None;
+    def next = throw new NoSuchElementException;
+  }
+  private case class NonEmpty[+A](item : A, right : () => TreeWalker[A]) extends TreeWalker[A] {
+    private var spent = false;
+    def hasNext = if (spent) right().hasNext else Some(this);
+    def next = if (spent) right().next else {
+      spent = true;
+      item;
+    }
+  }
+  def apply[A](                      item : A                             ) :       TreeWalker[A] =       NonEmpty(item, () => Empty);
+  def apply[A](                      item : A, right : () => TreeWalker[A]) : () => TreeWalker[A] = () => NonEmpty(item, right);
+  def apply[A](left : TreeWalker[A], item : A, right : () => TreeWalker[A]) :       TreeWalker[A] = left match {
+  case Empty => NonEmpty(item, right);
+  case NonEmpty(first, middle) =>
+    val rest = NonEmpty(item,right);
+    NonEmpty(first, apply(middle, () => rest));
+  }
+  def apply[A](left : () => TreeWalker[A], right : () => TreeWalker[A]) : () => TreeWalker[A] = () => (left() match {
+  case Empty => right();
+  case NonEmpty(item, middle) => NonEmpty(item, apply(middle, right));
+  });
+}
+
+sealed abstract class TreeWalker[+A] {
+  def hasNext : Option[TreeWalker[A]];
+  def next : A;
+  def append[B >: A](item : B) : TreeWalker[B] = append(item, () => TreeWalker.Empty);
+  def append[B >: A](item : B, right : () => TreeWalker[B]) : TreeWalker[B] = TreeWalker[B](this, item, right);
+  def append[B >: A](right : () => TreeWalker[B]) = TreeWalker(() => this,right)();
+  class Elements extends Iterator[A] {
+    private var cursor : TreeWalker[Any] = TreeWalker.this;
+    def check = {
+      if (!(cursor eq null)) cursor.hasNext match {
+      case None => cursor = null;
+      case Some(c) if !(c eq cursor) =>
+        cursor = c;
+      case Some(_) =>
+      }
+      cursor;
+    }
+    def hasNext = !(check eq null);
+    def next = check match {
+    case null => throw new NoSuchElementException;
+    case cursor => cursor.next.asInstanceOf[A];
+    }
+  }
+  def elements = new Elements;
+}
+
+
+
+
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
index 9c71016a1b..8a10b324e7 100755
--- a/src/library/scala/collection/immutable/RedBlack.scala
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -9,6 +9,7 @@
 // $Id: $
 
 package scala.collection.immutable
+import scala.collection.TreeWalker
 
 @serializable
 abstract class RedBlack[A] {
@@ -29,10 +30,17 @@ abstract class RedBlack[A] {
     def lookup(x: A): Tree[B]
     def update[B1 >: B](k: A, v: B1): Tree[B1] = blacken(upd(k, v))
     def delete(k: A): Tree[B] = del(k)
-    def elements: Iterator[(A, B)]
+
+    def visit[T](input : T)(f : (T,A,B) => Tuple2[Boolean,T]) : Tuple2[Boolean,T];
+    def elements : TreeWalker[Pair[A,B]];
+    def elementsSlow: Iterator[Pair[A, B]];
     def upd[B1 >: B](k: A, v: B1): Tree[B1]
     def del(k: A): Tree[B]
     def smallest: NonEmpty[B]
+    def range(from : Option[A], until : Option[A]) : Tree[B]
+    def first : A
+    def last : A
+    def count : Int
   }
   @serializable
   abstract class NonEmpty[+B] extends Tree[B] {
@@ -77,8 +85,34 @@ abstract class RedBlack[A] {
       }
     }
     def smallest: NonEmpty[B] = if (left.isEmpty) this else left.smallest
-    def elements: Iterator[(A, B)] =
-      left.elements append Iterator.single((key, value)) append right.elements
+    def elements : TreeWalker[Pair[A,B]] =
+      left.elements.append(Pair(key,value), () => right.elements)
+
+    def elementsSlow: Iterator[Pair[A, B]] =
+      left.elementsSlow append Iterator.single(Pair(key, value)) append right.elementsSlow
+
+    def visit[T](input : T)(f : (T,A,B) => Tuple2[Boolean,T]) : Tuple2[Boolean,T] = {
+      val left = this.left.visit(input)(f)
+      if (!left._1) return left
+      val middle = f(left._2, key, value)
+      if (!middle._1) return middle
+      return this.right.visit(middle._2)(f)
+    }
+   override def range(from : Option[A], until : Option[A]) : Tree[B] = {
+      if (from == None && until == None) return this
+      if (from != None && isSmaller(key, from.get)) return right.range(from, until);
+      if (until != None && (isSmaller(until.get,key) || !isSmaller(key,until.get)))
+        return left.range(from, until);
+      val newLeft = left.range(from, None)
+      val newRight = right.range(None, until)
+      if ((newLeft eq left) && (newRight eq right)) this
+      else if (newLeft eq Empty) newRight.upd(key, value);
+      else if (newRight eq Empty) newLeft.upd(key, value);
+      else mkTree(isBlack, key, value, newLeft, newRight)
+    }
+    def first = if (left .isEmpty) key else left.first
+    def last  = if (right.isEmpty) key else right.last
+    def count = 1 + left.count + right.count
   }
   @serializable
   case object Empty extends Tree[Nothing] {
@@ -88,7 +122,15 @@ abstract class RedBlack[A] {
     def upd[B](k: A, v: B): Tree[B] = RedTree(k, v, Empty, Empty)
     def del(k: A): Tree[Nothing] = this
     def smallest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
-    def elements: Iterator[(A, Nothing)] = Iterator.empty
+    def elementsSlow: Iterator[Pair[A, Nothing]] = Iterator.empty
+    def elements : TreeWalker[Pair[A,Nothing]] = TreeWalker.Empty
+
+    def visit[T](input : T)(f : (T,A,Nothing) => Tuple2[Boolean,T]) = Tuple2(true,input)
+
+    def range(from : Option[A], until : Option[A]) = this
+    def first = throw new NoSuchElementException("empty map")
+    def last = throw new NoSuchElementException("empty map")
+    def count = 0
   }
   @serializable
   case class RedTree[+B](override val key: A,
diff --git a/src/library/scala/collection/immutable/SortedMap.scala b/src/library/scala/collection/immutable/SortedMap.scala
new file mode 100644
index 0000000000..a26f734755
--- /dev/null
+++ b/src/library/scala/collection/immutable/SortedMap.scala
@@ -0,0 +1,38 @@
+package scala.collection.immutable;
+
+trait SortedMap[A,+B] extends Map[A,B] with collection.SortedMap[A,B] {
+  override def rangeImpl(from : Option[A], until : Option[A]) : SortedMap[A,B];
+  override def from(from: A) = rangeImpl(Some(from), None);
+  override def until(until: A) = rangeImpl(None, Some(until));
+  override def range(from: A, until: A) = rangeImpl(Some(from),Some(until));
+  override def empty[C]: SortedMap[A, C]
+  override def update [B1 >: B] (key: A, value: B1): SortedMap[A, B1]
+  override def + [B1 >: B] (kv: Pair[A, B1]): SortedMap[A, B1] = update(kv._1, kv._2)
+
+  override def + [B1 >: B] (kv1: Pair[A, B1], kv2: Pair[A, B1], kvs: Pair[A, B1]*): SortedMap[A, B1] =
+    this + kv1 + kv2 ++ kvs
+  override def ++ [B1 >: B] (kvs: Iterable[Pair[A, B1]]): SortedMap[A, B1] =
+    ((this: SortedMap[A, B1]) /: kvs) ((m, kv) => m + kv)
+  override def ++ [B1 >: B] (kvs: Iterator[Pair[A, B1]]): SortedMap[A, B1] =
+    ((this: SortedMap[A, B1]) /: kvs) ((m, kv) => m + kv)
+  override def - (key: A): SortedMap[A, B]
+  override def - (key1: A, key2: A, keys: A*): SortedMap[A, B] =
+    this - key1 - key2 -- keys
+  override def -- (keys: Iterable[A]): SortedMap[A, B] = this -- keys.elements
+
+  override def -- (keys: Iterator[A]): SortedMap[A, B] =
+    (this /: keys) ((m, key) => m - key)
+
+  override def transform[C](f: (A, B) => C): SortedMap[A, C] = {
+    var res = empty[C]
+    foreach { case Pair(key, value) => res = res.update(key, f(key, value)) }
+    res
+  }
+  override def filter(p: Pair[A, B] => Boolean): SortedMap[A, B] = {
+    var res = this
+    foreach {
+      case kv @ Pair(key, _) => if (!p(kv)) { res = res - key }
+    }
+    res
+  }
+}
\ No newline at end of file
diff --git a/src/library/scala/collection/immutable/SortedSet.scala b/src/library/scala/collection/immutable/SortedSet.scala
new file mode 100644
index 0000000000..05eaefe692
--- /dev/null
+++ b/src/library/scala/collection/immutable/SortedSet.scala
@@ -0,0 +1,3 @@
+package scala.collection.immutable
+
+trait SortedSet[A] extends scala.collection.SortedSet[A] with Set[A]
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index 2a61f3d46f..7e98e3a1fd 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -37,7 +37,7 @@ object TreeMap {
  */
 @serializable
 class TreeMap[A <% Ordered[A], +B](val size: int, t: RedBlack[A]#Tree[B])
-extends RedBlack[A] with Map[A, B] {
+extends RedBlack[A] with SortedMap[A, B] {
 
   def isSmaller(x: A, y: A) = x < y
 
@@ -45,11 +45,22 @@ extends RedBlack[A] with Map[A, B] {
 
   protected val tree: RedBlack[A]#Tree[B] = if (size == 0) Empty else t
 
+  override def rangeImpl(from : Option[A], until : Option[A]) : SortedMap[A,B] = {
+    val ntree = tree.range(from,until)
+    new TreeMap[A,B](ntree.count, ntree)
+  }
+  override def first = t.first
+  override def last = t.last
+  override def compare(k0: A, k1: A): Int = k0.compare(k1)
+
+
+
+
   private def newMap[B](s: int, t: RedBlack[A]#Tree[B]) = new TreeMap[A, B](s, t)
 
   /** A factory to create empty maps of the same type of keys.
    */
-  def empty[C] = ListMap.empty[A, C]
+  def empty[C] = TreeMap.empty[A, C]
 
   /** A new TreeMap with the entry added is returned,
    *  if key is <em>not</em> in the TreeMap, otherwise
@@ -105,7 +116,19 @@ extends RedBlack[A] with Map[A, B] {
    *
    *  @return the new iterator
    */
-  def elements: Iterator[(A, B)] = tree.elements
+  def elements: Iterator[Pair[A, B]] = tree.elements.elements
+
+  override def foreach(f : Tuple2[A,B] => Unit) : Unit =
+    tree.visit[Unit](())((unit0,a,b) => Tuple2(true, f(Tuple2(a,b))))
+  override def forall(f : Tuple2[A,B] => Boolean) : Boolean =
+    tree.visit[Boolean](true)((input,a,b) => f(Tuple2(a,b)) match {
+    case ret if input => Tuple2(ret,ret)
+    })._2
+  override def exists(f : Tuple2[A,B] => Boolean) : Boolean =
+    tree.visit[Boolean](false)((input,a,b) => f(Tuple2(a,b)) match {
+    case ret if !input => Tuple2(!ret,ret)
+    })._2
+
 }
 
 
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 33c165d3db..8dd1142557 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -36,7 +36,7 @@ object TreeSet {
 
 @serializable
 class TreeSet[A <% Ordered[A]](val size: int, t: RedBlack[A]#Tree[Unit])
-extends RedBlack[A] with Set[A] {
+  extends RedBlack[A] with SortedSet[A] {
 
   def isSmaller(x: A, y: A) = x < y
 
@@ -81,5 +81,26 @@ extends RedBlack[A] with Set[A] {
    *
    *  @return the new iterator
    */
-  def elements: Iterator[A] = tree.elements map (._1)
+  def elements: Iterator[A] = tree.elements.elements map (._1)
+
+  def elementsSlow = tree.elementsSlow map (._1)
+
+  override def foreach(f : A => Unit) : Unit =
+    tree.visit[Unit](())((unit0,y,unit1) => Tuple2(true, f(y)))
+  override def forall(f : A => Boolean) : Boolean =
+    tree.visit[Boolean](true)((input,a,unit) => f(a) match {
+    case ret if input => Tuple2(ret,ret)
+    })._2
+  override def exists(f : A => Boolean) : Boolean =
+    tree.visit[Boolean](false)((input,a,unit) => f(a) match {
+    case ret if !input => Tuple2(!ret,ret)
+    })._2
+
+   override def rangeImpl(from: Option[A], until: Option[A]) : TreeSet[A] = {
+     val tree = this.tree.range(from,until)
+     newSet(tree.count, tree)
+   }
+   override def first = tree.first
+   override def last = tree.last
+   override def compare(a0 : A, a1 : A) = a0.compare(a1)
 }
diff --git a/src/library/scala/collection/jcl/Ranged.scala b/src/library/scala/collection/jcl/Ranged.scala
index 51c5aba6a4..7e837c4f19 100644
--- a/src/library/scala/collection/jcl/Ranged.scala
+++ b/src/library/scala/collection/jcl/Ranged.scala
@@ -14,7 +14,7 @@ package scala.collection.jcl;
  *
  *  @author Sean McDirmid
  */
-trait Ranged[K,A] extends MutableIterable[A] {
+trait Ranged[K,A] extends MutableIterable[A] with scala.collection.Ranged[K,A] {
   protected type SortedSelf <: Ranged[K,A];
 
   /** Returns the first key of the collection. */
@@ -40,16 +40,16 @@ trait Ranged[K,A] extends MutableIterable[A] {
   /** Creates a ranged projection of this collection with no upper-bound.
    ** @param from The lower-bound (inclusive) of the ranged projection.
    **/
-  final def from(from: K): SortedSelf = rangeImpl(Some(from), None);
+  override final def from(from: K): SortedSelf = rangeImpl(Some(from), None);
   /** Creates a ranged projection of this collection with no lower-bound.
    ** @param until The upper-bound (exclusive) of the ranged projection.
    **/
-  final def until(until: K): SortedSelf = rangeImpl(None, Some(until));
+  override final def until(until: K): SortedSelf = rangeImpl(None, Some(until));
 
   /** Creates a ranged projection of this collection with both a lower-bound and an upper-bound.
    ** @param from The upper-bound (exclusive) of the ranged projection.
    **/
-  final def range(from: K, until: K) : SortedSelf = rangeImpl(Some(from),Some(until));
+  override final def range(from: K, until: K) : SortedSelf = rangeImpl(Some(from),Some(until));
 
   /** A wrapper around Java comparators. */
   protected class Comparator[K <% Ordered[K]] extends java.util.Comparator {
diff --git a/src/library/scala/collection/jcl/Set.scala b/src/library/scala/collection/jcl/Set.scala
index 08d4013bd4..bed84a8462 100644
--- a/src/library/scala/collection/jcl/Set.scala
+++ b/src/library/scala/collection/jcl/Set.scala
@@ -26,7 +26,11 @@ trait Set[A] extends Collection[A] with scala.collection.mutable.Set[A] {
   override def retain(f : A => Boolean) = super[Collection].retain(f);
   override def isEmpty = super[Collection].isEmpty;
   override final def contains(a : A) = has(a);
-  override def clear() = super.clear()
+  override def clear() = super.clear();
+  override def subsetOf(set : scala.collection.Set[A]) = set match {
+  case set : Set[A] => set.hasAll(this);
+  case set => super.subsetOf(set);
+  }
 
   override def transform(f : A => A) = {
     var toAdd : List[A] = Nil;
diff --git a/src/library/scala/collection/jcl/Sorted.scala b/src/library/scala/collection/jcl/Sorted.scala
index c9ff2b3990..7bbe49da75 100644
--- a/src/library/scala/collection/jcl/Sorted.scala
+++ b/src/library/scala/collection/jcl/Sorted.scala
@@ -14,10 +14,10 @@ package scala.collection.jcl;
  *
  *  @author Sean McDirmid
  */
-trait Sorted[K,A] extends Ranged[K,A] {
+trait Sorted[K,A] extends scala.collection.Sorted[K,A] with Ranged[K,A] {
   override protected type SortedSelf <: Sorted[K,A];
   /** return as a projection the set of keys in this collection */
-  def keySet : SortedSet[K];
+  override def keySet : SortedSet[K];
 
   /** Creates a ranged projection of this collection. Any mutations in the
    *  ranged projection will update this collection and vice versa.  Keys
@@ -33,7 +33,7 @@ trait Sorted[K,A] extends Ranged[K,A] {
   /** Create a range projection of this collection with no lower-bound.
    ** @param to The upper-bound (inclusive) of the ranged projection.
    **/
-  final def to(to : K): SortedSelf = {
+  final override def to(to : K): SortedSelf = {
     // tough!
     val i = keySet.from(to).elements;
     if (!i.hasNext) return this.asInstanceOf[SortedSelf];
diff --git a/src/library/scala/collection/jcl/SortedMap.scala b/src/library/scala/collection/jcl/SortedMap.scala
index 1449addf3b..ede870a6c9 100644
--- a/src/library/scala/collection/jcl/SortedMap.scala
+++ b/src/library/scala/collection/jcl/SortedMap.scala
@@ -14,7 +14,7 @@ package scala.collection.jcl;
  *
  *  @author Sean McDirmid
  */
-trait SortedMap[K,E] extends Map[K,E] with Sorted[K,Tuple2[K,E]] {
+trait SortedMap[K,E] extends scala.collection.SortedMap[K,E] with Map[K,E] with Sorted[K,Tuple2[K,E]] {
   final protected type SortedSelf = SortedMap[K,E];
   override def compare(k0 : K, k1 : K) : Int;
   override def first : K = elements.next._1;
diff --git a/src/library/scala/collection/jcl/SortedSet.scala b/src/library/scala/collection/jcl/SortedSet.scala
index 729c778106..bc381edb83 100644
--- a/src/library/scala/collection/jcl/SortedSet.scala
+++ b/src/library/scala/collection/jcl/SortedSet.scala
@@ -14,16 +14,19 @@ package scala.collection.jcl;
  *
  *  @author Sean McDirmid
  */
-trait SortedSet[A] extends jcl.Set[A] with Sorted[A,A] {
+trait SortedSet[A] extends scala.collection.SortedSet[A] with jcl.Set[A] with Sorted[A,A] {
   final protected type SortedSelf = SortedSet[A];
   override def keySet = this;
   def compare(a0 : A, a1 : A) : Int;
-  def first : A = {
+  override def first : A = {
     val i = elements;
     if (i.hasNext) i.next;
     else throw new NoSuchElementException;
   }
-  def last  : A = {
+  override def subsetOf(that : scala.collection.Set[A]) = super[SortedSet].subsetOf(that);
+  override def hasAll(that : Iterable[A]) = super[Sorted].hasAll(that.elements);
+
+  override def last  : A = {
     var last : A = null.asInstanceOf[A];
     val i = elements;
     while (i.hasNext) last = i.next;
diff --git a/src/library/scala/runtime/BooleanRef.java b/src/library/scala/runtime/BooleanRef.java
index b3e3f0e58f..eeb0e05055 100644
--- a/src/library/scala/runtime/BooleanRef.java
+++ b/src/library/scala/runtime/BooleanRef.java
@@ -15,4 +15,5 @@ package scala.runtime;
 public class BooleanRef implements java.io.Serializable {
     public boolean elem;
     public BooleanRef(boolean elem) { this.elem = elem; }
+    public String toString() { return "" + elem; }
 }