initial collection library fragments

9 files changed, 2290 insertions, 0 deletions

diff --git a/src/library/scalax/Fractional.scala b/src/library/scalax/Fractional.scala
new file mode 100755
index 0000000000..b29a903519
--- /dev/null
+++ b/src/library/scalax/Fractional.scala
@@ -0,0 +1,5 @@
+package scalax
+
+trait Fractional[T] extends Numeric[T] {
+  def div(x: T, y: T): T
+}
diff --git a/src/library/scalax/Integral.scala b/src/library/scalax/Integral.scala
new file mode 100755
index 0000000000..2e80b1bb7b
--- /dev/null
+++ b/src/library/scalax/Integral.scala
@@ -0,0 +1,6 @@
+package scalax
+
+trait Integral[T] extends Numeric[T] {
+  def quot(x: T, y: T): T
+  def rem(x: T, y: T): T
+}
diff --git a/src/library/scalax/Numeric.scala b/src/library/scalax/Numeric.scala
new file mode 100755
index 0000000000..6e61851dc5
--- /dev/null
+++ b/src/library/scalax/Numeric.scala
@@ -0,0 +1,79 @@
+package scalax
+
+object Numeric {
+  implicit object IntIsIntegral extends Integral[Int] {
+    def plus(x: Int, y: Int): Int = x + y
+    def minus(x: Int, y: Int): Int = x - y
+    def times(x: Int, y: Int): Int = x * y
+    def quot(x: Int, y: Int): Int = x / y
+    def rem(x: Int, y: Int): Int = x % y
+    def negate(x: Int): Int = -x
+    def abs(x: Int): Int = if (x < 0) -x else x
+    def signum(x: Int): Int = if (x < 0) -1 else if (x > 0) 1 else 0
+    def fromInt(x: Int): Int = x
+    def toInt(x: Int): Int = x
+    def toLong(x: Int): Long = x
+    def toFloat(x: Int): Float = x
+    def toDouble(x: Int): Double = x
+  }
+  implicit object LongIsIntegral extends Integral[Long] {
+    def plus(x: Long, y: Long): Long = x + y
+    def minus(x: Long, y: Long): Long = x - y
+    def times(x: Long, y: Long): Long = x * y
+    def quot(x: Long, y: Long): Long = x / y
+    def rem(x: Long, y: Long): Long = x % y
+    def negate(x: Long): Long = -x
+    def abs(x: Long): Long = if (x < 0) -x else x
+    def signum(x: Long): Long = if (x < 0) -1 else if (x > 0) 1 else 0
+    def fromInt(x: Int): Long = x
+    def toInt(x: Long): Int = x.toInt
+    def toLong(x: Long): Long = x
+    def toFloat(x: Long): Float = x
+    def toDouble(x: Long): Double = x
+  }
+  implicit object FloatIsFractional extends Fractional[Float] {
+    def plus(x: Float, y: Float): Float = x + y
+    def minus(x: Float, y: Float): Float = x - y
+    def times(x: Float, y: Float): Float = x * y
+    def div(x: Float, y: Float): Float = x / y
+    def negate(x: Float): Float = -x
+    def abs(x: Float): Float = if (x < 0) -x else x
+    def signum(x: Float): Float = if (x < 0) -1 else if (x > 0) 1 else 0
+    def fromInt(x: Int): Float = x
+    def toInt(x: Float): Int = x.toInt
+    def toLong(x: Float): Long = x.toLong
+    def toFloat(x: Float): Float = x
+    def toDouble(x: Float): Double = x
+  }
+  implicit object DoubleIsFractional extends Fractional[Double] {
+    def plus(x: Double, y: Double): Double = x + y
+    def minus(x: Double, y: Double): Double = x - y
+    def times(x: Double, y: Double): Double = x * y
+    def div(x: Double, y: Double): Double = x / y
+    def negate(x: Double): Double = -x
+    def abs(x: Double): Double = if (x < 0) -x else x
+    def signum(x: Double): Double = if (x < 0) -1 else if (x > 0) 1 else 0
+    def fromInt(x: Int): Double = x
+    def toInt(x: Double): Int = x.toInt
+    def toLong(x: Double): Long = x.toLong
+    def toFloat(x: Double): Float = x.toFloat
+    def toDouble(x: Double): Double = x
+  }
+}
+
+
+trait Numeric[T] {
+  def plus(x: T, y: T): T
+  def minus(x: T, y: T): T
+  def times(x: T, y: T): T
+  def negate(x: T): T
+  def abs(x: T): T
+  def signum(x: T): T
+  def fromInt(x: Int): T
+  def toInt(x: T): Int
+  def toLong(x: T): Long
+  def toFloat(x: T): Float
+  def toDouble(x: T): Double
+  def zero = fromInt(0)
+  def one = fromInt(1)
+}
diff --git a/src/library/scalax/collection/BufferedIterator.scala b/src/library/scalax/collection/BufferedIterator.scala
new file mode 100755
index 0000000000..07509c2758
--- /dev/null
+++ b/src/library/scalax/collection/BufferedIterator.scala
@@ -0,0 +1,27 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: BufferedIterator.scala 12641 2007-08-22 16:01:57Z mcdirmid $
+
+
+package scalax.collection
+
+/** Buffered iterators are iterators which allow to inspect the next
+ *  element without discarding it.
+ *
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+trait BufferedIterator[+A] extends Iterator[A] {
+
+  /** Returns current element of iterator without advancing beyond it.
+   */
+  def head: A
+
+  override def buffered: this.type = this
+}
diff --git a/src/library/scalax/collection/Builder.scala b/src/library/scalax/collection/Builder.scala
new file mode 100755
index 0000000000..c6ba104c4d
--- /dev/null
+++ b/src/library/scalax/collection/Builder.scala
@@ -0,0 +1,19 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     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
+
+
+trait Builder[+C[B], A] extends Iterable[A] {
+  def +=(x: A)
+  def ++=(xs: Iterator[A])
+  def ++=(xs: Iterable[A])
+  def result: C[A]
+}
diff --git a/src/library/scalax/collection/Iterable.scala b/src/library/scalax/collection/Iterable.scala
new file mode 100755
index 0000000000..0ffcdea1a5
--- /dev/null
+++ b/src/library/scalax/collection/Iterable.scala
@@ -0,0 +1,1063 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     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
+
+import scala.collection.mutable.{Buffer, ArrayBuffer, ListBuffer}
+import util.control.Break._
+
+/** Various utilities for instances of <a href="Iterable.html">Iterable</a>.
+ *
+ *  @author  Matthias Zenger
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+object Iterable extends SeqFactory[Iterable] {
+
+  type IterableOf[+C[+B] <: Iterable[B], A] = Iterable[A] { type CC[+B] = C[B] }
+
+  /** The empty iterable */
+  val empty = new Iterable[Nothing] {
+    type CC[+B] = Iterable[B]
+    def elements = Iterator.empty
+    def newBuilder[B]: Builder[Iterable, B] = null // !!!
+  }
+
+  class OrderedIterableOps[A](seq: Iterable[A], cmp: Ordering[A]) {
+    def min: A = {
+      require(!seq.isEmpty, "min(<empty>)")
+      var acc = seq.first
+      for (x <- seq)
+        if (cmp.lt(x, acc)) acc = x
+      acc
+    }
+    def max: A = {
+      require(!seq.isEmpty, "max(<empty>)")
+      var acc = seq.first
+      for (x <- seq)
+        if (cmp.gt(x, acc)) acc = x
+      acc
+    }
+  }
+
+  class NumericIterableOps[A](seq: Iterable[A], num: Numeric[A]) {
+    def sum: A = {
+      var acc = num.zero
+      for (x <- seq) acc = num.plus(acc, x)
+      acc
+    }
+    def product: A = {
+      var acc = num.one
+      for (x <- seq) acc = num.times(acc, x)
+      acc
+    }
+  }
+
+  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]]
+      for ((a, b) <- self) {
+        as += a
+        bs += b
+      }
+      (as.result, bs.result)
+    }
+  }
+
+  class IterableIterableOps[C[+B] <: Iterable[B], A](self: C[Iterable[A]]) {
+    def flatten: C[A] = {
+      val b = self.newBuilder[A].asInstanceOf[Builder[C, A]]
+      for (xs <- self)
+        b ++= xs
+      b.result
+    }
+  }
+
+  implicit def orderedIterableWrapper[A](seq: Iterable[A])(implicit cmp: Ordering[A]) =
+    new OrderedIterableOps(seq, cmp)
+  implicit def numericIterableWrapper[A](seq: Iterable[A])(implicit num: Numeric[A]) =
+    new NumericIterableOps(seq, num)
+  implicit def pairIterableWrapper[C[+B] <: Iterable[B], A1, A2](seq: C[(A1, A2)]) =
+    new PairIterableOps[C, A1, A2](seq)
+  implicit def iterableIterableWrapper[C[+B] <: Iterable[B], A](seq: C[Iterable[A]]) =
+    new IterableIterableOps[C, A](seq)
+
+  /** The minimum element of a non-empty sequence of ordered elements
+   *  @deprecated use seq.min instead
+   */
+  @deprecated def min[A <% Ordered[A]](seq: Iterable[A]): A = {
+    val xs = seq.elements
+    if (!xs.hasNext) throw new IllegalArgumentException("min(<empty>)")
+    var min = xs.next
+    while (xs.hasNext) {
+      val x = xs.next
+      if (x < min) min = x
+    }
+    min
+  }
+
+  /** The maximum element of a non-empty sequence of ordered elements
+   *  @deprecated use seq.max instead
+   */
+  @deprecated def max[A <% Ordered[A]](seq: Iterable[A]): A = {
+    val xs = seq.elements
+    if (!xs.hasNext) throw new IllegalArgumentException("max(<empty>)")
+    var max = xs.next
+    while (xs.hasNext) {
+      val x = xs.next
+      if (max < x) max = x
+    }
+    max
+  }
+
+  /** A non-strict projection of an iterable.
+   * @author Sean McDirmid
+   * @author Martin Odersky
+  abstract class View[+C[+B] <: Iterable[B], +A] extends Iterable[A] { self =>
+
+    type CC[+B] <: View[C, A]
+
+    def origin: IterableOf[C, _]
+    def elements: Iterator[A]
+
+    override val underlying: IterableOf[C, _] = origin.underlying
+
+    private[this] var forced: Option[C[A]] = None
+
+    def force: C[A] = forced match {
+      case Some(c) => c
+      case None =>
+        val isDelay = elements eq origin.elements
+        val result =
+          if (isDelay) origin.force.asInstanceOf[C[A]]
+          else {
+            val b = newBuilder[A]
+            for (x <- elements)
+              b += x
+            b.result
+          }
+        this.forced = Some(result)
+        result
+    }
+
+    def newBuilder[B]: Builder[C, B] = underlying.newBuilder[B]
+
+    /** The builds a new view object */
+    protected def newView[B](elems: Iterator[B]): View[C, B] = new View[C, B] {
+      val previous = self
+      val elements = elems
+    }
+
+    /** Non-strict variant of @see IterableLike.++ */
+    override def ++[B >: A](that: Iterator[B]): View[C, B] = newView(elements ++ that)
+
+    /** Non-strict variant of @see IterableLike.++ */
+    override def ++[B >: A](that: Iterable[B]): View[C, B] = newView(elements ++ that.elements)
+
+    /** Non-strict variant of @see IterableLike.map */
+    override def map[B](f: A => B): View[I, B] = newView(elements map f)
+
+    /** Non-strict variant of @see IterableLike.flatMap */
+    override def flatMap[B](f: A => Iterable[B]): View[C, B] = newView(elements flatMap (f(_).elements))
+
+    /** Non-strict variant of @see IterableLike.filter */
+    override def filter(p: A => Boolean): View[C, A] = newView(elements filter p)
+
+    /** Non-strict variant of @see IterableLike.partition */
+    override def partition(p: A => Boolean): (View[C, A], View[C, A]) = {
+      val (li, ri) = elements partition p
+      (newView(li), newView(ri))
+    }
+
+    /** Non-strict variant of @see IterableLike.take */
+    override def take(n: Int): View[C, A] = newView(elements take n)
+
+    /** Non-strict variant of @see IterableLike.drop */
+    override def drop(n: Int): View[C, A] = newView(elements drop n)
+
+    /** Non-strict variant of @see IterableLike.slice */
+    override def slice(from: Int, until: Int): View[C, A] = newView(elements slice (from, until))
+
+    /** Non-strict variant of @see IterableLike.takeWhile */
+    override def takeWhile(p: A => Boolean): View[C, A] = newView(elements takeWhile p)
+
+    /** Non-strict variant of @see IterableLike.dropWhile */
+    override def dropWhile(p: A => Boolean): View[C, A] = newView(elements dropWhile p)
+
+    /** Non-strict variant of @see IterableLike.zip */
+    override def zip[B](other: Iterable[B]): C[(A, B)] = newView(elements zip other.elements)
+
+    /** Non-strict variant of @see IterableLike.indices */
+    override def indices: C[Int] = newView(elements.zipWithIndex map (_._2))
+
+    /** Non-strict variant of @see IterableLike.zipWithIndex */
+    override def zipWithIndex: C[(A, Int)] = newView(elements.zipWithIndex)
+
+    /** Non-strict variant of @see IterableLike.zipAll */
+    override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): C[(A1, B1)] =
+      newView(elements zipAll (that.elements, thisElem, thatElem))
+
+    /** 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]): View[C, B] = this ++ rest.elements
+
+    override def stringPrefix = origin.stringPrefix+"D"
+  }
+   */
+/*
+  /** A non-strict projection of an iterable.
+   * @author Sean McDirmid
+   */
+  @deprecated trait Projection[+A] extends Iterable[A] {
+    override def projection = this
+    /** convert to a copied strict collection */
+    def force : Iterable[A] = toList.asInstanceOf[Iterable[A]] //!!!
+
+    /** non-strict */
+    override def filter(p : A => Boolean) : Projection[A] = new Projection[A] {
+      def elements = Projection.this.elements.filter(p)
+    }
+    /** non-strict */
+    override def map[B](f: A => B) : Projection[B] = new Projection[B] {
+      def elements = Projection.this.elements.map(f)
+    }
+    /** non-strict */
+    override def flatMap[B](f: A => Iterable[B]) : Projection[B] = new Projection[B] {
+      def elements = Projection.this.elements.flatMap(a => f(a).elements)
+    }
+    /** non-strict */
+    override def takeWhile(p: A => Boolean): Projection[A] = new Projection[A] {
+      def elements = Projection.this.elements.takeWhile(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
+     */
+    def append[B >: A](rest : => Iterable[B]): Projection[B] = new Projection[B] {
+      def elements = Projection.this.elements ++ rest.elements
+    }
+  }
+*/
+}
+
+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
+ *  @version 1.1, 04/02/2004
+ */
+trait Iterable[+A] {
+
+  /** The type of the underlying iterable object
+   */
+  type CC[+B] <: Iterable[B]
+
+  /** This iterable seen as a CC-typed value */
+  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]
+
+  /** Creates a view of this iterable @see Iterable.View
+  def view: Iterable.View[C, A] = new Iterable.View {
+    val previous = self
+    val elements = self.elements
+  }
+  */
+
+  /** 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 = newBuilder[B]
+    b ++= this
+    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 ++= this
+    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.
+   *  It is guaranteed that the receiver iterable
+   *  itself is returned iff all its elements satisfy the predicate `p'.
+   *  Hence the following equality is valid:
+   *
+   *  (xs filter p) eq xs  ==  xs forall p
+   *
+   *  @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]
+    var allTrue = true
+    for (x <- this)
+      if (p(x)) b += x
+      else allTrue = false
+    if (allTrue) thisCC
+    else 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)
+
+  /** The first element of this sequence.
+   *
+   *  @throws Predef.NoSuchAentException if the sequence is empty.
+   */
+  def first: A = if (isEmpty) throw new NoSuchElementException else elements.next
+
+  /** Returns as an option the first element of this list or
+   *  <code>None</code> if list is empty.
+   */
+  def firstOption: Option[A] = if (isEmpty) None else Some(first)
+
+  /** Return an iterable consisting only over 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
+   */
+  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 collection without its <code>n</code> first elements
+   *  If this collection has less than <code>n</code> elements, the empty
+   *  collection is returned.
+   *
+   *  @param n the number of elements to drop
+   *  @return  the new collection
+   */
+  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-sequence starting at index `from`
+   *  and extending up to (but not including) index `until`.
+   *
+   *  @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>
+   */
+  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
+  }
+
+  /** 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 `subseq` and `slice` is that `slice` produces
+   *         a view of the current sequence, whereas `subseq` produces a new sequence.
+   * !!!
+  def view(from: Int, until: Int) = subseq(from, until)
+    // : Iterable.View[C, A] = view.slice(from, until)
+   */
+
+  /** An iterable consisting of all elements of this iterable except the last one.
+   */
+  def init: CC[A] = {
+    var last: A = first
+    val b = newBuilder[A]
+    for (x <- this) {
+      b += last
+      last = x
+    }
+    b.result
+  }
+
+  /** Returns the rightmost <code>n</code> elements from this iterable.
+   *
+   *  @param n the number of elements to take
+   */
+  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
+   */
+  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.
+   */
+  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>.
+   */
+  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>.
+   */
+  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.
+   */
+  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)
+  }
+
+  /** 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
+  }
+
+  /** 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 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 = {
+    var result = -1
+    var i = from
+    breakable {
+      for (x <- this) {
+        if (x == elem) { result = i; break }
+        else i += 1
+      }
+    }
+    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): Unit = {
+    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): Unit =
+    copyToArray(xs, start, xs.length - start)
+
+  /** Converts this collection to a fresh Array with <code>size</code> 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
+  }
+
+  /** Checks if the other iterable object contains the same elements.
+   *
+   *  @note will not terminate for infinite-sized collections.
+   *  @param that  the other iterable object
+   *  @return true, iff both iterable objects contain the same elements.
+   */
+  def sameElements[B >: A](that: Iterable[B]): Boolean = {
+    val ita = this.elements
+    val itb = that.elements
+    var res = true
+    while (res && ita.hasNext && itb.hasNext) {
+      res = (ita.next == itb.next)
+    }
+    !ita.hasNext && !itb.hasNext && res
+  }
+
+  /**
+   *  Create a fresh list with all the elements of this iterable object.
+   *  @note Will not terminate for infinite-sized collections.
+   */
+  def toList: List[A] = {
+    val b = new ListBuffer[A]()
+    b ++= this.asInstanceOf[scala.Iterable[A]] // !!!
+    b.toList
+  }
+
+  /**
+   *  Returns a sequence containing all of the elements in this iterable object.
+   *  @note Will not terminate for infinite-sized collections.
+   */
+  def toSeq: Seq[A] = toList
+
+  /**
+   *  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.
+   */
+  protected 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
+  }
+}
+
+
+
diff --git a/src/library/scalax/collection/Iterator.scala b/src/library/scalax/collection/Iterator.scala
new file mode 100755
index 0000000000..dc80c10f6b
--- /dev/null
+++ b/src/library/scalax/collection/Iterator.scala
@@ -0,0 +1,965 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Iterator.scala 15939 2008-08-26 14:33:17Z stepancheg $
+
+
+package scalax.collection
+
+import scala.collection.mutable.{Buffer, ListBuffer, ArrayBuffer}
+
+/** The <code>Iterator</code> object provides various functions for
+ *  creating specialized iterators.
+ *
+ *  @author  Martin Odersky
+ *  @author  Matthias Zenger
+ *  @version 2.8
+ */
+object Iterator {
+
+  val empty = new Iterator[Nothing] {
+    def hasNext: Boolean = false
+    def next(): Nothing = throw new NoSuchElementException("next on empty iterator")
+  }
+
+  def apply[A](args: A*): Iterator[A] = args.asInstanceOf[Iterable[A]].elements // !!!
+
+  /** Concatenate all the argument iterators into a single iterator.
+   *
+   *  @param xss the lists that are to be concatenated
+   *  @return the concatenation of all the lists
+   */
+  def concat[A](xss: Iterator[A]*): Iterator[A] =
+    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
+   *  @param   elem The element returned each time
+   */
+  def fill[A](len: Int)(elem: => A) = new Iterator[A] {
+    private var i = 0
+    def hasNext: Boolean = i < len
+    def next(): A =
+      if (hasNext) { i += 1; elem }
+      else empty.next()
+  }
+
+  /** An iterator that returns values of a function <code>f(0), ..., f(n-1)</code>,
+   *  for given `f` and `n`.
+   */
+  def tabulate[A](n: Int)(f: Int => A) = new Iterator[A] {
+    private var i = 0
+    def hasNext: Boolean = i < n
+    def next(): A =
+      if (hasNext) { val result = f(i); i += 1; result }
+      else empty.next()
+  }
+
+ /** Nn iterator with elements
+   *  <code>e<sub>n+1</sub> = e<sub>n</sub> + 1</code>
+   *  where <code>e<sub>0</sub> = start</code>
+   *  and <code>e<sub>i</sub> &lt; end</code>. However,
+   *  if <code>start &ge; end</code>, then it will return an empty range.
+   *
+   *  @param start the start value of the iterator
+   *  @param end   the end value of the iterator
+   *  @return      the iterator with values in range <code>[start;end)</code>.
+   */
+  def range(start: Int, end: Int): Iterator[Int] = range(start, end, 1)
+
+  /** Create an iterator with elements
+   *  <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code>
+   *  where <code>e<sub>0</sub> = start</code>
+   *  and elements are in the range between <code>start</code> (inclusive)
+   *  and <code>end</code> (exclusive)
+   *
+   *  @param start the start value of the iterator
+   *  @param end   the end value of the iterator
+   *  @param step  the increment value of the iterator (must be positive or negative)
+   *  @return      the iterator with values in range <code>[start;end)</code>.
+   */
+  def range(start: Int, end: Int, step: Int) = new Iterator[Int] {
+    private var i = start
+    def hasNext: Boolean = (step <= 0 || i < end) && (step >= 0 || i > end)
+    def next(): Int =
+      if (hasNext) { val result = i; i += step; result }
+      else empty.next()
+  }
+
+  /** An iterator that repeatedly applies a given function to a start value.
+   *
+   *  @param start the start value of the iteratpr
+   *  @param len   the number of elements returned by the iterator
+   *  @param f     the function that's repeatedly applied
+   *  @return      the iterator returning values <code>(start, f(start), f(f(start)), ..., f<sup>len-1</sup>(start))</code>
+   */
+  def iterate(start: Int, len: Int)(f: Int => Int) = new Iterator[Int] {
+    private var acc = start
+    private var i = 0
+    def hasNext: Boolean = i < len
+    def next(): Int =
+      if (hasNext) { val result = f(acc); i += 1; result }
+      else empty.next()
+  }
+
+  /** An infinite iterator that repeatedly applies a given function to a start value.
+   *
+   *  @param start the start value of the iteratpr
+   *  @param f     the function that's repeatedly applied
+   *  @return      the iterator returning values <code>(start, f(start), f(f(start)), ..., f<sup>len-1</sup>(start))</code>
+   */
+  def iterate(start: Int)(f: Int => Int) = new Iterator[Int] {
+    private var acc = start
+    private var i = 0
+    def hasNext: Boolean = true
+    def next(): Int = { val result = f(acc); i += 1; result }
+  }
+
+  /** Create an iterator with elements
+   *  <code>e<sub>n+1</sub> = e<sub>n</sub> + 1</code>
+   *  where <code>e<sub>0</sub> = start</code>.
+   *
+   *  @param start the start value of the iterator
+   *  @return      the iterator starting at value <code>start</code>.
+   */
+  def from(start: Int): Iterator[Int] = from(start, 1)
+
+  /** Create an iterator with elements
+   * <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code>
+   *  where <code>e<sub>0</sub> = start</code>.
+   *
+   *  @param start the start value of the iterator
+   *  @param step  the increment value of the iterator
+   *  @return      the iterator starting at value <code>start</code>.
+   */
+  def from(start: Int, step: Int): Iterator[Int] = new Iterator[Int] {
+    private var i = 0
+    def hasNext: Boolean = true
+    def next(): Int = { val result = i; i += 1; result }
+  }
+
+  class IteratorIteratorOps[A](its: Iterator[Iterator[A]]) {
+    /** Create an iterator that is the concantenation of all iterators
+     *  returned by a given iterator of iterators.
+     *   @param its   The iterator which returns on each call to next
+     *                a new iterator whose elements are to be concatenated to the result.
+     */
+    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()
+    }
+  }
+
+  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
+
+  /**
+   *  @param xs the array of elements
+   *  @see also: RandomAccessSeq.elements and slice
+   *  @deprecated  use `xs.elements` instead
+   */
+  @deprecated def fromArray[a](xs: Array[a]): Iterator[a] =
+    fromArray(xs, 0, xs.length)
+
+  /**
+   *  @param xs     the array of elements
+   *  @param start  the start index
+   *  @param length  the length
+   *  @see also: RandomAccessSeq.elements and slice
+   *  @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]] // !!!
+
+  /**
+   *  @param str the given string
+   *  @return    the iterator on <code>str</code>
+   *  @deprecated replaced by <code>str.elements</code>
+   */
+  @deprecated def fromString(str: String): Iterator[Char] =
+    str.elements.asInstanceOf[Iterator[Char]] // !!!
+
+  /**
+   *  @param n the product arity
+   *  @return  the iterator on <code>Product&lt;n&gt;</code>.
+   *  @deprecated use product.productElements instead
+   */
+  @deprecated def fromProduct(n: Product): Iterator[Any] = new Iterator[Any] {
+    private var c: Int = 0
+    private val cmax = n.productArity
+    def hasNext = c < cmax
+    def next() = { val a = n productElement c; c += 1; a }
+  }
+
+  /** Create an iterator with elements
+   *  <code>e<sub>n+1</sub> = step(e<sub>n</sub>)</code>
+   *  where <code>e<sub>0</sub> = start</code>
+   *  and elements are in the range between <code>start</code> (inclusive)
+   *  and <code>end</code> (exclusive)
+   *
+   *  @param start the start value of the iterator
+   *  @param end   the end value of the iterator
+   *  @param step  the increment function of the iterator, must be monotonically increasing or decreasing
+   *  @return      the iterator with values in range <code>[start;end)</code>.
+   *  @deprecated  use Iterator.iterate(start, end - start)(step) instead
+   */
+  @deprecated def range(start: Int, end: Int, step: Int => Int) = new Iterator[Int] {
+    private val up = step(start) > start
+    private val down = step(start) < start
+    private var i = start
+    def hasNext: Boolean = (!up || i < end) && (!down || i > end)
+    def next(): Int =
+      if (hasNext) { val j = i; i = step(i); j }
+      else empty.next()
+  }
+
+  /** Create an iterator with elements
+   *  <code>e<sub>n+1</sub> = step(e<sub>n</sub>)</code>
+   *  where <code>e<sub>0</sub> = start</code>.
+   *
+   *  @param start the start value of the iterator
+   *  @param step  the increment function of the iterator
+   *  @return      the iterator starting at value <code>start</code>.
+   *  @deprecated  use iterate(start)(step) instead
+   */
+  @deprecated def from(start: Int, step: Int => Int): Iterator[Int] = new Iterator[Int] {
+    private var i = start
+    override def hasNext: Boolean = true
+    def next(): Int = { val j = i; i = step(i); j }
+  }
+
+  /** Create an iterator that is the concantenation of all iterators
+   *  returned by a given iterator of iterators.
+   *   @param its   The iterator which returns on each call to next
+   *                a new iterator whose elements are to be concatenated to the result.
+   *   @deprecated  use its.flatten instead
+   */
+  @deprecated def flatten[T](its: Iterator[Iterator[T]]): Iterator[T] = new Iterator[T] {
+    private var it = its.next
+    def hasNext: Boolean = {
+      while (!it.hasNext && its.hasNext) it = its.next
+      it.hasNext
+    }
+    def next(): T =
+      if (hasNext) it.next
+      else empty.next()
+  }
+}
+
+import Iterator.empty
+
+/** Iterators are data structures that allow to iterate over a sequence
+ *  of elements. They have a <code>hasNext</code> method for checking
+ *  if there is a next element available, and a <code>next</code> method
+ *  which returns the next element and discards it from the iterator.
+ *
+ *  @author  Martin Odersky, Matthias Zenger
+ *  @version 2.8
+ */
+trait Iterator[+A] {
+self =>
+
+  /** Does this iterator provide another element?
+   */
+  def hasNext: Boolean
+
+  /** Returns the next element.
+   */
+  def next(): A
+
+  /** Returns a new iterator that iterates only over the first <code>n</code>
+   *  elements.
+   *
+   *  @param n the number of elements to take
+   *  @return  the new iterator
+   */
+  def take(n: Int): Iterator[A] = new Iterator[A] {
+    private var remaining = n
+    def hasNext = remaining > 0 && self.hasNext
+    def next(): A =
+      if (hasNext) { remaining -= 1; self.next }
+      else throw new NoSuchElementException("next on empty iterator")
+  }
+
+  /** Removes the first <code>n</code> elements from this iterator.
+   *
+   *  @param n the number of elements to drop
+   *  @return  the new iterator
+   */
+  def drop(n: Int): Iterator[A] =
+    if (n > 0 && hasNext) { next(); drop(n - 1) } else this
+
+  /** A sub-iterator of <code>until - from elements
+   *  starting at index <code>from</code>
+   *
+   *  @param from   The index of the first element of the slice
+   *  @param until    The index of the element following the slice
+   */
+  def slice(from: Int, until: Int): Iterator[A] = drop(from).take(until - from)
+
+  /** Returns a new iterator that maps all elements of this iterator
+   *  to new elements using function <code>f</code>.
+   */
+  def map[B](f: A => B): Iterator[B] = new Iterator[B] {
+    def hasNext = self.hasNext
+    def next() = f(self.next())
+  }
+
+  /** Returns a new iterator that first yields the elements of this
+   *  iterator followed by the elements provided by iterator <code>that</code>.
+   *  @deprecated  use <code>++</code>
+   */
+  def append[B >: A](that: Iterator[B]) = new Iterator[B] {
+    def hasNext = self.hasNext || that.hasNext
+    def next() = (if (self.hasNext) self else that).next()
+  }
+
+  /** Returns a new iterator that first yields the elements of this
+   *  iterator followed by the elements provided by iterator <code>that</code>.
+   */
+  def ++[B >: A](that: => Iterator[B]) = new Iterator[B] {
+    // optimize a little bit to prevent n log n behavior.
+    var cur : Iterator[B] = self
+    def hasNext = cur.hasNext || (cur eq self) && { cur = that; hasNext }
+    def next() = { hasNext; cur.next }
+  }
+
+  /** Applies the given function <code>f</code> to each element of
+   *  this iterator, then concatenates the results.
+   *
+   *  @param f the function to apply on each element.
+   *  @return  an iterator over <code>f(a<sub>0</sub>), ... ,
+   *           f(a<sub>n</sub>)</code> if this iterator yields the
+   *           elements <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
+   */
+  def flatMap[B](f: A => Iterator[B]): Iterator[B] = new Iterator[B] {
+    private var cur: Iterator[B] = empty
+    def hasNext: Boolean =
+      cur.hasNext || self.hasNext && { cur = f(self.next); hasNext }
+    def next(): B = (if (hasNext) cur else empty).next()
+  }
+
+  /** Returns an iterator over all the elements of this iterator that
+   *  satisfy the predicate <code>p</code>. The order of the elements
+   *  is preserved.
+   *
+   *  @param p the predicate used to filter the iterator.
+   *  @return  the elements of this iterator satisfying <code>p</code>.
+   */
+  def filter(p: A => Boolean): Iterator[A] = {
+    val self = buffered
+    new Iterator[A] {
+      private def skip() = while (self.hasNext && !p(self.head)) self.next()
+      def hasNext = { skip(); self.hasNext }
+      def next() = { skip(); self.next() }
+    }
+  }
+
+  /** Returns an iterator over the longest prefix of this iterator such that
+   *  all elements of the result satisfy the predicate <code>p</code>.
+   *  The order of the elements is preserved.
+   *
+   *  The behavior of <code>this</code> iterator is undefined after this method invocation.
+   *
+   *  @param p the predicate used to filter the iterator.
+   *  @return  the longest prefix of this iterator satisfying <code>p</code>.
+   */
+  def takeWhile(p: A => Boolean): Iterator[A] = {
+    val self = buffered
+    new Iterator[A] {
+      def hasNext = { self.hasNext && p(self.head) }
+      def next() = (if (hasNext) self else empty).next()
+    }
+  }
+
+  /** Partitions this iterator in two iterators according to a predicate.
+   *
+   *  @param p the predicate on which to partition
+   *  @return  a pair of iterators: the iterator that satisfies the predicate
+   *           <code>p</code> and the iterator that does not.
+   *           The relative order of the elements in the resulting iterators
+   *           is the same as in the original iterator.
+   */
+  def partition(p: A => Boolean): (Iterator[A], Iterator[A]) = {
+    val self = buffered
+    class PartitionIterator(p: A => Boolean) extends Iterator[A] {
+      var other: PartitionIterator = _
+      val lookahead = new scala.collection.mutable.Queue[A]
+      def skip() =
+        while (self.hasNext && !p(self.head)) {
+          other.lookahead += self.next
+        }
+      def hasNext = !lookahead.isEmpty || self.hasNext
+      def next() = if (lookahead.isEmpty) self.next() else lookahead.dequeue()
+    }
+    val l = new PartitionIterator(p)
+    val r = new PartitionIterator(!p(_))
+    l.other = r
+    r.other = l
+    (l, r)
+  }
+
+  /** Skips longest sequence of elements of this iterator which satisfy given
+   *  predicate <code>p</code>, and returns an iterator of the remaining elements.
+   *
+   *  The behavior of <code>this</code> iterator is undefined after this method invocation.
+   *
+   *  @param p the predicate used to skip elements.
+   *  @return  an iterator consisting of the remaining elements
+   */
+  def dropWhile(p: A => Boolean): Iterator[A] = {
+    val self = buffered
+    new Iterator[A] {
+      var dropped = false
+      private def skip() =
+        if (!dropped) {
+          while (self.hasNext && p(self.head)) self.next()
+          dropped = true
+        }
+      def hasNext = { skip(); self.hasNext }
+      def next() = { skip(); self.next() }
+    }
+  }
+
+  /** Return an iterator formed from this iterator and the specified iterator
+   *  <code>that</code> by associating each element of the former with
+   *  the element at the same position in the latter.
+   *  If one of the two iterators is longer than the other, its remaining elements are ignored.
+   *
+   *  @return     an iterator yielding <code>{a<sub>0</sub>,b<sub>0</sub>},
+   *              {a<sub>1</sub>,b<sub>1</sub>}, ...</code> where
+   *              <code>a<sub>i</sub></code> are the elements from this iterator
+   *              and <code>b<sub>i</sub></code> are the elements from iterator
+   *              <code>that</code>.
+   */
+  def zip[B](that: Iterator[B]) = new Iterator[(A, B)] {
+    def hasNext = self.hasNext && that.hasNext
+    def next = (self.next, that.next)
+  }
+
+  /** Return an iterator that pairs each element of this iterator
+   *  with its index, counting from 0.
+   *
+   *  @return      an iterator yielding <code>{a<sub>0</sub>,0},
+   *               {a<sub>1</sub>,1}...</code> where <code>a<sub>i</sub></code>
+   *               are the elements from this iterator.
+   */
+  def zipWithIndex = new Iterator[(A, Int)] {
+    var idx = 0
+    def hasNext = self.hasNext
+    def next = {
+      val ret = (self.next, idx)
+      idx += 1
+      ret
+    }
+  }
+
+  /** Returns an iterator formed from this iterator and the specified iterator
+   *  <code>that</code> by associating each element of the former with
+   *  the element at the same position in the latter.
+   *
+   *  @param that     iterator <code>that</code> may have a different length
+   *                  as the self iterator.
+   *  @param thisElem element <code>thisElem</code> is used to fill up the
+   *                  resulting iterator if the self iterator is shorter than
+   *                  <code>that</code>
+   *  @param thatElem element <code>thatElem</code> is used to fill up the
+   *                  resulting iterator if <code>that</code> is shorter than
+   *                  the self iterator
+   *  @return         <code>Iterator((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: Iterator[B], thisElem: A1, thatElem: B1) = new Iterator[(A1, B1)] {
+    def hasNext = self.hasNext || that.hasNext
+    def next(): (A1, B1) =
+      if (self.hasNext) {
+        if (that.hasNext) (self.next(), that.next())
+        else (self.next(), thatElem)
+      } else {
+        if (that.hasNext) (thisElem, that.next())
+        else empty.next()
+      }
+  }
+
+  /** Apply a function <code>f</code> to all elements of this
+   *  iterable object.
+   *
+   *  @param  f   a function that is applied to every element.
+   */
+  def foreach(f: A => Unit) { while (hasNext) f(next()) }
+
+  /** Apply a predicate <code>p</code> to all elements of this
+   *  iterable object and return <code>true</code> iff the predicate yields
+   *  <code>true</code> for all elements.
+   *
+   *  @param p the predicate
+   *  @return  <code>true</code> iff the predicate yields <code>true</code>
+   *           for all elements.
+   */
+  def forall(p: A => Boolean): Boolean = {
+    var res = true
+    while (res && hasNext) res = p(next())
+    res
+  }
+
+  /** Apply a predicate <code>p</code> to all elements of this
+   *  iterable object and return true, iff there is at least one
+   *  element for which <code>p</code> yields <code>true</code>.
+   *
+   *  @param p the predicate
+   *  @return  <code>true</code> iff the predicate yields <code>true</code>
+   *           for at least one element.
+   */
+  def exists(p: A => Boolean): Boolean = {
+    var res = false
+    while (!res && hasNext) res = p(next())
+    res
+  }
+
+  /** Tests if the given value <code>elem</code> is a member of this iterator.
+   *
+   *  @param elem element whose membership has to be tested.
+   *  @return     <code>true</code> iff there is an element of this iterator which
+   *              is equal (w.r.t. <code>==</code>) to <code>elem</code>.
+   */
+  def contains(elem: Any): Boolean = exists { _ == elem }
+
+  /** Find and return the first element of the iterable object satisfying a
+   *  predicate, if any.
+   *
+   *  @param p the predicate
+   *  @return  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 res: Option[A] = None
+    while (res.isEmpty && hasNext) {
+      val e = next()
+      if (p(e)) res = Some(e)
+    }
+    res
+  }
+
+  /** Returns index of the first element satisying a predicate, or -1.
+   *
+   *  @note may not terminate for infinite-sized collections.
+   *  @param  p the predicate
+   *  @return   the index of the first element satisfying <code>p</code>,
+   *           or -1 if such an element does not exist
+   */
+  def indexWhere(p: A => Boolean): Int = {
+    var i = 0
+    var found = false
+    while (!found && hasNext) {
+      if (p(next())) {
+        found = true
+      } else {
+        i += 1
+      }
+    }
+    if (found) i else -1
+  }
+
+  /** 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 = {
+    var i = 0
+    var found = false
+    while (!found && hasNext) {
+      if (next() == elem) {
+        found = true
+      } else {
+        i += 1
+      }
+    }
+    if (found) i else -1
+  }
+
+  /** Combines the elements of this iterator together using the binary
+   *  operator <code>op</code>, from left to right, and starting with
+   *  the value <code>z</code>.
+   *
+   *  @return <code>op(... (op(op(z,a<sub>0</sub>),a<sub>1</sub>) ...),
+   *          a<sub>n</sub>)</code> if the iterator yields elements
+   *          <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 acc = z
+    while (hasNext) acc = op(acc, next())
+    acc
+  }
+
+  /** Combines the elements of this iterator together using the binary
+   *  operator <code>op</code>, from right to left, and starting with
+   *  the value <code>z</code>.
+   *
+   *  @return <code>a<sub>0</sub> op (... op (a<sub>n</sub> op z)...)</code>
+   *          if the iterator yields elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
+   *          a<sub>n</sub></code>.
+   */
+  def foldRight[B](z: B)(op: (A, B) => B): B = {
+    def fold(z: B): B = if (hasNext) op(next(), fold(z)) else z
+    fold(z)
+  }
+
+  /** Similar to <code>foldLeft</code> but can be used as
+   *  an operator with the order of iterator and zero arguments reversed.
+   *  That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code>.
+   *
+   *  @param z the left argument of the first application of <code>op</code>
+   *           (evaluation occurs from left to right).
+   *  @param op the applied operator.
+   *  @return  the result value
+   *  @see     <code><a href="#foldLeft">foldLeft</a></code>.
+   */
+  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>.
+   *
+   *  @param z the right argument of the first application of <code>op</code>
+   *           (evaluation occurs from right to left).
+   *  @param op the applied operator.
+   *  @return  the result value.
+   *  @see     <code><a href="#foldRight">foldRight</a></code>.
+   */
+  def :\[B](z: B)(op: (A, B) => B): B = foldRight(z)(op)
+
+  /** Combines the elements of this iterator together using the binary
+   *  operator <code>op</code>, from left to right
+   *  @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 iterator yields elements
+   *          <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
+   *  @throws Predef.UnsupportedOperationException if the iterator is empty.
+   */
+  def reduceLeft[B >: A](op: (B, A) => B): B = {
+    if (hasNext) foldLeft[B](next())(op)
+    else throw new UnsupportedOperationException("empty.reduceLeft")
+  }
+
+  /** Combines the elements of this iterator together using the binary
+   *  operator <code>op</code>, from right to left
+   *  @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 iterator yields 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 = {
+    if (!hasNext) throw new UnsupportedOperationException("empty.reduceRight")
+    foldRight[B](next())(op)
+  }
+
+  /** Returns a buffered iterator from this iterator.
+   */
+  def buffered = new BufferedIterator[A] {
+    private var hd: A = _
+    private var hdDefined: Boolean = false
+
+    def head: A = {
+      if (!hdDefined) {
+        hd = next()
+        hdDefined = true
+      }
+      hd
+    }
+
+    def hasNext =
+      hdDefined || self.hasNext
+
+    def next =
+      if (hdDefined) {
+        hdDefined = false
+        hd
+      } else self.next
+  }
+
+  /** Returns a counted iterator from this iterator.
+   *  @deprecated use @see zipWithIndex in Iterator
+   */
+  @deprecated def counted = new CountedIterator[A] {
+    private var cnt = -1
+    def count = cnt
+    def hasNext: Boolean = self.hasNext
+    def next(): A = { cnt += 1; self.next }
+  }
+
+  /** Creates two new iterators that both iterate over the same elements
+   *  than this iterator (in the same order).
+   *
+   *  @return a pair of iterators
+   */
+  def duplicate: (Iterator[A], Iterator[A]) = {
+    var xs: List[A] = Nil
+    var ahead: Iterator[A] = null
+    class Partner extends Iterator[A] {
+      var ys: List[A] = Nil
+      def hasNext: Boolean = self.synchronized (
+        ((this == ahead) && self.hasNext) ||
+        ((this != ahead) && (!xs.isEmpty || !ys.isEmpty || self.hasNext))
+      )
+      def next(): A = self.synchronized {
+        if (this == ahead) {
+          val e = self.next()
+          xs = e :: xs; e
+        } else {
+          if (ys.isEmpty) {
+            ys = xs.reverse
+            xs = Nil
+          }
+          ys match {
+            case Nil =>
+              val e = self.next()
+              ahead = this
+              xs = e :: xs; e
+            case z :: zs =>
+              ys = zs; z
+          }
+        }
+      }
+    }
+    ahead = new Partner
+    (ahead, new Partner)
+  }
+
+  def patch[B >: A](from: Int, ps: Seq[B], replaced: Int) = new Iterator[B] {
+    private val plen = ps.length
+    private var origElems = self
+    private val patchElems = ps.elements
+    private var i = 0
+    def hasNext: Boolean =
+      if (i < from) origElems.hasNext
+      else patchElems.hasNext || origElems.hasNext
+    def next(): B = {
+      val result: B =
+        if (i < from || i >= from + plen) origElems.next()
+        else patchElems.next()
+      i += 1
+      if (i == from) origElems = origElems drop replaced
+      result
+    }
+  }
+
+  /** Fills the given array <code>xs</code> with at most `len` elements of
+   *  this iterator starting at position `start`.
+   *  Copying will stop once either the end of the current iterable is reached or
+   *  `len` elements have been copied.
+   *
+   *  @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): Unit = {
+    var i = start
+    val end = start + len
+    while (hasNext && i < end) {
+      xs(i) = next()
+      i += 1
+    }
+  }
+
+  /** Fills the given array <code>xs</code> with the elements of
+   *  this iterator starting at position <code>start</code>
+   *  until either the end of the current iterator or the end of array `xs` is reached.
+   *
+   *  @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): Unit =
+    copyToArray(xs, start, xs.length - start)
+
+  /** Fills the given array <code>xs</code> with the elements of
+   *  this iterator starting at position <code>0</code>
+   *  until either the end of the current iterator or the end of array `xs` is reached.
+   *
+   *  @param  xs the array to fill.
+   *  @pre    the array must be large enough to hold all elements.
+   */
+  def copyToArray[B >: A](xs: Array[B]): Unit = copyToArray(xs, 0, xs.length)
+
+  /** Fills the given array <code>xs</code> with the elements of
+   *  this sequence starting at position <code>start</code>.  Like <code>copyToArray</code>,
+   *  but designed to accomodate IO stream operations.
+   *
+   *  @param  xs    the array to fill.
+   *  @param  start the starting index.
+   *  @param  sz    the maximum number of elements to be read.
+   *  @pre          the array must be large enough to hold <code>sz</code> elements.
+   *  @deprecated   use copyToArray instead
+   */
+  @deprecated def readInto[B >: A](xs: Array[B], start: Int, sz: Int) {
+    var i = start
+    while (hasNext && i - start < sz) {
+      xs(i) = next
+      i += 1
+    }
+  }
+  @deprecated def readInto[B >: A](xs: Array[B], start: Int) {
+    readInto(xs, start, xs.length - start)
+  }
+  @deprecated def readInto[B >: A](xs: Array[B]) {
+    readInto(xs, 0, xs.length)
+  }
+
+  /** Copy all elements to a buffer
+   *  @param   The buffer to which elements are copied
+   */
+  def copyToBuffer[B >: A](dest: Buffer[B]) {
+    while (hasNext) dest += next
+  }
+
+  /** Transform this iterator into a list of all elements.
+   *
+   *  @return  a list which enumerates all elements of this iterator.
+   */
+  def toList: List[A] = {
+    val res = new ListBuffer[A]
+    while (hasNext) res += next
+    res.toList
+  }
+
+  /**
+   *  Create a stream which contains all the elements of this iterator.
+   */
+  def toStream: Stream[A] =
+    if (hasNext) Stream.cons(next, toStream) else Stream.empty
+
+  /**
+   *  Create a sequence which contains all the elements of this iterator.
+   */
+  def toSeq: Seq[A] = {
+    val buffer = new ArrayBuffer[A]
+    this copyToBuffer buffer
+    buffer.readOnly
+  }
+
+  /** Collect elements into a seq.
+   *
+   * @return  a sequence which enumerates all elements of this iterator.
+   * @deprecated  use toSeq instead
+   */
+  @deprecated def collect: Seq[A] = {
+    val buffer = new ArrayBuffer[A]
+    this copyToBuffer buffer
+    buffer.readOnly
+  }
+
+  /** Returns a string representation of the elements in this iterator. 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>.
+   *  <p/>
+   *  Ex: <br/>
+   *  <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
+   *
+   *  @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 = {
+    val buf = new StringBuilder
+    addString(buf, 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>.
+   *
+   *  @param sep separator string.
+   *  @return a string representation of this iterable object.
+   */
+  def mkString(sep: String): String = this.mkString("", sep, "")
+
+  /** Returns a string representation of this iterable object. The string
+   *  representations of elements (w.r.t. the method <code>toString()</code>)
+   *  are separated by a comma.
+   *
+   *  @return a string representation of this iterable object.
+   */
+  def mkString: String =
+    mkString("")
+
+  /** Write all elements of this iterator 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>.
+   */
+  def addString(buf: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
+    buf.append(start)
+    val elems = this
+    if (elems.hasNext) buf.append(elems.next)
+    while (elems.hasNext) {
+      buf.append(sep); buf.append(elems.next)
+    }
+    buf.append(end)
+  }
+
+  /** Write all elements of this iterator 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>.
+   */
+  def addString(buf: StringBuilder, sep: String): StringBuilder =
+    addString(buf, "", sep, "")
+
+  /** Write all elements of this string into given string builder without using
+   *  any separator between consecutive elements.
+   */
+  def addString(buf: StringBuilder): StringBuilder =
+    addString(buf, "", "", "")
+
+  override def toString = (if (hasNext) "non-empty" else "empty")+" iterator"
+
+}
diff --git a/src/library/scalax/collection/SeqFactory.scala b/src/library/scalax/collection/SeqFactory.scala
new file mode 100755
index 0000000000..c5c3ed3afb
--- /dev/null
+++ b/src/library/scalax/collection/SeqFactory.scala
@@ -0,0 +1,111 @@
+package scalax.collection
+
+abstract class SeqFactory[CC[+A] <: Iterable[A]] {
+
+  /** The empty collection of type CC */
+  val empty: CC[Nothing]
+
+  private def newBuilder[A]: Builder[CC, A] =
+    empty.newBuilder[A].asInstanceOf[Builder[CC, A]]
+
+  /** Create CC collection of specified elements */
+  def apply[A](args: A*): CC[A] =
+    (empty ++ args.asInstanceOf[Iterable[A]]).asInstanceOf[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] =
+    Iterable.iterableIterableWrapper[CC, A](xss.asInstanceOf[CC[CC[A]]]).flatten // !!!
+
+  /** 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/util/control/Break.scala b/src/library/scalax/util/control/Break.scala
new file mode 100755
index 0000000000..4d43490a87
--- /dev/null
+++ b/src/library/scalax/util/control/Break.scala
@@ -0,0 +1,15 @@
+package scala.util.control
+
+object Break {
+  private class BreakException extends RuntimeException
+  private val breakException = new BreakException
+  def break { throw breakException }
+  def breakable(op: => Unit) {
+    try {
+      op
+    } catch {
+      case ex: BreakException =>
+    }
+  }
+}
+