Added David's additional collections.

4 files changed, 1145 insertions, 0 deletions

diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala
new file mode 100644
index 0000000000..71b10610a3
--- /dev/null
+++ b/src/library/scala/collection/immutable/IntMap.scala
@@ -0,0 +1,360 @@
+package scala.collection.immutable;
+
+private[immutable] object IntMapUtils{
+  def zero(i : Int, mask : Int) = (i & mask) == 0;
+  def mask(i : Int, mask : Int) = i & (complement(mask - 1) ^ mask)
+  def hasMatch(key : Int, prefix : Int, m : Int) = mask(key, m) == prefix;
+  def unsignedCompare(i : Int, j : Int) = (i < j) ^ (i < 0) ^ (j < 0)
+  def shorter(m1 : Int, m2 : Int) = unsignedCompare(m2, m1)
+  def complement(i : Int) = (-1) ^ i;
+  def branchMask(i : Int, j : Int) = java.lang.Integer.highestOneBit(i ^ j);
+
+  def join[T](p1 : Int, t1 : IntMap[T], p2 : Int, t2 : IntMap[T]) : IntMap[T] = {
+    val m = branchMask(p1, p2);
+    val p = mask(p1, m);
+    if (zero(p1, m)) IntMap.Bin(p, m, t1, t2)
+    else IntMap.Bin(p, m, t2, t1);
+  }
+
+  def bin[T](prefix : Int, mask : Int, left : IntMap[T], right : IntMap[T]) : IntMap[T] = (left, right) match {
+    case (left, IntMap.Nil) => left;
+    case (IntMap.Nil, right) => right;
+    case (left, right) => IntMap.Bin(prefix, mask, left, right);
+  }
+}
+
+import IntMapUtils._
+
+object IntMap{
+  def empty[T] : IntMap[T]  = IntMap.Nil;
+  def singleton[T](key : Int, value : T) : IntMap[T] = IntMap.Tip(key, value);
+  def apply[T](elems : (Int, T)*) : IntMap[T] =
+    elems.foldLeft(empty[T])((x, y) => x.update(y._1, y._2));
+
+
+  private[immutable] case object Nil extends IntMap[Nothing]{
+    override def equals(that : Any) = this eq that.asInstanceOf[AnyRef]
+  };
+  private[immutable] case class Tip[+T](key : Int, value : T) extends IntMap[T]{
+    def withValue[S](s : S) =
+      if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap.Tip[S]];
+      else IntMap.Tip(key, s);
+  }
+  private[immutable] case class Bin[+T](prefix : Int, mask : Int, left : IntMap[T], right : IntMap[T]) extends IntMap[T]{
+    def bin[S](left : IntMap[S], right : IntMap[S]) : IntMap[S] = {
+      if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[IntMap.Bin[S]];
+      else IntMap.Bin[S](prefix, mask, left, right);
+    }
+  }
+
+}
+
+import IntMap._
+
+// Iterator over a non-empty IntMap.
+private[immutable] abstract class IntMapIterator[V, T](it : IntMap[V]) extends Iterator[T]{
+
+  // Basically this uses a simple stack to emulate conversion over the tree. However
+  // because we know that Ints are at least 32 bits we can have at most 32 IntMap.Bins and
+  // one IntMap.Tip sitting on the tree at any point. Therefore we know the maximum stack
+  // depth is 33 and
+  var index = 0;
+  var buffer = new Array[AnyRef](33);
+
+  def pop = {
+    index -= 1;
+    buffer(index).asInstanceOf[IntMap[V]];
+  }
+
+  def push(x : IntMap[V]) {
+    buffer(index) = x.asInstanceOf[AnyRef];
+    index += 1;
+  }
+  push(it);
+
+  /**
+   * What value do we assign to a tip?
+   */
+  def valueOf(tip : IntMap.Tip[V]) : T;
+
+  def hasNext = index != 0;
+  final def next : T =
+    pop match {
+      case IntMap.Bin(_,_, t@IntMap.Tip(_, _), right) => {
+        push(right);
+        valueOf(t);
+      }
+      case IntMap.Bin(_, _, left, right) => {
+        push(right);
+        push(left);
+        next;
+      }
+      case t@IntMap.Tip(_, _) => valueOf(t);
+      // This should never happen. We don't allow IntMap.Nil in subtrees of the IntMap
+      // and don't return an IntMapIterator for IntMap.Nil.
+      case IntMap.Nil => error("Empty maps not allowed as subtrees");
+    }
+}
+
+private[immutable] class IntMapEntryIterator[V](it : IntMap[V]) extends IntMapIterator[V, (Int, V)](it){
+  def valueOf(tip : IntMap.Tip[V]) = (tip.key, tip.value);
+}
+
+private[immutable] class IntMapValueIterator[V](it : IntMap[V]) extends IntMapIterator[V, V](it){
+  def valueOf(tip : IntMap.Tip[V]) = tip.value;
+}
+
+private[immutable] class IntMapKeyIterator[V](it : IntMap[V]) extends IntMapIterator[V, Int](it){
+  def valueOf(tip : IntMap.Tip[V]) = tip.key;
+}
+
+import IntMap._;
+
+/**
+ * Specialised immutable map structure for integer keys, based on
+ * <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Integer Maps</a>
+ * by Okasaki and Gill. Essentially a trie based on binary digits of the the integers.
+ */
+sealed abstract class IntMap[+T] extends scala.collection.immutable.Map[Int, T]{
+  def empty[S] : IntMap[S] = IntMap.Nil;
+
+  override def toList = {
+    val buffer = new scala.collection.mutable.ListBuffer[(Int, T)];
+    foreach(buffer += _);
+    buffer.toList;
+  }
+
+  /**
+   * Iterator over key, value pairs of the map in unsigned order of the keys.
+   */
+  def elements : Iterator[(Int, T)] = this match {
+    case IntMap.Nil => Iterator.empty;
+    case _ => new IntMapEntryIterator(this);
+  }
+
+  /**
+   * Loops over the key, value pairs of the map in unsigned order of the keys.
+   */
+  override final def foreach(f : ((Int, T)) => Unit) : Unit = this match {
+    case IntMap.Bin(_, _, left, right) => {left.foreach(f); right.foreach(f); }
+    case IntMap.Tip(key, value) => f((key, value));
+    case IntMap.Nil => {};
+  }
+
+  override def keys : Iterator[Int] = this match {
+    case IntMap.Nil => Iterator.empty;
+    case _ => new IntMapKeyIterator(this);
+  }
+
+  /**
+   * Loop over the keys of the map. The same as keys.foreach(f), but may
+   * be more efficient.
+   *
+   * @param f The loop body
+   */
+  final def foreachKey(f : Int => Unit) : Unit = this match {
+    case IntMap.Bin(_, _, left, right) => {left.foreachKey(f); right.foreachKey(f); }
+    case IntMap.Tip(key, _) => f(key);
+    case IntMap.Nil => {}
+  }
+
+  override def values : Iterator[T] = this match {
+    case IntMap.Nil => Iterator.empty;
+    case _ => new IntMapValueIterator(this);
+  }
+
+  /**
+   * Loop over the keys of the map. The same as keys.foreach(f), but may
+   * be more efficient.
+   *
+   * @param f The loop body
+   */
+  final def foreachValue(f : T => Unit) : Unit = this match {
+    case IntMap.Bin(_, _, left, right) => {left.foreachValue(f); right.foreachValue(f); }
+    case IntMap.Tip(_, value) => f(value);
+    case IntMap.Nil => {};
+  }
+
+  override def stringPrefix = "IntMap"
+
+  override def isEmpty = this == IntMap.Nil;
+
+  override def filter(f : ((Int, T)) => Boolean) : IntMap[T] = this match {
+    case IntMap.Bin(prefix, mask, left, right) => {
+      val (newleft, newright) = (left.filter(f), right.filter(f));
+      if ((left eq newleft) && (right eq newright)) this;
+      else bin(prefix, mask, newleft, newright);
+    }
+    case IntMap.Tip(key, value) =>
+      if (f((key, value))) this
+      else IntMap.Nil;
+    case IntMap.Nil => IntMap.Nil;
+  }
+
+  override def transform[S](f : (Int, T) => S) : IntMap[S] = this match {
+    case b@IntMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f));
+    case t@IntMap.Tip(key, value) => t.withValue(f(key, value));
+    case IntMap.Nil => IntMap.Nil;
+  }
+
+  final def size : Int = this match {
+    case IntMap.Nil => 0;
+    case IntMap.Tip(_, _) => 1;
+    case IntMap.Bin(_, _, left, right) => left.size + right.size;
+  }
+
+  final def get(key : Int) : Option[T] = this match {
+    case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key);
+    case IntMap.Tip(key2, value) => if (key == key2) Some(value) else None;
+    case IntMap.Nil => None;
+  }
+
+  final override def getOrElse[S >: T](key : Int, default : =>S) : S = this match {
+    case IntMap.Nil => default;
+    case IntMap.Tip(key2, value) => if (key == key2) value else default;
+    case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key);
+  }
+
+  final override def apply(key : Int) : T = this match {
+    case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key);
+    case IntMap.Tip(key2, value) => if (key == key2) value else error("Key not found");
+    case IntMap.Nil => error("key not found");
+  }
+
+  def update[S >: T](key : Int, value : S) : IntMap[S] = this match {
+    case IntMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this);
+                                          else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.update(key, value), right)
+                                          else IntMap.Bin(prefix, mask, left, right.update(key, value));
+    case IntMap.Tip(key2, value2) => if (key == key2) IntMap.Tip(key, value);
+                             else join(key, IntMap.Tip(key, value), key2, this);
+    case IntMap.Nil => IntMap.Tip(key, value);
+  }
+
+  /**
+   * Updates the map, using the provided function to resolve conflicts if the key is already present.
+   * Equivalent to
+   * <pre>this.get(key) match {
+   *         case None => this.update(key, value);
+   *         case Some(oldvalue) => this.update(key, f(oldvalue, value) }
+   * </pre>
+   *
+   * @param key The key to update
+   * @param value The value to use if there is no conflict
+   * @param f The function used to resolve conflicts.
+   */
+  def updateWith[S >: T](key : Int, value : S, f : (T, S) => S) : IntMap[S] = this match {
+    case IntMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this);
+                                          else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updateWith(key, value, f), right)
+                                          else IntMap.Bin(prefix, mask, left, right.updateWith(key, value, f));
+    case IntMap.Tip(key2, value2) => if (key == key2) IntMap.Tip(key, f(value2, value));
+                             else join(key, IntMap.Tip(key, value), key2, this);
+    case IntMap.Nil => IntMap.Tip(key, value);
+  }
+
+  def -(key : Int) : IntMap[T] = this match {
+    case IntMap.Bin(prefix, mask, left, right) =>
+      if (!hasMatch(key, prefix, mask)) this;
+      else if (zero(key, mask)) bin(prefix, mask, left - key, right);
+      else bin(prefix, mask, left, right - key);
+    case IntMap.Tip(key2, _) =>
+      if (key == key2) IntMap.Nil;
+      else this;
+    case IntMap.Nil => IntMap.Nil;
+  }
+
+  /**
+   * A combined transform and filter function. Returns an IntMap such that for each (key, value) mapping
+   * in this map, if f(key, value) == None the map contains no mapping for key, and if <code>f(key, value)
+   *
+   * @param f The transforming function.
+   */
+  def modifyOrRemove[S](f : (Int, T) => Option[S]) : IntMap[S] = this match {
+      case IntMap.Bin(prefix, mask, left, right) => {
+        val newleft = left.modifyOrRemove(f);
+        val newright = right.modifyOrRemove(f);
+        if ((left eq newleft) && (right eq newright)) this.asInstanceOf[IntMap[S]];
+        else bin(prefix, mask, newleft, newright)
+      }
+    case IntMap.Tip(key, value) => f(key, value) match {
+      case None => IntMap.Nil;
+      case Some(value2) =>
+        //hack to preserve sharing
+        if (value.asInstanceOf[AnyRef] eq value2.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap[S]]
+        else IntMap.Tip(key, value2);
+      }
+    case IntMap.Nil => IntMap.Nil;
+  }
+
+
+  /**
+   * Forms a union map with that map, using the combining function to resolve conflicts.
+   *
+   * @param that the map to form a union with.
+   * @param f the function used to resolve conflicts between two mappings.
+   */
+  def unionWith[S >: T](that : IntMap[S], f : (Int, S, S) => S) : IntMap[S] = (this, that) match{
+    case (IntMap.Bin(p1, m1, l1, r1), that@(IntMap.Bin(p2, m2, l2, r2))) =>
+      if (shorter(m1, m2)) {
+        if (!hasMatch(p2, p1, m1)) join(p1, this, p2, that);
+        else if (zero(p2, m1)) IntMap.Bin(p1, m1, l1.unionWith(that, f), r1);
+        else IntMap.Bin(p1, m1, l1, r1.unionWith(that, f));
+      } else if (shorter(m2, m1)){
+        if (!hasMatch(p1, p2, m2)) join(p1, this, p2, that);
+        else if (zero(p1, m2)) IntMap.Bin(p2, m2, this.unionWith(l2, f), r2);
+        else IntMap.Bin(p2, m2, l2, this.unionWith(r2, f));
+      }
+      else {
+        if (p1 == p2) IntMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f));
+        else join(p1, this, p2, that);
+      }
+    case (IntMap.Tip(key, value), x) => x.updateWith(key, value, (x, y) => f(key, y, x));
+    case (x, IntMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y));
+    case (IntMap.Nil, x) => x;
+    case (x, IntMap.Nil) => x;
+  }
+
+  /**
+   * Forms the intersection of these two maps with a combinining function. The resulting map is
+   * a map that has only keys present in both maps and has values produced from the original mappings
+   * by combining them with f.
+   *
+   * @param that The map to intersect with.
+   * @param f The combining function.
+   */
+  def intersectionWith[S, R](that : IntMap[S], f : (Int, T, S) => R) : IntMap[R] = (this, that) match {
+    case (IntMap.Bin(p1, m1, l1, r1), that@IntMap.Bin(p2, m2, l2, r2)) =>
+      if (shorter(m1, m2)) {
+        if (!hasMatch(p2, p1, m1)) IntMap.Nil;
+        else if (zero(p2, m1)) l1.intersectionWith(that, f);
+        else r1.intersectionWith(that, f);
+      } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f));
+        else {
+        if (!hasMatch(p1, p2, m2)) IntMap.Nil;
+        else if (zero(p1, m2)) this.intersectionWith(l2, f);
+        else this.intersectionWith(r2, f);
+      }
+    case (IntMap.Tip(key, value), that) => that.get(key) match {
+      case None => IntMap.Nil;
+      case Some(value2) => IntMap.Tip(key, f(key, value, value2));
+    }
+    case (_, IntMap.Tip(key, value)) => this.get(key) match {
+      case None => IntMap.Nil;
+      case Some(value2) => IntMap.Tip(key, f(key, value2, value));
+    }
+    case (_, _) => IntMap.Nil;
+  }
+
+  /**
+   * Left biased intersection. Returns the map that has all the same mappings as this but only for keys
+   * which are present in the other map.
+   *
+   * @param that The map to intersect with.
+   */
+  def intersection[R](that : IntMap[R]) : IntMap[T] = this.intersectionWith(that, (key : Int, value : T, value2 : R) => value);
+
+  override def ++[S >: T](that : Iterable[(Int, S)]) = that match {
+    case (that : IntMap[_]) => this.unionWith[S](that.asInstanceOf[IntMap[S]], (key, x, y) => y);
+    case that => that.foldLeft(this : IntMap[S])({case (m, (x, y)) => m.update(x, y)});
+  }
+}
+
diff --git a/src/library/scala/collection/immutable/LongMap.scala b/src/library/scala/collection/immutable/LongMap.scala
new file mode 100644
index 0000000000..b23537aca6
--- /dev/null
+++ b/src/library/scala/collection/immutable/LongMap.scala
@@ -0,0 +1,360 @@
+package scala.collection.immutable;
+
+private[immutable] object LongMapUtils{
+  def zero(i : Long, mask : Long) = (i & mask) == 0;
+  def mask(i : Long, mask : Long) = i & (complement(mask - 1) ^ mask)
+  def hasMatch(key : Long, prefix : Long, m : Long) = mask(key, m) == prefix;
+  def unsignedCompare(i : Long, j : Long) = (i < j) ^ (i < 0) ^ (j < 0)
+  def shorter(m1 : Long, m2 : Long) = unsignedCompare(m2, m1)
+  def complement(i : Long) = (-1) ^ i;
+  def branchMask(i : Long, j : Long) = java.lang.Long.highestOneBit(i ^ j);
+
+  def join[T](p1 : Long, t1 : LongMap[T], p2 : Long, t2 : LongMap[T]) : LongMap[T] = {
+    val m = branchMask(p1, p2);
+    val p = mask(p1, m);
+    if (zero(p1, m)) LongMap.Bin(p, m, t1, t2)
+    else LongMap.Bin(p, m, t2, t1);
+  }
+
+  def bin[T](prefix : Long, mask : Long, left : LongMap[T], right : LongMap[T]) : LongMap[T] = (left, right) match {
+    case (left, LongMap.Nil) => left;
+    case (LongMap.Nil, right) => right;
+    case (left, right) => LongMap.Bin(prefix, mask, left, right);
+  }
+}
+
+import LongMapUtils._
+
+object LongMap{
+  def empty[T] : LongMap[T]  = LongMap.Nil;
+  def singleton[T](key : Long, value : T) : LongMap[T] = LongMap.Tip(key, value);
+  def apply[T](elems : (Long, T)*) : LongMap[T] =
+    elems.foldLeft(empty[T])((x, y) => x.update(y._1, y._2));
+
+
+  private[immutable] case object Nil extends LongMap[Nothing]{
+    override def equals(that : Any) = this eq that.asInstanceOf[AnyRef]
+  };
+  private[immutable] case class Tip[+T](key : Long, value : T) extends LongMap[T]{
+    def withValue[S](s : S) =
+      if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap.Tip[S]];
+      else LongMap.Tip(key, s);
+  }
+  private[immutable] case class Bin[+T](prefix : Long, mask : Long, left : LongMap[T], right : LongMap[T]) extends LongMap[T]{
+    def bin[S](left : LongMap[S], right : LongMap[S]) : LongMap[S] = {
+      if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[LongMap.Bin[S]];
+      else LongMap.Bin[S](prefix, mask, left, right);
+    }
+  }
+
+}
+
+import LongMap._
+
+// Iterator over a non-empty LongMap.
+private[immutable] abstract class LongMapIterator[V, T](it : LongMap[V]) extends Iterator[T]{
+
+  // Basically this uses a simple stack to emulate conversion over the tree. However
+  // because we know that Longs are only 64 bits we can have at most 64 LongMap.Bins and
+  // one LongMap.Tip sitting on the tree at any point. Therefore we know the maximum stack
+  // depth is 65
+  var index = 0;
+  var buffer = new Array[AnyRef](65);
+
+  def pop = {
+    index -= 1;
+    buffer(index).asInstanceOf[LongMap[V]];
+  }
+
+  def push(x : LongMap[V]) {
+    buffer(index) = x.asInstanceOf[AnyRef];
+    index += 1;
+  }
+  push(it);
+
+  /**
+   * What value do we assign to a tip?
+   */
+  def valueOf(tip : LongMap.Tip[V]) : T;
+
+  def hasNext = index != 0;
+  final def next : T =
+    pop match {
+      case LongMap.Bin(_,_, t@LongMap.Tip(_, _), right) => {
+        push(right);
+        valueOf(t);
+      }
+      case LongMap.Bin(_, _, left, right) => {
+        push(right);
+        push(left);
+        next;
+      }
+      case t@LongMap.Tip(_, _) => valueOf(t);
+      // This should never happen. We don't allow LongMap.Nil in subtrees of the LongMap
+      // and don't return an LongMapIterator for LongMap.Nil.
+      case LongMap.Nil => error("Empty maps not allowed as subtrees");
+    }
+}
+
+private[immutable] class LongMapEntryIterator[V](it : LongMap[V]) extends LongMapIterator[V, (Long, V)](it){
+  def valueOf(tip : LongMap.Tip[V]) = (tip.key, tip.value);
+}
+
+private[immutable] class LongMapValueIterator[V](it : LongMap[V]) extends LongMapIterator[V, V](it){
+  def valueOf(tip : LongMap.Tip[V]) = tip.value;
+}
+
+private[immutable] class LongMapKeyIterator[V](it : LongMap[V]) extends LongMapIterator[V, Long](it){
+  def valueOf(tip : LongMap.Tip[V]) = tip.key;
+}
+
+import LongMap._;
+
+/**
+ * Specialised immutable map structure for long keys, based on
+ * <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Long Maps</a>
+ * by Okasaki and Gill. Essentially a trie based on binary digits of the the integers.
+ */
+sealed abstract class LongMap[+T] extends scala.collection.immutable.Map[Long, T]{
+  def empty[S] : LongMap[S] = LongMap.Nil;
+
+  override def toList = {
+    val buffer = new scala.collection.mutable.ListBuffer[(Long, T)];
+    foreach(buffer += _);
+    buffer.toList;
+  }
+
+  /**
+   * Iterator over key, value pairs of the map in unsigned order of the keys.
+   */
+  def elements : Iterator[(Long, T)] = this match {
+    case LongMap.Nil => Iterator.empty;
+    case _ => new LongMapEntryIterator(this);
+  }
+
+  /**
+   * Loops over the key, value pairs of the map in unsigned order of the keys.
+   */
+  override final def foreach(f : ((Long, T)) => Unit) : Unit = this match {
+    case LongMap.Bin(_, _, left, right) => {left.foreach(f); right.foreach(f); }
+    case LongMap.Tip(key, value) => f((key, value));
+    case LongMap.Nil => {};
+  }
+
+  override def keys : Iterator[Long] = this match {
+    case LongMap.Nil => Iterator.empty;
+    case _ => new LongMapKeyIterator(this);
+  }
+
+  /**
+   * Loop over the keys of the map. The same as keys.foreach(f), but may
+   * be more efficient.
+   *
+   * @param f The loop body
+   */
+  final def foreachKey(f : Long => Unit) : Unit = this match {
+    case LongMap.Bin(_, _, left, right) => {left.foreachKey(f); right.foreachKey(f); }
+    case LongMap.Tip(key, _) => f(key);
+    case LongMap.Nil => {}
+  }
+
+  override def values : Iterator[T] = this match {
+    case LongMap.Nil => Iterator.empty;
+    case _ => new LongMapValueIterator(this);
+  }
+
+  /**
+   * Loop over the keys of the map. The same as keys.foreach(f), but may
+   * be more efficient.
+   *
+   * @param f The loop body
+   */
+  final def foreachValue(f : T => Unit) : Unit = this match {
+    case LongMap.Bin(_, _, left, right) => {left.foreachValue(f); right.foreachValue(f); }
+    case LongMap.Tip(_, value) => f(value);
+    case LongMap.Nil => {};
+  }
+
+  override def stringPrefix = "LongMap"
+
+  override def isEmpty = this == LongMap.Nil;
+
+  override def filter(f : ((Long, T)) => Boolean) : LongMap[T] = this match {
+    case LongMap.Bin(prefix, mask, left, right) => {
+      val (newleft, newright) = (left.filter(f), right.filter(f));
+      if ((left eq newleft) && (right eq newright)) this;
+      else bin(prefix, mask, newleft, newright);
+    }
+    case LongMap.Tip(key, value) =>
+      if (f((key, value))) this
+      else LongMap.Nil;
+    case LongMap.Nil => LongMap.Nil;
+  }
+
+  override def transform[S](f : (Long, T) => S) : LongMap[S] = this match {
+    case b@LongMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f));
+    case t@LongMap.Tip(key, value) => t.withValue(f(key, value));
+    case LongMap.Nil => LongMap.Nil;
+  }
+
+  final def size : Int = this match {
+    case LongMap.Nil => 0;
+    case LongMap.Tip(_, _) => 1;
+    case LongMap.Bin(_, _, left, right) => left.size + right.size;
+  }
+
+  final def get(key : Long) : Option[T] = this match {
+    case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key);
+    case LongMap.Tip(key2, value) => if (key == key2) Some(value) else None;
+    case LongMap.Nil => None;
+  }
+
+  final override def getOrElse[S >: T](key : Long, default : =>S) : S = this match {
+    case LongMap.Nil => default;
+    case LongMap.Tip(key2, value) => if (key == key2) value else default;
+    case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key);
+  }
+
+  final override def apply(key : Long) : T = this match {
+    case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key);
+    case LongMap.Tip(key2, value) => if (key == key2) value else error("Key not found");
+    case LongMap.Nil => error("key not found");
+  }
+
+  def update[S >: T](key : Long, value : S) : LongMap[S] = this match {
+    case LongMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this);
+                                          else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.update(key, value), right)
+                                          else LongMap.Bin(prefix, mask, left, right.update(key, value));
+    case LongMap.Tip(key2, value2) => if (key == key2) LongMap.Tip(key, value);
+                             else join(key, LongMap.Tip(key, value), key2, this);
+    case LongMap.Nil => LongMap.Tip(key, value);
+  }
+
+  /**
+   * Updates the map, using the provided function to resolve conflicts if the key is already present.
+   * Equivalent to
+   * <pre>this.get(key) match {
+   *         case None => this.update(key, value);
+   *         case Some(oldvalue) => this.update(key, f(oldvalue, value) }
+   * </pre>
+   *
+   * @param key The key to update
+   * @param value The value to use if there is no conflict
+   * @param f The function used to resolve conflicts.
+   */
+  def updateWith[S >: T](key : Long, value : S, f : (T, S) => S) : LongMap[S] = this match {
+    case LongMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this);
+                                          else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updateWith(key, value, f), right)
+                                          else LongMap.Bin(prefix, mask, left, right.updateWith(key, value, f));
+    case LongMap.Tip(key2, value2) => if (key == key2) LongMap.Tip(key, f(value2, value));
+                             else join(key, LongMap.Tip(key, value), key2, this);
+    case LongMap.Nil => LongMap.Tip(key, value);
+  }
+
+  def -(key : Long) : LongMap[T] = this match {
+    case LongMap.Bin(prefix, mask, left, right) =>
+      if (!hasMatch(key, prefix, mask)) this;
+      else if (zero(key, mask)) bin(prefix, mask, left - key, right);
+      else bin(prefix, mask, left, right - key);
+    case LongMap.Tip(key2, _) =>
+      if (key == key2) LongMap.Nil;
+      else this;
+    case LongMap.Nil => LongMap.Nil;
+  }
+
+  /**
+   * A combined transform and filter function. Returns an LongMap such that for each (key, value) mapping
+   * in this map, if f(key, value) == None the map contains no mapping for key, and if <code>f(key, value)
+   *
+   * @param f The transforming function.
+   */
+  def modifyOrRemove[S](f : (Long, T) => Option[S]) : LongMap[S] = this match {
+      case LongMap.Bin(prefix, mask, left, right) => {
+        val newleft = left.modifyOrRemove(f);
+        val newright = right.modifyOrRemove(f);
+        if ((left eq newleft) && (right eq newright)) this.asInstanceOf[LongMap[S]];
+        else bin(prefix, mask, newleft, newright)
+      }
+    case LongMap.Tip(key, value) => f(key, value) match {
+      case None => LongMap.Nil;
+      case Some(value2) =>
+        //hack to preserve sharing
+        if (value.asInstanceOf[AnyRef] eq value2.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap[S]]
+        else LongMap.Tip(key, value2);
+      }
+    case LongMap.Nil => LongMap.Nil;
+  }
+
+
+  /**
+   * Forms a union map with that map, using the combining function to resolve conflicts.
+   *
+   * @param that the map to form a union with.
+   * @param f the function used to resolve conflicts between two mappings.
+   */
+  def unionWith[S >: T](that : LongMap[S], f : (Long, S, S) => S) : LongMap[S] = (this, that) match{
+    case (LongMap.Bin(p1, m1, l1, r1), that@(LongMap.Bin(p2, m2, l2, r2))) =>
+      if (shorter(m1, m2)) {
+        if (!hasMatch(p2, p1, m1)) join(p1, this, p2, that);
+        else if (zero(p2, m1)) LongMap.Bin(p1, m1, l1.unionWith(that, f), r1);
+        else LongMap.Bin(p1, m1, l1, r1.unionWith(that, f));
+      } else if (shorter(m2, m1)){
+        if (!hasMatch(p1, p2, m2)) join(p1, this, p2, that);
+        else if (zero(p1, m2)) LongMap.Bin(p2, m2, this.unionWith(l2, f), r2);
+        else LongMap.Bin(p2, m2, l2, this.unionWith(r2, f));
+      }
+      else {
+        if (p1 == p2) LongMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f));
+        else join(p1, this, p2, that);
+      }
+    case (LongMap.Tip(key, value), x) => x.updateWith(key, value, (x, y) => f(key, y, x));
+    case (x, LongMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y));
+    case (LongMap.Nil, x) => x;
+    case (x, LongMap.Nil) => x;
+  }
+
+  /**
+   * Forms the intersection of these two maps with a combinining function. The resulting map is
+   * a map that has only keys present in both maps and has values produced from the original mappings
+   * by combining them with f.
+   *
+   * @param that The map to intersect with.
+   * @param f The combining function.
+   */
+  def intersectionWith[S, R](that : LongMap[S], f : (Long, T, S) => R) : LongMap[R] = (this, that) match {
+    case (LongMap.Bin(p1, m1, l1, r1), that@LongMap.Bin(p2, m2, l2, r2)) =>
+      if (shorter(m1, m2)) {
+        if (!hasMatch(p2, p1, m1)) LongMap.Nil;
+        else if (zero(p2, m1)) l1.intersectionWith(that, f);
+        else r1.intersectionWith(that, f);
+      } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f));
+        else {
+        if (!hasMatch(p1, p2, m2)) LongMap.Nil;
+        else if (zero(p1, m2)) this.intersectionWith(l2, f);
+        else this.intersectionWith(r2, f);
+      }
+    case (LongMap.Tip(key, value), that) => that.get(key) match {
+      case None => LongMap.Nil;
+      case Some(value2) => LongMap.Tip(key, f(key, value, value2));
+    }
+    case (_, LongMap.Tip(key, value)) => this.get(key) match {
+      case None => LongMap.Nil;
+      case Some(value2) => LongMap.Tip(key, f(key, value2, value));
+    }
+    case (_, _) => LongMap.Nil;
+  }
+
+  /**
+   * Left biased intersection. Returns the map that has all the same mappings as this but only for keys
+   * which are present in the other map.
+   *
+   * @param that The map to intersect with.
+   */
+  def intersection[R](that : LongMap[R]) : LongMap[T] = this.intersectionWith(that, (key : Long, value : T, value2 : R) => value);
+
+  override def ++[S >: T](that : Iterable[(Long, S)]) = that match {
+    case (that : LongMap[_]) => this.unionWith[S](that.asInstanceOf[LongMap[S]], (key, x, y) => y);
+    case that => that.foldLeft(this : LongMap[S])({case (m, (x, y)) => m.update(x, y)});
+  }
+}
+
diff --git a/src/library/scala/collection/immutable/TreeHashMap.scala b/src/library/scala/collection/immutable/TreeHashMap.scala
new file mode 100644
index 0000000000..1e0dd490fa
--- /dev/null
+++ b/src/library/scala/collection/immutable/TreeHashMap.scala
@@ -0,0 +1,270 @@
+package scala.collection.immutable;
+
+object TreeHashMap{
+  private[TreeHashMap] val _empty = new TreeHashMap[Any, Nothing](IntMap.empty[Nothing]);
+  def empty[Key, Value] : TreeHashMap[Key, Value] = _empty.asInstanceOf[TreeHashMap[Key, Value]];
+
+  def apply[Key, Value](elems : (Key, Value)*) : TreeHashMap[Key, Value] = fromIterable(elems)
+
+  def fromIterable[Key, Value](elems : Iterable[(Key, Value)]) : TreeHashMap[Key, Value] =
+    elems.foldLeft(TreeHashMap.empty[Key, Value])((m, entry) => m.update(entry._1, entry._2))
+
+  private def apply[Key, Value](underlying : IntMap[AssocMap[Key, Value]]) = new TreeHashMap(underlying);
+}
+
+/**
+ * An immutable Map which is based on an IntMap mapping hash codes to lists of (Key, Value) pairs with the
+ * same hashCode.
+ *
+ * Unlike the usual immutable.HashMap it is truly immutable behind the scenes. Consequently it is entirely
+ * safe to share between multiple threads and should achieve a much greater degree of sharing between instances.
+ *
+ * Performancewise, get and update seem to be somewhat slower than with a traditional hash map, but bulk operations
+ * such as filter, foreach and transform appear to get something of a speedup.
+ */
+class TreeHashMap[Key, +Value] private (private val underlying : IntMap[AssocMap[Key, Value]]) extends scala.collection.immutable.Map[Key, Value]{
+  def elements : Iterator[(Key, Value)] = new Iterator[(Key, Value)]{
+    val assocIt = new AssocMapIterator(AssocMap.empty[Key, Value]);
+    val intIterator = underlying.values;
+
+    def hasNext = assocIt.hasNext || intIterator.hasNext;
+    def next = {
+      if (!assocIt.hasNext) assocIt.it = intIterator.next;
+      assocIt.next
+    }
+  }
+
+  def empty[V] = TreeHashMap.empty[Key, V];
+
+  private def hash(key : Key) =  {
+    var h = key.hashCode;
+    h ^= ((h >>> 20) ^ (h >>> 12));
+    h ^ (h >>> 7) ^ (h >>> 4);
+  }
+
+  override def stringPrefix="TreeHashMap"
+
+  override lazy val size = underlying.values.foldLeft(0)((x, y) => x + y.size);
+
+  override def equals(that : Any) = that match {
+    case (that : TreeHashMap[_, _]) =>
+      if (this eq that) true
+      else if (this.size != that.size) false;
+      else this.underlying == that.underlying;
+    case _ => false;
+  }
+
+  override def hashCode = underlying.hashCode;
+
+  override def foreach(f : ((Key, Value)) => Unit) = underlying.foreachValue(_.foreach(f));
+
+  override def toList : List[(Key, Value)] = {
+    val buffer = new scala.collection.mutable.ListBuffer[(Key, Value)];
+    foreach(buffer += _);
+    buffer.toList;
+  }
+
+  override def apply(key : Key) =
+    underlying.get(hash(key)) match {
+      case None => default(key);
+      case Some(table) => table.getOrElse(key, default(key));
+  }
+
+  override def isEmpty = underlying.isEmpty;
+
+  override def filter(f : ((Key, Value)) => Boolean) : TreeHashMap[Key, Value]= {
+    val newunderlying = underlying.modifyOrRemove(
+      (key, x) => {
+        val newtable = x.filter(f);
+        if (newtable.isEmpty) None;
+        else Some(newtable);
+      }
+    )
+    if (newunderlying eq underlying) this;
+    else TreeHashMap(newunderlying);
+  }
+
+  override def transform[C](f : (Key, Value) => C) = {
+    val newunderlying = underlying.transform(
+      (key, value) => value.transform(f)
+    )
+    if (underlying eq newunderlying) this.asInstanceOf[TreeHashMap[Key, C]];
+    else TreeHashMap(newunderlying);
+  }
+
+  def get(key : Key) = underlying.get(hash(key)).flatMap(_.get(key));
+  def update[S >: Value](key : Key, value : S) : TreeHashMap[Key, S] = TreeHashMap(
+    underlying.updateWith[AssocMap[Key, S]](hash(key), AssocMap.singleton[Key, S](key, value), (x, y) => y.merge(x))
+  )
+
+  def -(key : Key) : TreeHashMap[Key, Value] = {
+    val h = hash(key);
+    underlying.get(h) match {
+      case None => this;
+      case Some(table) => {
+        val newtable = table - key;
+        if (table eq newtable) this;
+        else TreeHashMap(underlying.update(h, newtable));
+      }
+    }
+  }
+
+  override def ++[V >: Value](that : Iterable[(Key, V)]) : TreeHashMap[Key, V] = that match {
+    case (that : TreeHashMap[_, _]) => this ++ TreeHashMap.fromIterable(that.asInstanceOf[TreeHashMap[Key, V]])
+    case that => that.foldLeft(this : TreeHashMap[Key, V])((m, e) => m.update(e._1, e._2));
+  }
+
+  def ++[V >: Value](that : TreeHashMap[Key, V]) : TreeHashMap[Key, V] =
+    TreeHashMap(this.underlying.unionWith[AssocMap[Key, V]](that.underlying, (key, x, y) => x ++ y));
+}
+
+
+private [collection] object AssocMap{
+  val _empty = Nil[Any];
+  def empty[Key, Value] : AssocMap[Key, Value] = _empty.asInstanceOf[AssocMap[Key, Value]]
+  def singleton[Key, Value](key : Key, value : Value) = Cons(key, value, empty);
+  def apply[Key, Value](maps : (Key, Value)*) =
+    maps.foldLeft(empty[Key, Value])((x, y) => x.update(y._1, y._2));
+
+  private[collection] case class Nil[Key] extends AssocMap[Key, Nothing];
+  private[collection] case class Cons[S, +T](key : S, value : T, tail : AssocMap[S, T]) extends AssocMap[S, T]
+}
+
+import AssocMap._;
+
+// AssocMap is very similar to ListMap. I don't want to patch ListMap right now, so I've got a separate
+// implementation here to make tweaks to. Long term any of these changes should be merged into ListMap
+// Short term it doesn't really matter because there are almost no viable use cases for ListMap compared
+// to one of the alternatives.
+private[collection] sealed abstract class AssocMap[Key, +Value] extends immutable.Map[Key, Value]{
+  def empty[V] = AssocMap.empty[Key, V]
+
+  final def get(key : Key) : Option[Value] = this match {
+    case Nil() => None;
+    case Cons(key2, value, tail) => if (key == key2) Some(value)
+                                    else tail.get(key);
+  }
+
+  override final def getOrElse[V >: Value](key : Key, default : =>V) : V = this match {
+    case Nil() => default;
+    case Cons(key2, value, tail) => if (key == key2) value
+                                    else tail.getOrElse(key, default);
+  }
+
+  override final def apply(key : Key) : Value = getOrElse(key, default(key));
+
+  override def filter(f : ((Key, Value)) => Boolean) : AssocMap[Key, Value] = this match {
+    case Cons(key, value, tail) => {
+      val filteredtail = tail.filter(f);
+
+      if (f((key, value))) {
+        if (tail eq filteredtail) this;
+        else Cons(key, value, filteredtail);
+      } else filteredtail;
+    }
+    case Nil() => AssocMap.empty;
+  }
+
+  def elements : Iterator[(Key, Value)] = new AssocMapIterator(this);
+
+  override final def foreach(f : ((Key, Value)) => Unit) = this match {
+    case Cons(key, value, tail) => { f((key, value)); tail.foreach(f); }
+    case Nil() => {}
+  }
+
+  def size = this match {
+    case Nil() => 0;
+    case Cons(_, _, tail) => 1 + tail.size;
+  }
+
+  override def isEmpty = this match {
+    case Nil() => true;
+    case _ => false;
+  }
+
+  private def removeKeyValue(key : Any, value : Any) : Option[AssocMap[Key, Value]] = this match {
+    case Nil() => None;
+    case Cons(key2, value2, tail) =>
+      if (key == key2){
+        if (value == value2) Some(tail);
+        else None;
+      } else tail.removeKeyValue(key, value) match {
+        case None => None;
+        case Some(x) => Some(Cons(key2, value2, x));
+      }
+  }
+
+  private def sameMappings(that : AssocMap[_, _]) : Boolean = (this, that) match {
+    case (Nil(), Nil()) => true;
+    case (Nil(), _) => false;
+    case (_, Nil()) => false;
+    case (Cons(key, value, tail), that) =>  that.removeKeyValue(key, value) match {
+        case None => false;
+        case Some(x) => tail.sameMappings(x);
+      }
+  }
+
+  override def equals(that : Any) =
+    if (this eq that.asInstanceOf[AnyRef]) true;
+    else that match {
+      case (that : AssocMap[_, _]) =>
+        if (this.size != that.size) false;
+        else this.sameMappings(that);
+      case _ => false;
+    }
+
+  final def merge[S >: Value](that : AssocMap[Key, S]) : AssocMap[Key, S] = (this, that) match {
+    case (Nil(), that) => that;
+    case (_, Nil()) => this;
+    case (Cons(key, value, tail), that) =>
+      tail.merge[S](that).update(key, value);
+  }
+
+  def update[S >: Value](key : Key, value : S) : AssocMap[Key, S] = this match {
+    case Nil() => Cons(key, value, empty);
+    case Cons(key2, value2, tail) =>
+      if (key2 == key) Cons(key, value, tail)
+      else Cons(key2, value2, tail.update(key, value));
+  }
+
+  override def transform[C](f : (Key, Value) => C) : AssocMap[Key, C] = this match {
+    case Nil() => AssocMap.empty[Key, C];
+    case Cons(key, value, tail) => {
+      val newtail = tail.transform(f);
+      val newval = f(key, value);
+      if ((tail eq newtail) && (value.asInstanceOf[AnyRef] eq newval.asInstanceOf[AnyRef])) this.asInstanceOf[AssocMap[Key, C]];
+      else Cons(key, newval, newtail);
+    }
+  }
+
+  def -(key : Key) : AssocMap[Key, Value]= this match {
+    case Nil() => this;
+    case Cons(key2, value, tail) =>
+      if (key == key2) tail;
+      else {
+        val newtail = tail - key;
+        if (tail eq newtail) this;
+        else Cons(key2, value, newtail);
+      }
+  }
+
+  final def ++[V >: Value](that : AssocMap[Key, V]) : AssocMap[Key, V] = (this, that) match {
+    case (Nil(), that) => that;
+    case (_, Nil()) => this;
+    case (t1, Cons(key, value, tail)) => t1.update(key, value.asInstanceOf[Value] /* evil hack to work around bug 1140 */) ++ tail;
+  }
+}
+
+private[collection] class AssocMapIterator[Key, Value](var it : AssocMap[Key, Value]) extends Iterator[(Key, Value)]{
+  def hasNext = it match {
+    case Nil() => false;
+    case _ => true;
+  }
+
+  def next = {
+    val Cons(key, value, next) = it;
+    it = next;
+    (key, value);
+  }
+}
+
diff --git a/src/library/scala/collection/mutable/ArrayStack.scala b/src/library/scala/collection/mutable/ArrayStack.scala
new file mode 100644
index 0000000000..27e73f364e
--- /dev/null
+++ b/src/library/scala/collection/mutable/ArrayStack.scala
@@ -0,0 +1,155 @@
+package scala.collection.mutable;
+
+private object Utils{
+  def growArray(x : Array[AnyRef]) = {
+    val y = new Array[AnyRef](x.length * 2);
+    Array.copy(x, 0, y, 0, x.length);
+    y;
+  }
+
+  def clone(x : Array[AnyRef]) = {
+    val y = new Array[AnyRef](x.length);
+    Array.copy(x, 0, y, 0, x.length);
+    y;
+  }
+}
+
+/**
+ * Simple stack class backed by an array. Should be significantly faster
+ * than the standard mutable stack.
+ */
+class ArrayStack[T] private(private var table : Array[AnyRef],
+                            private var index : Int) extends Collection[T]{
+  def this() = this(new Array[AnyRef](1), 0);
+
+  /**
+   * Push an element onto the stack.
+   *
+   * @param x The element to push
+   */
+  def push(x : T) = {
+    if (index == table.length) table = Utils.growArray(table);
+    table(index) = x.asInstanceOf[AnyRef];
+    index += 1;
+  }
+
+  /**
+   * Pop the top element off the stack.
+   */
+  def pop = {
+    if (index == 0) error("Stack empty");
+    index -= 1;
+    val x = table(index).asInstanceOf[T];
+    table(index) = null;
+    x;
+  }
+
+  /**
+   * View the top element of the stack.
+   */
+  def peek = table(index - 1).asInstanceOf[T]
+
+  /**
+   * Duplicate the top element of the stack.
+   */
+  def dup = push(peek);
+
+  /**
+   * Empties the stack.
+   */
+  def clear = {
+    index = 0;
+    table = new Array(1);
+  }
+
+  /**
+   * Empties the stack, passing all elements on it in FIFO order to the
+   * provided function.
+   *
+   * @param f The function to drain to.
+   */
+  def drain(f : T => Unit) = while(!isEmpty) f(pop);
+
+  /**
+   * Pushes all the provided elements onto the stack.
+   *
+   * @param x The source of elements to push
+   */
+  def ++=(x : Iterable[T]) = x.foreach(this +=(_))
+
+
+  /**
+   * Pushes all the provided elements onto the stack.
+   *
+   * @param x The source of elements to push
+   */
+  def ++=(x : Iterator[T]) = x.foreach(this +=(_))
+
+  /**
+   *  Alias for push.
+   *
+   *  @param x The element to push
+   */
+  def +=(x : T) = push(x);
+
+
+
+  /**
+   * Pop the top two elements off the stack, apply f to them and push the result
+   * back on to the stack.
+   *
+   * @param f The combining function
+   */
+  def combine(f : (T, T) => T) = push(f(pop, pop));
+
+  /**
+   * Repeatedly combine the top elements of the stack until the stack contains only
+   * one element.
+   */
+  def reduceWith(f : (T, T) => T) = while(size > 1) combine(f)
+
+  def size = index;
+
+  /**
+   * Evaluates the expression, preserving the contents of the stack so that
+   * any changes the evaluation makes to the stack contents will be undone after
+   * it completes.
+   *
+   * @param action The action to run.
+   */
+  def preserving[T](action : => T) = {
+    val oldIndex = index;
+    val oldTable = Utils.clone(table);
+
+    try{
+      action;
+    } finally {
+      index = oldIndex;
+      table = oldTable;
+    }
+  }
+
+  override def isEmpty = index == 0;
+
+  /**
+   * Iterates over the stack in fifo order.
+   */
+  def elements = new Iterator[T]{
+    var currentIndex = index;
+    def hasNext = currentIndex > 0;
+    def next = {
+      currentIndex -= 1;
+      table(currentIndex).asInstanceOf[T];
+    }
+  }
+
+  override def foreach(f : T => Unit){
+    var currentIndex = index;
+    while(currentIndex > 0){
+      currentIndex -= 1;
+      f(table(currentIndex).asInstanceOf[T]);
+    }
+  }
+
+  override def clone = new ArrayStack[T](Utils.clone(table), index);
+}