Merging everything from the 2.8.x development b...

Merging everything from the 2.8.x development branch back to trunk.

- If you were working on trunk, please keep working on trunk If you were
- working on 2.8-devel, please switch to trunk now

8 files changed, 1848 insertions, 0 deletions

diff --git a/src/library/scalax/collection/generic/covartest/IterableFactory.scala b/src/library/scalax/collection/generic/covartest/IterableFactory.scala
new file mode 100755
index 0000000000..d12da89987
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/IterableFactory.scala
@@ -0,0 +1,108 @@
+package scalax.collection.generic.covartest
+
+trait IterableFactory[CC[A] <: Iterable[A]] {
+
+  /** Create CC collection of specified elements */
+  def apply[A](args: A*): CC[A]
+
+  protected def newBuilder[A]: Builder[CC, A] =
+    apply().newBuilder[A].asInstanceOf[Builder[CC, A]]
+
+  /** 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: CC[A]*): CC[A] = {
+    val b = newBuilder[A]
+    for (xs <- xss) b ++= xs
+    b.result
+  }
+
+  /** An iterable that contains the same element a number of times
+   *  @param   n  The number of elements returned
+   *  @param   elem The element returned each time
+   */
+  def fill[A](n: Int, elem: => A): CC[A] = {
+    val b = newBuilder[A]
+    var i = 0
+    while (i < n) {
+      b += elem
+      i += 1
+    }
+    b.result
+  }
+
+  def fill[A](n1: Int, n2: Int, elem: => A): CC[CC[A]] =
+    tabulate(n1)(_ => fill(n2, elem))
+
+  def fill[A](n1: Int, n2: Int, n3: Int, elem: => A): CC[CC[CC[A]]] =
+    tabulate(n1)(_ => fill(n2, n3, elem))
+
+  def tabulate[A](n: Int)(f: Int => A): CC[A] = {
+    val b = newBuilder[A]
+    var i = 0
+    while (i < n) {
+      b += f(i)
+      i += 1
+    }
+    b.result
+  }
+
+  def tabulate[A](n1: Int, n2: Int)(f: (Int, Int) => A): CC[CC[A]] =
+    tabulate(n1)(i1 => tabulate(n2)(i2 => f(i1, i2)))
+
+  def tabulate[A](n1: Int, n2: Int, n3: Int)(f: (Int, Int, Int) => A): CC[CC[CC[A]]] =
+    tabulate(n1)(i1 => tabulate(n2)(i2 => tabulate(n3)(i3 => f(i1, i2, i3))))
+// todo: go up to 5(?)
+
+  /** Create a sequence of increasing integers in a range.
+   *
+   *  @param from the start value of the sequence
+   *  @param end the end value of the sequence
+   *  @return the sorted list of all from `from` (inclusive)
+   *  up to, but exclusding, `end`.
+   */
+  def range[A](start: Int, end: Int): CC[Int] = range(start, end, 1)
+
+  /** Create a sequence of increasing integers in a range.
+   *
+   *  @param from the start value of the sequence
+   *  @param end the end value of the sequence
+   *  @param step the increment value of successive elements
+   *  @return a list of values <code>from + n * step</code> for
+   *          increasing n. If `step > 0` the sequence terminates
+   *          with the largest value less than `end`. If `step < 0`
+   *          the sequence terminates with the smallest value greater than `end`.
+   *          If `step == 0`, the sequence gors on infinitely (in that
+   *          case the `range` operation might not terminate.
+   */
+  def range(start: Int, end: Int, step: Int): CC[Int] = {
+    val b = newBuilder[Int]
+    var i = start
+    while ((step <= 0 || i < end) && (step >= 0 || i > end)) {
+      b += i
+      i += step
+    }
+    b.result
+  }
+
+  /** Create a sequence by repeatedly applying a given function to a start value.
+   *
+   *  @param start the start value of the sequence
+   *  @param len   the length of the sequence
+   *  @param f     the function that's repeatedly applied
+   *  @return      the sequence with elements <code>(start, f(start), f(f(start)), ..., f<sup>len-1</sup>(start))</code>
+   */
+  def iterate(start: Int, len: Int)(f: Int => Int): CC[Int] = {
+    val b = newBuilder[Int]
+    var acc = start
+    var i = 0
+    while (i < len) {
+      b += acc
+      acc = f(acc)
+      i += 1
+    }
+    b.result
+  }
+}
diff --git a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala
new file mode 100755
index 0000000000..b83f3b9247
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala
@@ -0,0 +1,816 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+
+package scalax.collection.generic.covartest
+
+import scalax.collection.mutable.{Buffer, ArrayBuffer, ListBuffer}
+import scalax.collection.immutable.{List, Nil, ::}
+import util.control.Break._
+import Iterable._
+
+/** Collection classes mixing in this class provide a method
+ *  <code>elements</code> which returns an iterator over all the
+ *  elements contained in the collection.
+ *
+ *  @note If a collection has a known <code>size</code>, it should also sub-type <code>Collection</code>.
+ *        Only potentially unbounded collections should directly sub-class <code>Iterable</code>.
+ *  @author Matthias Zenger
+ *  @author Martin Odersky
+ *  @version 2.8
+ */
+trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] { self/*: CC[A]*/ =>
+
+  /** The template itself seen as an instance of `CC[A]`.
+   * @note: It would be logical to have a self type `CC[A]` instead, then we would not need
+   * this method. Unfortunately, tyis runs afoul some pecularities in Scala's member resolution
+   * algorithm: If the self type is a CC, then Iterable is one of its supertypes. Iterable
+   * defines a number of concrete methods such as newBuilder which are abstract here.
+   * The newBuilder method in Iterable[A] has type Builder[Iterable, A]. Because Scala
+   * prefers concrete over abstract members, it is this newBuilder which is chosen, instead of
+   * the abstract newBuilder in class IterableTemplate of type Builder[CC, A].
+   * Even for concrete methods we have a problem because the last mixin in the parents of CC is
+   * Iterable, not IterableTemplate. So resolution picks the version in Iterable, which returns
+   * again an Iterable, not a CC, as would be required.
+   * These problems would be avoided if Scala computed the type of a member as the glb of the types
+   * all members in the class and its superclasses types.
+   * I think overall this would be a better design.
+   */
+  protected[this] def thisCC: CC[A] = this.asInstanceOf[CC[A]]
+
+  /** Creates a new iterator over all elements contained in this
+   *  object.
+   *
+   *  @return the new iterator
+   */
+  def elements: Iterator[A]
+
+  /** Create a new builder for this IterableType
+   */
+  def newBuilder[B]: Builder[CC, B]
+
+  /** Is this collection empty? */
+  def isEmpty: Boolean = !elements.hasNext
+
+  /** returns true iff this collection has a bound size.
+   *  Many APIs in this trait will not work on collections of
+   *  unbound sizes.
+   */
+  def hasDefiniteSize = true
+
+  /** Create a new sequence of type CC which contains all elements of this sequence
+   *  followed by all elements of Iterable `that'
+   */
+  def ++[B >: A](that: Iterable[B]): CC[B] = {
+    val b: Builder[CC, B] = (this: IterableTemplate[CC, A]).newBuilder[B]
+    b ++= thisCC
+    b ++= that
+    b.result
+  }
+
+  /** Create a new sequence of type IterableType which contains all elements of this sequence
+   *  followed by all elements of Iterator `that'
+   */
+  def ++[B >: A](that: Iterator[B]): CC[B] = {
+    val b = newBuilder[B]
+    b ++= thisCC
+    b ++= that
+    b.result
+  }
+
+  /** Returns the sequence resulting from applying the given function
+   *  <code>f</code> to each element of this sequence.
+   *
+   *  @param f function to apply to each element.
+   *  @return  <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> if this
+   *           sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
+   */
+  def map[B](f: A => B): CC[B] = {
+    val b = newBuilder[B]
+    for (x <- this) b += f(x)
+    b.result
+  }
+
+  /** Applies the given function <code>f</code> to each element of
+   *  this sequence, then concatenates the results.
+   *
+   *  @param f the function to apply on each element.
+   *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
+   *           this sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
+   */
+  def flatMap[B](f: A => Iterable[B]): CC[B] = {
+    val b = newBuilder[B]
+    for (x <- this) b ++= f(x)
+    b.result
+  }
+
+  /** Returns all the elements of this sequence that satisfy the
+   *  predicate <code>p</code>. The order of the elements is preserved.
+   *  @param p the predicate used to filter the list.
+   *  @return the elements of this list satisfying <code>p</code>.
+   */
+  def filter(p: A => Boolean): CC[A] = {
+    val b = newBuilder[A]
+    for (x <- this)
+      if (p(x)) b += x
+    b.result
+  }
+
+  /** Removes all elements of the iterable which satisfy the predicate
+   *  <code>p</code>. This is like <code>filter</code> with the
+   *  predicate inversed.
+   *
+   *  @param p the predicate to use to test elements
+   *  @return  the list without all elements which satisfy <code>p</code>
+   */
+  def remove(p: A => Boolean): CC[A] = filter(!p(_))
+
+  /** Partitions this iterable in two iterables according to a predicate.
+   *
+   *  @param p the predicate on which to partition
+   *  @return  a pair of iterables: the iterable that satisfies the predicate
+   *           <code>p</code> and the iterable that does not.
+   *           The relative order of the elements in the resulting iterables
+   *           is the same as in the original iterable.
+   */
+  def partition(p: A => Boolean): (CC[A], CC[A]) = {
+    val l, r = newBuilder[A]
+    for (x <- this) (if (p(x)) l else r) += x
+    (l.result, r.result)
+  }
+
+  /** Apply a function <code>f</code> to all elements of this
+   *  iterable object.
+   *
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param  f   a function that is applied to every element.
+   *  Note this function underlies the implementation of most other bulk operations.
+   *  It should be overridden in concrete collectionc classes with efficient implementations.
+   */
+  def foreach(f: A => Unit): Unit = elements.foreach(f)
+
+  /** Return true iff the given predicate `p` yields true for all elements
+   *  of this iterable.
+   *
+   *  @note May not terminate for infinite-sized collections.
+   *  @param   p     the predicate
+   */
+  def forall(p: A => Boolean): Boolean = {
+    var result = true
+    breakable {
+      for (x <- this)
+        if (!p(x)) { result = false; break }
+    }
+    result
+  }
+
+  /** Return true iff there is an element in this iterable for which the
+   *  given predicate `p` yields true.
+   *
+   *  @note May not terminate for infinite-sized collections.
+   *  @param   p     the predicate
+   */
+  def exists(p: A => Boolean): Boolean = {
+    var result = false
+    breakable {
+      for (x <- this)
+        if (p(x)) { result = true; break }
+    }
+    result
+  }
+
+  /** Count the number of elements in the iterable which satisfy a predicate.
+   *
+   *  @param p the predicate for which to count
+   *  @return  the number of elements satisfying the predicate <code>p</code>.
+   */
+  def count(p: A => Boolean): Int = {
+    var cnt = 0
+    for (x <- this) {
+      if (p(x)) cnt += 1
+    }
+    cnt
+  }
+
+  /** Find and return the first element of the iterable object satisfying a
+   *  predicate, if any.
+   *
+   *  @note may not terminate for infinite-sized collections.
+   *  @param p the predicate
+   *  @return an option containing the first element in the iterable object
+   *  satisfying <code>p</code>, or <code>None</code> if none exists.
+   */
+  def find(p: A => Boolean): Option[A] = {
+    var result: Option[A] = None
+    breakable {
+      for (x <- this)
+        if (p(x)) { result = Some(x); break }
+    }
+    result
+  }
+
+  /** Combines the elements of this iterable object together using the binary
+   *  function <code>f</code>, from left to right, and starting with
+   *  the value <code>z</code>.
+   *
+   *  @note Will not terminate for infinite-sized collections.
+   *  @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...),
+   *          a<sub>n</sub>)</code> if the list is
+   *          <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>.
+   */
+  def foldLeft[B](z: B)(op: (B, A) => B): B = {
+    var result = z
+    for (x <- this)
+      result = op(result, x)
+    result
+  }
+
+  /** Combines the elements of this list together using the binary
+   *  function <code>f</code>, from right to left, and starting with
+   *  the value <code>z</code>.
+   *
+   *  @note Will not terminate for infinite-sized collections.
+   *  @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code>
+   *          if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>.
+   */
+  def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op)
+
+  /** Similar to <code>foldLeft</code> but can be used as
+   *  an operator with the order of list and zero arguments reversed.
+   *  That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code>
+   *  @note Will not terminate for infinite-sized collections.
+   */
+  def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op)
+
+  /** An alias for <code>foldRight</code>.
+   *  That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code>
+   *  @note Will not terminate for infinite-sized collections.
+   */
+  def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op)
+
+  /** Combines the elements of this iterable object together using the binary
+   *  operator <code>op</code>, from left to right
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param op  The operator to apply
+   *  @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code>
+      if the iterable object has elements
+   *          <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
+   *  @throws Predef.UnsupportedOperationException if the iterable object is empty.
+   */
+  def reduceLeft[B >: A](op: (B, A) => B): B = {
+    if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
+    var result: B = elements.next
+    var first = true
+    for (x <- this)
+      if (first) first = false
+      else result = op(result, x)
+    result
+  }
+
+  /** Combines the elements of this iterable object together using the binary
+   *  operator <code>op</code>, from right to left
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param op  The operator to apply
+   *
+   *  @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code>
+   *          if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
+   *          a<sub>n</sub></code>.
+   *
+   *  @throws Predef.UnsupportedOperationException if the iterator is empty.
+   */
+  def reduceRight[B >: A](op: (A, B) => B): B =
+    elements.reduceRight(op)
+
+  /** Returns an iterable formed from this iterable and the specified list
+   *  `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.
+   */
+  def zip[B](that: Iterable[B]): CC[(A, B)] = {
+    val these = this.elements
+    val those = that.elements
+    val b = this.newBuilder[(A, B)]
+    while (these.hasNext && those.hasNext)
+      b += ((these.next, those.next))
+    b.result
+  }
+
+  /** Returns a iterable formed from this iterable and the specified iterable
+   *  <code>that</code> by associating each element of the former with
+   *  the element at the same position in the latter.
+   *
+   *  @param that     iterable <code>that</code> may have a different length
+   *                  as the self iterable.
+   *  @param thisElem element <code>thisElem</code> is used to fill up the
+   *                  resulting iterable if the self iterable is shorter than
+   *                  <code>that</code>
+b   *  @param thatElem element <code>thatElem</code> is used to fill up the
+   *                  resulting iterable if <code>that</code> is shorter than
+   *                  the self iterable
+   *  @return         <code>Iterable((a<sub>0</sub>,b<sub>0</sub>), ...,
+   *                  (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>),
+   *                  ..., {elem,b<sub>m</sub>})</code>
+   *                  when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip
+   *                  [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is
+   *                  invoked where <code>m &gt; n</code>.
+   */
+  def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): CC[(A1, B1)] = {
+    val these = this.elements
+    val those = that.elements
+    val b = newBuilder[(A1, B1)]
+    while (these.hasNext && those.hasNext)
+      b += ((these.next, those.next))
+    while (these.hasNext)
+      b += ((these.next, thatElem))
+    while (those.hasNext)
+      b += ((thisElem, those.next))
+    b.result
+  }
+
+  /** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to
+   *  `s zip s.indices`, but is usually more efficient.
+   */
+  def zipWithIndex: CC[(A, Int)] = {
+    val b = newBuilder[(A, Int)]
+    var i = 0
+    for (x <- this) {
+      b += ((x, i))
+      i +=1
+    }
+    b.result
+  }
+
+  /** Copy all elements to a given buffer
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param  dest   The buffer to which elements are copied
+   */
+  def copyToBuffer[B >: A](dest: Buffer[B]) {
+    for (x <- this) dest += x
+  }
+
+  /** Fills the given array <code>xs</code> with at most `len` elements of
+   *  this sequence starting at position `start`.
+   *  Copying will stop oce either the end of the current iterable is reached or
+   *  `len` elements have been copied.
+   *
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param  xs the array to fill.
+   *  @param  start starting index.
+   *  @param  len number of elements to copy
+   *  @pre    the array must be large enough to hold all elements.
+   */
+  def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) {
+    var i = start
+    val end = (start + len) min xs.length
+    for (x <- this) {
+      if (i < end) {
+        xs(i) = x
+        i += 1
+      }
+    }
+  }
+
+  /** Fills the given array <code>xs</code> with the elements of
+   *  this sequence starting at position <code>start</code>
+   *  until either the end of the current iterable or the end of array `xs` is reached.
+   *
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param  xs the array to fill.
+   *  @param  start starting index.
+   *  @pre    the array must be large enough to hold all elements.
+   */
+  def copyToArray[B >: A](xs: Array[B], start: Int) {
+    copyToArray(xs, start, xs.length - start)
+  }
+
+  /** Converts this collection to a fresh Array elements.
+   *  @note  Will not terminate for infinite-sized collections.
+   */
+  def toArray[B >: A]: Array[B] = {
+    var size = 0
+    for (x <- this) size += 1
+    val result = new Array[B](size)
+    copyToArray(result, 0)
+    result
+  }
+
+  /**
+   *  Create a fresh list with all the elements of this iterable object.
+   *  @note Will not terminate for infinite-sized collections.
+   */
+  def toList: List[A] = (new ListBuffer[A] ++ thisCC).toList
+
+  /**
+   *  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]] // !!!
+
+  /** @deprecated use toSequence instead
+   */
+  @deprecated def toSeq: Sequence[A] = toSequence
+
+  /**
+   *  Create a stream which contains all the elements of this iterable object.
+   *  @note consider using <code>projection</code> for lazy behavior.
+   */
+  def toStream: Stream[A] = elements.toStream
+
+  /** Sort the iterable according to the comparison function
+   *  <code>&lt;(e1: a, e2: a) =&gt; Boolean</code>,
+   *  which should be true iff <code>e1</code> is smaller than
+   *  <code>e2</code>.
+   *  The sort is stable. That is elements that are equal wrt `lt` appear in 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
+   *            <code>&lt;(e1: a, e2: a) =&gt; Boolean</code>.
+   *  @ex <pre>
+   *    List("Steve", "Tom", "John", "Bob")
+   *      .sort((e1, e2) => (e1 compareTo e2) &lt; 0) =
+   *    List("Bob", "John", "Steve", "Tom")</pre>
+   *  !!!
+  def sortWith(lt : (A,A) => Boolean): CC[A] = {
+    val arr = toArray
+    Array.sortWith(arr, lt)
+    val b = newBuilder[A]
+    for (x <- arr) b += x
+    b.result
+  }
+  */
+
+  /** Returns a string representation of this iterable object. The resulting string
+   *  begins with the string <code>start</code> and is finished by the string
+   *  <code>end</code>. Inside, the string representations of elements (w.r.t.
+   *  the method <code>toString()</code>) are separated by the string
+   *  <code>sep</code>.
+   *
+   *  @ex  <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param start starting string.
+   *  @param sep separator string.
+   *  @param end ending string.
+   *  @return a string representation of this iterable object.
+   */
+  def mkString(start: String, sep: String, end: String): String =
+    addString(new StringBuilder(), start, sep, end).toString
+
+  /** Returns a string representation of this iterable object. The string
+   *  representations of elements (w.r.t. the method <code>toString()</code>)
+   *  are separated by the string <code>sep</code>.
+   *
+   *  @note Will not terminate for infinite-sized collections.
+   *  @param sep separator string.
+   *  @return a string representation of this iterable object.
+   */
+  def mkString(sep: String): String =
+    addString(new StringBuilder(), sep).toString
+
+  /** Converts a collection into a flat <code>String</code> by each element's toString method.
+   *  @note Will not terminate for infinite-sized collections.
+   */
+  def mkString =
+    addString(new StringBuilder()).toString
+
+  /** Write all elements of this iterable into given string builder.
+   *  The written text begins with the string <code>start</code> and is finished by the string
+   *  <code>end</code>. Inside, the string representations of elements (w.r.t.
+   *  the method <code>toString()</code>) are separated by the string
+   *  <code>sep</code>.
+   *  @note Will not terminate for infinite-sized collections.
+   */
+  def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
+    b append start
+    var first = true
+    for (x <- this) {
+      if (first) first = false
+      else b append sep
+      b append x
+    }
+    b append end
+  }
+
+  /** Write all elements of this string into given string builder.
+   *  The string representations of elements (w.r.t. the method <code>toString()</code>)
+   *  are separated by the string <code>sep</code>.
+   *  @note Will not terminate for infinite-sized collections.
+   */
+  def addString(b: StringBuilder, sep: String): StringBuilder = {
+    var first = true
+    for (x <- this) {
+      if (first) first = false
+      else b append sep
+      b append x
+    }
+    b
+  }
+
+  /** 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
+  }
+
+  /**
+   * returns a projection that can be used to call non-strict <code>filter</code>,
+   * <code>map</code>, and <code>flatMap</code> methods that build projections
+   * of the collection.
+  def projection : Iterable.Projection[A] = new Iterable.Projection[A] {
+    def elements = Iterable.this.elements
+    override def force = Iterable.this
+  }
+   */
+
+  override def toString = mkString(stringPrefix + "(", ", ", ")")
+
+  /** Defines the prefix of this object's <code>toString</code> representation.
+   */
+  def stringPrefix : String = {
+    var string = this.getClass.getName
+    val idx1 = string.lastIndexOf('.' : Int)
+    if (idx1 != -1) string = string.substring(idx1 + 1)
+    val idx2 = string.indexOf('$')
+    if (idx2 != -1) string = string.substring(0, idx2)
+    string
+  }
+
+
+  /** Creates a view of this iterable @see IterableView
+   */
+  def view: IterableView[CC, A] = new IterableView[CC, A] { // !!! Martin: We should maybe infer the type parameters here?
+    val origin = thisCC
+    val elements: Iterator[A] = self.elements
+  }
+
+// The following methods return non-deterministic results, unless this iterable is an OrderedIterable
+
+  /** The first element of this sequence.
+   *
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   *  @throws Predef.NoSuchAentException if the sequence is empty.
+   */
+  def head: A = if (isEmpty) throw new NoSuchElementException else elements.next
+
+   /** @deprecated  use head instead */
+  @deprecated def first: A = head
+
+  /** Returns as an option the first element of this iterable
+   *  or <code>None</code> if iterable is empty.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def headOption: Option[A] = if (isEmpty) None else Some(head)
+
+  /** @deprecated use headOption instead
+   *  <code>None</code> if list is empty.
+   */
+  @deprecated def firstOption: Option[A] = headOption
+
+  /** An iterable consisting of all elements of this iterable
+   *  except the first one.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def tail: CC[A] = drop(1)
+
+  /** Return an iterable consisting only of the first <code>n</code>
+   *  elements of this iterable, or else the whole iterable, if it has less
+   *  than <code>n</code> elements.
+   *
+   *  @param n the number of elements to take
+   *  @return a possibly projected sequence
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def take(n: Int): CC[A] = {
+    val b = newBuilder[A]
+    var i = 0
+    breakable {
+      for (x <- this) {
+        b += x
+        i += 1
+        if (i == n) break
+      }
+    }
+    b.result
+  }
+
+  /** Returns this iterable without its <code>n</code> first elements
+   *  If this iterable has less than <code>n</code> elements, the empty
+   *  iterable is returned.
+   *
+   *  @param n the number of elements to drop
+   *  @return  the new iterable
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def drop(n: Int): CC[A] = {
+    val b = newBuilder[A]
+    var i = 0
+    for (x <- this) {
+      if (i >= n) b += x
+      i += 1
+    }
+    b.result
+  }
+
+  /** A sub-iterable starting at index `from`
+   *  and extending up to (but not including) index `until`.
+   *
+   *  @note c.slice(from, to)  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 <code>from &lt; 0</code>
+   *          or <code>length &lt; from + len<code>
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def slice(from: Int, until: Int): CC[A] = {
+    val b = newBuilder[A]
+    var i = 0
+    breakable {
+      for (x <- this) {
+        if (i >= from) b += x
+        i += 1
+        if (i == until) break
+      }
+    }
+    b.result
+  }
+
+  /** The last element of this iterable.
+   *
+   *  @throws Predef.NoSuchElementException if the sequence is empty.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def last: A = {
+    var lst = head
+    for (x <- this)
+      lst = x
+    lst
+  }
+
+  /** Returns as an option the last element of this iterable or
+   *  <code>None</code> if iterable is empty.
+   *
+   *  @return the last element as an option.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def lastOption: Option[A] = if (isEmpty) None else Some(last)
+
+  /** An iterable consisting of all elements of this iterable except the last one.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def init: CC[A] = {
+    var lst = head
+    val b = newBuilder[A]
+    for (x <- this) {
+      b += lst
+      lst = x
+    }
+    b.result
+  }
+
+  /** Returns the rightmost <code>n</code> elements from this iterable.
+   *
+   *  @param n the number of elements to take
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def takeRight(n: Int): CC[A] = {
+    val b = newBuilder[A]
+    val lead = elements drop n
+    var go = false
+    for (x <- this) {
+      if (go) b += x
+      else if (lead.hasNext) lead.next
+      else go = true
+    }
+    b.result
+  }
+
+  /** Returns the iterable wihtout its rightmost <code>n</code> elements.
+   *
+   *  @param n the number of elements to take
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def dropRight(n: Int): CC[A] = {
+    val b = newBuilder[A]
+    val lead = elements drop n
+    breakable {
+      for (x <- this) {
+        if (!lead.hasNext) break
+        lead.next
+        b += x
+      }
+    }
+    b.result
+  }
+
+  /** Split the iterable at a given point and return the two parts thus
+   *  created.
+   *
+   *  @param n the position at which to split
+   *  @return  a pair of iterables composed of the first <code>n</code>
+   *           elements, and the other elements.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def splitAt(n: Int): (CC[A], CC[A]) = {
+    val l, r = newBuilder[A]
+    var i = 0
+    for (x <- this)
+      (if (i < n) l else r) += x
+    (l.result, r.result)
+  }
+
+  /** Returns the longest prefix of this sequence whose elements satisfy
+   *  the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @return  the longest prefix of this sequence whose elements satisfy
+   *           the predicate <code>p</code>.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def takeWhile(p: A => Boolean): CC[A] = {
+    val b = newBuilder[A]
+    breakable {
+      for (x <- this) {
+        if (!p(x)) break
+        b += x
+      }
+    }
+    b.result
+  }
+
+  /** Returns the longest suffix of this sequence whose first element
+   *  does not satisfy the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @return  the longest suffix of the sequence whose first element
+   *           does not satisfy the predicate <code>p</code>.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def dropWhile(p: A => Boolean): CC[A] = {
+    val b = newBuilder[A]
+    var go = false
+    for (x <- this) {
+      if (go) b += x
+      else if (!p(x)) { go = true; b += x }
+    }
+    b.result
+  }
+
+ /** Returns a pair consisting of the longest prefix of the list whose
+   *  elements all satisfy the given predicate, and the rest of the list.
+   *
+   *  @param p the test predicate
+   *  @return  a pair consisting of the longest prefix of the list whose
+   *           elements all satisfy <code>p</code>, and the rest of the list.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def span(p: A => Boolean): (CC[A], CC[A]) = {
+    val l, r = newBuilder[A]
+    var toLeft = true
+    for (x <- this) {
+      toLeft = toLeft && p(x)
+      (if (toLeft) l else r) += x
+    }
+    (l.result, r.result)
+  }
+
+  /** Checks if the other iterable object contains the same elements as this one.
+   *
+   *  @note will not terminate for infinite-sized iterables.
+   *  @param that  the other iterable
+   *  @return true, iff both iterables contain the same elements.
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   */
+  def sameElements[B >: A](that: OrderedIterable[B]): Boolean = {
+    val these = this.elements
+    val those = that.elements
+    while (these.hasNext && those.hasNext && these.next() == those.next()) {}
+    !these.hasNext && !those.hasNext
+  }
+
+  /** A sub-sequence view  starting at index `from`
+   *  and extending up to (but not including) index `until`.
+   *
+   *  @param from   The index of the first element of the slice
+   *  @param until  The index of the element following the slice
+   *  @note  The difference between `view` and `slice` is that `view` produces
+   *         a view of the current sequence, whereas `slice` produces a new sequence.
+   *
+   *  @note  Might return different results for different runs, unless this iterable is ordered
+   *  @note view(from, to)  is equivalent to view.slice(from, to)
+   */
+  def view(from: Int, until: Int): IterableView[CC, A] = view.slice(from, until)
+}
diff --git a/src/library/scalax/collection/generic/covartest/IterableView.scala b/src/library/scalax/collection/generic/covartest/IterableView.scala
new file mode 100755
index 0000000000..80a455f776
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/IterableView.scala
@@ -0,0 +1,121 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+package scalax.collection.generic.covartest
+
+/** A non-strict projection of an iterable.
+ * @author Sean McDirmid
+ * @author Martin Odersky
+ * @note this should really be a virtual class of SequenceFactory
+ */
+trait IterableView[+UC[+B] <: Iterable[B], +A] extends Iterable[A] { self =>
+
+  val origin: Iterable[_]
+  def elements: Iterator[A]
+
+  val underlying: Iterable[_] = origin match {
+    case v: IterableView[t, _] => v.underlying
+    case _ => origin
+  }
+
+  private def isDelay = elements eq underlying.elements
+
+  private[this] var forced: UC[A] = _
+  private[this] var wasForced = false
+
+  def force: UC[A] = {
+    if (!wasForced) {
+      forced = {
+        val b = underlying.newBuilder[A]
+        for (x <- elements)
+          b += x
+        b.result
+      }.asInstanceOf[UC[A]]
+      wasForced = true
+    }
+    forced
+  }
+
+  def newBuilder[A] = underlying.newBuilder[A]
+
+  /** Builds a new view object. This method needs to be overridden in subclasses
+   *  which refine in IterableView type
+   */
+  protected def newView[B](elems: Iterator[B]) = new IterableView[UC, B] {
+    val origin = if (self.isDelay) self.origin else self
+    val elements = elems
+  }
+
+  /** Non-strict variant of @see IterableLike.++ */
+  override def ++[B >: A](that: Iterator[B]): IterableView[UC, B] = newView(elements ++ that)
+
+  /** Non-strict variant of @see IterableLike.++ */
+  override def ++[B >: A](that: Iterable[B]): IterableView[UC, B] = newView(elements ++ that.elements)
+
+  /** Non-strict variant of @see IterableLike.map */
+  override def map[B](f: A => B): IterableView[UC, B] = newView(elements map f)
+
+  /** Non-strict variant of @see IterableLike.flatMap */
+  override def flatMap[B](f: A => Iterable[B]): IterableView[UC, B] = newView(elements flatMap (f(_).elements))
+
+  /** Non-strict variant of @see IterableLike.filter */
+  override def filter(p: A => Boolean): IterableView[UC, A] = newView(elements filter p)
+
+  /** Non-strict variant of @see IterableLike.partition */
+  override def partition(p: A => Boolean): (IterableView[UC, A], IterableView[UC, A]) = {
+    val (li, ri) = elements partition p
+    (newView(li), newView(ri))
+  }
+
+  /** Non-strict variant of @see IterableLike.zip */
+  override def zip[B](other: Iterable[B]): IterableView[UC, (A, B)] = newView(elements zip other.elements)
+
+  /** Non-strict variant of @see IterableLike.zipWithIndex */
+  override def zipWithIndex: IterableView[UC, (A, Int)] = newView(elements.zipWithIndex)
+
+  /* Non-strict variant of @see IterableLike.zipAll
+   *  This is not enabled because it can't be specialized in VectorView:
+   *  VectorView is not covariant, yet must maintain updatability. Impossible to do this
+   *  with this type signature.
+  override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): IterableView[UC, (A1, B1)] =
+    newView(elements zipAll (that.elements, thisElem, thatElem))
+   */
+
+  /** Non-strict variant of @see Iterable.take */
+  override def take(n: Int): IterableView[UC, A] = newView(elements take n)
+
+  /** Non-strict variant of @see Iterable.drop */
+  override def drop(n: Int): IterableView[UC, A] = newView(elements drop n)
+
+  /** Non-strict variant of @see Iterable.splitAt */
+  override def splitAt(n: Int): (IterableView[UC, A], IterableView[UC, A]) = (take(n), drop(n))
+
+  /** Non-strict variant of @see Iterable.slice */
+  override def slice(from: Int, until: Int): IterableView[UC, A] = newView(elements slice (from, until))
+
+  /** Non-strict variant of @see Iterable.takeWhile */
+  override def takeWhile(p: A => Boolean): IterableView[UC, A] = newView(elements takeWhile p)
+
+  /** Non-strict variant of @see Iterable.dropWhile */
+  override def dropWhile(p: A => Boolean): IterableView[UC, A] = newView(elements dropWhile p)
+
+  /** Non-strict variant of @see Iterable.span */
+  override def span(p: A => Boolean): (IterableView[UC, A], IterableView[UC, A]) = (takeWhile(p), dropWhile(p))
+
+  /** The projection resulting from the concatenation of this projection with the <code>rest</code> projection.
+   *  @param rest   The projection that gets appended to this projection
+   *  @deprecated   Use ++ instead
+   */
+  @deprecated def append[B >: A](rest : => Iterable[B]): IterableView[UC, B] = this ++ rest.elements
+
+  override def stringPrefix = origin.stringPrefix+"V"
+
+
+}
diff --git a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala
new file mode 100755
index 0000000000..c6be1a5acd
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala
@@ -0,0 +1,17 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
+
+
+package scalax.collection.generic.covartest
+
+import OrderedIterable._
+
+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
new file mode 100755
index 0000000000..1fb85d02db
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/SequenceFactory.scala
@@ -0,0 +1,11 @@
+package scalax.collection.generic.covartest
+
+trait SequenceFactory[CC[A] <: Sequence[A]] extends IterableFactory[CC] {
+
+  /** This method is called in a pattern match { case Sequence(...) => }.
+   *
+   *  @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)
+}
diff --git a/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala
new file mode 100755
index 0000000000..bf1915edf0
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala
@@ -0,0 +1,382 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Sequence.scala 16092 2008-09-12 10:37:06Z nielsen $
+
+
+package scalax.collection.generic.covartest
+
+import util.control.Break._
+import scalax.collection.immutable.{List, Nil, ::}
+
+import Sequence._
+
+trait SequenceTemplate[+CC[+B] <: SequenceTemplate[CC, B] with Sequence[B], +A] extends PartialFunction[Int, A] with OrderedIterableTemplate[CC, A] {
+self /*: CC[A]*/ =>
+
+  /** Returns the length of the sequence.
+   *
+   *  @return the sequence length.
+   */
+  def length: Int
+
+  /** Result of comparing <code>length</code> with operand <code>len</code>.
+   *  returns <code>x</code> where
+   *  <code>x &lt; 0</code>    iff    <code>this.length &lt; len</code>
+   *  <code>x == 0</code>   iff    <code>this.length == len</code>
+   *  <code>x &gt; 0</code>    iff    <code>this.length &gt; len</code>.
+   *
+   *  The method as implemented here does not call length directly; its running time
+   *  is O(length min len) instead of O(length). The method should be overwritten
+   *  if computing length is cheap.
+   */
+  def lengthCompare(len: Int): Int =  {
+    var i = 0
+    breakable {
+      for (_ <- this) {
+        i += 1
+        if (i > len) break
+      }
+    }
+    i - len
+  }
+
+  /** Should always be <code>length</code> */
+  def size = length
+
+  /** Is this partial function defined for the index <code>x</code>?
+   */
+  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.
+   *  @param  p the predicate
+   *  @param  from  the start index
+   */
+  def segmentLength(p: A => Boolean, from: Int): Int = {
+    var result = 0
+    var i = from
+    breakable {
+      for (x <- this) {
+        if (i >= from && !p(x)) { result = i - from; break }
+        else i += 1
+      }
+    }
+    result
+  }
+
+  /** Returns length of longest prefix of this seqence
+   *  such that every element of the prefix satisfies predicate `p`.
+   *  @note may not terminate for infinite-sized collections.
+   *  @param  p the predicate
+   */
+  def prefixLength(p: A => Boolean) = segmentLength(p, 0)
+
+  /** 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 collections.
+   *  @param  p the predicate
+   *  @param  from  the start index
+   */
+  def indexWhere(p: A => Boolean, from: Int): Int = {
+    var result = -1
+    var i = from
+    breakable {
+      for (x <- this) {
+        if (i >= from && p(x)) { result = i; break }
+        else i += 1
+      }
+    }
+    result
+  }
+
+  /** Returns index of the first element satisying a predicate, or -1.
+   *
+   *  @deprecated  Use `indexWhere` instead
+   */
+  @deprecated def findIndexOf(p: A => Boolean): Int = indexWhere(p)
+
+  /** Returns the index of the first occurence of the specified
+   *  object in this iterable object.
+   *
+   *  @note may not terminate for infinite-sized collections.
+   *  @param  elem  element to search for.
+   *  @return the index in this sequence of the first occurence of the
+   *          specified element, or -1 if the sequence does not contain
+   *          this element.
+   */
+  def indexOf[B >: A](elem: B): Int = indexOf(elem, 0)
+
+  /** Returns the index of the first occurence of the specified
+   *  object in this iterable object,  starting from a start index, or
+   *  -1, if none exists.
+   *
+   *  @note may not terminate for infinite-sized collections.
+   *  @param  elem  element to search for.
+   */
+  def indexOf[B >: A](elem: B, from: Int): Int = indexWhere(elem ==, from)
+
+ /** Returns the index of the last occurence of the specified element
+   *  in this sequence, or -1 if the sequence does not contain this element.
+   *
+   *  @param  elem   element to search for.
+   *  @return the index in this sequence of the last occurence of the
+   *          specified element, or -1 if the sequence does not contain
+   *          this element.
+   */
+  def lastIndexOf[B >: A](elem: B): Int = lastIndexOf(elem, length - 1)
+
+  /** Returns the index of the last
+    *  occurence of the specified element in this sequence
+    *  before or at a given end index,
+    *  or -1 if the sequence does not contain this element.
+    *
+    *  @param  elem   element to search for.
+    *  @param  end    the end index
+    */
+  def lastIndexOf[B >: A](elem: B, end: Int): Int = {
+    var i = end
+    val it = reversedElements
+    while (it.hasNext && it.next != elem) i -= 1
+    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 <code>p</code>,
+   *            or -1 if such an element does not exist
+   */
+  def lastIndexWhere(p: A => Boolean): Int = lastIndexWhere(p, length - 1)
+
+  /** Returns index of the last element not exceeding a given end index
+   *  and satisying a predicate, or -1 if none exists.
+   *
+   *  @param  end the end index
+   *  @param  p the predicate
+   */
+  def lastIndexWhere(p: A => Boolean, end: Int): Int = {
+    var i = end
+    val it = reversedElements
+    while (it.hasNext && (i > end || !p(it.next))) i -= 1
+    i
+  }
+
+  /** A sequence of type <code>C</code> consisting of all elements of
+   *  this sequence in reverse order.
+   *  @note  the operation is implemented by building a new sequence
+   *         from <code>this(length - 1), ..., this(0)</code>
+   *  If random access is inefficient for the given sequence implementation,
+   *  this operation should be overridden.
+   */
+  def reverse: CC[A] = {
+    var xs: List[A] = List()
+    for (x <- this)
+      xs = x :: xs
+    val b = newBuilder[A]
+    for (x <- xs)
+      b += x
+    b.result
+  }
+
+  /** The elements of this sequence in reversed order
+   */
+  def reversedElements: Iterator[A] = reverse.elements
+
+  /**
+   * Checks whether the argument sequence is contained at the
+   * specified index within the receiver object.
+   *
+   * If the both the receiver object, <code>this</code> and
+   * the argument, <code>that</code> are infinite sequences
+   * this method may not terminate.
+   *
+   * @return true if <code>that</code> is contained in
+   * <code>this</code>, at the specified index, otherwise false
+   *
+   * @see String.startsWith
+   */
+  def startsWith[B](that: Sequence[B], offset: Int): Boolean = {
+    val i = elements.drop(offset)
+    val j = that.elements
+    while (j.hasNext && i.hasNext && i.next == j.next) {}
+    !j.hasNext
+  }
+
+  /**
+   * Check whether the receiver object starts with the argument sequence.
+   *
+   * @return true if <code>that</code> is a prefix of <code>this</code>,
+   * otherwise false
+   *
+   * @see Sequence.startsWith
+   */
+  def startsWith[B](that: Sequence[B]): Boolean = startsWith(that, 0)
+
+  /** @return true if this sequence end with that sequence
+   *  @see String.endsWith
+   */
+  def endsWith[B](that: Sequence[B]): Boolean = {
+    val i = this.elements.drop(length - that.length)
+    val j = that.elements
+    while (i.hasNext && j.hasNext && i.next == j.next) ()
+    !j.hasNext
+  }
+
+  /** @return -1 if <code>that</code> not contained in this, otherwise the
+   *  index where <code>that</code> is contained
+   *  @see String.indexOf
+   */
+  def indexOf[B >: A](that: Sequence[B]): Int = {
+    var i = 0
+    var s: Sequence[A] = thisCC
+    while (!s.isEmpty && !(s startsWith that)) {
+      i += 1
+      s = s drop 1
+    }
+    if (!s.isEmpty || that.isEmpty) i else -1
+  }
+
+  /** Tests if the given value <code>elem</code> is a member of this
+   *  sequence.
+   *
+   *  @param elem element whose membership has to be tested.
+   *  @return     <code>true</code> iff there is an element of this sequence
+   *              which is equal (w.r.t. <code>==</code>) to <code>elem</code>.
+   */
+  def contains(elem: Any): Boolean = exists (_ == elem)
+
+  /** Computes the union of this sequence and the given sequence
+   *  <code>that</code>.
+   *
+   *  @param that the sequence of elements to add to the sequence.
+   *  @return     an sequence containing the elements of this
+   *              sequence and those of the given sequence <code>that</code>
+   *              which are not contained in this sequence.
+   */
+  def union[B >: A](that: Sequence[B]): CC[B] = this ++ (that diff thisCC)
+
+  /** Computes the difference between this sequence and the given sequence
+   *  <code>that</code>.
+   *
+   *  @param that the sequence of elements to remove from this sequence.
+   *  @return     this sequence without the elements of the given sequence
+   *              <code>that</code>.
+   */
+  def diff[B >: A](that: Sequence[B]): CC[A] = this remove (that contains _)
+
+  /** Computes the intersection between this sequence and the given sequence
+   *  <code>that</code>.
+   *
+   *  @param that the sequence to intersect.
+   *  @return     the sequence of elements contained both in this sequence and
+   *              in the given sequence <code>that</code>.
+   */
+  def intersect[B >: A](that: Sequence[B]): CC[A] = this filter(that contains _)
+
+  /** Builds a new sequence from this sequence in which any duplicates (wrt to ==) removed.
+   *  Among duplicate elements, only the first one is retained in the result sequence
+   */
+  def removeDuplicates: CC[A] = {
+    val b = newBuilder[A]
+    var seen = Set[A]()
+    for (x <- this) {
+      if (!(seen contains x)) {
+        b += x
+        seen += x
+      }
+    }
+    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.
+   */
+  def padTo[B >: A](len: Int, elem: B): CC[B] = {
+    var diff = len - length
+    val b = newBuilder[B] //!!! drop [B] and get surprising results!
+    b ++= thisCC
+    while (diff > 0) {
+      b += elem
+      diff -=1
+    }
+    b.result
+  }
+
+  /**
+   *  Overridden for efficiency.
+   *
+   *  @return  the sequence itself
+   */
+  override def toSequence: Sequence[A] = this.asInstanceOf[Null] // !!!
+
+  def indices: Range = 0 until length
+
+  /** Creates a view of this iterable @see OrderedIterable.View
+   */
+  override def view: SequenceView[CC, A] = new SequenceView[CC, A] { // !!! Martin: We should maybe infer the type parameters here?
+    val origin: Sequence[_] = thisCC
+    val elements: Iterator[A] = self.elements
+    val length: Int = self.length
+    def apply(idx: Int): A = self.apply(idx)
+  }
+
+  /** A sub-sequence view  starting at index `from`
+   *  and extending up to (but not including) index `until`.
+   *
+   *  @param from   The index of the first element of the slice
+   *  @param until  The index of the element following the slice
+   *  @note  The difference between `view` and `slice` is that `view` produces
+   *         a view of the current sequence, whereas `slice` produces a new sequence.
+   *
+   *  @note view(from, to)  is equivalent to view.slice(from, to)
+   */
+  override def view(from: Int, until: Int): SequenceView[CC, A] = view.slice(from, until)
+
+  /** Returns index of the last element satisying a predicate, or -1.
+   *  @deprecated use `lastIndexWhere` instead
+   */
+  @deprecated def findLastIndexOf(p: A => Boolean): Int = lastIndexWhere(p)
+
+  /** A sub-sequence starting at index <code>from</code>
+    *  and extending up to the length of the current sequence
+    *
+    *  @param from   The index of the first element of the slice
+    *  @throws IndexOutOfBoundsException if <code>from &lt; 0</code>
+    *  @deprecated   use <code>drop</code> instead
+    */
+  @deprecated def slice(from: Int): Sequence[A] = slice(from, length)
+
+  /** @deprecated Should be replaced by
+   *
+   *   <code>(s1, s2) forall { case (x, y) => f(x, y) }</code>
+   */
+  @deprecated def equalsWith[B](that: Sequence[B])(f: (A,B) => Boolean): Boolean = {
+    val i = this.elements
+    val j = that.elements
+    while (i.hasNext && j.hasNext && f(i.next, j.next)) ()
+    !i.hasNext && !j.hasNext
+  }
+
+  /** Is <code>that</code> a slice in this?
+   *  @deprecated  Should be repaced by <code>indexOf(that) != -1</code>
+   */
+  @deprecated def containsSlice[B](that: Sequence[B]): Boolean = indexOf(that) != -1
+
+}
diff --git a/src/library/scalax/collection/generic/covartest/SequenceView.scala b/src/library/scalax/collection/generic/covartest/SequenceView.scala
new file mode 100755
index 0000000000..48477cf6e7
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/SequenceView.scala
@@ -0,0 +1,129 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Sequence.scala 16092 2008-09-12 10:37:06Z nielsen $
+
+
+package scalax.collection.generic.covartest
+
+import util.control.Break._
+import annotation.unchecked.uncheckedVariance
+
+import Sequence._
+
+/** A non-strict projection of an iterable.
+ * @author Sean McDirmid
+ * @author Martin Odersky
+ * @note this should really be a virtual class of SequenceFactory
+ */
+trait SequenceView[+UC[+B] <: Sequence[B], +A] extends IterableView[UC, A] with Sequence[A] {
+self =>
+
+  /** refined from Iterable.View */
+  val origin: Sequence[_]
+
+  trait Transformed[+B] extends SequenceView[UC, B] {
+    val origin = self
+    protected def asCC = asInstanceOf[SequenceView[UC, B]]
+  }
+
+  class Appended[+B >: A](that: Sequence[B]) extends Transformed[B] {
+    override def elements: Iterator[B] = self.elements ++ that.elements
+    override def length: Int = self.length + that.length
+    override def apply(idx: Int): B = {
+      val ll = self.length
+      if (idx < ll) self.apply(idx) else that.apply(idx - ll)
+    }
+    override def stringPrefix = self.stringPrefix + "A"
+  }
+
+  class Sliced(from: Int, to: Int) extends Transformed[A] {
+    override def elements: Iterator[A] = self.elements slice (from, to)
+    override lazy val length: Int = ((to min self.length) - (from max 0) min 0)
+    override def apply(idx: Int): A =
+      if (idx >= 0 && idx < length) self.apply(idx + from)
+      else throw new IndexOutOfBoundsException(idx.toString)
+    override def stringPrefix = self.stringPrefix + "S"
+    override def slice(from1: Int, to1: Int) =
+      new self.Sliced(from + (from1 min length max 0) , to + (to1 min length max 0)).asInstanceOf[SequenceView[UC, A]]
+  }
+
+  class Mapped[+B](f: A => B) extends Transformed[B] {
+    override def elements: Iterator[B] = self.elements map f
+    override def length: Int = self.length
+    override def apply(idx: Int): B = f(self.apply(idx))
+    override def stringPrefix = self.stringPrefix + "M"
+  }
+
+  class Reversed extends Transformed[A] {
+    override def elements: Iterator[A] = self.reversedElements
+    override def length: Int = self.length
+    override def apply(idx: Int): A = self.apply(length - 1 - idx)
+    override def stringPrefix = super.stringPrefix+"R"
+  }
+
+  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 length: Int = self.length + plen - replaced
+    override def apply(idx: Int): B =
+      if (idx < from) self.apply(idx)
+      else if (idx < from + plen) patch.apply(idx - from)
+      else self.apply(idx - plen + replaced)
+    override def stringPrefix = super.stringPrefix+"P"
+  }
+
+  class Zipped[+B](that: Sequence[B]) extends Transformed[(A, B)] {
+    override def elements: Iterator[(A, B)] = self.elements zip that.elements
+    override def length = self.length min that.length
+    override def apply(idx: Int): (A, B) = (self.apply(idx), that.apply(idx))
+    override def stringPrefix = super.stringPrefix+"Z"
+  }
+
+  override def ++[B >: A](that: Iterable[B]): SequenceView[UC, B] =
+    new Appended[B](that.toSequence).asCC
+  override def ++[B >: A](that: Iterator[B]): SequenceView[UC, B] =
+    new Appended[B](that.toSequence).asCC
+  override def map[B](f: A => B): SequenceView[UC, B] =
+    new Mapped(f).asCC
+  override def reverse: SequenceView[UC, A] =
+    (new Reversed).asCC
+  def patch[B >: A](from: Int, patch: Sequence[B], replaced: Int): SequenceView[UC, B] =
+    if (0 <= from && from < length) new Patched(from, patch, replaced).asCC
+    else throw new IndexOutOfBoundsException(from.toString)
+  override def padTo[B >: A](len: Int, elem: B): SequenceView[UC, B] =
+    patch(length, fill((len - length) max 0, elem), 0)
+  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]) // !!!
+    /*
+  override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): SequenceView[UC, (A1, B1)] = {
+    val that1 = that.toSequence
+    self.padTo(that1.length, thisElem) zip that1.padTo(this.length, thatElem)//.asInstanceOf[SequenceView[UC, (A1, B1)]]
+  }*/
+  override def take(n: Int): SequenceView[UC, A] =
+    slice(0, n)
+  override def drop(n: Int): SequenceView[UC, A] =
+    slice(n, Math.MAX_INT)
+  override def splitAt(n: Int): (SequenceView[UC, A], SequenceView[UC, A]) = (take(n), drop(n))
+  override def slice(from: Int, until: Int): SequenceView[UC, A] =
+    new Sliced(from, until).asCC
+  override def takeWhile(p: A => Boolean): SequenceView[UC, A] =
+    take(prefixLength(p))
+  override def dropWhile(p: A => Boolean): SequenceView[UC, A] =
+    drop(prefixLength(p))
+  override def span(p: A => Boolean): (SequenceView[UC, A], SequenceView[UC, A]) = {
+    val n = prefixLength(p)
+    (take(n), drop(n))
+  }
+
+  // missing here because we can't do anything about them, so we fall back to default construction
+  // if an IterableView via newView: flatMap, filter, partition
+}
+
diff --git a/src/library/scalax/collection/generic/covartest/VectorTemplate.scala b/src/library/scalax/collection/generic/covartest/VectorTemplate.scala
new file mode 100644
index 0000000000..0771b078d9
--- /dev/null
+++ b/src/library/scalax/collection/generic/covartest/VectorTemplate.scala
@@ -0,0 +1,264 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2006-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Vector.scala 15437 2008-06-25 16:22:45Z stepancheg $
+
+package scalax.collection.generic.covartest
+
+import Vector._
+
+/** Sequences that support O(1) element access and O(1) length computation.
+ *  @author Sean McDirmid
+ *  @author Martin Odersky
+ *  @version 2.8
+ */
+trait VectorTemplate[+CC[+B] <: VectorTemplate[CC, B] with Vector[B], +A] extends SequenceTemplate[CC, A] {
+self =>
+
+  // Overridden methods from IterableTemplate
+
+  /** The iterator returned by the elements method
+   */
+  protected class Elements(start: Int, end: Int) extends scalax.collection.BufferedIterator[A] {
+    var i = start
+    def hasNext: Boolean = i < end
+    def next: A =
+      if (i < end) {
+        val x = self(i)
+        i += 1
+        x
+      } else Iterator.empty.next
+    def head =
+      self(i)
+    /** drop is overridden to enable fast searching in the middle of random access sequences */
+    override def drop(n: Int): Iterator[A] =
+      if (n > 0) new Elements(start + n, end) else this
+    /**  is overridden to be symmetric to drop */
+    override def take(n: Int): Iterator[A] =
+      if (n < 0) Iterator.empty.buffered
+      else if (start + n < end) new Elements(start, start + n)
+      else this
+  }
+
+  override def elements: Iterator[A] = new Elements(0, length)
+
+  override def isEmpty: Boolean = { length == 0 }
+
+  override def foreach(f: A => Unit): Unit = {
+    var i = 0
+    val len = length
+    while (i < len) { f(this(i)); i += 1 }
+  }
+
+  override def forall(p: A => Boolean): Boolean = prefixLength(p(_)) == length
+  override def exists(p: A => Boolean): Boolean = prefixLength(!p(_)) != length
+
+  override def find(p: A => Boolean): Option[A] = {
+    val i = prefixLength(!p(_))
+    if (i < length) Some(this(i)) else None
+  }
+
+  private def foldl[B](start: Int, z: B, op: (B, A) => B): B = {
+    var i = start
+    val len = length
+    var result = z
+    while (i < len) {
+      result = op(result, this(i))
+      i += 1
+    }
+    result
+  }
+
+  private def foldr[B](start: Int, len: Int, z: B, op: (A, B) => B): B =
+    if (start == len) z
+    else op(this(start), foldr(start + 1, len, z, op))
+
+  override def foldLeft[B](z: B)(op: (B, A) => B): B = foldl(0, z, op)
+  override def foldRight[B](z: B)(op: (A, B) => B): B = foldr(0, length, z, op)
+  override def reduceLeft[B >: A](op: (B, A) => B): B =
+    if (length > 0) foldl(0, this(0), op) else super.reduceLeft(op)
+  override def reduceRight[B >: A](op: (A, B) => B): B =
+    if (length > 0) foldr(0, length - 1, this(length - 1), op) else super.reduceRight(op)
+
+  override def zip[B](that: Iterable[B]): CC[(A, B)] = that match {
+    case that: Vector[_] =>
+      var i = 0
+      val len = this.length min that.length
+      val b = this.newBuilder[(A, B)]
+      while (i < len) {
+        b += ((this(i), that(i).asInstanceOf[B]))
+        i += 1
+      }
+      b.result
+    case _ =>
+      super.zip(that)
+  }
+
+  override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): CC[(A1, B1)] = that match {
+    case that: Vector[_] =>
+      var i = 0
+      val len = this.length min that.length
+      val b = this.newBuilder[(A1, B1)]
+      while (i < len) {
+        b += ((this(i), that(i).asInstanceOf[B]))
+        i += 1
+      }
+      while (i < this.length) {
+        b += ((this(i), thatElem))
+        i += 1
+      }
+      while (i < that.length) {
+        b += ((this(i), thatElem.asInstanceOf[B]))
+        i += 1
+      }
+      b.result
+    case _ =>
+      super.zipAll(that, thisElem, thatElem)
+  }
+
+  override def zipWithIndex: CC[(A, Int)] = {
+    val b = newBuilder[(A, Int)]
+    var i = 0
+    val len = length
+    while (i < len) {
+      b += ((this(i), i))
+      i += 1
+    }
+    b.result
+  }
+
+  override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) {
+    var i = 0
+    var j = start
+    val end = length min len min (xs.length - start)
+    while (i < end) {
+      xs(j) = this(i)
+      i += 1
+      j += 1
+    }
+  }
+
+  // Overridden methods from OrderedIterableTemplate
+
+  override def head: A = if (isEmpty) throw new NoSuchElementException else this(0)
+
+  override def slice(from: Int, until: Int): CC[A] = {
+    val b = newBuilder[A]
+    var i = from max 0
+    val end = until min length
+    while (i < end) {
+      b += this(i)
+      i += 1
+    }
+    b.result
+  }
+
+  override def take(n: Int): CC[A] = slice(0, n)
+  override def drop(n: Int): CC[A] = slice(n, length)
+  override def takeRight(n: Int): CC[A] = slice(length - n, length)
+  override def dropRight(n: Int): CC[A] = slice(0, length - n)
+  override def splitAt(n: Int): (CC[A], CC[A]) = (take(n), drop(n))
+  override def takeWhile(p: A => Boolean): CC[A] = take(prefixLength(p))
+  override def dropWhile(p: A => Boolean): CC[A] = drop(prefixLength(p))
+  override def span(p: A => Boolean): (CC[A], CC[A]) = splitAt(prefixLength(p))
+  override def last: A = if (length > 0) this(length - 1) else super.last
+  override def init: CC[A] = if (length > 0) slice(0, length - 1) else super.init
+
+  override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = that match {
+    case that: Vector[_] =>
+      val len = length
+      len == that.length && {
+        var i = 0
+        while (i < len && this(i) == that(i)) i += 1
+        i == len
+      }
+    case _ =>
+      super.sameElements(that)
+  }
+
+  // Overridden methods from Sequence
+
+  override def lengthCompare(len: Int): Int = length - len
+
+  private def negLength(n: Int) = if (n == length) -1 else n
+
+  override def indexWhere(p: A => Boolean, from: Int): Int =
+    negLength(from + segmentLength(!p(_), from))
+
+  override def lastIndexWhere(p: A => Boolean, end: Int): Int = {
+    var i = end
+    while (i >= 0 && !p(this(i))) i -= 1
+    i
+  }
+
+  override def lastIndexOf[B >: A](elem: B, end: Int): Int = lastIndexWhere(elem ==, end)
+
+  override def reverse: CC[A] = {
+    val b = newBuilder[A]
+    var i = length
+    while (0 < i) {
+      i -= 1
+      b += this(i)
+    }
+    b.result
+  }
+
+  override def reversedElements = new Iterator[A] {
+    var i = length
+    def hasNext: Boolean = 0 < i
+    def next: A =
+      if (0 < i) {
+        i -= 1
+        self(i)
+      } else Iterator.empty.next
+  }
+
+  override def startsWith[B](that: Sequence[B], offset: Int): Boolean = that match {
+    case that: Vector[_] =>
+      var i = offset
+      var j = 0
+      val thisLen = length
+      val thatLen = that.length
+      while (i < thisLen && j < thatLen && this(i) == that(j)) {
+        i += 1
+        j += 1
+      }
+      j == thatLen
+    case _ =>
+      var i = offset
+      val thisLen = length
+      val thatElems = that.elements
+      while (i < thisLen && thatElems.hasNext && this(i) == thatElems.next) {
+        i += 1
+      }
+      !thatElems.hasNext
+  }
+
+  override def endsWith[B](that: Sequence[B]): Boolean = that match {
+    case that: Vector[_] =>
+      val thisLen = length
+      val thatLen = that.length
+      var i = thisLen - 1
+      var j = thatLen - 1
+      while (i >= 0 && j >= 0 && this(i) == that(j)) {
+        i -= 1
+        j -= 1
+      }
+      j == 0
+    case _ =>
+      super.endsWith(that)
+  }
+
+  override def indexOf[B >: A](that: Sequence[B]): Int = {
+    var i = 0
+    val last = length - that.length
+    while (i <= last && !startsWith(that, i)) i += 1
+    negLength(i)
+  }
+}
+