Initial check-in of Java collection library wra...

Initial check-in of Java collection library wrappers (JCL).

32 files changed, 1173 insertions, 0 deletions

diff --git a/src/library/scala/collection/jcl/ArrayList.scala b/src/library/scala/collection/jcl/ArrayList.scala
new file mode 100644
index 0000000000..5de213ce2a
--- /dev/null
+++ b/src/library/scala/collection/jcl/ArrayList.scala
@@ -0,0 +1,9 @@
+package scala.collection.jcl;
+
+/** Creates a buffer backed by a Java array list.
+ * @author Sean McDirmid
+ */
+class ArrayList[A](override val underlying : java.util.ArrayList) extends ConcreteWrapper[A] with BufferWrapper[A]  {
+  def this() = this(new java.util.ArrayList);
+  override def elements = super[BufferWrapper].elements;
+}
diff --git a/src/library/scala/collection/jcl/Buffer.scala b/src/library/scala/collection/jcl/Buffer.scala
new file mode 100644
index 0000000000..0919e62914
--- /dev/null
+++ b/src/library/scala/collection/jcl/Buffer.scala
@@ -0,0 +1,137 @@
+package scala.collection.jcl;
+
+/** A mutable sequence that supports element insertion and update.
+ *
+ * @author Sean McDirmid
+ */
+trait Buffer[A] extends MutableSeq[A] with Collection[A] with Sorted[Int,A] {
+  final protected type SortedSelf = Buffer[A];
+  override def elements : BufferIterator[Int,A];
+  /** The first index of a buffer is 0. */
+  override def first = 0;
+  /** The last index of a buffer is its size - 1. */
+  override def last = size - 1;
+  /** Indices are compared through subtraction. */
+  final def compare(k0 : Int, k1 : Int) = k0 - k1;
+  /** Removes the element at index "idx" */
+  def remove(idx : Int) = {
+    val i = elements;
+    val ret = i.seek(idx); i.remove; ret;
+  }
+  /** Replaces the element at index "idx" with "a."
+    * @returns the element replaced.
+    */
+  def set(idx : Int, a : A) : A = {
+    val i = elements;
+    val ret = i.seek(idx); i.set(a); ret;
+  }
+  /** Equivalent to set except the replaced element is not returned. */
+  def update(idx : Int, a : A) : Unit = set(idx, a);
+  /** @returns always true. */
+  def add(a : A) : Boolean = {
+    val i = elements;
+    while (i.hasNext) i.next;
+    i.add(a);
+    true;
+  }
+  /** Inserts "a" into this buffer just before the element at index "idx." */
+  def add(idx : Int, a : A) : Unit = {
+    val i = elements; i.seek(idx);
+    i.add(a);
+  }
+  /** Inserts all elements of "that" into this buffer just before the element at index "idx." */
+  def addAll(idx : Int, that : Iterable[A]) : Unit = {
+    val i = elements; i.seek(idx);
+    for (val that <- that) {
+      i.add(that); i.next;
+    }
+  }
+  override def transform(f : A => A) : Boolean = {
+    var changed = false;
+    val i = elements;
+    while (i.hasNext) {
+      val a0 = i.next;
+      val a1 = f(a0);
+      if (a0 != a1) {
+        i.set(a1); changed = true;
+      }
+    }
+    changed;
+  }
+  override def +(a : A) : this.type = super[Collection].+(a);
+  override def -=(a : A) = super[Collection].-=(a);
+  override def isEmpty = super[MutableSeq].isEmpty;
+  override def pfilter(p : A => Boolean) : MutableSeq[A] = super[MutableSeq].pfilter(p);
+  override def rangeImpl(from : Option[Int], until : Option[Int]) : Buffer[A] = new Range(from, until);
+
+  protected class Range(var from : Option[Int], var until : Option[Int]) extends Buffer[A] {
+    if (from == None && until == None) throw new IllegalArgumentException;
+    if (from != None && until != None && !(from.get < until.get)) throw new IllegalArgumentException;
+    override def add(a : A) =
+      if (until == None) Buffer.this.add(a);
+      else {
+        Buffer.this.add(until.get, a);
+        true;
+      }
+    private def translate(idx : Int) = {
+      if (until != None && idx > until.get) throw new IllegalArgumentException;
+      else if (from != None) from.get + idx;
+      else idx;
+    }
+    override def apply(idx : Int) : A = Buffer.this.apply(translate(idx));
+    override def set(idx : Int, a : A) = Buffer.this.set(translate(idx), a);
+    override def add(idx : Int, a : A) = Buffer.this.add(translate(idx), a);
+    override def remove(idx : Int) = Buffer.this.remove(translate(idx));
+    override def size = {
+      if (until != None) {
+        if (from != None) until.get - from.get;
+        else until.get;
+      } else super.size;
+    }
+    def elements : BufferIterator[Int,A] = new RangeIterator;
+    class RangeIterator extends BufferIterator[Int,A] {
+      val underlying = Buffer.this.elements;
+      if (from != None) underlying.seek(from.get);
+      def hasNext = underlying.hasNext &&
+        (until == None || underlying.nextIndex < until.get);
+      def hasPrevious = underlying.hasPrevious &&
+        (from == None || underlying.previousIndex >= from.get);
+      def next = {
+        if (until != None && underlying.nextIndex >= until.get) throw new NoSuchElementException;
+        underlying.next;
+      }
+      def previous = {
+        if (from != None && underlying.previousIndex < from.get) throw new NoSuchElementException;
+        underlying.previous;
+      }
+      def add(a : A) = {
+        if (until != None && underlying.nextIndex > until.get) throw new NoSuchElementException;
+        if (from != None && underlying.previousIndex < from.get) throw new NoSuchElementException;
+        underlying.add(a);
+        if (until != None) until = Some(until.get + 1);
+      }
+      def set(a : A) = {
+        if (until != None && underlying.nextIndex > until.get) throw new NoSuchElementException;
+        if (from != None && underlying.previousIndex < from.get) throw new NoSuchElementException;
+        underlying.set(a);
+      }
+      def remove = {
+        if (until != None && underlying.nextIndex > until.get) throw new NoSuchElementException;
+        if (from != None && underlying.previousIndex < from.get) throw new NoSuchElementException;
+        underlying.remove;
+      }
+      def nextIndex = {
+        val ret = underlying.nextIndex;
+        if (until != None && ret >= until.get) throw new NoSuchElementException;
+        if (from != None) ret - from.get;
+        else ret;
+      }
+      def previousIndex = {
+        val ret = underlying.previousIndex;
+        if (from != None && ret < from.get) throw new NoSuchElementException;
+        if (from != None) ret - from.get;
+        else ret;
+      }
+    }
+  }
+}
diff --git a/src/library/scala/collection/jcl/BufferIterator.scala b/src/library/scala/collection/jcl/BufferIterator.scala
new file mode 100644
index 0000000000..be1101df9f
--- /dev/null
+++ b/src/library/scala/collection/jcl/BufferIterator.scala
@@ -0,0 +1,19 @@
+package scala.collection.jcl;
+
+/** An iterator for a buffer that supports element update and insertion.
+ * @author Sean McDirmid
+ */
+trait BufferIterator[K,A] extends SeqIterator[K,A] {
+  /** Sets the element before this iterator's cursor to "a."
+    * Replaces either the last element returned by "next" or,
+    * if previous was called,
+    * the next element that would be return by "previous."
+    */
+  def set(a : A) : Unit;
+
+  /** Inserts "a" after the iterator's cursor.
+      If next was last called, "a" is inserted after the element returned.
+      If previous was last called, "a" is inserted before the element returned.
+    */
+  def add(a : A) : Unit;
+}
diff --git a/src/library/scala/collection/jcl/BufferWrapper.scala b/src/library/scala/collection/jcl/BufferWrapper.scala
new file mode 100644
index 0000000000..2364322d28
--- /dev/null
+++ b/src/library/scala/collection/jcl/BufferWrapper.scala
@@ -0,0 +1,40 @@
+package scala.collection.jcl;
+
+/** Wraps Java lists.
+  * @author Sean McDirmid
+  */
+trait BufferWrapper[A] extends Buffer[A] with CollectionWrapper[A] {
+  protected def underlying : java.util.List;
+  override def elements : BufferIterator[Int,A] = new IteratorWrapper(underlying.listIterator);
+  override def remove(idx : Int) = underlying.remove(idx).asInstanceOf[A];
+  override def add(a : A) = underlying.add(a);
+  override def add(idx : Int, a : A) = underlying.add(idx,a);
+  override def addAll(idx : Int, that : Iterable[A]) = that match {
+  case that : CollectionWrapper[_] => underlying.addAll(idx, that.underlying0); {}
+  case _ => super.addAll(idx, that);
+  }
+  override def indexOf(a : A) = {
+    val result = underlying.indexOf(a);
+    if (result == -1) None;
+    else Some(result);
+  }
+  override def apply(idx : Int) = underlying.get(idx).asInstanceOf[A];
+  override def set(idx : Int, a : A) = underlying.set(idx, a).asInstanceOf[A];
+  override def rangeImpl(from : Option[Int], until : Option[Int]) : Buffer[A] = new Range(from, until);
+  protected class Range(from : Option[Int], until : Option[Int]) extends super.Range(from,until) with BufferWrapper[A] {
+    val underlying = {
+      val fromi = if (from == None) 0 else from.get;
+      val toi = if (until == None) BufferWrapper.this.size else until.get;
+      BufferWrapper.this.underlying.subList(fromi, toi);
+    }
+    override def elements = super[BufferWrapper].elements;
+  }
+  class IteratorWrapper(underlying : java.util.ListIterator) extends super.IteratorWrapper(underlying) with BufferIterator[Int,A] {
+    def add(a : A) = underlying.add(a);
+    def set(a : A) = underlying.set(a);
+    def hasPrevious = underlying.hasPrevious;
+    def previous = underlying.previous.asInstanceOf[A];
+    def previousIndex = underlying.previousIndex;
+    def nextIndex = underlying.nextIndex;
+  }
+}
diff --git a/src/library/scala/collection/jcl/Collection.scala b/src/library/scala/collection/jcl/Collection.scala
new file mode 100644
index 0000000000..2b2589fdfc
--- /dev/null
+++ b/src/library/scala/collection/jcl/Collection.scala
@@ -0,0 +1,65 @@
+package scala.collection.jcl;
+object Collection {
+  val DEFAULT_FILTER : Any => Boolean = x => true;
+}
+
+/** Analogous to a Java collection.
+ **
+ ** @author Sean McDirmid
+ **/
+trait Collection[A] extends MutableIterable[A] {
+  /** Type-safe version of containsAll.
+   **
+   ** @author Sean McDirmid
+   **/
+  def hasAll(i : Iterable[A]) : Boolean = i.forall(elements.has);
+  /** Adds "a" to the collection, return true if "a" is actually added. */
+  def add(a : A ) : Boolean;
+  /** Adds all elements in "i" to the collection, return true if any elements are added. */
+  def addAll(i : Iterable[A]) : Boolean = {
+    var changed = false;
+    i.foreach(t => changed = add(t) || changed);
+    changed;
+  }
+  /** Operator shortcut for addAll. */
+  def ++(that : Iterable[A]) : this.type = {
+    addAll(that); this;
+  }
+
+
+  /** removes "a" from the collection. */
+  def -=(a : A) : Unit = remove(a);
+  /** adds "a" from the collection. */
+  def +=(t : A) : Unit = add(t);
+  /** adds "a" from the collection. Useful for chaining. */
+  def +(t : A) : this.type = { add(t); this; }
+
+  /** Transforms each element of the collection in-place according to "f." Returns true
+   ** if the collection is actually updated.
+   **/
+  def transform(f : A => A) : Boolean;
+  /** Used for non-strict filtered collection that only includes elements of this collection that are true for "p."
+   ** Any elements added to or removed from the resulting
+   ** filter will update this collection. Any changes to this collection
+   ** can update the filtered collection.
+   ** @return a non-strict filter of this collection.
+   **/
+  def pfilter(p : A => Boolean) : MutableIterable[A] = new Filter(p);
+  /** Base implementation of a filtered collection */
+  class Filter(p : A => Boolean) extends Collection[A] {
+    def transform(f : A => A) =
+      Collection.this.transform(a => if (p(a)) f(a) else a);
+    override def add(a : A) = {
+      if (!p(a)) throw new IllegalArgumentException;
+      Collection.this.add(a);
+    }
+    override def has(a : A) = if (!p(a)) false else Collection.this.has(a);
+    override def remove(a : A) = {
+      if (!p(a)) throw new IllegalArgumentException;
+      Collection.this.remove(a);
+    }
+    override def pfilter(p1 : A => Boolean) : MutableIterable[A] =
+      Collection.this.pfilter(a => p(a) && p1(a));
+    def elements = Collection.this.elements.filter(p);
+  }
+}
diff --git a/src/library/scala/collection/jcl/CollectionWrapper.scala b/src/library/scala/collection/jcl/CollectionWrapper.scala
new file mode 100644
index 0000000000..94a439e269
--- /dev/null
+++ b/src/library/scala/collection/jcl/CollectionWrapper.scala
@@ -0,0 +1,25 @@
+package scala.collection.jcl;
+
+/** Used to wrap Java collections in Scala.
+ **
+ ** @author Sean McDirmid
+ **/
+trait CollectionWrapper[A] extends Collection[A] with IterableWrapper[A] {
+  /** Override to specify the collection being accessed through this wrapper.
+   ** Collection operations are then routed through the wrapped Java collection.
+   **/
+  protected def underlying : java.util.Collection;
+  private[jcl] final def underlying0 = underlying;
+  override def has(a : A) = underlying.contains(a);
+  override def elements : MutableIterator[A] = super.elements;
+
+  override def hasAll(that : Iterable[A]) = that match {
+  case that : CollectionWrapper[_] => underlying.containsAll(that.underlying);
+  case _ => super.hasAll(that);
+  }
+  override def add(a : A) = underlying.add(a);
+  override def addAll(that : Iterable[A]) = that match {
+  case that : CollectionWrapper[_] => underlying.addAll(that.underlying);
+  case _ => super.addAll(that);
+  }
+}
diff --git a/src/library/scala/collection/jcl/ConcreteMapWrapper.scala b/src/library/scala/collection/jcl/ConcreteMapWrapper.scala
new file mode 100644
index 0000000000..1f9a16dab4
--- /dev/null
+++ b/src/library/scala/collection/jcl/ConcreteMapWrapper.scala
@@ -0,0 +1,14 @@
+package scala.collection.jcl;
+
+/** A concrete wrapper around a Java map. The identity of the wraper is fixed to the identity of the underlying map.
+  * @author Sean McDirmid
+  */
+abstract class ConcreteMapWrapper[K,E] extends MapWrapper[K,E] {
+  val underlying : java.util.Map;
+  override def toString = underlying.toString;
+  override def hashCode = underlying.hashCode;
+  override def equals(that : Any) = that match {
+  case that : ConcreteMapWrapper[_,_] => underlying == that.underlying;
+  case _ => false;
+  }
+}
diff --git a/src/library/scala/collection/jcl/ConcreteWrapper.scala b/src/library/scala/collection/jcl/ConcreteWrapper.scala
new file mode 100644
index 0000000000..f113ba827e
--- /dev/null
+++ b/src/library/scala/collection/jcl/ConcreteWrapper.scala
@@ -0,0 +1,18 @@
+package scala.collection.jcl;
+
+/* Describes wrappers around concrete underlying collections. The identity
+ * of the wrapper is related strictly to the Java collection being wrapped,
+ * which is structurally determined.
+ *
+ * @author Sean McDirmid
+ */
+abstract class ConcreteWrapper[A] extends CollectionWrapper[A] {
+  val underlying : java.util.Collection;
+  override def elements : MutableIterator[A] = super.elements;
+  override def toString = underlying.toString;
+  override def hashCode = underlying.hashCode;
+  override def equals(that : Any) = that match {
+  case that : ConcreteWrapper[_] => underlying == that.underlying;
+  case _ => false;
+  }
+}
diff --git a/src/library/scala/collection/jcl/HashMap.scala b/src/library/scala/collection/jcl/HashMap.scala
new file mode 100644
index 0000000000..f87631396e
--- /dev/null
+++ b/src/library/scala/collection/jcl/HashMap.scala
@@ -0,0 +1,8 @@
+package scala.collection.jcl;
+
+/** A map that is backed by a Java hash map.
+  * @author Sean McDirmid
+  */
+class HashMap[K,E](override val underlying : java.util.HashMap) extends ConcreteMapWrapper[K,E] {
+  def this() = this(new java.util.HashMap);
+}
diff --git a/src/library/scala/collection/jcl/HashSet.scala b/src/library/scala/collection/jcl/HashSet.scala
new file mode 100644
index 0000000000..005db81a36
--- /dev/null
+++ b/src/library/scala/collection/jcl/HashSet.scala
@@ -0,0 +1,10 @@
+package scala.collection.jcl;
+
+/** A hash set that is backed by a Java hash set.
+ **
+ ** @author Sean McDirmid
+ **/
+class HashSet[A](override val underlying : java.util.HashSet) extends ConcreteWrapper[A] with SetWrapper[A] {
+  /** Creates an underlying Java hash set. */
+  def this() = this(new java.util.HashSet);
+}
diff --git a/src/library/scala/collection/jcl/IdentityHashMap.scala b/src/library/scala/collection/jcl/IdentityHashMap.scala
new file mode 100644
index 0000000000..e1aa07c72e
--- /dev/null
+++ b/src/library/scala/collection/jcl/IdentityHashMap.scala
@@ -0,0 +1,9 @@
+package scala.collection.jcl;
+
+/** A map that is backed by a Java identity hash map, which compares keys by their reference-based identity
+   * as opposed to using equals and hashCode. An identity hash map will often perform better than traditional hash map because it can utilize linear probing.
+   * @author Sean McDirmid
+   */
+class IdentityHashMap[K,E](override val underlying : java.util.IdentityHashMap) extends ConcreteMapWrapper[K,E] {
+  def this() = this(new java.util.IdentityHashMap);
+}
diff --git a/src/library/scala/collection/jcl/IterableWrapper.scala b/src/library/scala/collection/jcl/IterableWrapper.scala
new file mode 100644
index 0000000000..10d37f5549
--- /dev/null
+++ b/src/library/scala/collection/jcl/IterableWrapper.scala
@@ -0,0 +1,27 @@
+package scala.collection.jcl;
+/** A wrapper around a Java collection that only supports remove mutations.
+ * @author Sean McDirmid
+ */
+trait IterableWrapper[A] extends MutableIterable[A] {
+  protected def underlying : java.util.Collection;
+  override def remove(a : A) = underlying.remove(a);
+  override def removeAll(that : Iterable[A]) = that match {
+  case that : IterableWrapper[_] => underlying.removeAll(that.underlying);
+  case _ => super.removeAll(that);
+  }
+  override def retainAll(that : Iterable[A]) = that match {
+  case that : IterableWrapper[_] => underlying.retainAll(that.underlying);
+  case _ => super.retainAll(that);
+  }
+  override def size = underlying.size;
+  override def isEmpty = underlying.isEmpty;
+  override def clear = underlying.clear;
+  override def elements : MutableIterator[A] = new IteratorWrapper(underlying.iterator);
+  class IteratorWrapper(underlying : java.util.Iterator) extends MutableIterator[A] {
+    // val underlying = IterableWrapper.this.underlying.iterator;
+    def hasNext = underlying.hasNext;
+    def next = underlying.next.asInstanceOf[A];
+    def remove = underlying.remove;
+  }
+
+}
diff --git a/src/library/scala/collection/jcl/LinkedHashMap.scala b/src/library/scala/collection/jcl/LinkedHashMap.scala
new file mode 100644
index 0000000000..f2050d05e3
--- /dev/null
+++ b/src/library/scala/collection/jcl/LinkedHashMap.scala
@@ -0,0 +1,8 @@
+package scala.collection.jcl;
+
+/** A map that is backed by a Java linked hash map, which fixes iteration order in terms of insertion order.
+   * @author Sean McDirmid
+   */
+class LinkedHashMap[K,E](override val underlying : java.util.LinkedHashMap) extends ConcreteMapWrapper[K,E] {
+  def this() = this(new java.util.LinkedHashMap);
+}
diff --git a/src/library/scala/collection/jcl/LinkedHashSet.scala b/src/library/scala/collection/jcl/LinkedHashSet.scala
new file mode 100644
index 0000000000..d3c7485cb8
--- /dev/null
+++ b/src/library/scala/collection/jcl/LinkedHashSet.scala
@@ -0,0 +1,8 @@
+package scala.collection.jcl;
+
+/** A set that is backed by a Java linked hash set, which fixes iteration order in terms of insertion order.
+   * @author Sean McDirmid
+   */
+class LinkedHashSet[A](override val underlying : java.util.LinkedHashSet) extends ConcreteWrapper[A] with SetWrapper[A] {
+  def this() = this(new java.util.LinkedHashSet);
+}
diff --git a/src/library/scala/collection/jcl/LinkedList.scala b/src/library/scala/collection/jcl/LinkedList.scala
new file mode 100644
index 0000000000..d05e68746f
--- /dev/null
+++ b/src/library/scala/collection/jcl/LinkedList.scala
@@ -0,0 +1,17 @@
+package scala.collection.jcl;
+
+/** Creates a buffer backed by a Java linked list. Includes additional peek/poll/removeFirst/removeLast APIs
+  * that are useful in implementing queues and stacks.
+  * @author Sean McDirmid
+  */
+class LinkedList[A](override val underlying : java.util.LinkedList) extends ConcreteWrapper[A] with BufferWrapper[A]  {
+  def this() = this(new java.util.LinkedList);
+  override def elements = super[BufferWrapper].elements;
+  override def add(idx : Int, a : A) =
+    if (idx == 0) underlying.addFirst(a);
+    else super.add(idx, a);
+  def peek = underlying.peek.asInstanceOf[A];
+  def poll = underlying.poll.asInstanceOf[A];
+  def removeFirst = underlying.removeFirst.asInstanceOf[A];
+  def removeLast  = underlying.removeLast.asInstanceOf[A];
+}
diff --git a/src/library/scala/collection/jcl/Map.scala b/src/library/scala/collection/jcl/Map.scala
new file mode 100644
index 0000000000..a16ba82d53
--- /dev/null
+++ b/src/library/scala/collection/jcl/Map.scala
@@ -0,0 +1,85 @@
+package scala.collection.jcl;
+
+/** A mutable map that is compatible with Java maps.
+ * @author Sean McDirmid
+ */
+trait Map[K,E] extends MutableIterable[Tuple2[K,E]] with scala.collection.mutable.Map[K,E] {
+  override def clear = super[MutableIterable].clear;
+  override def isEmpty = super[MutableIterable].isEmpty;
+  override def keySet : Set[K] = new KeySet;
+  /** The values of this map as a projection, which means
+      removals from the returned collection will remove the element from this map.
+      @returns a projection of this map's elements.  */
+  def valueSet : MutableIterable[E] = pmap(._2);
+  def put(key : K, elem : E) : Option[E];
+  def putAll(that : Iterable[Tuple2[K,E]]) : Unit =
+    that.foreach(p => put(p._1, p._2));
+  def remove(key : K) : Option[E] = {
+    val i = elements;
+    while (!i.hasNext) {
+      val result = i.next;
+      if (result._1 == key) {
+        i.remove;
+        return Some(result._2);
+      }
+    }
+    return None;
+  }
+  override def has(pair : Tuple2[K,E]) = get(pair._1) match {
+  case Some(e) if e == pair._2 => true;
+  case _ => false;
+  }
+  override def get(key : K) = elements.find(p => p._1 == key).map(._2);
+  override def update(key : K, e : E) : Unit = put(key,e);
+  override def +(pair : Tuple2[K,E]) : this.type = {
+    put(pair._1,pair._2); this;
+  }
+  override def +=(pair : Tuple2[K,E]) : Unit = put(pair._1, pair._2);
+  override def -(key : K) : this.type = {
+    remove(key); this;
+  }
+  override def -=(key : K) : Unit = remove(key);
+  override def elements : MutableIterator[Tuple2[K,E]];
+  /** Produces a filtered projection of this map that includes only entries of the map
+   *  whose keys are true with respect to predicate "p."
+   */
+  def pfilter(p : K => Boolean) : jcl.Map[K,E] = new Filter(p);
+  /**
+   */
+  def lense[F](f : E => F, g : F => E) : jcl.Map[K,F] = new Lense[F](f,g);
+
+  protected class Lense[F](f : E => F, g : F => E) extends jcl.Map[K,F] {
+    override def elements = Map.this.elements.map(k => Tuple2(k._1, f(k._2)));
+    override def remove(key : K) = Map.this.remove(key).map(f);
+    override def put(key : K, elem : F) = Map.this.put(key, g(elem)).map(f);
+    override def get(key : K) = Map.this.get(key).map(f);
+    override def pfilter(p : K => Boolean) : jcl.Map[K,F] =
+      Map.this.pfilter(p).lense(f, g);
+    override def lense[G](f0 : F => G, g0 : G => F) : jcl.Map[K,G] =
+      Map.this.lense[G](x => f0(f(x)), y => g(g0(y)));
+  }
+  protected class Filter(p : K => Boolean) extends jcl.Map[K,E] {
+    override def elements = Map.this.elements.filter(k => p(k._1));
+    override def remove(key : K) = {
+      if (!p(key)) throw new IllegalArgumentException;
+      Map.this.remove(key);
+    }
+    override def contains(key : K) = p(key) && Map.this.contains(key);
+    override def put(key : K, elem : E) = {
+      if (!p(key)) throw new IllegalArgumentException;
+      Map.this.put(key, elem);
+    }
+    override def get(key : K) = {
+      if (!p(key)) None;
+      else Map.this.get(key);
+    }
+    override def pfilter(p0 : K => Boolean) : jcl.Map[K,E] =
+      Map.this.pfilter(k => p(k) && p0(k));
+  }
+  protected class KeySet extends Set[K] {
+    override def add(k : K) = Map.this.put(k, default(k)) == None;
+    override def elements = Map.this.elements.map(._1);
+    override def has(k : K) = Map.this.contains(k);
+  }
+
+}
diff --git a/src/library/scala/collection/jcl/MapWrapper.scala b/src/library/scala/collection/jcl/MapWrapper.scala
new file mode 100644
index 0000000000..5fb1a8d6b4
--- /dev/null
+++ b/src/library/scala/collection/jcl/MapWrapper.scala
@@ -0,0 +1,44 @@
+package scala.collection.jcl;
+
+/** A wrapper around a Java map.
+   * @author Sean McDirmid
+   */
+trait MapWrapper[K,E] extends jcl.Map[K,E] {
+  protected def underlying : java.util.Map;
+  override def size = underlying.size;
+  override def isEmpty = underlying.isEmpty;
+  override def clear = underlying.clear;
+  override def put(key : K, elem : E) = {
+    if (elem == null) throw new IllegalArgumentException;
+    val ret = underlying.put(key,elem);
+    if (ret == null) None else Some(ret.asInstanceOf[E]);
+  }
+  override def putAll(that : Iterable[Tuple2[K,E]]) : Unit = that match {
+  case that : MapWrapper[_,_] => underlying.putAll(that.underlying);
+  case _ => super.putAll(that);
+  }
+  override def remove(key : K) = {
+    val ret = underlying.remove(key);
+    if (ret == null) None else Some(ret.asInstanceOf[E]);
+  }
+  override def contains(key : K) = underlying.containsKey(key);
+  override def keySet : Set[K] = new KeySet;
+  override def valueSet : MutableIterable[E] = new ValueSet;
+  override def elements : MutableIterator[Tuple2[K,E]] = new IteratorWrapper;
+  class IteratorWrapper extends MutableIterator[Tuple2[K,E]] {
+    val underlying = MapWrapper.this.underlying.entrySet.iterator;
+    def hasNext = underlying.hasNext;
+    def remove = underlying.remove;
+    def next = {
+      val next = underlying.next.asInstanceOf[java.util.Map.Entry];
+      Tuple2(next.getKey.asInstanceOf[K],next.getValue.asInstanceOf[E]);
+    }
+  }
+  class KeySet extends super.KeySet with SetWrapper[K] {
+    protected val underlying = MapWrapper.this.underlying.keySet;
+  }
+  class ValueSet extends IterableWrapper[E] {
+    val underlying = MapWrapper.this.underlying.values;
+    override def has(e : E) = MapWrapper.this.underlying.containsValue(e);
+  }
+}
diff --git a/src/library/scala/collection/jcl/MutableIterable.scala b/src/library/scala/collection/jcl/MutableIterable.scala
new file mode 100644
index 0000000000..baf5a0c727
--- /dev/null
+++ b/src/library/scala/collection/jcl/MutableIterable.scala
@@ -0,0 +1,70 @@
+package scala.collection.jcl;
+
+/**
+ * An iterable collection that supports remove operations.
+ * Useful for representing projections of mutable collections that where only
+ * the remove operation makes sense.
+ *
+ * @author Sean McDirmid
+ */
+trait MutableIterable[A] extends Iterable[A] {
+  /** @return true if t is in the collection.
+   **/
+  def has(t : A ) : Boolean = elements.has(t);
+  /** @return true if t was removed from this collection.
+   **/
+  def remove(t : A ) : Boolean = elements.remove(t);
+  /** @return true if any element in that was removed from this collection.
+   **/
+  def removeAll(that : Iterable[A]) : Boolean = {
+    var changed = false;
+    that.foreach(t => changed = elements.remove(t) || changed);
+    changed;
+  }
+  /** Operator shortcut for removeAll. */
+  def --(that : Iterable[A]) : this.type = {
+    removeAll(that); this;
+  }
+
+  /** @return the collection that t was removed from.
+   **/
+  def -(t : A) : this.type = { remove(t); this; }
+  /** retain only elements in the collection that predicate p is true for.
+   **/
+  def retain(p : A => Boolean) : Unit = elements.retain(p);
+  /** retain only elements that are also in that.
+   **/
+  def retainAll(that : Iterable[A]) : Boolean = elements.retain(s => that.exists(t => t == s));
+  /** @return true if the element has no elements.
+   **/
+  def isEmpty : Boolean = !elements.hasNext;
+  /** @return the current number of elements in the collection.
+   **/
+  def size : Int = {
+    var count = 0;
+    val i = elements;
+    while (i.hasNext) { count = count + 1; i.next; }
+    count;
+  }
+  /** clear all elements from the collection.
+   **/
+  def clear : Unit = {
+    val i = elements;
+    while (i.hasNext) {
+      i.next; i.remove;
+    }
+  }
+  /** Creates a non-strict map of this collection. Any removals from the returned
+   ** collection will remove from this collection, while any changes to this collection will also be
+   ** reflected in the mapped collection.
+   ** @return a non-strict map of this collection.
+   **/
+  def pmap[B](f : A => B) : MutableIterable[B] = new Map[B](f);
+  /** The default implementation of a map over mutable iterable collections.
+   **/
+  protected class Map[B](f : A => B) extends MutableIterable[B] {
+    override def elements = MutableIterable.this.elements.map(f);
+    override def toString = elements.toList.mkString("{", ", ", "}");
+  }
+  override def elements : MutableIterator[A];
+}
diff --git a/src/library/scala/collection/jcl/MutableIterator.scala b/src/library/scala/collection/jcl/MutableIterator.scala
new file mode 100644
index 0000000000..4a4530c641
--- /dev/null
+++ b/src/library/scala/collection/jcl/MutableIterator.scala
@@ -0,0 +1,80 @@
+package scala.collection.jcl;
+
+/** An iterator that supports the remove operation.
+ ** These iterators wrap Java iterators, and so have the same fail fast behavior when dealing
+ ** with concurrent modifications.
+ **
+ ** @author Sean McDirmid
+ **/
+trait MutableIterator[A] extends Iterator[A] {
+  def remove : Unit;
+  override def filter(f : A => Boolean) : MutableIterator[A] = {
+    val buffered = this.buffered0;
+    new buffered.Filter(f);
+  }
+  override def map[B](f : A => B) : MutableIterator[B] = new Map(f);
+  /** A type-safe version of contains.
+   **/
+  def has(a : A) = exists(b => a == a);
+  /** Finds and removes the first instance of "a" through the iterator. After execution, the iterator's cursor is located where the removed element existed.
+   ** Returns false if "a" is not encountered in the iterator and the iterator's cursor is located at the end of its elements.
+   **/
+  def remove(a : A) : Boolean = {
+    while (hasNext)
+      if (next == a) { remove; return true; }
+    return false;
+  }
+  /** Removes all elements in the iterator that predicate "p" returns false on.
+   **/
+  def retain(p : A => Boolean) : Boolean = {
+    var changed = false;
+    while (hasNext)
+      if (!p(next)) { remove; changed = true; }
+    changed;
+  }
+
+  private[jcl] def buffered0 : MutableIterator[A]#Buffered = new BufferedImpl;
+
+  /** Standard implementation of a mapped iterator. **/
+  class Map[B](f : A => B) extends MutableIterator[B] {
+    def hasNext = MutableIterator.this.hasNext;
+    def next = f(MutableIterator.this.next);
+    def remove = MutableIterator.this.remove;
+  }
+  private[jcl] trait Buffered extends MutableIterator[A] {
+    private[jcl] override def buffered0 : this.type = this;
+    private[jcl] def peekNext : A;
+    private[jcl] def seekNext(f : A => Boolean) : Option[A] = {
+      while (hasNext && !f(peekNext)) next;
+      if (hasNext) Some(peekNext) else None;
+    }
+    class Filter(p : A => Boolean) extends MutableIterator[A] {
+      private[jcl] def peekNext = Buffered.this.seekNext(p) match {
+      case Some(result) => result;
+      case None => throw new NoSuchElementException;
+      }
+      override def next = {
+        val ret = peekNext; val ret0 = Buffered.this.next; assert(ret == ret0); ret;
+      }
+      override def hasNext : Boolean = seekNext(p) != None;
+      override def remove : Unit = Buffered.this.remove;
+    }
+  }
+  private[jcl] class BufferedImpl extends Buffered {
+    protected var head : A = _;
+    protected def underlying = MutableIterator.this;
+    private[jcl] def peekNext = {
+      if (head == null) head = underlying.next;
+      head;
+    }
+    override def hasNext = head != null || underlying.hasNext;
+    override def next = {
+      val ret = peekNext; head = null.asInstanceOf[A]; ret;
+    }
+    override def remove = {
+      if (head != null) throw new NoSuchElementException;
+      underlying.remove;
+    }
+    override def toString = "buffered[" + underlying + "]";
+  }
+}
diff --git a/src/library/scala/collection/jcl/MutableSeq.scala b/src/library/scala/collection/jcl/MutableSeq.scala
new file mode 100644
index 0000000000..f1ea9fc61b
--- /dev/null
+++ b/src/library/scala/collection/jcl/MutableSeq.scala
@@ -0,0 +1,66 @@
+package scala.collection.jcl;
+
+/** A mutable sequence that supports the remove operation and is ordered.
+ *
+ * @author Sean McDirmid
+ */
+trait MutableSeq[A] extends MutableIterable[A] with Seq[A] {
+  override def elements : SeqIterator[Int,A];
+  override def isEmpty = super[MutableIterable].isEmpty;
+  override def length = size;
+  override def apply(idx : Int) = elements.seek(idx);
+  def pfilter(p : A => Boolean) : MutableSeq[A] = new Filter(p);
+  override def pmap[B](f : A => B) : MutableSeq[B] = new Map[B](f);
+  /** Find the index of "a" in this sequence.
+   *  @returns None if the "a" is not in this sequence.
+   */
+  def indexOf(a : A) = elements.indexOf(a);
+
+
+  protected class Filter(p : A => Boolean) extends MutableSeq[A] {
+    def elements : SeqIterator[Int,A] = new FilterIterator(MutableSeq.this.elements);
+    class FilterIterator(underlying : SeqIterator[Int,A]) extends SeqIterator[Int,A] {
+      private var index = 0;
+      protected def seekNext : Option[A] = {
+        while (underlying.hasNext) {
+          val next = underlying.next;
+          if (p(next)) return Some(next);
+        }
+        return None;
+      }
+      protected def seekPrevious : Option[A] = {
+        while (underlying.hasPrevious) {
+          val previous = underlying.previous;
+          if (p(previous)) return Some(previous);
+        }
+        return None;
+      }
+      def hasNext : Boolean = seekNext match {
+      case None => false;
+      case Some(_) => underlying.previous; true;
+      }
+      def nextIndex = index;
+      def next = seekNext match {
+      case None => throw new NoSuchElementException;
+      case Some(result) => index = index + 1; result;
+      }
+      def hasPrevious : Boolean = seekPrevious match {
+      case None => false;
+      case Some(_) => underlying.previous; true;
+      }
+      def previousIndex = {
+        if (index == 0) throw new NoSuchElementException;
+        index - 1;
+      }
+      def previous = seekPrevious match {
+      case None => throw new NoSuchElementException;
+      case Some(result) => index = index - 1; result;
+      }
+      def remove = underlying.remove;
+    }
+  }
+  protected class Map[B](f : A => B) extends super.Map[B](f) with MutableSeq[B] {
+    override def elements = MutableSeq.this.elements.map(f);
+    override def apply(idx : Int) = f(MutableSeq.this.apply(idx));
+  }
+}
diff --git a/src/library/scala/collection/jcl/SeqIterator.scala b/src/library/scala/collection/jcl/SeqIterator.scala
new file mode 100644
index 0000000000..584f2dfb79
--- /dev/null
+++ b/src/library/scala/collection/jcl/SeqIterator.scala
@@ -0,0 +1,41 @@
+package scala.collection.jcl;
+
+/** An iterator for a sequence that can move both forwards and backwards.
+  * over a set of ordered keys.
+  * @author Sean McDirmid
+  */
+trait SeqIterator[K,A] extends MutableIterator[A] {
+  /** @returns The index at the iterator's cursor. */
+  def nextIndex : K;
+  /** @returns The index of the element before the iterator's cursor. */
+  def previousIndex : K;
+  /** @returns The previous element, will move the iterator's cursor backwards. */
+  def previous : A;
+  /** @returns True if and only if the iterator's cursor is not at the beging of the iteration. */
+  def hasPrevious : Boolean;
+
+  /** Winds the iteration forward until index "idx" is found */
+  def seek(idx : K) = {
+    while (nextIndex != idx) next;
+    next;
+  }
+  /** finds the index of the next "a" in this iteration.
+      @returns None if "a" is not found in the iteration. */
+  def indexOf(a : A) : Option[K] = {
+    while (hasNext) {
+      val ret = next;
+      if (ret == a) return Some(previousIndex);
+    }
+    return None;
+  }
+
+  override def map[B](f : A => B) : SeqIterator[K,B] = new Map[B](f);
+  class Map[B](f : A => B) extends super.Map[B](f) with SeqIterator[K,B] {
+    override def hasPrevious = SeqIterator.this.hasPrevious;
+    override def previous = f(SeqIterator.this.previous);
+    override def previousIndex = SeqIterator.this.previousIndex;
+    override def nextIndex = SeqIterator.this.nextIndex;
+    override def map[C](g : B => C) : SeqIterator[K,C] =
+      SeqIterator.this.map(a => g(f(a)));
+  }
+}
diff --git a/src/library/scala/collection/jcl/Set.scala b/src/library/scala/collection/jcl/Set.scala
new file mode 100644
index 0000000000..68a92a7e6e
--- /dev/null
+++ b/src/library/scala/collection/jcl/Set.scala
@@ -0,0 +1,34 @@
+package scala.collection.jcl;
+
+/** Analogous to a Java set.
+ **
+ ** @author Sean McDirmid
+ **/
+trait Set[A] extends Collection[A] with scala.collection.mutable.Set[A] {
+  /** Add will return false if "a" already exists in the set. **/
+  override def add(a : A) : Boolean;
+
+  override def ++(i : Iterable[A]) : this.type = super[Collection].++(i);
+  override def --(i : Iterable[A]) : this.type = super[Collection].--(i);
+  override def +(t : A) : this.type = super[Collection].+(t);
+  override def -(t : A) : this.type = super[Collection].-(t);
+  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 transform(f : A => A) = {
+    var toAdd : List[A] = Nil;
+    val i = elements;
+    while (i.hasNext) {
+      val i0 = i.next;
+      val i1 = f(i0);
+      if (i0 != i1) {
+        i.remove; toAdd = i1 :: toAdd;
+      }
+    }
+    addAll(toAdd);
+  }
+  override def pfilter(p : A => Boolean) : Set[A] = new Filter(p);
+  class Filter(p : A => Boolean) extends super.Filter(p) with Set[A] {
+    override def filter(p : A => Boolean) = super[Set].filter(p);
+  }
+}
diff --git a/src/library/scala/collection/jcl/SetWrapper.scala b/src/library/scala/collection/jcl/SetWrapper.scala
new file mode 100644
index 0000000000..54d19e6675
--- /dev/null
+++ b/src/library/scala/collection/jcl/SetWrapper.scala
@@ -0,0 +1,10 @@
+package scala.collection.jcl;
+
+/** Used to wrap Java sets.
+ **
+ ** @author Sean McDirmid
+ **/
+trait SetWrapper[A] extends CollectionWrapper[A] with Set[A] {
+  protected def underlying : java.util.Set;
+  override def isEmpty = super[Set].isEmpty;
+}
diff --git a/src/library/scala/collection/jcl/Sorted.scala b/src/library/scala/collection/jcl/Sorted.scala
new file mode 100644
index 0000000000..5381720141
--- /dev/null
+++ b/src/library/scala/collection/jcl/Sorted.scala
@@ -0,0 +1,43 @@
+package scala.collection.jcl;
+
+/** Any collection (including maps) whose keys (or elements) are ordered.
+ **
+ ** @author Sean McDirmid
+ **/
+trait Sorted[K,A] extends MutableIterable[A] {
+  protected type SortedSelf <: Sorted[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.
+   ** @param from The lower-bound (inclusive) of the ranged projection. None if there is no lower bound.
+   ** @param until The upper-bound (exclusive) of the ranged projection. None if there is no upper bound.
+   **/
+  def rangeImpl(from : Option[K], until : Option[K]) : SortedSelf;
+  /** 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);
+  /** Creates a ranged projection of this collection with no lower-bound.
+   ** @param from The upper-bound (exclusive) of the ranged projection.
+   **/
+  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));
+
+  /** A wrapper around Java comparators. */
+  protected class Comparator[K <% Ordered[K]] extends java.util.Comparator {
+    def compare(x0 : Any, x1 : Any) = {
+      val k0 = x0.asInstanceOf[K];
+      val k1 = x1.asInstanceOf[K];
+      k0.compare(k1);
+    }
+  }
+}
diff --git a/src/library/scala/collection/jcl/SortedMap.scala b/src/library/scala/collection/jcl/SortedMap.scala
new file mode 100644
index 0000000000..968a9887e3
--- /dev/null
+++ b/src/library/scala/collection/jcl/SortedMap.scala
@@ -0,0 +1,78 @@
+package scala.collection.jcl;
+
+/** A map whose keys are sorted.
+  *  @author Sean McDirmid
+  */
+trait SortedMap[K,E] extends 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;
+  override def last : K = {
+    val i = elements;
+    var last : K = i.next._1;
+    while (i.hasNext) last = i.next._1;
+    last;
+  }
+  override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap[K,E] = Range(from, until);
+  override def keySet : SortedSet[K] = new KeySet;
+  override def pfilter(p : K => Boolean) : SortedMap[K,E] = new Filter(p);
+  override def lense[F](f : E => F, g : F => E) : jcl.SortedMap[K,F] = new Lense[F](f,g);
+
+  protected class Lense[F](f : E => F, g : F => E) extends super.Lense[F](f,g) with SortedMap[K,F] {
+    def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0, k1);
+    override def pfilter(p : K => Boolean) : jcl.SortedMap[K,F] =
+      SortedMap.this.pfilter(p).lense(f, g);
+    override def lense[G](f0 : F => G, g0 : G => F) : jcl.SortedMap[K,G] =
+      SortedMap.this.lense[G]({x:E => f0(f(x))}, {y:G => g(g0(y))});
+    override def rangeImpl(from : Option[K], until : Option[K]) =
+      SortedMap.this.rangeImpl(from,until).lense(f,g);
+  }
+  protected class KeySet extends super.KeySet with SortedSet[K] {
+    def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0,k1);
+    override def first = SortedMap.this.first;
+    override def last = SortedMap.this.last;
+    override def rangeImpl(from : Option[K], until : Option[K]) =
+      SortedMap.this.rangeImpl(from,until).keySet;
+  }
+  protected class SuperFilter(p : K => Boolean) extends super.Filter(p);
+  protected class Filter(p : K => Boolean) extends SuperFilter(p) with SortedMap[K,E] {
+    def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0,k1);
+    override def pfilter(p0 : K => Boolean) : SortedMap[K,E] =
+      SortedMap.this.pfilter(k => p(k) && p0(k));
+
+    override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap[K,E] =
+      SortedMap.this.Range(from, until).pfilter(p);
+  }
+  protected def Range(from : Option[K], until : Option[K]) : SortedMap[K,E] = new Range(from,until);
+  protected class Range(from : Option[K], until : Option[K]) extends SuperFilter(key => {
+    ((from == None || (compare(from.get,key) <= 0)) &&
+      (until == None || (compare(key,until.get) < 0)));
+  }) with SortedMap[K,E] {
+    def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0,k1);
+    private def contains0(key : K) =
+      (from == None || (compare(from.get,key) <= 0)) &&
+        (until == None || (compare(key,until.get) < 0));
+
+    override def contains(key : K) = SortedMap.this.contains(key) && contains0(key);
+    override def get(key : K) = if (!contains0(key)) None else SortedMap.this.get(key);
+    override def put(key : K, elem : E) = {
+      if (!contains0(key)) throw new IllegalArgumentException;
+      SortedMap.this.put(key, elem);
+    }
+    override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap[K,E] = {
+      if (this.from != None && from == None) return rangeImpl(this.from, until);
+      if (this.until != None && until == None) return rangeImpl(from, this.until);
+      if (from != None && compare(this.from.get, from.get) > 0) return rangeImpl(this.from, until);
+      if (until != None && compare(this.until.get, until.get) < 0) return rangeImpl(from, this.until);
+      SortedMap.this.Range(from, until);
+    }
+    override def pfilter(p : K => Boolean) : SortedMap[K,E] = new Filter(p);
+    protected class Filter(p : K => Boolean) extends SuperFilter(p) with SortedMap[K,E] {
+      def compare(k0 : K, k1 : K) = Range.this.compare(k0, k1);
+      override def pfilter(p0 : K => Boolean) =
+        Range.this.pfilter(key => p(key) && p0(key));
+      override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap[K,E] =
+        Range.this.rangeImpl(from,until).pfilter(p);
+    }
+  }
+}
diff --git a/src/library/scala/collection/jcl/SortedMapWrapper.scala b/src/library/scala/collection/jcl/SortedMapWrapper.scala
new file mode 100644
index 0000000000..c96aba9ff9
--- /dev/null
+++ b/src/library/scala/collection/jcl/SortedMapWrapper.scala
@@ -0,0 +1,28 @@
+package scala.collection.jcl;
+
+/** A sorted map that wraps an underlying Java sorted map.
+   *  @author Sean McDirmid
+   */
+trait SortedMapWrapper[K,E] extends MapWrapper[K,E] with SortedMap[K,E] {
+  protected override def underlying : java.util.SortedMap;
+  /** the comparator function of this sorted map is defined in terms
+    * of the underlying sorted map's comparator.
+    */
+  def compare(k0 : K, k1 : K) = underlying.comparator.compare(k0,k1);
+  override def first = underlying.firstKey.asInstanceOf[K];
+  override def last = underlying.lastKey.asInstanceOf[K];
+  override def keySet : SortedSet[K] = new KeySet;
+  override protected def Range(from : Option[K], until : Option[K]) = new Range(from,until);
+  protected class Range(from : Option[K], until : Option[K]) extends super.Range(from,until) with SortedMapWrapper[K,E] {
+    val underlying = Tuple2(from,until) match {
+    case Tuple2(None,None) => throw new IllegalArgumentException;
+    case Tuple2(Some(from),None) => SortedMapWrapper.this.underlying.tailMap(from);
+    case Tuple2(None,Some(until)) => SortedMapWrapper.this.underlying.headMap(until);
+    case Tuple2(Some(from),Some(until)) => SortedMapWrapper.this.underlying.subMap(from,until);
+    }
+    override def compare(k0 : K, k1 : K) = super[SortedMapWrapper].compare(k0, k1);
+  }
+  protected class KeySet extends super[SortedMap].KeySet with SetWrapper[K] {
+    protected val underlying = SortedMapWrapper.this.underlying.keySet;
+  }
+}
diff --git a/src/library/scala/collection/jcl/SortedSet.scala b/src/library/scala/collection/jcl/SortedSet.scala
new file mode 100644
index 0000000000..c5d5242e21
--- /dev/null
+++ b/src/library/scala/collection/jcl/SortedSet.scala
@@ -0,0 +1,62 @@
+package scala.collection.jcl;
+/** Analogous to a Java sorted set.
+ *  @author Sean McDirmid
+ */
+trait SortedSet[A] extends jcl.Set[A] with Sorted[A,A] {
+  final protected type SortedSelf = SortedSet[A];
+  def compare(a0 : A, a1 : A) : Int;
+  def first : A = {
+    val i = elements;
+    if (i.hasNext) i.next;
+    else throw new NoSuchElementException;
+  }
+  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] = new Range(from, until);
+  override def pfilter(p : A => Boolean) : SortedSet[A] = new Filter(p);
+  protected class Filter(p : A => Boolean) extends super.Filter(p) with SortedSet[A] {
+    def compare(a0 : A, a1 : A) : Int = SortedSet.this.compare(a0, a1);
+  }
+
+  protected class Range(from : Option[A], until : Option[A]) extends Filter(key => {
+    (from == None || (compare(from.get,key) <= 0)) &&
+      (until == None || (compare(key,until.get) < 0));
+  }) with SortedSet[A] {
+    if (from == None && until == None) throw new IllegalArgumentException;
+    if (from != None && until != None && !(SortedSet.this.compare(from.get, until.get) < 0))
+      throw new IllegalArgumentException;
+    override def elements : MutableIterator[A] =
+      new RangeIterator(SortedSet.this.elements.buffered0);
+    private def contains1(key : A) =
+      (from == None || (compare(from.get,key) <= 0)) &&
+        (until == None || (compare(key,until.get) < 0));
+    override def has(elem : A) = contains1(elem) && SortedSet.this.has(elem);
+    override def rangeImpl(from : Option[A], until : Option[A]) : SortedSet[A] = {
+      if (this.from != None && from == None) return rangeImpl(this.from, until);
+      if (this.until != None && until == None) return rangeImpl(from, this.until);
+      if (from != None && compare(this.from.get, from.get) > 0) return rangeImpl(this.from, until);
+      if (until != None && compare(this.until.get, until.get) < 0) return rangeImpl(from, this.until);
+      SortedSet.this.rangeImpl(from, until);
+    }
+    class RangeIterator(underlying : MutableIterator[A]#Buffered) extends MutableIterator[A] {
+      if (from != None)
+        underlying.seekNext(a => compare(from.get, a) <= 0);
+
+      private def okNext(a : A) =
+        if (until == None) true;
+        else compare(a, until.get) < 0;
+
+      def hasNext = underlying.hasNext && okNext(underlying.peekNext);
+      def next = underlying.seekNext(okNext) match {
+      case Some(result) => underlying.next; result;
+      case None => throw new NoSuchElementException;
+      }
+      def remove = underlying.remove;
+    }
+  }
+}
diff --git a/src/library/scala/collection/jcl/SortedSetWrapper.scala b/src/library/scala/collection/jcl/SortedSetWrapper.scala
new file mode 100644
index 0000000000..e087af93b8
--- /dev/null
+++ b/src/library/scala/collection/jcl/SortedSetWrapper.scala
@@ -0,0 +1,23 @@
+package scala.collection.jcl;
+
+/** A wrapper around a Java sorted set.
+ ** The comparator of the sorted set matches the comparator of this set.
+    @author Sean McDirmid
+  */
+trait SortedSetWrapper[A] extends SortedSet[A] with SetWrapper[A] {
+  protected def underlying : java.util.SortedSet;
+  /** delegates to the comparator of the underlying Java sorted set */
+  override def compare(a0 : A, a1 : A) = underlying.comparator.compare(a0, a1);
+  override def first = underlying.first.asInstanceOf[A];
+  override def last  = underlying.last .asInstanceOf[A];
+  override def rangeImpl(from : Option[A], until : Option[A]) : SortedSet[A] = new Range(from,until);
+  protected class Range(from : Option[A], until : Option[A]) extends super.Range(from, until) with SortedSetWrapper[A] {
+    val underlying = Tuple2(from,until) match {
+    case Tuple2(None,Some(until)) => SortedSetWrapper.this.underlying.headSet(until);
+    case Tuple2(Some(from),None)  => SortedSetWrapper.this.underlying.tailSet(from);
+    case Tuple2(Some(from),Some(until)) => SortedSetWrapper.this.underlying.subSet(from,until);
+    case _ => throw new IllegalArgumentException;
+    }
+    override def elements : MutableIterator[A] = super[SortedSetWrapper].elements;
+  }
+}
diff --git a/src/library/scala/collection/jcl/Tests.scala b/src/library/scala/collection/jcl/Tests.scala
new file mode 100644
index 0000000000..91f9d34943
--- /dev/null
+++ b/src/library/scala/collection/jcl/Tests.scala
@@ -0,0 +1,66 @@
+package scala.collection.jcl;
+
+private[jcl] object Tests {
+  def main(args : Array[String]) : Unit = {
+    hashSet;
+    treeSet;
+    treeMap;
+  }
+  def treeSet : Unit = {
+    val set = new TreeSet[String];
+    set + "aaa" + "bbb" + "ccc" + "ddd" + "eee" + "fff";
+    Console.println(set);
+    val rset : SortedSet[String] = set.range("b", "e");
+    Console.println(rset);
+    rset + "bad";
+    Console.println(rset);
+    Console.println(set);
+    val fset : SortedSet[String] = rset.pfilter(.endsWith("d"));
+    Console.println(fset);
+    fset += "cd";
+    Console.println(set);
+    set.pmap(.length).retain(x => x == 3);
+    Console.println(set);
+    Console.println(rset);
+    Console.println(fset);
+  }
+  def treeMap : Unit = {
+    val map = new TreeMap[String,Integer];
+    map + ("bb" -> 3) + ("cc" -> 4) + ("aa" -> 2) + ("dd" -> 5);
+    //Console.println(map);
+    val rmap : SortedMap[String,Integer] = map.range("b", "d");
+    rmap + ("bad" -> 10);
+    Console.println(rmap);
+    //Console.println(map);
+    val fmap : SortedMap[String,Integer] = rmap.pfilter(k => k.length == 2);
+    Console.println(fmap);
+
+  }
+
+
+  def hashSet = {
+    val set = new HashSet[String];
+    set + "hello" + "world" + "you" + "to";
+    Console.println(set);
+    val fset = set.pfilter(s => s.length <= 3);
+    Console.println(fset);
+    fset += "xxx";
+    Console.println(set);
+    try {
+      fset += "xxxx";
+      throw new Error;
+    } catch {
+      case e : IllegalArgumentException =>
+      case _ => throw new Error;
+    }
+    val mset : MutableIterable[Int] = set.pmap(s => s.length);
+    Console.println(mset);
+    mset.retain(n => n < 5);
+    Console.println(set);
+    val set1 = new HashSet[String] + "1" + "2" + "3";
+    set ++ (set1);
+    Console.println(set);
+    set.transform(s => "x_" + s);
+    Console.println(set);
+  }
+}
diff --git a/src/library/scala/collection/jcl/TreeMap.scala b/src/library/scala/collection/jcl/TreeMap.scala
new file mode 100644
index 0000000000..06cb3fd341
--- /dev/null
+++ b/src/library/scala/collection/jcl/TreeMap.scala
@@ -0,0 +1,8 @@
+package scala.collection.jcl;
+
+/** A sorted map that is backed by a Java tree map.
+  * @author Sean McDirmid
+  */
+class TreeMap[K <% Ordered[K],E] extends ConcreteMapWrapper[K,E] with SortedMapWrapper[K,E] {
+  val underlying = (new java.util.TreeMap(new Comparator[K]));
+}
diff --git a/src/library/scala/collection/jcl/TreeSet.scala b/src/library/scala/collection/jcl/TreeSet.scala
new file mode 100644
index 0000000000..01cfe5036e
--- /dev/null
+++ b/src/library/scala/collection/jcl/TreeSet.scala
@@ -0,0 +1,10 @@
+package scala.collection.jcl;
+
+/** Creates a sorted set that is backed by an underlying Java tree set. Elements
+  * of the sorted set are ordered with respect to the ordered view bound of A.
+  *
+  * @author Sean McDirmid
+  */
+class TreeSet[A <% Ordered[A]] extends ConcreteWrapper[A] with SortedSetWrapper[A] {
+  val underlying = new java.util.TreeSet(new Comparator[A]);
+}
diff --git a/src/library/scala/collection/jcl/WeakHashMap.scala b/src/library/scala/collection/jcl/WeakHashMap.scala
new file mode 100644
index 0000000000..726ad7407e
--- /dev/null
+++ b/src/library/scala/collection/jcl/WeakHashMap.scala
@@ -0,0 +1,11 @@
+package scala.collection.jcl;
+
+/** A map that is backed by a Java weak hash map, whose keys are maintained as weak references.
+ *  Because keys are weak references, the garbage collector can collect them if they are not referred to elsewhere.
+ *  Useful for implementing caches.
+ *
+ *  @author Sean McDirmid
+ */
+class WeakHashMap[K,E](override val underlying : java.util.WeakHashMap) extends ConcreteMapWrapper[K,E] {
+  def this() = this(new java.util.WeakHashMap);
+}