diff options
author | Antonio Cunei <antonio.cunei@epfl.ch> | 2008-11-25 18:05:48 +0000 |
---|---|---|
committer | Antonio Cunei <antonio.cunei@epfl.ch> | 2008-11-25 18:05:48 +0000 |
commit | af47e5b433ea538bf096a176c88f3c91116e09cd (patch) | |
tree | b3e66e93fb653570ebbef16183cf4f2be2111c12 /src/library | |
parent | 2d61f09332dbc6038f869c6a23a95dca1bc3b6c7 (diff) | |
download | scala-af47e5b433ea538bf096a176c88f3c91116e09cd.tar.gz scala-af47e5b433ea538bf096a176c88f3c91116e09cd.tar.bz2 scala-af47e5b433ea538bf096a176c88f3c91116e09cd.zip |
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
Diffstat (limited to 'src/library')
60 files changed, 7774 insertions, 4 deletions
diff --git a/src/library/scala/annotation/unchecked/uncheckedStable.scala b/src/library/scala/annotation/unchecked/uncheckedStable.scala new file mode 100755 index 0000000000..d6fcdf2127 --- /dev/null +++ b/src/library/scala/annotation/unchecked/uncheckedStable.scala @@ -0,0 +1,13 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ +package scala.annotation.unchecked + +/** An annotation for values that are assumed to be stable even though their + * types are volatile. + */ +final class uncheckedStable extends StaticAnnotation {} diff --git a/src/library/scala/annotation/unchecked/uncheckedVariance.scala b/src/library/scala/annotation/unchecked/uncheckedVariance.scala index 862db90809..1cb9a82d6b 100644 --- a/src/library/scala/annotation/unchecked/uncheckedVariance.scala +++ b/src/library/scala/annotation/unchecked/uncheckedVariance.scala @@ -1,6 +1,6 @@ /* __ *\ ** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2002-2007, LAMP/EPFL ** +** / __/ __// _ | / / / _ | (c) 2002-2008, LAMP/EPFL ** ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** ** /____/\___/_/ |_/____/_/ | | ** ** |/ ** diff --git a/src/library/scala/collection/mutable/ArrayBuffer.scala b/src/library/scala/collection/mutable/ArrayBuffer.scala index eb3f8a07ce..74bef697bc 100644 --- a/src/library/scala/collection/mutable/ArrayBuffer.scala +++ b/src/library/scala/collection/mutable/ArrayBuffer.scala @@ -1,6 +1,6 @@ /* __ *\ ** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** ** /____/\___/_/ |_/____/_/ | | ** ** |/ ** diff --git a/src/library/scala/collection/mutable/ResizableArray.scala b/src/library/scala/collection/mutable/ResizableArray.scala index 2e2e51ecb9..211d785a61 100644 --- a/src/library/scala/collection/mutable/ResizableArray.scala +++ b/src/library/scala/collection/mutable/ResizableArray.scala @@ -1,6 +1,6 @@ /* __ *\ ** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** ** /____/\___/_/ |_/____/_/ | | ** ** |/ ** @@ -74,7 +74,7 @@ trait ResizableArray[A] extends RandomAccessSeq[A] { /** ensure that the internal array has at n cells */ protected def ensureSize(n: Int) { if (n > array.length) { - var newsize = array.length * 2 + var newsize = if (array.length == 0) 2 else array.length * 2 while (n > newsize) newsize = newsize * 2 val newar: Array[AnyRef] = new Array(newsize) 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..eedd89537a --- /dev/null +++ b/src/library/scalax/collection/Builder.scala @@ -0,0 +1,21 @@ +/* __ *\ +** ________ ___ / / ___ 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[+CC[B], A] extends mutable.Appendable[A] { + def +=(x: A) + def elements: Iterator[A] + def result: CC[A] + override def ++=(xs: Iterator[A]) { for (x <- xs) this += x } + override def ++=(xs: Iterable[A]) { for (x <- xs) this += x } +} + diff --git a/src/library/scalax/collection/Iterable.scala b/src/library/scalax/collection/Iterable.scala new file mode 100755 index 0000000000..b6abd8d559 --- /dev/null +++ b/src/library/scalax/collection/Iterable.scala @@ -0,0 +1,143 @@ +/* __ *\ +** ________ ___ / / ___ 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 generic._ + +/** 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>SizedIterable</code>. + * + * @author Matthias Zenger + * @autor Martin Odersky + * @owner Martin Odersky + * @version 2.8 + */ +trait Iterable[+A] extends covariant.IterableTemplate[Iterable, A] { self => + + /** Creates a view of this iterable @see Iterable.View + def view: View[Iterable, A] = new View[Iterable, A] { // !!! Martin: We should maybe infer the type parameters here? + val origin: self.type = self + val elements: Iterator[A] = self.elements + } + */ +} + +/** Various utilities for instances of <a href="Iterable.html">Iterable</a>. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 + */ +object Iterable extends covariant.IterableFactory[Iterable] { + + /** The empty iterable */ + val empty: Iterable[Nothing] = null // !!! + + class OrderedIterableOps[A](seq: Iterable[A], cmp: Ordering[A]) { + def min: A = { + require(!seq.isEmpty, "min(<empty>)") + var acc = seq.elements.next + for (x <- seq) + if (cmp.lt(x, acc)) acc = x + acc + } + def max: A = { + require(!seq.isEmpty, "max(<empty>)") + var acc = seq.elements.next + 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 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 + } + } + + class PairCollectionOps[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) + } + } + + 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 iterableIterableWrapper[C[+B] <: Iterable[B], A](seq: C[Iterable[A]]) = + new IterableIterableOps[C, A](seq) + implicit def pairCollectionWrapper[C[+B] <: Iterable[B], A1, A2](seq: C[(A1, A2)]) = + new PairCollectionOps[C, A1, A2](seq) + + type View[+UC[+B] <: Sequence[B], +A] = covariant.IterableView[UC, A] + + /** @deprecated use View instead + */ + @deprecated type Projection[+A] = View[C, A] forSome { type C[B] <: Iterable[B] } + + /** 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 iConstead + */ + @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 + } + +} + diff --git a/src/library/scalax/collection/Iterator.scala b/src/library/scalax/collection/Iterator.scala new file mode 100755 index 0000000000..2758faf854 --- /dev/null +++ b/src/library/scalax/collection/Iterator.scala @@ -0,0 +1,970 @@ +/* __ *\ +** ________ ___ / / ___ 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 mutable.{Buffer, ArrayBuffer, ListBuffer} +import immutable.{List, Nil, ::} + +/** 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> < end</code>. However, + * if <code>start ≥ 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: Vector.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: Vector.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<n></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 > 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 + } + + def length: Int = { + var i = 0 + while (hasNext) { + next(); i += 1 + } + i + } + + /** Returns a counted iterator from this iterator. + * @deprecated use @see zipWithIndex in Iterator + */ + 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: Sequence[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 toSequence: Sequence[A] = { + val buffer = new ArrayBuffer[A] + this copyToBuffer buffer + null // !!! should be: buffer.readOnly + } + + /** Collect elements into a seq. + * + * @return a sequence which enumerates all elements of this iterator. + * @deprecated use toSequence instead + */ + @deprecated def collect: Sequence[A] = toSequence + + /** 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/OrderedIterable.scala b/src/library/scalax/collection/OrderedIterable.scala new file mode 100755 index 0000000000..97bd96e667 --- /dev/null +++ b/src/library/scalax/collection/OrderedIterable.scala @@ -0,0 +1,41 @@ +/* __ *\ +** ________ ___ / / ___ 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 generic._ + +/** An ordered collection is a collection with a fixed sequence of elements + * which corresponds to append order. In particular, it holds that + * + * (c1 ++ c2).elements = c1.elements ++ c2.elements + * + * for any two ordered collections c1 and c2. + * Ordered collections support + * - operations that form subsequences: take, takeWhile, drop, dropWhile, + * - zip, unzip + * + * @author Martin Odersky + * @version 2.8 + */ +trait OrderedIterable[+A] extends Iterable[A] with covariant.OrderedIterableTemplate[OrderedIterable, A] + +/** Various utilities for instances of <a href="Iterable.html">Iterable</a>. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 + */ +object OrderedIterable extends covariant.IterableFactory[OrderedIterable] { + + val empty: OrderedIterable[Nothing] = null // !!! + +} diff --git a/src/library/scalax/collection/Sequence.scala b/src/library/scalax/collection/Sequence.scala new file mode 100755 index 0000000000..0ee88e3575 --- /dev/null +++ b/src/library/scalax/collection/Sequence.scala @@ -0,0 +1,45 @@ +/* __ *\ +** ________ ___ / / ___ 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 + +import generic._ + +/** Class <code>Sequence[A]</code> represents finite sequences of elements + * of type <code>A</code>. + * + * @author Martin Odersky + * @author Matthias Zenger + * @version 1.0, 16/07/2003 + */ +trait Sequence[+A] extends OrderedIterable[A] with SizedIterable[A] with covariant.SequenceTemplate[Sequence, A] + +object Sequence extends covariant.SequenceFactory[Sequence] { + + /** The empty sequence */ + val empty : Sequence[Nothing] = null // !!! + + type View[+UC[+B] <: Sequence[B], +A] = covariant.SequenceView[UC, A] + + /** @deprecated use View instead + */ + @deprecated type Projection[A] = View[C, A] forSome { type C[+B] <: Sequence[B] } + + /** @deprecated use Sequence(value) instead */ + @deprecated def singleton[A](value: A) = Sequence(value) + + /** Builds a singleton sequence. + * + * @deprecated use <code>Sequence(x)</code> instead. + */ + @deprecated def single[A](x: A) = singleton(x) +} + diff --git a/src/library/scalax/collection/SizedIterable.scala b/src/library/scalax/collection/SizedIterable.scala new file mode 100644 index 0000000000..f4e13f3521 --- /dev/null +++ b/src/library/scalax/collection/SizedIterable.scala @@ -0,0 +1,38 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Collection.scala 12340 2007-07-17 15:29:47Z mcdirmid $ + + +package scalax.collection + +/** Variant of <code>Iterable</code> which also demands + * implementation of a `size` method. + * Basically, this trait just adds size to Iterable, + * and provides an optimized implementation of toArray based on it. + * + * @author Martin Odersky + * @version 2.8 + */ +trait SizedIterable[+A] extends Iterable[A] { + + /** Returns the number of elements in this collection. + * + * @return number of collection elements. + */ + def size : Int + + /** Converts this iterable to a fresh Array with <code>size</code> elements. + */ + override def toArray[B >: A]: Array[B] = { + val result = new Array[B](size) + copyToArray(result, 0) + result + } +} + diff --git a/src/library/scalax/collection/Vector.scala b/src/library/scalax/collection/Vector.scala new file mode 100755 index 0000000000..8787d7fd42 --- /dev/null +++ b/src/library/scalax/collection/Vector.scala @@ -0,0 +1,21 @@ +/* __ *\ +** ________ ___ / / ___ 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 + +import generic._ + +trait Vector[+A] extends Sequence[A] with covariant.VectorTemplate[Vector, A] + +object Vector extends covariant.SequenceFactory[Vector] { + + /** The empty sequence */ + val empty : Vector[Nothing] = null // !!! +} diff --git a/src/library/scalax/collection/generic/IterableFactory.scala b/src/library/scalax/collection/generic/IterableFactory.scala new file mode 100755 index 0000000000..264e333ac5 --- /dev/null +++ b/src/library/scalax/collection/generic/IterableFactory.scala @@ -0,0 +1,108 @@ +package scalax.collection.generic + +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/IterableForwarder.scala b/src/library/scalax/collection/generic/IterableForwarder.scala new file mode 100644 index 0000000000..fba1e6d0e9 --- /dev/null +++ b/src/library/scalax/collection/generic/IterableForwarder.scala @@ -0,0 +1,61 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: IterableProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $ + + +package scalax.collection.generic + +import collection.mutable.Buffer +import collection.immutable.List + +/** This trait implements a forwarder for iterable objects. It forwards + * all calls to a different iterable object, except for + * + * - toString, hashCode, equals, stringPrefix + * - newBuilder, view + * - all calls creating a new iterable objetc of the same kind + * + * The above methods are forwarded by subclass IterableProxy + * + * @author Martin Odersky + * @version 2.8 + */ +trait IterableForwarder[+A] extends Iterable[A] { + + /** The iterable object to which calls are forwarded */ + protected def underlying: Iterable[A] + + // Iterable delegates + // Iterable methods could be printed by cat IterableTemplate.scala | sed -n '/trait Iterable/,$ p' | egrep '^ (override )?def' + + override def elements = underlying.elements + override def isEmpty = underlying.isEmpty + override def hasDefiniteSize = underlying.hasDefiniteSize + override def foreach(f: A => Unit) = underlying.foreach(f) + override def forall(p: A => Boolean): Boolean = underlying.forall(p) + override def exists(p: A => Boolean): Boolean = underlying.exists(p) + override def count(p: A => Boolean): Int = underlying.count(p) + override def find(p: A => Boolean): Option[A] = underlying.find(p) + override def foldLeft[B](z: B)(op: (B, A) => B): B = underlying.foldLeft(z)(op) + override def foldRight[B](z: B)(op: (A, B) => B): B = underlying.foldRight(z)(op) + override def reduceLeft[B >: A](op: (B, A) => B): B = underlying.reduceLeft(op) + override def reduceRight[B >: A](op: (A, B) => B): B = underlying.reduceRight(op) + override def copyToBuffer[B >: A](dest: Buffer[B]) = underlying.copyToBuffer(dest) + override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) = underlying.copyToArray(xs, start, len) + override def toArray[B >: A]: Array[B] = underlying.toArray + override def toList: List[A] = underlying.toList + override def toSequence: Sequence[A] = underlying.toSequence + override def toStream: Stream[A] = underlying.toStream + override def mkString(start: String, sep: String, end: String): String = underlying.mkString(start, sep, end) + override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = underlying.addString(b, start, sep, end) + + override def head: A = underlying.head + override def last: A = underlying.last + override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that) +} diff --git a/src/library/scalax/collection/generic/IterableTemplate.scala b/src/library/scalax/collection/generic/IterableTemplate.scala new file mode 100755 index 0000000000..01a23f5ecf --- /dev/null +++ b/src/library/scalax/collection/generic/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 + +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 > 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><(e1: a, e2: a) => 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><(e1: a, e2: a) => Boolean</code>. + * @ex <pre> + * List("Steve", "Tom", "John", "Bob") + * .sort((e1, e2) => (e1 compareTo e2) < 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 < 0</code> + * or <code>length < 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/IterableView.scala b/src/library/scalax/collection/generic/IterableView.scala new file mode 100755 index 0000000000..b9b826b0a4 --- /dev/null +++ b/src/library/scalax/collection/generic/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 + +/** 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/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/OrderedIterableTemplate.scala new file mode 100755 index 0000000000..fd2dbac8e4 --- /dev/null +++ b/src/library/scalax/collection/generic/OrderedIterableTemplate.scala @@ -0,0 +1,23 @@ +/* __ *\ +** ________ ___ / / ___ 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 + +import OrderedIterable._ + +/** Ordered iterables are iterables where the `elements` method always returns elements in the same + * order (namely the order in which elements were appended to the iterable). In particular, one has + * for every two ordered iterables `xs` and `ys`: + * + * `(xs ++ ys).elements = xs.elements ++ ys.elements + */ +trait OrderedIterableTemplate[+CC[/*+*/B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], /*+*/A] + extends IterableTemplate[CC, A] diff --git a/src/library/scalax/collection/generic/SequenceFactory.scala b/src/library/scalax/collection/generic/SequenceFactory.scala new file mode 100755 index 0000000000..ee97c80c75 --- /dev/null +++ b/src/library/scalax/collection/generic/SequenceFactory.scala @@ -0,0 +1,11 @@ +package scalax.collection.generic + +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/SequenceForwarder.scala b/src/library/scalax/collection/generic/SequenceForwarder.scala new file mode 100644 index 0000000000..208d0079f1 --- /dev/null +++ b/src/library/scalax/collection/generic/SequenceForwarder.scala @@ -0,0 +1,50 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: SeqProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $ + + +package scalax.collection.generic + +/** This class implements a forwarder for sequences. It forwards + * all calls to a different sequence object except for + * + * - toString, hashCode, equals, stringPrefix + * - newBuilder, view, toSequence + * - all calls creating a new iterable objetc of the same kind + * + * The above methods are forwarded by subclass SequenceProxy + * + * @author Martin Odersky + * @version 2.8 + */ +trait SequenceForwarder[+A] extends Sequence[A] with IterableForwarder[A] { + + protected override def underlying: Sequence[A] + + // PartialFunction delegates + + override def apply(i: Int): A = underlying.apply(i) + override def isDefinedAt(x: Int): Boolean = underlying.isDefinedAt(x) + + // Sequence delegates + // Sequence methods could be printed by cat SequenceTemplate.scala | sed -n '/trait Seq/,$ p' | egrep '^ (override )?def' + + override def length: Int = underlying.length + override def lengthCompare(l: Int) = underlying lengthCompare l + override def segmentLength(p: A => Boolean, from: Int): Int = underlying.segmentLength(p, from) + override def prefixLength(p: A => Boolean) = underlying.prefixLength(p) + override def indexWhere(p: A => Boolean, from: Int): Int = underlying.indexWhere(p, from) + override def indexOf[B >: A](elem: B, from: Int): Int = underlying.indexOf(elem, from) + override def reversedElements: Iterator[A] = underlying.reversedElements + override def startsWith[B](that: Sequence[B], offset: Int): Boolean = underlying.startsWith(that, offset) + override def endsWith[B](that: Sequence[B]): Boolean = underlying.endsWith(that) + override def indexOf[B >: A](that: Sequence[B]): Int = underlying.indexOf(that) + override def contains(elem: Any): Boolean = underlying.contains(elem) + override def indices: Range = underlying.indices +} diff --git a/src/library/scalax/collection/generic/SequenceTemplate.scala b/src/library/scalax/collection/generic/SequenceTemplate.scala new file mode 100755 index 0000000000..eba0e4bf98 --- /dev/null +++ b/src/library/scalax/collection/generic/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 + +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 < 0</code> iff <code>this.length < len</code> + * <code>x == 0</code> iff <code>this.length == len</code> + * <code>x > 0</code> iff <code>this.length > 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 < 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/SequenceView.scala b/src/library/scalax/collection/generic/SequenceView.scala new file mode 100755 index 0000000000..6178542241 --- /dev/null +++ b/src/library/scalax/collection/generic/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 + +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/VectorTemplate.scala b/src/library/scalax/collection/generic/VectorTemplate.scala new file mode 100644 index 0000000000..bc18ac45c2 --- /dev/null +++ b/src/library/scalax/collection/generic/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 + +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: Iterator[A] = 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) + } +} + diff --git a/src/library/scalax/collection/generic/covariant/IterableFactory.scala b/src/library/scalax/collection/generic/covariant/IterableFactory.scala new file mode 100755 index 0000000000..67445f54d9 --- /dev/null +++ b/src/library/scalax/collection/generic/covariant/IterableFactory.scala @@ -0,0 +1,14 @@ +package scalax.collection.generic.covariant + +trait IterableFactory[CC[+A] <: Iterable[A]] extends generic.IterableFactory[CC] { + + /** The empty collection of type CC */ + val empty: CC[Nothing] + + override protected def newBuilder[A]: Builder[CC, A] = + empty.newBuilder[A].asInstanceOf[Builder[CC, A]] + + /** Create CC collection of specified elements */ + override def apply[A](args: A*): CC[A] = + (empty ++ args.asInstanceOf[Iterable[A]]).asInstanceOf[CC[A]] // !!! +} diff --git a/src/library/scalax/collection/generic/covariant/IterableTemplate.scala b/src/library/scalax/collection/generic/covariant/IterableTemplate.scala new file mode 100755 index 0000000000..41155a5ad5 --- /dev/null +++ b/src/library/scalax/collection/generic/covariant/IterableTemplate.scala @@ -0,0 +1,29 @@ +/* __ *\ +** ________ ___ / / ___ 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.covariant + +import annotation.unchecked.uncheckedVariance + +/** 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 IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] + extends generic.IterableTemplate[CC, A @uncheckedVariance] { self /*: CC[A]*/ => } + +// !!! todo: explain why @uncheckedVariance is justified here. + diff --git a/src/library/scalax/collection/generic/covariant/IterableView.scala b/src/library/scalax/collection/generic/covariant/IterableView.scala new file mode 100755 index 0000000000..7ccad07405 --- /dev/null +++ b/src/library/scalax/collection/generic/covariant/IterableView.scala @@ -0,0 +1,21 @@ +/* __ *\ +** ________ ___ / / ___ 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.covariant + +import annotation.unchecked.uncheckedVariance + +/** 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 generic.IterableView[UC, A @uncheckedVariance] diff --git a/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala new file mode 100755 index 0000000000..449bac9cfc --- /dev/null +++ b/src/library/scalax/collection/generic/covariant/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.covariant + +import annotation.unchecked.uncheckedVariance + +trait OrderedIterableTemplate[+CC[+B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], +A] + extends generic.OrderedIterableTemplate[CC, A @uncheckedVariance] {self /*: CC[A]*/ => } diff --git a/src/library/scalax/collection/generic/covariant/SequenceFactory.scala b/src/library/scalax/collection/generic/covariant/SequenceFactory.scala new file mode 100755 index 0000000000..49a6e685fa --- /dev/null +++ b/src/library/scalax/collection/generic/covariant/SequenceFactory.scala @@ -0,0 +1,3 @@ +package scalax.collection.generic.covariant + +trait SequenceFactory[CC[+A] <: Sequence[A]] extends IterableFactory[CC] with generic.SequenceFactory[CC] diff --git a/src/library/scalax/collection/generic/covariant/SequenceTemplate.scala b/src/library/scalax/collection/generic/covariant/SequenceTemplate.scala new file mode 100755 index 0000000000..958e73cd47 --- /dev/null +++ b/src/library/scalax/collection/generic/covariant/SequenceTemplate.scala @@ -0,0 +1,17 @@ +/* __ *\ +** ________ ___ / / ___ 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.covariant + +import annotation.unchecked.uncheckedVariance + +trait SequenceTemplate[+CC[+B] <: SequenceTemplate[CC, B] with Sequence[B], +A] + extends generic.SequenceTemplate[CC, A @uncheckedVariance] {self /*: CC[A]*/ => } diff --git a/src/library/scalax/collection/generic/covariant/SequenceView.scala b/src/library/scalax/collection/generic/covariant/SequenceView.scala new file mode 100755 index 0000000000..cfcf9d4a25 --- /dev/null +++ b/src/library/scalax/collection/generic/covariant/SequenceView.scala @@ -0,0 +1,22 @@ +/* __ *\ +** ________ ___ / / ___ 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.covariant + +import annotation.unchecked.uncheckedVariance + +/** 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 generic.SequenceView[UC, A @uncheckedVariance] diff --git a/src/library/scalax/collection/generic/covariant/VectorTemplate.scala b/src/library/scalax/collection/generic/covariant/VectorTemplate.scala new file mode 100644 index 0000000000..1f75c68e82 --- /dev/null +++ b/src/library/scalax/collection/generic/covariant/VectorTemplate.scala @@ -0,0 +1,17 @@ +/* __ *\ +** ________ ___ / / ___ 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.covariant + +import annotation.unchecked.uncheckedVariance + +trait VectorTemplate[+CC[+B] <: VectorTemplate[CC, B] with Vector[B], +A] + extends generic.VectorTemplate[CC, A @uncheckedVariance] {self /*: CC[A]*/ => } 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 > 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><(e1: a, e2: a) => 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><(e1: a, e2: a) => Boolean</code>. + * @ex <pre> + * List("Steve", "Tom", "John", "Bob") + * .sort((e1, e2) => (e1 compareTo e2) < 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 < 0</code> + * or <code>length < 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 < 0</code> iff <code>this.length < len</code> + * <code>x == 0</code> iff <code>this.length == len</code> + * <code>x > 0</code> iff <code>this.length > 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 < 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) + } +} + diff --git a/src/library/scalax/collection/generic/mutable/VectorTemplate.scala b/src/library/scalax/collection/generic/mutable/VectorTemplate.scala new file mode 100644 index 0000000000..aafee3ae3b --- /dev/null +++ b/src/library/scalax/collection/generic/mutable/VectorTemplate.scala @@ -0,0 +1,55 @@ +/* __ *\ +** ________ ___ / / ___ 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.mutable + +import collection.mutable.Vector +import collection.mutable.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 nonvariant.VectorTemplate[CC, A] { +self => + + def update(idx: Int, elem: A) + + /** Creates a view of this iterable @see OrderedIterable.View + */ + override def view: VectorView[CC, A] = new VectorView[CC, A] { // !!! Martin: We should maybe infer the type parameters here? + val origin: Vector[_] = thisCC + val length: Int = self.length + def apply(idx: Int): A = self.apply(idx) + def update(idx: Int, elem: A) = self.update(idx, elem) + } + + /** A sub-sequence view starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + * @note The difference between `view` and `slice` is that `view` produces + * a view of the current sequence, whereas `slice` produces a new sequence. + * + * @note view(from, to) is equivalent to view.slice(from, to) + */ + override def view(from: Int, until: Int): VectorView[CC, A] = view.slice(from, until) + + def readOnly: Sequence[A] = new collection./*immutable.*/Vector[A] { //!!! + def length = self.length + def apply(idx : Int) = self.apply(idx) + def newBuilder[B]: Builder[CC, B] = self.newBuilder[B] + override def foreach(f: A => Unit) = self.foreach(f) + override def stringPrefix = self.stringPrefix+"RO" + } +} + diff --git a/src/library/scalax/collection/generic/mutable/VectorView.scala b/src/library/scalax/collection/generic/mutable/VectorView.scala new file mode 100644 index 0000000000..05a7bf6f5a --- /dev/null +++ b/src/library/scalax/collection/generic/mutable/VectorView.scala @@ -0,0 +1,95 @@ +/* __ *\ +** ________ ___ / / ___ 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.mutable + +import collection.mutable.Vector +import collection.mutable.Vector._ + +/** A non-strict projection of an iterable. + * @author Sean McDirmid + * @author Martin Odersky + * @note this should really be a virtual class of SequenceFactory + */ +trait VectorView[+UC[B] <: Vector[B], A] extends SequenceView[UC, A] with Vector[A] { +self => + + /** refined from Iterable.View */ + val origin: Vector[_] + + trait Transformed[B] extends super.Transformed[B] with VectorView[UC, B] { + override val origin = self + override def elements: Iterator[B] = new Elements(0, length) + override protected def asCC = asInstanceOf[VectorView[UC, B]] + } + + class Appended(that: Vector[A]) extends super.Appended[A](that) with Transformed[A] { + override def update(idx: Int, elem: A) { + val ll = self.length + if (idx < ll) self.update(idx, elem) else that.update(idx - ll, elem) + } + } + + class Sliced(from: Int, to: Int) extends super.Sliced(from, to) with Transformed[A] { + override def update(idx: Int, elem: A) { + if (idx >= 0 && idx < length) self.update(idx + from, elem) + else throw new IndexOutOfBoundsException(idx.toString) + } + override def slice(from1: Int, to1: Int) = + new self.Sliced(from + (from1 min length max 0) , to + (to1 min length max 0)) + } + + class Reversed extends super.Reversed with Transformed[A] { + override def update(idx: Int, elem: A) { + self.update(length - 1 - idx, elem) + } + } + + class Zipped[B](that: Vector[B]) extends super.Zipped[B](that) with Transformed[(A, B)] { + override def update(idx: Int, elem: (A, B)) { + self.update(idx, elem._1) + that.update(idx, elem._2) + } + } + + def ++(that: Vector[A]): VectorView[UC, A] = + new Appended(that).asCC + + override def reverse: VectorView[UC, A] = + (new Reversed).asCC + + private def toVector[B](xs: Iterable[B]): Vector[B] = xs match { + case ras: Vector[_] => ras.asInstanceOf[Vector[B]] + case _ => Vector() ++ xs + } + + override def zip[B](that: Iterable[B]): VectorView[UC, (A, B)] = + new Zipped(toVector(that)).asCC + + override def zipWithIndex: VectorView[UC, (A, Int)] = + zip((0 until length).asInstanceOf[Null]) // !!! + override def take(n: Int): VectorView[UC, A] = + slice(0, n) + override def drop(n: Int): VectorView[UC, A] = + slice(n, Math.MAX_INT) + override def splitAt(n: Int): (VectorView[UC, A], VectorView[UC, A]) = (take(n), drop(n)) + override def slice(from: Int, until: Int): VectorView[UC, A] = + new Sliced(from, until).asCC + override def takeWhile(p: A => Boolean): VectorView[UC, A] = + take(prefixLength(p)) + override def dropWhile(p: A => Boolean): VectorView[UC, A] = + drop(prefixLength(p)) + override def span(p: A => Boolean): (VectorView[UC, A], VectorView[UC, A]) = { + val n = prefixLength(p) + (take(n), drop(n)) + } +} + diff --git a/src/library/scalax/collection/generic/nonvariant/IterableFactory.scala b/src/library/scalax/collection/generic/nonvariant/IterableFactory.scala new file mode 100755 index 0000000000..a3786a246d --- /dev/null +++ b/src/library/scalax/collection/generic/nonvariant/IterableFactory.scala @@ -0,0 +1,3 @@ +package scalax.collection.generic.nonvariant + +trait IterableFactory[CC[A] <: Iterable[A]] extends generic.IterableFactory[CC] diff --git a/src/library/scalax/collection/generic/nonvariant/IterableTemplate.scala b/src/library/scalax/collection/generic/nonvariant/IterableTemplate.scala new file mode 100755 index 0000000000..cb4b5bdaac --- /dev/null +++ b/src/library/scalax/collection/generic/nonvariant/IterableTemplate.scala @@ -0,0 +1,24 @@ +/* __ *\ +** ________ ___ / / ___ 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.nonvariant + +/** 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 IterableTemplate[+CC[B] <: IterableTemplate[CC, B] with Iterable[B] , A] + extends generic.IterableTemplate[CC, A] { self /*: CC[A]*/ => } diff --git a/src/library/scalax/collection/generic/nonvariant/IterableView.scala b/src/library/scalax/collection/generic/nonvariant/IterableView.scala new file mode 100755 index 0000000000..66238b19ac --- /dev/null +++ b/src/library/scalax/collection/generic/nonvariant/IterableView.scala @@ -0,0 +1,19 @@ +/* __ *\ +** ________ ___ / / ___ 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.nonvariant + +/** 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 generic.IterableView[UC, A] diff --git a/src/library/scalax/collection/generic/nonvariant/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/nonvariant/OrderedIterableTemplate.scala new file mode 100755 index 0000000000..59358875a0 --- /dev/null +++ b/src/library/scalax/collection/generic/nonvariant/OrderedIterableTemplate.scala @@ -0,0 +1,15 @@ +/* __ *\ +** ________ ___ / / ___ 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.nonvariant + +trait OrderedIterableTemplate[+CC[B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], A] + extends generic.OrderedIterableTemplate[CC, A] {self /*: CC[A]*/ => } diff --git a/src/library/scalax/collection/generic/nonvariant/SequenceFactory.scala b/src/library/scalax/collection/generic/nonvariant/SequenceFactory.scala new file mode 100755 index 0000000000..5c658b0bfb --- /dev/null +++ b/src/library/scalax/collection/generic/nonvariant/SequenceFactory.scala @@ -0,0 +1,3 @@ +package scalax.collection.generic.nonvariant + +trait SequenceFactory[CC[A] <: Sequence[A]] extends IterableFactory[CC] with generic.SequenceFactory[CC] diff --git a/src/library/scalax/collection/generic/nonvariant/SequenceTemplate.scala b/src/library/scalax/collection/generic/nonvariant/SequenceTemplate.scala new file mode 100755 index 0000000000..7f9b2acd60 --- /dev/null +++ b/src/library/scalax/collection/generic/nonvariant/SequenceTemplate.scala @@ -0,0 +1,15 @@ +/* __ *\ +** ________ ___ / / ___ 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.nonvariant + +trait SequenceTemplate[+CC[B] <: SequenceTemplate[CC, B] with Sequence[B], A] + extends generic.SequenceTemplate[CC, A] {self /*: CC[A]*/ => } diff --git a/src/library/scalax/collection/generic/nonvariant/SequenceView.scala b/src/library/scalax/collection/generic/nonvariant/SequenceView.scala new file mode 100755 index 0000000000..46f5716ad4 --- /dev/null +++ b/src/library/scalax/collection/generic/nonvariant/SequenceView.scala @@ -0,0 +1,21 @@ +/* __ *\ +** ________ ___ / / ___ 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.nonvariant + + +/** 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 generic.SequenceView[UC, A] diff --git a/src/library/scalax/collection/generic/nonvariant/VectorTemplate.scala b/src/library/scalax/collection/generic/nonvariant/VectorTemplate.scala new file mode 100644 index 0000000000..7dfc4db64d --- /dev/null +++ b/src/library/scalax/collection/generic/nonvariant/VectorTemplate.scala @@ -0,0 +1,15 @@ +/* __ *\ +** ________ ___ / / ___ 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.nonvariant + +trait VectorTemplate[+CC[B] <: VectorTemplate[CC, B] with Vector[B], A] + extends generic.VectorTemplate[CC, A] {self /*: CC[A]*/ => } diff --git a/src/library/scalax/collection/immutable/List.scala b/src/library/scalax/collection/immutable/List.scala new file mode 100644 index 0000000000..366ae15d15 --- /dev/null +++ b/src/library/scalax/collection/immutable/List.scala @@ -0,0 +1,1222 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: List.scala 16287 2008-10-18 13:41:36Z nielsen $ + + +package scalax.collection.immutable + +import mutable.ListBuffer +import generic.covariant.SequenceTemplate + +/** A class representing an ordered collection of elements of type + * <code>a</code>. This class comes with two implementing case + * classes <code>scala.Nil</code> and <code>scala.::</code> that + * implement the abstract members <code>isEmpty</code>, + * <code>head</code> and <code>tail</code>. + * + * @author Martin Odersky and others + * @version 1.0, 16/07/2003 + */ +sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A] with Product { + + /** Returns true if the list does not contain any elements. + * @return <code>true</code>, iff the list is empty. + */ + def isEmpty: Boolean + + /** Returns this first element of the list. + * + * @return the first element of this list. + * @throws Predef.NoSuchElementException if the list is empty. + */ + def head: A + + /** Returns this list without its first element. + * + * @return this list without its first element. + * @throws Predef.NoSuchElementException if the list is empty. + */ + def tail: List[A] + + def newBuilder[B]: Builder[List, B] = new ListBuffer[B] + + /** <p> + * Add an element <code>x</code> at the beginning of this list. + * </p> + * + * @param x the element to prepend. + * @return the list with <code>x</code> added at the beginning. + * @ex <code>1 :: List(2, 3) = List(2, 3).::(1) = List(1, 2, 3)</code> + */ + def ::[B >: A] (x: B): List[B] = + new scalax.collection.immutable.::(x, this) + + /** <p> + * Returns a list resulting from the concatenation of the given + * list <code>prefix</code> and this list. + * </p> + * + * @param prefix the list to concatenate at the beginning of this list. + * @return the concatenation of the two lists. + * @ex <code>List(1, 2) ::: List(3, 4) = List(3, 4).:::(List(1, 2)) = List(1, 2, 3, 4)</code> + */ + def :::[B >: A](prefix: List[B]): List[B] = + if (isEmpty) prefix + else (new ListBuffer[B] ++ prefix).prependToList(this) + + /** Appends two list objects. + */ + override def ++[B >: A](that: Iterable[B]): List[B] = + this ::: that.toList + + /** Reverse the given prefix and append the current list to that. + * This function is equivalent to an application of <code>reverse</code> + * on the prefix followed by a call to <code>:::</code>, but more + * efficient (and tail recursive). + * + * @param prefix the prefix to reverse and then prepend + * @return the concatenation of the reversed prefix and the current list. + */ + def reverse_:::[B >: A](prefix: List[B]): List[B] = { + var these: List[B] = this + var pres = prefix + while (!pres.isEmpty) { + these = pres.head :: these + pres = pres.tail + } + these + } + + /** Returns the number of elements in the list. + * + * @return the number of elements in the list. + */ + def length: Int = { + var these = this + var len = 0 + while (!these.isEmpty) { + len += 1 + these = these.tail + } + len + } + + /** Returns the elements in the list as an iterator + * + * @return an iterator on the list elements. + */ + override def elements: Iterator[A] = new Iterator[A] { + var these = List.this + def hasNext: Boolean = !these.isEmpty + def next: A = + if (!hasNext) + throw new NoSuchElementException("next on empty Iterator") + else { + val result = these.head; these = these.tail; result + } + override def toList: List[A] = these + } + + /** Overrides the method in Iterable for efficiency. + * + * @return the list itself + */ + override def toList: List[A] = this + + /** Returns the <code>n</code> first elements of this list, or else the whole + * list, if it has less than <code>n</code> elements. + * + * @param n the number of elements to take. + * @return the <code>n</code> first elements of this list. + */ + override def take(n: Int): List[A] = { + val b = new ListBuffer[A] + var i = 0 + var these = this + while (!these.isEmpty && i < n) { + i += 1 + b += these.head + these = these.tail + } + if (these.isEmpty) this + else b.toList + } + + /** Returns the list with elements belonging to the given index range. + * + * @param start the start position of the list slice. + * @param end the end position (exclusive) of the list slice. + * @return the list with elements belonging to the given index range. + */ + override def slice(start: Int, end: Int): List[A] = { + val s = start max 0 + val e = end min this.length + drop(s) take (e - s) + } + + /** Returns the list without its <code>n</code> first elements. + * If this list has less than <code>n</code> elements, the empty list is returned. + * + * @param n the number of elements to drop. + * @return the list without its <code>n</code> first elements. + */ + override def drop(n: Int): List[A] = { + var these = this + var count = n + while (!these.isEmpty && count > 0) { + these = these.tail + count -= 1 + } + these + } + + /** Returns the rightmost <code>n</code> elements from this list. + * + * @param n the number of elements to take + * @return the suffix of length <code>n</code> of the list + */ + override def takeRight(n: Int): List[A] = { + def loop(lead: List[A], lag: List[A]): List[A] = lead match { + case Nil => lag + case _ :: tail => loop(tail, lag.tail) + } + loop(drop(n), this) + } + + /** Returns the list wihout its rightmost <code>n</code> elements. + * + * @param n the number of elements to take + * @return the list without its rightmost <code>n</code> elements + */ + override def dropRight(n: Int): List[A] = { + def loop(lead: List[A], lag: List[A]): List[A] = lead match { + case Nil => Nil + case _ :: tail => lag.head :: loop(tail, lag.tail) + } + loop(drop(n), this) + } + + /** Split the list at a given point and return the two parts thus + * created. + * + * @param n the position at which to split + * @return a pair of lists composed of the first <code>n</code> + * elements, and the other elements. + */ + override def splitAt(n: Int): (List[A], List[A]) = { + val b = new ListBuffer[A] + var i = 0 + var these = this + while (!these.isEmpty && i < n) { + i += 1 + b += these.head + these = these.tail + } + (b.toList, these) + } + + /** Returns the longest prefix of this list whose elements satisfy + * the predicate <code>p</code>. + * + * @param p the test predicate. + * @return the longest prefix of this list whose elements satisfy + * the predicate <code>p</code>. + */ + override def takeWhile(p: A => Boolean): List[A] = { + val b = new ListBuffer[A] + var these = this + while (!these.isEmpty && p(these.head)) { + b += these.head + these = these.tail + } + b.toList + } + + /** Returns the longest suffix of this list whose first element + * does not satisfy the predicate <code>p</code>. + * + * @param p the test predicate. + * @return the longest suffix of the list whose first element + * does not satisfy the predicate <code>p</code>. + */ + override def dropWhile(p: A => Boolean): List[A] = + if (isEmpty || !p(head)) this + else tail dropWhile p + + /** Returns 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. + */ + override def span(p: A => Boolean): (List[A], List[A]) = { + val b = new ListBuffer[A] + var these = this + while (!these.isEmpty && p(these.head)) { + b += these.head + these = these.tail + } + (b.toList, these) + } + + /** Returns the <code>n</code>-th element of this list. The first element + * (head of the list) is at position 0. + * + * @param n index of the element to return + * @return the element at position <code>n</code> in this list. + * @throws Predef.NoSuchElementException if the list is too short. + */ + def apply(n: Int): A = drop(n).head + + /** Returns the list resulting from applying the given function <code>f</code> to each + * element of this list. + * + * @param f function to apply to each element. + * @return <code>[f(a0), ..., f(an)]</code> if this list is <code>[a0, ..., an]</code>. + */ + final override def map[B](f: A => B): List[B] = { + val b = new ListBuffer[B] + var these = this + while (!these.isEmpty) { + b += f(these.head) + these = these.tail + } + b.toList + } + + /** Apply a function to all the elements of the list, and return the + * reversed list of results. This is equivalent to a call to <code>map</code> + * followed by a call to <code>reverse</code>, but more efficient. + * + * @param f the function to apply to each elements. + * @return the reversed list of results. + */ + def reverseMap[B](f: A => B): List[B] = { + def loop(l: List[A], res: List[B]): List[B] = l match { + case Nil => res + case head :: tail => loop(tail, f(head) :: res) + } + loop(this, Nil) + } + + /** Apply the given function <code>f</code> to each element of this list + * (while respecting the order of the elements). + * + * @param f the treatment to apply to each element. + */ + final override def foreach(f: A => Unit) { + var these = this + while (!these.isEmpty) { + f(these.head) + these = these.tail + } + } + + /** Returns all the elements of this list that satisfy the + * predicate <code>p</code>. The order of the elements is preserved. + * It is guarenteed that the receiver list 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>. + */ + final override def filter(p: A => Boolean): List[A] = { + // return same list if all elements satisfy p + var these = this + while (!these.isEmpty && p(these.head)) { + these = these.tail + } + if (these.isEmpty) this + else { + val b = new ListBuffer[A] + var these1 = this + while (these1 ne these) { + b += these1.head + these1 = these1.tail + } + + these = these.tail // prevent the second evaluation of the predicate + // on the element on which it first failed + while (!these.isEmpty) { + if (p(these.head)) b += these.head + these = these.tail + } + b.toList + } + } + + /** <p> + * Sort the list according to the comparison function + * <code><(e1: a, e2: a) => Boolean</code>, + * which should be true iff <code>e1</code> is smaller than + * <code>e2</code>. + * </p> + * + * @param lt the comparison function + * @return a list sorted according to the comparison function + * <code><(e1: a, e2: a) => Boolean</code>. + * @ex <pre> + * List("Steve", "Tom", "John", "Bob") + * .sort((e1, e2) => (e1 compareTo e2) < 0) = + * List("Bob", "John", "Steve", "Tom")</pre> + */ + def sort(lt : (A,A) => Boolean): List[A] = { + /** Merge two already-sorted lists */ + def merge(l1: List[A], l2: List[A]): List[A] = { + val res = new ListBuffer[A] + var left1 = l1 + var left2 = l2 + + while (!left1.isEmpty && !left2.isEmpty) { + if(lt(left1.head, left2.head)) { + res += left1.head + left1 = left1.tail + } else { + res += left2.head + left2 = left2.tail + } + } + + res ++= left1 + res ++= left2 + + res.toList + } + + /** Split a list into two lists of about the same size */ + def split(lst: List[A]) = { + val res1 = new ListBuffer[A] + val res2 = new ListBuffer[A] + var left = lst + + while (!left.isEmpty) { + res1 += left.head + left = left.tail + if (!left.isEmpty) { + res2 += left.head + left = left.tail + } + } + + (res1.toList, res2.toList) + } + + + /** Merge-sort the specified list */ + def ms(lst: List[A]): List[A] = + lst match { + case Nil => lst + case x :: Nil => lst + case x :: y :: Nil => + if (lt(x,y)) + lst + else + y :: x :: Nil + + case lst => + val (l1, l2) = split(lst) + val l1s = ms(l1) + val l2s = ms(l2) + merge(l1s, l2s) + } + + ms(this) + } + + /** Tests if the predicate <code>p</code> is satisfied by all elements + * in this list. + * + * @param p the test predicate. + * @return <code>true</code> iff all elements of this list satisfy the + * predicate <code>p</code>. + */ + override def forall(p: A => Boolean): Boolean = { + var these = this + while (!these.isEmpty) { + if (!p(these.head)) return false + these = these.tail + } + true + } + + /** Tests the existence in this list of an element that satisfies the + * predicate <code>p</code>. + * + * @param p the test predicate. + * @return <code>true</code> iff there exists an element in this list that + * satisfies the predicate <code>p</code>. + */ + override def exists(p: A => Boolean): Boolean = { + var these = this + while (!these.isEmpty) { + if (p(these.head)) return true + these = these.tail + } + false + } + + /** Find and return the first element of the list satisfying a + * predicate, if any. + * + * @param p the predicate + * @return the first element in the list satisfying <code>p</code>, + * or <code>None</code> if none exists. + */ + override def find(p: A => Boolean): Option[A] = { + var these = this + while (!these.isEmpty) { + if (p(these.head)) return Some(these.head) + these = these.tail + } + None + } + + /** Combines the elements of this list together using the binary + * function <code>f</code>, from left to right, and starting with + * the value <code>z</code>. + * + * @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>. + */ + override def foldLeft[B](z: B)(f: (B, A) => B): B = { + var acc = z + var these = this + while (!these.isEmpty) { + acc = f(acc, these.head) + these = these.tail + } + acc + } + + /** Combines the elements of this list together using the binary + * function <code>f</code>, from right to left, and starting with + * the value <code>z</code>. + * + * @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>. + */ + override def foldRight[B](z: B)(f: (A, B) => B): B = this match { + case Nil => z + case x :: xs => f(x, xs.foldRight(z)(f)) + } + + /** Combines the elements of this list together using the binary + * operator <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 list has elements + * <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>. + * @throws Predef.UnsupportedOperationException if the list is empty. + */ + override def reduceLeft[B >: A](f: (B, A) => B): B = this match { + case Nil => throw new UnsupportedOperationException("Nil.reduceLeft") + case x :: Nil => x + case x0 :: x1 :: xs => + var acc : B = f(x0, x1) + var these : List[A] = xs + while (!these.isEmpty) { + acc = f(acc, these.head) + these = these.tail + } + acc + } + + /** Combines the elements of this list together using the binary + * operator <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 list has elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., + * a<sub>n</sub></code>. + * + * @throws Predef.UnsupportedOperationException if the list is empty. + */ + override def reduceRight[B >: A](f: (A, B) => B): B = this match { + case Nil => throw new UnsupportedOperationException("Nil.reduceRight") + case x :: Nil => x + case x :: xs => f(x, xs reduceRight f) + } + + /** Applies the given function <code>f</code> to each element of + * this list, 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 list is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>. + */ + final override def flatMap[B](f: A => Iterable[B]): List[B] = { + val b = new ListBuffer[B] + var these = this + while (!these.isEmpty) { + var those = f(these.head).elements + while (those.hasNext) { + b += those.next + } + these = these.tail + } + b.toList + } + + /** A list consisting of all elements of this list in reverse order. + */ + override def reverse: List[A] = { + var result: List[A] = Nil + var these = this + while (!these.isEmpty) { + result = these.head :: result + these = these.tail + } + result + } + + /** Returns a list formed from this list and the specified list + * <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 lists is longer than the other, its remaining elements are ignored. + * + * @return <code>List((a<sub>0</sub>,b<sub>0</sub>), ..., + * (a<sub>min(m,n)</sub>,b<sub>min(m,n)</sub>))</code> when + * <code>List(a<sub>0</sub>, ..., a<sub>m</sub>) + * zip List(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked. + */ + def zip[B](that: List[B]): List[(A, B)] = { + val b = new ListBuffer[(A, B)] + var these = this + var those = that + while (!these.isEmpty && !those.isEmpty) { + b += ((these.head, those.head)) + these = these.tail + those = those.tail + } + b.toList + } + + /** Returns a list formed from this list and the specified list + * <code>that</code> by associating each element of the former with + * the element at the same position in the latter. + * + * @param that list <code>that</code> may have a different length + * as the self list. + * @param thisElem element <code>thisElem</code> is used to fill up the + * resulting list if the self list is shorter than + * <code>that</code> + * @param thatElem element <code>thatElem</code> is used to fill up the + * resulting list if <code>that</code> is shorter than + * the self list + * @return <code>List((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 > n</code>. + */ + def zipAll[B, C >: A, D >: B](that: List[B], thisElem: C, thatElem: D): List[(C, D)] = { + val b = new ListBuffer[(C, D)] + var these = this + var those = that + while (!these.isEmpty && !those.isEmpty) { + b += ((these.head, those.head)) + these = these.tail + those = those.tail + } + while (!these.isEmpty) { + b += ((these.head, thatElem)) + these = these.tail + } + while (!those.isEmpty) { + b += ((thisElem, those.head)) + those = those.tail + } + b.toList + } + + /** Computes the union of this list and the given list + * <code>that</code>. + * + * @param that the list of elements to add to the list. + * @return a list without doubles containing the elements of this + * list and those of the given list <code>that</code>. + */ + def union[B >: A](that: List[B]): List[B] = { + val b = new ListBuffer[B] + var these = this + while (!these.isEmpty) { + if (!that.contains(these.head)) b += these.head + these = these.tail + } + b.prependToList(that) + } + + /** Computes the difference between this list and the given list + * <code>that</code>. + * + * @param that the list of elements to remove from this list. + * @return this list without the elements of the given list + * <code>that</code>. + * @deprecated use <code>--</code> instead + */ + @deprecated + def diff[B >: A](that: List[B]): List[B] = this -- that + + /** Computes the difference between this list and the given list + * <code>that</code>. + * + * @param that the list of elements to remove from this list. + * @return this list without the elements of the given list + * <code>that</code>. + */ + def -- [B >: A](that: List[B]): List[B] = { + val b = new ListBuffer[B] + var these = this + while (!these.isEmpty) { + if (!that.contains(these.head)) b += these.head + these = these.tail + } + b.toList + } + + /** Computes the difference between this list and the given object + * <code>x</code>. + * + * @param x the object to remove from this list. + * @return this list without the elements of the given object + * <code>x</code>. + */ + def - [B >: A](x: B): List[B] = { + val b = new ListBuffer[B] + var these = this + while (!these.isEmpty) { + if (these.head != x) b += these.head + these = these.tail + } + b.toList + } + + /** Concatenate the elements of this list. The elements of this list + * should be a <code>Iterables</code>. + * + * Note: The compiler might not be able to infer the type parameter. + * + * @param f An implicit conversion to an <code>Iterable</code> instance. + * @return The concatenation of all elements of iterables in this list. + */ + def flatten[B](implicit f : A => Iterable[B]) : List[B] = { + val buf = new ListBuffer[B] + foreach(f(_).foreach(buf += _)) + buf.toList + } + + override def stringPrefix = "List" + + override def toStream : Stream[A] = null // !!! + /*new Stream.Definite[A] { + override def force : List[A] = List.this + override def isEmpty = List.this.isEmpty + override def head = List.this.head + override def tail = List.this.tail.toStream + protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder = if (!isEmpty) { + var prefix0 = prefix + var buf1 = buf.append(prefix0).append(head) + prefix0 = ", " + var tail0 = tail + while (!tail0.isEmpty) { + buf1 = buf.append(prefix0).append(tail0.head) + tail0 = tail0.tail + } + buf1 + } else buf + }*/ + +} + +/** The empty list. + * + * @author Martin Odersky + * @version 1.0, 15/07/2003 + */ +@SerialVersionUID(0 - 8256821097970055419L) +case object Nil extends List[Nothing] { + override def isEmpty = true + override def head: Nothing = + throw new NoSuchElementException("head of empty list") + override def tail: List[Nothing] = + throw new NoSuchElementException("tail of empty list") +} + +/** A non empty list characterized by a head and a tail. + * + * @author Martin Odersky + * @version 1.0, 15/07/2003 + */ +@SerialVersionUID(0L - 8476791151983527571L) +final case class ::[B](private var hd: B, private[scalax] var tl: List[B]) extends List[B] { + override def head : B = hd + override def tail : List[B] = tl + override def isEmpty: Boolean = false + + import java.io._ + + private def writeObject(out: ObjectOutputStream) { + var xs: List[B] = this + while (!xs.isEmpty) { out.writeObject(xs.head); xs = xs.tail } + out.writeObject(ListSerializeEnd) + } + + private def readObject(in: ObjectInputStream) { + hd = in.readObject.asInstanceOf[B] + assert(hd != ListSerializeEnd) + var current: ::[B] = this + while (true) in.readObject match { + case ListSerializeEnd => + current.tl = Nil + return + case a : Any => + val list : ::[B] = new ::(a.asInstanceOf[B], Nil) + current.tl = list + current = list + } + } +} + +/** Only used for list serialization */ +@SerialVersionUID(0L - 8476791151975527571L) +private[scalax] case object ListSerializeEnd +/** This object provides methods for creating specialized lists, and for + * transforming special kinds of lists (e.g. lists of lists). + * + * @author Martin Odersky and others + * @version 1.0, 15/07/2003 + */ +object List { + + /** Create a list with given elements. + * + * @param xs the elements to put in the list + * @return the list containing elements xs. + */ + def apply[A](xs: A*): List[A] = (xs.asInstanceOf[Iterable[A]]).toList // !!! + + /** for unapply matching + */ + def unapplySeq[A](x: List[A]): Some[List[A]] = Some(x) + + /** Create a sorted list of all integers in a range. + * + * @param from the start value of the list + * @param end the end value of the list + * @return the sorted list of all integers in range [from;end). + */ + def range(start: Int, end: Int): List[Int] = + range(start, end, 1) + + /** Create a list with element values + * <code>v<sub>n+1</sub> = v<sub>n</sub> + step</code> + * where <code>v<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 list + * @param end the end value of the list + * @param step the increment value of the list + * @return the sorted list of all integers in range [start;end). + */ + def range(start: Int, end: Int, step: Int): List[Int] = { + val b = new ListBuffer[Int] + var i = start + while ((step <= 0 || i < end) && (step >= 0 || i > end)) { + b += i + i += step + } + b.toList + } + + /** Create a sorted list with element values + * <code>v<sub>n+1</sub> = step(v<sub>n</sub>)</code> + * where <code>v<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 list + * @param end the end value of the list + * @param step the increment function of the list, must be monotonically increasing or decreasing + * @return the sorted list of all integers in range [start;end). + */ + def range(start: Int, end: Int, step: Int => Int): List[Int] = { + val up = step(start) > start + val down = step(start) < start + val b = new ListBuffer[Int] + var i = start + while ((!up || i < end) && (!down || i > end)) { + b += i + i += step(i) + } + b.toList + } + + /** Create a list containing several copies of an element. + * + * @param n the length of the resulting list + * @param elem the element composing the resulting list + * @return a list composed of n elements all equal to elem + */ + def make[A](n: Int, elem: A): List[A] = { + val b = new ListBuffer[A] + var i = 0 + while (i < n) { + b += elem + i += 1 + } + b.toList + } + + /** Create a list by applying a function to successive integers. + * + * @param n the length of the resulting list + * @param maker the procedure which, given an integer <code>n</code>, + * returns the nth element of the resulting list, where + * <code>n</code> is in interval <code>[0;n)</code>. + * @return the list obtained by applying the maker function to + * successive integers from 0 to n (exclusive). + */ + def tabulate[A](n: Int, maker: Int => A): List[A] = { + val b = new ListBuffer[A] + var i = 0 + while (i < n) { + b += maker(i) + i += 1 + } + b.toList + } + + /** Concatenate all the elements of a given list of lists. + * + * @param xss the list of lists that are to be concatenated + * @return the concatenation of all the lists + */ + def flatten[A](xss: List[List[A]]): List[A] = { + val b = new ListBuffer[A] + for (xs <- xss) { + var xc = xs + while (!xc.isEmpty) { + b += xc.head + xc = xc.tail + } + } + b.toList + } + + /** Concatenate all the argument lists into a single list. + * + * @param xss the lists that are to be concatenated + * @return the concatenation of all the lists + */ + def concat[A](xss: List[A]*): List[A] = { + val b = new ListBuffer[A] + for (xs <- xss) { + var xc = xs + while (!xc.isEmpty) { + b += xc.head + xc = xc.tail + } + } + b.toList + } + + /** Transforms a list of pairs into a pair of lists. + * + * @param xs the list of pairs to unzip + * @return a pair of lists. + */ + def unzip[A,B](xs: List[(A,B)]): (List[A], List[B]) = { + val b1 = new ListBuffer[A] + val b2 = new ListBuffer[B] + var xc = xs + while (!xc.isEmpty) { + b1 += xc.head._1 + b2 += xc.head._2 + xc = xc.tail + } + (b1.toList, b2.toList) + } + + /** Transforms an iterable of pairs into a pair of lists. + * + * @param xs the iterable of pairs to unzip + * @return a pair of lists. + */ + def unzip[A,B](xs: Iterable[(A,B)]): (List[A], List[B]) = + xs.foldRight[(List[A], List[B])]((Nil, Nil)) { + case ((x, y), (xs, ys)) => (x :: xs, y :: ys) + } + + /** + * Returns the <code>Left</code> values in the given <code>Iterable</code> of <code>Either</code>s. + */ + def lefts[A, B](es: Iterable[Either[A, B]]) = + es.foldRight[List[A]](Nil)((e, as) => e match { + case Left(a) => a :: as + case Right(_) => as + }) + + /** + * Returns the <code>Right</code> values in the given<code>Iterable</code> of <code>Either</code>s. + */ + def rights[A, B](es: Iterable[Either[A, B]]) = + es.foldRight[List[B]](Nil)((e, bs) => e match { + case Left(_) => bs + case Right(b) => b :: bs + }) + + /** Transforms an Iterable of Eithers into a pair of lists. + * + * @param xs the iterable of Eithers to separate + * @return a pair of lists. + */ + def separate[A,B](es: Iterable[Either[A,B]]): (List[A], List[B]) = + es.foldRight[(List[A], List[B])]((Nil, Nil)) { + case (Left(a), (lefts, rights)) => (a :: lefts, rights) + case (Right(b), (lefts, rights)) => (lefts, b :: rights) + } + + /** Converts an iterator to a list. + * + * @param it the iterator to convert + * @return a list that contains the elements returned by successive + * calls to <code>it.next</code> + */ + def fromIterator[A](it: Iterator[A]): List[A] = it.toList + + /** Converts an array into a list. + * + * @param arr the array to convert + * @return a list that contains the same elements than <code>arr</code> + * in the same order + */ + def fromArray[A](arr: Array[A]): List[A] = fromArray(arr, 0, arr.length) + + /** Converts a range of an array into a list. + * + * @param arr the array to convert + * @param start the first index to consider + * @param len the lenght of the range to convert + * @return a list that contains the same elements than <code>arr</code> + * in the same order + */ + def fromArray[A](arr: Array[A], start: Int, len: Int): List[A] = { + var res: List[A] = Nil + var i = start + len + while (i > start) { + i -= 1 + res = arr(i) :: res + } + res + } + + /** Parses a string which contains substrings separated by a + * separator character and returns a list of all substrings. + * + * @param str the string to parse + * @param separator the separator character + * @return the list of substrings + */ + def fromString(str: String, separator: Char): List[String] = { + var words: List[String] = Nil + var pos = str.length() + while (pos > 0) { + val pos1 = str.lastIndexOf(separator, pos - 1) + if (pos1 + 1 < pos) + words = str.substring(pos1 + 1, pos) :: words + pos = pos1 + } + words + } + + /** Returns the given string as a list of characters. + * + * @param str the string to convert. + * @return the string as a list of characters. + * @deprecated use <code>str.toList</code> instead + */ + @deprecated def fromString(str: String): List[Char] = + str.toList.asInstanceOf[List[Char]] // !!! + + /** Returns the given list of characters as a string. + * + * @param xs the list to convert. + * @return the list in form of a string. + */ + def toString(xs: List[Char]): String = { + val sb = new StringBuilder() + var xc = xs + while (!xc.isEmpty) { + sb.append(xc.head) + xc = xc.tail + } + sb.toString() + } + + /** Like xs map f, but returns <code>xs</code> unchanged if function + * <code>f</code> maps all elements to themselves. + * + * @param xs ... + * @param f ... + * @return ... + */ + def mapConserve[A <: AnyRef](xs: List[A])(f: A => A): List[A] = { + def loop(ys: List[A]): List[A] = + if (ys.isEmpty) xs + else { + val head0 = ys.head + val head1 = f(head0) + if (head1 eq head0) { + loop(ys.tail) + } else { + val ys1 = head1 :: mapConserve(ys.tail)(f) + if (xs eq ys) ys1 + else { + val b = new ListBuffer[A] + var xc = xs + while (xc ne ys) { + b += xc.head + xc = xc.tail + } + b.prependToList(ys1) + } + } + } + loop(xs) + } + + /** Returns the list resulting from applying the given function <code>f</code> + * to corresponding elements of the argument lists. + * + * @param f function to apply to each pair of elements. + * @return <code>[f(a0,b0), ..., f(an,bn)]</code> if the lists are + * <code>[a0, ..., ak]</code>, <code>[b0, ..., bl]</code> and + * <code>n = min(k,l)</code> + */ + def map2[A,B,C](xs: List[A], ys: List[B])(f: (A, B) => C): List[C] = { + val b = new ListBuffer[C] + var xc = xs + var yc = ys + while (!xc.isEmpty && !yc.isEmpty) { + b += f(xc.head, yc.head) + xc = xc.tail + yc = yc.tail + } + b.toList + } + + /** Returns the list resulting from applying the given function + * <code>f</code> to corresponding elements of the argument lists. + * + * @param f function to apply to each pair of elements. + * @return <code>[f(a<sub>0</sub>,b<sub>0</sub>,c<sub>0</sub>), + * ..., f(a<sub>n</sub>,b<sub>n</sub>,c<sub>n</sub>)]</code> + * if the lists are <code>[a<sub>0</sub>, ..., a<sub>k</sub>]</code>, + * <code>[b<sub>0</sub>, ..., b<sub>l</sub>]</code>, + * <code>[c<sub>0</sub>, ..., c<sub>m</sub>]</code> and + * <code>n = min(k,l,m)</code> + */ + def map3[A,B,C,D](xs: List[A], ys: List[B], zs: List[C])(f: (A, B, C) => D): List[D] = { + val b = new ListBuffer[D] + var xc = xs + var yc = ys + var zc = zs + while (!xc.isEmpty && !yc.isEmpty && !zc.isEmpty) { + b += f(xc.head, yc.head, zc.head) + xc = xc.tail + yc = yc.tail + zc = zc.tail + } + b.toList + } + + /** Tests whether the given predicate <code>p</code> holds + * for all corresponding elements of the argument lists. + * + * @param p function to apply to each pair of elements. + * @return <code>(p(a<sub>0</sub>,b<sub>0</sub>) && + * ... && p(a<sub>n</sub>,b<sub>n</sub>))]</code> + * if the lists are <code>[a<sub>0</sub>, ..., a<sub>k</sub>]</code>; + * <code>[b<sub>0</sub>, ..., b<sub>l</sub>]</code> + * and <code>n = min(k,l)</code> + */ + def forall2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = { + var xc = xs + var yc = ys + while (!xc.isEmpty && !yc.isEmpty) { + if (!f(xc.head, yc.head)) return false + xc = xc.tail + yc = yc.tail + } + true + } + + /** Tests whether the given predicate <code>p</code> holds + * for some corresponding elements of the argument lists. + * + * @param p function to apply to each pair of elements. + * @return <code>n != 0 && (p(a<sub>0</sub>,b<sub>0</sub>) || + * ... || p(a<sub>n</sub>,b<sub>n</sub>))]</code> if the lists are + * <code>[a<sub>0</sub>, ..., a<sub>k</sub>]</code>, + * <code>[b<sub>0</sub>, ..., b<sub>l</sub>]</code> and + * <code>n = min(k,l)</code> + */ + def exists2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = { + var xc = xs + var yc = ys + while (!xc.isEmpty && !yc.isEmpty) { + if (f(xc.head, yc.head)) return true + xc = xc.tail + yc = yc.tail + } + false + } + + /** Transposes a list of lists. + * pre: All element lists have the same length. + * + * @param xss the list of lists + * @return the transposed list of lists + */ + def transpose[A](xss: List[List[A]]): List[List[A]] = { + val buf = new ListBuffer[List[A]] + var yss = xss + while (!yss.head.isEmpty) { + buf += (yss map (_.head)) + yss = (yss map (_.tail)) + } + buf.toList + } + + /** Lists with ordered elements are ordered + implicit def list2ordered[a <% Ordered[a]](x: List[a]): Ordered[List[a]] = new Ordered[List[a]] { + def compare [b >: List[a] <% Ordered[b]](y: b): Int = y match { + case y1: List[a] => compareLists(x, y1); + case _ => -(y compare x) + } + private def compareLists(xs: List[a], ys: List[a]): Int = { + if (xs.isEmpty && ys.isEmpty) 0 + else if (xs.isEmpty) -1 + else if (ys.isEmpty) 1 + else { + val s = xs.head compare ys.head; + if (s != 0) s + else compareLists(xs.tail, ys.tail) + } + } + } + */ +} + diff --git a/src/library/scalax/collection/mutable/Appendable.scala b/src/library/scalax/collection/mutable/Appendable.scala new file mode 100644 index 0000000000..b8e8569a14 --- /dev/null +++ b/src/library/scalax/collection/mutable/Appendable.scala @@ -0,0 +1,94 @@ +/* __ *\ +** ________ ___ / / ___ 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.mutable + +/** This class represents collections that can be augmented using a += operator. + * + * @autor Martin Odersky + * @owner Martin Odersky + * @version 2.8 + */ +trait Appendable[A] { + + /** Append a single element to this buffer. + * + * @param elem the element to append. + */ + def +=(elem: A): Unit + + /** Append a two or more elements to this buffer. + * + * @param elem1 the first element to append. + * @param elem2 the second element to append. + * @param elems the remaining elements to append. + */ + def +=(elem1: A, elem2: A, elems: A*) { + this += elem1 + this += elem2 + this ++= elems.asInstanceOf[Iterable[A]] // !!! + } + + /** Appends a number of elements provided by an iterator + * + * @param iter the iterator. + */ + def ++=(iter: collection.Iterator[A]) { iter foreach += } + + /** Appends a number of elements provided by an iterable object + * via its <code>elements</code> method. + * + * @param iter the iterable object. + */ + def ++=(iter: collection.Iterable[A]) { iter foreach += } + + /** Append a single element to this buffer and return + * the identity of the buffer. + * + * @param elem the element to append. + */ + def +(elem: A): this.type = { this += elem; this } + + /** Append two or more elements to this buffer and return + * the identity of the buffer. + * + * @param elem1 the first element to append. + * @param elem2 the second element to append. + * @param elems the remaining elements to append. + */ + def +(elem1: A, elem2: A, elems: A*): this.type = + this + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]] // !!! + + /** Appends a number of elements provided by an iterable object + * via its <code>elements</code> method. The identity of the + * buffer is returned. + * + * @param iter the iterable object. + * @return the updated buffer. + */ + def ++(iter: Iterable[A]): this.type = { this ++= iter; this } + + /** Appends a number of elements provided by an iterator + * via its <code>elements</code> method. The identity of the + * buffer is returned. + * + * @param iter the iterator + * @return the updated buffer. + */ + def ++(iter: Iterator[A]): this.type = { this ++= iter; this } + + /** Clears the buffer contents. + */ + def clear() +} + + + + diff --git a/src/library/scalax/collection/mutable/ArrayBuffer.scala b/src/library/scalax/collection/mutable/ArrayBuffer.scala new file mode 100644 index 0000000000..3e4877cef7 --- /dev/null +++ b/src/library/scalax/collection/mutable/ArrayBuffer.scala @@ -0,0 +1,118 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ArrayBuffer.scala 15407 2008-06-20 09:26:36Z stepancheg $ + + +package scalax.collection.mutable + +/** An implementation of the <code>Buffer</code> class using an array to + * represent the assembled sequence internally. Append, update and random + * access take constant time (amortized time). Prepends and removes are + * linear in the buffer size. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 + */ +@serializable +class ArrayBuffer[A] extends Buffer[A] with Builder[ArrayBuffer, A] with ResizableArray[A] { + + def clear() { + size0 = 0 + } + + /** Appends a single element to this buffer and returns + * the identity of the buffer. It takes constant time. + * + * @param elem the element to append. + */ + def +=(elem: A) { + ensureSize(size0 + 1) + array(size0) = elem.asInstanceOf[AnyRef] + size0 += 1 + } + + /** Appends a number of elements provided by an iterable object + * via its <code>elements</code> method. The identity of the + * buffer is returned. + * + * @param iter the iterable object. + * @return the updated buffer. + */ + override def ++=(iter: Iterable[A]) { iter copyToBuffer this } + + /** Prepends a single element to this buffer and return + * the identity of the buffer. It takes time linear in + * the buffer size. + * + * @param elem the element to append. + * @return the updated buffer. + */ + def +:(elem: A): this.type = { + ensureSize(size0 + 1) + copy(0, 1, size0) + array(0) = elem.asInstanceOf[AnyRef] + size0 += 1 + this + } + + /** Prepends a number of elements provided by an iterable object + * via its <code>elements</code> method. The identity of the + * buffer is returned. + * + * @param iter the iterable object. + * @return the updated buffer. + */ + override def ++:(iter: Iterable[A]): this.type = { insertAll(0, iter); this } + + /** Inserts new elements at the index <code>n</code>. Opposed to method + * <code>update</code>, this method will not replace an element with a + * one. Instead, it will insert a new element at index <code>n</code>. + * + * @param n the index where a new element will be inserted. + * @param iter the iterable object providing all elements to insert. + * @throws Predef.IndexOutOfBoundsException if <code>n</code> is out of bounds. + */ + def insertAll(n: Int, iter: Iterable[A]) { + if ((n < 0) || (n > size0)) + throw new IndexOutOfBoundsException(n.toString) + val xs = iter.elements.toList + val len = xs.length + ensureSize(size0 + len) + copy(n, n + len, size0 - n) + xs.copyToArray(array.asInstanceOf[Array[Any]], n) + size0 += len + } + + /** Removes the element on a given index position. It takes time linear in + * the buffer size. + * + * @param n the index which refers to the element to delete. + * @return the updated array buffer. + * @throws Predef.IndexOutOfBoundsException if <code>n</code> is out of bounds. + */ + def remove(n: Int, count: Int) { + if ((n < 0) || (n >= size0)) + throw new IndexOutOfBoundsException(n.toString) + copy(n + count, n, size0 - (n + count)) + size0 -= count + } + + /** Return a clone of this buffer. + * + * @return an <code>ArrayBuffer</code> with the same elements. + */ + override def clone(): Buffer[A] = new ArrayBuffer[A] ++ this + + def result: ArrayBuffer[A] = this + + /** Defines the prefix of the string representation. + */ + override def stringPrefix: String = "ArrayBuffer" +} diff --git a/src/library/scalax/collection/mutable/Buffer.scala b/src/library/scalax/collection/mutable/Buffer.scala new file mode 100644 index 0000000000..c11fa37409 --- /dev/null +++ b/src/library/scalax/collection/mutable/Buffer.scala @@ -0,0 +1,264 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Buffer.scala 15799 2008-08-15 18:23:54Z odersky $ + + +package scalax.collection.mutable + +import generic.mutable.VectorTemplate + +/** Buffers are used to create sequences of elements incrementally by + * appending, prepending, or inserting new elements. It is also + * possible to access and modify elements in a random access fashion + * via the index of the element in the current sequence. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 + */ +@cloneable +trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable[A] +// with Scriptable[Message[(Location, A)]] + with CloneableCollection +{ + +// Abstract methods from Vector: + + /** Return element at index `n` + * @throws IndexOutofBoundsException if the index is not valid + */ + def apply(n: Int): A + + /** Return number of elements in the buffer + */ + def length: Int + + /** Create a new buffer of the same kind as this one */ + def newBuilder[B]: Builder[Buffer, B] = new ArrayBuffer[B] + + /** Replace element at index <code>n</code> with the new element + * <code>newelem</code>. + * + * @param n the index of the element to replace. + * @param newelem the new element. + * @throws IndexOutofBoundsException if the index is not valid + */ + def update(n: Int, newelem: A): Unit + +// Abstract methods from Appendable + + /** Append a single element to this buffer. + * + * @param elem the element to append. + */ + def +=(elem: A): Unit + + /** Clears the buffer contents. + */ + def clear() + +// Abstract methods new in this class + + /** Prepend a single element to this buffer and return + * the identity of the buffer. + * @param elem the element to prepend. + */ + def +:(elem: A): this.type + + /** Inserts new elements at the index <code>n</code>. Opposed to method + * <code>update</code>, this method will not replace an element with a + * one. Instead, it will insert a new element at index <code>n</code>. + * + * @param n the index where a new element will be inserted. + * @param iter the iterable object providing all elements to insert. + * @throws IndexOutofBoundsException if the index is not valid + */ + def insertAll(n: Int, iter: Iterable[A]): Unit + + /** Removes a number of elements from a given index position. + * + * @param n the index which refers to the element to delete. + * @param count the number of elements to delete + * @throws IndexOutofBoundsException if the index is not valid + */ + def remove(n: Int, count: Int): Unit + +// Concrete methods + + /** Removes the element on a given index position. + * + * @param n the index which refers to the element to delete. + */ + def remove(n: Int): A = { + val elem = this(n) + remove(n, 1) + elem + } + + /** Removes a single element from this buffer, at its first occurrence. + * If the list does not contain that element, it is unchanged + * + * @param x the element to remove. + */ + def -= (x: A) { + val i = indexOf(x) + if (i != -1) remove(i) + } + + /** Removes a single element from this buffer, at its first occurrence, + * and returns the identity of the buffer. + * If the buffer does not contain that element, it is unchanged + * + * @param x the element to remove. + */ + def - (x: A): this.type = { -=(x); this } + + /** Prepend two ore more elements to this buffer and return + * the identity of the buffer. + * @param elem the element to prepend. + */ + def +:(elem1: A, elem2: A, elems: A*): this.type = + elem1 +: elem2 +: (elems.asInstanceOf[Iterable[A]]) ++: this // !!! + + /** Prepends a number of elements provided by an iterable object + * via its <code>elements</code> method. The identity of the + * buffer is returned. + * + * @param iter the iterable object. + */ + def ++:(iter: Iterable[A]): this.type = { for (x <- iter) x +: this; this } + + /** Prepends a number of elements provided by an iterator + * The identity of the buffer is returned. + * + * @param iter the iterator + * @return the updated buffer. + */ + def ++:(iter: Iterator[A]): this.type = { for (x <- iter) x +: this; this } + + /** Appends a elements to this buffer. + * + * @param elems the elements to append. + */ + def append(elems: A*) { this ++= elems.asInstanceOf[Iterable[A]] } // !!! + + /** Appends a number of elements provided by an iterable object + * via its <code>elements</code> method. + * + * @param iter the iterable object. + */ + def appendAll(iter: Iterable[A]) { this ++= iter } + + /** Prepend given elements to this list. + * + * @param elem the element to prepend. + */ + def prepend(elems: A*) { elems.asInstanceOf[Iterable[A]] ++: this } // !!! + + /** Prepends a number of elements provided by an iterable object + * via its <code>elements</code> method. The identity of the + * buffer is returned. + * + * @param iter the iterable object. + */ + def prependAll(iter: Iterable[A]) { iter ++: this } + + /** Prepends a number of elements provided by an iterable object + * via its <code>elements</code> method. The identity of the + * buffer is returned. + * + * @param iter the iterable object. + */ + def prependAll(iter: Iterator[A]) { iter ++: this } + + /** Inserts new elements at the index <code>n</code>. Opposed to method + * <code>update</code>, this method will not replace an element with a + * one. Instead, it will insert the new elements at index <code>n</code>. + * + * @param n the index where a new element will be inserted. + * @param elems the new elements to insert. + */ + def insert(n: Int, elems: A*) { insertAll(n, elems.asInstanceOf[Iterable[A]]) } // !!! + + /** Removes the first <code>n</code> elements. + * + * @param n the number of elements to remove from the beginning + * of this buffer. + */ + def trimStart(n: Int) { remove(0, n) } + + /** Removes the last <code>n</code> elements. + * + * @param n the number of elements to remove from the end + * of this buffer. + */ + def trimEnd(n: Int) { remove(length - n max 0, n) } + + /** Send a message to this scriptable object. + * + * @param cmd the message to send. + * !!!! todo: rewrite location, msg etc with enumerations or else pack in a subpackage + def <<(cmd: Message[(Location, A)]) { + cmd match { + case Include((l, elem)) => l match { + case Start => prepend(elem) + case End => append(elem) + case Index(n) => insert(n, elem) + case _ => throw new UnsupportedOperationException("message " + cmd + " not understood") + } + case Update((l, elem)) => l match { + case Start => update(0, elem) + case End => update(length - 1, elem) + case Index(n) => update(n, elem) + case _ => throw new UnsupportedOperationException("message " + cmd + " not understood") + } + case Remove((l, _)) => l match { + case Start => remove(0) + case End => remove(length - 1) + case Index(n) => remove(n) + case _ => throw new UnsupportedOperationException("message " + cmd + " not understood") + } + case Reset() => clear + case s: Script[_] => s.elements foreach << + case _ => throw new UnsupportedOperationException("message " + cmd + " not understood") + } + } + */ + + /** Return a clone of this buffer. + * + * @return a buffer with the same elements. + */ + override def clone(): Buffer[A] = super.clone().asInstanceOf[Buffer[A]] + + /** Defines the prefix of the string representation. + */ + override def stringPrefix: String = "Buffer" + + /** Adds a number of elements in an array + * + * @param src the array + * @param start the first element to append + * @param len the number of elements to append + * @deprecated replace by: <code>buf ++= src.view(start, end)</code> + */ + @deprecated def ++=(src: Array[A], start: Int, len: Int) { + var i = start + val end = i + len + while (i < end) { + this += src(i) + i += 1 + } + } + +} + + + + diff --git a/src/library/scalax/collection/mutable/CloneableCollection.scala b/src/library/scalax/collection/mutable/CloneableCollection.scala new file mode 100644 index 0000000000..ab2c210134 --- /dev/null +++ b/src/library/scalax/collection/mutable/CloneableCollection.scala @@ -0,0 +1,19 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: CloneableCollection.scala 12003 2007-06-13 12:14:15Z mihaylov $ + + +package scalax.collection.mutable + +/** The J2ME version of the library defined this trait with a clone method + * to substitute for the lack of Object.clone there + */ +trait CloneableCollection { + override def clone(): AnyRef = super.clone() +} diff --git a/src/library/scalax/collection/mutable/ListBuffer.scala b/src/library/scalax/collection/mutable/ListBuffer.scala new file mode 100644 index 0000000000..adc8cbdb26 --- /dev/null +++ b/src/library/scalax/collection/mutable/ListBuffer.scala @@ -0,0 +1,288 @@ +/* __ *\ +** ________ ___ / / ___ 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.mutable + +import generic.SequenceForwarder +import immutable.List +import collection.immutable.{List, Nil, ::} + +/** A Buffer implementation back up by a list. It provides constant time + * prepend and append. Most other operations are linear. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 + */ +@serializable +final class ListBuffer[A] + extends Buffer[A] + with Builder[List, A] + with SequenceForwarder[A] +{ + private var start: List[A] = Nil + private var last0: ::[A] = _ + private var exported: Boolean = false + + protected def underlying: Sequence[A] = start + + // Implementations of abstract methods in Buffer + + /** Replaces element at index <code>n</code> with the new element + * <code>newelem</code>. Takes time linear in the buffer size. (except the first + * element, which is updated in constant time). + * + * @param n the index of the element to replace. + * @param x the new element. + * @throws Predef.IndexOutOfBoundsException if <code>n</code> is out of bounds. + */ + def update(n: Int, x: A) { + try { + if (exported) copy() + if (n == 0) { + val newElem = new :: (x, start.tail); + if (last0 eq start) last0 = newElem + start = newElem + } else { + var cursor = start + var i = 1 + while (i < n) { + cursor = cursor.tail + i += 1 + } + val newElem = new :: (x, cursor.tail.tail) + if (last0 eq cursor.tail) last0 = newElem + cursor.asInstanceOf[::[A]].tl = newElem + } + } catch { + case ex: Exception => throw new IndexOutOfBoundsException(n.toString()) + } + } + + /** Appends a single element to this buffer. This operation takes constant time. + * + * @param x the element to append. + */ + def += (x: A) { + if (exported) copy() + if (start.isEmpty) { + last0 = new :: (x, Nil) + start = last0 + } else { + val last1 = last0 + last0 = new :: (x, Nil) + last1.tl = last0 + } + } + + /** Clears the buffer contents. + */ + def clear() { + start = Nil + exported = false + } + + /** Prepends a single element to this buffer. This operation takes constant + * time. + * + * @param x the element to prepend. + * @return this buffer. + */ + def +: (x: A): this.type = { + if (exported) copy() + val newElem = new :: (x, start) + if (start.isEmpty) last0 = newElem + start = newElem + this + } + + /** Inserts new elements at the index <code>n</code>. Opposed to method + * <code>update</code>, this method will not replace an element with a new + * one. Instead, it will insert a new element at index <code>n</code>. + * + * @param n the index where a new element will be inserted. + * @param iter the iterable object providing all elements to insert. + * @throws Predef.IndexOutOfBoundsException if <code>n</code> is out of bounds. + */ + def insertAll(n: Int, iter: Iterable[A]) { + try { + if (exported) copy() + var elems = iter.elements.toList.reverse + if (n == 0) { + while (!elems.isEmpty) { + val newElem = new :: (elems.head, start) + if (start.isEmpty) last0 = newElem + start = newElem + elems = elems.tail + } + } else { + var cursor = start + var i = 1 + while (i < n) { + cursor = cursor.tail + i += 1 + } + while (!elems.isEmpty) { + val newElem = new :: (elems.head, cursor.tail) + if (cursor.tail.isEmpty) last0 = newElem + cursor.asInstanceOf[::[A]].tl = newElem + elems = elems.tail + } + } + } catch { + case ex: Exception => + throw new IndexOutOfBoundsException(n.toString()) + } + } + + /** Removes the element on a given index position. This operation takes time linear in + * the buffer size. + * + * @param n the index which refers to the element to delete. + * @return the updated array buffer. + * @throws Predef.IndexOutOfBoundsException if <code>n</code> is out of bounds. + */ + def remove(n: Int, count: Int) { + try { + if (exported) copy() + var old = start.head; + if (n == 0) { + var c = count + while (c > 0) { + start = start.tail + c -= 1 + } + } else { + var cursor = start + var i = 1 + while (i < n) { + cursor = cursor.tail + i += 1 + } + var c = count + while (c > 0) { + if (last0 eq cursor.tail) last0 = cursor.asInstanceOf[::[A]] + cursor.asInstanceOf[::[A]].tl = cursor.tail.tail + c -= 1 + } + } + old + } catch { + case ex: Exception => + throw new IndexOutOfBoundsException(n.toString()) + } + } + +// Implementation of abstract method in Builder + + def result = toList + + /** Converts this buffer to a list. Takes constant time. The buffer is + * copied lazily, the first time it is mutated. + */ + override def toList: List[A] = { + exported = !start.isEmpty + start + } + +// New methods in ListBuffer + + /** Prepends the elements of this buffer to a given list + * + * @param xs the list to which elements are prepended + */ + def prependToList(xs: List[A]): List[A] = + if (start.isEmpty) xs + else { last0.tl = xs; toList } + +// Overrides of methods in Buffer + + /** Removes the element on a given index position. Takes time linear in + * the buffer size (except for the first element, which is removed in constant + * time). + * + * @param n the index which refers to the element to delete. + * @return n the element that was formerly at position <code>n</code>. + * @pre an element exists at position <code>n</code> + * @throws Predef.IndexOutOfBoundsException if <code>n</code> is out of bounds. + */ + override def remove(n: Int): A = try { + if (exported) copy() + var old = start.head; + if (n == 0) { + start = start.tail + } else { + var cursor = start + var i = 1 + while (i < n) { + cursor = cursor.tail + i += 1 + } + old = cursor.tail.head + if (last0 eq cursor.tail) last0 = cursor.asInstanceOf[::[A]] + cursor.asInstanceOf[::[A]].tl = cursor.tail.tail + } + old + } catch { + case ex: Exception => + throw new IndexOutOfBoundsException(n.toString()) + } + + /** Remove a single element from this buffer. This operation takes linear time + * (except removing the first element, which is done in constant time). + * + * @param x the element to remove. + */ + override def -= (x: A) { + if (exported) copy() + if (start.isEmpty) {} + else if (start.head == x) start = start.tail + else { + var cursor = start + while (!cursor.tail.isEmpty && cursor.tail.head != x) { cursor = cursor.tail } + if (!cursor.tail.isEmpty) { + val z = cursor.asInstanceOf[::[A]] + if (z.tl == last0) + last0 = z + z.tl = cursor.tail.tail + } + } + } + + /** expose the underlying list but do not mark it as exported */ + override def readOnly : List[A] = start + + // Private methods + + /** Copy contents of this buffer */ + private def copy() { + var cursor = start + val limit = last0.tail + clear + while (cursor ne limit) { + this += cursor.head + cursor = cursor.tail + } + } + + /** Returns a clone of this buffer. + * + * @return a <code>ListBuffer</code> with the same elements. + */ + override def clone(): Buffer[A] = (new ListBuffer[A]) ++ this + + /** Defines the prefix of the string representation. + * + * @return the string representation of this buffer. + */ + override def stringPrefix: String = "ListBuffer" +} + diff --git a/src/library/scalax/collection/mutable/ResizableArray.scala b/src/library/scalax/collection/mutable/ResizableArray.scala new file mode 100644 index 0000000000..e4dd8bd47d --- /dev/null +++ b/src/library/scalax/collection/mutable/ResizableArray.scala @@ -0,0 +1,103 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ResizableArray.scala 15407 2008-06-20 09:26:36Z stepancheg $ + + +package scalax.collection.mutable + +/** This class is used internally to implement data structures that + * are based on resizable arrays. + * + * @author Matthias Zenger, Burak Emir + * @version 1.0, 03/05/2004 + */ +trait ResizableArray[A] extends Vector[A] { + + protected def initialSize: Int = 16 + protected var array: Array[AnyRef] = new Array[AnyRef](initialSize min 1) + + protected var size0: Int = 0 + + //########################################################################## + // implement/override methods of Vector[A] + + /** Returns the length of this resizable array. + */ + def length: Int = size0 + + def apply(idx: Int) = { + if (idx >= size0) throw new IndexOutOfBoundsException(idx.toString) + array(idx).asInstanceOf[A] + } + + def update(idx: Int, elem: A) { + if (idx >= size0) throw new IndexOutOfBoundsException(idx.toString) + array(idx) = elem.asInstanceOf[AnyRef] + } + + /** Fills the given array <code>xs</code> with the elements of + * this sequence starting at position <code>start</code>. + * + * @param xs the array to fill. + * @param start starting index. + */ + override def copyToArray[B >: A](xs: Array[B], start: Int) { + Array.copy(array, 0, xs, start, size0) + } + + /** Copy all elements to a buffer + * @param The buffer to which elements are copied + */ + override def copyToBuffer[B >: A](dest: Buffer[B]) { + dest ++= array.asInstanceOf[Iterable[A]] // !!! + } + + override def foreach(f: A => Unit) { + var i = 0 + while (i < size) { + f(array(i).asInstanceOf[A]) + i += 1 + } + } + + //########################################################################## + + /** remove elements of this array at indices after <code>sz</code> + */ + def reduceToSize(sz: Int) { + require(sz <= size0) + size0 = sz + } + + /** ensure that the internal array has at n cells */ + protected def ensureSize(n: Int) { + if (n > array.length) { + var newsize = array.length * 2 + while (n > newsize) + newsize = newsize * 2 + val newar: Array[AnyRef] = new Array(newsize) + Array.copy(array, 0, newar, 0, size0) + array = newar + } + } + + /** Swap two elements of this array. + */ + protected def swap(a: Int, b: Int) { + val h = array(a) + array(a) = array(b) + array(b) = h + } + + /** Move parts of the array. + */ + protected def copy(m: Int, n: Int, len: Int) { + Array.copy(array, m, array, n, len) + } +} diff --git a/src/library/scalax/collection/mutable/Vector.scala b/src/library/scalax/collection/mutable/Vector.scala new file mode 100644 index 0000000000..b181e93303 --- /dev/null +++ b/src/library/scalax/collection/mutable/Vector.scala @@ -0,0 +1,20 @@ +/* __ *\ +** ________ ___ / / ___ 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.mutable + +trait Vector[A] extends collection.Vector[A] with generic.mutable.VectorTemplate[Vector, A] + +object Vector extends generic.nonvariant.SequenceFactory[Vector] { + + /** The empty iterable */ + def apply[A](args: A*): Vector[A] = null // !!! + +} diff --git a/src/library/scalax/util/control/Break.scala b/src/library/scalax/util/control/Break.scala new file mode 100755 index 0000000000..173188d2e9 --- /dev/null +++ b/src/library/scalax/util/control/Break.scala @@ -0,0 +1,15 @@ +package scalax.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 => + } + } +} + |