new version of collection libraries

74 files changed, 2876 insertions, 494 deletions

diff --git a/src/library/scalax/Tuple2.scala b/src/library/scalax/Tuple2.scala
new file mode 100755
index 0000000000..4adb9e471b
--- /dev/null
+++ b/src/library/scalax/Tuple2.scala
@@ -0,0 +1,97 @@
+
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2002-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Tuple2.scala 14794 2008-04-23 08:15:17Z washburn $
+
+// generated by genprod on Wed Apr 23 10:06:16 CEST 2008  (with extra methods)
+
+package scalax
+
+import annotation.unchecked.uncheckedVariance
+
+object Tuple2 {
+
+  import collection._
+  import collection.generic._
+
+  class IterableOps[CC[+B] <: Iterable[B] with IterableTemplate[CC, B @uncheckedVariance], A1, A2](tuple: (CC[A1], Iterable[A2])) {
+    def zip: CC[(A1, A2)] = {
+      val elems1 = tuple._1.elements
+      val elems2 = tuple._2.elements
+      val b = tuple._1.newBuilder[(A1, A2)]
+      while (elems1.hasNext && elems2.hasNext)
+        b += ((elems1.next, elems2.next))
+      b.result
+    }
+    def map[B](f: (A1, A2) => B): CC[B] = {
+      val elems1 = tuple._1.elements
+      val elems2 = tuple._2.elements
+      val b = tuple._1.newBuilder[B]
+      while (elems1.hasNext && elems2.hasNext)
+        b += f(elems1.next, elems2.next)
+      b.result
+    }
+    def flatMap[B](f: (A1, A2) => CC[B]): CC[B] = {
+      val elems1 = tuple._1.elements
+      val elems2 = tuple._2.elements
+      val b = tuple._1.newBuilder[B]
+      while (elems1.hasNext && elems2.hasNext)
+        b ++= f(elems1.next, elems2.next)
+      b.result
+    }
+    def foreach(f: (A1, A2) => Unit) {
+      val elems1 = tuple._1.elements
+      val elems2 = tuple._2.elements
+      while (elems1.hasNext && elems2.hasNext)
+        f(elems1.next, elems2.next)
+    }
+    def forall(p: (A1, A2) => Boolean): Boolean = {
+      val elems1 = tuple._1.elements
+      val elems2 = tuple._2.elements
+      while (elems1.hasNext && elems2.hasNext)
+        if (!p(elems1.next, elems2.next)) return false
+      true
+    }
+    def exists(p: (A1, A2) => Boolean): Boolean = {
+      val elems1 = tuple._1.elements
+      val elems2 = tuple._2.elements
+      while (elems1.hasNext && elems2.hasNext)
+        if (p(elems1.next, elems2.next)) return true
+      false
+    }
+  }
+  implicit def tupleOfIterableWrapper[CC[+B] <: Iterable[B] with IterableTemplate[CC, B], A1, A2](tuple: (CC[A1], Iterable[A2])) =
+    new IterableOps[CC, A1, A2](tuple)
+
+
+/* A more general version which will probably not work.
+  implicit def tupleOfIterableWrapper[CC[+B] <: Iterable[B] with IterableTemplate[CC, B], A1, A2, B1 <: CC[A1]](tuple: B1, Iterable[A2]) =
+    new IterableOps[CC, A1, A2](tuple)
+*/
+
+  // Adriaan: If you drop the type parameters it will infer the wrong types.
+  tupleOfIterableWrapper[collection.immutable.List, Int, Int]((collection.immutable.Nil, collection.immutable.Nil)) forall (_ + _ < 10)
+}
+
+/** Tuple2 is the canonical representation of a @see Product2
+ *
+ */
+case class Tuple2[+T1, +T2](_1:T1, _2:T2)
+  extends Product2[T1, T2]  {
+
+   override def toString() = {
+     val sb = new StringBuilder
+     sb.append('(').append(_1).append(',').append(_2).append(')')
+     sb.toString
+   }
+
+  /** Swap the elements of the tuple */
+  def swap: Tuple2[T2,T1] = Tuple2(_2, _1)
+
+}
diff --git a/src/library/scalax/collection/Iterable.scala b/src/library/scalax/collection/Iterable.scala
index 08bf338290..3dc181707c 100755
--- a/src/library/scalax/collection/Iterable.scala
+++ b/src/library/scalax/collection/Iterable.scala
@@ -13,6 +13,7 @@ package scalax.collection
 
 import generic._
 import collection.immutable.{List, Nil, ::}
+import annotation.unchecked.uncheckedVariance
 
 /** Collection classes mixing in this class provide a method
  *  <code>elements</code> which returns an iterator over all the
@@ -25,7 +26,7 @@ import collection.immutable.{List, Nil, ::}
  *  @owner   Martin Odersky
  *  @version 2.8
  */
-trait Iterable[+A] extends covariant.IterableTemplate[Iterable, A] { self =>
+trait Iterable[+A] extends IterableTemplate[Iterable, A @uncheckedVariance] { self =>
 
   /** Creates a view of this iterable @see Iterable.View
   def view: View[Iterable, A] = new View[Iterable, A] { // !!! Martin: We should maybe infer the type parameters here?
@@ -41,7 +42,7 @@ trait Iterable[+A] extends covariant.IterableTemplate[Iterable, A] { self =>
  *  @author  Martin Odersky
  *  @version 2.8
  */
-object Iterable extends covariant.IterableFactory[Iterable] {
+object Iterable extends IterableFactory[Iterable] with EmptyIterableFactory[Iterable] {
 
   /** The empty iterable */
   val empty: Iterable[Nothing] = Nil
@@ -76,16 +77,16 @@ object Iterable extends covariant.IterableFactory[Iterable] {
     }
   }
 
-  class IterableIterableOps[C[+B] <: Iterable[B] with covariant.IterableTemplate[C, B], A](self: C[C[A]]) {
+  class IterableIterableOps[C[+B] <: Iterable[B] with IterableTemplate[C, B @uncheckedVariance], A](self: C[C[A]]) {
     def flatten: C[A] = {
-      val b: Builder[C, A] = self.newBuilder[A]
+      val b: generic.Builder[C, A] = self.newBuilder[A]
       for (xs <- self)
         b ++= xs
       b.result
     }
 
     def transpose: C[C[A]] = {
-      val bs: Array[Builder[C, A]] = self.head.map(_ => self.newBuilder[A]).toArray
+      val bs: scala.Array[generic.Builder[C, A]] = self.head.map(_ => self.newBuilder[A]).toArray
       for (xs <- self) {
         var i = 0
         for (x <- xs) {
@@ -93,7 +94,6 @@ object Iterable extends covariant.IterableFactory[Iterable] {
           i += 1
         }
       }
-      type CC[B] = C[C[B]]
       val bb = self.newBuilder[C[A]]
       for (b <- bs) bb += b.result
       bb.result
@@ -117,16 +117,16 @@ object Iterable extends covariant.IterableFactory[Iterable] {
     new ComparableIterableOps(seq, cmp)
   implicit def numericIterableWrapper[A](seq: Iterable[A])(implicit num: Numeric[A]) =
     new NumericIterableOps(seq, num)
-  implicit def iterableIterableWrapper[C[+B] <: Iterable[B] with covariant.IterableTemplate[C, B], A](seq: C[C[A]]) =
+  implicit def iterableIterableWrapper[C[+B] <: Iterable[B] with IterableTemplate[C, B], A](seq: C[C[A]]) =
     new IterableIterableOps[C, A](seq)
   implicit def pairIterableWrapper[C[+B] <: Iterable[B], A1, A2](seq: C[(A1, A2)]) =
     new PairIterableOps[C, A1, A2](seq)
 
-  type View[+UC[B] <: Sequence[B], A] = IterableView[UC, A]
+  type View[A] = IterableView[UC, A] forSome { type UC[B] <: Iterable[B] }
 
   /** @deprecated use View instead
    */
-  @deprecated type Projection[A] = View[C, A] forSome { type C[B] <: Iterable[B] }
+  @deprecated type Projection[A] = View[A]
 
   /** The minimum element of a non-empty sequence of ordered elements
    *  @deprecated use seq.min instead
diff --git a/src/library/scalax/collection/Iterator.scala b/src/library/scalax/collection/Iterator.scala
index b858c91d2c..48eda407aa 100755
--- a/src/library/scalax/collection/Iterator.scala
+++ b/src/library/scalax/collection/Iterator.scala
@@ -29,15 +29,15 @@ object Iterator {
   }
 
   /**
-   *  @param x the element
+   *  @param elem the element
    *  @return  the iterator with one single element
    *  @note  Equivalent, but more efficient than Iterator(x)
    */
-  def single[A](x: A) = new Iterator[A] {
+  def single[A](elem: A) = new Iterator[A] {
     private var hasnext = true
     def hasNext: Boolean = hasnext
     def next(): A =
-      if (hasnext) { hasnext = false; x }
+      if (hasnext) { hasnext = false; elem }
       else empty.next()
   }
 
@@ -173,7 +173,7 @@ object Iterator {
   implicit def iteratorIteratorWrapper[A](its: Iterator[Iterator[A]]): IteratorIteratorOps[A] =
     new IteratorIteratorOps[A](its)
 
-  /** @deprecated  use `xs.elements` instead
+  /** @deprecated  use `xs.elements`, or `Iterator(x1, ..., xn)` instead
    */
   @deprecated def fromValues[a](xs: a*) = xs.elements
 
diff --git a/src/library/scalax/collection/Map.scala b/src/library/scalax/collection/Map.scala
new file mode 100755
index 0000000000..602da06bb0
--- /dev/null
+++ b/src/library/scalax/collection/Map.scala
@@ -0,0 +1,21 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Map.scala 16884 2009-01-09 16:52:09Z cunei $
+
+
+package scalax.collection
+
+import generic._
+
+trait Map[A, B] extends MapTemplate[A, B, Map]
+
+/* Factory object for `Map` class */
+object Map extends MapFactory[Map] {
+  def empty[A, B]: Map[A, B] = new immutable.EmptyMap[A, B]
+}
diff --git a/src/library/scalax/collection/OrderedIterable.scala b/src/library/scalax/collection/OrderedIterable.scala
index 929618fc19..9a0b77e575 100755
--- a/src/library/scalax/collection/OrderedIterable.scala
+++ b/src/library/scalax/collection/OrderedIterable.scala
@@ -13,11 +13,10 @@ package scalax.collection
 
 import generic._
 import immutable.Nil
+import annotation.unchecked.uncheckedVariance
 
 /** An ordered collection is a collection with a fixed sequence of elements
- *  which corresponds to append order. In particular, it holds that
- *
- *    (c1 ++ c2).elements = c1.elements ++ c2.elements
+ *  which is the same in every run.
  *
  *  for any two ordered collections c1 and c2.
  *  Ordered collections support
@@ -27,7 +26,7 @@ import immutable.Nil
  *  @author Martin Odersky
  *  @version 2.8
  */
-trait OrderedIterable[+A] extends Iterable[A] with covariant.OrderedIterableTemplate[OrderedIterable, A]
+trait OrderedIterable[+A] extends Iterable[A] with OrderedIterableTemplate[OrderedIterable, A @uncheckedVariance]
 
 /** Various utilities for instances of <a href="Iterable.html">Iterable</a>.
  *
@@ -35,7 +34,7 @@ trait OrderedIterable[+A] extends Iterable[A] with covariant.OrderedIterableTemp
  *  @author  Martin Odersky
  *  @version 2.8
  */
-object OrderedIterable extends covariant.IterableFactory[OrderedIterable] {
+object OrderedIterable extends IterableFactory[OrderedIterable] with EmptyIterableFactory[OrderedIterable] {
 
   val empty: OrderedIterable[Nothing] = Nil
 
diff --git a/src/library/scalax/collection/Sequence.scala b/src/library/scalax/collection/Sequence.scala
index 90212b3b5e..48081c99e8 100755
--- a/src/library/scalax/collection/Sequence.scala
+++ b/src/library/scalax/collection/Sequence.scala
@@ -13,6 +13,7 @@ package scalax.collection
 
 import generic._
 import immutable.Nil
+import annotation.unchecked.uncheckedVariance
 
 /** Class <code>Sequence[A]</code> represents finite sequences of elements
  *  of type <code>A</code>.
@@ -21,9 +22,9 @@ import immutable.Nil
  *  @author  Matthias Zenger
  *  @version 1.0, 16/07/2003
  */
-trait Sequence[+A] extends OrderedIterable[A] with SizedIterable[A] with generic.covariant.SequenceTemplate[Sequence, A]
+trait Sequence[+A] extends OrderedIterable[A] with SizedIterable[A] with SequenceTemplate[Sequence, A @uncheckedVariance]
 
-object Sequence extends covariant.SequenceFactory[Sequence] {
+object Sequence extends SequenceFactory[Sequence] with EmptyIterableFactory[Sequence] {
 
   /** The empty sequence */
   val empty : Sequence[Nothing] = immutable.Nil
diff --git a/src/library/scalax/collection/Set.scala b/src/library/scalax/collection/Set.scala
index 24829364b3..a7234d0261 100644
--- a/src/library/scalax/collection/Set.scala
+++ b/src/library/scalax/collection/Set.scala
@@ -12,12 +12,13 @@ package scalax.collection
 
 import generic._
 
-trait Set[A] extends OrderedIterable[A] with SetTemplate[Set, A]
+trait Set[A] extends SetTemplate[Set, A]
 
-/* Factory object for `Sequence` class */
+/* Factory object for `Set` class */
 object Set extends IterableFactory[Set] {
   /** The empty set */
   def apply[A](args: A*): Set[A] = null // !!!
+
 }
 
 
diff --git a/src/library/scalax/collection/Vector.scala b/src/library/scalax/collection/Vector.scala
index d36c980df2..8224a8630b 100755
--- a/src/library/scalax/collection/Vector.scala
+++ b/src/library/scalax/collection/Vector.scala
@@ -12,10 +12,11 @@ package scalax.collection
 
 import generic._
 import mutable.ArrayBuffer
+import annotation.unchecked.uncheckedVariance
 
-trait Vector[+A] extends Sequence[A] with covariant.VectorTemplate[Vector, A]
+trait Vector[+A] extends Sequence[A] with VectorTemplate[Vector, A @uncheckedVariance]
 
-object Vector extends covariant.SequenceFactory[Vector] {
+object Vector extends SequenceFactory[Vector] with EmptyIterableFactory[Vector] {
 
   /** The empty sequence */
   val empty : Vector[Nothing] = null // !!! todo: insert good immutable vector implementation here.
diff --git a/src/library/scalax/collection/generic/Addable.scala b/src/library/scalax/collection/generic/Addable.scala
new file mode 100755
index 0000000000..40a4f60e6e
--- /dev/null
+++ b/src/library/scalax/collection/generic/Addable.scala
@@ -0,0 +1,64 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+package scalax.collection.generic
+
+/** This class represents collections that can be augmented using a += operator.
+ *
+ *  @autor   Martin Odersky
+ *  @owner   Martin Odersky
+ *  @version 2.8
+ */
+trait Addable[+C <: Addable[C, A], A] {
+
+  protected def thisCC: C
+
+  /** Adds a single element to this collection and returns
+   *  either the collection itself (if it is mutable), or a new collection
+   *  with the added element.
+   *
+   *  @param elem  the element to add.
+   */
+  def +(elem: A): C
+
+  /** Adds two or more elements to this collection and returns
+   *  either the collection itself (if it is mutable), or a new collection
+   *  with the added elements.
+   *
+   *  @param elem1 the first element to add.
+   *  @param elem2 the second element to add.
+   *  @param elems the remaining elements to add.
+   */
+  def +(elem1: A, elem2: A, elems: A*): C =
+    thisCC + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]] // !@!
+
+  /** Adds a number of elements provided by an iterable object
+   *  via its <code>elements</code> method and returns
+   *  either the collection itself (if it is mutable), or a new collection
+   *  with the added elements.
+   *
+   *  @param iter     the iterable object.
+   */
+  def ++(iter: Iterable[A]): C = (thisCC /: iter) (_ + _)
+
+  /** Adds a number of elements provided by an iterator
+   *  via its <code>elements</code> method and returns
+   *  either the collection itself (if it is mutable), or a new collection
+   *  with the added elements.
+   *
+   *  @param iter   the iterator
+   */
+  def ++(iter: Iterator[A]): C = (thisCC /: iter) (_ + _)
+
+}
+
+
+
+
diff --git a/src/library/scalax/collection/generic/AddableBuilder.scala b/src/library/scalax/collection/generic/AddableBuilder.scala
new file mode 100644
index 0000000000..b1f3e4e522
--- /dev/null
+++ b/src/library/scalax/collection/generic/AddableBuilder.scala
@@ -0,0 +1,22 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $
+
+package scalax.collection.generic
+
+import collection.mutable.ListBuffer
+import collection.immutable.{List, Nil, ::}
+
+class AddableBuilder[CC[B] <: Iterable[B] with Addable[CC[B], B], A](empty: CC[A]) extends Builder[CC, A] {
+  protected var elems: CC[A] = empty
+  def +=(x: A) { elems = elems + x }
+  def elements: Iterator[A] = elems.elements
+  def clear() { elems = empty }
+  def result: CC[A] = elems
+}
diff --git a/src/library/scalax/collection/Builder.scala b/src/library/scalax/collection/generic/Builder.scala
index 2c80916d50..155ca553fa 100755
--- a/src/library/scalax/collection/Builder.scala
+++ b/src/library/scalax/collection/generic/Builder.scala
@@ -8,14 +8,14 @@
 
 // $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $
 
-package scalax.collection
+package scalax.collection.generic
 
-trait Builder[+CC[B], A] extends generic.mutable.Growable[A] {
+import generic._
+
+trait Builder[+CC[B], A] extends Growable[A] {
   def +=(x: A)
   def elements: Iterator[A]
   def result: CC[A]
-  override def ++=(xs: Iterator[A]) { for (x <- xs) this += x }
-  override def ++=(xs: Iterable[A]) { for (x <- xs) this += x }
 
   def mapResult[DD[B]](f: CC[A] => DD[A]) =
     new Builder[DD, A] with Proxy {
diff --git a/src/library/scalax/collection/generic/Cloneable.scala b/src/library/scalax/collection/generic/Cloneable.scala
index 455c88e47b..acf9a16686 100644
--- a/src/library/scalax/collection/generic/Cloneable.scala
+++ b/src/library/scalax/collection/generic/Cloneable.scala
@@ -9,10 +9,11 @@
 // $Id: CloneableCollection.scala 16893 2009-01-13 13:09:22Z cunei $
 
 
-package scala.collection.generic
+package scalax.collection.generic
 
 /** A trait for cloneable collections.
  */
-trait Cloneable[A <: AnyRef] extends java.lang.Cloneable {
+@cloneable
+trait Cloneable[A <: AnyRef]  {
   override def clone(): A = super.clone().asInstanceOf[A]
 }
diff --git a/src/library/scalax/collection/generic/EmptyIterableFactory.scala b/src/library/scalax/collection/generic/EmptyIterableFactory.scala
new file mode 100755
index 0000000000..7f110d13d2
--- /dev/null
+++ b/src/library/scalax/collection/generic/EmptyIterableFactory.scala
@@ -0,0 +1,17 @@
+package scalax.collection.generic
+
+import annotation.unchecked.uncheckedVariance
+
+trait EmptyIterableFactory[CC[+A] <: Iterable[A] with IterableTemplate[CC, A @uncheckedVariance]] extends IterableFactory[CC] {
+
+  /** The empty collection of type CC */
+  val empty: CC[Nothing]
+
+  /** An override of newBuilder, to work off the empty object */
+  override protected def newBuilder[A]: Builder[CC, A] =
+    empty.newBuilder[A]
+
+  /** Create CC collection of specified elements */
+  override def apply[A](args: A*): CC[A] =
+    empty ++ args.asInstanceOf[Iterable[A]]
+}
diff --git a/src/library/scalax/collection/generic/Growable.scala b/src/library/scalax/collection/generic/Growable.scala
new file mode 100755
index 0000000000..960384f9d0
--- /dev/null
+++ b/src/library/scalax/collection/generic/Growable.scala
@@ -0,0 +1,58 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+package scalax.collection.generic
+
+/** This class represents collections that can be augmented using a += operator.
+ *
+ *  @autor   Martin Odersky
+ *  @owner   Martin Odersky
+ *  @version 2.8
+ */
+trait Growable[A] {
+
+  /** Adds a single element to this collection.
+   *
+   *  @param elem  the element to add.
+   */
+  def +=(elem: A): Unit
+
+  /** Adds two or more elements to this collection.
+   *
+   *  @param elem1 the first element to add.
+   *  @param elem2 the second element to add.
+   *  @param elems the remaining elements to add.
+   */
+  def +=(elem1: A, elem2: A, elems: A*) {
+    this += elem1
+    this += elem2
+    this ++= elems.asInstanceOf[Iterable[A]] // !@!
+  }
+
+  /** Adds a number of elements provided by an iterator to this collection.
+   *
+   *  @param iter  the iterator.
+   */
+  def ++=(iter: collection.Iterator[A]) { iter foreach += }
+
+  /** Adds a number of elements provided by an iterable object to this collection.
+   *
+   *  @param iter  the iterable object.
+   */
+  def ++=(iter: collection.Iterable[A]) { iter foreach += }
+
+  /** Clears the collection contents.
+   */
+  def clear()
+}
+
+
+
+
diff --git a/src/library/scalax/collection/generic/IterableFactory.scala b/src/library/scalax/collection/generic/IterableFactory.scala
index 9570970abe..0cf9c8ac95 100755
--- a/src/library/scalax/collection/generic/IterableFactory.scala
+++ b/src/library/scalax/collection/generic/IterableFactory.scala
@@ -8,7 +8,7 @@ trait IterableFactory[CC[A] <: Iterable[A]] {
   protected def newBuilder[A]: Builder[CC, A] =
     apply().newBuilder[A].asInstanceOf[Builder[CC, A]]
 
-  // can't have an empty here because it is defined in subclass covariant.IterableFactory with type
+  // can't have an empty here because it is defined in subclass EmptyIterableFactory with type
   // CC[Nothing]. This type does not make sense for immutable iterables.
 
   /** Concatenate all the argument lists into a single list.
@@ -88,10 +88,10 @@ trait IterableFactory[CC[A] <: Iterable[A]] {
    *          increasing n. If `step > 0` the sequence terminates
    *          with the largest value less than `end`. If `step < 0`
    *          the sequence terminates with the smallest value greater than `end`.
-   *          If `step == 0`, the sequence gors on infinitely (in that
-   *          case the `range` operation might not terminate.
+   *          If `step == 0`, an IllegalArgumentException is thrown.
    */
   def range(start: Int, end: Int, step: Int): CC[Int] = {
+    if (step == 0) throw new IllegalArgumentException("zero step")
     val b = newBuilder[Int]
     var i = start
     while ((step <= 0 || i < end) && (step >= 0 || i > end)) {
diff --git a/src/library/scalax/collection/generic/IterableForwarder.scala b/src/library/scalax/collection/generic/IterableForwarder.scala
index 8613b18345..e38f030414 100644
--- a/src/library/scalax/collection/generic/IterableForwarder.scala
+++ b/src/library/scalax/collection/generic/IterableForwarder.scala
@@ -56,6 +56,4 @@ trait IterableForwarder[+A] extends Iterable[A] {
   override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = underlying.addString(b, start, sep, end)
 
   override def head: A = underlying.head
-  override def last: A = underlying.last
-  override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that)
 }
diff --git a/src/library/scalax/collection/generic/IterableTemplate.scala b/src/library/scalax/collection/generic/IterableTemplate.scala
index adbf5d2de7..cc562c308a 100755
--- a/src/library/scalax/collection/generic/IterableTemplate.scala
+++ b/src/library/scalax/collection/generic/IterableTemplate.scala
@@ -646,76 +646,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
     b.result
   }
 
-  /** The last element of this iterable.
-   *
-   *  @throws Predef.NoSuchElementException if the iterable is empty.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def last: A = {
-    var lst = head
-    for (x <- this)
-      lst = x
-    lst
-  }
-
-  /** Returns as an option the last element of this iterable or
-   *  <code>None</code> if iterable is empty.
-   *
-   *  @return the last element as an option.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def lastOption: Option[A] = if (isEmpty) None else Some(last)
-
-  /** An iterable consisting of all elements of this iterable except the last one.
-   *  @throws Predef.UnsupportedOperationException if the stream is empty.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def init: CC[A] = {
-    if (isEmpty) throw new UnsupportedOperationException("empty.init")
-    var lst = head
-    val b = newBuilder[A]
-    for (x <- this) {
-      b += lst
-      lst = x
-    }
-    b.result
-  }
-
-  /** Returns the rightmost <code>n</code> elements from this iterable.
-   *
-   *  @param n the number of elements to take
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def takeRight(n: Int): CC[A] = {
-    val b = newBuilder[A]
-    val lead = elements drop n
-    var go = false
-    for (x <- this) {
-      if (go) b += x
-      else if (lead.hasNext) lead.next
-      else go = true
-    }
-    b.result
-  }
-
-  /** Returns the iterable wihtout its rightmost <code>n</code> elements.
-   *
-   *  @param n the number of elements to take
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def dropRight(n: Int): CC[A] = {
-    val b = newBuilder[A]
-    val lead = elements drop n
-    breakable {
-      for (x <- this) {
-        if (!lead.hasNext) break
-        lead.next
-        b += x
-      }
-    }
-    b.result
-  }
-
   /** Split the iterable at a given point and return the two parts thus
    *  created.
    *
@@ -732,71 +662,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
     (l.result, r.result)
   }
 
-  /** Returns the longest prefix of this iterable whose elements satisfy
-   *  the predicate <code>p</code>.
-   *
-   *  @param p the test predicate.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def takeWhile(p: A => Boolean): CC[A] = {
-    val b = newBuilder[A]
-    breakable {
-      for (x <- this) {
-        if (!p(x)) break
-        b += x
-      }
-    }
-    b.result
-  }
-
-  /** Returns the longest suffix of this iterable whose first element
-   *  does not satisfy the predicate <code>p</code>.
-   *
-   *  @param p the test predicate.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def dropWhile(p: A => Boolean): CC[A] = {
-    val b = newBuilder[A]
-    var go = false
-    for (x <- this) {
-      if (go) b += x
-      else if (!p(x)) { go = true; b += x }
-    }
-    b.result
-  }
-
- /** Returns a pair consisting of the longest prefix of the iterable whose
-   *  elements all satisfy the given predicate, and the rest of the iterable.
-   *
-   *  @param p the test predicate
-   *  @return  a pair consisting of the longest prefix of the iterable whose
-   *           elements all satisfy <code>p</code>, and the rest of the iterable.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def span(p: A => Boolean): (CC[A], CC[A]) = {
-    val l, r = newBuilder[A]
-    var toLeft = true
-    for (x <- this) {
-      toLeft = toLeft && p(x)
-      (if (toLeft) l else r) += x
-    }
-    (l.result, r.result)
-  }
-
-  /** Checks if the other iterable object contains the same elements as this one.
-   *
-   *  @note will not terminate for infinite-sized iterables.
-   *  @param that  the other iterable
-   *  @return true, iff both iterables contain the same elements.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def sameElements[B >: A](that: OrderedIterable[B]): Boolean = {
-    val these = this.elements
-    val those = that.elements
-    while (these.hasNext && those.hasNext && these.next() == those.next()) {}
-    !these.hasNext && !those.hasNext
-  }
-
   /** A sub-iterable view  starting at index `from`
    *  and extending up to (but not including) index `until`.
    *
diff --git a/src/library/scalax/collection/generic/IterableView.scala b/src/library/scalax/collection/generic/IterableView.scala
index 45a0a50be2..bb111e2252 100755
--- a/src/library/scalax/collection/generic/IterableView.scala
+++ b/src/library/scalax/collection/generic/IterableView.scala
@@ -25,7 +25,7 @@ trait IterableView[+UC[/*+*/B] <: Iterable[B], /*+*/A] extends Iterable[A] { sel
     case _ => origin
   }
 
-  private def isDelay = elements eq underlying.elements
+  protected def isDelay = elements eq underlying.elements
 
   private[this] var forced: UC[A] = _
   private[this] var wasForced = false
@@ -100,15 +100,6 @@ trait IterableView[+UC[/*+*/B] <: Iterable[B], /*+*/A] extends Iterable[A] { sel
   /** Non-strict variant of @see Iterable.slice */
   override def slice(from: Int, until: Int): IterableView[UC, A] = newView(elements slice (from, until))
 
-  /** Non-strict variant of @see Iterable.takeWhile */
-  override def takeWhile(p: A => Boolean): IterableView[UC, A] = newView(elements takeWhile p)
-
-  /** Non-strict variant of @see Iterable.dropWhile */
-  override def dropWhile(p: A => Boolean): IterableView[UC, A] = newView(elements dropWhile p)
-
-  /** Non-strict variant of @see Iterable.span */
-  override def span(p: A => Boolean): (IterableView[UC, A], IterableView[UC, A]) = (takeWhile(p), dropWhile(p))
-
   /** The projection resulting from the concatenation of this projection with the <code>rest</code> projection.
    *  @param rest   The projection that gets appended to this projection
    *  @deprecated   Use ++ instead
diff --git a/src/library/scalax/collection/LazyBuilder.scala b/src/library/scalax/collection/generic/LazyBuilder.scala
index 185930a916..74764351b6 100755
--- a/src/library/scalax/collection/LazyBuilder.scala
+++ b/src/library/scalax/collection/generic/LazyBuilder.scala
@@ -8,7 +8,7 @@
 
 // $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $
 
-package scalax.collection
+package scalax.collection.generic
 
 import collection.mutable.ListBuffer
 import collection.immutable.{List, Nil, ::}
@@ -18,7 +18,7 @@ abstract class LazyBuilder[+CC[B], A] extends Builder[CC, A] {
   def +=(x: A) = { parts += Iterator.single(x) }
   override def ++=(xs: Iterator[A]) { parts += xs }
   override def ++=(xs: Iterable[A]) { parts += xs.elements }
-  def elements: Iterator[A] = Iterator.iteratorIteratorWrapper(parts.elements).flatten // !!! drop the wrapper and get an error
+  def elements: Iterator[A] = Iterator.iteratorIteratorWrapper(parts.elements).flatten // !!! can remove the wrapper once new compiler is in starr
   def result: CC[A]
   def clear() { parts.clear() }
 }
diff --git a/src/library/scalax/collection/generic/MapFactory.scala b/src/library/scalax/collection/generic/MapFactory.scala
new file mode 100755
index 0000000000..d7413b8928
--- /dev/null
+++ b/src/library/scalax/collection/generic/MapFactory.scala
@@ -0,0 +1,9 @@
+package scalax.collection.generic
+
+trait MapFactory[CC[A, B] <: MapTemplate[A, B, CC]] {
+
+  def empty[A, B]: CC[A, B]
+
+  def apply[A, B](elems: (A, B)*): CC[A, B] = empty[A, B] ++ elems.asInstanceOf[Iterable[(A, B)]] // !@!
+
+}
diff --git a/src/library/scalax/collection/generic/MapTemplate.scala b/src/library/scalax/collection/generic/MapTemplate.scala
new file mode 100755
index 0000000000..6d1a9e3c93
--- /dev/null
+++ b/src/library/scalax/collection/generic/MapTemplate.scala
@@ -0,0 +1,247 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Map.scala 16884 2009-01-09 16:52:09Z cunei $
+
+
+package scalax.collection.generic
+
+import collection.immutable.Set
+import collection.mutable.ArrayBuffer
+import annotation.unchecked.uncheckedVariance
+
+/** <p>
+*     A map is a collection that maps each key to one or zero values.
+ *  </p>
+ *  <p>
+ *    This trait provides a limited interface, only allowing reading of elements.
+ *    There are two extensions of this trait, in packages
+ *    <code><a href="mutable$content.html" target="contentFrame">
+ *    scala.collection.mutable</a></code>
+ *    and <code><a href="immutable$content.html" target="contentFrame">
+ *    scala.collection.immutable</a></code>, which provide functionality for
+ *    adding new key/value mappings to a map. The trait in the first package is
+ *    for maps that are modified destructively, whereas the trait in
+ *    the second package is for immutable maps which create a new map
+ *    when something is added or removed from them.
+ *  </p>
+ *
+ *  @author  Matthias Zenger
+ *  @author  Martin Odersky
+ *  @version 1.2, 31/12/2006
+ */
+trait MapTemplate[A, B, +CC[A1, B1] <: Map[A1, B1] with MapTemplate[A1, B1, CC]]
+  extends PartialFunction[A, B]
+     with SizedIterable[(A, B)]
+     with Addable[CC[A, B], (A, B)]
+     with Subtractable[CC[A, B], A] {
+self: CC[A, B] =>
+
+  def newBuilder[B]: Builder[SizedIterable, B] = new ArrayBuffer[B]
+
+  override def thisCC: CC[A, B] = this
+
+  /** This method returns a new map instance of the same class
+   *  mapping keys of the same type to values of type <code>C</code>.
+   */
+  def empty[C]: CC[A, C]
+
+  /** Compute the number of key-to-value mappings.
+   *
+   *  @return the number of mappings
+   */
+  def size: Int
+
+  /** Check if this map maps <code>key</code> to a value and return the
+   *  value if it exists.
+   *
+   *  @param  key the key of the mapping of interest
+   *  @return     the value of the mapping, if it exists
+   */
+  def get(key: A): Option[B]
+
+  /** Check if this map maps <code>key</code> to a value.
+    *  Return that value if it exists, otherwise return <code>default</code>.
+    */
+  def getOrElse[B2 >: B](key: A, default: => B2): B2 =
+    get(key) match {
+      case Some(v) => v
+      case None => default
+    }
+
+  /** Is this an empty map?
+   *
+   *  @return <code>true</code> iff the map is empty.
+   */
+  override def isEmpty: Boolean = size == 0
+
+  /** Retrieve the value which is associated with the given key. This
+   *  method throws an exception if there is no mapping from the given
+   *  key to a value.
+   *
+   *  @param  key the key
+   *  @return     the value associated with the given key.
+   */
+  def apply(key: A): B = get(key) match {
+    case None => default(key)
+    case Some(value) => value
+  }
+
+  /** Is the given key mapped to a value by this map?
+   *
+   *  @param key the key
+   *  @return    <code>true</code> iff there is a mapping for key in this map
+   */
+  def contains(key: A): Boolean = get(key) match {
+    case None => false
+    case Some(_) => true
+  }
+
+  /** Does this map contain a mapping from the given key to a value?
+   *
+   *  @param key the key
+   *  @return    <code>true</code> iff there is a mapping for key in this map
+   */
+  def isDefinedAt(key: A) = contains(key)
+
+  /** Creates an iterator for all keys.
+   *
+   *  @return an iterator over all keys.
+   */
+  def keys: Iterator[A] = new Iterator[A] {
+    val iter = self.elements
+    def hasNext = iter.hasNext
+    def next = iter.next._1
+  }
+
+  /** @return the keys of this map as a set.
+   */
+  def keySet: Set[A] = new Set[A] {
+    def size = self.size
+    def contains(key : A) = self.contains(key)
+    def elements = self.elements.map(_._1)
+    def + (elem: A): Set[A] = immutable.Set[A]() ++ this + elem
+    def - (elem: A): Set[A] = immutable.Set[A]() ++ this - elem
+    override def newBuilder[B]: Builder[Set, B] = Set.newBuilder[B]
+  }
+
+  /** Creates an iterator for a contained values.
+   *
+   *  @return an iterator over all values.
+   */
+  def values: Iterator[B] = new Iterator[B] {
+    val iter = self.elements
+    def hasNext = iter.hasNext
+    def next = iter.next._2
+  }
+
+  /** Creates a string representation for this map.
+   *
+   *  @return    a string showing all mappings
+   */
+  override def toString() =
+    elements.toList.map(kv => kv._1 + " -> " + kv._2).mkString(stringPrefix + "(", ", ", ")")
+
+  /** The default value for the map, returned when a key is not found
+   *  The method implemented here yields an error,
+   *  but it might be overridden in subclasses.
+   *
+   *  @param key the given key value
+   *  @throws Predef.NoSuchElementException
+   */
+  def default(key: A): B =
+    throw new NoSuchElementException("key not found: " + key)
+
+/*
+  override def view: Map.View[A,B] = new Map.View[A, B] {
+    override def elements = self.elements
+    override def size = self.size
+    override def get(key: A): Option[B] = self.get(key)
+  }
+*/
+  def filterKeys(p: A => Boolean) = new MapView[CC, A, B] {
+    val origin = self
+    override def foreach(f: ((A, B)) => Unit): Unit = for (kv <- self) if (p(kv._1)) f(kv)
+    def elements = self.elements.filter(kv => p(kv._1))
+    def size = { var sz = 0; foreach(_ => sz += 1); sz }
+    override def contains(key: A) = self.contains(key) && p(key)
+    def get(key: A) = if (!p(key)) None else self.get(key)
+  }
+
+  def mapElements[C](f: B => C) = new MapView[CC, A,C] {
+    val origin = self
+    override def foreach(g: ((A, C)) => Unit): Unit = for ((k, v) <- self) g((k, f(v)))
+    def elements = for ((k, v) <- self.elements) yield (k, f(v))
+    def size = self.size
+    override def contains(key: A) = self.contains(key)
+    def get(key: A) = self.get(key).map(f)
+  }
+
+  /** Defines the prefix of this object's <code>toString</code> representation.
+   */
+  override def stringPrefix: String = "Map"
+
+  /** Add a key/value pair to this map.
+   *  @param    key the key
+   *  @param    value the value
+   *  @return   A new map with the new binding added to this map
+   */
+  def update (key: A, value: B): CC[A, B]
+
+  /** Add a key/value pair to this map.
+   *  @param    kv the key/value pair.
+   *  @return   A new map with the new binding added to this map
+   */
+  def + (kv: (A, B)): CC[A, B] = update(kv._1, kv._2)
+
+  /** Remove a key from this map
+   *  @param    key the key to be removed
+   *  @return   If the map does not contain a binding for <code>key</code>
+   *            it is returned unchanged. Otherwise, return a new map
+   *            without a binding for <code>key</code>
+   */
+  def - (key: A): CC[A, B]
+
+  /** This function transforms all the values of mappings contained
+   *  in this map with function <code>f</code>.
+   *
+   *  @param f A function over keys and values
+   *  @return  the updated map
+   */
+  def transform[C](f: (A, B) => C): CC[A, C] = {
+    var res = empty[C]
+    for ((key, value) <- this) res += ((key, f(key, value)))
+    res
+  }
+
+  /** Builds a new map with all key/value pairs of this map
+   *  for which the predicate <code>p</code> returns <code>true</code>.
+   *
+   *  @param p A predicate over key-value pairs
+   *  @return  the updated map
+   */
+  override def filter(p: ((A, B)) => Boolean): CC[A, B] = {
+    var res = empty[B]
+    for (kv <- this)
+      if (p(kv)) res += kv
+    res
+  }
+
+  /** Removes all the mappings for which the predicate
+   *  <code>p</code> returns <code>false</code>.
+   *
+   *  @param p A predicate over key-value pairs
+   *  @return  the updated map
+   */
+  override def remove(p: ((A, B)) => Boolean): CC[A, B] = {
+    var res = this
+    for (kv <- this)
+      if (!p(kv)) res -= kv._1
+    res
+  }
+}
diff --git a/src/library/scalax/collection/generic/MapView.scala b/src/library/scalax/collection/generic/MapView.scala
new file mode 100644
index 0000000000..924fd1173e
--- /dev/null
+++ b/src/library/scalax/collection/generic/MapView.scala
@@ -0,0 +1,44 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+package scalax.collection.generic
+
+/** A non-strict view of a map.
+ * @author Martin Odersky
+ * @version 2.8
+ */
+trait MapView[+UC[A1, B1] <: MapTemplate[A1, B1, UC] with Map[A1, B1], A, B] extends Map[A, B] { self =>
+
+  val origin: Map[A, _]
+
+  def empty[C] = origin.empty[C]
+
+  def elements: Iterator[(A, B)]
+
+  val underlying: Map[A, _] = origin match {
+    case v: MapView[t, _, _] => v.underlying
+    case _ => origin
+  }
+  private[this] var forced: UC[A, B] = _
+  private[this] var wasForced = false
+
+  def force: UC[A, B] = {
+    if (!wasForced) {
+      forced = underlying.empty[B].asInstanceOf[UC[A, B]] ++ elements
+      wasForced = true
+    }
+    forced
+  }
+
+  def update (key: A, value: B): UC[A, B] = force update (key, value)
+  def - (key: A): UC[A, B] = force - key
+}
+
+
diff --git a/src/library/scalax/collection/generic/MutableVectorTemplate.scala b/src/library/scalax/collection/generic/MutableVectorTemplate.scala
new file mode 100755
index 0000000000..71c3f7bdf8
--- /dev/null
+++ b/src/library/scalax/collection/generic/MutableVectorTemplate.scala
@@ -0,0 +1,56 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2006-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Vector.scala 15437 2008-06-25 16:22:45Z stepancheg $
+
+package scalax.collection.generic
+
+import collection.mutable.Vector
+import collection.mutable.Vector._
+
+/** Sequences that support O(1) element access and O(1) length computation.
+ *  plus an update operation.
+ *  @author Sean McDirmid
+ *  @author Martin Odersky
+ *  @version 2.8
+ */
+trait MutableVectorTemplate[+CC[B] <: MutableVectorTemplate[CC, B] with Vector[B], A] extends VectorTemplate[CC, A] {
+self =>
+
+  def update(idx: Int, elem: A)
+
+  /** Creates a view of this iterable @see OrderedIterable.View
+   */
+  override def view: MutableVectorView[CC, A] = new MutableVectorView[CC, A] { // !!! Martin: We should maybe infer the type parameters here?
+    val origin: Vector[_] = thisCC
+    val length: Int = self.length
+    def apply(idx: Int): A = self.apply(idx)
+    def update(idx: Int, elem: A) = self.update(idx, elem)
+  }
+
+  /** A sub-sequence view  starting at index `from`
+   *  and extending up to (but not including) index `until`.
+   *
+   *  @param from   The index of the first element of the slice
+   *  @param until  The index of the element following the slice
+   *  @note  The difference between `view` and `slice` is that `view` produces
+   *         a view of the current sequence, whereas `slice` produces a new sequence.
+   *
+   *  @note view(from, to)  is equivalent to view.slice(from, to)
+   */
+  override def view(from: Int, until: Int): MutableVectorView[CC, A] = view.slice(from, until)
+
+  def readOnly: collection.Vector[A] = new collection.Vector[A] { //!!! just use a VectorProxy?
+    def length = self.length
+    def apply(idx : Int) = self.apply(idx)
+    def newBuilder[B]: Builder[collection.Vector, B] = self.newBuilder[B] //mapResult (_.readOnly)
+    override def foreach(f: A => Unit) = self.foreach(f)
+    override def stringPrefix = self.stringPrefix+"RO"
+  }
+}
+
diff --git a/src/library/scalax/collection/generic/MutableVectorView.scala b/src/library/scalax/collection/generic/MutableVectorView.scala
new file mode 100755
index 0000000000..450943f61d
--- /dev/null
+++ b/src/library/scalax/collection/generic/MutableVectorView.scala
@@ -0,0 +1,95 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Sequence.scala 16092 2008-09-12 10:37:06Z nielsen $
+
+
+package scalax.collection.generic
+
+import collection.mutable.Vector
+import collection.mutable.Vector._
+
+/** A non-strict projection of an iterable.
+ * @author Sean McDirmid
+ * @author Martin Odersky
+ * @note this should really be a virtual class of SequenceFactory
+ */
+trait MutableVectorView[+UC[B] <: Vector[B], A] extends SequenceView[UC, A] with Vector[A] {
+self =>
+
+  /** refined from Iterable.View */
+  val origin: Vector[_]
+
+  trait Transformed[B] extends super.Transformed[B] with MutableVectorView[UC, B] {
+    override val origin = self
+    override def elements: Iterator[B] = new Elements(0, length)
+    override protected def asCC = asInstanceOf[MutableVectorView[UC, B]]
+  }
+
+  class Appended(that: Vector[A]) extends super.Appended[A](that) with Transformed[A] {
+    override def update(idx: Int, elem: A)  {
+      val ll = self.length
+      if (idx < ll) self.update(idx, elem) else that.update(idx - ll, elem)
+    }
+  }
+
+  class Sliced(from: Int, to: Int) extends super.Sliced(from, to) with Transformed[A] {
+    override def update(idx: Int, elem: A) {
+      if (idx >= 0 && idx < length) self.update(idx + from, elem)
+      else throw new IndexOutOfBoundsException(idx.toString)
+    }
+    override def slice(from1: Int, to1: Int) =
+      new self.Sliced(from + (from1 min length max 0) , to + (to1 min length max 0))
+  }
+
+  class Reversed extends super.Reversed with Transformed[A] {
+    override def update(idx: Int, elem: A) {
+      self.update(length - 1 - idx, elem)
+    }
+  }
+
+  class Zipped[B](that: Vector[B]) extends super.Zipped[B](that) with Transformed[(A, B)] {
+    override def update(idx: Int, elem: (A, B)) {
+      self.update(idx, elem._1)
+      that.update(idx, elem._2)
+    }
+  }
+
+  def ++(that: Vector[A]): MutableVectorView[UC, A] =
+    new Appended(that).asCC
+
+  override def reverse: MutableVectorView[UC, A] =
+    (new Reversed).asCC
+
+  private def toVector[B](xs: Iterable[B]): Vector[B] = xs match {
+    case ras: Vector[_] => ras.asInstanceOf[Vector[B]]
+    case _ => Vector() ++ xs
+  }
+
+  override def zip[B](that: Iterable[B]): MutableVectorView[UC, (A, B)] =
+    new Zipped(toVector(that)).asCC
+
+  override def zipWithIndex: MutableVectorView[UC, (A, Int)] =
+    zip((0 until length).asInstanceOf[Null]) // !@!
+  override def take(n: Int): MutableVectorView[UC, A] =
+    slice(0, n)
+  override def drop(n: Int): MutableVectorView[UC, A] =
+    slice(n, Math.MAX_INT)
+  override def splitAt(n: Int): (MutableVectorView[UC, A], MutableVectorView[UC, A]) = (take(n), drop(n))
+  override def slice(from: Int, until: Int): MutableVectorView[UC, A] =
+    new Sliced(from, until).asCC
+  override def takeWhile(p: A => Boolean): MutableVectorView[UC, A] =
+    take(prefixLength(p))
+  override def dropWhile(p: A => Boolean): MutableVectorView[UC, A] =
+    drop(prefixLength(p))
+  override def span(p: A => Boolean): (MutableVectorView[UC, A], MutableVectorView[UC, A]) = {
+    val n = prefixLength(p)
+    (take(n), drop(n))
+  }
+}
+
diff --git a/src/library/scalax/collection/generic/OrderedIterableForwarder.scala b/src/library/scalax/collection/generic/OrderedIterableForwarder.scala
new file mode 100755
index 0000000000..643f31d861
--- /dev/null
+++ b/src/library/scalax/collection/generic/OrderedIterableForwarder.scala
@@ -0,0 +1,37 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: IterableProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $
+
+
+package scalax.collection.generic
+
+/** This trait implements a forwarder for iterable objects. It forwards
+ *  all calls to a different iterable object, except for
+ *
+ *    - toString, hashCode, equals, stringPrefix
+ *    - newBuilder, view
+ *    - all calls creating a new iterable object of the same kind
+ *
+ *  The above methods are forwarded by subclass IterableProxy
+ *
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+trait OrderedIterableForwarder[+A] extends OrderedIterable[A] with IterableForwarder[A] {
+
+  /** The iterable object to which calls are forwarded */
+  protected def underlying: OrderedIterable[A]
+
+  // Iterable delegates
+  // Iterable methods could be printed by  cat IterableTemplate.scala | sed -n '/trait Iterable/,$ p' | egrep '^  (override )?def'
+
+  override def last: A = underlying.last
+  override def lastOption: Option[A] = underlying.lastOption
+  override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that)
+}
diff --git a/src/library/scalax/collection/generic/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/OrderedIterableTemplate.scala
index 9e61daa418..501cbf6447 100755
--- a/src/library/scalax/collection/generic/OrderedIterableTemplate.scala
+++ b/src/library/scalax/collection/generic/OrderedIterableTemplate.scala
@@ -13,6 +13,8 @@ package scalax.collection.generic
 
 import OrderedIterable._
 
+import util.control.Breaks._
+
 /** Ordered iterables are iterables where the `elements` method always returns elements in the same
  *  order (namely the order in which elements were appended to the iterable). In particular, one has
  *  for every two ordered iterables `xs` and `ys`:
@@ -20,4 +22,140 @@ import OrderedIterable._
  *  `(xs ++ ys).elements = xs.elements ++ ys.elements
  */
 trait OrderedIterableTemplate[+CC[/*+*/B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], /*+*/A]
-  extends IterableTemplate[CC, A]
+  extends IterableTemplate[CC, A] {
+
+  /** The last element of this iterable.
+   *
+   *  @throws Predef.NoSuchElementException if the iterable is empty.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def last: A = {
+    var lst = head
+    for (x <- this)
+      lst = x
+    lst
+  }
+
+  /** Returns as an option the last element of this iterable or
+   *  <code>None</code> if iterable is empty.
+   *
+   *  @return the last element as an option.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def lastOption: Option[A] = if (isEmpty) None else Some(last)
+
+  /** An iterable consisting of all elements of this iterable except the last one.
+   *  @throws Predef.UnsupportedOperationException if the stream is empty.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def init: CC[A] = {
+    if (isEmpty) throw new UnsupportedOperationException("empty.init")
+    var lst = head
+    val b = newBuilder[A]
+    for (x <- this) {
+      b += lst
+      lst = x
+    }
+    b.result
+  }
+
+  /** Returns the rightmost <code>n</code> elements from this iterable.
+   *
+   *  @param n the number of elements to take
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def takeRight(n: Int): CC[A] = {
+    val b = newBuilder[A]
+    val lead = elements drop n
+    var go = false
+    for (x <- this) {
+      if (go) b += x
+      else if (lead.hasNext) lead.next
+      else go = true
+    }
+    b.result
+  }
+
+  /** Returns the iterable wihtout its rightmost <code>n</code> elements.
+   *
+   *  @param n the number of elements to take
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def dropRight(n: Int): CC[A] = {
+    val b = newBuilder[A]
+    val lead = elements drop n
+    breakable {
+      for (x <- this) {
+        if (!lead.hasNext) break
+        lead.next
+        b += x
+      }
+    }
+    b.result
+  }
+
+  /** Returns the longest prefix of this iterable whose elements satisfy
+   *  the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def takeWhile(p: A => Boolean): CC[A] = {
+    val b = newBuilder[A]
+    breakable {
+      for (x <- this) {
+        if (!p(x)) break
+        b += x
+      }
+    }
+    b.result
+  }
+
+  /** Returns the longest suffix of this iterable whose first element
+   *  does not satisfy the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def dropWhile(p: A => Boolean): CC[A] = {
+    val b = newBuilder[A]
+    var go = false
+    for (x <- this) {
+      if (go) b += x
+      else if (!p(x)) { go = true; b += x }
+    }
+    b.result
+  }
+
+ /** Returns a pair consisting of the longest prefix of the iterable whose
+   *  elements all satisfy the given predicate, and the rest of the iterable.
+   *
+   *  @param p the test predicate
+   *  @return  a pair consisting of the longest prefix of the iterable whose
+   *           elements all satisfy <code>p</code>, and the rest of the iterable.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def span(p: A => Boolean): (CC[A], CC[A]) = {
+    val l, r = newBuilder[A]
+    var toLeft = true
+    for (x <- this) {
+      toLeft = toLeft && p(x)
+      (if (toLeft) l else r) += x
+    }
+    (l.result, r.result)
+  }
+
+  /** Checks if the other iterable object contains the same elements as this one.
+   *
+   *  @note will not terminate for infinite-sized iterables.
+   *  @param that  the other iterable
+   *  @return true, iff both iterables contain the same elements.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def sameElements[B >: A](that: OrderedIterable[B]): Boolean = {
+    val these = this.elements
+    val those = that.elements
+    while (these.hasNext && those.hasNext && these.next() == those.next()) {}
+    !these.hasNext && !those.hasNext
+  }
+}
diff --git a/src/library/scalax/collection/generic/OrderedIterableView.scala b/src/library/scalax/collection/generic/OrderedIterableView.scala
new file mode 100755
index 0000000000..fd04daa0b6
--- /dev/null
+++ b/src/library/scalax/collection/generic/OrderedIterableView.scala
@@ -0,0 +1,85 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+package scalax.collection.generic
+
+/** A non-strict projection of an iterable.
+ * @author Sean McDirmid
+ * @author Martin Odersky
+ * @note this should really be a virtual class of SequenceFactory
+ */
+trait OrderedIterableView[+UC[/*+*/B] <: Iterable[B], /*+*/A] extends IterableView[UC, A] with OrderedIterable[A] { self =>
+
+  val origin: OrderedIterable[_]
+
+  /** Builds a new view object. This method needs to be overridden in subclasses
+   *  which refine in IterableView type
+   */
+  protected override def newView[B](elems: Iterator[B]) = new OrderedIterableView[UC, B] {
+    val origin = if (self.isDelay) self.origin else self
+    val elements = elems
+  }
+
+  /** Non-strict variant of @see IterableLike.++ */
+  override def ++[B >: A](that: Iterator[B]): OrderedIterableView[UC, B] = newView(elements ++ that)
+
+  /** Non-strict variant of @see IterableLike.++ */
+  override def ++[B >: A](that: Iterable[B]): OrderedIterableView[UC, B] = newView(elements ++ that.elements)
+
+  /** Non-strict variant of @see IterableLike.map */
+  override def map[B](f: A => B): OrderedIterableView[UC, B] = newView(elements map f)
+
+  /** Non-strict variant of @see IterableLike.flatMap */
+  override def flatMap[B](f: A => Iterable[B]): OrderedIterableView[UC, B] = newView(elements flatMap (f(_).elements))
+
+  /** Non-strict variant of @see IterableLike.filter */
+  override def filter(p: A => Boolean): OrderedIterableView[UC, A] = newView(elements filter p)
+
+  /** Non-strict variant of @see IterableLike.partition */
+  override def partition(p: A => Boolean): (OrderedIterableView[UC, A], OrderedIterableView[UC, A]) = {
+    val (li, ri) = elements partition p
+    (newView(li), newView(ri))
+  }
+
+  /** Non-strict variant of @see IterableLike.zip */
+  override def zip[B](other: Iterable[B]): OrderedIterableView[UC, (A, B)] = newView(elements zip other.elements)
+
+  /** Non-strict variant of @see IterableLike.zipWithIndex */
+  override def zipWithIndex: OrderedIterableView[UC, (A, Int)] = newView(elements.zipWithIndex)
+
+  /* Non-strict variant of @see IterableLike.zipAll
+   *  This is not enabled because it can't be specialized in VectorView:
+   *  VectorView is not covariant, yet must maintain updatability. Impossible to do this
+   *  with this type signature.
+  override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): OrderedIterableView[UC, (A1, B1)] =
+    newView(elements zipAll (that.elements, thisElem, thatElem))
+   */
+
+  /** Non-strict variant of @see Iterable.take */
+  override def take(n: Int): OrderedIterableView[UC, A] = newView(elements take n)
+
+  /** Non-strict variant of @see Iterable.drop */
+  override def drop(n: Int): OrderedIterableView[UC, A] = newView(elements drop n)
+
+  /** Non-strict variant of @see Iterable.splitAt */
+  override def splitAt(n: Int): (OrderedIterableView[UC, A], OrderedIterableView[UC, A]) = (take(n), drop(n))
+
+  /** Non-strict variant of @see Iterable.slice */
+  override def slice(from: Int, until: Int): OrderedIterableView[UC, A] = newView(elements slice (from, until))
+
+  /** Non-strict variant of @see Iterable.takeWhile */
+  override def takeWhile(p: A => Boolean): OrderedIterableView[UC, A] = newView(elements takeWhile p)
+
+  /** Non-strict variant of @see Iterable.dropWhile */
+  override def dropWhile(p: A => Boolean): OrderedIterableView[UC, A] = newView(elements dropWhile p)
+
+  /** Non-strict variant of @see Iterable.span */
+  override def span(p: A => Boolean): (OrderedIterableView[UC, A], OrderedIterableView[UC, A]) = (takeWhile(p), dropWhile(p))
+}
diff --git a/src/library/scalax/collection/generic/SetFactory.scala b/src/library/scalax/collection/generic/SetFactory.scala
index 0fbcf68466..458d4bbade 100644
--- a/src/library/scalax/collection/generic/SetFactory.scala
+++ b/src/library/scalax/collection/generic/SetFactory.scala
@@ -6,4 +6,6 @@ trait SetFactory[CC[A] <: SetTemplate[CC, A] with Set[A]] extends IterableFactor
 
   def apply[A](elems: A*): CC[A] = empty[A] ++ elems.asInstanceOf[Iterable[A]] // !@!
 
+  override def newBuilder[B]: Builder[CC, B] = new AddableBuilder[CC, B](empty)
+
 }
diff --git a/src/library/scalax/collection/generic/SetTemplate.scala b/src/library/scalax/collection/generic/SetTemplate.scala
index 9c3056cc04..bd94f10fc0 100755
--- a/src/library/scalax/collection/generic/SetTemplate.scala
+++ b/src/library/scalax/collection/generic/SetTemplate.scala
@@ -31,7 +31,12 @@ package scalax.collection.generic
  *  @author  Martin Odersky
  *  @version 2.8
  */
-trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boolean) with SizedIterable[A] with OrderedIterableTemplate[CC, A] {
+trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A]
+  extends (A => Boolean)
+     with SizedIterable[A]
+     with IterableTemplate[CC, A]
+     with Addable[CC[A], A]
+     with Subtractable[CC[A], A] {
 
   /** Returns the number of elements in this set.
    *
@@ -52,13 +57,13 @@ trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boo
 
   /** Create a new set with an additional element.
    */
-  def +(elem: A): CC[A]
+  def + (elem: A): CC[A]
 
   /** Remove a single element from a set.
    *  @param elem the element to be removed
    *  @return a new set with the element removed.
    */
-  def -(elem: A): CC[A]
+  def - (elem: A): CC[A]
 
   /** Checks if this set is empty.
    *
@@ -76,43 +81,6 @@ trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boo
    */
   def apply(elem: A): Boolean = contains(elem)
 
-  /** Add two or more elements to this set.
-   *  @param    elem1 the first element.
-   *  @param    elem2 the second element.
-   *  @param    elems the remaining elements.
-   *  @return a new set with the elements added.
-   */
-  def + (elem1: A, elem2: A, elems: A*): CC[A] = {
-    thisCC + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]]
-  }
-
-  /** Remove two or more elements from this set.
-   *
-   *  @param    elem1 the first element.
-   *  @param    elem2 the second element.
-   *  @param    elems the remaining elements.
-   *  @return a new set with the elements removed.
-   */
-  def - (elem1: A, elem2: A, elems: A*): CC[A] =
-    this - elem1 - elem2 -- elems.asInstanceOf[Iterable[A]]
-
-  /** Remove all the elements provided by an iterator
-   *  of the iterable object <code>elems</code> from the set.
-   *
-   *  @param elems An iterable object containing the elements to remove from the set.
-   *  @return a new set with the elements removed.
-   */
-  def -- (elems: Iterable[A]): CC[A] = this -- elems.elements
-
-  /** Remove all the elements provided by an iterator
-   *  <code>elems</code> from the set.
-   *
-   *  @param elems An iterator containing the elements to remove from the set.
-   *  @return a new set with the elements removed.
-   */
-  def -- (elems: Iterator[A]): CC[A] =
-    (thisCC /: elems) (_ - _)
-
   /** This method computes an intersection with set <code>that</code>.
    *  It removes all the elements that are not present in <code>that</code>.
    *
@@ -137,6 +105,9 @@ trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boo
    */
   def subsetOf(that: Set[A]): Boolean = forall(that.contains)
 
+/* What a mess! We need to remove these methods, but can't without breaking
+ * existing code. What to do?
+
   /** Compares this set with another object and returns true, iff the
    *  other object is also a set which contains the same elements as
    *  this set.
@@ -156,18 +127,22 @@ trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boo
       false
   }
 
-  /*  @deprecated hashCode is not stable for mutable sets.
-   *              if you intend to have object identity hashCode and wish the deprecated warning
+  /*  @deprecated Since the previous hashCode is not stable for mutable sets,
+   *              the implementation of this method has been changed to
+   *              standard address-based hashCode from java.lang.Object.
+   *              If you relied on the old behavior, y
+   *              IT has been
+   *  if you intend to have object identity hashCode and wish the deprecated warning
    *              to go away, cast this set to AnyRef before calling hashCode.
    */
   @deprecated override def hashCode() =
     (0 /: this)((hash, e) => hash + e.hashCode())
-
+*/
   /** Defines the prefix of this object's <code>toString</code> representation.
    */
   override def stringPrefix: String = "Set"
 
   /** Need to override string, so that it's not the Function1's string that gets mixed in.
    */
-  override def toString = super[OrderedIterableTemplate].toString
+  override def toString = super[IterableTemplate].toString
 }
diff --git a/src/library/scalax/collection/generic/Shrinkable.scala b/src/library/scalax/collection/generic/Shrinkable.scala
new file mode 100755
index 0000000000..e6d3b085f3
--- /dev/null
+++ b/src/library/scalax/collection/generic/Shrinkable.scala
@@ -0,0 +1,54 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+package scalax.collection.generic
+
+/** This class represents collections that can be reduced using a -= operator.
+ *
+ *  @autor   Martin Odersky
+ *  @owner   Martin Odersky
+ *  @version 2.8
+ */
+trait Shrinkable[A] {
+
+  /** Removes a single element from this collection.
+   *
+   *  @param elem  the element to remove.
+   */
+  def -=(elem: A): Unit
+
+  /** Removes two or more elements from this collection.
+   *
+   *  @param elem1 the first element to remove.
+   *  @param elem2 the second element to remove.
+   *  @param elems the remaining elements to remove.
+   */
+  def -=(elem1: A, elem2: A, elems: A*) {
+    this -= elem1
+    this -= elem2
+    this --= elems.asInstanceOf[Iterable[A]] // !@!
+  }
+
+  /** Removes a number of elements provided by an iterator from this collection.
+   *
+   *  @param iter  the iterator.
+   */
+  def --=(iter: collection.Iterator[A]) { iter foreach -= }
+
+  /** Removes a number of elements provided by an iterable object from this collection.
+   *
+   *  @param iter  the iterable object.
+   */
+  def --=(iter: collection.Iterable[A]) { iter foreach -= }
+}
+
+
+
+
diff --git a/src/library/scalax/collection/generic/Subtractable.scala b/src/library/scalax/collection/generic/Subtractable.scala
new file mode 100755
index 0000000000..93fe2f8190
--- /dev/null
+++ b/src/library/scalax/collection/generic/Subtractable.scala
@@ -0,0 +1,64 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+package scalax.collection.generic
+
+/** This class represents collections that can be reduced using a -= operator.
+ *
+ *  @autor   Martin Odersky
+ *  @owner   Martin Odersky
+ *  @version 2.8
+ */
+trait Subtractable[+C <: Subtractable[C, A], A] {
+
+  protected def thisCC: C
+
+  /** Removes a single element from this collection and returns
+   *  either the collection itself (if it is mutable), or a new collection
+   *  with the removed element.
+   *
+   *  @param elem  the element to remove.
+   */
+  def -(elem: A): C
+
+  /** Removes two or more elements from this collection and returns
+   *  either the collection itself (if it is mutable), or a new collection
+   *  with the removed elements.
+   *
+   *  @param elem1 the first element to remove.
+   *  @param elem2 the second element to remove.
+   *  @param elems the remaining elements to remove.
+   */
+  def -(elem1: A, elem2: A, elems: A*): C =
+    thisCC - elem1 - elem2 -- elems.asInstanceOf[Iterable[A]] // !@!
+
+  /** Removes a number of elements provided by an iterable object
+   *  via its <code>elements</code> method and returns
+   *  either the collection itself (if it is mutable), or a new collection
+   *  with the removed elements.
+   *
+   *  @param iter     the iterable object.
+   */
+  def --(iter: Iterable[A]): C = (thisCC /: iter) (_ - _)
+
+  /** Removes a number of elements provided by an iterator
+   *  via its <code>elements</code> method and returns
+   *  either the collection itself (if it is mutable), or a new collection
+   *  with the removed elements.
+   *
+   *  @param iter   the iterator
+   */
+  def --(iter: Iterator[A]): C = (thisCC /: iter) (_ - _)
+
+}
+
+
+
+
diff --git a/src/library/scalax/collection/generic/covartest/IterableForwarder.scala b/src/library/scalax/collection/generic/covartest/IterableForwarder.scala
index cd4a754e97..58290cfc68 100755
--- a/src/library/scalax/collection/generic/covartest/IterableForwarder.scala
+++ b/src/library/scalax/collection/generic/covartest/IterableForwarder.scala
@@ -56,6 +56,4 @@ trait IterableForwarder[+A] extends Iterable[A] {
   override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = underlying.addString(b, start, sep, end)
 
   override def head: A = underlying.head
-  override def last: A = underlying.last
-  override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that)
 }
diff --git a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala
index 27772b2ece..791d698a75 100755
--- a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala
+++ b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala
@@ -56,6 +56,11 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
    */
   def newBuilder[B]: Builder[CC, B]
 
+  /** Create a new builder for this IterableType
+   *  with a hint what that its size should be size `sizeHint`
+   */
+  def newBuilder[B](sizeHint: Int): Builder[CC, B] = newBuilder[B]
+
   /** Is this collection empty? */
   def isEmpty: Boolean = !elements.hasNext
 
@@ -65,7 +70,7 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
    */
   def hasDefiniteSize = true
 
-  /** Create a new sequence of type CC which contains all elements of this sequence
+  /** Create a new iterable of type CC which contains all elements of this iterable
    *  followed by all elements of Iterable `that'
    */
   def ++[B >: A](that: Iterable[B]): CC[B] = {
@@ -75,7 +80,7 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
     b.result
   }
 
-  /** Create a new sequence of type IterableType which contains all elements of this sequence
+  /** Create a new iterable of type CC which contains all elements of this iterable
    *  followed by all elements of Iterator `that'
    */
   def ++[B >: A](that: Iterator[B]): CC[B] = {
@@ -85,12 +90,12 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
     b.result
   }
 
-  /** Returns the sequence resulting from applying the given function
-   *  <code>f</code> to each element of this sequence.
+  /** Returns the iterable resulting from applying the given function
+   *  <code>f</code> to each element of this iterable.
    *
    *  @param f function to apply to each element.
    *  @return  <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> if this
-   *           sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
+   *           iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
    */
   def map[B](f: A => B): CC[B] = {
     val b = newBuilder[B]
@@ -99,11 +104,11 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
   }
 
   /** Applies the given function <code>f</code> to each element of
-   *  this sequence, then concatenates the results.
+   *  this iterable, then concatenates the results.
    *
    *  @param f the function to apply on each element.
    *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
-   *           this sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
+   *           this iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
    */
   def flatMap[B](f: A => Iterable[B]): CC[B] = {
     val b = newBuilder[B]
@@ -111,10 +116,10 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
     b.result
   }
 
-  /** Returns all the elements of this sequence that satisfy the
+  /** Returns all the elements of this iterable that satisfy the
    *  predicate <code>p</code>. The order of the elements is preserved.
-   *  @param p the predicate used to filter the list.
-   *  @return the elements of this list satisfying <code>p</code>.
+   *  @param p the predicate used to filter the iterable.
+   *  @return the elements of this iterable satisfying <code>p</code>.
    */
   def filter(p: A => Boolean): CC[A] = {
     val b = newBuilder[A]
@@ -128,7 +133,7 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
    *  predicate inversed.
    *
    *  @param p the predicate to use to test elements
-   *  @return  the list without all elements which satisfy <code>p</code>
+   *  @return  the iterable without all elements which satisfy <code>p</code>
    */
   def remove(p: A => Boolean): CC[A] = filter(!p(_))
 
@@ -203,6 +208,8 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
    *  predicate, if any.
    *
    *  @note may not terminate for infinite-sized collections.
+   *  @note Might return different results for different runs, unless this iterable is ordered, or
+   *        the operator is associative and commutative.
    *  @param p the predicate
    *  @return an option containing the first element in the iterable object
    *  satisfying <code>p</code>, or <code>None</code> if none exists.
@@ -221,8 +228,10 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
    *  the value <code>z</code>.
    *
    *  @note Will not terminate for infinite-sized collections.
+   *  @note Might return different results for different runs, unless this iterable is ordered, or
+   *        the operator is associative and commutative.
    *  @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...),
-   *          a<sub>n</sub>)</code> if the list is
+   *          a<sub>n</sub>)</code> if the iterable is
    *          <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>.
    */
   def foldLeft[B](z: B)(op: (B, A) => B): B = {
@@ -232,32 +241,40 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
     result
   }
 
-  /** Combines the elements of this list together using the binary
+  /** Combines the elements of this iterable together using the binary
    *  function <code>f</code>, from right to left, and starting with
    *  the value <code>z</code>.
    *
    *  @note Will not terminate for infinite-sized collections.
+   *  @note Might return different results for different runs, unless this iterable is ordered, or
+   *        the operator is associative and commutative.
    *  @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code>
-   *          if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>.
+   *          if the iterable is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>.
    */
   def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op)
 
   /** Similar to <code>foldLeft</code> but can be used as
-   *  an operator with the order of list and zero arguments reversed.
+   *  an operator with the order of iterable and zero arguments reversed.
    *  That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code>
    *  @note Will not terminate for infinite-sized collections.
+   *  @note Might return different results for different runs, unless this iterable is ordered, or
+   *        the operator is associative and commutative.
    */
   def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op)
 
   /** An alias for <code>foldRight</code>.
    *  That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code>
    *  @note Will not terminate for infinite-sized collections.
+   *  @note Might return different results for different runs, unless this iterable is ordered, or
+   *        the operator is associative and commutative.
    */
   def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op)
 
   /** Combines the elements of this iterable object together using the binary
    *  operator <code>op</code>, from left to right
    *  @note Will not terminate for infinite-sized collections.
+   *  @note Might return different results for different runs, unless this iterable is ordered, or
+   *        the operator is associative and commutative.
    *  @param op  The operator to apply
    *  @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code>
       if the iterable object has elements
@@ -277,6 +294,8 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
   /** Combines the elements of this iterable object together using the binary
    *  operator <code>op</code>, from right to left
    *  @note Will not terminate for infinite-sized collections.
+   *  @note Might return different results for different runs, unless this iterable is ordered, or
+   *        the operator is associative and commutative.
    *  @param op  The operator to apply
    *
    *  @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code>
@@ -288,7 +307,7 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A]
   def reduceRight[B >: A](op: (A, B) => B): B =
     elements.reduceRight(op)
 
-  /** Returns an iterable formed from this iterable and the specified list
+  /** Returns an iterable formed from this iterable and the specified iterable
    *  `other` by associating each element of the former with
    *  the element at the same position in the latter.
    *  If one of the two iterables is longer than the other, its remaining elements are ignored.
@@ -356,7 +375,7 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
   }
 
   /** Fills the given array <code>xs</code> with at most `len` elements of
-   *  this sequence starting at position `start`.
+   *  this iterable starting at position `start`.
    *  Copying will stop oce either the end of the current iterable is reached or
    *  `len` elements have been copied.
    *
@@ -378,7 +397,7 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
   }
 
   /** Fills the given array <code>xs</code> with the elements of
-   *  this sequence starting at position <code>start</code>
+   *  this iterable starting at position <code>start</code>
    *  until either the end of the current iterable or the end of array `xs` is reached.
    *
    *  @note Will not terminate for infinite-sized collections.
@@ -431,7 +450,7 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
    *  same order in the sorted iterable as in the original.
    *
    *  @param lt the comparison function
-   *  @return   a list sorted according to the comparison function
+   *  @return   a iterable sorted according to the comparison function
    *            <code>&lt;(e1: a, e2: a) =&gt; Boolean</code>.
    *  @ex <pre>
    *    List("Steve", "Tom", "John", "Bob")
@@ -454,7 +473,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
    *  <code>sep</code>.
    *
    *  @ex  <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
-   *  @note Will not terminate for infinite-sized collections.
    *  @param start starting string.
    *  @param sep separator string.
    *  @param end ending string.
@@ -467,7 +485,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
    *  representations of elements (w.r.t. the method <code>toString()</code>)
    *  are separated by the string <code>sep</code>.
    *
-   *  @note Will not terminate for infinite-sized collections.
    *  @param sep separator string.
    *  @return a string representation of this iterable object.
    */
@@ -475,7 +492,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
     addString(new StringBuilder(), sep).toString
 
   /** Converts a collection into a flat <code>String</code> by each element's toString method.
-   *  @note Will not terminate for infinite-sized collections.
    */
   def mkString =
     addString(new StringBuilder()).toString
@@ -485,7 +501,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
    *  <code>end</code>. Inside, the string representations of elements (w.r.t.
    *  the method <code>toString()</code>) are separated by the string
    *  <code>sep</code>.
-   *  @note Will not terminate for infinite-sized collections.
    */
   def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
     b append start
@@ -501,28 +516,13 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
   /** Write all elements of this string into given string builder.
    *  The string representations of elements (w.r.t. the method <code>toString()</code>)
    *  are separated by the string <code>sep</code>.
-   *  @note Will not terminate for infinite-sized collections.
    */
-  def addString(b: StringBuilder, sep: String): StringBuilder = {
-    var first = true
-    for (x <- this) {
-      if (first) first = false
-      else b append sep
-      b append x
-    }
-    b
-  }
+  def addString(b: StringBuilder, sep: String): StringBuilder = addString(b, "", sep, "")
 
   /** Write all elements of this string into given string builder without using
    *  any separator between consecutive elements.
-   *  @note Will not terminate for infinite-sized collections.
    */
-  def addString(b: StringBuilder): StringBuilder = {
-    for (x <- this) {
-      b append x
-    }
-    b
-  }
+  def addString(b: StringBuilder): StringBuilder = addString(b, "")
 
   /**
    * returns a projection that can be used to call non-strict <code>filter</code>,
@@ -547,7 +547,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
     string
   }
 
-
   /** Creates a view of this iterable @see IterableView
    */
   def view: IterableView[CC, A] = new IterableView[CC, A] { // !!! Martin: We should maybe infer the type parameters here?
@@ -557,10 +556,10 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
 
 // The following methods return non-deterministic results, unless this iterable is an OrderedIterable
 
-  /** The first element of this sequence.
+  /** The first element of this iterable.
    *
    *  @note  Might return different results for different runs, unless this iterable is ordered
-   *  @throws Predef.NoSuchAentException if the sequence is empty.
+   *  @throws Predef.NoSuchElementException if the iterable is empty.
    */
   def head: A = if (isEmpty) throw new NoSuchElementException else elements.next
 
@@ -574,7 +573,7 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
   def headOption: Option[A] = if (isEmpty) None else Some(head)
 
   /** @deprecated use headOption instead
-   *  <code>None</code> if list is empty.
+   *  <code>None</code> if iterable is empty.
    */
   @deprecated def firstOption: Option[A] = headOption
 
@@ -589,7 +588,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
    *  than <code>n</code> elements.
    *
    *  @param n the number of elements to take
-   *  @return a possibly projected sequence
    *  @note  Might return different results for different runs, unless this iterable is ordered
    */
   def take(n: Int): CC[A] = {
@@ -648,74 +646,6 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
     b.result
   }
 
-  /** The last element of this iterable.
-   *
-   *  @throws Predef.NoSuchElementException if the sequence is empty.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def last: A = {
-    var lst = head
-    for (x <- this)
-      lst = x
-    lst
-  }
-
-  /** Returns as an option the last element of this iterable or
-   *  <code>None</code> if iterable is empty.
-   *
-   *  @return the last element as an option.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def lastOption: Option[A] = if (isEmpty) None else Some(last)
-
-  /** An iterable consisting of all elements of this iterable except the last one.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def init: CC[A] = {
-    var lst = head
-    val b = newBuilder[A]
-    for (x <- this) {
-      b += lst
-      lst = x
-    }
-    b.result
-  }
-
-  /** Returns the rightmost <code>n</code> elements from this iterable.
-   *
-   *  @param n the number of elements to take
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def takeRight(n: Int): CC[A] = {
-    val b = newBuilder[A]
-    val lead = elements drop n
-    var go = false
-    for (x <- this) {
-      if (go) b += x
-      else if (lead.hasNext) lead.next
-      else go = true
-    }
-    b.result
-  }
-
-  /** Returns the iterable wihtout its rightmost <code>n</code> elements.
-   *
-   *  @param n the number of elements to take
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def dropRight(n: Int): CC[A] = {
-    val b = newBuilder[A]
-    val lead = elements drop n
-    breakable {
-      for (x <- this) {
-        if (!lead.hasNext) break
-        lead.next
-        b += x
-      }
-    }
-    b.result
-  }
-
   /** Split the iterable at a given point and return the two parts thus
    *  created.
    *
@@ -732,82 +662,13 @@ b   *  @param thatElem element <code>thatElem</code> is used to fill up the
     (l.result, r.result)
   }
 
-  /** Returns the longest prefix of this sequence whose elements satisfy
-   *  the predicate <code>p</code>.
-   *
-   *  @param p the test predicate.
-   *  @return  the longest prefix of this sequence whose elements satisfy
-   *           the predicate <code>p</code>.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def takeWhile(p: A => Boolean): CC[A] = {
-    val b = newBuilder[A]
-    breakable {
-      for (x <- this) {
-        if (!p(x)) break
-        b += x
-      }
-    }
-    b.result
-  }
-
-  /** Returns the longest suffix of this sequence whose first element
-   *  does not satisfy the predicate <code>p</code>.
-   *
-   *  @param p the test predicate.
-   *  @return  the longest suffix of the sequence whose first element
-   *           does not satisfy the predicate <code>p</code>.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def dropWhile(p: A => Boolean): CC[A] = {
-    val b = newBuilder[A]
-    var go = false
-    for (x <- this) {
-      if (go) b += x
-      else if (!p(x)) { go = true; b += x }
-    }
-    b.result
-  }
-
- /** Returns a pair consisting of the longest prefix of the list whose
-   *  elements all satisfy the given predicate, and the rest of the list.
-   *
-   *  @param p the test predicate
-   *  @return  a pair consisting of the longest prefix of the list whose
-   *           elements all satisfy <code>p</code>, and the rest of the list.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def span(p: A => Boolean): (CC[A], CC[A]) = {
-    val l, r = newBuilder[A]
-    var toLeft = true
-    for (x <- this) {
-      toLeft = toLeft && p(x)
-      (if (toLeft) l else r) += x
-    }
-    (l.result, r.result)
-  }
-
-  /** Checks if the other iterable object contains the same elements as this one.
-   *
-   *  @note will not terminate for infinite-sized iterables.
-   *  @param that  the other iterable
-   *  @return true, iff both iterables contain the same elements.
-   *  @note  Might return different results for different runs, unless this iterable is ordered
-   */
-  def sameElements[B >: A](that: OrderedIterable[B]): Boolean = {
-    val these = this.elements
-    val those = that.elements
-    while (these.hasNext && those.hasNext && these.next() == those.next()) {}
-    !these.hasNext && !those.hasNext
-  }
-
-  /** A sub-sequence view  starting at index `from`
+  /** A sub-iterable view  starting at index `from`
    *  and extending up to (but not including) index `until`.
    *
    *  @param from   The index of the first element of the slice
    *  @param until  The index of the element following the slice
    *  @note  The difference between `view` and `slice` is that `view` produces
-   *         a view of the current sequence, whereas `slice` produces a new sequence.
+   *         a view of the current iterable, whereas `slice` produces a new iterable.
    *
    *  @note  Might return different results for different runs, unless this iterable is ordered
    *  @note view(from, to)  is equivalent to view.slice(from, to)
diff --git a/src/library/scalax/collection/generic/covartest/IterableView.scala b/src/library/scalax/collection/generic/covartest/IterableView.scala
index 855e4d259b..43a1f68dc0 100755
--- a/src/library/scalax/collection/generic/covartest/IterableView.scala
+++ b/src/library/scalax/collection/generic/covartest/IterableView.scala
@@ -25,7 +25,7 @@ trait IterableView[+UC[+B] <: Iterable[B], +A] extends Iterable[A] { self =>
     case _ => origin
   }
 
-  private def isDelay = elements eq underlying.elements
+  protected def isDelay = elements eq underlying.elements
 
   private[this] var forced: UC[A] = _
   private[this] var wasForced = false
@@ -100,15 +100,6 @@ trait IterableView[+UC[+B] <: Iterable[B], +A] extends Iterable[A] { self =>
   /** Non-strict variant of @see Iterable.slice */
   override def slice(from: Int, until: Int): IterableView[UC, A] = newView(elements slice (from, until))
 
-  /** Non-strict variant of @see Iterable.takeWhile */
-  override def takeWhile(p: A => Boolean): IterableView[UC, A] = newView(elements takeWhile p)
-
-  /** Non-strict variant of @see Iterable.dropWhile */
-  override def dropWhile(p: A => Boolean): IterableView[UC, A] = newView(elements dropWhile p)
-
-  /** Non-strict variant of @see Iterable.span */
-  override def span(p: A => Boolean): (IterableView[UC, A], IterableView[UC, A]) = (takeWhile(p), dropWhile(p))
-
   /** The projection resulting from the concatenation of this projection with the <code>rest</code> projection.
    *  @param rest   The projection that gets appended to this projection
    *  @deprecated   Use ++ instead
diff --git a/src/library/scalax/collection/generic/covartest/OrderedIterableForwarder.scala b/src/library/scalax/collection/generic/covartest/OrderedIterableForwarder.scala
new file mode 100755
index 0000000000..3a33dc6694
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/OrderedIterableForwarder.scala
@@ -0,0 +1,37 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: IterableProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $
+
+
+package scalax.collection.generic.covartest
+
+/** This trait implements a forwarder for iterable objects. It forwards
+ *  all calls to a different iterable object, except for
+ *
+ *    - toString, hashCode, equals, stringPrefix
+ *    - newBuilder, view
+ *    - all calls creating a new iterable object of the same kind
+ *
+ *  The above methods are forwarded by subclass IterableProxy
+ *
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+trait OrderedIterableForwarder[+A] extends OrderedIterable[A] with IterableForwarder[A] {
+
+  /** The iterable object to which calls are forwarded */
+  protected def underlying: OrderedIterable[A]
+
+  // Iterable delegates
+  // Iterable methods could be printed by  cat IterableTemplate.scala | sed -n '/trait Iterable/,$ p' | egrep '^  (override )?def'
+
+  override def last: A = underlying.last
+  override def lastOption: Option[A] = underlying.lastOption
+  override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that)
+}
diff --git a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala
index 4316c9b34d..f3c509887c 100755
--- a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala
+++ b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala
@@ -13,6 +13,8 @@ package scalax.collection.generic.covartest
 
 import OrderedIterable._
 
+import util.control.Breaks._
+
 /** Ordered iterables are iterables where the `elements` method always returns elements in the same
  *  order (namely the order in which elements were appended to the iterable). In particular, one has
  *  for every two ordered iterables `xs` and `ys`:
@@ -20,4 +22,140 @@ import OrderedIterable._
  *  `(xs ++ ys).elements = xs.elements ++ ys.elements
  */
 trait OrderedIterableTemplate[+CC[+B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], +A]
-  extends IterableTemplate[CC, A]
+  extends IterableTemplate[CC, A] {
+
+  /** The last element of this iterable.
+   *
+   *  @throws Predef.NoSuchElementException if the iterable is empty.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def last: A = {
+    var lst = head
+    for (x <- this)
+      lst = x
+    lst
+  }
+
+  /** Returns as an option the last element of this iterable or
+   *  <code>None</code> if iterable is empty.
+   *
+   *  @return the last element as an option.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def lastOption: Option[A] = if (isEmpty) None else Some(last)
+
+  /** An iterable consisting of all elements of this iterable except the last one.
+   *  @throws Predef.UnsupportedOperationException if the stream is empty.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def init: CC[A] = {
+    if (isEmpty) throw new UnsupportedOperationException("empty.init")
+    var lst = head
+    val b = newBuilder[A]
+    for (x <- this) {
+      b += lst
+      lst = x
+    }
+    b.result
+  }
+
+  /** Returns the rightmost <code>n</code> elements from this iterable.
+   *
+   *  @param n the number of elements to take
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def takeRight(n: Int): CC[A] = {
+    val b = newBuilder[A]
+    val lead = elements drop n
+    var go = false
+    for (x <- this) {
+      if (go) b += x
+      else if (lead.hasNext) lead.next
+      else go = true
+    }
+    b.result
+  }
+
+  /** Returns the iterable wihtout its rightmost <code>n</code> elements.
+   *
+   *  @param n the number of elements to take
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def dropRight(n: Int): CC[A] = {
+    val b = newBuilder[A]
+    val lead = elements drop n
+    breakable {
+      for (x <- this) {
+        if (!lead.hasNext) break
+        lead.next
+        b += x
+      }
+    }
+    b.result
+  }
+
+  /** Returns the longest prefix of this iterable whose elements satisfy
+   *  the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def takeWhile(p: A => Boolean): CC[A] = {
+    val b = newBuilder[A]
+    breakable {
+      for (x <- this) {
+        if (!p(x)) break
+        b += x
+      }
+    }
+    b.result
+  }
+
+  /** Returns the longest suffix of this iterable whose first element
+   *  does not satisfy the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def dropWhile(p: A => Boolean): CC[A] = {
+    val b = newBuilder[A]
+    var go = false
+    for (x <- this) {
+      if (go) b += x
+      else if (!p(x)) { go = true; b += x }
+    }
+    b.result
+  }
+
+ /** Returns a pair consisting of the longest prefix of the iterable whose
+   *  elements all satisfy the given predicate, and the rest of the iterable.
+   *
+   *  @param p the test predicate
+   *  @return  a pair consisting of the longest prefix of the iterable whose
+   *           elements all satisfy <code>p</code>, and the rest of the iterable.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def span(p: A => Boolean): (CC[A], CC[A]) = {
+    val l, r = newBuilder[A]
+    var toLeft = true
+    for (x <- this) {
+      toLeft = toLeft && p(x)
+      (if (toLeft) l else r) += x
+    }
+    (l.result, r.result)
+  }
+
+  /** Checks if the other iterable object contains the same elements as this one.
+   *
+   *  @note will not terminate for infinite-sized iterables.
+   *  @param that  the other iterable
+   *  @return true, iff both iterables contain the same elements.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def sameElements[B >: A](that: OrderedIterable[B]): Boolean = {
+    val these = this.elements
+    val those = that.elements
+    while (these.hasNext && those.hasNext && these.next() == those.next()) {}
+    !these.hasNext && !those.hasNext
+  }
+}
diff --git a/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala b/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala
index 5ada55f62d..47c512545d 100644
--- a/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala
+++ b/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala
@@ -23,7 +23,7 @@ package scalax.collection.generic.covartest
  *  @author  Martin Odersky
  *  @version 2.8
  */
-trait SequenceForwarder[+A] extends Sequence[A] with IterableForwarder[A] {
+trait SequenceForwarder[+A] extends Sequence[A] with OrderedIterableForwarder[A] {
 
   protected override def underlying: Sequence[A]
 
diff --git a/src/library/scalax/collection/immutable/DefaultSet.scala b/src/library/scalax/collection/immutable/DefaultSet.scala
new file mode 100644
index 0000000000..a9ce3fb3df
--- /dev/null
+++ b/src/library/scalax/collection/immutable/DefaultSet.scala
@@ -0,0 +1,45 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashSet.scala 16884 2009-01-09 16:52:09Z cunei $
+
+package scalax.collection.immutable
+
+import generic.SetTemplate
+
+/** A default implementation of immutable sets.
+ *  This is currently implemented as a proxy for an immutable HashSet,
+ *  except that its builder returns specialized representations EmptySet,Set1,..., Set4
+ *  for sets of size <= 4.
+ */
+class DefaultSet[A] private (hset: HashSet[A])
+  extends Set[A]
+     with SetTemplate[Set, A] {
+
+  def this() = this(new HashSet[A])
+
+  def contains(elem: A): Boolean = hset.contains(elem)
+
+  def + (elem: A): Set[A] = hset + elem
+
+  /** Keeps underlying HashSet representation, but switches back to EmptySet if
+   *  result does not contain any elements
+   */
+  def - (elem: A): Set[A] = {
+    val hset1 = hset - elem
+    if (hset1.isEmpty) new EmptySet[A]
+    else new DefaultSet(hset)
+  }
+
+  def size: Int = hset.size
+
+  def elements: Iterator[A] = hset.elements
+
+  override def foreach(f: A => Unit): Unit = hset.foreach(f)
+}
+
diff --git a/src/library/scalax/collection/immutable/EmptyMap.scala b/src/library/scalax/collection/immutable/EmptyMap.scala
new file mode 100644
index 0000000000..c04d988f08
--- /dev/null
+++ b/src/library/scalax/collection/immutable/EmptyMap.scala
@@ -0,0 +1,34 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: EmptyMap.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+/** This class implements empty immutable maps
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class EmptyMap[A, B] extends Map[A, B] {
+
+  def size: Int = 0
+
+  def get(key: A): Option[B] = None
+
+  def elements: Iterator[(A, B)] = Iterator.empty
+
+  def update (key: A, value: B): Map[A, B] = new Map1(key, value)
+
+  def - (key: A): Map[A, B] = this
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/EmptySet.scala b/src/library/scalax/collection/immutable/EmptySet.scala
new file mode 100755
index 0000000000..32c4915a49
--- /dev/null
+++ b/src/library/scalax/collection/immutable/EmptySet.scala
@@ -0,0 +1,38 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: EmptySet.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+import collection.generic.Builder
+
+/** This class implements empty immutable sets
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class EmptySet[A] extends Set[A] {
+
+  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(f: A => Unit): Unit = {}
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/HashMap.scala b/src/library/scalax/collection/immutable/HashMap.scala
new file mode 100644
index 0000000000..7d3595904d
--- /dev/null
+++ b/src/library/scalax/collection/immutable/HashMap.scala
@@ -0,0 +1,162 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashMap.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+package scalax.collection.immutable
+
+import generic._
+
+/** The canonical factory methods for <a href="HashMap.html">immutable HashMap's</a>.
+ *
+ *  @author  Martin Odersky
+ *  @version 2.0, 19/01/2007
+ */
+object HashMap extends MapFactory[HashMap] {
+
+  /** The empty map of this type */
+  def empty[A, B] = new HashMap[A, B]
+
+}
+
+/** This class implements immutable maps using a hash table.
+  * It is optimized for sequential accesses where the last updated table is accessed most often.
+  * It supports with reasonable efficiency accesses to previous versions of the table by keeping
+  * a change log that's regularly compacted.
+  * It needs to synchronize most methods, so it is less suitable for highly concurrent accesses.
+  *
+  *  @author  Martin Odersky
+  *  @version 2.0, 19/01/2007
+  */
+@serializable
+class HashMap[A, B] extends Map[A,B]
+                       with MapTemplate[A, B, HashMap]
+                       with mutable.HashTable[A] {
+
+  type Entry = mutable.DefaultEntry[A, Any]
+
+  protected var later: HashMap[A, B] = null
+  protected var oldKey: A = _
+  protected var oldValue: Option[B] = _
+  protected var deltaSize: Int = _
+
+  def get(key: A): Option[B] = synchronized {
+    var m = this
+    var cnt = 0
+    while (m.later != null) {
+      if (key == m.oldKey) return m.oldValue
+      cnt += 1
+      m = m.later
+    }
+    if (cnt > logLimit) makeCopy(m)
+    val e = m.findEntry(key)
+    if (e == null) None
+    else Some(getValue(e))
+  }
+
+  def update(key: A, value: B): HashMap[A, B] = synchronized {
+    makeCopyIfUpdated()
+    val e = findEntry(key)
+    if (e == null) {
+      markUpdated(key, None, 1)
+      later.addEntry(new Entry(key, value))
+    } else {
+      markUpdated(key, Some(getValue(e)), 0)
+      e.value = value
+    }
+    later
+  }
+
+  def - (key: A): HashMap[A, B] = synchronized {
+    makeCopyIfUpdated()
+    val e = findEntry(key)
+    if (e == null) this
+    else {
+      markUpdated(key, Some(getValue(e)), -1)
+      later removeEntry key
+      later
+    }
+  }
+
+  override def size: Int = synchronized {
+    var m = this
+    var cnt = 0
+    var s = 0
+    while (m.later != null) {
+      s -= m.deltaSize
+      cnt += 1
+      m = m.later
+    }
+    s += m.tableSize
+    if (cnt > logLimit) makeCopy(m)
+    s
+  }
+
+  def elements = synchronized {
+    makeCopyIfUpdated()
+    entries map {e => (e.key, getValue(e))}
+  }
+
+  private def getValue(e: Entry) =
+    e.value.asInstanceOf[B]
+
+  private def logLimit: Int = Math.sqrt(table.length).toInt
+
+  private def markUpdated(key: A, ov: Option[B], delta: Int) {
+    val lv = loadFactor
+    later = new HashMap[A, B] {
+      override def initialSize = 0
+      override def loadFactor = lv
+      table     = HashMap.this.table
+      tableSize = HashMap.this.tableSize
+      threshold = HashMap.this.threshold
+    }
+    oldKey = key
+    oldValue = ov
+    deltaSize = delta
+  }
+
+  private def makeCopy(last: HashMap[A, B]) {
+    def undo(m: HashMap[A, B]) {
+      if (m ne last) {
+        undo(m.later)
+        if (m.deltaSize == 1) removeEntry(m.oldKey)
+        else if (m.deltaSize == 0) findEntry(m.oldKey).value = m.oldValue.get
+        else if (m.deltaSize == -1) addEntry(new Entry(m.oldKey, m.oldValue.get))
+      }
+    }
+    def copy(e: Entry): Entry =
+      if (e == null) null
+      else {
+        val rest = copy(e.next)
+        val result = new Entry(e.key, e.value)
+        result.next = rest
+        result
+      }
+    val ltable = last.table
+    val s = ltable.length
+    table = new scala.Array[mutable.HashEntry[A, Entry]](s)
+    var i = 0
+    while (i < s) {
+      table(i) = copy(ltable(i).asInstanceOf[Entry])
+      i += 1
+    }
+    tableSize = last.tableSize
+    threshold = last.threshold
+    undo(this)
+    later = null
+  }
+
+  private def makeCopyIfUpdated() {
+    var m = this
+    while (m.later != null) m = m.later
+    if (m ne this) makeCopy(m)
+  }
+}
+
diff --git a/src/library/scalax/collection/immutable/HashSet.scala b/src/library/scalax/collection/immutable/HashSet.scala
new file mode 100644
index 0000000000..56394b9bc6
--- /dev/null
+++ b/src/library/scalax/collection/immutable/HashSet.scala
@@ -0,0 +1,138 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashSet.scala 16884 2009-01-09 16:52:09Z cunei $
+
+package scalax.collection.immutable
+
+import generic.{SetTemplate, SetFactory, AddableBuilder}
+
+/** The canonical factory methods for <a href="HashSet.html">immutable HashSet's<la>.
+  *
+  *  @author  Martin Odersky
+  *  @version 2.8
+  */
+object HashSet extends SetFactory[HashSet] {
+
+  /** The empty set of this type.
+   */
+  def empty[A] = new HashSet[A]
+
+}
+
+/** This class implements immutable maps/sets using a hash table.
+  * It is optimized for sequential accesses where the last updated table is accessed most often.
+  * It supports with reasonable efficiency accesses to previous versions of the table by keeping
+  * a change log that's regularly compacted.
+  * It needs to synchronize most methods, so it is less suitable for highly concurrent accesses.
+  *
+  *  @author  Martin Odersky
+  *  @version 2.0, 19/01/2007
+  */
+@serializable
+class HashSet[A] extends Set[A]
+                    with SetTemplate[HashSet, A]
+                    with mutable.FlatHashTable[A] {
+  protected var later: HashSet[A] = null
+  protected var changedElem: A = _
+  protected var deleted: Boolean = _
+
+  def contains(elem: A): Boolean = synchronized {
+    var m = this
+    var cnt = 0
+    while (m.later != null) {
+      if (elem == m.changedElem) return m.deleted
+      cnt += 1
+      m = m.later
+    }
+    if (cnt > logLimit) makeCopy(m)
+    m.containsEntry(elem)
+  }
+
+  def + (elem: A): HashSet[A] = synchronized {
+    makeCopyIfUpdated()
+    if (containsEntry(elem)) this
+    else {
+      markUpdated(elem, false)
+      later addEntry elem
+      later
+    }
+  }
+
+  def - (elem: A): HashSet[A] = synchronized {
+    makeCopyIfUpdated()
+    if (!containsEntry(elem)) this
+    else {
+      markUpdated(elem, true)
+      later removeEntry elem
+      later
+    }
+  }
+
+  override def size: Int = synchronized {
+    var m = this
+    var cnt = 0
+    var s = 0
+    while (m.later != null) {
+      if (m.deleted) s += 1 else s -= 1
+      cnt += 1
+      m = m.later
+    }
+    s += m.tableSize
+    if (cnt > logLimit) makeCopy(m)
+    s
+  }
+
+  override def elements = synchronized {
+    makeCopyIfUpdated()
+    // note need to cache because (later versions of) set might be mutated while elements are traversed.
+    val cached = new mutable.ArrayBuffer() ++ super.elements
+    cached.elements
+  }
+
+  override def newBuilder[B]: generic.Builder[HashSet, B] =
+    new AddableBuilder[HashSet, B](HashSet.empty)
+
+  private def logLimit: Int = Math.sqrt(table.length).toInt
+
+  private def markUpdated(elem: A, del: Boolean) {
+    val lv = loadFactor
+    later = new HashSet[A] {
+      override def initialSize = 0
+      override def loadFactor = lv
+      table     = HashSet.this.table
+      tableSize = HashSet.this.tableSize
+      threshold = HashSet.this.threshold
+    }
+    changedElem = elem
+    deleted = del
+  }
+
+  private def makeCopy(last: HashSet[A]) {
+    def undo(m: HashSet[A]) {
+      if (m ne last) {
+        undo(m.later)
+        if (m.deleted) addEntry(m.changedElem)
+        else removeEntry(m.changedElem)
+      }
+    }
+    table = new scala.Array[AnyRef](last.table.length)
+    scala.Array.copy(last.table, 0, table, 0, table.length)
+    tableSize = last.tableSize
+    threshold = last.threshold
+    undo(this)
+    later = null
+  }
+
+  private def makeCopyIfUpdated() {
+    var m = this
+    while (m.later != null) m = m.later
+    if (m ne this) makeCopy(m)
+  }
+}
+
diff --git a/src/library/scalax/collection/immutable/Iterable.scala b/src/library/scalax/collection/immutable/Iterable.scala
index 07e1fed890..0e6bb8fae0 100644
--- a/src/library/scalax/collection/immutable/Iterable.scala
+++ b/src/library/scalax/collection/immutable/Iterable.scala
@@ -1,6 +1,7 @@
 package scalax.collection.immutable
 
-import generic.covariant
+import generic._
+import annotation.unchecked.uncheckedVariance
 
 /** Collection classes mixing in this class provide a method
  *  <code>elements</code> which returns an iterator over all the
@@ -14,9 +15,9 @@ import generic.covariant
  *  @version 2.8
  */
 trait Iterable[+A] extends collection.Iterable[A]
-                      with covariant.IterableTemplate[Iterable, A]
+                      with IterableTemplate[Iterable, A @uncheckedVariance]
 
-object Iterable extends covariant.IterableFactory[Iterable] {
+object Iterable extends IterableFactory[Iterable] with EmptyIterableFactory[Iterable] {
   val empty: Iterable[Nothing] = Nil
 }
 
diff --git a/src/library/scalax/collection/immutable/List.scala b/src/library/scalax/collection/immutable/List.scala
index 6851fb9769..cb5965a18a 100644
--- a/src/library/scalax/collection/immutable/List.scala
+++ b/src/library/scalax/collection/immutable/List.scala
@@ -12,7 +12,8 @@
 package scalax.collection.immutable
 
 import mutable.ListBuffer
-import generic.covariant.{SequenceTemplate, SequenceFactory}
+import generic.{SequenceTemplate, SequenceFactory, EmptyIterableFactory, Builder}
+import annotation.unchecked.uncheckedVariance
 
 /** A class representing an ordered collection of elements of type
  *  <code>a</code>. This class comes with two implementing case
@@ -23,7 +24,9 @@ import generic.covariant.{SequenceTemplate, SequenceFactory}
  *  @author  Martin Odersky and others
  *  @version 2.8
  */
-sealed abstract class List[+A] extends Stream[A] with SequenceTemplate[List, A] with Product {
+sealed abstract class List[+A] extends Stream[A]
+                                  with SequenceTemplate[List, A @uncheckedVariance]
+                                  with Product {
 
   import collection.{Iterable, OrderedIterable, Sequence, Vector}
 
@@ -572,7 +575,7 @@ final case class ::[B](private var hd: B, private[scalax] var tl: List[B]) exten
  *  @author  Martin Odersky and others
  *  @version 1.0, 15/07/2003
  */
-object List extends SequenceFactory[List] {
+object List extends SequenceFactory[List] with EmptyIterableFactory[List] {
 
   override val empty: List[Nothing] = Nil
 
@@ -721,7 +724,7 @@ object List extends SequenceFactory[List] {
    *             in the same order
    *  @deprecated use `array.toList` instead
    */
-  def fromArray[A](arr: Array[A]): List[A] = fromArray(arr, 0, arr.length)
+  @deprecated def fromArray[A](arr: Array[A]): List[A] = fromArray(arr, 0, arr.length)
 
   /** Converts a range of an array into a list.
    *
diff --git a/src/library/scalax/collection/immutable/Map.scala b/src/library/scalax/collection/immutable/Map.scala
new file mode 100755
index 0000000000..923866fb8e
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Map.scala
@@ -0,0 +1,66 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Set.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+package scalax.collection.immutable
+
+import generic._
+
+object Map extends MapFactory[Map] {
+  private val hashSeed = "Map".hashCode
+  def empty[A, B]: Map[A, B] = new EmptyMap[A, B]
+}
+
+trait Map[A, B] extends MapTemplate[A, B, Map] with collection.Map[A, B] { self =>
+
+  def empty[B]: Map[A, B] = new EmptyMap[A, B]
+
+  /** The same map with a given default function */
+  def withDefault(d: A => B): Map[A, B] = new Map[A, B] {
+    def size = self.size
+    def get(key: A) = self.get(key)
+    def elements = self.elements
+    override def empty[C] = self.empty
+    def update (key: A, value: B): Map[A, B] =
+      self update (key, value) withDefault d
+    def - (key: A): Map[A, B] =
+      self - key withDefault d
+    override def default(key: A): B = d(key)
+  }
+
+  /** The same map with a given default value */
+  def withDefaultValue(d: B): Map[A, B] = withDefault(x => d)
+
+  /** Compares this set with another object and returns true, iff the
+   *  other object is also a set which contains the same elements as
+   *  this set.
+   *
+   *  @param that the other object
+   *  @note not necessarily run-time type safe.
+   *  @return     <code>true</code> iff this set and the other set
+   *              contain the same elements.
+   */
+  override def equals(that: Any): Boolean = that match {
+    case other: Map[a, b] =>
+      this.size == other.size && this.forall {
+        case (key, value) => other.get(key.asInstanceOf[a]) match {
+          case None => false
+          case Some(otherval) => value == otherval
+        }
+      }
+    case _ => false
+  }
+
+  /** A hash method compatible with <code>equals</code>
+   */
+  override def hashCode() =
+    (Map.hashSeed /: this) (_ * 41 + _.hashCode)
+
+}
diff --git a/src/library/scalax/collection/immutable/Map1.scala b/src/library/scalax/collection/immutable/Map1.scala
new file mode 100755
index 0000000000..f518c7cf17
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Map1.scala
@@ -0,0 +1,39 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Map1.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+/** This class implements immutable maps with exactly one entry
+ *
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class Map1[A, B](key1: A, value1: B) extends Map[A, B] {
+
+  def size = 1
+
+  def get(key: A): Option[B] =
+    if (key == key1) Some(value1) else None
+
+  def elements = Iterator((key1, value1))
+
+  def update (key: A, value: B): Map[A, B] =
+    if (key == key1) new Map1(key1, value)
+    else null // new Map2(key1, value1, key, value)
+
+  def - (key: A): Map[A, B] =
+    if (key == key1) empty else this
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/Map2.scala b/src/library/scalax/collection/immutable/Map2.scala
new file mode 100644
index 0000000000..f3f55c5828
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Map2.scala
@@ -0,0 +1,44 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Map1.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+/** This class implements immutable maps with exactly one entry
+ *
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class Map2[A, B](key1: A, value1: B, key2: A, value2: B) extends Map[A, B] {
+
+  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))
+
+  def update (key: A, value: B): Map[A, B] =
+    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
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/Map3.scala b/src/library/scalax/collection/immutable/Map3.scala
new file mode 100644
index 0000000000..3c8e6298cd
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Map3.scala
@@ -0,0 +1,47 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Map1.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+/** This class implements immutable maps with exactly one entry
+ *
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class Map3[A, B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends Map[A, B] {
+
+  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))
+
+  def update (key: A, value: B): Map[A, B] =
+    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
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/Map4.scala b/src/library/scalax/collection/immutable/Map4.scala
new file mode 100644
index 0000000000..ad2dcd513b
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Map4.scala
@@ -0,0 +1,50 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Map1.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+/** This class implements immutable maps with exactly one entry
+ *
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@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] {
+
+  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))
+
+  def update (key: A, value: B): Map[A, B] =
+    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 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
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/OrderedIterable.scala b/src/library/scalax/collection/immutable/OrderedIterable.scala
index 1c3fb67fb2..80fa418eec 100644
--- a/src/library/scalax/collection/immutable/OrderedIterable.scala
+++ b/src/library/scalax/collection/immutable/OrderedIterable.scala
@@ -1,6 +1,7 @@
 package scalax.collection.immutable
 
-import generic.covariant
+import generic._
+import annotation.unchecked.uncheckedVariance
 
 /** Collection classes mixing in this class provide a method
  *  <code>elements</code> which returns an iterator over all the
@@ -13,11 +14,12 @@ import generic.covariant
  *  @owner   Martin Odersky
  *  @version 2.8
  */
-trait OrderedIterable[+A] extends Iterable[A]
-                             with covariant.OrderedIterableTemplate[OrderedIterable, A]
+trait OrderedIterable[+A] extends immutable.Iterable[A]
+                             with OrderedIterableTemplate[OrderedIterable, A @uncheckedVariance]
                              with collection.OrderedIterable[A]
 
-object OrderedIterable extends covariant.IterableFactory[OrderedIterable] {
+object OrderedIterable extends IterableFactory[OrderedIterable]
+                          with EmptyIterableFactory[OrderedIterable] {
   val empty: OrderedIterable[Nothing] = Nil
 }
 
diff --git a/src/library/scalax/collection/immutable/Sequence.scala b/src/library/scalax/collection/immutable/Sequence.scala
index 10ae805106..78de3cbfaf 100644
--- a/src/library/scalax/collection/immutable/Sequence.scala
+++ b/src/library/scalax/collection/immutable/Sequence.scala
@@ -1,6 +1,7 @@
 package scalax.collection.immutable
 
-import generic.covariant
+import generic._
+import annotation.unchecked.uncheckedVariance
 
 /** Collection classes mixing in this class provide a method
  *  <code>elements</code> which returns an iterator over all the
@@ -14,10 +15,10 @@ import generic.covariant
  *  @version 2.8
  */
 trait Sequence[+A] extends OrderedIterable[A]
-                      with covariant.SequenceTemplate[Sequence, A]
+                      with SequenceTemplate[Sequence, A @uncheckedVariance]
                       with collection.Sequence[A]
 
-object Sequence extends covariant.SequenceFactory[Sequence] {
+object Sequence extends SequenceFactory[Sequence] with EmptyIterableFactory[Sequence] {
   val empty: Sequence[Nothing] = Nil
 }
 
diff --git a/src/library/scalax/collection/immutable/Set.scala b/src/library/scalax/collection/immutable/Set.scala
index 5b39aaa3a4..9462cd3c5f 100755
--- a/src/library/scalax/collection/immutable/Set.scala
+++ b/src/library/scalax/collection/immutable/Set.scala
@@ -11,17 +11,19 @@
 
 package scalax.collection.immutable
 
-import collection.generic._
+import generic._
 
 object Set extends generic.SetFactory[Set] {
   private val hashSeed = "Set".hashCode
-  def empty[A]: Set[A] = null // !!!
+  def empty[A]: Set[A] = new EmptySet[A]
 }
 
 trait Set[A] extends OrderedIterable[A]
                 with collection.Set[A]
                 with SetTemplate[Set, A] {
 
+  override def newBuilder[B]: Builder[Set, B] = Set.newBuilder[B]
+
   /** Compares this set with another object and returns true, iff the
    *  other object is also a set which contains the same elements as
    *  this set.
diff --git a/src/library/scalax/collection/immutable/Set1.scala b/src/library/scalax/collection/immutable/Set1.scala
new file mode 100755
index 0000000000..276cd83bb0
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Set1.scala
@@ -0,0 +1,46 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Set1.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+import collection.generic.Builder
+
+/** This class implements immutable sets with exactly one element.
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class Set1[A](elem1: A) extends Set[A] {
+
+  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(f: A => Unit): Unit = {
+    f(elem1)
+  }
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/Set2.scala b/src/library/scalax/collection/immutable/Set2.scala
new file mode 100755
index 0000000000..828c52d053
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Set2.scala
@@ -0,0 +1,47 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Set1.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+import collection.generic.Builder
+
+/** This class implements immutable sets with exactly one element.
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class Set2[A](elem1: A, elem2: A) extends Set[A] {
+
+  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(f: A => Unit): Unit = {
+    f(elem1); f(elem2)
+  }
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/Set3.scala b/src/library/scalax/collection/immutable/Set3.scala
new file mode 100755
index 0000000000..f14253231f
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Set3.scala
@@ -0,0 +1,48 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Set1.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+import collection.generic.Builder
+
+/** This class implements immutable sets with exactly one element.
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class Set3[A](elem1: A, elem2: A, elem3: A) extends Set[A] {
+
+  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(f: A => Unit): Unit = {
+    f(elem1); f(elem2); f(elem3)
+  }
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/Set4.scala b/src/library/scalax/collection/immutable/Set4.scala
new file mode 100755
index 0000000000..bef1b6588d
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Set4.scala
@@ -0,0 +1,49 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Set1.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+
+package scalax.collection.immutable
+
+import collection.generic.Builder
+
+/** This class implements immutable sets with exactly one element.
+ *  @author  Martin Oderskty
+ *  @version 1.0, 019/01/2007
+ */
+@serializable
+class Set4[A](elem1: A, elem2: A, elem3: A, elem4: A) extends Set[A] {
+
+  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 DefaultSet[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(f: A => Unit): Unit = {
+    f(elem1); f(elem2); f(elem3); f(elem4)
+  }
+}
+
+
+
diff --git a/src/library/scalax/collection/immutable/Stream.scala b/src/library/scalax/collection/immutable/Stream.scala
index 3581ac5b5d..036fefe70c 100755
--- a/src/library/scalax/collection/immutable/Stream.scala
+++ b/src/library/scalax/collection/immutable/Stream.scala
@@ -12,7 +12,8 @@
 package scalax.collection.immutable
 
 import mutable.ListBuffer
-import generic.covariant.{SequenceTemplate, SequenceFactory}
+import generic.{SequenceTemplate, SequenceFactory, EmptyIterableFactory, Builder, LazyBuilder}
+import annotation.unchecked.uncheckedVariance
 
 /**
  * The object <code>Stream</code> provides helper functions
@@ -21,7 +22,7 @@ import generic.covariant.{SequenceTemplate, SequenceFactory}
  * @author Martin Odersky, Matthias Zenger
  * @version 1.1 08/08/03
  */
-object Stream extends SequenceFactory[Stream] {
+object Stream extends SequenceFactory[Stream] with EmptyIterableFactory[Stream] {
 
   import collection.{Iterable, OrderedIterable, Sequence, Vector}
 
@@ -417,7 +418,7 @@ import Stream._
  * @version 1.1 08/08/03
  */
 abstract class Stream[+A] extends Sequence[A]
-                             with SequenceTemplate[Stream, A] {
+                             with SequenceTemplate[Stream, A @uncheckedVariance] {
 self =>
 
   import collection.{Iterable, OrderedIterable, Sequence, Vector}
diff --git a/src/library/scalax/collection/immutable/Vector.scala b/src/library/scalax/collection/immutable/Vector.scala
index 3848304525..93e9601bd2 100644
--- a/src/library/scalax/collection/immutable/Vector.scala
+++ b/src/library/scalax/collection/immutable/Vector.scala
@@ -1,6 +1,7 @@
 package scalax.collection.immutable
 
-import generic.covariant
+import generic._
+import annotation.unchecked.uncheckedVariance
 
 /** Collection classes mixing in this class provide a method
  *  <code>elements</code> which returns an iterator over all the
@@ -14,10 +15,10 @@ import generic.covariant
  *  @version 2.8
  */
 trait Vector[+A] extends Sequence[A]
-                    with covariant.VectorTemplate[Vector, A]
+                    with VectorTemplate[Vector, A @uncheckedVariance]
                     with collection.Vector[A]
 
-object Vector extends covariant.SequenceFactory[Vector] {
+object Vector extends SequenceFactory[Vector] with EmptyIterableFactory[Vector] {
   val empty: Vector[Nothing] = immutable.Vector.empty
 }
 
diff --git a/src/library/scalax/collection/mutable/Array.scala b/src/library/scalax/collection/mutable/Array.scala
index c2b4d19101..cf1e02008b 100755
--- a/src/library/scalax/collection/mutable/Array.scala
+++ b/src/library/scalax/collection/mutable/Array.scala
@@ -253,7 +253,7 @@ object Array extends SequenceFactory[Array] {
  *  @author Martin Odersky
  *  @version 1.0
  */
-final class Array[A](_length: Int) extends Vector[A] with mutable.VectorTemplate[Array, A] {
+final class Array[A](_length: Int) extends Vector[A] with MutableVectorTemplate[Array, A] {
 
    /** Multidimensional array creation
     *  @deprecated use Array.ofDim instead
diff --git a/src/library/scalax/collection/mutable/ArrayBuffer.scala b/src/library/scalax/collection/mutable/ArrayBuffer.scala
index dbdb96e004..daf514c485 100644
--- a/src/library/scalax/collection/mutable/ArrayBuffer.scala
+++ b/src/library/scalax/collection/mutable/ArrayBuffer.scala
@@ -11,7 +11,7 @@
 
 package scalax.collection.mutable
 
-import generic.SequenceFactory
+import generic.{SequenceFactory, MutableVectorTemplate, Builder}
 
 /* Factory object for `ArrayBuffer` class */
 object ArrayBuffer extends SequenceFactory[ArrayBuffer] {
@@ -31,7 +31,7 @@ object ArrayBuffer extends SequenceFactory[ArrayBuffer] {
 class ArrayBuffer[A](override protected val initialSize: Int)
   extends Buffer[A]
      with Vector[A]
-     with generic.mutable.VectorTemplate[ArrayBuffer, A]
+     with MutableVectorTemplate[ArrayBuffer, A]
      with Builder[ArrayBuffer, A]
      with ResizableArray[A] {
 
diff --git a/src/library/scalax/collection/mutable/Buffer.scala b/src/library/scalax/collection/mutable/Buffer.scala
index 502f99758a..3d0eaec84e 100644
--- a/src/library/scalax/collection/mutable/Buffer.scala
+++ b/src/library/scalax/collection/mutable/Buffer.scala
@@ -11,8 +11,7 @@
 
 package scalax.collection.mutable
 
-import generic.{SequenceFactory, SequenceTemplate}
-import generic.mutable.{Growable, Shrinkable}
+import generic._
 
 /* Factory object for `Buffer` trait */
 object Buffer extends SequenceFactory[Buffer] {
@@ -29,12 +28,14 @@ object Buffer extends SequenceFactory[Buffer] {
  *  @version 2.8
   */
 @cloneable
-trait Buffer[A] extends mutable.Sequence[A]
+trait Buffer[A] extends Sequence[A]
                    with SequenceTemplate[Buffer, A]
+                   with Addable[Buffer[A], A]
+                   with Subtractable[Buffer[A], A]
                    with Growable[A]
                    with Shrinkable[A]
 //      with Scriptable[Message[(Location, A)]]
-                   with CloneableCollection
+                   with Cloneable[Buffer[A]]
 {
 
 // Abstract methods from Vector:
@@ -83,6 +84,10 @@ trait Buffer[A] extends mutable.Sequence[A]
    */
   def +:(elem: A): this.type
 
+  /** Append a single element to this buffer and return the identity of the buffer
+   */
+  def +(elem: A): this.type = { +=(elem); this }
+
   /** Inserts new elements at the index <code>n</code>. Opposed to method
    *  <code>update</code>, this method will not replace an element with a
    *  one. Instead, it will insert a new element at index <code>n</code>.
@@ -114,7 +119,7 @@ trait Buffer[A] extends mutable.Sequence[A]
   }
 
   /** Removes a single element from this buffer, at its first occurrence.
-   *  If the list does not contain that element, it is unchanged
+   *  If the buffer does not contain that element, it is unchanged.
    *
    *  @param x  the element to remove.
    */
@@ -123,6 +128,13 @@ trait Buffer[A] extends mutable.Sequence[A]
     if (i != -1) remove(i)
   }
 
+  /** Removes a single element from this buffer and returns the identity
+   *  of the buffer. If the buffer does not contain that element, it is unchanged.
+   *
+   *  @param x  the element to remove.
+   */
+  def -(elem: A): this.type = { -=(elem); this }
+
   /** Prepend two ore more elements to this buffer and return
    *  the identity of the buffer.
    *  @param elem  the element to prepend.
@@ -235,12 +247,6 @@ trait Buffer[A] extends mutable.Sequence[A]
   }
    */
 
-  /** Return a clone of this buffer.
-   *
-   *  @return a buffer with the same elements.
-   */
-  override def clone(): Buffer[A] = super.clone().asInstanceOf[Buffer[A]]
-
   /** Defines the prefix of the string representation.
    */
   override def stringPrefix: String = "Buffer"
diff --git a/src/library/scalax/collection/mutable/CloneableCollection.scala b/src/library/scalax/collection/mutable/DefaultEntry.scala
index 465995ac7e..2fb0f62226 100644
--- a/src/library/scalax/collection/mutable/CloneableCollection.scala
+++ b/src/library/scalax/collection/mutable/DefaultEntry.scala
@@ -6,14 +6,11 @@
 **                          |/                                          **
 \*                                                                      */
 
-// $Id: CloneableCollection.scala 12003 2007-06-13 12:14:15Z mihaylov $
+// $Id: DefaultEntry.scala 16893 2009-01-13 13:09:22Z cunei $
 
 
 package scalax.collection.mutable
 
-/** The J2ME version of the library defined this trait with a clone method
- * to substitute for the lack of Object.clone there
- */
-trait CloneableCollection {
-  override def clone(): AnyRef = super.clone()
-}
+@serializable
+final class DefaultEntry[A, B](val key: A, var value: B)
+      extends HashEntry[A, DefaultEntry[A, B]]
diff --git a/src/library/scalax/collection/mutable/DefaultMapModel.scala b/src/library/scalax/collection/mutable/DefaultMapModel.scala
new file mode 100644
index 0000000000..fda7798e26
--- /dev/null
+++ b/src/library/scalax/collection/mutable/DefaultMapModel.scala
@@ -0,0 +1,44 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: DefaultMapModel.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+package scalax.collection.mutable
+
+/** This class is used internally. It implements the mutable <code>Map</code>
+ *  class in terms of three functions: <code>findEntry</code>,
+ *  <code>addEntry</code>, and <code>entries</code>.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 08/07/2003
+ */
+trait DefaultMapModel[A, B] extends Map[A, B] {
+
+  type Entry = DefaultEntry[A, B]
+
+  protected def findEntry(key: A): Entry
+  protected def addEntry(e: Entry)
+  protected def entries: Iterator[Entry]
+
+  def get(key: A): Option[B] = {
+    val e = findEntry(key)
+    if (e == null) None
+    else Some(e.value);
+  }
+
+  def update(key: A, value: B): this.type = {
+    val e = findEntry(key)
+    if (e == null) addEntry(new Entry(key, value))
+    else e.value = value
+    this
+  }
+
+  def elements = entries map {e => (e.key, e.value)}
+}
+
diff --git a/src/library/scalax/collection/mutable/FlatHashTable.scala b/src/library/scalax/collection/mutable/FlatHashTable.scala
new file mode 100644
index 0000000000..c8fe2cede3
--- /dev/null
+++ b/src/library/scalax/collection/mutable/FlatHashTable.scala
@@ -0,0 +1,164 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: FlatHashTable.scala 16893 2009-01-13 13:09:22Z cunei $
+
+package scalax.collection.mutable
+
+trait FlatHashTable[A] {
+
+  /** The load factor for the hash table; must be < 500 (0.5)
+   */
+  protected def loadFactor: Int = 450
+  protected final def loadFactorDenum = 1000
+
+  /** The initial size of the hash table.
+   */
+  protected def initialSize: Int = 16
+
+  private final val tableDebug = false
+
+  /** The actual hash table.
+   */
+  protected var table: scala.Array[AnyRef] =
+    if (initialSize == 0) null else new scala.Array(initialSize)
+
+  /** The number of mappings contained in this hash table.
+   */
+  protected var tableSize = 0
+
+  /** The next size value at which to resize (capacity * load factor).
+   */
+  protected var threshold: Int = newThreshold(initialSize)
+
+  /** Returns the number of entires in this hash table.
+   */
+  def size: Int = tableSize
+
+  def findEntry(elem: A): Option[A] = {
+    var h = index(elemHashCode(elem))
+    var entry = table(h)
+    while (null != entry && entry != elem) {
+      h = (h + 1) % table.length
+      entry = table(h)
+    }
+    if (null == entry) None else Some(entry.asInstanceOf[A])
+  }
+
+  def containsEntry(elem: A): Boolean = {
+    var h = index(elemHashCode(elem))
+    var entry = table(h)
+    while (null != entry && entry != elem) {
+      h = (h + 1) % table.length
+      entry = table(h)
+    }
+    null != entry
+  }
+
+  def addEntry(elem: A) : Boolean = {
+    var h = index(elemHashCode(elem))
+    var entry = table(h)
+    while (null != entry) {
+      if (entry == elem) return false
+      h = (h + 1) % table.length
+      entry = table(h)
+    }
+    table(h) = elem.asInstanceOf[AnyRef]
+    tableSize = tableSize + 1
+    if (tableSize >= threshold) growTable()
+    true
+  }
+
+  def removeEntry(elem: A) : Option[A] = {
+    if (tableDebug) checkConsistent()
+    def precedes(i: Int, j: Int) = {
+      val d = table.length >> 1
+      if (i <= j) j - i < d
+      else i - j > d
+    }
+    var h = index(elemHashCode(elem))
+    var entry = table(h)
+    while (null != entry) {
+      if (entry == elem) {
+        var h0 = h
+        var h1 = (h0 + 1) % table.length
+        while (null != table(h1)) {
+          val h2 = index(elemHashCode(table(h1).asInstanceOf[A]))
+          //Console.println("shift at "+h1+":"+table(h1)+" with h2 = "+h2+"? "+(h2 != h1)+precedes(h2, h0)+table.length)
+          if (h2 != h1 && precedes(h2, h0)) {
+            //Console.println("shift "+h1+" to "+h0+"!")
+            table(h0) = table(h1)
+            h0 = h1
+          }
+          h1 = (h1 + 1) % table.length
+        }
+        table(h0) = null
+        tableSize -= 1
+        if (tableDebug) checkConsistent()
+        return Some(entry.asInstanceOf[A])
+      }
+      h = (h + 1) % table.length
+      entry = table(h)
+    }
+    None
+  }
+
+  def elements = new Iterator[A] {
+    private var i = 0
+    def hasNext: Boolean = {
+      while (i < table.length && (null == table(i))) i += 1;
+      i < table.length
+    }
+    def next(): A =
+      if (hasNext) { i += 1; table(i - 1).asInstanceOf[A] }
+      else Iterator.empty.next
+  }
+
+  private def growTable() {
+    val oldtable = table
+    table = new scala.Array[AnyRef](table.length * 2)
+    tableSize = 0
+    threshold = newThreshold(table.length)
+    var i = 0
+    while (i < oldtable.length) {
+      val entry = oldtable(i)
+      if (null != entry) addEntry(entry.asInstanceOf[A])
+      i += 1
+    }
+    if (tableDebug) checkConsistent()
+  }
+
+  private def checkConsistent() {
+    for (i <- 0 until table.length)
+      if (table(i) != null && !containsEntry(table(i).asInstanceOf[A]))
+        assert(false, i+" "+table(i)+" "+table.toString)
+  }
+
+  protected def elemHashCode(elem: A) = elem.hashCode()
+
+  protected final def improve(hcode: Int) = {
+    var h: Int = hcode + ~(hcode << 9)
+    h = h ^ (h >>> 14)
+    h = h + (h << 4)
+    h ^ (h >>> 10)
+  }
+
+  protected final def index(hcode: Int) = improve(hcode) & (table.length - 1)
+
+  private def newThreshold(size: Int) = {
+    val lf = loadFactor
+    assert(lf < (loadFactorDenum / 2), "loadFactor too large; must be < 0.5")
+    (size.toLong * lf / loadFactorDenum ).toInt
+  }
+
+  protected def clear() {
+    var i = table.length - 1
+    while (i >= 0) { table(i) = null; i -= 1 }
+    tableSize = 0
+  }
+}
diff --git a/src/library/scalax/collection/mutable/HashMap.scala b/src/library/scalax/collection/mutable/HashMap.scala
new file mode 100644
index 0000000000..4d3342636c
--- /dev/null
+++ b/src/library/scalax/collection/mutable/HashMap.scala
@@ -0,0 +1,43 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashMap.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+package scalax.collection.mutable
+
+import generic._
+
+/** This class implements mutable maps using a hashtable.
+ *
+ *  @author  Matthias Zenger
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+object HashMap  extends MapFactory[HashMap] {
+
+  /** The empty map of this type */
+  def empty[A, B] = new HashMap[A, B]
+
+}
+
+@serializable
+class HashMap[A, B]
+  extends Map[A, B]
+     with MapTemplate[A, B, HashMap]
+     with HashTable[A]
+     with DefaultMapModel[A, B] {
+
+  def empty[B] = HashMap.empty[A, B]
+
+  def -= (key: A) { removeEntry(key) }
+
+  override def clear() = super.clear()
+
+  override def clone(): Map[A, B] = new HashMap[A, B] ++ this
+}
diff --git a/src/library/scalax/collection/mutable/HashSet.scala b/src/library/scalax/collection/mutable/HashSet.scala
new file mode 100644
index 0000000000..601d0885c0
--- /dev/null
+++ b/src/library/scalax/collection/mutable/HashSet.scala
@@ -0,0 +1,48 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashSet.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+package scalax.collection.mutable
+
+import generic.{SetTemplate, SetFactory, AddableBuilder}
+
+/** Factory object for `HashSet` class */
+object HashSet extends SetFactory[HashSet] {
+  /** The empty set of this type */
+  def empty[A] = new HashSet[A]
+}
+
+/** This class implements mutable sets using a hashtable.
+ *
+ *  @author  Matthias Zenger
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
+ */
+@serializable
+class HashSet[A]
+  extends Set[A]
+     with SetTemplate[HashSet, A]
+     with FlatHashTable[A] {
+
+  def contains(elem: A): Boolean = containsEntry(elem)
+
+  def +=(elem: A) { addEntry(elem) }
+
+  def -=(elem: A) { removeEntry(elem) }
+
+  override def clear() = super.clear()
+
+  override def newBuilder[B]: generic.Builder[HashSet, B] =
+    new AddableBuilder[HashSet, B](HashSet.empty)
+
+  override def clone(): HashSet[A] = new HashSet[A] ++ this
+}
+
+
diff --git a/src/library/scalax/collection/mutable/HashTable.scala b/src/library/scalax/collection/mutable/HashTable.scala
new file mode 100644
index 0000000000..73ff61f3df
--- /dev/null
+++ b/src/library/scalax/collection/mutable/HashTable.scala
@@ -0,0 +1,172 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://www.scala-lang.org/           **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashTable.scala 16884 2009-01-09 16:52:09Z cunei $
+
+
+package scalax.collection.mutable
+
+/** This class can be used to construct data structures that are based
+ *  on hashtables. Class <code>HashTable[A]</code> implements a hashtable
+ *  that maps keys of type <code>A</code> to values of the fully abstract
+ *  member type <code>Entry</code>. Classes that make use of <code>HashTable</code>
+ *  have to provide an implementation for <code>Entry</code>
+ *
+ *  There are mainly two parameters that affect the performance of a hashtable:
+ *  the <i>initial size</i> and the <i>load factor</i>. The <i>size</i>
+ *  refers to the number of <i>buckets</i> in the hashtable, and the <i>load
+ *  factor</i> is a measure of how full the hashtable is allowed to get before
+ *  its size is automatically doubled. Both parameters may be changed by
+ *  overriding the corresponding values in class <code>HashTable</code>.
+ *
+ *  @author  Matthias Zenger
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
+ */
+trait HashTable[A] extends AnyRef {
+
+  protected type Entry >: Null <: HashEntry[A, Entry]
+
+  /** The load factor for the hash table (in 0.001 step).
+   */
+  protected def loadFactor: Int = 750 // corresponds to 75%
+  protected final val loadFactorDenum = 1000;
+
+  /** The initial size of the hash table.
+   */
+  protected def initialSize: Int = 16
+
+  /** The initial threshold
+   */
+  protected def initialThreshold: Int = newThreshold(initialSize)
+
+  /** The actual hash table.
+   */
+  protected var table: scala.Array[HashEntry[A, Entry]] =
+    if (initialSize == 0) null else new scala.Array(initialSize)
+
+  /** The number of mappings contained in this hash table.
+   */
+  protected var tableSize: Int = 0
+
+  /** The next size value at which to resize (capacity * load factor).
+   */
+  protected var threshold: Int = initialThreshold
+
+  /** Returns the size of this hash table.
+   */
+  def size = tableSize
+
+  protected def findEntry(key: A): Entry = {
+    val h = index(elemHashCode(key))
+    var e = table(h).asInstanceOf[Entry]
+    while (e != null && !elemEquals(e.key, key)) e = e.next
+    e
+  }
+
+  protected def addEntry(e: Entry) {
+    val h = index(elemHashCode(e.key))
+    e.next = table(h).asInstanceOf[Entry]
+    table(h) = e
+    tableSize = tableSize + 1
+    if (tableSize > threshold)
+      resize(2 * table.length)
+  }
+
+  protected def removeEntry(key: A) : Option[Entry] = {
+    val h = index(elemHashCode(key))
+    var e = table(h).asInstanceOf[Entry]
+    if (e != null) {
+      if (elemEquals(e.key, key)) {
+        table(h) = e.next
+        tableSize = tableSize - 1
+        return Some(e)
+      } else {
+        var e1 = e.next
+        while (e1 != null && !elemEquals(e1.key, key)) {
+          e = e1
+          e1 = e1.next
+        }
+        if (e1 != null) {
+          e.next = e1.next
+          tableSize = tableSize - 1
+          return Some(e1)
+        }
+      }
+    }
+    None
+  }
+
+  protected def entries: Iterator[Entry] = new Iterator[Entry] {
+    val iterTable = table
+    var idx = table.length - 1
+    var es = iterTable(idx).asInstanceOf[Entry]
+    scan()
+    def hasNext = es != null
+    def next = {
+      val res = es
+      es = es.next
+      scan()
+      res
+    }
+    def scan() {
+      while (es == null && idx > 0) {
+        idx = idx - 1
+        es = iterTable(idx).asInstanceOf[Entry]
+      }
+    }
+  }
+
+  def clear() {
+    var i = table.length - 1
+    while (i >= 0) { table(i) = null; i = i - 1 }
+    tableSize = 0
+  }
+
+  private def newThreshold(size: Int) =
+    ((size.toLong * loadFactor)/loadFactorDenum).toInt
+
+  private def resize(newSize: Int) = {
+    val oldTable = table
+    table = new scala.Array(newSize)
+    var i = oldTable.length - 1
+    while (i >= 0) {
+      var e = oldTable(i)
+      while (e != null) {
+        val h = index(elemHashCode(e.key))
+        val e1 = e.next
+        e.next = table(h).asInstanceOf[Entry]
+        table(h) = e
+        e = e1
+      }
+      i = i - 1
+    }
+    threshold = newThreshold(newSize)
+  }
+
+  protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2)
+
+  protected def elemHashCode(key: A) = key.hashCode()
+
+  protected final def improve(hcode: Int) = {
+    var h: Int = hcode + ~(hcode << 9)
+    h = h ^ (h >>> 14)
+    h = h + (h << 4)
+    h ^ (h >>> 10)
+  }
+
+  protected final def index(hcode: Int) = improve(hcode) & (table.length - 1)
+}
+
+trait HashEntry[A, E] {
+  val key: A
+  var next: E = _
+}
+
+
+
diff --git a/src/library/scalax/collection/mutable/ListBuffer.scala b/src/library/scalax/collection/mutable/ListBuffer.scala
index dff29f6453..4d0ad7ec80 100644
--- a/src/library/scalax/collection/mutable/ListBuffer.scala
+++ b/src/library/scalax/collection/mutable/ListBuffer.scala
@@ -11,7 +11,7 @@
 
 package scalax.collection.mutable
 
-import generic.{SequenceForwarder, SequenceFactory, SequenceTemplate}
+import generic._
 import immutable.List
 import collection.immutable.{List, Nil, ::}
 
@@ -31,6 +31,8 @@ object ListBuffer extends SequenceFactory[ListBuffer] {
 final class ListBuffer[A]
       extends Buffer[A]
          with SequenceTemplate[ListBuffer, A]
+         with Addable[ListBuffer[A], A]
+         with Subtractable[ListBuffer[A], A]
          with Builder[List, A]
          with SequenceForwarder[A]
 {
diff --git a/src/library/scalax/collection/mutable/Map.scala b/src/library/scalax/collection/mutable/Map.scala
new file mode 100755
index 0000000000..43f42df298
--- /dev/null
+++ b/src/library/scalax/collection/mutable/Map.scala
@@ -0,0 +1,75 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Map.scala 16884 2009-01-09 16:52:09Z cunei $
+
+
+package scalax.collection.mutable
+
+import generic._
+
+/* Factory object for `Map` class */
+object Map extends MapFactory[Map] {
+  def empty[A, B]: Map[A, B] = new HashMap[A, B]
+}
+
+trait Map[A, B]
+  extends collection.Map[A, B]
+     with MapTemplate[A, B, Map]
+     with Growable[(A, B)]
+     with Shrinkable[A]
+     with Cloneable[Map[A, B]] {
+self =>
+
+  override def thisCC: Map[A, B] = this
+
+  /** This method allows one to add a new mapping from <code>key</code>
+   *  to <code>value</code> to the map. If the map already contains a
+   *  mapping for <code>key</code>, it will be overridden by this
+   *  function.
+   *
+   * @param key    The key to update
+   * @param value  The new value
+   */
+  def update(key: A, value: B): this.type
+
+  /** Add a key/value pair to this map.
+   *  @param    kv the key/value pair.
+   */
+  def += (kv: (A, B)) { update(kv._1, kv._2) }
+
+  /** Remove a key from this map, noop if key is not present.
+   *  @param    key the key to be removed
+   */
+  def -= (key: A)
+
+  def -(key: A): this.type = { -=(key); this }
+
+  /** Removes all elements from the set for
+   *  which the predicate <code>p</code> yields the value <code>false</code>.
+   */
+  def retain(p: A => Boolean): Unit = for ((k, v) <- this) if (!p(k)) -=(k)
+
+  /** Removes all elements from the set. After this operation is completed,
+   *  the set will be empty.
+   */
+  def clear() { for ((k, v) <- elements) -=(k) }
+
+  override def clone(): Map[A, B] = empty[B] ++ this
+
+  /** Return a read-only projection of this set !!! just us an (immutable) setProxy? */
+  def readOnly : collection.Map[A, B] = new collection.Map[A, B] {
+    override def size = self.size
+    override def update(key: A, value: B) = self.update(key, value)
+    override def - (elem: A) = self - elem
+    override def elements = self.elements
+    override def foreach(f: ((A, B)) => Unit) = self.foreach(f)
+    override def empty[C] = self.empty[C]
+    def get(key: A) = self.get(key)
+  }
+}
diff --git a/src/library/scalax/collection/mutable/Set.scala b/src/library/scalax/collection/mutable/Set.scala
index 40dc643012..78f3234336 100644
--- a/src/library/scalax/collection/mutable/Set.scala
+++ b/src/library/scalax/collection/mutable/Set.scala
@@ -12,14 +12,13 @@
 package scalax.collection.mutable
 
 import collection.generic._
-import collection.generic.mutable.{Growable, Shrinkable}
 
 /** The canonical factory methods for <a href="Set.html">mutable sets</a>.
  *  Currently these return <a href="HashSet.html">HashSet's</a>.
  */
 object Set extends generic.SetFactory[Set] {
   /** The empty map of this type; this is implemented as a hashtable */
-  def empty[A]: Set[A] = null // !!! new HashSet[A]
+  def empty[A]: Set[A] = new HashSet[A]
 }
 
 /** This class represents mutable sets. Concrete set implementations
@@ -32,13 +31,13 @@ object Set extends generic.SetFactory[Set] {
  *  @author Martin Odersky
  *  @version 2.8
  */
-@cloneable
-trait Set[A] extends OrderedIterable[A]
-                with collection.Set[A]
+trait Set[A] extends collection.Set[A]
                 with SetTemplate[Set, A]
+                with Addable[Set[A], A]
+                with Subtractable[Set[A], A]
                 with Growable[A]
                 with Shrinkable[A]
-                with Cloneable[A] {
+                with Cloneable[Set[A]] {
 self =>
 
   /** This method allows one to add or remove an element <code>elem</code>
@@ -51,7 +50,7 @@ self =>
     if (included) this += elem else this -= elem
   }
 
-  /** Add a new element to the set.
+  /** Adds a new element to the set.
    *
    *  @param elem the element to be added
    */
@@ -62,18 +61,17 @@ self =>
    */
   def -=(elem: A)
 
-  // Bridge methods to methods in Growable/Shrinkable;
-  // we can't directly inherit these because they override nothing.
-
-  override def - (elem: A): this.type = super.-(elem)
-  override def - (elem1: A, elem2: A, elems: A*): this.type = super.-(elem1, elem2, elems: _*)
-  override def -- (elems: collection.Iterable[A]): this.type = super.--(elems)
-  override def -- (elems: Iterator[A]): this.type = super.--(elems)
+  /** Adds a new element to the set and returns the set itself.
+   *
+   *  @param elem the element to be added
+   */
+  def +(elem: A): this.type = { +=(elem); this }
 
-  override def + (elem: A): this.type = super.+(elem)
-  override def + (elem1: A, elem2: A, elems: A*): this.type = super.+(elem1, elem2, elems: _*)
-  override def ++ (elems: collection.Iterable[A]): this.type = super.++(elems)
-  override def ++ (elems: Iterator[A]): this.type = super.++(elems)
+  /** Removed a new element from the set and returns the set itself.
+   *
+   *  @param elem the element to be added
+   */
+  def -(elem: A): this.type = { -=(elem); this }
 
   /** This method computes an intersection with set <code>that</code>.
    *  It removes all the elements that are not present in <code>that</code>.
@@ -90,14 +88,16 @@ self =>
   /** Removes all elements from the set. After this operation is completed,
    *  the set will be empty.
    */
-  def clear() { elements foreach -= }
+  def clear() { foreach(-=) }
+
+  override def clone(): Set[A] = { val b = newBuilder[A]; b ++= this; b.result }
 
   /** Send a message to this scriptable object.
    *
    *  @param cmd  the message to send.
    *  @throws <code>Predef.UnsupportedOperationException</code>
    *  if the message was not understood.
-  def <<(cmd: Message[A]): Unit = cmd match {
+   def <<(cmd: Message[A]): Unit = cmd match {
     case Include(elem) => this += elem
     case Remove(elem) => this -= elem
     case Reset() => clear
diff --git a/src/library/scalax/collection/mutable/StringBuilder.scala b/src/library/scalax/collection/mutable/StringBuilder.scala
index 3152182dc4..30aeba4aed 100755
--- a/src/library/scalax/collection/mutable/StringBuilder.scala
+++ b/src/library/scalax/collection/mutable/StringBuilder.scala
@@ -12,7 +12,6 @@
 package scalax.collection.mutable
 
 import scalax.collection.generic._
-import scalax.collection.generic.mutable.Growable
 import scalax.runtime._
 
 
diff --git a/src/library/scalax/collection/mutable/Vector.scala b/src/library/scalax/collection/mutable/Vector.scala
index aef1c75d94..1813172fbf 100644
--- a/src/library/scalax/collection/mutable/Vector.scala
+++ b/src/library/scalax/collection/mutable/Vector.scala
@@ -12,7 +12,7 @@ package scalax.collection.mutable
 
 import generic._
 
-trait Vector[A] extends Sequence[A] with collection.Vector[A] with generic.mutable.VectorTemplate[Vector, A]
+trait Vector[A] extends Sequence[A] with collection.Vector[A] with MutableVectorTemplate[Vector, A]
 
 /* Factory object for `Vector` class */
 object Vector extends SequenceFactory[Vector] {
diff --git a/src/library/scalax/runtime/BoxedArray.scala b/src/library/scalax/runtime/BoxedArray.scala
index 388d652882..47bb3a0d64 100755
--- a/src/library/scalax/runtime/BoxedArray.scala
+++ b/src/library/scalax/runtime/BoxedArray.scala
@@ -21,7 +21,7 @@ import collection.generic._
  *  @author  Martin Odersky, Stephane Micheloud
  *  @version 1.0
  */
-abstract class BoxedArray[A] extends Vector[A] with mutable.VectorTemplate[BoxedArray, A] with Boxed {
+abstract class BoxedArray[A] extends Vector[A] with MutableVectorTemplate[BoxedArray, A] with Boxed {
 
   /** The length of the array */
   def length: Int
diff --git a/src/library/scalax/runtime/StringVector.scala b/src/library/scalax/runtime/StringVector.scala
index c12243bed7..a612b7d7a5 100644
--- a/src/library/scalax/runtime/StringVector.scala
+++ b/src/library/scalax/runtime/StringVector.scala
@@ -13,7 +13,8 @@ package scalax.runtime
 
 import collection.immutable.Vector
 import collection.mutable.ArrayBuffer
-import collection.generic.covariant.VectorTemplate
+import collection.generic.VectorTemplate
+import annotation.unchecked.uncheckedVariance
 
 object StringVector {
 
@@ -22,7 +23,7 @@ object StringVector {
 }
 
 @cloneable
-abstract class StringVector[+A] extends VectorTemplate[StringVector, A] with Vector[A] {
+abstract class StringVector[+A] extends VectorTemplate[StringVector, A @uncheckedVariance] with Vector[A] {
 
   /** The length of the string */
   def length: Int