cleaned up collection builder framework

65 files changed, 651 insertions, 575 deletions

diff --git a/src/library/scala/Array.scala b/src/library/scala/Array.scala
index 6336a774c6..820195be3c 100644
--- a/src/library/scala/Array.scala
+++ b/src/library/scala/Array.scala
@@ -25,7 +25,6 @@ object Array extends SequenceFactory[Array] {
   import runtime.BoxedArray;
   import scala.runtime.ScalaRunTime.boxArray;
 
-  type Coll = Array[_]
   implicit def builderFactory[A]: BuilderFactory[A, Array[A], Coll] = new BuilderFactory[A, Array[A], Coll] { def apply(from: Coll) = newBuilder[A] }
   def newBuilder[A]: Builder[A, Array[A]] = new ArrayBuffer[A].mapResult(_.toArray)
 
@@ -246,9 +245,11 @@ object Array extends SequenceFactory[Array] {
  *  @author Martin Odersky
  *  @version 1.0
  */
-final class Array[A](_length: Int) extends Vector[A] with VectorTemplate[A, Array[A]] {
+final class Array[A](_length: Int) extends Vector[A]
+                                      with TraversableClass[A, Array]
+                                      with VectorTemplate[A, Array[A]] {
 
-  override protected[this] def newBuilder: Builder[A, Array[A]] = throw new Error()
+  override def companion: Companion[Array] = throw new Error()
 
    /** Multidimensional array creation
     *  @deprecated use Array.ofDim instead
diff --git a/src/library/scala/collection/BitSet.scala b/src/library/scala/collection/BitSet.scala
index 2fb469e680..b7a77c63ce 100644
--- a/src/library/scala/collection/BitSet.scala
+++ b/src/library/scala/collection/BitSet.scala
@@ -15,17 +15,13 @@ import generic._
 
 /** common base class for mutable and immutable bit sets
  */
-trait BitSet extends Set[Int] with BitSetTemplate[BitSet] {
-  override def empty = BitSet.empty
+trait BitSet extends Set[Int]
+                with BitSetTemplate[BitSet] {
+  override def empty: BitSet = BitSet.empty
 }
 
 /** A factory object for bitsets */
-object BitSet {
-
-    /** The empty bitset */
+object BitSet extends BitSetFactory[BitSet] {
   val empty: BitSet = immutable.BitSet.empty
-
-  /** A bitset containing given elements */
-  def apply(elems: Int*) = immutable.BitSet.apply(elems: _*)
 }
 
diff --git a/src/library/scala/collection/Iterable.scala b/src/library/scala/collection/Iterable.scala
index 42b6c5afe7..af52831428 100644
--- a/src/library/scala/collection/Iterable.scala
+++ b/src/library/scala/collection/Iterable.scala
@@ -31,9 +31,10 @@ import generic._
  *  @author Martin Odersky
  *  @version 2.8
  */
-trait Iterable[+A] extends Traversable[A] with IterableTemplate[A, Iterable[A]] {
-  override protected[this] def newBuilder = Iterable.newBuilder
-  override def traversableBuilder[B]: Builder[B, Iterable[B]] = Iterable.newBuilder[B]
+trait Iterable[+A] extends Traversable[A]
+                      with TraversableClass[A, Iterable]
+                      with IterableTemplate[A, Iterable[A]] {
+   override def companion: Companion[Iterable] = Iterable
 
   /* The following methods are inherited from trait IterableTemplate
    *
@@ -44,13 +45,13 @@ trait Iterable[+A] extends Traversable[A] with IterableTemplate[A, Iterable[A]]
   override def view
   override def view(from: Int, until: Int)
   */
+
 }
 
 /** Factory methods and utilities for instances of type Traversable */
 object Iterable extends TraversableFactory[Iterable] {
 
-  type Coll	= Iterable[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new BuilderFactory[A, Iterable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Iterable[A]] = immutable.Iterable.newBuilder[A]
 
   def fromOld[A](it: scala.Iterable[A]): Iterable[A] = new Iterable[A] {
diff --git a/src/library/scala/collection/LinearSequence.scala b/src/library/scala/collection/LinearSequence.scala
index aed1b88a9a..676102fe35 100644
--- a/src/library/scala/collection/LinearSequence.scala
+++ b/src/library/scala/collection/LinearSequence.scala
@@ -26,13 +26,13 @@ import util.control.Breaks._
  *  @author  Matthias Zenger
  *  @version 1.0, 16/07/2003
  */
-trait LinearSequence[+A] extends Sequence[A] with LinearSequenceTemplate[A, LinearSequence[A]] {
-  override protected[this] def newBuilder = LinearSequence.newBuilder
-  override def traversableBuilder[B]: Builder[B, LinearSequence[B]] = LinearSequence.newBuilder[B]
+trait LinearSequence[+A] extends Sequence[A]
+                            with TraversableClass[A, LinearSequence]
+                            with LinearSequenceTemplate[A, LinearSequence[A]] {
+  override def companion: Companion[LinearSequence] = LinearSequence
 }
 
 object LinearSequence extends SequenceFactory[LinearSequence] {
-  type Coll = LinearSequence[_]
-  implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new BuilderFactory[A, LinearSequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, LinearSequence[A]] = immutable.LinearSequence.newBuilder[A]
 }
diff --git a/src/library/scala/collection/Map.scala b/src/library/scala/collection/Map.scala
index 3544c195dd..174ed8e863 100644
--- a/src/library/scala/collection/Map.scala
+++ b/src/library/scala/collection/Map.scala
@@ -37,16 +37,11 @@ import generic._
  */
 trait Map[A, +B] extends Iterable[(A, B)] with MapTemplate[A, B, Map[A, B]] {
   def empty: Map[A, B] = Map.empty
-
-  override protected[this] def newBuilder : Builder[(A, B), Map[A, B]] =
-    throw new UnsupportedOperationException("Map.newBuilder")
-
-  def mapBuilder[A, B]: Builder[(A, B), Map[A, B]] = Map.newBuilder[A, B]
+  override protected[this] def newBuilder: Builder[(A, B), Map[A, B]] = immutable.Map.newBuilder[A, B]
 }
 
 /* Factory object for `Map` class */
 object Map extends ImmutableMapFactory[immutable.Map] {
-  type Coll = Map[_, _]
   def empty[A, B]: immutable.Map[A, B] = immutable.Map.empty
-  implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new BuilderFactory[(A, B), Map[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] }
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new MapBuilderFactory[A, B]
 }
diff --git a/src/library/scala/collection/Sequence.scala b/src/library/scala/collection/Sequence.scala
index 5391a89997..c5853355d4 100644
--- a/src/library/scala/collection/Sequence.scala
+++ b/src/library/scala/collection/Sequence.scala
@@ -28,15 +28,16 @@ import util.control.Breaks._
  *  @author  Matthias Zenger
  *  @version 1.0, 16/07/2003
  */
-trait Sequence[+A] extends PartialFunction[Int, A] with Iterable[A] with SequenceTemplate[A, Sequence[A]] {
-  override protected[this] def newBuilder = Sequence.newBuilder
-  override def traversableBuilder[B]: Builder[B, Sequence[B]] = Sequence.newBuilder[B]
+trait Sequence[+A] extends PartialFunction[Int, A]
+                      with Iterable[A]
+                      with TraversableClass[A, Sequence]
+                      with SequenceTemplate[A, Sequence[A]] {
+  override def companion: Companion[Sequence] = Sequence
 }
 
 object Sequence extends SequenceFactory[Sequence] {
 
-  type Coll = Sequence[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new BuilderFactory[A, Sequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Sequence[A]] = immutable.Sequence.newBuilder[A]
 
   /** @deprecated use View instead
diff --git a/src/library/scala/collection/Set.scala b/src/library/scala/collection/Set.scala
index 16cfbf3a1b..8a215a0bf2 100644
--- a/src/library/scala/collection/Set.scala
+++ b/src/library/scala/collection/Set.scala
@@ -21,16 +21,17 @@ import generic._
  *  @author  Martin Odersky
  *  @version 2.8
  */
-trait Set[A] extends (A => Boolean) with Iterable[A] with SetTemplate[A, Set[A]] {
-  def empty = Set.empty
-  override def traversableBuilder[B]: Builder[B, Set[B]] = Set.newBuilder[B]
+trait Set[A] extends (A => Boolean)
+                with Iterable[A]
+                with SetClass[A, Set]
+                with SetTemplate[A, Set[A]] {
+  override def companion: Companion[Set] = Set
 }
 
 /* Factory object for `Set` class */
 object Set extends SetFactory[Set] {
-  def empty[A]: Set[A] = immutable.Set.empty[A]
-  type Coll = Set[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = new BuilderFactory[A, Set[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  override def empty[A]: Set[A] = immutable.Set.empty[A]
+  implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = setBuilderFactory[A]
 }
 
 /* !!! what to do about this?
diff --git a/src/library/scala/collection/SortedMap.scala b/src/library/scala/collection/SortedMap.scala
index b2f44ebbac..1c1029da58 100644
--- a/src/library/scala/collection/SortedMap.scala
+++ b/src/library/scala/collection/SortedMap.scala
@@ -19,8 +19,16 @@ import generic._
  */
 trait SortedMap[A, +B] extends Map[A, B] with SortedMapTemplate[A, B, SortedMap[A, B]] {
   /** Needs to be overridden in subclasses. */
-  override def empty: SortedMap[A, B] = throw new UnsupportedOperationException("SortedMap.empty")
+  override def empty = SortedMap.empty[A, B]
+
   override protected[this] def newBuilder : Builder[(A, B), SortedMap[A, B]] =
-    throw new UnsupportedOperationException("SortedMap.newBuilder")
+    immutable.SortedMap.newBuilder[A, B]
+}
 
+object SortedMap extends ImmutableSortedMapFactory[immutable.SortedMap] {
+  implicit def builderFactory[A, B](implicit ord: Ordering[A]): BuilderFactory[(A, B), SortedMap[A, B], Coll] = new SortedMapBuilderFactory[A, B]
+  def empty[A, B](implicit ord: Ordering[A]): immutable.SortedMap[A, B] = immutable.SortedMap.empty[A, B](ord)
 }
+
+
+
diff --git a/src/library/scala/collection/Traversable.scala b/src/library/scala/collection/Traversable.scala
index 39a7a188f0..4d2ace813c 100644
--- a/src/library/scala/collection/Traversable.scala
+++ b/src/library/scala/collection/Traversable.scala
@@ -25,9 +25,9 @@ import generic._
  *  @author Martin Odersky
  *  @version 2.8
  */
-trait Traversable[+A] extends TraversableTemplate[A, Traversable[A]] {
-  protected[this] def newBuilder = Traversable.newBuilder
-  def traversableBuilder[B]: Builder[B, Traversable[B]] = Traversable.newBuilder[B]
+trait Traversable[+A] extends TraversableTemplate[A, Traversable[A]]
+                         with TraversableClass[A, Traversable] {
+  def companion: Companion[Traversable] = Traversable
 
   /* The following methods are inherited from TraversableTemplate
    *
@@ -93,10 +93,9 @@ trait Traversable[+A] extends TraversableTemplate[A, Traversable[A]] {
 /** Factory methods and utilities for instances of type Traversable */
 object Traversable extends TraversableFactory[Traversable] { self =>
 
-  type Coll = Traversable[_]
 
-  implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] =
-    new BuilderFactory[A, Traversable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new VirtualBuilderFactory[A]
+//    new BuilderFactory[A, Traversable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
 
   def newBuilder[A]: Builder[A, Traversable[A]] = immutable.Traversable.newBuilder[A]
 
diff --git a/src/library/scala/collection/Vector.scala b/src/library/scala/collection/Vector.scala
index 7ac579283c..723fd8c610 100644
--- a/src/library/scala/collection/Vector.scala
+++ b/src/library/scala/collection/Vector.scala
@@ -21,13 +21,13 @@ import mutable.ArrayBuffer
  *  @author Martin Odersky
  *  @version 2.8
  */
-trait Vector[+A] extends Sequence[A] with VectorTemplate[A, Vector[A]] {
-  override protected[this] def newBuilder = Vector.newBuilder
-  override def traversableBuilder[B]: Builder[B, Vector[B]] = Vector.newBuilder[B]
+trait Vector[+A] extends Sequence[A]
+                    with TraversableClass[A, Vector]
+                    with VectorTemplate[A, Vector[A]] {
+  override def companion: Companion[Vector] = Vector
 }
 
 object Vector extends SequenceFactory[Vector] {
-  type Coll = Vector[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new BuilderFactory[A, Vector[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Vector[A]] = mutable.Vector.newBuilder[A]
 }
diff --git a/src/library/scala/collection/generic/BitSetFactory.scala b/src/library/scala/collection/generic/BitSetFactory.scala
new file mode 100644
index 0000000000..479a857ee7
--- /dev/null
+++ b/src/library/scala/collection/generic/BitSetFactory.scala
@@ -0,0 +1,19 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+// $Id: Traversable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+package scala.collection.generic
+
+trait BitSetFactory[Coll <: BitSet with BitSetTemplate[Coll]] {
+  def newBuilder: Builder[Int, Coll] = new AddingBuilder[Int, Coll](empty)
+  def empty: Coll
+  def apply(elems: Int*): Coll = (empty /: elems) (_ + _)
+  def bitsetBuilderFactory = new BuilderFactory[Int, Coll, Coll] {
+    def apply(from: Coll) = newBuilder
+  }
+}
+
diff --git a/src/library/scala/collection/generic/BitSetTemplate.scala b/src/library/scala/collection/generic/BitSetTemplate.scala
index 83c51d9aed..f5c5a64d4e 100644
--- a/src/library/scala/collection/generic/BitSetTemplate.scala
+++ b/src/library/scala/collection/generic/BitSetTemplate.scala
@@ -7,6 +7,8 @@ import generic._
  */
 trait BitSetTemplate[+This <: BitSetTemplate[This] with Set[Int]] extends SetTemplate[Int, This] { self =>
 
+  def empty: This
+
   /** The number of words (each with 64 bits) making up the set */
   protected def nwords: Int
 
diff --git a/src/library/scala/collection/generic/Companion.scala b/src/library/scala/collection/generic/Companion.scala
new file mode 100644
index 0000000000..21bd6ece3e
--- /dev/null
+++ b/src/library/scala/collection/generic/Companion.scala
@@ -0,0 +1,26 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+// $Id: Traversable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+package scala.collection.generic
+
+abstract class Companion[+CC[X] <: Traversable[X]] {
+  type Coll = CC[_]
+
+  def newBuilder[A]: Builder[A, CC[A]]
+
+ /** The empty iterable of type CC */
+  def empty[A]:  CC[A] = newBuilder[A].result
+
+  /** Creates an iterable of type CC with specified elements */
+  def apply[A](args: A*): CC[A] = {
+    val b = newBuilder[A]
+    b ++= args
+    b.result
+  }
+}
+
diff --git a/src/library/scala/collection/generic/ImmutableMapFactory.scala b/src/library/scala/collection/generic/ImmutableMapFactory.scala
index 51758fe8c2..07eb37a4ad 100644
--- a/src/library/scala/collection/generic/ImmutableMapFactory.scala
+++ b/src/library/scala/collection/generic/ImmutableMapFactory.scala
@@ -2,15 +2,8 @@ package scala.collection.generic
 
 /** A template for companion objects of immutable.Map and subclasses thereof.
  */
-abstract class ImmutableMapFactory[CC[A, +B] <: immutable.Map[A, B] with MapTemplate[A, B, CC[A, B]]] {
+abstract class ImmutableMapFactory[CC[A, +B] <: immutable.Map[A, B] with ImmutableMapTemplate[A, B, CC[A, B]]]
+  extends MapFactory[CC] {
 
-  def newBuilder[A, B]: Builder[(A, B), CC[A, B]] = new ImmutableMapBuilder[A, B, CC[A, B]](empty[A, B])
-
-  def empty[A, B]: CC[A, B]
-
-  def apply[A, B](elems: (A, B)*): CC[A, B] = {
-    val b = newBuilder[A, B]
-    b ++= Iterable.fromOld(elems)
-    b.result
-  }
+  def newBuilder[A, B] = new ImmutableMapBuilder[A, B, CC[A, B]](empty[A, B])
 }
diff --git a/src/library/scala/collection/generic/ImmutableSortedMapFactory.scala b/src/library/scala/collection/generic/ImmutableSortedMapFactory.scala
new file mode 100644
index 0000000000..d6751e24e9
--- /dev/null
+++ b/src/library/scala/collection/generic/ImmutableSortedMapFactory.scala
@@ -0,0 +1,10 @@
+package scala.collection.generic
+
+/** A template for companion objects of mutable.Map and subclasses thereof.
+ */
+abstract class ImmutableSortedMapFactory[CC[A, B] <: immutable.SortedMap[A, B] with SortedMapTemplate[A, B, CC[A, B]]]
+  extends SortedMapFactory[CC] {
+
+  def newBuilder[A, B](implicit ord: Ordering[A]): Builder[(A, B), CC[A, B]] =
+    new ImmutableMapBuilder[A, B, CC[A, B]](empty(ord))
+}
diff --git a/src/library/scala/collection/generic/MapFactory.scala b/src/library/scala/collection/generic/MapFactory.scala
new file mode 100644
index 0000000000..067f22dbf1
--- /dev/null
+++ b/src/library/scala/collection/generic/MapFactory.scala
@@ -0,0 +1,18 @@
+package scala.collection.generic
+
+/** A template for companion objects of mutable.Map and subclasses thereof.
+ */
+abstract class MapFactory[CC[A, B] <: Map[A, B] with MapTemplate[A, B, CC[A, B]]] {
+
+  type Coll = CC[_, _]
+
+  def newBuilder[A, B]: Builder[(A, B), CC[A, B]]
+
+  def empty[A, B]: CC[A, B]
+
+  def apply[A, B](elems: (A, B)*): CC[A, B] = (newBuilder[A, B] ++= elems).result
+
+  class MapBuilderFactory[A, B] extends BuilderFactory[(A, B), CC[A, B], Coll] {
+    def apply(from: Coll) = newBuilder[A, B]
+  }
+}
diff --git a/src/library/scala/collection/generic/MapTemplate.scala b/src/library/scala/collection/generic/MapTemplate.scala
index 3f2c9d2fb0..1076347977 100644
--- a/src/library/scala/collection/generic/MapTemplate.scala
+++ b/src/library/scala/collection/generic/MapTemplate.scala
@@ -33,8 +33,6 @@ trait MapTemplate[A, +B, +This <: MapTemplate[A, B, This] with Map[A, B]]
      with Subtractable[A, This] {
 self =>
 
-//  import immutable.{Set, FlexSet}
-
   def empty: This
 
   /** Is this an empty map?
diff --git a/src/library/scala/collection/generic/MutableMapBuilder.scala b/src/library/scala/collection/generic/MutableMapBuilder.scala
index 419eaef0a4..1e55a3b069 100644
--- a/src/library/scala/collection/generic/MutableMapBuilder.scala
+++ b/src/library/scala/collection/generic/MutableMapBuilder.scala
@@ -19,8 +19,8 @@ package scala.collection.generic
  */
 class MutableMapBuilder[A, B, Coll <: mutable.Map[A, B] with MapTemplate[A, B, Coll]](empty: Coll)
 extends Builder[(A, B), Coll] {
-  protected var elems: Coll = empty
+  protected val elems: Coll = empty
   def +=(x: (A, B)): this.type = { elems += x; this }
-  def clear() { elems = empty }
+  def clear() { elems.clear() }
   def result: Coll = elems
 }
diff --git a/src/library/scala/collection/generic/MutableMapFactory.scala b/src/library/scala/collection/generic/MutableMapFactory.scala
index 9b3ccf7221..09fc16cd02 100644
--- a/src/library/scala/collection/generic/MutableMapFactory.scala
+++ b/src/library/scala/collection/generic/MutableMapFactory.scala
@@ -2,15 +2,8 @@ package scala.collection.generic
 
 /** A template for companion objects of mutable.Map and subclasses thereof.
  */
-abstract class MutableMapFactory[CC[A, B] <: mutable.Map[A, B] with MutableMapTemplate[A, B, CC[A, B]]] {
+abstract class MutableMapFactory[CC[A, B] <: mutable.Map[A, B] with MutableMapTemplate[A, B, CC[A, B]]]
+  extends MapFactory[CC] {
 
-  def newBuilder[A, B]: Builder[(A, B), CC[A, B]] = new MutableMapBuilder(empty[A, B])
-
-  def empty[A, B]: CC[A, B]
-
-  def apply[A, B](elems: (A, B)*): CC[A, B] = {
-    val b = newBuilder[A, B]
-    b ++= Iterable.fromOld(elems)
-    b.result
-  }
+  def newBuilder[A, B] = new MutableMapBuilder[A, B, CC[A, B]](empty[A, B])
 }
diff --git a/src/library/scala/collection/generic/SequenceFactory.scala b/src/library/scala/collection/generic/SequenceFactory.scala
index b3ae8c7dd2..3a2979dd70 100644
--- a/src/library/scala/collection/generic/SequenceFactory.scala
+++ b/src/library/scala/collection/generic/SequenceFactory.scala
@@ -2,7 +2,7 @@ package scala.collection.generic
 
 /** A template for companion objects of Sequence and subclasses thereof.
  */
-abstract class SequenceFactory[CC[A] <: Sequence[A]] extends TraversableFactory[CC] {
+abstract class SequenceFactory[CC[X] <: Sequence[X] with TraversableClass[X, CC]] extends TraversableFactory[CC] {
 
   /** This method is called in a pattern match { case Sequence(...) => }.
    *
diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala
index b1643a1a62..c8f321075f 100644
--- a/src/library/scala/collection/generic/SequenceTemplate.scala
+++ b/src/library/scala/collection/generic/SequenceTemplate.scala
@@ -12,6 +12,7 @@
 package scala.collection.generic
 
 import mutable.{ListBuffer, HashMap}
+
 // import immutable.{List, Nil, ::}
 import generic._
 import util.control.Breaks._
@@ -402,8 +403,12 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]]
     b.result
   }
 
-  private def occCounts[B](seq: Sequence[B]): HashMap[B, Int] = {
-    val occ = new HashMap[B, Int] { override def default(k: B) = 0 }
+  private def occCounts[B](seq: Sequence[B]): mutable.Map[B, Int] = {
+    val occ =
+      if (seq.isEmpty || seq.head.isInstanceOf[Unhashable])
+        new mutable.ListMap[B, Int] { override def default(k: B) = 0 }
+      else
+        new mutable.HashMap[B, Int] { override def default(k: B) = 0 }
     for (y <- seq) occ(y) += 1
     occ
   }
diff --git a/src/library/scala/collection/generic/SetClass.scala b/src/library/scala/collection/generic/SetClass.scala
new file mode 100644
index 0000000000..0b38b7c91e
--- /dev/null
+++ b/src/library/scala/collection/generic/SetClass.scala
@@ -0,0 +1,14 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+// $Id: Traversable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+package scala.collection.generic
+
+trait SetClass[A, +CC[X] <: Set[X]] extends TraversableClass[A, CC] {
+  def empty: CC[A] = companion.empty[A]
+}
+
diff --git a/src/library/scala/collection/generic/SetFactory.scala b/src/library/scala/collection/generic/SetFactory.scala
index ea7bb69192..72774e659b 100644
--- a/src/library/scala/collection/generic/SetFactory.scala
+++ b/src/library/scala/collection/generic/SetFactory.scala
@@ -2,15 +2,12 @@ package scala.collection.generic
 
 /** A template for companion objects of Map and subclasses thereof.
  */
-abstract class SetFactory[CC[A] <: Set[A] with SetTemplate[A, CC[A]]] {
+abstract class SetFactory[CC[X] <: Set[X] with SetTemplate[X, CC[X]]]
+  extends Companion[CC] {
 
   def newBuilder[A]: Builder[A, CC[A]] = new AddingBuilder[A, CC[A]](empty[A])
 
-  def empty[A]: CC[A]
-
-  def apply[A](elems: A*): CC[A] = {
-    var s = empty[A]
-    for (elem <- elems) s = s + elem
-    s
+  def setBuilderFactory[A] = new BuilderFactory[A, CC[A], CC[_]] {
+    def apply(from: CC[_]) = newBuilder[A]
   }
 }
diff --git a/src/library/scala/collection/generic/SetTemplate.scala b/src/library/scala/collection/generic/SetTemplate.scala
index 5d5abca295..ed706ab1bc 100644
--- a/src/library/scala/collection/generic/SetTemplate.scala
+++ b/src/library/scala/collection/generic/SetTemplate.scala
@@ -30,7 +30,6 @@ trait SetTemplate[A, +This <: SetTemplate[A, This] with Set[A]] extends Iterable
 self =>
 
   def empty: This
-
   override protected[this] def newBuilder: Builder[A, This] = new AddingBuilder[A, This](empty)
 
   /** Checks if this set contains element <code>elem</code>.
diff --git a/src/library/scala/collection/generic/SortedMapFactory.scala b/src/library/scala/collection/generic/SortedMapFactory.scala
new file mode 100644
index 0000000000..938ce145f9
--- /dev/null
+++ b/src/library/scala/collection/generic/SortedMapFactory.scala
@@ -0,0 +1,18 @@
+package scala.collection.generic
+
+/** A template for companion objects of mutable.Map and subclasses thereof.
+ */
+abstract class SortedMapFactory[CC[A, B] <: SortedMap[A, B] with SortedMapTemplate[A, B, CC[A, B]]] {
+
+  type Coll = CC[_, _]
+
+  def newBuilder[A, B](implicit ord: Ordering[A]): Builder[(A, B), CC[A, B]]
+
+  def empty[A, B](implicit ord: Ordering[A]): CC[A, B]
+
+  def apply[A, B](elems: (A, B)*)(implicit ord: Ordering[A]): CC[A, B] = (newBuilder[A, B](ord) ++= elems).result
+
+  class SortedMapBuilderFactory[A, B](implicit ord: Ordering[A]) extends BuilderFactory[(A, B), CC[A, B], Coll] {
+    def apply(from: Coll) = newBuilder[A, B](ord)
+  }
+}
diff --git a/src/library/scala/collection/generic/SortedMapTemplate.scala b/src/library/scala/collection/generic/SortedMapTemplate.scala
index eefd257136..90c81e8484 100644
--- a/src/library/scala/collection/generic/SortedMapTemplate.scala
+++ b/src/library/scala/collection/generic/SortedMapTemplate.scala
@@ -23,6 +23,8 @@ self =>
   def firstKey : A = head._1
   def lastKey : A = last._1
 
+  implicit def ordering: Ordering[A]
+
   // XXX: implement default version
   def rangeImpl(from : Option[A], until : Option[A]) : This
 
diff --git a/src/library/scala/collection/generic/TraversableClass.scala b/src/library/scala/collection/generic/TraversableClass.scala
new file mode 100644
index 0000000000..9ed2ff4eb3
--- /dev/null
+++ b/src/library/scala/collection/generic/TraversableClass.scala
@@ -0,0 +1,23 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+// $Id: Traversable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+package scala.collection.generic
+
+trait TraversableClass[+A, +CC[X] <: Traversable[X]] {
+
+  /** The factory companion object that builds instances of class CC */
+
+  def companion: Companion[CC]
+  /** The builder that builds instances of CC[A] */
+
+  protected[this] def newBuilder: Builder[A, CC[A]] = companion.newBuilder[A]
+
+  /** The generic builder that builds instances of CC at arbitrary element types. */
+  def traversableBuilder[B]: Builder[B, CC[B]] = companion.newBuilder[B]
+}
+
diff --git a/src/library/scala/collection/generic/TraversableFactory.scala b/src/library/scala/collection/generic/TraversableFactory.scala
index e1d4f4bc24..d8afe73d02 100644
--- a/src/library/scala/collection/generic/TraversableFactory.scala
+++ b/src/library/scala/collection/generic/TraversableFactory.scala
@@ -2,20 +2,11 @@
 
 /** A template for companion objects of Traversable and subclasses thereof.
  */
-abstract class TraversableFactory[CC[A] <: Traversable[A]] {
+abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[X, CC]]
+  extends Companion[CC] {
 
-  /** The builder for this kind of collection.
-   */
-  def newBuilder[A]: Builder[A, CC[A]]
-
- /** The empty iterable of type CC */
-  def empty[A]:  CC[A] = newBuilder[A].result
-
-  /** Creates an iterable of type CC with specified elements */
-  def apply[A](args: A*): CC[A] = {
-    val b = newBuilder[A]
-    b ++= Iterable.fromOld(args)
-    b.result
+  class VirtualBuilderFactory[A] extends BuilderFactory[A, CC[A], CC[_]] {
+    def apply(from: Coll) = from.traversableBuilder[A]
   }
 
   /** Concatenate all the argument collections into a single collection.
diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala
index f3bfffff81..01c0d78b53 100644
--- a/src/library/scala/collection/immutable/BitSet.scala
+++ b/src/library/scala/collection/immutable/BitSet.scala
@@ -11,14 +11,16 @@
 
 package scala.collection.immutable
 
-import BitSet._
 import generic._
 import BitSetTemplate.{LogWL, updateArray}
 
 /** a base class for immutable bit sets
  */
-abstract class BitSet extends Set[Int] with collection.BitSet with BitSetTemplate[BitSet] {
+abstract class BitSet extends Set[Int]
+                         with collection.BitSet
+                         with BitSetTemplate[BitSet] {
   override def empty = BitSet.empty
+
   def fromArray(elems: Array[Long]): BitSet = BitSet.fromArray(elems)
 
   /** Update word at index `idx`; enlarge set if `idx` outside range of set
@@ -48,13 +50,12 @@ abstract class BitSet extends Set[Int] with collection.BitSet with BitSetTemplat
 }
 
 /** A factory object for bitsets */
-object BitSet {
+object BitSet extends BitSetFactory[BitSet] {
 
   /** The empty bitset */
   val empty: BitSet = new BitSet1(0L)
 
-  /** A bitset containing given elements */
-  def apply(elems: Int*) = (empty /: elems) (_ + _)
+  implicit def builderFactory: BuilderFactory[Int, BitSet, BitSet] = bitsetBuilderFactory
 
   /** A bitset containing all the bits in an array */
   def fromArray(elems: Array[Long]): BitSet = {
diff --git a/src/library/scala/collection/immutable/FlexMap.scala b/src/library/scala/collection/immutable/FlexMap.scala
deleted file mode 100644
index 8370acd07c..0000000000
--- a/src/library/scala/collection/immutable/FlexMap.scala
+++ /dev/null
@@ -1,144 +0,0 @@
-/*                     __                                               *\
-**     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
-**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
-** /____/\___/_/ |_/____/_/ | |                                         **
-**                          |/                                          **
-\*                                                                      */
-
-// $Id: Map.scala 16893 2009-01-13 13:09:22Z cunei $
-
-
-package scala.collection.immutable
-
-import generic._
-
-/** A default implementation of immutable maps.
- *  This is implemented by specialized implementations
- *  `EmptyMap`, Map1, ..., Map4, for maps of size up to 4, and
- *  a proxy for an immutable HashMap for larger maps.
- */
-trait FlexMap[A, +B] extends Map[A, B] { self =>
-  override def empty: Map[A, B] = FlexMap.empty
-  def + [B1 >: B] (kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
-}
-
-/* Factory object for `FlexMap class */
-object FlexMap extends ImmutableMapFactory[Map] {
-  def empty[A, B]: FlexMap[A, B] = new EmptyMap[A, B]
-
-  @serializable
-  class EmptyMap[A, +B] extends FlexMap[A, B] {
-    override def size: Int = 0
-    def get(key: A): Option[B] = None
-    def elements: Iterator[(A, B)] = Iterator.empty
-    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = new Map1(key, value)
-    def - (key: A): Map[A, B] = this
-  }
-
-  @serializable
-  class Map1[A, +B](key1: A, value1: B) extends FlexMap[A, B] {
-    override def size = 1
-    def get(key: A): Option[B] =
-      if (key == key1) Some(value1) else None
-    def elements = Iterator((key1, value1))
-    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
-      if (key == key1) new Map1(key1, value)
-      else new Map2(key1, value1, key, value)
-    def - (key: A): Map[A, B] =
-      if (key == key1) empty else this
-    override def foreach[U](f: ((A, B)) =>  U): Unit = {
-      f((key1, value1))
-    }
-  }
-
-  @serializable
-  class Map2[A, +B](key1: A, value1: B, key2: A, value2: B) extends FlexMap[A, B] {
-    override def size = 2
-    def get(key: A): Option[B] =
-      if (key == key1) Some(value1)
-      else if (key == key2) Some(value2)
-      else None
-    def elements = Iterator((key1, value1), (key2, value2))
-    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
-      if (key == key1) new Map2(key1, value, key2, value2)
-      else if (key == key2) new Map2(key1, value1, key2, value)
-      else new Map3(key1, value1, key2, value2, key, value)
-    def - (key: A): Map[A, B] =
-      if (key == key1) new Map1(key2, value2)
-      else if (key == key2) new Map1(key1, value1)
-      else this
-    override def foreach[U](f: ((A, B)) =>  U): Unit = {
-      f((key1, value1)); f((key2, value2))
-    }
-  }
-
-  @serializable
-  class Map3[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends FlexMap[A, B] {
-    override def size = 3
-    def get(key: A): Option[B] =
-      if (key == key1) Some(value1)
-      else if (key == key2) Some(value2)
-      else if (key == key3) Some(value3)
-      else None
-    def elements = Iterator((key1, value1), (key2, value2), (key3, value3))
-    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
-      if (key == key1)      new Map3(key1, value, key2, value2, key3, value3)
-      else if (key == key2) new Map3(key1, value1, key2, value, key3, value3)
-      else if (key == key3) new Map3(key1, value1, key2, value2, key3, value)
-      else new Map4(key1, value1, key2, value2, key3, value3, key, value)
-    def - (key: A): Map[A, B] =
-      if (key == key1)      new Map2(key2, value2, key3, value3)
-      else if (key == key2) new Map2(key1, value1, key3, value3)
-      else if (key == key3) new Map2(key1, value1, key2, value2)
-      else this
-    override def foreach[U](f: ((A, B)) =>  U): Unit = {
-      f((key1, value1)); f((key2, value2)); f((key3, value3))
-    }
-  }
-
-  @serializable
-  class Map4[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B, key4: A, value4: B) extends FlexMap[A, B] {
-    override def size = 4
-    def get(key: A): Option[B] =
-      if (key == key1) Some(value1)
-      else if (key == key2) Some(value2)
-      else if (key == key3) Some(value3)
-      else if (key == key4) Some(value4)
-      else None
-    def elements = Iterator((key1, value1), (key2, value2), (key3, value3), (key4, value4))
-    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
-      if (key == key1)      new Map4(key1, value, key2, value2, key3, value3, key4, value4)
-      else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4)
-      else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4)
-      else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value)
-      else new HashMap + ((key1, value1), (key2, value2), (key3, value3), (key4, value4), (key, value))
-    def - (key: A): Map[A, B] =
-      if (key == key1)      new Map3(key2, value2, key3, value3, key4, value4)
-      else if (key == key2) new Map3(key1, value1, key3, value3, key4, value4)
-      else if (key == key3) new Map3(key1, value1, key2, value2, key4, value4)
-      else if (key == key4) new Map3(key1, value1, key2, value2, key3, value3)
-      else this
-    override def foreach[U](f: ((A, B)) =>  U): Unit = {
-      f((key1, value1)); f((key2, value2)); f((key3, value3)); f((key4, value4))
-    }
-  }
-}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
diff --git a/src/library/scala/collection/immutable/FlexSet.scala b/src/library/scala/collection/immutable/FlexSet.scala
deleted file mode 100644
index 37082a4407..0000000000
--- a/src/library/scala/collection/immutable/FlexSet.scala
+++ /dev/null
@@ -1,120 +0,0 @@
-/*                     __                                               *\
-**     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
-**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
-** /____/\___/_/ |_/____/_/ | |                                         **
-**                          |/                                          **
-\*                                                                      */
-
-// $Id: HashSet.scala 16884 2009-01-09 16:52:09Z cunei $
-
-package scala.collection.immutable
-
-import generic._
-
-/** A default implementation of immutable sets.
- *  This is implemented by specialized implementations
- *  `EmptySet`, Set1, ..., Set4, for sets of size up to 4, and
- *  a proxy for an immutable HashSet for larger sets.
- */
-trait FlexSet[A] extends Set[A] { self =>
-  override def empty = FlexSet.empty
-}
-
-/* Factory object for `FlexSet` class */
-object FlexSet extends SetFactory[Set] {
-  def empty[A]: FlexSet[A] = new EmptySet[A]
-
-  /** An optimized representation for immutable empty sets */
-  @serializable
-  class EmptySet[A] extends FlexSet[A] {
-    override def size: Int = 0
-    def contains(elem: A): Boolean = false
-    def + (elem: A): Set[A] = new Set1(elem)
-    def - (elem: A): Set[A] = this
-    def elements: Iterator[A] = Iterator.empty
-    override def foreach[U](f: A =>  U): Unit = {}
-  }
-
-  /** An optimized representation for immutable sets of size 1 */
-  @serializable
-  class Set1[A](elem1: A) extends FlexSet[A] {
-    override def size: Int = 1
-    def contains(elem: A): Boolean =
-      elem == elem1
-    def + (elem: A): Set[A] =
-      if (contains(elem)) this
-      else new Set2(elem1, elem)
-    def - (elem: A): Set[A] =
-      if (elem == elem1) new EmptySet[A]
-      else this
-    def elements: Iterator[A] =
-      Iterator(elem1)
-    override def foreach[U](f: A =>  U): Unit = {
-      f(elem1)
-    }
-  }
-
-  /** An optimized representation for immutable sets of size 2 */
-  @serializable
-  class Set2[A](elem1: A, elem2: A) extends FlexSet[A] {
-    override def size: Int = 2
-    def contains(elem: A): Boolean =
-      elem == elem1 || elem == elem2
-    def + (elem: A): Set[A] =
-      if (contains(elem)) this
-      else new Set3(elem1, elem2, elem)
-    def - (elem: A): Set[A] =
-      if (elem == elem1) new Set1(elem2)
-      else if (elem == elem2) new Set1(elem1)
-      else this
-    def elements: Iterator[A] =
-      Iterator(elem1, elem2)
-    override def foreach[U](f: A =>  U): Unit = {
-      f(elem1); f(elem2)
-    }
-  }
-
-  /** An optimized representation for immutable sets of size 3 */
-  @serializable
-  class Set3[A](elem1: A, elem2: A, elem3: A) extends FlexSet[A] {
-    override def size: Int = 3
-    def contains(elem: A): Boolean =
-      elem == elem1 || elem == elem2 || elem == elem3
-    def + (elem: A): Set[A] =
-      if (contains(elem)) this
-      else new Set4(elem1, elem2, elem3, elem)
-    def - (elem: A): Set[A] =
-      if (elem == elem1) new Set2(elem2, elem3)
-      else if (elem == elem2) new Set2(elem1, elem3)
-      else if (elem == elem3) new Set2(elem1, elem2)
-      else this
-    def elements: Iterator[A] =
-      Iterator(elem1, elem2, elem3)
-    override def foreach[U](f: A =>  U): Unit = {
-      f(elem1); f(elem2); f(elem3)
-    }
-  }
-
-  /** An optimized representation for immutable sets of size 4 */
-  @serializable
-  class Set4[A](elem1: A, elem2: A, elem3: A, elem4: A) extends FlexSet[A] {
-    override def size: Int = 4
-    def contains(elem: A): Boolean =
-      elem == elem1 || elem == elem2 || elem == elem3 || elem == elem4
-    def + (elem: A): Set[A] =
-      if (contains(elem)) this
-      else new HashSet[A] + (elem1, elem2, elem3, elem4, elem)
-    def - (elem: A): Set[A] =
-      if (elem == elem1) new Set3(elem2, elem3, elem4)
-      else if (elem == elem2) new Set3(elem1, elem3, elem4)
-      else if (elem == elem3) new Set3(elem1, elem2, elem4)
-      else if (elem == elem4) new Set3(elem1, elem2, elem3)
-      else this
-    def elements: Iterator[A] =
-      Iterator(elem1, elem2, elem3, elem4)
-    override def foreach[U](f: A =>  U): Unit = {
-      f(elem1); f(elem2); f(elem3); f(elem4)
-    }
-  }
-}
diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index 7979d096aa..351cbf60d8 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -37,7 +37,6 @@ class HashMap[A, +B] extends Map[A,B] with ImmutableMapTemplate[A, B, HashMap[A,
   protected var deltaSize: Int = _
 
   override def empty = HashMap.empty[A, B]
-  override def mapBuilder[A, B]: Builder[(A, B), HashMap[A, B]] = HashMap.newBuilder[A, B]
 
   def get(key: A): Option[B] = synchronized {
     var m: HashMap[A, _ >: B] = this
@@ -176,8 +175,7 @@ class HashMap[A, +B] extends Map[A,B] with ImmutableMapTemplate[A, B, HashMap[A,
  *  @version 2.8
  */
 object HashMap extends ImmutableMapFactory[HashMap] {
-  type Coll = HashMap[_, _]
-  implicit def builderFactory[A, B]: BuilderFactory[(A, B), HashMap[A, B], Coll] = new BuilderFactory[(A, B), HashMap[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] }
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), HashMap[A, B], Coll] = new MapBuilderFactory[A, B]
   def empty[A, B]: HashMap[A, B] = new HashMap
 }
 
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index 3abffa6ec4..86efa9c6c6 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -25,10 +25,11 @@ import generic._
  *  @version 2.8
  */
 @serializable
-class HashSet[A] extends Set[A] with SetTemplate[A, HashSet[A]] with mutable.FlatHashTable[A] {
-
-  override def empty = HashSet.empty
-  override def traversableBuilder[B]: Builder[B, HashSet[B]] = HashSet.newBuilder[B]
+class HashSet[A] extends Set[A]
+                    with SetClass[A, HashSet]
+                    with SetTemplate[A, HashSet[A]]
+                    with mutable.FlatHashTable[A] {
+  override def companion: Companion[HashSet] = HashSet
 
   protected var later: HashSet[A] = null
   protected var changedElem: A = _
@@ -131,8 +132,7 @@ class HashSet[A] extends Set[A] with SetTemplate[A, HashSet[A]] with mutable.Fla
   *  @version 2.8
   */
 object HashSet extends SetFactory[HashSet] {
-  type Coll = HashSet[_]
-  implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = new BuilderFactory[A, HashSet[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
-  def empty[A]: HashSet[A] = new HashSet
+  implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = setBuilderFactory[A]
+  override def empty[A]: HashSet[A] = new HashSet
 }
 
diff --git a/src/library/scala/collection/immutable/Iterable.scala b/src/library/scala/collection/immutable/Iterable.scala
index 60f77bdc6f..bcc3951965 100644
--- a/src/library/scala/collection/immutable/Iterable.scala
+++ b/src/library/scala/collection/immutable/Iterable.scala
@@ -9,15 +9,16 @@ import generic._
  *  @autor   Martin Odersky
  *  @version 2.8
  */
-trait Iterable[+A] extends Traversable[A] with collection.Iterable[A] with IterableTemplate[A, Iterable[A]] { self =>
-  override protected[this] def newBuilder = Iterable.newBuilder
-  override def traversableBuilder[B]: Builder[B, Iterable[B]] = Iterable.newBuilder[B]
+trait Iterable[+A] extends Traversable[A]
+                      with collection.Iterable[A]
+                      with TraversableClass[A, Iterable]
+                      with IterableTemplate[A, Iterable[A]] {
+  override def companion: Companion[Iterable] = Iterable
 }
 
 /* A factory object for the trait `Iterable` */
 object Iterable extends TraversableFactory[Iterable] {
-  type Coll = Iterable[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new BuilderFactory[A, Iterable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Iterable[A]] = new mutable.ListBuffer
 }
 
diff --git a/src/library/scala/collection/immutable/LinearSequence.scala b/src/library/scala/collection/immutable/LinearSequence.scala
index 36e9a50428..6a9665e705 100644
--- a/src/library/scala/collection/immutable/LinearSequence.scala
+++ b/src/library/scala/collection/immutable/LinearSequence.scala
@@ -5,13 +5,14 @@ import generic._
 /** A subtrait of collection.Sequence which represents sequences
  *  that cannot be mutated.
  */
-trait LinearSequence[+A] extends Sequence[A] with collection.LinearSequence[A] with LinearSequenceTemplate[A, LinearSequence[A]] {
-  override protected[this] def newBuilder = LinearSequence.newBuilder
-  override def traversableBuilder[B]: Builder[B, LinearSequence[B]] = LinearSequence.newBuilder[B]
+trait LinearSequence[+A] extends Sequence[A]
+                            with collection.LinearSequence[A]
+                            with TraversableClass[A, LinearSequence]
+                            with LinearSequenceTemplate[A, LinearSequence[A]] {
+  override def companion: Companion[LinearSequence] = LinearSequence
 }
 
 object LinearSequence extends SequenceFactory[LinearSequence] {
-  type Coll = LinearSequence[_]
-  implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new BuilderFactory[A, LinearSequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, LinearSequence[A]] = new mutable.ListBuffer
 }
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index e715fad0fa..acfbdc531f 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -12,7 +12,7 @@
 package scala.collection.immutable
 
 import mutable.ListBuffer
-import generic.{SequenceFactory, Builder, BuilderFactory, LinearSequenceTemplate}
+import generic._
 
 /** A class representing an ordered collection of elements of type
  *  <code>a</code>. This class comes with two implementing case
@@ -23,7 +23,11 @@ import generic.{SequenceFactory, Builder, BuilderFactory, LinearSequenceTemplate
  *  @author  Martin Odersky and others
  *  @version 2.8
  */
-sealed abstract class List[+A] extends LinearSequence[A] with Product with LinearSequenceTemplate[A, List[A]] {
+sealed abstract class List[+A] extends LinearSequence[A]
+                                  with Product
+                                  with TraversableClass[A, List]
+                                  with LinearSequenceTemplate[A, List[A]] {
+  override def companion: Companion[List] = List
 
   import collection.{Iterable, Traversable, Sequence, Vector}
 
@@ -46,10 +50,6 @@ sealed abstract class List[+A] extends LinearSequence[A] with Product with Linea
    */
   def tail: List[A]
 
-  /** Creates a list buffer as builder for this class */
-  override protected[this] def newBuilder = List.newBuilder
-  override def traversableBuilder[B]: Builder[B, List[B]] = List.newBuilder[B]
-
   // New methods in List
 
   /** <p>
@@ -488,8 +488,7 @@ object List extends SequenceFactory[List] {
 
   import collection.{Iterable, Sequence, Vector}
 
-  type Coll = List[_]
-  implicit def builderFactory[A]: BuilderFactory[A, List[A], Coll] = new BuilderFactory[A, List[A], Coll] { def apply(from: Coll) = new ListBuffer[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, List[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, List[A]] = new ListBuffer[A]
 
   override def empty[A]: List[A] = Nil
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index b812cef8df..98aca89049 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -16,9 +16,7 @@ import generic._
 
 /** The canonical factory of <a href="ListMap.html">ListMap</a>'s */
 object ListMap extends ImmutableMapFactory[ListMap] {
-
-  type Coll = ListMap[_,_]
-  implicit def builderFactory[A, B]: BuilderFactory[(A, B), ListMap[A, B], Coll] = new BuilderFactory[(A, B), ListMap[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] }
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), ListMap[A, B], Coll] = new MapBuilderFactory[A, B]
   def empty[A, B]: ListMap[A, B] = new ListMap
 }
 
@@ -35,7 +33,6 @@ object ListMap extends ImmutableMapFactory[ListMap] {
 class ListMap[A, +B] extends Map[A, B] with ImmutableMapTemplate[A, B, ListMap[A, B]] {
 
   override def empty = ListMap.empty
-  override def mapBuilder[A, B]: Builder[(A, B), ListMap[A, B]] = ListMap.newBuilder[A, B]
 
   /** Returns the number of mappings in this map.
    *
diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala
index 6257e8c9cc..210413171b 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -15,9 +15,8 @@ import generic._
 
 /** The canonical factory of <a href="ListSet.html">ListSet</a>'s */
 object ListSet extends SetFactory[ListSet] {
-  type Coll = ListSet[_]
-  implicit def builderFactory[A]: BuilderFactory[A, ListSet[A], Coll] = new BuilderFactory[A, ListSet[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
-  def empty[A] = new ListSet[A]
+  implicit def builderFactory[A]: BuilderFactory[A, ListSet[A], Coll] = setBuilderFactory[A]
+  override def empty[A] = new ListSet[A]
 }
 
 
@@ -30,19 +29,18 @@ object ListSet extends SetFactory[ListSet] {
  *  @version 1.0, 09/07/2003
  */
 @serializable
-class ListSet[A] extends Set[A] with SetTemplate[A, ListSet[A]] { self =>
+class ListSet[A] extends Set[A]
+                    with SetClass[A, ListSet]
+                    with SetTemplate[A, ListSet[A]] { self =>
+  override def companion: Companion[ListSet] = ListSet
 
   /** Returns the number of elements in this set.
    *
    *  @return number of set elements.
    */
   override def size: Int = 0
-
   override def isEmpty: Boolean = true;
 
-  override def empty = ListSet.empty
-  override def traversableBuilder[B]: Builder[B, ListSet[B]] = ListSet.newBuilder[B]
-
   /** Checks if this set contains element <code>elem</code>.
    *
    *  @param  elem    the element to check for membership.
diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala
index 8a1325735f..103d8f3d5a 100644
--- a/src/library/scala/collection/immutable/Map.scala
+++ b/src/library/scala/collection/immutable/Map.scala
@@ -18,7 +18,6 @@ trait Map[A, +B] extends Iterable[(A, B)]
                     with ImmutableMapTemplate[A, B, Map[A, B]] { self =>
 
   override def empty: Map[A, B] = Map.empty
-  override def mapBuilder[A, B]: Builder[(A, B), Map[A, B]] = Map.newBuilder[A, B]
 
   /** Add a key/value pair to this map.
    *  @param    key the key
@@ -33,7 +32,6 @@ trait Map[A, +B] extends Iterable[(A, B)]
   override def hashCode() =
     (Map.hashSeed /: this) (_ * 41 + _.hashCode)
 
-
   /** The same map with a given default function !!! todo: move to general maps? */
   def withDefault[B1 >: B](d: A => B1): Map[A, B1] = new Map.WithDefault[A, B1](this, d)
 
@@ -43,10 +41,9 @@ trait Map[A, +B] extends Iterable[(A, B)]
 
 object Map extends ImmutableMapFactory[Map] {
   private val hashSeed = "Map".hashCode
-  type Coll = Map[_, _]
-  implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new BuilderFactory[(A, B), Map[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] }
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new MapBuilderFactory[A, B]
 
-  def empty[A, B]: Map[A, B] = FlexMap.empty
+  def empty[A, B]: Map[A, B] = new EmptyMap[A, B]
 
   class WithDefault[A, +B](underlying: Map[A, B], d: A => B) extends Map[A, B] {
     override def size = underlying.size
@@ -58,5 +55,107 @@ object Map extends ImmutableMapFactory[Map] {
     def - (key: A): WithDefault[A, B] = new WithDefault(underlying - key, d)
     override def default(key: A): B = d(key)
   }
+
+  @serializable
+  class EmptyMap[A, +B] extends Map[A, B] {
+    override def size: Int = 0
+    def get(key: A): Option[B] = None
+    def elements: Iterator[(A, B)] = Iterator.empty
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = new Map1(key, value)
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] = this
+  }
+
+  @serializable
+  class Map1[A, +B](key1: A, value1: B) extends Map[A, B] {
+    override def size = 1
+    def get(key: A): Option[B] =
+      if (key == key1) Some(value1) else None
+    def elements = Iterator((key1, value1))
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
+      if (key == key1) new Map1(key1, value)
+      else new Map2(key1, value1, key, value)
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] =
+      if (key == key1) empty else this
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      f((key1, value1))
+    }
+  }
+
+  @serializable
+  class Map2[A, +B](key1: A, value1: B, key2: A, value2: B) extends Map[A, B] {
+    override def size = 2
+    def get(key: A): Option[B] =
+      if (key == key1) Some(value1)
+      else if (key == key2) Some(value2)
+      else None
+    def elements = Iterator((key1, value1), (key2, value2))
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
+      if (key == key1) new Map2(key1, value, key2, value2)
+      else if (key == key2) new Map2(key1, value1, key2, value)
+      else new Map3(key1, value1, key2, value2, key, value)
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] =
+      if (key == key1) new Map1(key2, value2)
+      else if (key == key2) new Map1(key1, value1)
+      else this
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      f((key1, value1)); f((key2, value2))
+    }
+  }
+
+  @serializable
+  class Map3[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends Map[A, B] {
+    override def size = 3
+    def get(key: A): Option[B] =
+      if (key == key1) Some(value1)
+      else if (key == key2) Some(value2)
+      else if (key == key3) Some(value3)
+      else None
+    def elements = Iterator((key1, value1), (key2, value2), (key3, value3))
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
+      if (key == key1)      new Map3(key1, value, key2, value2, key3, value3)
+      else if (key == key2) new Map3(key1, value1, key2, value, key3, value3)
+      else if (key == key3) new Map3(key1, value1, key2, value2, key3, value)
+      else new Map4(key1, value1, key2, value2, key3, value3, key, value)
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] =
+      if (key == key1)      new Map2(key2, value2, key3, value3)
+      else if (key == key2) new Map2(key1, value1, key3, value3)
+      else if (key == key3) new Map2(key1, value1, key2, value2)
+      else this
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      f((key1, value1)); f((key2, value2)); f((key3, value3))
+    }
+  }
+
+  @serializable
+  class Map4[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B, key4: A, value4: B) extends Map[A, B] {
+    override def size = 4
+    def get(key: A): Option[B] =
+      if (key == key1) Some(value1)
+      else if (key == key2) Some(value2)
+      else if (key == key3) Some(value3)
+      else if (key == key4) Some(value4)
+      else None
+    def elements = Iterator((key1, value1), (key2, value2), (key3, value3), (key4, value4))
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
+      if (key == key1)      new Map4(key1, value, key2, value2, key3, value3, key4, value4)
+      else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4)
+      else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4)
+      else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value)
+      else new HashMap + ((key1, value1), (key2, value2), (key3, value3), (key4, value4), (key, value))
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] =
+      if (key == key1)      new Map3(key2, value2, key3, value3, key4, value4)
+      else if (key == key2) new Map3(key1, value1, key3, value3, key4, value4)
+      else if (key == key3) new Map3(key1, value1, key2, value2, key4, value4)
+      else if (key == key4) new Map3(key1, value1, key2, value2, key3, value3)
+      else this
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      f((key1, value1)); f((key2, value2)); f((key3, value3)); f((key4, value4))
+    }
+  }
 }
 
diff --git a/src/library/scala/collection/immutable/Sequence.scala b/src/library/scala/collection/immutable/Sequence.scala
index 565937335f..715cabb705 100644
--- a/src/library/scala/collection/immutable/Sequence.scala
+++ b/src/library/scala/collection/immutable/Sequence.scala
@@ -12,15 +12,17 @@ import generic._
 /** A subtrait of collection.Sequence which represents sequences
  *  that cannot be mutated.
  */
-trait Sequence[+A] extends Iterable[A] with collection.Sequence[A] with SequenceTemplate[A, Sequence[A]] {
-  override protected[this] def newBuilder = Sequence.newBuilder
-  override def traversableBuilder[B]: Builder[B, Sequence[B]] = Sequence.newBuilder[B]
+trait Sequence[+A] extends Iterable[A]
+                      with collection.Sequence[A]
+                      with TraversableClass[A, Sequence]
+                      with SequenceTemplate[A, Sequence[A]] {
+  override def companion: Companion[Sequence] = Sequence
+
   override def hashCode = (Sequence.hashSeed /: this)(_ * 41 + _.hashCode)
 }
 
 object Sequence extends SequenceFactory[Sequence] {
   private val hashSeed = "Sequence".hashCode
-  type Coll = Sequence[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new BuilderFactory[A, Sequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Sequence[A]] = new mutable.ListBuffer
 }
diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala
index 315f658542..78aaa54f1c 100644
--- a/src/library/scala/collection/immutable/Set.scala
+++ b/src/library/scala/collection/immutable/Set.scala
@@ -13,21 +13,125 @@ package scala.collection.immutable
 
 import generic._
 
-/** A generic trait for immutable sets
+/** A generic trait for immutable sets. Concrete set implementations
+ *  have to provide functionality for the abstract methods in Set:
+ *
+ *  def contains(elem: A): Boolean
+ *  def elements: Iterator[A]
+ *  def + (elem: A): This
+ *  def - (elem: A): This
+ *
+ *  where `This` is the type of the set
+ *
+ *  @author Matthias Zenger
+ *  @author Martin Odersky
+ *  @version 2.8
  */
-trait Set[A] extends Iterable[A] with collection.Set[A] with SetTemplate[A, Set[A]] { self =>
-
-  override def empty = Set.empty
-
+trait Set[A] extends Iterable[A]
+                with collection.Set[A]
+                with SetClass[A, Set]
+                with SetTemplate[A, Set[A]] {
+  override def companion: Companion[Set] = Set
   override def hashCode = (Set.hashSeed /: this)(_ * 41 + _.hashCode)
-
-  override def traversableBuilder[B]: Builder[B, Set[B]] = Set.newBuilder[B]
 }
 
 object Set extends SetFactory[Set] {
+  implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = setBuilderFactory[A]
+  override def empty[A]: Set[A] = new EmptySet[A]
+
   private val hashSeed = "Set".hashCode
-  type Coll = Set[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = new BuilderFactory[A, Set[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
-  def empty[A]: Set[A] = FlexSet.empty
+
+  /** An optimized representation for immutable empty sets */
+  @serializable
+  class EmptySet[A] extends Set[A] {
+    override def size: Int = 0
+    def contains(elem: A): Boolean = false
+    def + (elem: A): Set[A] = new Set1(elem)
+    def - (elem: A): Set[A] = this
+    def elements: Iterator[A] = Iterator.empty
+    override def foreach[U](f: A =>  U): Unit = {}
+  }
+
+  /** An optimized representation for immutable sets of size 1 */
+  @serializable
+  class Set1[A](elem1: A) extends Set[A] {
+    override def size: Int = 1
+    def contains(elem: A): Boolean =
+      elem == elem1
+    def + (elem: A): Set[A] =
+      if (contains(elem)) this
+      else new Set2(elem1, elem)
+    def - (elem: A): Set[A] =
+      if (elem == elem1) new EmptySet[A]
+      else this
+    def elements: Iterator[A] =
+      Iterator(elem1)
+    override def foreach[U](f: A =>  U): Unit = {
+      f(elem1)
+    }
+  }
+
+  /** An optimized representation for immutable sets of size 2 */
+  @serializable
+  class Set2[A](elem1: A, elem2: A) extends Set[A] {
+    override def size: Int = 2
+    def contains(elem: A): Boolean =
+      elem == elem1 || elem == elem2
+    def + (elem: A): Set[A] =
+      if (contains(elem)) this
+      else new Set3(elem1, elem2, elem)
+    def - (elem: A): Set[A] =
+      if (elem == elem1) new Set1(elem2)
+      else if (elem == elem2) new Set1(elem1)
+      else this
+    def elements: Iterator[A] =
+      Iterator(elem1, elem2)
+    override def foreach[U](f: A =>  U): Unit = {
+      f(elem1); f(elem2)
+    }
+  }
+
+  /** An optimized representation for immutable sets of size 3 */
+  @serializable
+  class Set3[A](elem1: A, elem2: A, elem3: A) extends Set[A] {
+    override def size: Int = 3
+    def contains(elem: A): Boolean =
+      elem == elem1 || elem == elem2 || elem == elem3
+    def + (elem: A): Set[A] =
+      if (contains(elem)) this
+      else new Set4(elem1, elem2, elem3, elem)
+    def - (elem: A): Set[A] =
+      if (elem == elem1) new Set2(elem2, elem3)
+      else if (elem == elem2) new Set2(elem1, elem3)
+      else if (elem == elem3) new Set2(elem1, elem2)
+      else this
+    def elements: Iterator[A] =
+      Iterator(elem1, elem2, elem3)
+    override def foreach[U](f: A =>  U): Unit = {
+      f(elem1); f(elem2); f(elem3)
+    }
+  }
+
+  /** An optimized representation for immutable sets of size 4 */
+  @serializable
+  class Set4[A](elem1: A, elem2: A, elem3: A, elem4: A) extends Set[A] {
+    override def size: Int = 4
+    def contains(elem: A): Boolean =
+      elem == elem1 || elem == elem2 || elem == elem3 || elem == elem4
+    def + (elem: A): Set[A] =
+      if (contains(elem)) this
+      else new HashSet[A] + (elem1, elem2, elem3, elem4, elem)
+    def - (elem: A): Set[A] =
+      if (elem == elem1) new Set3(elem2, elem3, elem4)
+      else if (elem == elem2) new Set3(elem1, elem3, elem4)
+      else if (elem == elem3) new Set3(elem1, elem2, elem4)
+      else if (elem == elem4) new Set3(elem1, elem2, elem3)
+      else this
+    def elements: Iterator[A] =
+      Iterator(elem1, elem2, elem3, elem4)
+    override def foreach[U](f: A =>  U): Unit = {
+      f(elem1); f(elem2); f(elem3); f(elem4)
+    }
+  }
 }
 
diff --git a/src/library/scala/collection/immutable/SortedMap.scala b/src/library/scala/collection/immutable/SortedMap.scala
index 43a7562f84..2ce558fa00 100644
--- a/src/library/scala/collection/immutable/SortedMap.scala
+++ b/src/library/scala/collection/immutable/SortedMap.scala
@@ -25,12 +25,8 @@ trait SortedMap[A, +B] extends Map[A, B]
                          with ImmutableMapTemplate[A, B, SortedMap[A, B]]
                          with SortedMapTemplate[A, B, SortedMap[A, B]] {
 
-  /** Needs to be overridden in subclasses. */
-  override def empty: SortedMap[A, B] = throw new AbstractMethodError("SortedMap.empty")
-
-  /** Needs to be overridden in subclasses. */
   override protected[this] def newBuilder : Builder[(A, B), SortedMap[A, B]] =
-    throw new AbstractMethodError("SortedMap.newBuilder")
+    immutable.SortedMap.newBuilder[A, B]
 
   override def updated [B1 >: B](key: A, value: B1): SortedMap[A, B1] = this + ((key, value))
 
@@ -109,3 +105,7 @@ trait SortedMap[A, +B] extends Map[A, B]
   override def plusAll [B1 >: B](iter: Iterator[(A, B1)]): SortedMap[A, B1] = this.++(iter)
 }
 
+object SortedMap extends ImmutableSortedMapFactory[SortedMap] {
+  implicit def builderFactory[A, B](implicit ord: Ordering[A]): BuilderFactory[(A, B), SortedMap[A, B], Coll] = new SortedMapBuilderFactory[A, B]
+  def empty[A, B](implicit ord: Ordering[A]): SortedMap[A, B] = TreeMap.empty[A, B]
+}
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala
index 5e678edddf..7ac6b78bf4 100644
--- a/src/library/scala/collection/immutable/Stream.scala
+++ b/src/library/scala/collection/immutable/Stream.scala
@@ -12,7 +12,7 @@
 package scala.collection.immutable
 
 import mutable.ListBuffer
-import generic.{SequenceFactory, Builder, BuilderFactory, LazyBuilder, LinearSequenceTemplate}
+import generic._
 
 /**
  * <p>The class <code>Stream</code> implements lazy lists where elements
@@ -35,8 +35,12 @@ import generic.{SequenceFactory, Builder, BuilderFactory, LazyBuilder, LinearSeq
  * @author Martin Odersky, Matthias Zenger
  * @version 1.1 08/08/03
  */
-abstract class Stream[+A] extends LinearSequence[A] with LinearSequenceTemplate[A, Stream[A]] {
+abstract class Stream[+A] extends LinearSequence[A]
+                             with TraversableClass[A, Stream]
+                             with LinearSequenceTemplate[A, Stream[A]] {
 self =>
+  override def companion: Companion[Stream] = Stream
+
   import collection.{Traversable, Iterable, Sequence, Vector}
 
   /** is this stream empty? */
@@ -57,14 +61,6 @@ self =>
 
   // Implementation of abstract method in Traversable
 
-  /** The builder for stream objects.
-   *  @note: This builder is lazy only in the sense that it does not go downs the spine
-   *         of traversables taht are added as a whole. If more layzness can be achieved,
-   *         this builder should be bypassed.
-   */
-  override protected[this] def newBuilder = Stream.newBuilder
-  override def traversableBuilder[B]: Builder[B, Stream[B]] = Stream.newBuilder[B]
-
   // New methods in Stream
 
   /** The stream resulting from the concatenation of this stream with the argument stream.
@@ -367,8 +363,8 @@ self =>
  */
 object Stream extends SequenceFactory[Stream] {
 
-  type Coll = Stream[_]
-  class StreamBuilderFactory[A] extends BuilderFactory[A, Stream[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  class StreamBuilderFactory[A] extends VirtualBuilderFactory[A]
+
   implicit def builderFactory[A]: BuilderFactory[A, Stream[A], Coll] = new StreamBuilderFactory[A]
 
   /** Creates a new builder for a stream */
@@ -377,6 +373,9 @@ object Stream extends SequenceFactory[Stream] {
   import collection.{Iterable, Sequence, Vector}
 
   /** A builder for streams
+   *  @note: This builder is lazy only in the sense that it does not go downs the spine
+   *         of traversables taht are added as a whole. If more layzness can be achieved,
+   *         this builder should be bypassed.
    */
   class StreamBuilder[A] extends LazyBuilder[A, Stream[A]] {
     def result: Stream[A] = (for (xs <- parts.elements; x <- xs.toIterable.elements) yield x).toStream
diff --git a/src/library/scala/collection/immutable/Traversable.scala b/src/library/scala/collection/immutable/Traversable.scala
index 302115a6d6..ffb389212b 100644
--- a/src/library/scala/collection/immutable/Traversable.scala
+++ b/src/library/scala/collection/immutable/Traversable.scala
@@ -9,15 +9,16 @@ import generic._
  *  @autor   Martin Odersky
  *  @version 2.8
  */
-trait Traversable[+A] extends collection.Traversable[A] with TraversableTemplate[A, Traversable[A]] with Immutable { self =>
-  override protected[this] def newBuilder = Traversable.newBuilder
-  override def traversableBuilder[B]: Builder[B, Traversable[B]] = Traversable.newBuilder[B]
+trait Traversable[+A] extends collection.Traversable[A]
+                         with TraversableClass[A, Traversable]
+                         with TraversableTemplate[A, Traversable[A]]
+                         with Immutable {
+  override def companion: Companion[Traversable] = Traversable
 }
 
 /* A factory object for the trait `Traversable` */
 object Traversable extends TraversableFactory[Traversable] {
-  type Coll = Traversable[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new BuilderFactory[A, Traversable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Traversable[A]] = new mutable.ListBuffer
 }
 
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index fd596465a0..2298a64ba7 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -8,25 +8,15 @@
 
 // $Id$
 
-// todo: make balanced once Tree.scala is updated to be covariant.
-
 package scala.collection.immutable
 
 import generic._
 
 /** The canonical factory of <a href="TreeMap.html">TreeMap</a>'s. */
-object TreeMap {
-
-  type Coll = TreeMap[_, _]
-  implicit def builderFactory[A <% Ordered[A], B]: BuilderFactory[(A, B), TreeMap[A, B], Coll] = new BuilderFactory[(A, B), TreeMap[A, B], Coll] { def apply(from: Coll) = newBuilder[A, B] }
-  def newBuilder[A <% Ordered[A], B]: Builder[(A, B), TreeMap[A, B]] = new ImmutableMapBuilder(empty[A, B])
-
-  /** The empty map of this type */
-  def empty[A <% Ordered[A], B] = new TreeMap[A, B]
-
-  /** The canonical factory for this type
-   */
-  def apply[A <% Ordered[A], B](elems: (A, B)*) = empty[A, B] ++ elems
+object TreeMap extends ImmutableSortedMapFactory[TreeMap] {
+  def empty[A, B](implicit ord: Ordering[A]) = new TreeMap[A, B]()(ord)
+  implicit def builderFactory[A, B](implicit ord: Ordering[A]): BuilderFactory[(A, B), TreeMap[A, B], Coll] = new SortedMapBuilderFactory[A, B]
+  private def make[A, B](s: Int, t: RedBlack[A]#Tree[B])(implicit ord: Ordering[A]) = new TreeMap[A, B](s, t)(ord)
 }
 
 /** This class implements immutable maps using a tree.
@@ -36,18 +26,18 @@ object TreeMap {
  *  @version 1.1, 03/05/2004
  */
 @serializable
-class TreeMap[A <% Ordered[A], +B](override val size: Int, t: RedBlack[A]#Tree[B])
+class TreeMap[A, +B](override val size: Int, t: RedBlack[A]#Tree[B])(implicit val ordering: Ordering[A])
   extends RedBlack[A]
      with SortedMap[A, B]
      with SortedMapTemplate[A, B, TreeMap[A, B]]
      with ImmutableMapTemplate[A, B, TreeMap[A, B]] {
 
+  def isSmaller(x: A, y: A) = ordering.lt(x, y)
+
   override protected[this] def newBuilder : Builder[(A, B), TreeMap[A, B]] =
     TreeMap.newBuilder[A, B]
 
-  def isSmaller(x: A, y: A) = x < y
-
-  def this() = this(0, null)
+  def this()(implicit ordering: Ordering[A]) = this(0, null)(ordering)
 
   protected val tree: RedBlack[A]#Tree[B] = if (size == 0) Empty else t
 
@@ -58,13 +48,11 @@ class TreeMap[A <% Ordered[A], +B](override val size: Int, t: RedBlack[A]#Tree[B
 
   override def firstKey = t.first
   override def lastKey = t.last
-  override def compare(k0: A, k1: A): Int = k0.compare(k1)
-
-  private def newMap[B](s: Int, t: RedBlack[A]#Tree[B]) = new TreeMap[A, B](s, t)
+  override def compare(k0: A, k1: A): Int = ordering.compare(k0, k1)
 
   /** A factory to create empty maps of the same type of keys.
    */
-  override def empty = TreeMap.empty
+  override def empty: TreeMap[A, B] = TreeMap.empty[A, B](ordering)
 
   /** A new TreeMap with the entry added is returned,
    *  if key is <em>not</em> in the TreeMap, otherwise
@@ -76,7 +64,7 @@ class TreeMap[A <% Ordered[A], +B](override val size: Int, t: RedBlack[A]#Tree[B
    */
   override def updated [B1 >: B](key: A, value: B1): TreeMap[A, B1] = {
     val newsize = if (tree.lookup(key).isEmpty) size + 1 else size
-    newMap(newsize, tree.update(key, value))
+    TreeMap.make(newsize, tree.update(key, value))
   }
 
     /** Add a key/value pair to this map.
@@ -94,19 +82,19 @@ class TreeMap[A <% Ordered[A], +B](override val size: Int, t: RedBlack[A]#Tree[B
    *  @param elems the remaining elements to add.
    */
   override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1) *): TreeMap[A, B1] =
-    this + elem1 + elem2 ++ collection.Iterable.fromOld(elems)
+    this + elem1 + elem2 ++ elems
 
   /** A new TreeMap with the entry added is returned,
    *  assuming that key is <em>not</em> in the TreeMap.
    */
   def insert [B1 >: B](key: A, value: B1): TreeMap[A, B1] = {
     assert(tree.lookup(key).isEmpty)
-    newMap(size + 1, tree.update(key, value))
+    TreeMap.make(size + 1, tree.update(key, value))
   }
 
   def - (key:A): TreeMap[A, B] =
     if (tree.lookup(key).isEmpty) this
-    else newMap(size - 1, tree.delete(key))
+    else TreeMap.make(size - 1, tree.delete(key))
 
   /** Check if this map maps <code>key</code> to a value and return the
    *  value if it exists.
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
index 2fe3f36e67..58ff1ceafd 100644
--- a/src/library/scala/collection/immutable/Vector.scala
+++ b/src/library/scala/collection/immutable/Vector.scala
@@ -13,17 +13,18 @@ import mutable.ArrayBuffer
 /** A subtrait of collection.Vector which represents sequences
  *  that cannot be mutated.
  */
-trait Vector[+A] extends Sequence[A] with collection.Vector[A] with VectorTemplate[A, Vector[A]] { self =>
-  override protected[this] def newBuilder = Vector.newBuilder
-  override def traversableBuilder[B]: Builder[B, Vector[B]] = Vector.newBuilder[B]
+trait Vector[+A] extends Sequence[A]
+                    with collection.Vector[A]
+                    with TraversableClass[A, Vector]
+                    with VectorTemplate[A, Vector[A]] {
+  override def companion: Companion[Vector]  = Vector
 }
 
 object Vector extends SequenceFactory[Vector] {
-  type Coll = Vector[_]
-  class Impl[A](buf: ArrayBuffer[A]) extends Vector[A] { // todo: insert better vector implementation here
+    class Impl[A](buf: ArrayBuffer[A]) extends Vector[A] { // todo: insert better vector implementation here
     def length = buf.length
     def apply(idx: Int) = buf.apply(idx)
   }
-  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new BuilderFactory[A, Vector[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Vector[A]] = new ArrayBuffer[A] mapResult (buf => new Impl(buf))
 }
diff --git a/src/library/scala/collection/mutable/ArrayBuffer.scala b/src/library/scala/collection/mutable/ArrayBuffer.scala
index 2e37d55ed2..8586ae3fee 100644
--- a/src/library/scala/collection/mutable/ArrayBuffer.scala
+++ b/src/library/scala/collection/mutable/ArrayBuffer.scala
@@ -25,11 +25,14 @@ import generic._
 @serializable
 class ArrayBuffer[A](override protected val initialSize: Int)
   extends Buffer[A]
+     with TraversableClass[A, ArrayBuffer]
      with BufferTemplate[A, ArrayBuffer[A]]
      with VectorTemplate[A, ArrayBuffer[A]]
      with Builder[A, ArrayBuffer[A]]
      with ResizableArray[A] {
 
+  override def companion: Companion[ArrayBuffer] = ArrayBuffer
+
   import collection.Traversable
 
   def this() = this(16)
@@ -42,9 +45,6 @@ class ArrayBuffer[A](override protected val initialSize: Int)
     array = newarray
   }
 
-  override protected[this] def newBuilder = ArrayBuffer.newBuilder
-  override def traversableBuilder[B]: Builder[B, ArrayBuffer[B]] = ArrayBuffer.newBuilder[B]
-
   /** Appends a single element to this buffer and returns
    *  the identity of the buffer. It takes constant time.
    *
@@ -159,8 +159,7 @@ class ArrayBuffer[A](override protected val initialSize: Int)
 
 /* Factory object for `ArrayBuffer` class */
 object ArrayBuffer extends SequenceFactory[ArrayBuffer] {
-  type Coll = ArrayBuffer[_]
-  implicit def builderFactory[A]: BuilderFactory[A, ArrayBuffer[A], Coll] = new BuilderFactory[A, ArrayBuffer[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, ArrayBuffer[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, ArrayBuffer[A]] = new ArrayBuffer[A]
 }
 
diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala
index 9518597b2f..996130766c 100644
--- a/src/library/scala/collection/mutable/BitSet.scala
+++ b/src/library/scala/collection/mutable/BitSet.scala
@@ -4,7 +4,10 @@ import generic._
 import BitSetTemplate.{LogWL, updateArray}
 
 /** A class for mutable bitsets */
-class BitSet (protected var elems: Array[Long]) extends Set[Int] with collection.BitSet with BitSetTemplate[BitSet] with MutableSetTemplate[Int, BitSet] {
+class BitSet (protected var elems: Array[Long]) extends Set[Int]
+                                                  with collection.BitSet
+                                                  with BitSetTemplate[BitSet]
+                                                  with MutableSetTemplate[Int, BitSet] {
 
   override def empty = BitSet.empty
 
@@ -67,9 +70,7 @@ class BitSet (protected var elems: Array[Long]) extends Set[Int] with collection
 }
 
 /** A factory object for mutable bitsets */
-object BitSet {
+object BitSet extends BitSetFactory[BitSet] {
   def empty: BitSet = new BitSet
-  def apply(bits: Int*): BitSet = {
-    var s = empty; for (b <- bits) s += b; s
-  }
+  implicit def builderFactory: BuilderFactory[Int, BitSet, BitSet] = bitsetBuilderFactory
 }
diff --git a/src/library/scala/collection/mutable/Buffer.scala b/src/library/scala/collection/mutable/Buffer.scala
index f2e0997294..2099f134fc 100644
--- a/src/library/scala/collection/mutable/Buffer.scala
+++ b/src/library/scala/collection/mutable/Buffer.scala
@@ -23,15 +23,15 @@ import generic._
  *  @version 2.8
   */
 @cloneable
-trait Buffer[A] extends Sequence[A] with BufferTemplate[A, Buffer[A]] {
-  override protected[this] def newBuilder = Buffer.newBuilder
-  override def traversableBuilder[B]: Builder[B, Buffer[B]] = Buffer.newBuilder[B]
+trait Buffer[A] extends Sequence[A]
+                   with TraversableClass[A, Buffer]
+                   with BufferTemplate[A, Buffer[A]] {
+  override def companion: Companion[Buffer] = Buffer
 }
 
 /* Factory object for `Buffer` trait */
 object Buffer extends SequenceFactory[Buffer] {
-  type Coll = Buffer[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Buffer[A], Coll] = new BuilderFactory[A, Buffer[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Buffer[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Buffer[A]] = new ArrayBuffer
 }
 
diff --git a/src/library/scala/collection/mutable/DoubleLinkedList.scala b/src/library/scala/collection/mutable/DoubleLinkedList.scala
index 1c67e3a413..aeaaf71808 100644
--- a/src/library/scala/collection/mutable/DoubleLinkedList.scala
+++ b/src/library/scala/collection/mutable/DoubleLinkedList.scala
@@ -1,10 +1,12 @@
+/* TODO: reintegrate
+
 /*                     __                                               *\
 **     ________ ___   / /  ___     Scala API                            **
 **    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
 **  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
 ** /____/\___/_/ |_/____/_/ | |                                         **
 **                          |/                                          **
-\*                                                                      */
+*                                                                      */
 
 // $Id$
 
@@ -27,10 +29,10 @@ class DoubleLinkedList[A]/*(_elem: A, _next: DoubleLinkedList[A])*/ extends Line
 }
 
 object DoubleLinkedList extends SequenceFactory[DoubleLinkedList] {
-  type Coll = DoubleLinkedList[_]
   implicit def builderFactory[A]: BuilderFactory[A, DoubleLinkedList[A], Coll] = new BuilderFactory[A, DoubleLinkedList[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
   def newBuilder[A]: Builder[A, DoubleLinkedList[A]] = null // !!!
 }
 
 
 
+*/
diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
index a2cce3358b..d80e514ac8 100644
--- a/src/library/scala/collection/mutable/HashMap.scala
+++ b/src/library/scala/collection/mutable/HashMap.scala
@@ -18,7 +18,6 @@ import generic._
 class HashMap[A, B] extends Map[A, B] with MutableMapTemplate[A, B, HashMap[A, B]] with HashTable[A] with DefaultMapModel[A, B] {
 
   override def empty: HashMap[A, B] = HashMap.empty[A, B]
-  override def mapBuilder[A, B]: Builder[(A, B), HashMap[A, B]] = HashMap.newBuilder[A, B]
 
   override def remove(key: A): Option[B] = removeEntry(key) match {
     case Some(e) => Some(e.value)
@@ -39,7 +38,6 @@ class HashMap[A, B] extends Map[A, B] with MutableMapTemplate[A, B, HashMap[A, B
  *  @version 2.8
  */
 object HashMap extends MutableMapFactory[HashMap] {
-  type Coll = HashMap[_, _]
-  implicit def builderFactory[A, B]: BuilderFactory[(A, B), HashMap[A, B], Coll] = new BuilderFactory[(A, B), HashMap[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] }
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), HashMap[A, B], Coll] = new MapBuilderFactory[A, B]
   def empty[A, B]: HashMap[A, B] = new HashMap[A, B]
 }
diff --git a/src/library/scala/collection/mutable/HashSet.scala b/src/library/scala/collection/mutable/HashSet.scala
index b72f3dc6fd..5c93ff96eb 100644
--- a/src/library/scala/collection/mutable/HashSet.scala
+++ b/src/library/scala/collection/mutable/HashSet.scala
@@ -20,10 +20,11 @@ import generic._
  *  @version 2.0, 31/12/2006
  */
 @serializable
-class HashSet[A] extends Set[A] with MutableSetTemplate[A, HashSet[A]] with FlatHashTable[A] {
-
-  override def empty = HashSet.empty
-  override def traversableBuilder[B]: Builder[B, HashSet[B]] = HashSet.newBuilder[B]
+class HashSet[A] extends Set[A]
+                    with SetClass[A, HashSet]
+                    with MutableSetTemplate[A, HashSet[A]]
+                    with FlatHashTable[A] {
+  override def companion: Companion[HashSet] = HashSet
 
   override def size = super.size
 
@@ -52,8 +53,7 @@ class HashSet[A] extends Set[A] with MutableSetTemplate[A, HashSet[A]] with Flat
 
 /** Factory object for `HashSet` class */
 object HashSet extends SetFactory[HashSet] {
-  type Coll = HashSet[_]
-  implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = new BuilderFactory[A, HashSet[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
-  def empty[A]: HashSet[A] = new HashSet[A]
+  implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = setBuilderFactory[A]
+  override def empty[A]: HashSet[A] = new HashSet[A]
 }
 
diff --git a/src/library/scala/collection/mutable/Iterable.scala b/src/library/scala/collection/mutable/Iterable.scala
index f7896dc3cc..18ca5588d6 100644
--- a/src/library/scala/collection/mutable/Iterable.scala
+++ b/src/library/scala/collection/mutable/Iterable.scala
@@ -15,15 +15,16 @@ import generic._
  *  @autor   Martin Odersky
  *  @version 2.8
  */
-trait Iterable[A] extends Traversable[A] with collection.Iterable[A] with IterableTemplate[A, Iterable[A]] { self =>
-  override protected[this] def newBuilder = Iterable.newBuilder
-  override def traversableBuilder[B]: Builder[B, Iterable[B]] = Iterable.newBuilder[B]
+trait Iterable[A] extends Traversable[A]
+                     with collection.Iterable[A]
+                     with TraversableClass[A, Iterable]
+                     with IterableTemplate[A, Iterable[A]] {
+  override def companion: Companion[Iterable] = Iterable
 }
 
 /* A factory object for the trait `Iterable` */
 object Iterable extends TraversableFactory[Iterable] {
-  type Coll = Iterable[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new BuilderFactory[A, Iterable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Iterable[A]] = new ArrayBuffer
 }
 
diff --git a/src/library/scala/collection/mutable/LinearSequence.scala b/src/library/scala/collection/mutable/LinearSequence.scala
index 60858bcb77..3d71be1f81 100644
--- a/src/library/scala/collection/mutable/LinearSequence.scala
+++ b/src/library/scala/collection/mutable/LinearSequence.scala
@@ -5,13 +5,14 @@ import generic._
 /** A subtrait of collection.Sequence which represents sequences
  *  that cannot be mutated.
  */
-trait LinearSequence[A] extends Sequence[A] with collection.LinearSequence[A] with LinearSequenceTemplate[A, LinearSequence[A]] {
-  override protected[this] def newBuilder = LinearSequence.newBuilder
-  override def traversableBuilder[B]: Builder[B, LinearSequence[B]] = LinearSequence.newBuilder[B]
+trait LinearSequence[A] extends Sequence[A]
+                           with collection.LinearSequence[A]
+                           with TraversableClass[A, LinearSequence]
+                           with LinearSequenceTemplate[A, LinearSequence[A]] {
+  override def companion: Companion[LinearSequence] = LinearSequence
 }
 
 object LinearSequence extends SequenceFactory[LinearSequence] {
-  type Coll = LinearSequence[_]
-  implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new BuilderFactory[A, LinearSequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, LinearSequence[A]] = new MutableList[A]
 }
diff --git a/src/library/scala/collection/mutable/LinkedHashMap.scala b/src/library/scala/collection/mutable/LinkedHashMap.scala
index e02e574c43..476bd39b7e 100644
--- a/src/library/scala/collection/mutable/LinkedHashMap.scala
+++ b/src/library/scala/collection/mutable/LinkedHashMap.scala
@@ -12,6 +12,7 @@
 package scala.collection.mutable
 
 import Predef._
+import generic._
 
 /** This class implements mutable maps using a hashtable.
  *
@@ -19,20 +20,19 @@ import Predef._
  *  @author  Martin Odersky
  *  @version 2.0, 31/12/2006
  */
-object LinkedHashMap {
-
-  /** The empty map of this type */
+object LinkedHashMap extends MutableMapFactory[LinkedHashMap] {
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), LinkedHashMap[A, B], Coll] = new MapBuilderFactory[A, B]
   def empty[A, B] = new LinkedHashMap[A, B]
-
-  /** The canonical factory for this type
-   */
-  def apply[A, B](elems: (A, B)*) = empty[A, B] ++ elems
 }
 
 @serializable
-class LinkedHashMap[A, B] extends Map[A,B] with HashTable[A] with DefaultMapModel[A,B] {
+class LinkedHashMap[A, B] extends Map[A, B]
+                             with MutableMapTemplate[A, B, LinkedHashMap[A, B]]
+                             with HashTable[A]
+                             with DefaultMapModel[A,B] {
 
   override def empty = LinkedHashMap.empty
+
   override def size = super[HashTable].size
 
   private var ordered = List[Entry]()
@@ -66,7 +66,5 @@ class LinkedHashMap[A, B] extends Map[A,B] with HashTable[A] with DefaultMapMode
     super.clear()
   }
 
-  override def clone(): Map[A, B] = new LinkedHashMap[A, B] ++ this
-
   override def elements = ordered.reverse.elements map {e => (e.key, e.value)}
 }
diff --git a/src/library/scala/collection/mutable/LinkedList.scala b/src/library/scala/collection/mutable/LinkedList.scala
index 47be78a8ed..90c88439b4 100644
--- a/src/library/scala/collection/mutable/LinkedList.scala
+++ b/src/library/scala/collection/mutable/LinkedList.scala
@@ -21,16 +21,16 @@ import generic._
  *  @version 2.8
  */
 @serializable
-class LinkedList[A](_elem: A, _next: LinkedList[A]) extends LinearSequence[A] with LinkedListTemplate[A, LinkedList[A]] {
+class LinkedList[A](_elem: A, _next: LinkedList[A]) extends LinearSequence[A]
+                                                       with TraversableClass[A, LinkedList]
+                                                       with LinkedListTemplate[A, LinkedList[A]] {
   elem = _elem
   next = _next
-  override protected[this] def newBuilder = LinkedList.newBuilder
-  override def traversableBuilder[B]: Builder[B, LinkedList[B]] = LinkedList.newBuilder[B]
+  override def companion: Companion[LinkedList] = LinkedList
 }
 
 object LinkedList extends SequenceFactory[LinkedList] {
-  type Coll = LinkedList[_]
-  implicit def builderFactory[A]: BuilderFactory[A, LinkedList[A], Coll] = new BuilderFactory[A, LinkedList[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, LinkedList[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, LinkedList[A]] = (new MutableList) mapResult ((l: MutableList[A]) => l.toLinkedList)
 }
 
diff --git a/src/library/scala/collection/mutable/ListBuffer.scala b/src/library/scala/collection/mutable/ListBuffer.scala
index 22396f1322..a83f620699 100644
--- a/src/library/scala/collection/mutable/ListBuffer.scala
+++ b/src/library/scala/collection/mutable/ListBuffer.scala
@@ -24,10 +24,13 @@ import generic._
 @serializable
 final class ListBuffer[A]
       extends Buffer[A]
+         with TraversableClass[A, ListBuffer]
          with BufferTemplate[A, ListBuffer[A]]
          with Builder[A, List[A]]
          with SequenceForwarder[A]
 {
+  override def companion: Companion[ListBuffer] = ListBuffer
+
   import collection.Traversable
 
   private var start: List[A] = Nil
@@ -37,9 +40,6 @@ final class ListBuffer[A]
 
   protected def underlying: immutable.Sequence[A] = start
 
-  override protected[this] def newBuilder = ListBuffer.newBuilder[A]
-  override def traversableBuilder[B]: Builder[B, ListBuffer[B]] = ListBuffer.newBuilder[B]
-
   /** The current length of the buffer
    */
   override def length = len
@@ -320,8 +320,7 @@ final class ListBuffer[A]
 
 /* Factory object for `ListBuffer` class */
 object ListBuffer extends SequenceFactory[ListBuffer] {
-  type Coll = ListBuffer[_]
-  implicit def builderFactory[A]: BuilderFactory[A, ListBuffer[A], Coll] = new BuilderFactory[A, ListBuffer[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, ListBuffer[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, ListBuffer[A]] = new AddingBuilder(new ListBuffer[A])
 }
 
diff --git a/src/library/scala/collection/mutable/ListMap.scala b/src/library/scala/collection/mutable/ListMap.scala
new file mode 100644
index 0000000000..8b8e5d87a6
--- /dev/null
+++ b/src/library/scala/collection/mutable/ListMap.scala
@@ -0,0 +1,47 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashMap.scala 17715 2009-05-12 18:33:22Z odersky $
+
+
+package scala.collection.mutable
+
+import generic._
+
+@serializable
+class ListMap[A, B] extends Map[A, B] with MutableMapTemplate[A, B, ListMap[A, B]] {
+
+
+  override def empty = ListMap.empty[A, B]
+
+  private var elems: List[(A, B)] = List()
+  private var siz: Int = 0
+
+  def get(key: A): Option[B] = elems find (_._1 == key) map (_._2)
+  def elements: Iterator[(A, B)] = elems.elements
+  def += (kv: (A, B)) = { elems = remove(kv._1, elems); elems = kv :: elems; siz += 1; this }
+  def -= (key: A) = { elems = remove(key, elems); this }
+
+  private def remove(key: A, elems: List[(A, B)]): List[(A, B)] =
+    if (elems.isEmpty) elems
+    else if (elems.head._1 == key) { siz -= 1; elems.tail }
+    else elems.head :: remove(key, elems.tail)
+
+  override def clear() = elems = List()
+  override def size: Int = siz
+}
+
+/** This class implements mutable maps using a list.
+ *
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+object ListMap extends MutableMapFactory[ListMap] {
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), ListMap[A, B], Coll] = new MapBuilderFactory[A, B]
+  def empty[A, B]: ListMap[A, B] = new ListMap[A, B]
+}
diff --git a/src/library/scala/collection/mutable/Map.scala b/src/library/scala/collection/mutable/Map.scala
index 17c3e81472..94e376cd67 100644
--- a/src/library/scala/collection/mutable/Map.scala
+++ b/src/library/scala/collection/mutable/Map.scala
@@ -20,7 +20,6 @@ trait Map[A, B]
      with Unhashable {
 
   override def empty: Map[A, B] = Map.empty
-  override def mapBuilder[A, B]: Builder[(A, B), Map[A, B]] = Map.newBuilder[A, B]
 
   /** Return a read-only projection of this map.  !!! or just use an (immutable) MapProxy?
   def readOnly : collection.Map[A, B] = new collection.Map[A, B] {
@@ -38,8 +37,7 @@ trait Map[A, B]
  * Currently this returns a HashMap.
  */
 object Map extends MutableMapFactory[Map] {
-  type Coll = Map[_, _]
-  implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new BuilderFactory[(A, B), Map[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] }
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new MapBuilderFactory[A, B]
   def empty[A, B]: Map[A, B] = new HashMap[A, B]
 }
 
diff --git a/src/library/scala/collection/mutable/ResizableArray.scala b/src/library/scala/collection/mutable/ResizableArray.scala
index b7d0c14806..6f8d58ad47 100644
--- a/src/library/scala/collection/mutable/ResizableArray.scala
+++ b/src/library/scala/collection/mutable/ResizableArray.scala
@@ -20,13 +20,11 @@ import generic._
  *  @author Martin Odersky
  *  @version 2.8
  */
-trait ResizableArray[A] extends Vector[A] with VectorTemplate[A, ResizableArray[A]] { self =>
+trait ResizableArray[A] extends Vector[A]
+                           with TraversableClass[A, ResizableArray]
+                           with VectorTemplate[A, ResizableArray[A]] {
 
-  import scala.Array // !!!
-  import collection.Iterable // !!!
-
-  override protected[this] def newBuilder = ResizableArray.newBuilder
-  override def traversableBuilder[B]: Builder[B, ResizableArray[B]] = ResizableArray.newBuilder[B]
+  override def companion: Companion[ResizableArray] = ResizableArray
 
   protected def initialSize: Int = 16
   protected var array: Array[AnyRef] = new Array[AnyRef](initialSize max 1)
@@ -115,7 +113,6 @@ trait ResizableArray[A] extends Vector[A] with VectorTemplate[A, ResizableArray[
 }
 
 object ResizableArray extends SequenceFactory[ResizableArray] {
-  type Coll = Vector[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new BuilderFactory[A, Vector[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, ResizableArray[A]] = new ArrayBuffer[A]
 }
diff --git a/src/library/scala/collection/mutable/Sequence.scala b/src/library/scala/collection/mutable/Sequence.scala
index efc4092853..4f460f74c7 100644
--- a/src/library/scala/collection/mutable/Sequence.scala
+++ b/src/library/scala/collection/mutable/Sequence.scala
@@ -13,15 +13,17 @@ import generic._
  *  that can be mutated.
  *  The class adds an `update` method to collection.Sequence.
  */
-trait Sequence[A] extends Iterable[A] with collection.Sequence[A] with SequenceTemplate[A, Sequence[A]] with Unhashable {
-  override protected[this] def newBuilder = Sequence.newBuilder
-  override def traversableBuilder[B]: Builder[B, Sequence[B]] = Sequence.newBuilder[B]
+trait Sequence[A] extends Iterable[A]
+                     with collection.Sequence[A]
+                     with TraversableClass[A, Sequence]
+                     with SequenceTemplate[A, Sequence[A]]
+                     with Unhashable {
+  override def companion: Companion[Sequence] = Sequence
 
   def update(idx: Int, elem: A)
 }
 
 object Sequence extends SequenceFactory[Sequence] {
-  type Coll = Sequence[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new BuilderFactory[A, Sequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Sequence[A]] = new ArrayBuffer
 }
diff --git a/src/library/scala/collection/mutable/Set.scala b/src/library/scala/collection/mutable/Set.scala
index 79a31cc5ef..8118f8a58f 100644
--- a/src/library/scala/collection/mutable/Set.scala
+++ b/src/library/scala/collection/mutable/Set.scala
@@ -13,7 +13,7 @@ package scala.collection.mutable
 
 import generic._
 
-/** This class represents mutable sets. Concrete set implementations
+/** A generic trait for mutable sets. Concrete set implementations
  *  have to provide functionality for the abstract methods in Set:
  *
  *  def contains(elem: A): Boolean
@@ -27,20 +27,17 @@ import generic._
  */
 trait Set[A] extends Iterable[A]
                 with collection.Set[A]
+                with SetClass[A, Set]
                 with MutableSetTemplate[A, Set[A]]
                 with Unhashable {
-
-  override def empty = Set.empty
-
-  override def traversableBuilder[B]: Builder[B, Set[B]] = Set.newBuilder[B]
+  override def companion: Companion[Set] = Set
 }
 
 /** The canonical factory methods for <a href="Set.html">mutable sets</a>.
  *  Currently this returns a HashSet.
  */
 object Set extends SetFactory[Set] {
-  type Coll = Set[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = new BuilderFactory[A, Set[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
-  def empty[A]: Set[A] = HashSet.empty[A]
+  implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = setBuilderFactory[A]
+  override def empty[A]: Set[A] = HashSet.empty[A]
 }
 
diff --git a/src/library/scala/collection/mutable/SynchronizedMap.scala b/src/library/scala/collection/mutable/SynchronizedMap.scala
index 1afc02ed57..838b987e9b 100644
--- a/src/library/scala/collection/mutable/SynchronizedMap.scala
+++ b/src/library/scala/collection/mutable/SynchronizedMap.scala
@@ -23,7 +23,6 @@ trait SynchronizedMap[A, B] extends Map[A, B] {
 
   import collection.Traversable
 
-  override def mapBuilder[A, B]: Builder[(A, B), SynchronizedMap[A, B]] = SynchronizedMap.newBuilder[A, B]
 
   abstract override def size: Int = synchronized {
     super.size
diff --git a/src/library/scala/collection/mutable/Traversable.scala b/src/library/scala/collection/mutable/Traversable.scala
index 72b7271b85..46a99c7b42 100644
--- a/src/library/scala/collection/mutable/Traversable.scala
+++ b/src/library/scala/collection/mutable/Traversable.scala
@@ -15,15 +15,16 @@ import generic._
  *  @autor   Martin Odersky
  *  @version 2.8
  */
-trait Traversable[A] extends collection.Traversable[A] with TraversableTemplate[A, Traversable[A]] with Mutable { self =>
-  override protected[this] def newBuilder = Traversable.newBuilder
-  override def traversableBuilder[B]: Builder[B, Traversable[B]] = Traversable.newBuilder[B]
+trait Traversable[A] extends collection.Traversable[A]
+                        with TraversableClass[A, Traversable]
+                        with TraversableTemplate[A, Traversable[A]]
+                        with Mutable {
+  override def companion: Companion[Traversable] = Traversable
 }
 
 /* A factory object for the trait `Traversable` */
 object Traversable extends TraversableFactory[Traversable] {
-  type Coll = Traversable[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new BuilderFactory[A, Traversable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Traversable[A]] = new ArrayBuffer
 }
 
diff --git a/src/library/scala/collection/mutable/Vector.scala b/src/library/scala/collection/mutable/Vector.scala
index dae5c4864f..db082bb09d 100644
--- a/src/library/scala/collection/mutable/Vector.scala
+++ b/src/library/scala/collection/mutable/Vector.scala
@@ -12,13 +12,14 @@ import generic._
 /** A subtrait of collection.Vector which represents sequences
  *  that can be mutated.
  */
-trait Vector[A] extends Sequence[A] with collection.Vector[A] with MutableVectorTemplate[A, Vector[A]] {
-  override protected[this] def newBuilder = Vector.newBuilder
-  override def traversableBuilder[B]: Builder[B, Vector[B]] = Vector.newBuilder[B]
+trait Vector[A] extends Sequence[A]
+                   with collection.Vector[A]
+                   with TraversableClass[A, Vector]
+                   with MutableVectorTemplate[A, Vector[A]] {
+  override def companion: Companion[Vector]  = Vector
 }
 
 object Vector extends SequenceFactory[Vector] {
-  type Coll = Vector[_]
-  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new BuilderFactory[A, Vector[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] }
+  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Vector[A]] = new ArrayBuffer
 }