From f83d8977544ec7fc3eed59e032e3705f30290c00 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Tue, 9 Dec 2008 17:40:50 +0000 Subject: updates to scalax collections and standard libr... updates to scalax collections and standard library classes. --- src/library/scalax/collection/Iterable.scala | 37 +- src/library/scalax/collection/Iterator.scala | 47 +- src/library/scalax/collection/LazyBuilder.scala | 24 + .../scalax/collection/OrderedIterable.scala | 3 +- src/library/scalax/collection/Sequence.scala | 3 +- src/library/scalax/collection/Vector.scala | 3 +- .../collection/generic/IterableFactory.scala | 3 + .../collection/generic/IterableForwarder.scala | 2 +- .../collection/generic/IterableTemplate.scala | 110 ++- .../collection/generic/SequenceFactory.scala | 2 +- .../collection/generic/SequenceTemplate.scala | 22 +- .../scalax/collection/generic/SequenceView.scala | 4 +- .../generic/covariant/IterableFactory.scala | 8 +- .../covariant/OrderedIterableTemplate.scala | 2 +- .../generic/covartest/IterableForwarder.scala | 61 ++ .../generic/covartest/IterableTemplate.scala | 4 +- .../covartest/OrderedIterableTemplate.scala | 6 + .../generic/covartest/SequenceFactory.scala | 2 +- .../generic/covartest/SequenceForwarder.scala | 50 ++ .../generic/covartest/SequenceTemplate.scala | 2 +- .../generic/covartest/SequenceView.scala | 4 +- .../generic/covartest/VectorTemplate.scala | 2 +- .../generic/mutable/VectorTemplate.scala | 2 +- .../collection/generic/mutable/VectorView.scala | 2 +- .../scalax/collection/immutable/Iterable.scala | 22 + src/library/scalax/collection/immutable/List.scala | 680 ++++++------------ .../collection/immutable/OrderedIterable.scala | 22 + .../scalax/collection/immutable/Sequence.scala | 22 + .../scalax/collection/immutable/Stream.scala | 790 +++++++++++++++++++++ .../scalax/collection/immutable/Vector.scala | 22 + .../scalax/collection/mutable/Appendable.scala | 4 +- src/library/scalax/collection/mutable/Buffer.scala | 8 +- .../scalax/collection/mutable/ResizableArray.scala | 2 +- src/library/scalax/collection/mutable/Vector.scala | 2 +- src/library/scalax/util/control/TailRec.scala | 24 + 35 files changed, 1391 insertions(+), 612 deletions(-) create mode 100755 src/library/scalax/collection/LazyBuilder.scala create mode 100755 src/library/scalax/collection/generic/covartest/IterableForwarder.scala create mode 100644 src/library/scalax/collection/generic/covartest/SequenceForwarder.scala create mode 100644 src/library/scalax/collection/immutable/Iterable.scala create mode 100644 src/library/scalax/collection/immutable/OrderedIterable.scala create mode 100644 src/library/scalax/collection/immutable/Sequence.scala create mode 100755 src/library/scalax/collection/immutable/Stream.scala create mode 100644 src/library/scalax/collection/immutable/Vector.scala create mode 100644 src/library/scalax/util/control/TailRec.scala (limited to 'src/library/scalax') diff --git a/src/library/scalax/collection/Iterable.scala b/src/library/scalax/collection/Iterable.scala index b6abd8d559..8775fcb22a 100755 --- a/src/library/scalax/collection/Iterable.scala +++ b/src/library/scalax/collection/Iterable.scala @@ -12,6 +12,7 @@ package scalax.collection import generic._ +import collection.immutable.{List, Nil, ::} /** Collection classes mixing in this class provide a method * elements which returns an iterator over all the @@ -43,9 +44,9 @@ trait Iterable[+A] extends covariant.IterableTemplate[Iterable, A] { self => object Iterable extends covariant.IterableFactory[Iterable] { /** The empty iterable */ - val empty: Iterable[Nothing] = null // !!! + val empty: Iterable[Nothing] = Nil - class OrderedIterableOps[A](seq: Iterable[A], cmp: Ordering[A]) { + class ComparableIterableOps[A](seq: Iterable[A], cmp: Ordering[A]) { def min: A = { require(!seq.isEmpty, "min()") var acc = seq.elements.next @@ -75,16 +76,32 @@ object Iterable extends covariant.IterableFactory[Iterable] { } } - class IterableIterableOps[C[+B] <: Iterable[B], A](self: C[Iterable[A]]) { + class IterableIterableOps[C[+B] <: Iterable[B] with covariant.IterableTemplate[C, B], A](self: C[C[A]]) { def flatten: C[A] = { - val b = self.newBuilder[A].asInstanceOf[Builder[C, A]] + val b: 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 + for (xs <- self) { + var i = 0 + for (x <- xs) { + bs(i) += x + i += 1 + } + } + type CC[B] = C[C[B]] + val bb = self.newBuilder[C[A]] + for (b <- bs) bb += b.result + bb.result + } } - class PairCollectionOps[C[+B] <: Iterable[B], A1, A2](self: C[(A1, A2)]) { + + class PairIterableOps[C[+B] <: Iterable[B], A1, A2](self: C[(A1, A2)]) { def unzip: (C[A1], C[A2]) = { val as = self.newBuilder[A1].asInstanceOf[Builder[C, A1]] val bs = self.newBuilder[A2].asInstanceOf[Builder[C, A2]] @@ -96,14 +113,14 @@ object Iterable extends covariant.IterableFactory[Iterable] { } } - implicit def orderedIterableWrapper[A](seq: Iterable[A])(implicit cmp: Ordering[A]) = - new OrderedIterableOps(seq, cmp) + implicit def comparableIterableWrapper[A](seq: Iterable[A])(implicit cmp: Ordering[A]) = + 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], A](seq: C[Iterable[A]]) = + implicit def iterableIterableWrapper[C[+B] <: Iterable[B] with covariant.IterableTemplate[C, B], A](seq: C[C[A]]) = new IterableIterableOps[C, A](seq) - implicit def pairCollectionWrapper[C[+B] <: Iterable[B], A1, A2](seq: C[(A1, A2)]) = - new PairCollectionOps[C, A1, A2](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] = covariant.IterableView[UC, A] diff --git a/src/library/scalax/collection/Iterator.scala b/src/library/scalax/collection/Iterator.scala index 2758faf854..20ba9ba820 100755 --- a/src/library/scalax/collection/Iterator.scala +++ b/src/library/scalax/collection/Iterator.scala @@ -12,7 +12,7 @@ package scalax.collection import mutable.{Buffer, ArrayBuffer, ListBuffer} -import immutable.{List, Nil, ::} +import immutable.{List, Nil, ::, Stream} /** The Iterator object provides various functions for * creating specialized iterators. @@ -28,7 +28,20 @@ object Iterator { def next(): Nothing = throw new NoSuchElementException("next on empty iterator") } - def apply[A](args: A*): Iterator[A] = args.asInstanceOf[Iterable[A]].elements // !!! + /** + * @param x 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] { + private var hasnext = true + def hasNext: Boolean = hasnext + def next(): A = + if (hasnext) { hasnext = false; x } + else empty.next() + } + + def apply[A](args: A*): Iterator[A] = args.asInstanceOf[Iterable[A]].elements // !@! /** Concatenate all the argument iterators into a single iterator. * @@ -36,7 +49,7 @@ object Iterator { * @return the concatenation of all the lists */ def concat[A](xss: Iterator[A]*): Iterator[A] = - xss.asInstanceOf[Iterable[Iterator[A]]].elements.flatten // !!! + xss.asInstanceOf[Iterable[Iterator[A]]].elements.flatten // !@! /** An iterator that returns the same element a number of times * @param len The number of elements returned @@ -152,32 +165,14 @@ object Iterator { */ def flatten: Iterator[A] = new Iterator[A] { private var it = its.next - def hasNext: Boolean = { - while (!it.hasNext && its.hasNext) it = its.next - it.hasNext - } - def next(): A = - if (hasNext) it.next - else empty.next() + def hasNext: Boolean = if (it.hasNext) { it = its.next; hasNext } else false + def next(): A = if (hasNext) it.next else empty.next() } } implicit def iteratorIteratorWrapper[A](its: Iterator[Iterator[A]]): IteratorIteratorOps[A] = new IteratorIteratorOps[A](its) - /** - * @param x the element - * @return the iterator with one single element - * @deprecated use Iterator(x) instead - */ - @deprecated def single[a](x: a) = new Iterator[a] { - private var hasnext = true - def hasNext: Boolean = hasnext - def next(): a = - if (hasnext) { hasnext = false; x } - else empty.next() - } - /** @deprecated use `xs.elements` instead */ @deprecated def fromValues[a](xs: a*) = xs.elements @@ -198,7 +193,7 @@ object Iterator { * @deprecated use `xs.slice(start, start + length).elements` instead */ @deprecated def fromArray[a](xs: Array[a], start: Int, length: Int): Iterator[a] = - xs.slice(start, start + length).elements.asInstanceOf[Iterator[a]] // !!! + xs.slice(start, start + length).elements.asInstanceOf[Iterator[a]] // !@! /** * @param str the given string @@ -206,7 +201,7 @@ object Iterator { * @deprecated replaced by str.elements */ @deprecated def fromString(str: String): Iterator[Char] = - str.elements.asInstanceOf[Iterator[Char]] // !!! + str.elements.asInstanceOf[Iterator[Char]] // !@! /** * @param n the product arity @@ -889,7 +884,7 @@ self => def toSequence: Sequence[A] = { val buffer = new ArrayBuffer[A] this copyToBuffer buffer - null // !!! should be: buffer.readOnly + buffer.readOnly } /** Collect elements into a seq. diff --git a/src/library/scalax/collection/LazyBuilder.scala b/src/library/scalax/collection/LazyBuilder.scala new file mode 100755 index 0000000000..784d437eba --- /dev/null +++ b/src/library/scalax/collection/LazyBuilder.scala @@ -0,0 +1,24 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $ + +package scalax.collection + +import collection.mutable.ListBuffer +import collection.immutable.{List, Nil, ::} + +abstract class LazyBuilder[+CC[B], A] extends Builder[CC, A] { + protected var parts = new ListBuffer[Iterator[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 result: CC[A] + def clear() { parts.clear() } +} diff --git a/src/library/scalax/collection/OrderedIterable.scala b/src/library/scalax/collection/OrderedIterable.scala index 97bd96e667..bf28cbf083 100755 --- a/src/library/scalax/collection/OrderedIterable.scala +++ b/src/library/scalax/collection/OrderedIterable.scala @@ -12,6 +12,7 @@ package scalax.collection import generic._ +import immutable.Nil /** An ordered collection is a collection with a fixed sequence of elements * which corresponds to append order. In particular, it holds that @@ -36,6 +37,6 @@ trait OrderedIterable[+A] extends Iterable[A] with covariant.OrderedIterableTemp */ object OrderedIterable extends covariant.IterableFactory[OrderedIterable] { - val empty: OrderedIterable[Nothing] = null // !!! + val empty: OrderedIterable[Nothing] = Nil } diff --git a/src/library/scalax/collection/Sequence.scala b/src/library/scalax/collection/Sequence.scala index 0ee88e3575..e370684727 100755 --- a/src/library/scalax/collection/Sequence.scala +++ b/src/library/scalax/collection/Sequence.scala @@ -12,6 +12,7 @@ package scalax.collection import generic._ +import immutable.Nil /** Class Sequence[A] represents finite sequences of elements * of type A. @@ -25,7 +26,7 @@ trait Sequence[+A] extends OrderedIterable[A] with SizedIterable[A] with covaria object Sequence extends covariant.SequenceFactory[Sequence] { /** The empty sequence */ - val empty : Sequence[Nothing] = null // !!! + val empty : Sequence[Nothing] = immutable.Nil type View[+UC[+B] <: Sequence[B], +A] = covariant.SequenceView[UC, A] diff --git a/src/library/scalax/collection/Vector.scala b/src/library/scalax/collection/Vector.scala index 8787d7fd42..4e5df7e59d 100755 --- a/src/library/scalax/collection/Vector.scala +++ b/src/library/scalax/collection/Vector.scala @@ -11,11 +11,12 @@ package scalax.collection import generic._ +import mutable.ArrayBuffer trait Vector[+A] extends Sequence[A] with covariant.VectorTemplate[Vector, A] object Vector extends covariant.SequenceFactory[Vector] { /** The empty sequence */ - val empty : Vector[Nothing] = null // !!! + val empty : Vector[Nothing] = null // !!! todo: insert good immutable vector implementation here. } diff --git a/src/library/scalax/collection/generic/IterableFactory.scala b/src/library/scalax/collection/generic/IterableFactory.scala index 264e333ac5..1362e97079 100755 --- a/src/library/scalax/collection/generic/IterableFactory.scala +++ b/src/library/scalax/collection/generic/IterableFactory.scala @@ -8,6 +8,9 @@ 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 + // CC[Nothing]. This type does not make sense for immutable iterables. + /** Concatenate all the argument lists into a single list. * * @param xss the lists that are to be concatenated diff --git a/src/library/scalax/collection/generic/IterableForwarder.scala b/src/library/scalax/collection/generic/IterableForwarder.scala index fba1e6d0e9..91e527dafa 100644 --- a/src/library/scalax/collection/generic/IterableForwarder.scala +++ b/src/library/scalax/collection/generic/IterableForwarder.scala @@ -12,7 +12,7 @@ package scalax.collection.generic import collection.mutable.Buffer -import collection.immutable.List +import collection.immutable.{List, Stream} /** This trait implements a forwarder for iterable objects. It forwards * all calls to a different iterable object, except for diff --git a/src/library/scalax/collection/generic/IterableTemplate.scala b/src/library/scalax/collection/generic/IterableTemplate.scala index 01a23f5ecf..e5e22aa7c8 100755 --- a/src/library/scalax/collection/generic/IterableTemplate.scala +++ b/src/library/scalax/collection/generic/IterableTemplate.scala @@ -12,7 +12,7 @@ package scalax.collection.generic import scalax.collection.mutable.{Buffer, ArrayBuffer, ListBuffer} -import scalax.collection.immutable.{List, Nil, ::} +import scalax.collection.immutable.{List, Nil, ::, Stream} import util.control.Break._ import Iterable._ @@ -65,7 +65,7 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], */ 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 +75,7 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], 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 +85,12 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], b.result } - /** Returns the sequence resulting from applying the given function - * f to each element of this sequence. + /** Returns the iterable resulting from applying the given function + * f to each element of this iterable. * * @param f function to apply to each element. * @return f(a0), ..., f(an) if this - * sequence is a0, ..., an. + * iterable is a0, ..., an. */ def map[B](f: A => B): CC[B] = { val b = newBuilder[B] @@ -99,11 +99,11 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], } /** Applies the given function f 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 f(a0) ::: ... ::: f(an) if - * this sequence is a0, ..., an. + * this iterable is a0, ..., an. */ def flatMap[B](f: A => Iterable[B]): CC[B] = { val b = newBuilder[B] @@ -111,10 +111,10 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], b.result } - /** Returns all the elements of this sequence that satisfy the + /** Returns all the elements of this iterable that satisfy the * predicate p. The order of the elements is preserved. - * @param p the predicate used to filter the list. - * @return the elements of this list satisfying p. + * @param p the predicate used to filter the iterable. + * @return the elements of this iterable satisfying p. */ def filter(p: A => Boolean): CC[A] = { val b = newBuilder[A] @@ -128,7 +128,7 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], * predicate inversed. * * @param p the predicate to use to test elements - * @return the list without all elements which satisfy p + * @return the iterable without all elements which satisfy p */ def remove(p: A => Boolean): CC[A] = filter(!p(_)) @@ -203,6 +203,8 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], * 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 p, or None if none exists. @@ -221,8 +223,10 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], * the value z. * * @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 f(... (f(f(z, a0), a1) ...), - * an) if the list is + * an) if the iterable is * [a0, a1, ..., an]. */ def foldLeft[B](z: B)(op: (B, A) => B): B = { @@ -232,32 +236,40 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], result } - /** Combines the elements of this list together using the binary + /** Combines the elements of this iterable together using the binary * function f, from right to left, and starting with * the value z. * * @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 f(a0, f(a1, f(..., f(an, z)...))) - * if the list is [a0, a1, ..., an]. + * if the iterable is [a0, a1, ..., an]. */ def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op) /** Similar to foldLeft 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, z /: xs is the same as xs foldLeft z * @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 foldRight. * That is, xs :\ z is the same as xs foldRight z * @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 op, 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 op(... op(a0,a1), ..., an) if the iterable object has elements @@ -277,6 +289,8 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], /** Combines the elements of this iterable object together using the binary * operator op, 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 a0 op (... op (an-1 op an)...) @@ -288,7 +302,7 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], 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 +370,7 @@ b * @param thatElem element thatElem is used to fill up the } /** Fills the given array xs 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 +392,7 @@ b * @param thatElem element thatElem is used to fill up the } /** Fills the given array xs with the elements of - * this sequence starting at position start + * this iterable starting at position start * until either the end of the current iterable or the end of array `xs` is reached. * * @note Will not terminate for infinite-sized collections. @@ -411,7 +425,7 @@ b * @param thatElem element thatElem is used to fill up the * Returns a sequence containing all of the elements in this iterable object. * @note Will not terminate for infinite-sized collections. */ - def toSequence: Sequence[A] = toList.asInstanceOf[Sequence[A]] // !!! + def toSequence: Sequence[A] = toList /** @deprecated use toSequence instead */ @@ -431,7 +445,7 @@ b * @param thatElem element thatElem 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 * <(e1: a, e2: a) => Boolean. * @ex 
    *    List("Steve", "Tom", "John", "Bob")
@@ -454,7 +468,6 @@ b   *  @param thatElem element thatElem is used to fill up the
    *  sep.
    *
    *  @ex  List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"
-   *  @note Will not terminate for infinite-sized collections.
    *  @param start starting string.
    *  @param sep separator string.
    *  @param end ending string.
@@ -467,7 +480,6 @@ b   *  @param thatElem element thatElem is used to fill up the
    *  representations of elements (w.r.t. the method toString())
    *  are separated by the string sep.
    *
-   *  @note Will not terminate for infinite-sized collections.
    *  @param sep separator string.
    *  @return a string representation of this iterable object.
    */
@@ -475,7 +487,6 @@ b   *  @param thatElem element thatElem is used to fill up the
     addString(new StringBuilder(), sep).toString
 
   /** Converts a collection into a flat String by each element's toString method.
-   *  @note Will not terminate for infinite-sized collections.
    */
   def mkString =
     addString(new StringBuilder()).toString
@@ -485,7 +496,6 @@ b   *  @param thatElem element thatElem is used to fill up the
    *  end. Inside, the string representations of elements (w.r.t.
    *  the method toString()) are separated by the string
    *  sep.
-   *  @note Will not terminate for infinite-sized collections.
    */
   def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
     b append start
@@ -501,28 +511,13 @@ b   *  @param thatElem element thatElem 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 toString())
    *  are separated by the string sep.
-   *  @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 filter,
@@ -557,10 +552,10 @@ b   *  @param thatElem element thatElem 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 +569,7 @@ b   *  @param thatElem element thatElem is used to fill up the
   def headOption: Option[A] = if (isEmpty) None else Some(head)
 
   /** @deprecated use headOption instead
-   *  None if list is empty.
+   *  None if iterable is empty.
    */
   @deprecated def firstOption: Option[A] = headOption
 
@@ -589,7 +584,6 @@ b   *  @param thatElem element thatElem is used to fill up the
    *  than n 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] = {
@@ -650,7 +644,7 @@ b   *  @param thatElem element thatElem is used to fill up the
 
   /** The last element of this iterable.
    *
-   *  @throws Predef.NoSuchElementException if the sequence is empty.
+   *  @throws Predef.NoSuchElementException if the iterable is empty.
    *  @note  Might return different results for different runs, unless this iterable is ordered
    */
   def last: A = {
@@ -669,9 +663,11 @@ b   *  @param thatElem element thatElem is used to fill up the
   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) {
@@ -732,12 +728,10 @@ b   *  @param thatElem element thatElem is used to fill up the
     (l.result, r.result)
   }
 
-  /** Returns the longest prefix of this sequence whose elements satisfy
+  /** Returns the longest prefix of this iterable whose elements satisfy
    *  the predicate p.
    *
    *  @param p the test predicate.
-   *  @return  the longest prefix of this sequence whose elements satisfy
-   *           the predicate p.
    *  @note  Might return different results for different runs, unless this iterable is ordered
    */
   def takeWhile(p: A => Boolean): CC[A] = {
@@ -751,12 +745,10 @@ b   *  @param thatElem element thatElem is used to fill up the
     b.result
   }
 
-  /** Returns the longest suffix of this sequence whose first element
+  /** Returns the longest suffix of this iterable whose first element
    *  does not satisfy the predicate p.
    *
    *  @param p the test predicate.
-   *  @return  the longest suffix of the sequence whose first element
-   *           does not satisfy the predicate p.
    *  @note  Might return different results for different runs, unless this iterable is ordered
    */
   def dropWhile(p: A => Boolean): CC[A] = {
@@ -769,12 +761,12 @@ b   *  @param thatElem element thatElem is used to fill up the
     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.
+ /** 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 list whose
-   *           elements all satisfy p, and the rest of the list.
+   *  @return  a pair consisting of the longest prefix of the iterable whose
+   *           elements all satisfy p, 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]) = {
@@ -801,13 +793,13 @@ b   *  @param thatElem element thatElem is used to fill up the
     !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/SequenceFactory.scala b/src/library/scalax/collection/generic/SequenceFactory.scala
index ee97c80c75..26818c49c9 100755
--- a/src/library/scalax/collection/generic/SequenceFactory.scala
+++ b/src/library/scalax/collection/generic/SequenceFactory.scala
@@ -7,5 +7,5 @@ trait SequenceFactory[CC[A] <: Sequence[A]] extends IterableFactory[CC] {
    *  @param x the selector value
    *  @return  sequence wrapped in an option, if this is a Sequence, otherwise none
    */
-  def unapplySequence[A](x: CC[A]): Some[CC[A]] = Some(x)
+  def unapplySeq[A](x: CC[A]): Some[CC[A]] = Some(x)
 }
diff --git a/src/library/scalax/collection/generic/SequenceTemplate.scala b/src/library/scalax/collection/generic/SequenceTemplate.scala
index eba0e4bf98..b4a2c6f95a 100755
--- a/src/library/scalax/collection/generic/SequenceTemplate.scala
+++ b/src/library/scalax/collection/generic/SequenceTemplate.scala
@@ -53,13 +53,6 @@ self /*: CC[A]*/ =>
    */
   def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length)
 
-  /** Returns index of the first element satisying a predicate, or -1, if none exists.
-   *
-   *  @note may not terminate for infinite-sized collections.
-   *  @param  p the predicate
-   */
-  def indexWhere(p: A => Boolean): Int = indexWhere(p, 0)
-
   /** Returns length of longest segment starting from a start index `from`
    *  such that every element of the segment satisfies predicate `p`.
    *  @note may not terminate for infinite-sized collections.
@@ -85,6 +78,13 @@ self /*: CC[A]*/ =>
    */
   def prefixLength(p: A => Boolean) = segmentLength(p, 0)
 
+  /** Returns index of the first element satisfying a predicate, or -1, if none exists.
+   *
+   *  @note may not terminate for infinite-sized collections.
+   *  @param  p the predicate
+   */
+  def indexWhere(p: A => Boolean): Int = indexWhere(p, 0)
+
   /** Returns index of the first element starting from a start index
    *  satisying a predicate, or -1, if none exists.
    *
@@ -303,10 +303,8 @@ self /*: CC[A]*/ =>
     b.result
   }
 
-  /** Returns a sequence of given length containing the elements of this sequence followed by zero
-   *  or more occurrences of given elements. If this sequence is already at least as long as given
-   *  length, it is returned directly. Otherwise, a new sequence is created consisting of the elements
-   *  of this sequence followed by enough occurrences of the given elements to reach the given length.
+  /** Returns a new sequence of given length containing the elements of this sequence followed by zero
+   *  or more occurrences of given elements.
    */
   def padTo[B >: A](len: Int, elem: B): CC[B] = {
     var diff = len - length
@@ -324,7 +322,7 @@ self /*: CC[A]*/ =>
    *
    *  @return  the sequence itself
    */
-  override def toSequence: Sequence[A] = this.asInstanceOf[Null] // !!!
+  override def toSequence: Sequence[A] = thisCC
 
   def indices: Range = 0 until length
 
diff --git a/src/library/scalax/collection/generic/SequenceView.scala b/src/library/scalax/collection/generic/SequenceView.scala
index 6178542241..43ce49d3a5 100755
--- a/src/library/scalax/collection/generic/SequenceView.scala
+++ b/src/library/scalax/collection/generic/SequenceView.scala
@@ -69,7 +69,7 @@ self =>
 
   class Patched[/*+*/B >: A](from: Int, patch: Sequence[B], replaced: Int) extends Transformed[B] {
     val plen = patch.length
-    override def elements: Iterator[B] = self.elements patch (from, patch.asInstanceOf[Null], replaced) // !!!
+    override def elements: Iterator[B] = self.elements patch (from, patch, replaced)
     override def length: Int = self.length + plen - replaced
     override def apply(idx: Int): B =
       if (idx < from) self.apply(idx)
@@ -101,7 +101,7 @@ self =>
   override def zip[B](that: Iterable[B]): SequenceView[UC, (A, B)] =
     new Zipped(that.toSequence).asCC
   override def zipWithIndex: SequenceView[UC, (A, Int)] =
-    zip((0 until length).asInstanceOf[Null]) // !!!
+    zip((0 until length).asInstanceOf[Null]) // !@!
     /*
   override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): SequenceView[UC, (A1, B1)] = {
     val that1 = that.toSequence
diff --git a/src/library/scalax/collection/generic/covariant/IterableFactory.scala b/src/library/scalax/collection/generic/covariant/IterableFactory.scala
index 67445f54d9..0fd2284cea 100755
--- a/src/library/scalax/collection/generic/covariant/IterableFactory.scala
+++ b/src/library/scalax/collection/generic/covariant/IterableFactory.scala
@@ -7,8 +7,14 @@ trait IterableFactory[CC[+A] <: Iterable[A]] extends generic.IterableFactory[CC]
 
   override protected def newBuilder[A]: Builder[CC, A] =
     empty.newBuilder[A].asInstanceOf[Builder[CC, A]]
+     // the cast here is unavoidable because CC is not constrained with covariant.IterableTemplate[CC, A]
+     // It's can't be constrained because some suntype links between covariant and generic Templates
+     // are missing. That's a consequence of our hacks to have both nonvariant and covariant templates.
 
   /** Create CC collection of specified elements */
   override def apply[A](args: A*): CC[A] =
-    (empty ++ args.asInstanceOf[Iterable[A]]).asInstanceOf[CC[A]] // !!!
+    (empty ++ args.asInstanceOf[Iterable[A]]).asInstanceOf[CC[A]]
+     // the cast here is unavoidable because CC is not constrained with covariant.IterableTemplate[CC, A]
+     // It's can't be constrained because some suntype links between covariant and generic Templates
+     // are missing. That's a consequence of our hacks to have both nonvariant and covariant templates.
 }
diff --git a/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala
index 449bac9cfc..38c1c2ab4c 100755
--- a/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala
+++ b/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala
@@ -13,5 +13,5 @@ package scalax.collection.generic.covariant
 
 import annotation.unchecked.uncheckedVariance
 
-trait OrderedIterableTemplate[+CC[+B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], +A]
+trait OrderedIterableTemplate[+CC[+B] <: OrderedIterable[B] with OrderedIterableTemplate[CC, B], +A]
   extends generic.OrderedIterableTemplate[CC, A @uncheckedVariance] {self /*: CC[A]*/ => }
diff --git a/src/library/scalax/collection/generic/covartest/IterableForwarder.scala b/src/library/scalax/collection/generic/covartest/IterableForwarder.scala
new file mode 100755
index 0000000000..9d78cb18e0
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/IterableForwarder.scala
@@ -0,0 +1,61 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: IterableProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $
+
+
+package scalax.collection.generic.covartest
+
+import collection.mutable.Buffer
+import collection.immutable.{List, Stream}
+
+/** 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 objetc of the same kind
+ *
+ *  The above methods are forwarded by subclass IterableProxy
+ *
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+trait IterableForwarder[+A] extends Iterable[A] {
+
+  /** The iterable object to which calls are forwarded */
+  protected def underlying: Iterable[A]
+
+  // Iterable delegates
+  // Iterable methods could be printed by  cat IterableTemplate.scala | sed -n '/trait Iterable/,$ p' | egrep '^  (override )?def'
+
+  override def elements = underlying.elements
+  override def isEmpty = underlying.isEmpty
+  override def hasDefiniteSize = underlying.hasDefiniteSize
+  override def foreach(f: A => Unit) = underlying.foreach(f)
+  override def forall(p: A => Boolean): Boolean = underlying.forall(p)
+  override def exists(p: A => Boolean): Boolean = underlying.exists(p)
+  override def count(p: A => Boolean): Int = underlying.count(p)
+  override def find(p: A => Boolean): Option[A] = underlying.find(p)
+  override def foldLeft[B](z: B)(op: (B, A) => B): B = underlying.foldLeft(z)(op)
+  override def foldRight[B](z: B)(op: (A, B) => B): B = underlying.foldRight(z)(op)
+  override def reduceLeft[B >: A](op: (B, A) => B): B = underlying.reduceLeft(op)
+  override def reduceRight[B >: A](op: (A, B) => B): B = underlying.reduceRight(op)
+  override def copyToBuffer[B >: A](dest: Buffer[B]) = underlying.copyToBuffer(dest)
+  override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) = underlying.copyToArray(xs, start, len)
+  override def toArray[B >: A]: Array[B] = underlying.toArray
+  override def toList: List[A] = underlying.toList
+  override def toSequence: Sequence[A] = underlying.toSequence
+  override def toStream: Stream[A] = underlying.toStream
+  override def mkString(start: String, sep: String, end: String): String = underlying.mkString(start, sep, end)
+  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 b83f3b9247..eb4281b427 100755
--- a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala
+++ b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala
@@ -12,7 +12,7 @@
 package scalax.collection.generic.covartest
 
 import scalax.collection.mutable.{Buffer, ArrayBuffer, ListBuffer}
-import scalax.collection.immutable.{List, Nil, ::}
+import scalax.collection.immutable.{List, Nil, ::, Stream}
 import util.control.Break._
 import Iterable._
 
@@ -411,7 +411,7 @@ b   *  @param thatElem element thatElem is used to fill up the
    *  Returns a sequence containing all of the elements in this iterable object.
    *  @note Will not terminate for infinite-sized collections.
    */
-  def toSequence: Sequence[A] = toList.asInstanceOf[Sequence[A]] // !!!
+  def toSequence: Sequence[A] = toList
 
   /** @deprecated use toSequence instead
    */
diff --git a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala
index c6be1a5acd..5256a4e40d 100755
--- a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala
+++ b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala
@@ -13,5 +13,11 @@ package scalax.collection.generic.covartest
 
 import OrderedIterable._
 
+/** 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`:
+ *
+ *  `(xs ++ ys).elements = xs.elements ++ ys.elements
+ */
 trait OrderedIterableTemplate[+CC[+B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], +A]
   extends IterableTemplate[CC, A]
diff --git a/src/library/scalax/collection/generic/covartest/SequenceFactory.scala b/src/library/scalax/collection/generic/covartest/SequenceFactory.scala
index 1fb85d02db..eb6c093bff 100755
--- a/src/library/scalax/collection/generic/covartest/SequenceFactory.scala
+++ b/src/library/scalax/collection/generic/covartest/SequenceFactory.scala
@@ -7,5 +7,5 @@ trait SequenceFactory[CC[A] <: Sequence[A]] extends IterableFactory[CC] {
    *  @param x the selector value
    *  @return  sequence wrapped in an option, if this is a Sequence, otherwise none
    */
-  def unapplySequence[A](x: CC[A]): Some[CC[A]] = Some(x)
+  def unapplySeq[A](x: CC[A]): Some[CC[A]] = Some(x)
 }
diff --git a/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala b/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala
new file mode 100644
index 0000000000..d5ba7ea063
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala
@@ -0,0 +1,50 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: SeqProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $
+
+
+package scalax.collection.generic.covartest
+
+/** This class implements a forwarder for sequences. It forwards
+ *  all calls to a different sequence object except for
+ *
+ *    - toString, hashCode, equals, stringPrefix
+ *    - newBuilder, view, toSequence
+ *    - all calls creating a new iterable objetc of the same kind
+ *
+ *  The above methods are forwarded by subclass SequenceProxy
+ *
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+trait SequenceForwarder[+A] extends Sequence[A] with IterableForwarder[A] {
+
+  protected override def underlying: Sequence[A]
+
+  // PartialFunction delegates
+
+  override def apply(i: Int): A = underlying.apply(i)
+  override def isDefinedAt(x: Int): Boolean = underlying.isDefinedAt(x)
+
+  // Sequence delegates
+  // Sequence methods could be printed by  cat SequenceTemplate.scala | sed -n '/trait Seq/,$ p' | egrep '^  (override )?def'
+
+  override def length: Int = underlying.length
+  override def lengthCompare(l: Int) = underlying lengthCompare l
+  override def segmentLength(p: A => Boolean, from: Int): Int = underlying.segmentLength(p, from)
+  override def prefixLength(p: A => Boolean) = underlying.prefixLength(p)
+  override def indexWhere(p: A => Boolean, from: Int): Int = underlying.indexWhere(p, from)
+  override def indexOf[B >: A](elem: B, from: Int): Int = underlying.indexOf(elem, from)
+  override def reversedElements: Iterator[A] = underlying.reversedElements
+  override def startsWith[B](that: Sequence[B], offset: Int): Boolean = underlying.startsWith(that, offset)
+  override def endsWith[B](that: Sequence[B]): Boolean = underlying.endsWith(that)
+  override def indexOf[B >: A](that: Sequence[B]): Int = underlying.indexOf(that)
+  override def contains(elem: Any): Boolean = underlying.contains(elem)
+  override def indices: Range = underlying.indices
+}
diff --git a/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala
index bf1915edf0..ffc4c3d8f7 100755
--- a/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala
+++ b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala
@@ -324,7 +324,7 @@ self /*: CC[A]*/ =>
    *
    *  @return  the sequence itself
    */
-  override def toSequence: Sequence[A] = this.asInstanceOf[Null] // !!!
+  override def toSequence: Sequence[A] = thisCC
 
   def indices: Range = 0 until length
 
diff --git a/src/library/scalax/collection/generic/covartest/SequenceView.scala b/src/library/scalax/collection/generic/covartest/SequenceView.scala
index 48477cf6e7..09d5c0efa1 100755
--- a/src/library/scalax/collection/generic/covartest/SequenceView.scala
+++ b/src/library/scalax/collection/generic/covartest/SequenceView.scala
@@ -69,7 +69,7 @@ self =>
 
   class Patched[+B >: A](from: Int, patch: Sequence[B], replaced: Int) extends Transformed[B] {
     val plen = patch.length
-    override def elements: Iterator[B] = self.elements patch (from, patch.asInstanceOf[Null], replaced) // !!!
+    override def elements: Iterator[B] = self.elements patch (from, patch, replaced)
     override def length: Int = self.length + plen - replaced
     override def apply(idx: Int): B =
       if (idx < from) self.apply(idx)
@@ -101,7 +101,7 @@ self =>
   override def zip[B](that: Iterable[B]): SequenceView[UC, (A, B)] =
     new Zipped(that.toSequence).asCC
   override def zipWithIndex: SequenceView[UC, (A, Int)] =
-    zip((0 until length).asInstanceOf[Null]) // !!!
+    zip((0 until length).asInstanceOf[Null]) // !@!
     /*
   override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): SequenceView[UC, (A1, B1)] = {
     val that1 = that.toSequence
diff --git a/src/library/scalax/collection/generic/covartest/VectorTemplate.scala b/src/library/scalax/collection/generic/covartest/VectorTemplate.scala
index 0771b078d9..6e44b6a6c5 100644
--- a/src/library/scalax/collection/generic/covartest/VectorTemplate.scala
+++ b/src/library/scalax/collection/generic/covartest/VectorTemplate.scala
@@ -208,7 +208,7 @@ self =>
     b.result
   }
 
-  override def reversedElements = new Iterator[A] {
+  override def reversedElements: Iterator[A] = new Iterator[A] {
     var i = length
     def hasNext: Boolean = 0 < i
     def next: A =
diff --git a/src/library/scalax/collection/generic/mutable/VectorTemplate.scala b/src/library/scalax/collection/generic/mutable/VectorTemplate.scala
index aafee3ae3b..747cd01a4c 100644
--- a/src/library/scalax/collection/generic/mutable/VectorTemplate.scala
+++ b/src/library/scalax/collection/generic/mutable/VectorTemplate.scala
@@ -44,7 +44,7 @@ self =>
    */
   override def view(from: Int, until: Int): VectorView[CC, A] = view.slice(from, until)
 
-  def readOnly: Sequence[A] = new collection./*immutable.*/Vector[A] { //!!!
+  def readOnly: Sequence[A] = new collection.immutable.Vector[A] { //!!!
     def length = self.length
     def apply(idx : Int) = self.apply(idx)
     def newBuilder[B]: Builder[CC, B] = self.newBuilder[B]
diff --git a/src/library/scalax/collection/generic/mutable/VectorView.scala b/src/library/scalax/collection/generic/mutable/VectorView.scala
index 05a7bf6f5a..caebcb567f 100644
--- a/src/library/scalax/collection/generic/mutable/VectorView.scala
+++ b/src/library/scalax/collection/generic/mutable/VectorView.scala
@@ -75,7 +75,7 @@ self =>
     new Zipped(toVector(that)).asCC
 
   override def zipWithIndex: VectorView[UC, (A, Int)] =
-    zip((0 until length).asInstanceOf[Null]) // !!!
+    zip((0 until length).asInstanceOf[Null]) // !@!
   override def take(n: Int): VectorView[UC, A] =
     slice(0, n)
   override def drop(n: Int): VectorView[UC, A] =
diff --git a/src/library/scalax/collection/immutable/Iterable.scala b/src/library/scalax/collection/immutable/Iterable.scala
new file mode 100644
index 0000000000..c299518d1b
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Iterable.scala
@@ -0,0 +1,22 @@
+package scalax.collection.immutable
+
+import generic.covariant
+
+/** Collection classes mixing in this class provide a method
+ *  elements which returns an iterator over all the
+ *  elements contained in the collection.
+ *
+ *  @note If a collection has a known size, it should also sub-type SizedIterable.
+ *
+ *  @author  Matthias Zenger
+ *  @autor   Martin Odersky
+ *  @owner   Martin Odersky
+ *  @version 2.8
+ */
+trait Iterable[+A] extends collection.Iterable[A]
+
+object Iterable extends covariant.IterableFactory[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 366ae15d15..d5cecad27f 100644
--- a/src/library/scalax/collection/immutable/List.scala
+++ b/src/library/scalax/collection/immutable/List.scala
@@ -12,7 +12,7 @@
 package scalax.collection.immutable
 
 import mutable.ListBuffer
-import generic.covariant.SequenceTemplate
+import generic.covariant.{SequenceTemplate, SequenceFactory}
 
 /** A class representing an ordered collection of elements of type
  *  a. This class comes with two implementing case
@@ -21,9 +21,11 @@ import generic.covariant.SequenceTemplate
  *  head and tail.
  *
  *  @author  Martin Odersky and others
- *  @version 1.0, 16/07/2003
+ *  @version 2.8
  */
-sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A] with Product {
+sealed abstract class List[+A] extends Stream[A] with SequenceTemplate[List, A] with Product {
+
+  import collection.{Iterable, OrderedIterable, Sequence, Vector}
 
   /** Returns true if the list does not contain any elements.
    *  @return true, iff the list is empty.
@@ -44,7 +46,10 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
    */
   def tail: List[A]
 
-  def newBuilder[B]: Builder[List, B] = new ListBuffer[B]
+  /** Creates a list buffer as builder for this class */
+  override def newBuilder[B]: Builder[List, B] = new ListBuffer[B]
+
+  // New methods in List
 
   /** 

    *    Add an element x at the beginning of this list.
@@ -70,15 +75,10 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     if (isEmpty) prefix
     else (new ListBuffer[B] ++ prefix).prependToList(this)
 
-  /** Appends two list objects.
-   */
-  override def ++[B >: A](that: Iterable[B]): List[B] =
-    this ::: that.toList
-
   /** Reverse the given prefix and append the current list to that.
    *  This function is equivalent to an application of reverse
-   *  on the prefix followed by a call to :::, but more
-   *  efficient (and tail recursive).
+   *  on the prefix followed by a call to :::, but is more
+   *  efficient.
    *
    *  @param prefix the prefix to reverse and then prepend
    *  @return       the concatenation of the reversed prefix and the current list.
@@ -93,36 +93,57 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     these
   }
 
-  /** Returns the number of elements in the list.
-   *
-   *  @return the number of elements in the list.
+  /** Apply a function to all the elements of the list, and return the
+   *  reversed list of results. This is equivalent to a call to map
+   *  followed by a call to reverse, but more efficient.
+   *  !!! should we deprecate this? Why have reverseMap, but not filterMap, say?
+   *  @param f the function to apply to each elements.
+   *  @return  the reversed list of results.
    */
-  def length: Int = {
-    var these = this
-    var len = 0
-    while (!these.isEmpty) {
-      len += 1
-      these = these.tail
+  def reverseMap[B](f: A => B): List[B] = {
+    def loop(l: List[A], res: List[B]): List[B] = l match {
+      case Nil => res
+      case head :: tail => loop(tail, f(head) :: res)
     }
-    len
+    loop(this, Nil)
   }
 
-  /** Returns the elements in the list as an iterator
-   *
-   *  @return an iterator on the list elements.
+  /** Like xs map f, but returns xs unchanged if function
+   *  f maps all elements to themselves (wrt eq)
+   *  @note Unlike `map`, `mapConserve` is not tail-recursive
    */
-  override def elements: Iterator[A] = new Iterator[A] {
-    var these = List.this
-    def hasNext: Boolean = !these.isEmpty
-    def next: A =
-      if (!hasNext)
-        throw new NoSuchElementException("next on empty Iterator")
+  def mapConserve[B >: A] (f: A => B): List[B] = {
+    def loop(ys: List[A]): List[B] =
+      if (ys.isEmpty) this
       else {
-        val result = these.head; these = these.tail; result
+        val head0 = ys.head
+        val head1 = f(head0)
+        if (head1.asInstanceOf[AnyRef] eq head0.asInstanceOf[AnyRef]) {
+          loop(ys.tail)
+        } else {
+          val ys1 = head1 :: ys.tail.mapConserve(f)
+          if (this eq ys) ys1
+          else {
+            val b = new ListBuffer[B]
+            var xc = this
+            while (xc ne ys) {
+              b += xc.head
+              xc = xc.tail
+            }
+            b.prependToList(ys1)
+          }
+        }
       }
-    override def toList: List[A] = these
+    loop(this)
   }
 
+  // Overridden methods from IterableTemplate or overloaded variants of such methods
+
+  /** Appends two list objects.
+   */
+  override def ++[B >: A](that: Iterable[B]): List[B] =
+    this ::: that.toList
+
   /** Overrides the method in Iterable for efficiency.
    *
    *  @return  the list itself
@@ -131,7 +152,7 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
 
   /** Returns the n first elements of this list, or else the whole
    *  list, if it has less than n elements.
-   *
+
    *  @param n the number of elements to take.
    *  @return the n first elements of this list.
    */
@@ -148,18 +169,6 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     else b.toList
   }
 
-  /** Returns the list with elements belonging to the given index range.
-   *
-   *  @param start the start position of the list slice.
-   *  @param end   the end position (exclusive) of the list slice.
-   *  @return the list with elements belonging to the given index range.
-   */
-  override def slice(start: Int, end: Int): List[A] = {
-    val s = start max 0
-    val e = end min this.length
-    drop(s) take (e - s)
-  }
-
   /** Returns the list without its n first elements.
    *  If this list has less than n elements, the empty list is returned.
    *
@@ -176,6 +185,18 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     these
   }
 
+  /** Returns the list with elements belonging to the given index range.
+   *
+   *  @param start the start position of the list slice.
+   *  @param end   the end position (exclusive) of the list slice.
+   *  @return the list with elements belonging to the given index range.
+   */
+  override def slice(start: Int, end: Int): List[A] = {
+    val s = start max 0
+    val e = end min this.length
+    drop(s) take (e - s)
+  }
+
   /** Returns the rightmost n elements from this list.
    *
    *  @param n the number of elements to take
@@ -189,18 +210,7 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     loop(drop(n), this)
   }
 
-  /** Returns the list wihout its rightmost n elements.
-   *
-   *  @param n the number of elements to take
-   *  @return the list without its rightmost n elements
-   */
-  override def dropRight(n: Int): List[A] = {
-    def loop(lead: List[A], lag: List[A]): List[A] = lead match {
-      case Nil => Nil
-      case _ :: tail => lag.head :: loop(tail, lag.tail)
-    }
-    loop(drop(n), this)
-  }
+  // dropRight is inherited from Stream
 
   /** Split the list at a given point and return the two parts thus
    *  created.
@@ -266,15 +276,6 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     (b.toList, these)
   }
 
-  /** Returns the n-th element of this list. The first element
-   *  (head of the list) is at position 0.
-   *
-   *  @param n index of the element to return
-   *  @return  the element at position n in this list.
-   *  @throws Predef.NoSuchElementException if the list is too short.
-   */
-  def apply(n: Int): A = drop(n).head
-
   /** Returns the list resulting from applying the given function f to each
    *  element of this list.
    *
@@ -291,34 +292,6 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     b.toList
   }
 
-  /** Apply a function to all the elements of the list, and return the
-   *  reversed list of results. This is equivalent to a call to map
-   *  followed by a call to reverse, but more efficient.
-   *
-   *  @param f the function to apply to each elements.
-   *  @return  the reversed list of results.
-   */
-  def reverseMap[B](f: A => B): List[B] = {
-    def loop(l: List[A], res: List[B]): List[B] = l match {
-      case Nil => res
-      case head :: tail => loop(tail, f(head) :: res)
-    }
-    loop(this, Nil)
-  }
-
-  /** Apply the given function f to each element of this list
-   *  (while respecting the order of the elements).
-   *
-   *  @param f the treatment to apply to each element.
-   */
-  final override def foreach(f: A => Unit) {
-    var these = this
-    while (!these.isEmpty) {
-      f(these.head)
-      these = these.tail
-    }
-  }
-
   /** Returns all the elements of this list that satisfy the
    *  predicate p. The order of the elements is preserved.
    *  It is guarenteed that the receiver list itself is returned iff all its
@@ -332,219 +305,14 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
   final override def filter(p: A => Boolean): List[A] = {
     // return same list if all elements satisfy p
     var these = this
-    while (!these.isEmpty && p(these.head)) {
-      these = these.tail
-    }
-    if (these.isEmpty) this
-    else {
-      val b = new ListBuffer[A]
-      var these1 = this
-      while (these1 ne these) {
-        b += these1.head
-        these1 = these1.tail
-      }
-
-      these = these.tail // prevent the second evaluation of the predicate
-                         // on the element on which it first failed
-      while (!these.isEmpty) {
-        if (p(these.head)) b += these.head
-        these = these.tail
-      }
-      b.toList
-    }
-  }
-
-  /** 

-   *    Sort the list according to the comparison function
-   *    <(e1: a, e2: a) => Boolean,
-   *    which should be true iff e1 is smaller than
-   *    e2.
-   *  

-   *
-   *  @param lt the comparison function
-   *  @return   a list sorted according to the comparison function
-   *            <(e1: a, e2: a) => Boolean.
-   *  @ex 
-   *    List("Steve", "Tom", "John", "Bob")
-   *      .sort((e1, e2) => (e1 compareTo e2) < 0) =
-   *    List("Bob", "John", "Steve", "Tom")

-   */
-  def sort(lt : (A,A) => Boolean): List[A] = {
-    /** Merge two already-sorted lists */
-    def merge(l1: List[A], l2: List[A]): List[A] = {
-      val res = new ListBuffer[A]
-      var left1 = l1
-      var left2 = l2
-
-      while (!left1.isEmpty && !left2.isEmpty) {
-	if(lt(left1.head, left2.head)) {
-	  res += left1.head
-	  left1 = left1.tail
-	} else {
-	  res += left2.head
-	  left2 = left2.tail
-	}
-      }
-
-      res ++= left1
-      res ++= left2
-
-      res.toList
-    }
-
-    /** Split a list into two lists of about the same size */
-    def split(lst: List[A]) = {
-      val res1 = new ListBuffer[A]
-      val res2 = new ListBuffer[A]
-      var left = lst
-
-      while (!left.isEmpty) {
-	res1 += left.head
-	left = left.tail
-	if (!left.isEmpty) {
-	  res2 += left.head
-	  left = left.tail
-	}
-      }
-
-      (res1.toList, res2.toList)
-    }
-
-
-    /** Merge-sort the specified list */
-    def ms(lst: List[A]): List[A] =
-      lst match {
-	case Nil => lst
-	case x :: Nil => lst
-	case x :: y :: Nil =>
-	  if (lt(x,y))
-	    lst
-	  else
-	    y :: x :: Nil
-
-	case lst =>
-          val (l1, l2) = split(lst)
-          val l1s = ms(l1)
-          val l2s = ms(l2)
-          merge(l1s, l2s)
-      }
-
-    ms(this)
-  }
-
-  /** Tests if the predicate p is satisfied by all elements
-   *  in this list.
-   *
-   *  @param p the test predicate.
-   *  @return  true iff all elements of this list satisfy the
-   *           predicate p.
-   */
-  override def forall(p: A => Boolean): Boolean = {
-    var these = this
-    while (!these.isEmpty) {
-      if (!p(these.head)) return false
-      these = these.tail
-    }
-    true
-  }
-
-  /** Tests the existence in this list of an element that satisfies the
-   *  predicate p.
-   *
-   *  @param p the test predicate.
-   *  @return  true iff there exists an element in this list that
-   *           satisfies the predicate p.
-   */
-  override def exists(p: A => Boolean): Boolean = {
-    var these = this
-    while (!these.isEmpty) {
-      if (p(these.head)) return true
-      these = these.tail
-    }
-    false
-  }
-
-  /** Find and return the first element of the list satisfying a
-   *  predicate, if any.
-   *
-   *  @param p the predicate
-   *  @return the first element in the list satisfying p,
-   *  or None if none exists.
-   */
-  override def find(p: A => Boolean): Option[A] = {
-    var these = this
-    while (!these.isEmpty) {
-      if (p(these.head)) return Some(these.head)
-      these = these.tail
-    }
-    None
-  }
-
-  /** Combines the elements of this list together using the binary
-   *  function f, from left to right, and starting with
-   *  the value z.
-   *
-   *  @return f(... (f(f(z, a0), a1) ...),
-   *          an) if the list is
-   *          [a0, a1, ..., an].
-   */
-  override def foldLeft[B](z: B)(f: (B, A) => B): B = {
-    var acc = z
-    var these = this
+    var allTrue = true
+    val b = new ListBuffer[A]
     while (!these.isEmpty) {
-      acc = f(acc, these.head)
+      if (p(these.head)) b += these.head
+      else allTrue = false
       these = these.tail
     }
-    acc
-  }
-
-  /** Combines the elements of this list together using the binary
-   *  function f, from right to left, and starting with
-   *  the value z.
-   *
-   *  @return f(a0, f(a1, f(..., f(an, z)...)))
-   *          if the list is [a0, a1, ..., an].
-   */
-  override def foldRight[B](z: B)(f: (A, B) => B): B = this match {
-    case Nil => z
-    case x :: xs => f(x, xs.foldRight(z)(f))
-  }
-
-  /** Combines the elements of this list together using the binary
-   *  operator op, from left to right
-   *  @param op  The operator to apply
-   *  @return op(... op(a0,a1), ..., an)
-      if the list has elements
-   *          a0, a1, ..., an.
-   *  @throws Predef.UnsupportedOperationException if the list is empty.
-   */
-  override def reduceLeft[B >: A](f: (B, A) => B): B = this match {
-    case Nil => throw new UnsupportedOperationException("Nil.reduceLeft")
-    case x :: Nil => x
-    case x0 :: x1 :: xs =>
-      var acc : B = f(x0, x1)
-      var these : List[A] = xs
-      while (!these.isEmpty) {
-        acc = f(acc, these.head)
-        these = these.tail
-      }
-      acc
-  }
-
-  /** Combines the elements of this list together using the binary
-   *  operator op, from right to left
-   *  @param op  The operator to apply
-   *
-   *  @return a0 op (... op (an-1 op an)...)
-   *          if the list has elements a0, a1, ...,
-   *          an.
-   *
-   *  @throws Predef.UnsupportedOperationException if the list is empty.
-   */
-  override def reduceRight[B >: A](f: (A, B) => B): B = this match {
-    case Nil => throw new UnsupportedOperationException("Nil.reduceRight")
-    case x :: Nil => x
-    case x :: xs => f(x, xs reduceRight f)
+    if (allTrue) this else b.toList
   }
 
   /** Applies the given function f to each element of
@@ -558,32 +326,19 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     val b = new ListBuffer[B]
     var these = this
     while (!these.isEmpty) {
-      var those = f(these.head).elements
-      while (those.hasNext) {
-        b += those.next
-      }
+      b ++= f(these.head)
       these = these.tail
     }
     b.toList
   }
 
-  /** A list consisting of all elements of this list in reverse order.
-   */
-  override def reverse: List[A] = {
-    var result: List[A] = Nil
-    var these = this
-    while (!these.isEmpty) {
-      result = these.head :: result
-      these = these.tail
-    }
-    result
-  }
-
   /** Returns a list formed from this list and the specified list
    *  that by associating each element of the former with
    *  the element at the same position in the latter.
    *  If one of the two lists is longer than the other, its remaining elements are ignored.
    *
+   *  !!! todo: perform speed with inherited version from Iterable, and drop
+   *      if not significantly better
    *  @return     List((a0,b0), ...,
    *              (amin(m,n),bmin(m,n))) when
    *              List(a0, ..., am)
@@ -640,33 +395,9 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     b.toList
   }
 
-  /** Computes the union of this list and the given list
-   *  that.
-   *
-   *  @param that the list of elements to add to the list.
-   *  @return     a list without doubles containing the elements of this
-   *              list and those of the given list that.
-   */
-  def union[B >: A](that: List[B]): List[B] = {
-    val b = new ListBuffer[B]
-    var these = this
-    while (!these.isEmpty) {
-      if (!that.contains(these.head)) b += these.head
-      these = these.tail
-    }
-    b.prependToList(that)
-  }
+  override def stringPrefix = "List"
 
-  /** Computes the difference between this list and the given list
-   *  that.
-   *
-   *  @param that the list of elements to remove from this list.
-   *  @return     this list without the elements of the given list
-   *              that.
-   *  @deprecated use -- instead
-   */
-  @deprecated
-  def diff[B >: A](that: List[B]): List[B] = this -- that
+  override def toStream : Stream[A] = this
 
   /** Computes the difference between this list and the given list
    *  that.
@@ -674,8 +405,9 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
    *  @param that the list of elements to remove from this list.
    *  @return     this list without the elements of the given list
    *              that.
+   *  @deprecated use diff instead
    */
-  def -- [B >: A](that: List[B]): List[B] = {
+  @deprecated def -- [B >: A](that: List[B]): List[B] = {
     val b = new ListBuffer[B]
     var these = this
     while (!these.isEmpty) {
@@ -691,8 +423,9 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
    *  @param x    the object to remove from this list.
    *  @return     this list without the elements of the given object
    *              x.
+   *  @deprecated use diff instead
    */
-  def - [B >: A](x: B): List[B] = {
+  @deprecated def - [B >: A](x: B): List[B] = {
     val b = new ListBuffer[B]
     var these = this
     while (!these.isEmpty) {
@@ -702,40 +435,85 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A
     b.toList
   }
 
-  /** Concatenate the elements of this list. The elements of this list
-   *  should be a Iterables.
-   *
-   *  Note: The compiler might not be able to infer the type parameter.
+  /** 

+   *    Sort the list according to the comparison function
+   *    <(e1: a, e2: a) => Boolean,
+   *    which should be true iff e1 is smaller than
+   *    e2.
+   *  !!! todo: move sorting to IterableTemplate
+   *  

    *
-   *  @param f    An implicit conversion to an Iterable instance.
-   *  @return     The concatenation of all elements of iterables in this list.
+   *  @param lt the comparison function
+   *  @return   a list sorted according to the comparison function
+   *            <(e1: a, e2: a) => Boolean.
+   *  @ex 
+   *    List("Steve", "Tom", "John", "Bob")
+   *      .sort((e1, e2) => (e1 compareTo e2) < 0) =
+   *    List("Bob", "John", "Steve", "Tom")

+   *  @deprecated  use sortWith instead
    */
-  def flatten[B](implicit f : A => Iterable[B]) : List[B] = {
-    val buf = new ListBuffer[B]
-    foreach(f(_).foreach(buf += _))
-    buf.toList
-  }
+  @deprecated def sort(lt : (A,A) => Boolean): List[A] = {
+    /** Merge two already-sorted lists */
+    def merge(l1: List[A], l2: List[A]): List[A] = {
+      val res = new ListBuffer[A]
+      var left1 = l1
+      var left2 = l2
 
-  override def stringPrefix = "List"
+      while (!left1.isEmpty && !left2.isEmpty) {
+	if(lt(left1.head, left2.head)) {
+	  res += left1.head
+	  left1 = left1.tail
+	} else {
+	  res += left2.head
+	  left2 = left2.tail
+	}
+      }
 
-  override def toStream : Stream[A] = null // !!!
-  /*new Stream.Definite[A] {
-    override def force : List[A] = List.this
-    override def isEmpty = List.this.isEmpty
-    override def head = List.this.head
-    override def tail = List.this.tail.toStream
-    protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder = if (!isEmpty) {
-      var prefix0 = prefix
-      var buf1 = buf.append(prefix0).append(head)
-      prefix0 = ", "
-      var tail0 = tail
-      while (!tail0.isEmpty) {
-        buf1 = buf.append(prefix0).append(tail0.head)
-        tail0 = tail0.tail
+      res ++= left1
+      res ++= left2
+
+      res.toList
+    }
+
+    /** Split a list into two lists of about the same size */
+    def split(lst: List[A]) = {
+      val res1 = new ListBuffer[A]
+      val res2 = new ListBuffer[A]
+      var left = lst
+
+      while (!left.isEmpty) {
+	res1 += left.head
+	left = left.tail
+	if (!left.isEmpty) {
+	  res2 += left.head
+	  left = left.tail
+	}
+      }
+
+      (res1.toList, res2.toList)
+    }
+
+
+    /** Merge-sort the specified list */
+    def ms(lst: List[A]): List[A] =
+      lst match {
+	case Nil => lst
+	case x :: Nil => lst
+	case x :: y :: Nil =>
+	  if (lt(x,y))
+	    lst
+	  else
+	    y :: x :: Nil
+
+	case lst =>
+          val (l1, l2) = split(lst)
+          val l1s = ms(l1)
+          val l2s = ms(l2)
+          merge(l1s, l2s)
       }
-      buf1
-    } else buf
-  }*/
+
+    ms(this)
+  }
 
 }
 
@@ -788,57 +566,19 @@ final case class ::[B](private var hd: B, private[scalax] var tl: List[B]) exten
   }
 }
 
-/** Only used for list serialization */
-@SerialVersionUID(0L - 8476791151975527571L)
-private[scalax] case object ListSerializeEnd
 /** This object provides methods for creating specialized lists, and for
  *  transforming special kinds of lists (e.g. lists of lists).
  *
  *  @author  Martin Odersky and others
  *  @version 1.0, 15/07/2003
  */
-object List {
-
-  /** Create a list with given elements.
-   *
-   *  @param xs the elements to put in the list
-   *  @return the list containing elements xs.
-   */
-  def apply[A](xs: A*): List[A] = (xs.asInstanceOf[Iterable[A]]).toList // !!!
+object List extends SequenceFactory[List] {
 
-  /** for unapply matching
-   */
-  def unapplySeq[A](x: List[A]): Some[List[A]] = Some(x)
+  override val empty: List[Nothing] = Nil
 
-  /** Create a sorted list of all integers in a range.
-   *
-   *  @param from the start value of the list
-   *  @param end the end value of the list
-   *  @return the sorted list of all integers in range [from;end).
-   */
-  def range(start: Int, end: Int): List[Int] =
-    range(start, end, 1)
+  override def apply[A](xs: A*) = xs.asInstanceOf[Iterable[A]].toList // !@!
 
-  /** Create a list with element values
-   * vn+1 = vn + step
-   * where v0 = start
-   * and elements are in the range between start (inclusive)
-   * and end (exclusive)
-   *
-   *  @param start the start value of the list
-   *  @param end  the end value of the list
-   *  @param step the increment value of the list
-   *  @return     the sorted list of all integers in range [start;end).
-   */
-  def range(start: Int, end: Int, step: Int): List[Int] = {
-    val b = new ListBuffer[Int]
-    var i = start
-    while ((step <= 0 || i < end) && (step >= 0 || i > end)) {
-      b += i
-      i += step
-    }
-    b.toList
-  }
+  override def newBuilder[B]: Builder[List, B] = new ListBuffer[B]
 
   /** Create a sorted list with element values
    * vn+1 = step(vn)
@@ -846,12 +586,13 @@ object List {
    * and elements are in the range between start (inclusive)
    * and end (exclusive)
    *
+   *  @deprecated  use @see iterate instead.
    *  @param start the start value of the list
    *  @param end  the end value of the list
    *  @param step the increment function of the list, must be monotonically increasing or decreasing
    *  @return     the sorted list of all integers in range [start;end).
    */
-  def range(start: Int, end: Int, step: Int => Int): List[Int] = {
+  @deprecated def range(start: Int, end: Int, step: Int => Int): List[Int] = {
     val up = step(start) > start
     val down = step(start) < start
     val b = new ListBuffer[Int]
@@ -864,12 +605,13 @@ object List {
   }
 
   /** Create a list containing several copies of an element.
+   *  @deprecated use @see fill instead
    *
    *  @param n    the length of the resulting list
    *  @param elem the element composing the resulting list
    *  @return     a list composed of n elements all equal to elem
    */
-  def make[A](n: Int, elem: A): List[A] = {
+  @deprecated def make[A](n: Int, elem: A): List[A] = {
     val b = new ListBuffer[A]
     var i = 0
     while (i < n) {
@@ -879,48 +621,13 @@ object List {
     b.toList
   }
 
-  /** Create a list by applying a function to successive integers.
-   *
-   *  @param n     the length of the resulting list
-   *  @param maker the procedure which, given an integer n,
-   *               returns the nth element of the resulting list, where
-   *               n is in interval [0;n).
-   *  @return      the list obtained by applying the maker function to
-   *               successive integers from 0 to n (exclusive).
-   */
-  def tabulate[A](n: Int, maker: Int => A): List[A] = {
-    val b = new ListBuffer[A]
-    var i = 0
-    while (i < n) {
-      b += maker(i)
-      i += 1
-    }
-    b.toList
-  }
-
   /** Concatenate all the elements of a given list of lists.
    *
+   *  @deprecated use `xss.flatten` instead
    *  @param xss the list of lists that are to be concatenated
    *  @return    the concatenation of all the lists
    */
-  def flatten[A](xss: List[List[A]]): List[A] = {
-    val b = new ListBuffer[A]
-    for (xs <- xss) {
-      var xc = xs
-      while (!xc.isEmpty) {
-        b += xc.head
-        xc = xc.tail
-      }
-    }
-    b.toList
-  }
-
-  /** Concatenate all the argument lists into a single list.
-   *
-   *  @param xss the lists that are to be concatenated
-   *  @return the concatenation of all the lists
-   */
-  def concat[A](xss: List[A]*): List[A] = {
+  @deprecated def flatten[A](xss: List[List[A]]): List[A] = {
     val b = new ListBuffer[A]
     for (xs <- xss) {
       var xc = xs
@@ -936,8 +643,9 @@ object List {
    *
    *  @param xs the list of pairs to unzip
    *  @return a pair of lists.
+   *  @deprecated  use `xs.unzp` instead
    */
-  def unzip[A,B](xs: List[(A,B)]): (List[A], List[B]) = {
+  @deprecated def unzip[A,B](xs: List[(A,B)]): (List[A], List[B]) = {
     val b1 = new ListBuffer[A]
     val b2 = new ListBuffer[B]
     var xc = xs
@@ -951,18 +659,20 @@ object List {
 
   /** Transforms an iterable of pairs into a pair of lists.
    *
+   *  @deprecated use `xs.unzip` instead
    *  @param xs the iterable of pairs to unzip
    *  @return a pair of lists.
    */
-  def unzip[A,B](xs: Iterable[(A,B)]): (List[A], List[B]) =
+  @deprecated def unzip[A,B](xs: Iterable[(A,B)]): (List[A], List[B]) =
       xs.foldRight[(List[A], List[B])]((Nil, Nil)) {
         case ((x, y), (xs, ys)) => (x :: xs, y :: ys)
       }
 
   /**
    * Returns the Left values in the given Iterable of Eithers.
+   * @deprecated use `Either.lefts` instead
    */
-  def lefts[A, B](es: Iterable[Either[A, B]]) =
+  @deprecated def lefts[A, B](es: Iterable[Either[A, B]]) =
     es.foldRight[List[A]](Nil)((e, as) => e match {
       case Left(a) => a :: as
       case Right(_) => as
@@ -970,8 +680,9 @@ object List {
 
   /**
    * Returns the Right values in the givenIterable of  Eithers.
+   * @deprecated use `Either.rights` instead
    */
-  def rights[A, B](es: Iterable[Either[A, B]]) =
+  @deprecated def rights[A, B](es: Iterable[Either[A, B]]) =
     es.foldRight[List[B]](Nil)((e, bs) => e match {
       case Left(_) => bs
       case Right(b) => b :: bs
@@ -981,8 +692,9 @@ object List {
    *
    *  @param xs the iterable of Eithers to separate
    *  @return a pair of lists.
+   *  @deprecated  use `Either.separate` instead
    */
-  def separate[A,B](es: Iterable[Either[A,B]]): (List[A], List[B]) =
+  @deprecated def separate[A,B](es: Iterable[Either[A,B]]): (List[A], List[B]) =
       es.foldRight[(List[A], List[B])]((Nil, Nil)) {
       case (Left(a), (lefts, rights)) => (a :: lefts, rights)
       case (Right(b), (lefts, rights)) => (lefts, b :: rights)
@@ -993,14 +705,16 @@ object List {
    *  @param it the iterator to convert
    *  @return   a list that contains the elements returned by successive
    *            calls to it.next
+   *  @deprecated use it.toList instead
    */
-  def fromIterator[A](it: Iterator[A]): List[A] = it.toList
+  @deprecated def fromIterator[A](it: Iterator[A]): List[A] = it.toList
 
   /** Converts an array into a list.
    *
    *  @param arr the array to convert
    *  @return    a list that contains the same elements than arr
    *             in the same order
+   *  @deprecated use `array.toList` instead
    */
   def fromArray[A](arr: Array[A]): List[A] = fromArray(arr, 0, arr.length)
 
@@ -1011,8 +725,9 @@ object List {
    *  @param len   the lenght of the range to convert
    *  @return      a list that contains the same elements than arr
    *               in the same order
+   *  @deprecated use `array.view(start, end).toList` instead
    */
-  def fromArray[A](arr: Array[A], start: Int, len: Int): List[A] = {
+  @deprecated def fromArray[A](arr: Array[A], start: Int, len: Int): List[A] = {
     var res: List[A] = Nil
     var i = start + len
     while (i > start) {
@@ -1028,8 +743,9 @@ object List {
    *  @param str       the string to parse
    *  @param separator the separator character
    *  @return          the list of substrings
+   *  @deprecated      use `str.split(separator).toList` instead
    */
-  def fromString(str: String, separator: Char): List[String] = {
+  @deprecated def fromString(str: String, separator: Char): List[String] = {
     var words: List[String] = Nil
     var pos = str.length()
     while (pos > 0) {
@@ -1048,14 +764,15 @@ object List {
    *  @deprecated use str.toList instead
    */
   @deprecated def fromString(str: String): List[Char] =
-    str.toList.asInstanceOf[List[Char]] // !!!
+    str.toList.asInstanceOf[List[Char]] // !@!
 
   /** Returns the given list of characters as a string.
    *
    *  @param xs the list to convert.
    *  @return   the list in form of a string.
+   *  @deprecated  use xs.mkString instead
    */
-  def toString(xs: List[Char]): String = {
+  @deprecated def toString(xs: List[Char]): String = {
     val sb = new StringBuilder()
     var xc = xs
     while (!xc.isEmpty) {
@@ -1067,12 +784,9 @@ object List {
 
   /** Like xs map f, but returns xs unchanged if function
    *  f maps all elements to themselves.
-   *
-   *  @param xs ...
-   *  @param f  ...
-   *  @return   ...
+   *  @deprecated  use xs.mapConserve(f)
    */
-  def mapConserve[A <: AnyRef](xs: List[A])(f: A => A): List[A] = {
+  @deprecated def mapConserve[A <: AnyRef](xs: List[A])(f: A => A): List[A] = {
     def loop(ys: List[A]): List[A] =
       if (ys.isEmpty) xs
       else {
@@ -1099,13 +813,13 @@ object List {
 
   /** Returns the list resulting from applying the given function f
    *  to corresponding elements of the argument lists.
-   *
+   *  @deprecated   use (xs, ys).map(f) instead
    *  @param f function to apply to each pair of elements.
    *  @return [f(a0,b0), ..., f(an,bn)] if the lists are
    *          [a0, ..., ak], [b0, ..., bl] and
    *          n = min(k,l)
    */
-  def map2[A,B,C](xs: List[A], ys: List[B])(f: (A, B) => C): List[C] = {
+  @deprecated def map2[A,B,C](xs: List[A], ys: List[B])(f: (A, B) => C): List[C] = {
     val b = new ListBuffer[C]
     var xc = xs
     var yc = ys
@@ -1121,6 +835,7 @@ object List {
    *  f to corresponding elements of the argument lists.
    *
    *  @param f function to apply to each pair of elements.
+   *  @deprecated  use (xs, ys, zs).map(f) instead
    *  @return  [f(a0,b0,c0),
    *           ..., f(an,bn,cn)]
    *           if the lists are [a0, ..., ak],
@@ -1128,7 +843,7 @@ object List {
    *           [c0, ..., cm] and
    *           n = min(k,l,m)
    */
-  def map3[A,B,C,D](xs: List[A], ys: List[B], zs: List[C])(f: (A, B, C) => D): List[D] = {
+  @deprecated def map3[A,B,C,D](xs: List[A], ys: List[B], zs: List[C])(f: (A, B, C) => D): List[D] = {
     val b = new ListBuffer[D]
     var xc = xs
     var yc = ys
@@ -1151,8 +866,9 @@ object List {
    *           if the lists are [a0, ..., ak];
    *           [b0, ..., bl]
    *           and n = min(k,l)
+   *  @deprecated  use (xs, ys).forall(f) instead
    */
-  def forall2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = {
+  @deprecated def forall2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = {
     var xc = xs
     var yc = ys
     while (!xc.isEmpty && !yc.isEmpty) {
@@ -1172,8 +888,9 @@ object List {
    *           [a0, ..., ak],
    *           [b0, ..., bl] and
    *           n = min(k,l)
+   *  @deprecated  use (xs, ys).forall(f) instead
    */
-  def exists2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = {
+  @deprecated def exists2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = {
     var xc = xs
     var yc = ys
     while (!xc.isEmpty && !yc.isEmpty) {
@@ -1189,8 +906,9 @@ object List {
    *
    *  @param xss the list of lists
    *  @return    the transposed list of lists
+   *  @deprecated use xss.transpose  instead
    */
-  def transpose[A](xss: List[List[A]]): List[List[A]] = {
+  @deprecated def transpose[A](xss: List[List[A]]): List[List[A]] = {
     val buf = new ListBuffer[List[A]]
     var yss = xss
     while (!yss.head.isEmpty) {
@@ -1220,3 +938,7 @@ object List {
    */
 }
 
+/** Only used for list serialization */
+@SerialVersionUID(0L - 8476791151975527571L)
+private[scalax] case object ListSerializeEnd
+
diff --git a/src/library/scalax/collection/immutable/OrderedIterable.scala b/src/library/scalax/collection/immutable/OrderedIterable.scala
new file mode 100644
index 0000000000..402244953d
--- /dev/null
+++ b/src/library/scalax/collection/immutable/OrderedIterable.scala
@@ -0,0 +1,22 @@
+package scalax.collection.immutable
+
+import generic.covariant
+
+/** Collection classes mixing in this class provide a method
+ *  elements which returns an iterator over all the
+ *  elements contained in the collection.
+ *
+ *  @note If a collection has a known size, it should also sub-type SizedIterable.
+ *
+ *  @author  Matthias Zenger
+ *  @autor   Martin Odersky
+ *  @owner   Martin Odersky
+ *  @version 2.8
+ */
+trait OrderedIterable[+A] extends collection.OrderedIterable[A] with Iterable[A]
+
+object OrderedIterable extends covariant.IterableFactory[OrderedIterable] {
+  val empty: OrderedIterable[Nothing] = Nil
+}
+
+
diff --git a/src/library/scalax/collection/immutable/Sequence.scala b/src/library/scalax/collection/immutable/Sequence.scala
new file mode 100644
index 0000000000..fdb9fadf04
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Sequence.scala
@@ -0,0 +1,22 @@
+package scalax.collection.immutable
+
+import generic.covariant
+
+/** Collection classes mixing in this class provide a method
+ *  elements which returns an iterator over all the
+ *  elements contained in the collection.
+ *
+ *  @note If a collection has a known size, it should also sub-type SizedIterable.
+ *
+ *  @author  Matthias Zenger
+ *  @autor   Martin Odersky
+ *  @owner   Martin Odersky
+ *  @version 2.8
+ */
+trait Sequence[+A] extends collection.Sequence[A] with OrderedIterable[A]
+
+object Sequence extends covariant.SequenceFactory[Sequence] {
+  val empty: Sequence[Nothing] = Nil
+}
+
+
diff --git a/src/library/scalax/collection/immutable/Stream.scala b/src/library/scalax/collection/immutable/Stream.scala
new file mode 100755
index 0000000000..6b4a8a60f6
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Stream.scala
@@ -0,0 +1,790 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Stream.scala 16287 2008-10-18 13:41:36Z nielsen $
+
+
+package scalax.collection.immutable
+
+import mutable.ListBuffer
+import generic.covariant.{SequenceTemplate, SequenceFactory}
+
+/**
+ * The object Stream provides helper functions
+ * to manipulate streams.
+ *
+ * @author Martin Odersky, Matthias Zenger
+ * @version 1.1 08/08/03
+ */
+object Stream extends SequenceFactory[Stream] {
+
+  import collection.{Iterable, OrderedIterable, Sequence, Vector}
+
+  override val empty: Stream[Nothing] = Nil
+  override def apply[A](xs: A*) = xs.asInstanceOf[Iterable[A]].toList // !@!
+  override def newBuilder[B]: Builder[Stream, B] = new ListBuffer[B]
+
+  class ConsWrapper[A](tl: => Stream[A]) {
+    def #::(hd: A): Stream[A] = new Cons(hd, tl)
+    def #:::(prefix: Stream[A]): Stream[A] = prefix append tl
+  }
+
+  implicit def consWrapper[A](stream: => Stream[A]): ConsWrapper[A] =
+    new ConsWrapper[A](stream)
+
+  object #:: {
+    def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] =
+      if (xs.isEmpty) None
+      else Some(xs.head, xs.tail)
+  }
+
+  /** @deprecated   use #:: instead */
+  @deprecated lazy val lazy_:: = #::
+
+  /** An alternative way of building and matching Streams using Stream.cons(hd, tl).
+   */
+  object cons {
+
+    /** A stream consisting of a given first element and remaining elements
+     *  @param hd   The first element of the result stream
+     *  @param tl   The remaining elements of the result stream
+     */
+    def apply[A](hd: A, tl: => Stream[A]) = new Cons(hd, tl)
+
+    /** Maps a stream to its head and tail */
+    def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = #::.unapply(xs)
+  }
+
+  final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] {
+    override def isEmpty = false
+    override def head = hd
+    private[this] var tlVal: Stream[A] = _
+    private def tlDefined = tlVal ne null
+    override def tail: Stream[A] = {
+      if (!tlDefined) { tlVal = tl }
+      tlVal
+    }
+    override def hasDefiniteSize = tlDefined && tlVal.hasDefiniteSize
+
+    // Overridden methods from IterableTemplate or overloaded variants of such methods
+
+    /** Create a new stream which contains all elements of this stream
+     *  followed by all elements of Iterable `that'
+     */
+    override def ++[B >: A](that: Iterable[B]): Stream[B] = this append that
+
+    /** Create a new stream which contains all elements of this stream
+     *  followed by all elements of Iterator `that'
+     */
+    override def ++[B >: A](that: Iterator[B]): Stream[B] = this append that.toStream
+
+    /** Returns the stream resulting from applying the given function
+     *  f to each element of this stream.
+     *
+     *  @param f function to apply to each element.
+     *  @return  f(a0), ..., f(an) if this
+     *           sequence is a0, ..., an.
+     */
+    override def map[B](f: A => B): Stream[B] =
+      new Cons(f(head), tail map f)
+
+    /** Applies the given function f to each element of
+     *  this stream, then concatenates the results.
+     *
+     *  @param f the function to apply on each element.
+     *  @return  f(a0) ::: ... ::: f(an) if
+     *           this stream is [a0, ..., an].
+     */
+    override def flatMap[B](f: A => Iterable[B]): Stream[B] = {
+      // drops A's for which f yields an empty Iterable[B]
+      def loop(s: Stream[A]): Stream[B] =
+        if (s.isEmpty) Nil
+        else {
+          val i = f(s.head)
+          if (i.isEmpty) loop(s.tail)
+          else i.toStream append loop(s.tail)
+        }
+      loop(this)
+    }
+
+    /** Returns all the elements of this stream that satisfy the
+     *  predicate p. The order of the elements is preserved.
+     *
+     *  @param p the predicate used to filter the stream.
+     *  @return the elements of this stream satisfying p.
+     */
+    override def filter(p: A => Boolean): Stream[A] = {
+      // drops A's for which p yields false
+      def loop(s: Stream[A]): Stream[A] =
+        if (s.isEmpty) Nil
+        else {
+          val b = p(s.head)
+          if (!b) loop(s.tail)
+          else new Cons(s.head, tail filter p)
+        }
+      loop(this)
+    }
+
+    /** Returns all the elements of this stream that satisfy the
+     *  predicate p. The order of the elements is preserved.
+     *
+     *  @param p the predicate used to filter the stream.
+     *  @return the elements of this stream satisfying p.
+     */
+    override def partition(p: A => Boolean): (Stream[A], Stream[A]) = (filter(p(_)), remove(p(_)))
+
+    /** Returns a stream formed from this stream and the specified stream
+     *  that by associating each element of the former with
+     *  the element at the same position in the latter.
+     *  If one of the two streams is longer than the other, its remaining elements are ignored.
+     *
+     *  @return     Stream({a0,b0}, ...,
+     *              {amin(m,n),bmin(m,n))} when
+     *              Stream(a0, ..., am)
+     *              zip Stream(b0, ..., bn) is invoked.
+     */
+    def zip[B](that: Stream[B]): Stream[(A, B)] =
+      if (that.isEmpty) empty
+      else new Cons((this.head, that.head), this.tail zip that.tail)
+
+    /** Returns a list formed from this list and the specified list
+     *  that by associating each element of the former with
+     *  the element at the same position in the latter.
+     *
+     *  @param that     list that may have a different length
+     *                  as the self list.
+     *  @param thisElem element thisElem is used to fill up the
+     *                  resulting list if the self list is shorter than
+     *                  that
+     *  @param thatElem element thatElem is used to fill up the
+     *                  resulting list if that is shorter than
+     *                  the self list
+     *  @return         List((a0,b0), ...,
+     *                  (an,bn), (elem,bn+1),
+     *                  ..., {elem,bm})
+     *                  when [a0, ..., an] zip
+     *                  [b0, ..., bm] is
+     *                  invoked where m > n.
+     */
+    def zipAll[B, A1 >: A, B1 >: B](that: Stream[B], thisElem: A1, thatElem: B1): Stream[(A1, B1)] = {
+      if (that.isEmpty) new Cons((this.head, thatElem), this.tail.zipAll(that, thisElem, thatElem))
+      else new Cons((this.head, that.head), this.tail.zipAll(that.tail, thisElem, thatElem))
+    }
+
+    /** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to
+     *  `s zip s.indices`
+     */
+    override def zipWithIndex = this zip (Iterator.from(0).toStream)
+
+    /** Write all defined elements of this iterable into given string builder.
+     *  The written text begins with the string start and is finished by the string
+     *  end. Inside, the string representations of defined elements (w.r.t.
+     *  the method toString()) are separated by the string
+     *  sep. The method will not force evaluation of undefined elements. A
+     *  tail of such elements will be represented by a "?" instead.
+     */
+    override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
+      b append start append hd
+      if (tlDefined) tlVal.addString(b, sep, sep, end)
+      else b append ", ?" append end
+    }
+
+    /** Returns the n first elements of this stream, or else the whole
+     *  stream, if it has less than n elements.
+     *
+     *  @param n the number of elements to take.
+     *  @return the n first elements of this stream.
+     */
+    override def take(n: Int): Stream[A] =
+      if (n <= 0) Nil else new Cons(head, tail take (n-1))
+
+    /** Returns the stream without its n first elements.
+     *  If the stream has less than n elements, the empty stream is returned.
+     *
+     *  @param n the number of elements to drop.
+     *  @return the stream without its n first elements.
+     */
+    override def drop(n: Int): Stream[A] = {
+      var these: Stream[A] = this
+      var i = n
+      while (!these.isEmpty && i > 0) {
+        these = these.tail
+        i -= 1
+      }
+      these
+    }
+
+    /** A substream starting at index `from`
+     *  and extending up to (but not including) index `until`.
+     *
+     *  @This is equivalent to (but possibly more efficient than)
+     *  c.drop(from).take(to - from)
+     *
+     *  @param from   The index of the first element of the returned subsequence
+     *  @param until  The index of the element following the returned subsequence
+     *  @throws IndexOutOfBoundsException if from < 0
+     *          or length < from + len
+     *  @note  Might return different results for different runs, unless this iterable is ordered
+     */
+    override def slice(from: Int, to: Int): Stream[A] =
+      this.drop(from).take(to - from)
+
+    /** The stream without its last element.
+     *  @throws Predef.UnsupportedOperationException if the stream is empty.
+     */
+    override def init: Stream[A] =
+      if (tail.isEmpty) Nil
+      else new Cons(head, tail.init)
+
+    /** Returns the rightmost n elements from this iterable.
+     *  @param n the number of elements to take
+     */
+    override def takeRight(n: Int): Stream[A] = {
+      var these: Stream[A] = this
+      var lead = this drop n
+      while (!lead.isEmpty) {
+        these = these.tail
+        lead = lead.tail
+      }
+      these
+    }
+
+    /** Returns the longest prefix of this stream whose elements satisfy
+     *  the predicate p.
+     *
+     *  @param p the test predicate.
+     */
+    override def takeWhile(p: A => Boolean): Stream[A] =
+      if (p(head)) new Cons(head, tail takeWhile p) else Nil
+
+
+    /** Returns the longest suffix of this iterable whose first element
+     *  does not satisfy the predicate p.
+     *
+     *  @param p the test predicate.
+     */
+    override def dropWhile(p: A => Boolean): Stream[A] = {
+      var these: Stream[A] = this
+      while (!these.isEmpty && p(these.head)) these = these.tail
+      these
+    }
+
+    /** Returns a pair consisting of the longest prefix of the stream whose
+     *  elements all satisfy the given predicate, and the rest of the stream.
+     *
+     *  @param p the test predicate
+     */
+    override def span(p: A => Boolean): (List[A], Stream[A]) = {
+      var these: Stream[A] = this
+      val l = new ListBuffer[A]
+      while (!these.isEmpty && p(these.head)) {
+        l += these.head
+        these = these.tail
+      }
+      (l.toList, these)
+    }
+
+    // Overridden methods from Sequence
+
+    /** Builds a new stream from this stream in which any duplicates (wrt to ==) removed.
+     *  Among duplicate elements, only the first one is retained in the result stream
+     */
+    override def removeDuplicates: Stream[A] =
+      new Cons(head, tail.filter(head !=).removeDuplicates)
+
+    /** Returns a new sequence of given length containing the elements of this sequence followed by zero
+     *  or more occurrences of given elements.
+     */
+    override def padTo[B >: A](len: Int, elem: B): Stream[B] =
+      new Cons(head, tail.padTo(len - 1, elem))
+  }
+
+  /**
+   * Create an infinite stream starting at start
+   * and incrementing by step step
+   *
+   * @param start the start value of the stream
+   * @param step the increment value of the stream
+   * @return the stream starting at value start.
+   */
+  def from(start: Int, step: Int): Stream[Int] =
+    new Cons(start, from(start+step, step))
+
+  /**
+   * Create an infinite stream starting at start
+   * and incrementing by 1.
+   *
+   * @param start the start value of the stream
+   * @return the stream starting at value start.
+   */
+  def from(start: Int): Stream[Int] = from(start, 1)
+
+  /**
+   * Create an infinite stream containing the given element expression (which is computed for each
+   * occurrence)
+   * @param elem the element composing the resulting stream
+   * @return the stream containing an inifinite number of elem
+   * @deprecated use fill instead
+   */
+  @deprecated def fill[A](elem: => A): Stream[A] = new Cons(elem, fill(elem))
+
+  /** A stream containing all elements of a given iterator, in the order they are produced.
+   *  @param it   The iterator producing the stream's elements
+   *  @deprecated use it.toStream instead
+   */
+  @deprecated def fromIterator[A](it: Iterator[A]): Stream[A] =
+    if (it.hasNext) cons(it.next, fromIterator(it)) else empty
+
+  /** The concatenation of a sequence of streams
+   * @deprecated use xs.flatten instead
+   */
+  @deprecated def concat[A](xs: Iterable[Stream[A]]): Stream[A] = concat(xs.elements)
+
+  /** The concatenation of all streams returned by an iterator
+   * @deprecated use xs.toStream.flatten instead
+   */
+  @deprecated def concat[A](xs: Iterator[Stream[A]]): Stream[A] =
+    if (xs.hasNext) xs.next append concat(xs)
+    else empty
+
+  /**
+   * Create a stream with element values
+   * vn+1 = step(vn)
+   * where v0 = start
+   * and elements are in the range between start (inclusive)
+   * and end (exclusive)
+   * @deprecated  use @see iterate instead.
+   * @param start the start value of the stream
+   * @param end the end value of the stream
+   * @param step the increment function of the stream, must be monotonically increasing or decreasing
+   * @return the stream starting at value start.
+   */
+  @deprecated def range(start: Int, end: Int, step: Int => Int): Stream[Int] = {
+    val up = step(start) > start
+    val down = step(start) < start
+    def loop(lo: Int): Stream[Int] =
+      if ((!up || lo < end) && (!down || lo > end)) cons(lo, loop(step(lo)))
+      else empty
+    loop(start)
+  }
+
+  /**
+   * Create an infinite stream containing the given element.
+   *
+   * @param elem the element composing the resulting stream
+   * @return the stream containing an inifinite number of elem
+   * @deprecated use fill(elem) instead
+   */
+  @deprecated def const[A](elem: A): Stream[A] = cons(elem, const(elem))
+
+  /** Create a stream containing several copies of an element.
+   *
+   *  @param n    the length of the resulting stream
+   *  @param elem the element composing the resulting stream
+   *  @return     the stream composed of n elements all equal to elem
+   *  @deprecated use fill(n, elem) instead
+   */
+  @deprecated def make[A](n: Int, elem: A): Stream[A] =
+    const(elem) take n
+}
+
+import Stream._
+
+/**
+ * 
The class Stream implements lazy lists where elements
+ * are only evaluated when they are needed. Here is an example:

+ * 
+ * object Main extends Application {
+ *
+ *   def from(n: Int): Stream[Int] =
+ *     Stream.cons(n, from(n + 1))
+ *
+ *   def sieve(s: Stream[Int]): Stream[Int] =
+ *     Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))
+ *
+ *   def primes = sieve(from(2))
+ *
+ *   primes take 10 print
+ * }
+ * 

+ *
+ * @author Martin Odersky, Matthias Zenger
+ * @version 1.1 08/08/03
+ */
+abstract class Stream[+A] extends Sequence[A] with SequenceTemplate[Stream, A] {
+self =>
+
+  import collection.{Iterable, OrderedIterable, Sequence, Vector}
+
+  /** is this stream empty? */
+  def isEmpty: Boolean
+
+  /** The first element of this stream
+   *  @throws Predef.NoSuchElementException if the stream is empty.
+   */
+  def head: A
+
+  /** A stream consisting of the remaining elements of this stream after the first one.
+   *  @throws Predef.UnsupportedOperationException if the stream is empty.
+   */
+  def tail: Stream[A]
+
+  // Implementation of abstract methods
+
+  /** Create a new @see LazyBuilder to build a stream */
+  def newBuilder[B]: Builder[Stream, B] = new LazyBuilder[Stream, B] {
+    def result: Stream[B] = elements.toStream
+  }
+
+  /** Returns the number of elements in the list.
+   */
+  def length: Int = {
+    var these = self
+    var len = 0
+    while (!these.isEmpty) {
+      len += 1
+      these = these.tail
+    }
+    len
+  }
+
+  /** Returns the n-th element of this stream. The first element
+   *  (head of the stream) is at position 0.
+   *
+   *  @param n index of the element to return
+   *  @return  the element at position n in this stream.
+   *  @throws Predef.NoSuchElementException if the stream is too short.
+   */
+  override def apply(n: Int): A = drop(n).head
+
+  // New methods in Stream
+
+  /** The stream resulting from the concatenation of this stream with the argument stream.
+   *  @param rest   The stream that gets appended to this stream
+   */
+  def append[B >: A](rest: => Iterable[B]): Stream[B] =
+    if (isEmpty) rest.toStream else new Cons(head, tail append rest)
+
+  /** Force evaluation of the whole stream and return it */
+  def force: Stream[A] = {
+    var these = this
+    while (!isEmpty) these = these.tail
+    this
+  }
+
+  /** Prints elements of this stream one by one, separated by commas */
+  def print() { print(", ") }
+
+  /** Prints elements of this stream one by one, separated by sep
+   *  @param sep   The separator string printed between consecutive elements.
+   */
+  def print(sep: String) {
+    def loop(these: Stream[A], start: String) {
+      Console.print(start)
+      if (isEmpty) Console.print("empty")
+      else {
+        Console.print(these.head)
+        loop(these.tail, sep)
+      }
+    }
+    loop(this, "")
+  }
+
+  // Overridden methods from IterableTemplate or overloaded variants of such methods
+
+  /** Returns the elements in the sequence as an iterator
+   */
+  override def elements: Iterator[A] = new Iterator[A] {
+    var these = self
+    def hasNext: Boolean = !these.isEmpty
+    def next: A =
+      if (hasNext) {
+        val result = these.head; these = these.tail; result
+      } else Iterator.empty.next
+    override def toList: List[A] = these.toList
+  }
+
+  /** Apply the given function f to each element of this stream
+   *  (while respecting the order of the elements).
+   *
+   *  @param f the treatment to apply to each element.
+   */
+  override def foreach(f: A => Unit) {
+    var these = this
+    while (!these.isEmpty) {
+      f(these.head)
+      these = these.tail
+    }
+  }
+
+  /** Tests if the predicate p is satisfied by all elements
+   *  in this list.
+   *
+   *  !!! todo: perform speed with inherited version from Iterable, and drop
+   *      if not significantly better
+   *  @param p the test predicate.
+   *  @return  true iff all elements of this list satisfy the
+   *           predicate p.
+   */
+  override def forall(p: A => Boolean): Boolean = {
+    var these = this
+    while (!these.isEmpty) {
+      if (!p(these.head)) return false
+      these = these.tail
+    }
+    true
+  }
+
+  /** Tests the existence in this list of an element that satisfies the
+   *  predicate p.
+   *
+   *  !!! todo: perform speed with inherited version from Iterable, and drop
+   *      if not significantly better
+   *  @param p the test predicate.
+   *  @return  true iff there exists an element in this list that
+   *           satisfies the predicate p.
+   */
+  override def exists(p: A => Boolean): Boolean = {
+    var these = this
+    while (!these.isEmpty) {
+      if (p(these.head)) return true
+      these = these.tail
+    }
+    false
+  }
+
+  /** Count the number of elements in the iterable which satisfy a predicate.
+   *
+   *  !!! todo: perform speed with inherited version from Iterable, and drop
+   *      if not significantly better
+   *  @param p the predicate for which to count
+   *  @return  the number of elements satisfying the predicate p.
+   */
+  override def count(p: A => Boolean): Int = {
+    var these = this
+    var cnt = 0
+    while (!these.isEmpty) {
+      if (p(these.head)) cnt += 1
+      these = these.tail
+    }
+    cnt
+  }
+
+  /** Find and return the first element of the list satisfying a
+   *  predicate, if any.
+   *
+   *  !!! todo: perform speed with inherited version from Iterable, and drop
+   *      if not significantly better
+   *  @param p the predicate
+   *  @return the first element in the list satisfying p,
+   *  or None if none exists.
+   */
+  override def find(p: A => Boolean): Option[A] = {
+    var these = this
+    while (!these.isEmpty) {
+      if (p(these.head)) return Some(these.head)
+      these = these.tail
+    }
+    None
+  }
+
+  /** Combines the elements of this list together using the binary
+   *  function f, from left to right, and starting with
+   *  the value z.
+   *
+   *  !!! todo: perform speed with inherited version from Iterable, and drop
+   *      if not significantly better
+   *  @return f(... (f(f(z, a0), a1) ...),
+   *          an) if the list is
+   *          [a0, a1, ..., an].
+   */
+  override def foldLeft[B](z: B)(f: (B, A) => B): B = {
+    var acc = z
+    var these = this
+    while (!these.isEmpty) {
+      acc = f(acc, these.head)
+      these = these.tail
+    }
+    acc
+  }
+
+  /** Combines the elements of this list together using the binary
+   *  function f, from right to left, and starting with
+   *  the value z.
+   *
+   *  @return f(a0, f(a1, f(..., f(an, z)...)))
+   *          if the list is [a0, a1, ..., an].
+   */
+  override def foldRight[B](z: B)(f: (A, B) => B): B =
+    if (this.isEmpty) z
+    else f(head, tail.foldRight(z)(f))
+
+  /** Combines the elements of this list together using the binary
+   *  operator op, from left to right
+   *  @param op  The operator to apply
+   *  @return op(... op(a0,a1), ..., an)
+      if the list has elements
+   *          a0, a1, ..., an.
+   *  @throws Predef.UnsupportedOperationException if the list is empty.
+   */
+  override def reduceLeft[B >: A](f: (B, A) => B): B =
+    if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
+    else tail.foldLeft[B](head)(f)
+
+  /** Combines the elements of this iterable object together using the binary
+   *  operator op, from right to left
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param op  The operator to apply
+   *
+   *  @return a0 op (... op (an-1 op an)...)
+   *          if the iterable object has elements a0, a1, ...,
+   *          an.
+   *
+   *  @throws Predef.UnsupportedOperationException if the iterator is empty.
+   */
+  override def reduceRight[B >: A](op: (A, B) => B): B =
+    if (isEmpty) throw new UnsupportedOperationException("Nil.reduceRight")
+    else if (tail.isEmpty) head
+    else op(head, tail.reduceRight(op))
+
+  /**
+   *  Create a stream which contains all the elements of this iterable object.
+   *  @note consider using projection for lazy behavior.
+   */
+  override def toStream: Stream[A] = this
+
+  /** Defines the prefix of this object's toString representation as ``Stream''.
+   */
+  override def stringPrefix = "Stream"
+
+  /** The last element of this stream.
+   *
+   *  @throws Predef.NoSuchElementException if the stream is empty.
+   */
+  override def last: A = {
+    if (isEmpty) throw new NoSuchElementException
+    var these = this
+    var nx = these.tail
+    while (!nx.isEmpty) {
+      these = nx
+      nx = nx.tail
+    }
+    these.head
+  }
+
+  /** Returns the rightmost n elements from this iterable.
+   *  @param n the number of elements to take
+   */
+  override def dropRight(n: Int): List[A] = {
+    val b = new ListBuffer[A]
+    var these = this
+    var lead = this drop n
+    while (!lead.isEmpty) {
+      b += these.head
+      these = these.tail
+      lead = lead.tail
+    }
+    b.toList
+  }
+
+  /** Returns true iff the other stream contains the same elements as this one.
+   *
+   *  @note will not terminate for two infinite-sized streams.
+   *  @param that  the other stream
+   */
+  def sameElements[B >: A](that: Stream[B]): Boolean = {
+    val these = this
+    val those = that
+    while (!these.isEmpty && !those.isEmpty && these.head == those.head) {}
+    these.isEmpty && those.isEmpty
+  }
+
+  // Overridden methods from Sequence
+
+  /** Result of comparing length with operand len.
+   *  returns x where
+   *  x < 0    iff    this.length < len
+   *  x == 0   iff    this.length == len
+   *  x > 0    iff    this.length > len.
+   */
+  override def lengthCompare(len: Int): Int =  {
+    var i = 0
+    var these = self
+    while (!these.isEmpty && i <= len) {
+      i += 1
+      these = these.tail
+    }
+    i - len
+  }
+
+  /** Is this partial function defined for the index x?
+   */
+  override def isDefinedAt(x: Int): Boolean = x >= 0 && lengthCompare(x) >= 0
+
+  /** Returns length of longest segment starting from a start index `from`
+   *  such that every element of the segment satisfies predicate `p`.
+   *  @note may not terminate for infinite-sized collections.
+   *  @param  p the predicate
+   *  @param  from  the start index
+   */
+  override def segmentLength(p: A => Boolean, from: Int): Int = {
+    var i = from
+    var these = this drop from
+    while (!these.isEmpty && p(these.head)) {
+      i += 1
+      these = these.tail
+    }
+    i
+  }
+
+  /** Returns index of the first element starting from a start index
+   *  satisying a predicate, or -1, if none exists.
+   *
+   *  @note may not terminate for infinite-sized streams.
+   *  @param  p the predicate
+   *  @param  from  the start index
+   */
+  override def indexWhere(p: A => Boolean, from: Int): Int = {
+    var i = from
+    var these = this drop from
+    while (!these.isEmpty && !p(these.head)) {
+      i += 1
+      these = these.tail
+    }
+    if (these.isEmpty) -1 else i
+  }
+
+  /** Returns index of the last element satisying a predicate, or -1, if none exists.
+   *
+   *  @param  p the predicate
+   *  @return   the index of the last element satisfying p,
+   *            or -1 if such an element does not exist
+   */
+  override def lastIndexWhere(p: A => Boolean, end: Int): Int = {
+    var i = 0
+    var these = this
+    var last = -1
+    while (!these.isEmpty && i <= end) {
+      if (p(these.head)) last = i
+    }
+    i
+  }
+
+  /** A list consisting of all elements of this list in reverse order.
+   */
+  override def reverse: List[A] = {
+    var result: List[A] = Nil
+    var these = this
+    while (!these.isEmpty) {
+      result = these.head :: result
+      these = these.tail
+    }
+    result
+  }
+}
+
diff --git a/src/library/scalax/collection/immutable/Vector.scala b/src/library/scalax/collection/immutable/Vector.scala
new file mode 100644
index 0000000000..64cf512c90
--- /dev/null
+++ b/src/library/scalax/collection/immutable/Vector.scala
@@ -0,0 +1,22 @@
+package scalax.collection.immutable
+
+import generic.covariant
+
+/** Collection classes mixing in this class provide a method
+ *  elements which returns an iterator over all the
+ *  elements contained in the collection.
+ *
+ *  @note If a collection has a known size, it should also sub-type SizedIterable.
+ *    // !!! todo: insert good immutable vector implementation here.
+ *  @author  Matthias Zenger
+ *  @autor   Martin Odersky
+ *  @owner   Martin Odersky
+ *  @version 2.8
+ */
+trait Vector[+A] extends collection.Vector[A] with Sequence[A]
+
+object Vector extends covariant.SequenceFactory[Vector] {
+  val empty: Vector[Nothing] = immutable.Vector.empty
+}
+
+
diff --git a/src/library/scalax/collection/mutable/Appendable.scala b/src/library/scalax/collection/mutable/Appendable.scala
index b8e8569a14..6dbe89346e 100644
--- a/src/library/scalax/collection/mutable/Appendable.scala
+++ b/src/library/scalax/collection/mutable/Appendable.scala
@@ -33,7 +33,7 @@ trait Appendable[A] {
   def +=(elem1: A, elem2: A, elems: A*) {
     this += elem1
     this += elem2
-    this ++= elems.asInstanceOf[Iterable[A]] // !!!
+    this ++= elems.asInstanceOf[Iterable[A]] // !@!
   }
 
   /** Appends a number of elements provided by an iterator
@@ -64,7 +64,7 @@ trait Appendable[A] {
    *  @param elems the remaining elements to append.
    */
   def +(elem1: A, elem2: A, elems: A*): this.type =
-    this + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]] // !!!
+    this + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]] // !@!
 
   /** Appends a number of elements provided by an iterable object
    *  via its elements method. The identity of the
diff --git a/src/library/scalax/collection/mutable/Buffer.scala b/src/library/scalax/collection/mutable/Buffer.scala
index c11fa37409..c03b49ee16 100644
--- a/src/library/scalax/collection/mutable/Buffer.scala
+++ b/src/library/scalax/collection/mutable/Buffer.scala
@@ -124,7 +124,7 @@ trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable
    *  @param elem  the element to prepend.
    */
   def +:(elem1: A, elem2: A, elems: A*): this.type =
-    elem1 +: elem2 +: (elems.asInstanceOf[Iterable[A]]) ++: this // !!!
+    elem1 +: elem2 +: (elems.asInstanceOf[Iterable[A]]) ++: this // !@!
 
   /** Prepends a number of elements provided by an iterable object
    *  via its elements method. The identity of the
@@ -146,7 +146,7 @@ trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable
    *
    *  @param elems  the elements to append.
    */
-  def append(elems: A*) { this ++= elems.asInstanceOf[Iterable[A]] } // !!!
+  def append(elems: A*) { this ++= elems.asInstanceOf[Iterable[A]] } // !@!
 
   /** Appends a number of elements provided by an iterable object
    *  via its elements method.
@@ -159,7 +159,7 @@ trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable
    *
    *  @param elem  the element to prepend.
    */
-  def prepend(elems: A*) { elems.asInstanceOf[Iterable[A]] ++: this } // !!!
+  def prepend(elems: A*) { elems.asInstanceOf[Iterable[A]] ++: this } // !@!
 
   /** Prepends a number of elements provided by an iterable object
    *  via its elements method. The identity of the
@@ -184,7 +184,7 @@ trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable
    *  @param n      the index where a new element will be inserted.
    *  @param elems  the new elements to insert.
    */
-  def insert(n: Int, elems: A*) { insertAll(n, elems.asInstanceOf[Iterable[A]]) } // !!!
+  def insert(n: Int, elems: A*) { insertAll(n, elems.asInstanceOf[Iterable[A]]) } // !@!
 
   /** Removes the first n elements.
    *
diff --git a/src/library/scalax/collection/mutable/ResizableArray.scala b/src/library/scalax/collection/mutable/ResizableArray.scala
index e4dd8bd47d..97d1ba2d6d 100644
--- a/src/library/scalax/collection/mutable/ResizableArray.scala
+++ b/src/library/scalax/collection/mutable/ResizableArray.scala
@@ -55,7 +55,7 @@ trait ResizableArray[A] extends Vector[A] {
    *  @param   The buffer to which elements are copied
    */
   override def copyToBuffer[B >: A](dest: Buffer[B]) {
-    dest ++= array.asInstanceOf[Iterable[A]] // !!!
+    dest ++= array.asInstanceOf[Iterable[A]] // !@!
   }
 
   override def foreach(f: A => Unit) {
diff --git a/src/library/scalax/collection/mutable/Vector.scala b/src/library/scalax/collection/mutable/Vector.scala
index b181e93303..91a50b5300 100644
--- a/src/library/scalax/collection/mutable/Vector.scala
+++ b/src/library/scalax/collection/mutable/Vector.scala
@@ -15,6 +15,6 @@ trait Vector[A] extends collection.Vector[A] with generic.mutable.VectorTemplate
 object Vector extends generic.nonvariant.SequenceFactory[Vector] {
 
   /** The empty iterable */
-  def apply[A](args: A*): Vector[A] = null // !!!
+  def apply[A](args: A*): Vector[A] = new ArrayBuffer[A] ++ args.asInstanceOf[Iterable[A]] // !@!
 
 }
diff --git a/src/library/scalax/util/control/TailRec.scala b/src/library/scalax/util/control/TailRec.scala
new file mode 100644
index 0000000000..db6cbfa2ed
--- /dev/null
+++ b/src/library/scalax/util/control/TailRec.scala
@@ -0,0 +1,24 @@
+package scala.util.control
+
+abstract class TailRec[+A]
+
+object TailRec {
+
+  case class Call[A](rest: () => TailRec[A]) extends TailRec[A]
+  case class Done[A](result: A) extends TailRec[A]
+
+  def tailcall[A](rest: => TailRec[A]) = new Call(() => rest)
+  def done    [A](result: A) = new Done(result)
+  def trampoline[A](body: TailRec[A]): A = {
+    def loop(body: TailRec[A]): A = body match {
+      case Call(rest) => loop(rest())
+      case Done(result) => result
+    }
+    loop(body)
+  }
+  def loop[A](body: TailRec[A]): A = body match {
+    case Call(rest) => loop[A](rest())
+    case Done(result) => result
+  }
+}
+
-- 
cgit v1.2.3