diff options
Diffstat (limited to 'src/library/scalax')
35 files changed, 1391 insertions, 612 deletions
diff --git a/src/library/scalax/collection/Iterable.scala b/src/library/scalax/collection/Iterable.scala index b6abd8d559..8775fcb22a 100755 --- a/src/library/scalax/collection/Iterable.scala +++ b/src/library/scalax/collection/Iterable.scala @@ -12,6 +12,7 @@ package scalax.collection import generic._ +import collection.immutable.{List, Nil, ::} /** Collection classes mixing in this class provide a method * <code>elements</code> which returns an iterator over all the @@ -43,9 +44,9 @@ trait Iterable[+A] extends covariant.IterableTemplate[Iterable, A] { self => object Iterable extends covariant.IterableFactory[Iterable] { /** The empty iterable */ - val empty: Iterable[Nothing] = null // !!! + val empty: Iterable[Nothing] = Nil - class OrderedIterableOps[A](seq: Iterable[A], cmp: Ordering[A]) { + class ComparableIterableOps[A](seq: Iterable[A], cmp: Ordering[A]) { def min: A = { require(!seq.isEmpty, "min(<empty>)") var acc = seq.elements.next @@ -75,16 +76,32 @@ object Iterable extends covariant.IterableFactory[Iterable] { } } - class IterableIterableOps[C[+B] <: Iterable[B], A](self: C[Iterable[A]]) { + class IterableIterableOps[C[+B] <: Iterable[B] with covariant.IterableTemplate[C, B], A](self: C[C[A]]) { def flatten: C[A] = { - val b = self.newBuilder[A].asInstanceOf[Builder[C, A]] + val b: Builder[C, A] = self.newBuilder[A] for (xs <- self) b ++= xs b.result } + + def transpose: C[C[A]] = { + val bs: Array[Builder[C, A]] = self.head.map(_ => self.newBuilder[A]).toArray + for (xs <- self) { + var i = 0 + for (x <- xs) { + bs(i) += x + i += 1 + } + } + type CC[B] = C[C[B]] + val bb = self.newBuilder[C[A]] + for (b <- bs) bb += b.result + bb.result + } } - class PairCollectionOps[C[+B] <: Iterable[B], A1, A2](self: C[(A1, A2)]) { + + class PairIterableOps[C[+B] <: Iterable[B], A1, A2](self: C[(A1, A2)]) { def unzip: (C[A1], C[A2]) = { val as = self.newBuilder[A1].asInstanceOf[Builder[C, A1]] val bs = self.newBuilder[A2].asInstanceOf[Builder[C, A2]] @@ -96,14 +113,14 @@ object Iterable extends covariant.IterableFactory[Iterable] { } } - implicit def orderedIterableWrapper[A](seq: Iterable[A])(implicit cmp: Ordering[A]) = - new OrderedIterableOps(seq, cmp) + implicit def comparableIterableWrapper[A](seq: Iterable[A])(implicit cmp: Ordering[A]) = + new ComparableIterableOps(seq, cmp) implicit def numericIterableWrapper[A](seq: Iterable[A])(implicit num: Numeric[A]) = new NumericIterableOps(seq, num) - implicit def iterableIterableWrapper[C[+B] <: Iterable[B], A](seq: C[Iterable[A]]) = + implicit def iterableIterableWrapper[C[+B] <: Iterable[B] with covariant.IterableTemplate[C, B], A](seq: C[C[A]]) = new IterableIterableOps[C, A](seq) - implicit def pairCollectionWrapper[C[+B] <: Iterable[B], A1, A2](seq: C[(A1, A2)]) = - new PairCollectionOps[C, A1, A2](seq) + implicit def pairIterableWrapper[C[+B] <: Iterable[B], A1, A2](seq: C[(A1, A2)]) = + new PairIterableOps[C, A1, A2](seq) type View[+UC[+B] <: Sequence[B], +A] = covariant.IterableView[UC, A] diff --git a/src/library/scalax/collection/Iterator.scala b/src/library/scalax/collection/Iterator.scala index 2758faf854..20ba9ba820 100755 --- a/src/library/scalax/collection/Iterator.scala +++ b/src/library/scalax/collection/Iterator.scala @@ -12,7 +12,7 @@ package scalax.collection import mutable.{Buffer, ArrayBuffer, ListBuffer} -import immutable.{List, Nil, ::} +import immutable.{List, Nil, ::, Stream} /** The <code>Iterator</code> object provides various functions for * creating specialized iterators. @@ -28,7 +28,20 @@ object Iterator { def next(): Nothing = throw new NoSuchElementException("next on empty iterator") } - def apply[A](args: A*): Iterator[A] = args.asInstanceOf[Iterable[A]].elements // !!! + /** + * @param x the element + * @return the iterator with one single element + * @note Equivalent, but more efficient than Iterator(x) + */ + def single[A](x: A) = new Iterator[A] { + private var hasnext = true + def hasNext: Boolean = hasnext + def next(): A = + if (hasnext) { hasnext = false; x } + else empty.next() + } + + def apply[A](args: A*): Iterator[A] = args.asInstanceOf[Iterable[A]].elements // !@! /** Concatenate all the argument iterators into a single iterator. * @@ -36,7 +49,7 @@ object Iterator { * @return the concatenation of all the lists */ def concat[A](xss: Iterator[A]*): Iterator[A] = - xss.asInstanceOf[Iterable[Iterator[A]]].elements.flatten // !!! + xss.asInstanceOf[Iterable[Iterator[A]]].elements.flatten // !@! /** An iterator that returns the same element a number of times * @param len The number of elements returned @@ -152,32 +165,14 @@ object Iterator { */ def flatten: Iterator[A] = new Iterator[A] { private var it = its.next - def hasNext: Boolean = { - while (!it.hasNext && its.hasNext) it = its.next - it.hasNext - } - def next(): A = - if (hasNext) it.next - else empty.next() + def hasNext: Boolean = if (it.hasNext) { it = its.next; hasNext } else false + def next(): A = if (hasNext) it.next else empty.next() } } implicit def iteratorIteratorWrapper[A](its: Iterator[Iterator[A]]): IteratorIteratorOps[A] = new IteratorIteratorOps[A](its) - /** - * @param x the element - * @return the iterator with one single element - * @deprecated use Iterator(x) instead - */ - @deprecated def single[a](x: a) = new Iterator[a] { - private var hasnext = true - def hasNext: Boolean = hasnext - def next(): a = - if (hasnext) { hasnext = false; x } - else empty.next() - } - /** @deprecated use `xs.elements` instead */ @deprecated def fromValues[a](xs: a*) = xs.elements @@ -198,7 +193,7 @@ object Iterator { * @deprecated use `xs.slice(start, start + length).elements` instead */ @deprecated def fromArray[a](xs: Array[a], start: Int, length: Int): Iterator[a] = - xs.slice(start, start + length).elements.asInstanceOf[Iterator[a]] // !!! + xs.slice(start, start + length).elements.asInstanceOf[Iterator[a]] // !@! /** * @param str the given string @@ -206,7 +201,7 @@ object Iterator { * @deprecated replaced by <code>str.elements</code> */ @deprecated def fromString(str: String): Iterator[Char] = - str.elements.asInstanceOf[Iterator[Char]] // !!! + str.elements.asInstanceOf[Iterator[Char]] // !@! /** * @param n the product arity @@ -889,7 +884,7 @@ self => def toSequence: Sequence[A] = { val buffer = new ArrayBuffer[A] this copyToBuffer buffer - null // !!! should be: buffer.readOnly + buffer.readOnly } /** Collect elements into a seq. diff --git a/src/library/scalax/collection/LazyBuilder.scala b/src/library/scalax/collection/LazyBuilder.scala new file mode 100755 index 0000000000..784d437eba --- /dev/null +++ b/src/library/scalax/collection/LazyBuilder.scala @@ -0,0 +1,24 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $ + +package scalax.collection + +import collection.mutable.ListBuffer +import collection.immutable.{List, Nil, ::} + +abstract class LazyBuilder[+CC[B], A] extends Builder[CC, A] { + protected var parts = new ListBuffer[Iterator[A]] + def +=(x: A) = { parts += Iterator.single(x) } + override def ++=(xs: Iterator[A]) { parts += xs } + override def ++=(xs: Iterable[A]) { parts += xs.elements } + def elements: Iterator[A] = Iterator.iteratorIteratorWrapper(parts.elements).flatten // !!! drop the wrapper and get an error + def result: CC[A] + def clear() { parts.clear() } +} diff --git a/src/library/scalax/collection/OrderedIterable.scala b/src/library/scalax/collection/OrderedIterable.scala index 97bd96e667..bf28cbf083 100755 --- a/src/library/scalax/collection/OrderedIterable.scala +++ b/src/library/scalax/collection/OrderedIterable.scala @@ -12,6 +12,7 @@ package scalax.collection import generic._ +import immutable.Nil /** An ordered collection is a collection with a fixed sequence of elements * which corresponds to append order. In particular, it holds that @@ -36,6 +37,6 @@ trait OrderedIterable[+A] extends Iterable[A] with covariant.OrderedIterableTemp */ object OrderedIterable extends covariant.IterableFactory[OrderedIterable] { - val empty: OrderedIterable[Nothing] = null // !!! + val empty: OrderedIterable[Nothing] = Nil } diff --git a/src/library/scalax/collection/Sequence.scala b/src/library/scalax/collection/Sequence.scala index 0ee88e3575..e370684727 100755 --- a/src/library/scalax/collection/Sequence.scala +++ b/src/library/scalax/collection/Sequence.scala @@ -12,6 +12,7 @@ package scalax.collection import generic._ +import immutable.Nil /** Class <code>Sequence[A]</code> represents finite sequences of elements * of type <code>A</code>. @@ -25,7 +26,7 @@ trait Sequence[+A] extends OrderedIterable[A] with SizedIterable[A] with covaria object Sequence extends covariant.SequenceFactory[Sequence] { /** The empty sequence */ - val empty : Sequence[Nothing] = null // !!! + val empty : Sequence[Nothing] = immutable.Nil type View[+UC[+B] <: Sequence[B], +A] = covariant.SequenceView[UC, A] diff --git a/src/library/scalax/collection/Vector.scala b/src/library/scalax/collection/Vector.scala index 8787d7fd42..4e5df7e59d 100755 --- a/src/library/scalax/collection/Vector.scala +++ b/src/library/scalax/collection/Vector.scala @@ -11,11 +11,12 @@ package scalax.collection import generic._ +import mutable.ArrayBuffer trait Vector[+A] extends Sequence[A] with covariant.VectorTemplate[Vector, A] object Vector extends covariant.SequenceFactory[Vector] { /** The empty sequence */ - val empty : Vector[Nothing] = null // !!! + val empty : Vector[Nothing] = null // !!! todo: insert good immutable vector implementation here. } diff --git a/src/library/scalax/collection/generic/IterableFactory.scala b/src/library/scalax/collection/generic/IterableFactory.scala index 264e333ac5..1362e97079 100755 --- a/src/library/scalax/collection/generic/IterableFactory.scala +++ b/src/library/scalax/collection/generic/IterableFactory.scala @@ -8,6 +8,9 @@ trait IterableFactory[CC[A] <: Iterable[A]] { protected def newBuilder[A]: Builder[CC, A] = apply().newBuilder[A].asInstanceOf[Builder[CC, A]] + // can't have an empty here because it is defined in subclass covariant.IterableFactory with type + // CC[Nothing]. This type does not make sense for immutable iterables. + /** Concatenate all the argument lists into a single list. * * @param xss the lists that are to be concatenated diff --git a/src/library/scalax/collection/generic/IterableForwarder.scala b/src/library/scalax/collection/generic/IterableForwarder.scala index fba1e6d0e9..91e527dafa 100644 --- a/src/library/scalax/collection/generic/IterableForwarder.scala +++ b/src/library/scalax/collection/generic/IterableForwarder.scala @@ -12,7 +12,7 @@ package scalax.collection.generic import collection.mutable.Buffer -import collection.immutable.List +import collection.immutable.{List, Stream} /** This trait implements a forwarder for iterable objects. It forwards * all calls to a different iterable object, except for diff --git a/src/library/scalax/collection/generic/IterableTemplate.scala b/src/library/scalax/collection/generic/IterableTemplate.scala index 01a23f5ecf..e5e22aa7c8 100755 --- a/src/library/scalax/collection/generic/IterableTemplate.scala +++ b/src/library/scalax/collection/generic/IterableTemplate.scala @@ -12,7 +12,7 @@ package scalax.collection.generic import scalax.collection.mutable.{Buffer, ArrayBuffer, ListBuffer} -import scalax.collection.immutable.{List, Nil, ::} +import scalax.collection.immutable.{List, Nil, ::, Stream} import util.control.Break._ import Iterable._ @@ -65,7 +65,7 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], */ def hasDefiniteSize = true - /** Create a new sequence of type CC which contains all elements of this sequence + /** Create a new iterable of type CC which contains all elements of this iterable * followed by all elements of Iterable `that' */ def ++[B >: A](that: Iterable[B]): CC[B] = { @@ -75,7 +75,7 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], b.result } - /** Create a new sequence of type IterableType which contains all elements of this sequence + /** Create a new iterable of type CC which contains all elements of this iterable * followed by all elements of Iterator `that' */ def ++[B >: A](that: Iterator[B]): CC[B] = { @@ -85,12 +85,12 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], b.result } - /** Returns the sequence resulting from applying the given function - * <code>f</code> to each element of this sequence. + /** Returns the iterable resulting from applying the given function + * <code>f</code> to each element of this iterable. * * @param f function to apply to each element. * @return <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> if this - * sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. + * iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. */ def map[B](f: A => B): CC[B] = { val b = newBuilder[B] @@ -99,11 +99,11 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], } /** Applies the given function <code>f</code> to each element of - * this sequence, then concatenates the results. + * this iterable, then concatenates the results. * * @param f the function to apply on each element. * @return <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if - * this sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. + * this iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. */ def flatMap[B](f: A => Iterable[B]): CC[B] = { val b = newBuilder[B] @@ -111,10 +111,10 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], b.result } - /** Returns all the elements of this sequence that satisfy the + /** Returns all the elements of this iterable that satisfy the * predicate <code>p</code>. The order of the elements is preserved. - * @param p the predicate used to filter the list. - * @return the elements of this list satisfying <code>p</code>. + * @param p the predicate used to filter the iterable. + * @return the elements of this iterable satisfying <code>p</code>. */ def filter(p: A => Boolean): CC[A] = { val b = newBuilder[A] @@ -128,7 +128,7 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], * predicate inversed. * * @param p the predicate to use to test elements - * @return the list without all elements which satisfy <code>p</code> + * @return the iterable without all elements which satisfy <code>p</code> */ def remove(p: A => Boolean): CC[A] = filter(!p(_)) @@ -203,6 +203,8 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], * predicate, if any. * * @note may not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @param p the predicate * @return an option containing the first element in the iterable object * satisfying <code>p</code>, or <code>None</code> if none exists. @@ -221,8 +223,10 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], * the value <code>z</code>. * * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...), - * a<sub>n</sub>)</code> if the list is + * a<sub>n</sub>)</code> if the iterable is * <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>. */ def foldLeft[B](z: B)(op: (B, A) => B): B = { @@ -232,32 +236,40 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], result } - /** Combines the elements of this list together using the binary + /** Combines the elements of this iterable together using the binary * function <code>f</code>, from right to left, and starting with * the value <code>z</code>. * * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> - * if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. + * if the iterable is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. */ def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op) /** Similar to <code>foldLeft</code> but can be used as - * an operator with the order of list and zero arguments reversed. + * an operator with the order of iterable and zero arguments reversed. * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. */ def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) /** An alias for <code>foldRight</code>. * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. */ def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op) /** Combines the elements of this iterable object together using the binary * operator <code>op</code>, from left to right * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @param op The operator to apply * @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code> if the iterable object has elements @@ -277,6 +289,8 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], /** Combines the elements of this iterable object together using the binary * operator <code>op</code>, from right to left * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @param op The operator to apply * * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> @@ -288,7 +302,7 @@ trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], def reduceRight[B >: A](op: (A, B) => B): B = elements.reduceRight(op) - /** Returns an iterable formed from this iterable and the specified list + /** Returns an iterable formed from this iterable and the specified iterable * `other` by associating each element of the former with * the element at the same position in the latter. * If one of the two iterables is longer than the other, its remaining elements are ignored. @@ -356,7 +370,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the } /** Fills the given array <code>xs</code> with at most `len` elements of - * this sequence starting at position `start`. + * this iterable starting at position `start`. * Copying will stop oce either the end of the current iterable is reached or * `len` elements have been copied. * @@ -378,7 +392,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the } /** Fills the given array <code>xs</code> with the elements of - * this sequence starting at position <code>start</code> + * this iterable starting at position <code>start</code> * until either the end of the current iterable or the end of array `xs` is reached. * * @note Will not terminate for infinite-sized collections. @@ -411,7 +425,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * Returns a sequence containing all of the elements in this iterable object. * @note Will not terminate for infinite-sized collections. */ - def toSequence: Sequence[A] = toList.asInstanceOf[Sequence[A]] // !!! + def toSequence: Sequence[A] = toList /** @deprecated use toSequence instead */ @@ -431,7 +445,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * same order in the sorted iterable as in the original. * * @param lt the comparison function - * @return a list sorted according to the comparison function + * @return a iterable sorted according to the comparison function * <code><(e1: a, e2: a) => Boolean</code>. * @ex <pre> * List("Steve", "Tom", "John", "Bob") @@ -454,7 +468,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * <code>sep</code>. * * @ex <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code> - * @note Will not terminate for infinite-sized collections. * @param start starting string. * @param sep separator string. * @param end ending string. @@ -467,7 +480,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * representations of elements (w.r.t. the method <code>toString()</code>) * are separated by the string <code>sep</code>. * - * @note Will not terminate for infinite-sized collections. * @param sep separator string. * @return a string representation of this iterable object. */ @@ -475,7 +487,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the addString(new StringBuilder(), sep).toString /** Converts a collection into a flat <code>String</code> by each element's toString method. - * @note Will not terminate for infinite-sized collections. */ def mkString = addString(new StringBuilder()).toString @@ -485,7 +496,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * <code>end</code>. Inside, the string representations of elements (w.r.t. * the method <code>toString()</code>) are separated by the string * <code>sep</code>. - * @note Will not terminate for infinite-sized collections. */ def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = { b append start @@ -501,28 +511,13 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the /** Write all elements of this string into given string builder. * The string representations of elements (w.r.t. the method <code>toString()</code>) * are separated by the string <code>sep</code>. - * @note Will not terminate for infinite-sized collections. */ - def addString(b: StringBuilder, sep: String): StringBuilder = { - var first = true - for (x <- this) { - if (first) first = false - else b append sep - b append x - } - b - } + def addString(b: StringBuilder, sep: String): StringBuilder = addString(b, "", sep, "") /** Write all elements of this string into given string builder without using * any separator between consecutive elements. - * @note Will not terminate for infinite-sized collections. */ - def addString(b: StringBuilder): StringBuilder = { - for (x <- this) { - b append x - } - b - } + def addString(b: StringBuilder): StringBuilder = addString(b, "") /** * returns a projection that can be used to call non-strict <code>filter</code>, @@ -557,10 +552,10 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the // The following methods return non-deterministic results, unless this iterable is an OrderedIterable - /** The first element of this sequence. + /** The first element of this iterable. * * @note Might return different results for different runs, unless this iterable is ordered - * @throws Predef.NoSuchAentException if the sequence is empty. + * @throws Predef.NoSuchElementException if the iterable is empty. */ def head: A = if (isEmpty) throw new NoSuchElementException else elements.next @@ -574,7 +569,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the def headOption: Option[A] = if (isEmpty) None else Some(head) /** @deprecated use headOption instead - * <code>None</code> if list is empty. + * <code>None</code> if iterable is empty. */ @deprecated def firstOption: Option[A] = headOption @@ -589,7 +584,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * than <code>n</code> elements. * * @param n the number of elements to take - * @return a possibly projected sequence * @note Might return different results for different runs, unless this iterable is ordered */ def take(n: Int): CC[A] = { @@ -650,7 +644,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the /** The last element of this iterable. * - * @throws Predef.NoSuchElementException if the sequence is empty. + * @throws Predef.NoSuchElementException if the iterable is empty. * @note Might return different results for different runs, unless this iterable is ordered */ def last: A = { @@ -669,9 +663,11 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the def lastOption: Option[A] = if (isEmpty) None else Some(last) /** An iterable consisting of all elements of this iterable except the last one. + * @throws Predef.UnsupportedOperationException if the stream is empty. * @note Might return different results for different runs, unless this iterable is ordered */ def init: CC[A] = { + if (isEmpty) throw new UnsupportedOperationException("empty.init") var lst = head val b = newBuilder[A] for (x <- this) { @@ -732,12 +728,10 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the (l.result, r.result) } - /** Returns the longest prefix of this sequence whose elements satisfy + /** Returns the longest prefix of this iterable whose elements satisfy * the predicate <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] = { @@ -751,12 +745,10 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the b.result } - /** Returns the longest suffix of this sequence whose first element + /** Returns the longest suffix of this iterable whose first element * does not satisfy the predicate <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] = { @@ -769,12 +761,12 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the b.result } - /** Returns a pair consisting of the longest prefix of the list whose - * elements all satisfy the given predicate, and the rest of the list. + /** Returns a pair consisting of the longest prefix of the iterable whose + * elements all satisfy the given predicate, and the rest of the iterable. * * @param p the test predicate - * @return a pair consisting of the longest prefix of the list whose - * elements all satisfy <code>p</code>, and the rest of the list. + * @return a pair consisting of the longest prefix of the iterable whose + * elements all satisfy <code>p</code>, and the rest of the iterable. * @note Might return different results for different runs, unless this iterable is ordered */ def span(p: A => Boolean): (CC[A], CC[A]) = { @@ -801,13 +793,13 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the !these.hasNext && !those.hasNext } - /** A sub-sequence view starting at index `from` + /** A sub-iterable view starting at index `from` * and extending up to (but not including) index `until`. * * @param from The index of the first element of the slice * @param until The index of the element following the slice * @note The difference between `view` and `slice` is that `view` produces - * a view of the current sequence, whereas `slice` produces a new sequence. + * a view of the current iterable, whereas `slice` produces a new iterable. * * @note Might return different results for different runs, unless this iterable is ordered * @note view(from, to) is equivalent to view.slice(from, to) diff --git a/src/library/scalax/collection/generic/SequenceFactory.scala b/src/library/scalax/collection/generic/SequenceFactory.scala index ee97c80c75..26818c49c9 100755 --- a/src/library/scalax/collection/generic/SequenceFactory.scala +++ b/src/library/scalax/collection/generic/SequenceFactory.scala @@ -7,5 +7,5 @@ trait SequenceFactory[CC[A] <: Sequence[A]] extends IterableFactory[CC] { * @param x the selector value * @return sequence wrapped in an option, if this is a Sequence, otherwise none */ - def unapplySequence[A](x: CC[A]): Some[CC[A]] = Some(x) + def unapplySeq[A](x: CC[A]): Some[CC[A]] = Some(x) } diff --git a/src/library/scalax/collection/generic/SequenceTemplate.scala b/src/library/scalax/collection/generic/SequenceTemplate.scala index eba0e4bf98..b4a2c6f95a 100755 --- a/src/library/scalax/collection/generic/SequenceTemplate.scala +++ b/src/library/scalax/collection/generic/SequenceTemplate.scala @@ -53,13 +53,6 @@ self /*: CC[A]*/ => */ def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length) - /** Returns index of the first element satisying a predicate, or -1, if none exists. - * - * @note may not terminate for infinite-sized collections. - * @param p the predicate - */ - def indexWhere(p: A => Boolean): Int = indexWhere(p, 0) - /** Returns length of longest segment starting from a start index `from` * such that every element of the segment satisfies predicate `p`. * @note may not terminate for infinite-sized collections. @@ -85,6 +78,13 @@ self /*: CC[A]*/ => */ def prefixLength(p: A => Boolean) = segmentLength(p, 0) + /** Returns index of the first element satisfying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + */ + def indexWhere(p: A => Boolean): Int = indexWhere(p, 0) + /** Returns index of the first element starting from a start index * satisying a predicate, or -1, if none exists. * @@ -303,10 +303,8 @@ self /*: CC[A]*/ => b.result } - /** Returns a sequence of given length containing the elements of this sequence followed by zero - * or more occurrences of given elements. If this sequence is already at least as long as given - * length, it is returned directly. Otherwise, a new sequence is created consisting of the elements - * of this sequence followed by enough occurrences of the given elements to reach the given length. + /** Returns a new sequence of given length containing the elements of this sequence followed by zero + * or more occurrences of given elements. */ def padTo[B >: A](len: Int, elem: B): CC[B] = { var diff = len - length @@ -324,7 +322,7 @@ self /*: CC[A]*/ => * * @return the sequence itself */ - override def toSequence: Sequence[A] = this.asInstanceOf[Null] // !!! + override def toSequence: Sequence[A] = thisCC def indices: Range = 0 until length diff --git a/src/library/scalax/collection/generic/SequenceView.scala b/src/library/scalax/collection/generic/SequenceView.scala index 6178542241..43ce49d3a5 100755 --- a/src/library/scalax/collection/generic/SequenceView.scala +++ b/src/library/scalax/collection/generic/SequenceView.scala @@ -69,7 +69,7 @@ self => class Patched[/*+*/B >: A](from: Int, patch: Sequence[B], replaced: Int) extends Transformed[B] { val plen = patch.length - override def elements: Iterator[B] = self.elements patch (from, patch.asInstanceOf[Null], replaced) // !!! + override def elements: Iterator[B] = self.elements patch (from, patch, replaced) override def length: Int = self.length + plen - replaced override def apply(idx: Int): B = if (idx < from) self.apply(idx) @@ -101,7 +101,7 @@ self => override def zip[B](that: Iterable[B]): SequenceView[UC, (A, B)] = new Zipped(that.toSequence).asCC override def zipWithIndex: SequenceView[UC, (A, Int)] = - zip((0 until length).asInstanceOf[Null]) // !!! + zip((0 until length).asInstanceOf[Null]) // !@! /* override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): SequenceView[UC, (A1, B1)] = { val that1 = that.toSequence diff --git a/src/library/scalax/collection/generic/covariant/IterableFactory.scala b/src/library/scalax/collection/generic/covariant/IterableFactory.scala index 67445f54d9..0fd2284cea 100755 --- a/src/library/scalax/collection/generic/covariant/IterableFactory.scala +++ b/src/library/scalax/collection/generic/covariant/IterableFactory.scala @@ -7,8 +7,14 @@ trait IterableFactory[CC[+A] <: Iterable[A]] extends generic.IterableFactory[CC] override protected def newBuilder[A]: Builder[CC, A] = empty.newBuilder[A].asInstanceOf[Builder[CC, A]] + // the cast here is unavoidable because CC is not constrained with covariant.IterableTemplate[CC, A] + // It's can't be constrained because some suntype links between covariant and generic Templates + // are missing. That's a consequence of our hacks to have both nonvariant and covariant templates. /** Create CC collection of specified elements */ override def apply[A](args: A*): CC[A] = - (empty ++ args.asInstanceOf[Iterable[A]]).asInstanceOf[CC[A]] // !!! + (empty ++ args.asInstanceOf[Iterable[A]]).asInstanceOf[CC[A]] + // the cast here is unavoidable because CC is not constrained with covariant.IterableTemplate[CC, A] + // It's can't be constrained because some suntype links between covariant and generic Templates + // are missing. That's a consequence of our hacks to have both nonvariant and covariant templates. } diff --git a/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala index 449bac9cfc..38c1c2ab4c 100755 --- a/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala +++ b/src/library/scalax/collection/generic/covariant/OrderedIterableTemplate.scala @@ -13,5 +13,5 @@ package scalax.collection.generic.covariant import annotation.unchecked.uncheckedVariance -trait OrderedIterableTemplate[+CC[+B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], +A] +trait OrderedIterableTemplate[+CC[+B] <: OrderedIterable[B] with OrderedIterableTemplate[CC, B], +A] extends generic.OrderedIterableTemplate[CC, A @uncheckedVariance] {self /*: CC[A]*/ => } diff --git a/src/library/scalax/collection/generic/covartest/IterableForwarder.scala b/src/library/scalax/collection/generic/covartest/IterableForwarder.scala new file mode 100755 index 0000000000..9d78cb18e0 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/IterableForwarder.scala @@ -0,0 +1,61 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: IterableProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $ + + +package scalax.collection.generic.covartest + +import collection.mutable.Buffer +import collection.immutable.{List, Stream} + +/** This trait implements a forwarder for iterable objects. It forwards + * all calls to a different iterable object, except for + * + * - toString, hashCode, equals, stringPrefix + * - newBuilder, view + * - all calls creating a new iterable objetc of the same kind + * + * The above methods are forwarded by subclass IterableProxy + * + * @author Martin Odersky + * @version 2.8 + */ +trait IterableForwarder[+A] extends Iterable[A] { + + /** The iterable object to which calls are forwarded */ + protected def underlying: Iterable[A] + + // Iterable delegates + // Iterable methods could be printed by cat IterableTemplate.scala | sed -n '/trait Iterable/,$ p' | egrep '^ (override )?def' + + override def elements = underlying.elements + override def isEmpty = underlying.isEmpty + override def hasDefiniteSize = underlying.hasDefiniteSize + override def foreach(f: A => Unit) = underlying.foreach(f) + override def forall(p: A => Boolean): Boolean = underlying.forall(p) + override def exists(p: A => Boolean): Boolean = underlying.exists(p) + override def count(p: A => Boolean): Int = underlying.count(p) + override def find(p: A => Boolean): Option[A] = underlying.find(p) + override def foldLeft[B](z: B)(op: (B, A) => B): B = underlying.foldLeft(z)(op) + override def foldRight[B](z: B)(op: (A, B) => B): B = underlying.foldRight(z)(op) + override def reduceLeft[B >: A](op: (B, A) => B): B = underlying.reduceLeft(op) + override def reduceRight[B >: A](op: (A, B) => B): B = underlying.reduceRight(op) + override def copyToBuffer[B >: A](dest: Buffer[B]) = underlying.copyToBuffer(dest) + override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) = underlying.copyToArray(xs, start, len) + override def toArray[B >: A]: Array[B] = underlying.toArray + override def toList: List[A] = underlying.toList + override def toSequence: Sequence[A] = underlying.toSequence + override def toStream: Stream[A] = underlying.toStream + override def mkString(start: String, sep: String, end: String): String = underlying.mkString(start, sep, end) + override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = underlying.addString(b, start, sep, end) + + override def head: A = underlying.head + override def last: A = underlying.last + override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that) +} diff --git a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala index b83f3b9247..eb4281b427 100755 --- a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala +++ b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala @@ -12,7 +12,7 @@ package scalax.collection.generic.covartest import scalax.collection.mutable.{Buffer, ArrayBuffer, ListBuffer} -import scalax.collection.immutable.{List, Nil, ::} +import scalax.collection.immutable.{List, Nil, ::, Stream} import util.control.Break._ import Iterable._ @@ -411,7 +411,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * Returns a sequence containing all of the elements in this iterable object. * @note Will not terminate for infinite-sized collections. */ - def toSequence: Sequence[A] = toList.asInstanceOf[Sequence[A]] // !!! + def toSequence: Sequence[A] = toList /** @deprecated use toSequence instead */ diff --git a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala index c6be1a5acd..5256a4e40d 100755 --- a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala +++ b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala @@ -13,5 +13,11 @@ package scalax.collection.generic.covartest import OrderedIterable._ +/** Ordered iterables are iterables where the `elements` method always returns elements in the same + * order (namely the order in which elements were appended to the iterable). In particular, one has + * for every two ordered iterables `xs` and `ys`: + * + * `(xs ++ ys).elements = xs.elements ++ ys.elements + */ trait OrderedIterableTemplate[+CC[+B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], +A] extends IterableTemplate[CC, A] diff --git a/src/library/scalax/collection/generic/covartest/SequenceFactory.scala b/src/library/scalax/collection/generic/covartest/SequenceFactory.scala index 1fb85d02db..eb6c093bff 100755 --- a/src/library/scalax/collection/generic/covartest/SequenceFactory.scala +++ b/src/library/scalax/collection/generic/covartest/SequenceFactory.scala @@ -7,5 +7,5 @@ trait SequenceFactory[CC[A] <: Sequence[A]] extends IterableFactory[CC] { * @param x the selector value * @return sequence wrapped in an option, if this is a Sequence, otherwise none */ - def unapplySequence[A](x: CC[A]): Some[CC[A]] = Some(x) + def unapplySeq[A](x: CC[A]): Some[CC[A]] = Some(x) } diff --git a/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala b/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala new file mode 100644 index 0000000000..d5ba7ea063 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala @@ -0,0 +1,50 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: SeqProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $ + + +package scalax.collection.generic.covartest + +/** This class implements a forwarder for sequences. It forwards + * all calls to a different sequence object except for + * + * - toString, hashCode, equals, stringPrefix + * - newBuilder, view, toSequence + * - all calls creating a new iterable objetc of the same kind + * + * The above methods are forwarded by subclass SequenceProxy + * + * @author Martin Odersky + * @version 2.8 + */ +trait SequenceForwarder[+A] extends Sequence[A] with IterableForwarder[A] { + + protected override def underlying: Sequence[A] + + // PartialFunction delegates + + override def apply(i: Int): A = underlying.apply(i) + override def isDefinedAt(x: Int): Boolean = underlying.isDefinedAt(x) + + // Sequence delegates + // Sequence methods could be printed by cat SequenceTemplate.scala | sed -n '/trait Seq/,$ p' | egrep '^ (override )?def' + + override def length: Int = underlying.length + override def lengthCompare(l: Int) = underlying lengthCompare l + override def segmentLength(p: A => Boolean, from: Int): Int = underlying.segmentLength(p, from) + override def prefixLength(p: A => Boolean) = underlying.prefixLength(p) + override def indexWhere(p: A => Boolean, from: Int): Int = underlying.indexWhere(p, from) + override def indexOf[B >: A](elem: B, from: Int): Int = underlying.indexOf(elem, from) + override def reversedElements: Iterator[A] = underlying.reversedElements + override def startsWith[B](that: Sequence[B], offset: Int): Boolean = underlying.startsWith(that, offset) + override def endsWith[B](that: Sequence[B]): Boolean = underlying.endsWith(that) + override def indexOf[B >: A](that: Sequence[B]): Int = underlying.indexOf(that) + override def contains(elem: Any): Boolean = underlying.contains(elem) + override def indices: Range = underlying.indices +} diff --git a/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala index bf1915edf0..ffc4c3d8f7 100755 --- a/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala +++ b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala @@ -324,7 +324,7 @@ self /*: CC[A]*/ => * * @return the sequence itself */ - override def toSequence: Sequence[A] = this.asInstanceOf[Null] // !!! + override def toSequence: Sequence[A] = thisCC def indices: Range = 0 until length diff --git a/src/library/scalax/collection/generic/covartest/SequenceView.scala b/src/library/scalax/collection/generic/covartest/SequenceView.scala index 48477cf6e7..09d5c0efa1 100755 --- a/src/library/scalax/collection/generic/covartest/SequenceView.scala +++ b/src/library/scalax/collection/generic/covartest/SequenceView.scala @@ -69,7 +69,7 @@ self => class Patched[+B >: A](from: Int, patch: Sequence[B], replaced: Int) extends Transformed[B] { val plen = patch.length - override def elements: Iterator[B] = self.elements patch (from, patch.asInstanceOf[Null], replaced) // !!! + override def elements: Iterator[B] = self.elements patch (from, patch, replaced) override def length: Int = self.length + plen - replaced override def apply(idx: Int): B = if (idx < from) self.apply(idx) @@ -101,7 +101,7 @@ self => override def zip[B](that: Iterable[B]): SequenceView[UC, (A, B)] = new Zipped(that.toSequence).asCC override def zipWithIndex: SequenceView[UC, (A, Int)] = - zip((0 until length).asInstanceOf[Null]) // !!! + zip((0 until length).asInstanceOf[Null]) // !@! /* override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): SequenceView[UC, (A1, B1)] = { val that1 = that.toSequence diff --git a/src/library/scalax/collection/generic/covartest/VectorTemplate.scala b/src/library/scalax/collection/generic/covartest/VectorTemplate.scala index 0771b078d9..6e44b6a6c5 100644 --- a/src/library/scalax/collection/generic/covartest/VectorTemplate.scala +++ b/src/library/scalax/collection/generic/covartest/VectorTemplate.scala @@ -208,7 +208,7 @@ self => b.result } - override def reversedElements = new Iterator[A] { + override def reversedElements: Iterator[A] = new Iterator[A] { var i = length def hasNext: Boolean = 0 < i def next: A = diff --git a/src/library/scalax/collection/generic/mutable/VectorTemplate.scala b/src/library/scalax/collection/generic/mutable/VectorTemplate.scala index aafee3ae3b..747cd01a4c 100644 --- a/src/library/scalax/collection/generic/mutable/VectorTemplate.scala +++ b/src/library/scalax/collection/generic/mutable/VectorTemplate.scala @@ -44,7 +44,7 @@ self => */ override def view(from: Int, until: Int): VectorView[CC, A] = view.slice(from, until) - def readOnly: Sequence[A] = new collection./*immutable.*/Vector[A] { //!!! + def readOnly: Sequence[A] = new collection.immutable.Vector[A] { //!!! def length = self.length def apply(idx : Int) = self.apply(idx) def newBuilder[B]: Builder[CC, B] = self.newBuilder[B] diff --git a/src/library/scalax/collection/generic/mutable/VectorView.scala b/src/library/scalax/collection/generic/mutable/VectorView.scala index 05a7bf6f5a..caebcb567f 100644 --- a/src/library/scalax/collection/generic/mutable/VectorView.scala +++ b/src/library/scalax/collection/generic/mutable/VectorView.scala @@ -75,7 +75,7 @@ self => new Zipped(toVector(that)).asCC override def zipWithIndex: VectorView[UC, (A, Int)] = - zip((0 until length).asInstanceOf[Null]) // !!! + zip((0 until length).asInstanceOf[Null]) // !@! override def take(n: Int): VectorView[UC, A] = slice(0, n) override def drop(n: Int): VectorView[UC, A] = diff --git a/src/library/scalax/collection/immutable/Iterable.scala b/src/library/scalax/collection/immutable/Iterable.scala new file mode 100644 index 0000000000..c299518d1b --- /dev/null +++ b/src/library/scalax/collection/immutable/Iterable.scala @@ -0,0 +1,22 @@ +package scalax.collection.immutable + +import generic.covariant + +/** Collection classes mixing in this class provide a method + * <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 collection.Iterable[A] + +object Iterable extends covariant.IterableFactory[Iterable] { + val empty: Iterable[Nothing] = Nil +} + + diff --git a/src/library/scalax/collection/immutable/List.scala b/src/library/scalax/collection/immutable/List.scala index 366ae15d15..d5cecad27f 100644 --- a/src/library/scalax/collection/immutable/List.scala +++ b/src/library/scalax/collection/immutable/List.scala @@ -12,7 +12,7 @@ package scalax.collection.immutable import mutable.ListBuffer -import generic.covariant.SequenceTemplate +import generic.covariant.{SequenceTemplate, SequenceFactory} /** A class representing an ordered collection of elements of type * <code>a</code>. This class comes with two implementing case @@ -21,9 +21,11 @@ import generic.covariant.SequenceTemplate * <code>head</code> and <code>tail</code>. * * @author Martin Odersky and others - * @version 1.0, 16/07/2003 + * @version 2.8 */ -sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A] with Product { +sealed abstract class List[+A] extends Stream[A] with SequenceTemplate[List, A] with Product { + + import collection.{Iterable, OrderedIterable, Sequence, Vector} /** Returns true if the list does not contain any elements. * @return <code>true</code>, iff the list is empty. @@ -44,7 +46,10 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A */ def tail: List[A] - def newBuilder[B]: Builder[List, B] = new ListBuffer[B] + /** Creates a list buffer as builder for this class */ + override def newBuilder[B]: Builder[List, B] = new ListBuffer[B] + + // New methods in List /** <p> * Add an element <code>x</code> at the beginning of this list. @@ -70,15 +75,10 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A if (isEmpty) prefix else (new ListBuffer[B] ++ prefix).prependToList(this) - /** Appends two list objects. - */ - override def ++[B >: A](that: Iterable[B]): List[B] = - this ::: that.toList - /** Reverse the given prefix and append the current list to that. * This function is equivalent to an application of <code>reverse</code> - * on the prefix followed by a call to <code>:::</code>, but more - * efficient (and tail recursive). + * on the prefix followed by a call to <code>:::</code>, but is more + * efficient. * * @param prefix the prefix to reverse and then prepend * @return the concatenation of the reversed prefix and the current list. @@ -93,36 +93,57 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A these } - /** Returns the number of elements in the list. - * - * @return the number of elements in the list. + /** Apply a function to all the elements of the list, and return the + * reversed list of results. This is equivalent to a call to <code>map</code> + * followed by a call to <code>reverse</code>, but more efficient. + * !!! should we deprecate this? Why have reverseMap, but not filterMap, say? + * @param f the function to apply to each elements. + * @return the reversed list of results. */ - def length: Int = { - var these = this - var len = 0 - while (!these.isEmpty) { - len += 1 - these = these.tail + def reverseMap[B](f: A => B): List[B] = { + def loop(l: List[A], res: List[B]): List[B] = l match { + case Nil => res + case head :: tail => loop(tail, f(head) :: res) } - len + loop(this, Nil) } - /** Returns the elements in the list as an iterator - * - * @return an iterator on the list elements. + /** Like xs map f, but returns <code>xs</code> unchanged if function + * <code>f</code> maps all elements to themselves (wrt eq) + * @note Unlike `map`, `mapConserve` is not tail-recursive */ - override def elements: Iterator[A] = new Iterator[A] { - var these = List.this - def hasNext: Boolean = !these.isEmpty - def next: A = - if (!hasNext) - throw new NoSuchElementException("next on empty Iterator") + def mapConserve[B >: A] (f: A => B): List[B] = { + def loop(ys: List[A]): List[B] = + if (ys.isEmpty) this else { - val result = these.head; these = these.tail; result + val head0 = ys.head + val head1 = f(head0) + if (head1.asInstanceOf[AnyRef] eq head0.asInstanceOf[AnyRef]) { + loop(ys.tail) + } else { + val ys1 = head1 :: ys.tail.mapConserve(f) + if (this eq ys) ys1 + else { + val b = new ListBuffer[B] + var xc = this + while (xc ne ys) { + b += xc.head + xc = xc.tail + } + b.prependToList(ys1) + } + } } - override def toList: List[A] = these + loop(this) } + // Overridden methods from IterableTemplate or overloaded variants of such methods + + /** Appends two list objects. + */ + override def ++[B >: A](that: Iterable[B]): List[B] = + this ::: that.toList + /** Overrides the method in Iterable for efficiency. * * @return the list itself @@ -131,7 +152,7 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A /** Returns the <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. */ @@ -148,18 +169,6 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A else b.toList } - /** Returns the list with elements belonging to the given index range. - * - * @param start the start position of the list slice. - * @param end the end position (exclusive) of the list slice. - * @return the list with elements belonging to the given index range. - */ - override def slice(start: Int, end: Int): List[A] = { - val s = start max 0 - val e = end min this.length - drop(s) take (e - s) - } - /** Returns the list without its <code>n</code> first elements. * If this list has less than <code>n</code> elements, the empty list is returned. * @@ -176,6 +185,18 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A these } + /** Returns the list with elements belonging to the given index range. + * + * @param start the start position of the list slice. + * @param end the end position (exclusive) of the list slice. + * @return the list with elements belonging to the given index range. + */ + override def slice(start: Int, end: Int): List[A] = { + val s = start max 0 + val e = end min this.length + drop(s) take (e - s) + } + /** Returns the rightmost <code>n</code> elements from this list. * * @param n the number of elements to take @@ -189,18 +210,7 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A loop(drop(n), this) } - /** Returns the list wihout its rightmost <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) - } + // dropRight is inherited from Stream /** Split the list at a given point and return the two parts thus * created. @@ -266,15 +276,6 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A (b.toList, these) } - /** Returns the <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. * @@ -291,34 +292,6 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A b.toList } - /** Apply a function to all the elements of the list, and return the - * reversed list of results. This is equivalent to a call to <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 @@ -332,219 +305,14 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A final override def filter(p: A => Boolean): List[A] = { // return same list if all elements satisfy p var these = this - while (!these.isEmpty && p(these.head)) { - these = these.tail - } - if (these.isEmpty) this - else { - val b = new ListBuffer[A] - var these1 = this - while (these1 ne these) { - b += these1.head - these1 = these1.tail - } - - these = these.tail // prevent the second evaluation of the predicate - // on the element on which it first failed - while (!these.isEmpty) { - if (p(these.head)) b += these.head - these = these.tail - } - b.toList - } - } - - /** <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 + var allTrue = true + val b = new ListBuffer[A] while (!these.isEmpty) { - acc = f(acc, these.head) + if (p(these.head)) b += these.head + else allTrue = false these = these.tail } - acc - } - - /** Combines the elements of this list together using the binary - * function <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) + if (allTrue) this else b.toList } /** Applies the given function <code>f</code> to each element of @@ -558,32 +326,19 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A val b = new ListBuffer[B] var these = this while (!these.isEmpty) { - var those = f(these.head).elements - while (those.hasNext) { - b += those.next - } + b ++= f(these.head) these = these.tail } b.toList } - /** A list consisting of all elements of this list in reverse order. - */ - override def reverse: List[A] = { - var result: List[A] = Nil - var these = this - while (!these.isEmpty) { - result = these.head :: result - these = these.tail - } - result - } - /** Returns a list formed from this list and the specified list * <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. * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better * @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>) @@ -640,33 +395,9 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A b.toList } - /** Computes the union of this list and the given list - * <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) - } + override def stringPrefix = "List" - /** 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 + override def toStream : Stream[A] = this /** Computes the difference between this list and the given list * <code>that</code>. @@ -674,8 +405,9 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A * @param that the list of elements to remove from this list. * @return this list without the elements of the given list * <code>that</code>. + * @deprecated use diff instead */ - def -- [B >: A](that: List[B]): List[B] = { + @deprecated def -- [B >: A](that: List[B]): List[B] = { val b = new ListBuffer[B] var these = this while (!these.isEmpty) { @@ -691,8 +423,9 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A * @param x the object to remove from this list. * @return this list without the elements of the given object * <code>x</code>. + * @deprecated use diff instead */ - def - [B >: A](x: B): List[B] = { + @deprecated def - [B >: A](x: B): List[B] = { val b = new ListBuffer[B] var these = this while (!these.isEmpty) { @@ -702,40 +435,85 @@ sealed abstract class List[+A] extends Sequence[A] with SequenceTemplate[List, A b.toList } - /** Concatenate the elements of this list. The elements of this list - * should be a <code>Iterables</code>. - * - * Note: The compiler might not be able to infer the type parameter. + /** <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>. + * !!! todo: move sorting to IterableTemplate + * </p> * - * @param f An implicit conversion to an <code>Iterable</code> instance. - * @return The concatenation of all elements of iterables in this list. + * @param lt the comparison function + * @return a list sorted according to the comparison function + * <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> + * @deprecated use sortWith instead */ - def flatten[B](implicit f : A => Iterable[B]) : List[B] = { - val buf = new ListBuffer[B] - foreach(f(_).foreach(buf += _)) - buf.toList - } + @deprecated def sort(lt : (A,A) => Boolean): List[A] = { + /** Merge two already-sorted lists */ + def merge(l1: List[A], l2: List[A]): List[A] = { + val res = new ListBuffer[A] + var left1 = l1 + var left2 = l2 - override def stringPrefix = "List" + while (!left1.isEmpty && !left2.isEmpty) { + if(lt(left1.head, left2.head)) { + res += left1.head + left1 = left1.tail + } else { + res += left2.head + left2 = left2.tail + } + } - override def toStream : Stream[A] = null // !!! - /*new Stream.Definite[A] { - override def force : List[A] = List.this - override def isEmpty = List.this.isEmpty - override def head = List.this.head - override def tail = List.this.tail.toStream - protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder = if (!isEmpty) { - var prefix0 = prefix - var buf1 = buf.append(prefix0).append(head) - prefix0 = ", " - var tail0 = tail - while (!tail0.isEmpty) { - buf1 = buf.append(prefix0).append(tail0.head) - tail0 = tail0.tail + res ++= left1 + res ++= left2 + + res.toList + } + + /** Split a list into two lists of about the same size */ + def split(lst: List[A]) = { + val res1 = new ListBuffer[A] + val res2 = new ListBuffer[A] + var left = lst + + while (!left.isEmpty) { + res1 += left.head + left = left.tail + if (!left.isEmpty) { + res2 += left.head + left = left.tail + } + } + + (res1.toList, res2.toList) + } + + + /** Merge-sort the specified list */ + def ms(lst: List[A]): List[A] = + lst match { + case Nil => lst + case x :: Nil => lst + case x :: y :: Nil => + if (lt(x,y)) + lst + else + y :: x :: Nil + + case lst => + val (l1, l2) = split(lst) + val l1s = ms(l1) + val l2s = ms(l2) + merge(l1s, l2s) } - buf1 - } else buf - }*/ + + ms(this) + } } @@ -788,57 +566,19 @@ final case class ::[B](private var hd: B, private[scalax] var tl: List[B]) exten } } -/** Only used for list serialization */ -@SerialVersionUID(0L - 8476791151975527571L) -private[scalax] case object ListSerializeEnd /** This object provides methods for creating specialized lists, and for * transforming special kinds of lists (e.g. lists of lists). * * @author Martin Odersky and others * @version 1.0, 15/07/2003 */ -object List { - - /** Create a list with given elements. - * - * @param xs the elements to put in the list - * @return the list containing elements xs. - */ - def apply[A](xs: A*): List[A] = (xs.asInstanceOf[Iterable[A]]).toList // !!! +object List extends SequenceFactory[List] { - /** for unapply matching - */ - def unapplySeq[A](x: List[A]): Some[List[A]] = Some(x) + override val empty: List[Nothing] = Nil - /** Create a sorted list of all integers in a range. - * - * @param from the start value of the list - * @param end the end value of the list - * @return the sorted list of all integers in range [from;end). - */ - def range(start: Int, end: Int): List[Int] = - range(start, end, 1) + override def apply[A](xs: A*) = xs.asInstanceOf[Iterable[A]].toList // !@! - /** Create a list with element values - * <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 - } + override def newBuilder[B]: Builder[List, B] = new ListBuffer[B] /** Create a sorted list with element values * <code>v<sub>n+1</sub> = step(v<sub>n</sub>)</code> @@ -846,12 +586,13 @@ object List { * and elements are in the range between <code>start</code> (inclusive) * and <code>end</code> (exclusive) * + * @deprecated use @see iterate instead. * @param start the start value of the list * @param end the end value of the list * @param step the increment function of the list, must be monotonically increasing or decreasing * @return the sorted list of all integers in range [start;end). */ - def range(start: Int, end: Int, step: Int => Int): List[Int] = { + @deprecated def range(start: Int, end: Int, step: Int => Int): List[Int] = { val up = step(start) > start val down = step(start) < start val b = new ListBuffer[Int] @@ -864,12 +605,13 @@ object List { } /** Create a list containing several copies of an element. + * @deprecated use @see fill instead * * @param n the length of the resulting list * @param elem the element composing the resulting list * @return a list composed of n elements all equal to elem */ - def make[A](n: Int, elem: A): List[A] = { + @deprecated def make[A](n: Int, elem: A): List[A] = { val b = new ListBuffer[A] var i = 0 while (i < n) { @@ -879,48 +621,13 @@ object List { b.toList } - /** Create a list by applying a function to successive integers. - * - * @param n the length of the resulting list - * @param maker the procedure which, given an integer <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. * + * @deprecated use `xss.flatten` instead * @param xss the list of lists that are to be concatenated * @return the concatenation of all the lists */ - def flatten[A](xss: List[List[A]]): List[A] = { - val b = new ListBuffer[A] - for (xs <- xss) { - var xc = xs - while (!xc.isEmpty) { - b += xc.head - xc = xc.tail - } - } - b.toList - } - - /** Concatenate all the argument lists into a single list. - * - * @param xss the lists that are to be concatenated - * @return the concatenation of all the lists - */ - def concat[A](xss: List[A]*): List[A] = { + @deprecated def flatten[A](xss: List[List[A]]): List[A] = { val b = new ListBuffer[A] for (xs <- xss) { var xc = xs @@ -936,8 +643,9 @@ object List { * * @param xs the list of pairs to unzip * @return a pair of lists. + * @deprecated use `xs.unzp` instead */ - def unzip[A,B](xs: List[(A,B)]): (List[A], List[B]) = { + @deprecated def unzip[A,B](xs: List[(A,B)]): (List[A], List[B]) = { val b1 = new ListBuffer[A] val b2 = new ListBuffer[B] var xc = xs @@ -951,18 +659,20 @@ object List { /** Transforms an iterable of pairs into a pair of lists. * + * @deprecated use `xs.unzip` instead * @param xs the iterable of pairs to unzip * @return a pair of lists. */ - def unzip[A,B](xs: Iterable[(A,B)]): (List[A], List[B]) = + @deprecated def unzip[A,B](xs: Iterable[(A,B)]): (List[A], List[B]) = xs.foldRight[(List[A], List[B])]((Nil, Nil)) { case ((x, y), (xs, ys)) => (x :: xs, y :: ys) } /** * Returns the <code>Left</code> values in the given <code>Iterable</code> of <code>Either</code>s. + * @deprecated use `Either.lefts` instead */ - def lefts[A, B](es: Iterable[Either[A, B]]) = + @deprecated def lefts[A, B](es: Iterable[Either[A, B]]) = es.foldRight[List[A]](Nil)((e, as) => e match { case Left(a) => a :: as case Right(_) => as @@ -970,8 +680,9 @@ object List { /** * Returns the <code>Right</code> values in the given<code>Iterable</code> of <code>Either</code>s. + * @deprecated use `Either.rights` instead */ - def rights[A, B](es: Iterable[Either[A, B]]) = + @deprecated def rights[A, B](es: Iterable[Either[A, B]]) = es.foldRight[List[B]](Nil)((e, bs) => e match { case Left(_) => bs case Right(b) => b :: bs @@ -981,8 +692,9 @@ object List { * * @param xs the iterable of Eithers to separate * @return a pair of lists. + * @deprecated use `Either.separate` instead */ - def separate[A,B](es: Iterable[Either[A,B]]): (List[A], List[B]) = + @deprecated def separate[A,B](es: Iterable[Either[A,B]]): (List[A], List[B]) = es.foldRight[(List[A], List[B])]((Nil, Nil)) { case (Left(a), (lefts, rights)) => (a :: lefts, rights) case (Right(b), (lefts, rights)) => (lefts, b :: rights) @@ -993,14 +705,16 @@ object List { * @param it the iterator to convert * @return a list that contains the elements returned by successive * calls to <code>it.next</code> + * @deprecated use it.toList instead */ - def fromIterator[A](it: Iterator[A]): List[A] = it.toList + @deprecated def fromIterator[A](it: Iterator[A]): List[A] = it.toList /** Converts an array into a list. * * @param arr the array to convert * @return a list that contains the same elements than <code>arr</code> * in the same order + * @deprecated use `array.toList` instead */ def fromArray[A](arr: Array[A]): List[A] = fromArray(arr, 0, arr.length) @@ -1011,8 +725,9 @@ object List { * @param len the lenght of the range to convert * @return a list that contains the same elements than <code>arr</code> * in the same order + * @deprecated use `array.view(start, end).toList` instead */ - def fromArray[A](arr: Array[A], start: Int, len: Int): List[A] = { + @deprecated def fromArray[A](arr: Array[A], start: Int, len: Int): List[A] = { var res: List[A] = Nil var i = start + len while (i > start) { @@ -1028,8 +743,9 @@ object List { * @param str the string to parse * @param separator the separator character * @return the list of substrings + * @deprecated use `str.split(separator).toList` instead */ - def fromString(str: String, separator: Char): List[String] = { + @deprecated def fromString(str: String, separator: Char): List[String] = { var words: List[String] = Nil var pos = str.length() while (pos > 0) { @@ -1048,14 +764,15 @@ object List { * @deprecated use <code>str.toList</code> instead */ @deprecated def fromString(str: String): List[Char] = - str.toList.asInstanceOf[List[Char]] // !!! + str.toList.asInstanceOf[List[Char]] // !@! /** Returns the given list of characters as a string. * * @param xs the list to convert. * @return the list in form of a string. + * @deprecated use xs.mkString instead */ - def toString(xs: List[Char]): String = { + @deprecated def toString(xs: List[Char]): String = { val sb = new StringBuilder() var xc = xs while (!xc.isEmpty) { @@ -1067,12 +784,9 @@ object List { /** Like xs map f, but returns <code>xs</code> unchanged if function * <code>f</code> maps all elements to themselves. - * - * @param xs ... - * @param f ... - * @return ... + * @deprecated use xs.mapConserve(f) */ - def mapConserve[A <: AnyRef](xs: List[A])(f: A => A): List[A] = { + @deprecated def mapConserve[A <: AnyRef](xs: List[A])(f: A => A): List[A] = { def loop(ys: List[A]): List[A] = if (ys.isEmpty) xs else { @@ -1099,13 +813,13 @@ object List { /** Returns the list resulting from applying the given function <code>f</code> * to corresponding elements of the argument lists. - * + * @deprecated use (xs, ys).map(f) instead * @param f function to apply to each pair of elements. * @return <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] = { + @deprecated def map2[A,B,C](xs: List[A], ys: List[B])(f: (A, B) => C): List[C] = { val b = new ListBuffer[C] var xc = xs var yc = ys @@ -1121,6 +835,7 @@ object List { * <code>f</code> to corresponding elements of the argument lists. * * @param f function to apply to each pair of elements. + * @deprecated use (xs, ys, zs).map(f) instead * @return <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>, @@ -1128,7 +843,7 @@ object List { * <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] = { + @deprecated def map3[A,B,C,D](xs: List[A], ys: List[B], zs: List[C])(f: (A, B, C) => D): List[D] = { val b = new ListBuffer[D] var xc = xs var yc = ys @@ -1151,8 +866,9 @@ object List { * if the lists are <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> + * @deprecated use (xs, ys).forall(f) instead */ - def forall2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = { + @deprecated def forall2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = { var xc = xs var yc = ys while (!xc.isEmpty && !yc.isEmpty) { @@ -1172,8 +888,9 @@ object List { * <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> + * @deprecated use (xs, ys).forall(f) instead */ - def exists2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = { + @deprecated def exists2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = { var xc = xs var yc = ys while (!xc.isEmpty && !yc.isEmpty) { @@ -1189,8 +906,9 @@ object List { * * @param xss the list of lists * @return the transposed list of lists + * @deprecated use xss.transpose instead */ - def transpose[A](xss: List[List[A]]): List[List[A]] = { + @deprecated def transpose[A](xss: List[List[A]]): List[List[A]] = { val buf = new ListBuffer[List[A]] var yss = xss while (!yss.head.isEmpty) { @@ -1220,3 +938,7 @@ object List { */ } +/** Only used for list serialization */ +@SerialVersionUID(0L - 8476791151975527571L) +private[scalax] case object ListSerializeEnd + diff --git a/src/library/scalax/collection/immutable/OrderedIterable.scala b/src/library/scalax/collection/immutable/OrderedIterable.scala new file mode 100644 index 0000000000..402244953d --- /dev/null +++ b/src/library/scalax/collection/immutable/OrderedIterable.scala @@ -0,0 +1,22 @@ +package scalax.collection.immutable + +import generic.covariant + +/** Collection classes mixing in this class provide a method + * <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 OrderedIterable[+A] extends collection.OrderedIterable[A] with Iterable[A] + +object OrderedIterable extends covariant.IterableFactory[OrderedIterable] { + val empty: OrderedIterable[Nothing] = Nil +} + + diff --git a/src/library/scalax/collection/immutable/Sequence.scala b/src/library/scalax/collection/immutable/Sequence.scala new file mode 100644 index 0000000000..fdb9fadf04 --- /dev/null +++ b/src/library/scalax/collection/immutable/Sequence.scala @@ -0,0 +1,22 @@ +package scalax.collection.immutable + +import generic.covariant + +/** Collection classes mixing in this class provide a method + * <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 Sequence[+A] extends collection.Sequence[A] with OrderedIterable[A] + +object Sequence extends covariant.SequenceFactory[Sequence] { + val empty: Sequence[Nothing] = Nil +} + + diff --git a/src/library/scalax/collection/immutable/Stream.scala b/src/library/scalax/collection/immutable/Stream.scala new file mode 100755 index 0000000000..6b4a8a60f6 --- /dev/null +++ b/src/library/scalax/collection/immutable/Stream.scala @@ -0,0 +1,790 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Stream.scala 16287 2008-10-18 13:41:36Z nielsen $ + + +package scalax.collection.immutable + +import mutable.ListBuffer +import generic.covariant.{SequenceTemplate, SequenceFactory} + +/** + * The object <code>Stream</code> provides helper functions + * to manipulate streams. + * + * @author Martin Odersky, Matthias Zenger + * @version 1.1 08/08/03 + */ +object Stream extends SequenceFactory[Stream] { + + import collection.{Iterable, OrderedIterable, Sequence, Vector} + + override val empty: Stream[Nothing] = Nil + override def apply[A](xs: A*) = xs.asInstanceOf[Iterable[A]].toList // !@! + override def newBuilder[B]: Builder[Stream, B] = new ListBuffer[B] + + class ConsWrapper[A](tl: => Stream[A]) { + def #::(hd: A): Stream[A] = new Cons(hd, tl) + def #:::(prefix: Stream[A]): Stream[A] = prefix append tl + } + + implicit def consWrapper[A](stream: => Stream[A]): ConsWrapper[A] = + new ConsWrapper[A](stream) + + object #:: { + def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = + if (xs.isEmpty) None + else Some(xs.head, xs.tail) + } + + /** @deprecated use #:: instead */ + @deprecated lazy val lazy_:: = #:: + + /** An alternative way of building and matching Streams using Stream.cons(hd, tl). + */ + object cons { + + /** A stream consisting of a given first element and remaining elements + * @param hd The first element of the result stream + * @param tl The remaining elements of the result stream + */ + def apply[A](hd: A, tl: => Stream[A]) = new Cons(hd, tl) + + /** Maps a stream to its head and tail */ + def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = #::.unapply(xs) + } + + final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] { + override def isEmpty = false + override def head = hd + private[this] var tlVal: Stream[A] = _ + private def tlDefined = tlVal ne null + override def tail: Stream[A] = { + if (!tlDefined) { tlVal = tl } + tlVal + } + override def hasDefiniteSize = tlDefined && tlVal.hasDefiniteSize + + // Overridden methods from IterableTemplate or overloaded variants of such methods + + /** Create a new stream which contains all elements of this stream + * followed by all elements of Iterable `that' + */ + override def ++[B >: A](that: Iterable[B]): Stream[B] = this append that + + /** Create a new stream which contains all elements of this stream + * followed by all elements of Iterator `that' + */ + override def ++[B >: A](that: Iterator[B]): Stream[B] = this append that.toStream + + /** Returns the stream resulting from applying the given function + * <code>f</code> to each element of this stream. + * + * @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>. + */ + override def map[B](f: A => B): Stream[B] = + new Cons(f(head), tail map f) + + /** Applies the given function <code>f</code> to each element of + * this stream, 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 stream is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>. + */ + override def flatMap[B](f: A => Iterable[B]): Stream[B] = { + // drops A's for which f yields an empty Iterable[B] + def loop(s: Stream[A]): Stream[B] = + if (s.isEmpty) Nil + else { + val i = f(s.head) + if (i.isEmpty) loop(s.tail) + else i.toStream append loop(s.tail) + } + loop(this) + } + + /** Returns all the elements of this stream that satisfy the + * predicate <code>p</code>. The order of the elements is preserved. + * + * @param p the predicate used to filter the stream. + * @return the elements of this stream satisfying <code>p</code>. + */ + override def filter(p: A => Boolean): Stream[A] = { + // drops A's for which p yields false + def loop(s: Stream[A]): Stream[A] = + if (s.isEmpty) Nil + else { + val b = p(s.head) + if (!b) loop(s.tail) + else new Cons(s.head, tail filter p) + } + loop(this) + } + + /** Returns all the elements of this stream that satisfy the + * predicate <code>p</code>. The order of the elements is preserved. + * + * @param p the predicate used to filter the stream. + * @return the elements of this stream satisfying <code>p</code>. + */ + override def partition(p: A => Boolean): (Stream[A], Stream[A]) = (filter(p(_)), remove(p(_))) + + /** Returns a stream formed from this stream and the specified stream + * <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 streams is longer than the other, its remaining elements are ignored. + * + * @return <code>Stream({a<sub>0</sub>,b<sub>0</sub>}, ..., + * {a<sub>min(m,n)</sub>,b<sub>min(m,n)</sub>)}</code> when + * <code>Stream(a<sub>0</sub>, ..., a<sub>m</sub>) + * zip Stream(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked. + */ + def zip[B](that: Stream[B]): Stream[(A, B)] = + if (that.isEmpty) empty + else new Cons((this.head, that.head), this.tail zip that.tail) + + /** Returns a list formed from this list and the specified list + * <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, A1 >: A, B1 >: B](that: Stream[B], thisElem: A1, thatElem: B1): Stream[(A1, B1)] = { + if (that.isEmpty) new Cons((this.head, thatElem), this.tail.zipAll(that, thisElem, thatElem)) + else new Cons((this.head, that.head), this.tail.zipAll(that.tail, thisElem, thatElem)) + } + + /** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to + * `s zip s.indices` + */ + override def zipWithIndex = this zip (Iterator.from(0).toStream) + + /** Write all defined elements of this iterable into given string builder. + * The written text begins with the string <code>start</code> and is finished by the string + * <code>end</code>. Inside, the string representations of defined elements (w.r.t. + * the method <code>toString()</code>) are separated by the string + * <code>sep</code>. The method will not force evaluation of undefined elements. A + * tail of such elements will be represented by a "?" instead. + */ + override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = { + b append start append hd + if (tlDefined) tlVal.addString(b, sep, sep, end) + else b append ", ?" append end + } + + /** Returns the <code>n</code> first elements of this stream, or else the whole + * stream, 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 stream. + */ + override def take(n: Int): Stream[A] = + if (n <= 0) Nil else new Cons(head, tail take (n-1)) + + /** Returns the stream without its <code>n</code> first elements. + * If the stream has less than <code>n</code> elements, the empty stream is returned. + * + * @param n the number of elements to drop. + * @return the stream without its <code>n</code> first elements. + */ + override def drop(n: Int): Stream[A] = { + var these: Stream[A] = this + var i = n + while (!these.isEmpty && i > 0) { + these = these.tail + i -= 1 + } + these + } + + /** A substream starting at index `from` + * and extending up to (but not including) index `until`. + * + * @This is equivalent to (but possibly more efficient than) + * c.drop(from).take(to - from) + * + * @param from The index of the first element of the returned subsequence + * @param until The index of the element following the returned subsequence + * @throws IndexOutOfBoundsException if <code>from < 0</code> + * or <code>length < from + len<code> + * @note Might return different results for different runs, unless this iterable is ordered + */ + override def slice(from: Int, to: Int): Stream[A] = + this.drop(from).take(to - from) + + /** The stream without its last element. + * @throws Predef.UnsupportedOperationException if the stream is empty. + */ + override def init: Stream[A] = + if (tail.isEmpty) Nil + else new Cons(head, tail.init) + + /** Returns the rightmost <code>n</code> elements from this iterable. + * @param n the number of elements to take + */ + override def takeRight(n: Int): Stream[A] = { + var these: Stream[A] = this + var lead = this drop n + while (!lead.isEmpty) { + these = these.tail + lead = lead.tail + } + these + } + + /** Returns the longest prefix of this stream whose elements satisfy + * the predicate <code>p</code>. + * + * @param p the test predicate. + */ + override def takeWhile(p: A => Boolean): Stream[A] = + if (p(head)) new Cons(head, tail takeWhile p) else Nil + + + /** Returns the longest suffix of this iterable whose first element + * does not satisfy the predicate <code>p</code>. + * + * @param p the test predicate. + */ + override def dropWhile(p: A => Boolean): Stream[A] = { + var these: Stream[A] = this + while (!these.isEmpty && p(these.head)) these = these.tail + these + } + + /** Returns a pair consisting of the longest prefix of the stream whose + * elements all satisfy the given predicate, and the rest of the stream. + * + * @param p the test predicate + */ + override def span(p: A => Boolean): (List[A], Stream[A]) = { + var these: Stream[A] = this + val l = new ListBuffer[A] + while (!these.isEmpty && p(these.head)) { + l += these.head + these = these.tail + } + (l.toList, these) + } + + // Overridden methods from Sequence + + /** Builds a new stream from this stream in which any duplicates (wrt to ==) removed. + * Among duplicate elements, only the first one is retained in the result stream + */ + override def removeDuplicates: Stream[A] = + new Cons(head, tail.filter(head !=).removeDuplicates) + + /** Returns a new sequence of given length containing the elements of this sequence followed by zero + * or more occurrences of given elements. + */ + override def padTo[B >: A](len: Int, elem: B): Stream[B] = + new Cons(head, tail.padTo(len - 1, elem)) + } + + /** + * Create an infinite stream starting at <code>start</code> + * and incrementing by step <code>step</code> + * + * @param start the start value of the stream + * @param step the increment value of the stream + * @return the stream starting at value <code>start</code>. + */ + def from(start: Int, step: Int): Stream[Int] = + new Cons(start, from(start+step, step)) + + /** + * Create an infinite stream starting at <code>start</code> + * and incrementing by 1. + * + * @param start the start value of the stream + * @return the stream starting at value <code>start</code>. + */ + def from(start: Int): Stream[Int] = from(start, 1) + + /** + * Create an infinite stream containing the given element expression (which is computed for each + * occurrence) + * @param elem the element composing the resulting stream + * @return the stream containing an inifinite number of elem + * @deprecated use fill instead + */ + @deprecated def fill[A](elem: => A): Stream[A] = new Cons(elem, fill(elem)) + + /** A stream containing all elements of a given iterator, in the order they are produced. + * @param it The iterator producing the stream's elements + * @deprecated use it.toStream instead + */ + @deprecated def fromIterator[A](it: Iterator[A]): Stream[A] = + if (it.hasNext) cons(it.next, fromIterator(it)) else empty + + /** The concatenation of a sequence of streams + * @deprecated use xs.flatten instead + */ + @deprecated def concat[A](xs: Iterable[Stream[A]]): Stream[A] = concat(xs.elements) + + /** The concatenation of all streams returned by an iterator + * @deprecated use xs.toStream.flatten instead + */ + @deprecated def concat[A](xs: Iterator[Stream[A]]): Stream[A] = + if (xs.hasNext) xs.next append concat(xs) + else empty + + /** + * Create a stream with element values + * <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) + * @deprecated use @see iterate instead. + * @param start the start value of the stream + * @param end the end value of the stream + * @param step the increment function of the stream, must be monotonically increasing or decreasing + * @return the stream starting at value <code>start</code>. + */ + @deprecated def range(start: Int, end: Int, step: Int => Int): Stream[Int] = { + val up = step(start) > start + val down = step(start) < start + def loop(lo: Int): Stream[Int] = + if ((!up || lo < end) && (!down || lo > end)) cons(lo, loop(step(lo))) + else empty + loop(start) + } + + /** + * Create an infinite stream containing the given element. + * + * @param elem the element composing the resulting stream + * @return the stream containing an inifinite number of elem + * @deprecated use fill(elem) instead + */ + @deprecated def const[A](elem: A): Stream[A] = cons(elem, const(elem)) + + /** Create a stream containing several copies of an element. + * + * @param n the length of the resulting stream + * @param elem the element composing the resulting stream + * @return the stream composed of n elements all equal to elem + * @deprecated use fill(n, elem) instead + */ + @deprecated def make[A](n: Int, elem: A): Stream[A] = + const(elem) take n +} + +import Stream._ + +/** + * <p>The class <code>Stream</code> implements lazy lists where elements + * are only evaluated when they are needed. Here is an example:</p> + * <pre> + * <b>object</b> Main <b>extends</b> Application { + * + * <b>def</b> from(n: Int): Stream[Int] = + * Stream.cons(n, from(n + 1)) + * + * <b>def</b> sieve(s: Stream[Int]): Stream[Int] = + * Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 })) + * + * <b>def</b> primes = sieve(from(2)) + * + * primes take 10 print + * } + * </pre> + * + * @author Martin Odersky, Matthias Zenger + * @version 1.1 08/08/03 + */ +abstract class Stream[+A] extends Sequence[A] with SequenceTemplate[Stream, A] { +self => + + import collection.{Iterable, OrderedIterable, Sequence, Vector} + + /** is this stream empty? */ + def isEmpty: Boolean + + /** The first element of this stream + * @throws Predef.NoSuchElementException if the stream is empty. + */ + def head: A + + /** A stream consisting of the remaining elements of this stream after the first one. + * @throws Predef.UnsupportedOperationException if the stream is empty. + */ + def tail: Stream[A] + + // Implementation of abstract methods + + /** Create a new @see LazyBuilder to build a stream */ + def newBuilder[B]: Builder[Stream, B] = new LazyBuilder[Stream, B] { + def result: Stream[B] = elements.toStream + } + + /** Returns the number of elements in the list. + */ + def length: Int = { + var these = self + var len = 0 + while (!these.isEmpty) { + len += 1 + these = these.tail + } + len + } + + /** Returns the <code>n</code>-th element of this stream. The first element + * (head of the stream) is at position 0. + * + * @param n index of the element to return + * @return the element at position <code>n</code> in this stream. + * @throws Predef.NoSuchElementException if the stream is too short. + */ + override def apply(n: Int): A = drop(n).head + + // New methods in Stream + + /** The stream resulting from the concatenation of this stream with the argument stream. + * @param rest The stream that gets appended to this stream + */ + def append[B >: A](rest: => Iterable[B]): Stream[B] = + if (isEmpty) rest.toStream else new Cons(head, tail append rest) + + /** Force evaluation of the whole stream and return it */ + def force: Stream[A] = { + var these = this + while (!isEmpty) these = these.tail + this + } + + /** Prints elements of this stream one by one, separated by commas */ + def print() { print(", ") } + + /** Prints elements of this stream one by one, separated by <code>sep</code> + * @param sep The separator string printed between consecutive elements. + */ + def print(sep: String) { + def loop(these: Stream[A], start: String) { + Console.print(start) + if (isEmpty) Console.print("empty") + else { + Console.print(these.head) + loop(these.tail, sep) + } + } + loop(this, "") + } + + // Overridden methods from IterableTemplate or overloaded variants of such methods + + /** Returns the elements in the sequence as an iterator + */ + override def elements: Iterator[A] = new Iterator[A] { + var these = self + def hasNext: Boolean = !these.isEmpty + def next: A = + if (hasNext) { + val result = these.head; these = these.tail; result + } else Iterator.empty.next + override def toList: List[A] = these.toList + } + + /** Apply the given function <code>f</code> to each element of this stream + * (while respecting the order of the elements). + * + * @param f the treatment to apply to each element. + */ + override def foreach(f: A => Unit) { + var these = this + while (!these.isEmpty) { + f(these.head) + these = these.tail + } + } + + /** Tests if the predicate <code>p</code> is satisfied by all elements + * in this list. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @param p the test predicate. + * @return <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>. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @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 + } + + /** Count the number of elements in the iterable which satisfy a predicate. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @param p the predicate for which to count + * @return the number of elements satisfying the predicate <code>p</code>. + */ + override def count(p: A => Boolean): Int = { + var these = this + var cnt = 0 + while (!these.isEmpty) { + if (p(these.head)) cnt += 1 + these = these.tail + } + cnt + } + + /** Find and return the first element of the list satisfying a + * predicate, if any. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @param p the predicate + * @return the first element in the list satisfying <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>. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @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 = + if (this.isEmpty) z + else f(head, tail.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 = + if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") + else tail.foldLeft[B](head)(f) + + /** Combines the elements of this iterable object together using the binary + * operator <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. + */ + override def reduceRight[B >: A](op: (A, B) => B): B = + if (isEmpty) throw new UnsupportedOperationException("Nil.reduceRight") + else if (tail.isEmpty) head + else op(head, tail.reduceRight(op)) + + /** + * Create a stream which contains all the elements of this iterable object. + * @note consider using <code>projection</code> for lazy behavior. + */ + override def toStream: Stream[A] = this + + /** Defines the prefix of this object's <code>toString</code> representation as ``Stream''. + */ + override def stringPrefix = "Stream" + + /** The last element of this stream. + * + * @throws Predef.NoSuchElementException if the stream is empty. + */ + override def last: A = { + if (isEmpty) throw new NoSuchElementException + var these = this + var nx = these.tail + while (!nx.isEmpty) { + these = nx + nx = nx.tail + } + these.head + } + + /** Returns the rightmost <code>n</code> elements from this iterable. + * @param n the number of elements to take + */ + override def dropRight(n: Int): List[A] = { + val b = new ListBuffer[A] + var these = this + var lead = this drop n + while (!lead.isEmpty) { + b += these.head + these = these.tail + lead = lead.tail + } + b.toList + } + + /** Returns true iff the other stream contains the same elements as this one. + * + * @note will not terminate for two infinite-sized streams. + * @param that the other stream + */ + def sameElements[B >: A](that: Stream[B]): Boolean = { + val these = this + val those = that + while (!these.isEmpty && !those.isEmpty && these.head == those.head) {} + these.isEmpty && those.isEmpty + } + + // Overridden methods from Sequence + + /** Result of comparing <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>. + */ + override def lengthCompare(len: Int): Int = { + var i = 0 + var these = self + while (!these.isEmpty && i <= len) { + i += 1 + these = these.tail + } + i - len + } + + /** Is this partial function defined for the index <code>x</code>? + */ + override def isDefinedAt(x: Int): Boolean = x >= 0 && lengthCompare(x) >= 0 + + /** Returns length of longest segment starting from a start index `from` + * such that every element of the segment satisfies predicate `p`. + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @param from the start index + */ + override def segmentLength(p: A => Boolean, from: Int): Int = { + var i = from + var these = this drop from + while (!these.isEmpty && p(these.head)) { + i += 1 + these = these.tail + } + i + } + + /** Returns index of the first element starting from a start index + * satisying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized streams. + * @param p the predicate + * @param from the start index + */ + override def indexWhere(p: A => Boolean, from: Int): Int = { + var i = from + var these = this drop from + while (!these.isEmpty && !p(these.head)) { + i += 1 + these = these.tail + } + if (these.isEmpty) -1 else i + } + + /** Returns index of the last element satisying a predicate, or -1, if none exists. + * + * @param p the predicate + * @return the index of the last element satisfying <code>p</code>, + * or -1 if such an element does not exist + */ + override def lastIndexWhere(p: A => Boolean, end: Int): Int = { + var i = 0 + var these = this + var last = -1 + while (!these.isEmpty && i <= end) { + if (p(these.head)) last = i + } + i + } + + /** A list consisting of all elements of this list in reverse order. + */ + override def reverse: List[A] = { + var result: List[A] = Nil + var these = this + while (!these.isEmpty) { + result = these.head :: result + these = these.tail + } + result + } +} + diff --git a/src/library/scalax/collection/immutable/Vector.scala b/src/library/scalax/collection/immutable/Vector.scala new file mode 100644 index 0000000000..64cf512c90 --- /dev/null +++ b/src/library/scalax/collection/immutable/Vector.scala @@ -0,0 +1,22 @@ +package scalax.collection.immutable + +import generic.covariant + +/** Collection classes mixing in this class provide a method + * <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>. + * // !!! todo: insert good immutable vector implementation here. + * @author Matthias Zenger + * @autor Martin Odersky + * @owner Martin Odersky + * @version 2.8 + */ +trait Vector[+A] extends collection.Vector[A] with Sequence[A] + +object Vector extends covariant.SequenceFactory[Vector] { + val empty: Vector[Nothing] = immutable.Vector.empty +} + + diff --git a/src/library/scalax/collection/mutable/Appendable.scala b/src/library/scalax/collection/mutable/Appendable.scala index b8e8569a14..6dbe89346e 100644 --- a/src/library/scalax/collection/mutable/Appendable.scala +++ b/src/library/scalax/collection/mutable/Appendable.scala @@ -33,7 +33,7 @@ trait Appendable[A] { def +=(elem1: A, elem2: A, elems: A*) { this += elem1 this += elem2 - this ++= elems.asInstanceOf[Iterable[A]] // !!! + this ++= elems.asInstanceOf[Iterable[A]] // !@! } /** Appends a number of elements provided by an iterator @@ -64,7 +64,7 @@ trait Appendable[A] { * @param elems the remaining elements to append. */ def +(elem1: A, elem2: A, elems: A*): this.type = - this + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]] // !!! + this + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]] // !@! /** Appends a number of elements provided by an iterable object * via its <code>elements</code> method. The identity of the diff --git a/src/library/scalax/collection/mutable/Buffer.scala b/src/library/scalax/collection/mutable/Buffer.scala index c11fa37409..c03b49ee16 100644 --- a/src/library/scalax/collection/mutable/Buffer.scala +++ b/src/library/scalax/collection/mutable/Buffer.scala @@ -124,7 +124,7 @@ trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable * @param elem the element to prepend. */ def +:(elem1: A, elem2: A, elems: A*): this.type = - elem1 +: elem2 +: (elems.asInstanceOf[Iterable[A]]) ++: this // !!! + elem1 +: elem2 +: (elems.asInstanceOf[Iterable[A]]) ++: this // !@! /** Prepends a number of elements provided by an iterable object * via its <code>elements</code> method. The identity of the @@ -146,7 +146,7 @@ trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable * * @param elems the elements to append. */ - def append(elems: A*) { this ++= elems.asInstanceOf[Iterable[A]] } // !!! + def append(elems: A*) { this ++= elems.asInstanceOf[Iterable[A]] } // !@! /** Appends a number of elements provided by an iterable object * via its <code>elements</code> method. @@ -159,7 +159,7 @@ trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable * * @param elem the element to prepend. */ - def prepend(elems: A*) { elems.asInstanceOf[Iterable[A]] ++: this } // !!! + def prepend(elems: A*) { elems.asInstanceOf[Iterable[A]] ++: this } // !@! /** Prepends a number of elements provided by an iterable object * via its <code>elements</code> method. The identity of the @@ -184,7 +184,7 @@ trait Buffer[A] extends Vector[A] with VectorTemplate[Buffer, A] with Appendable * @param n the index where a new element will be inserted. * @param elems the new elements to insert. */ - def insert(n: Int, elems: A*) { insertAll(n, elems.asInstanceOf[Iterable[A]]) } // !!! + def insert(n: Int, elems: A*) { insertAll(n, elems.asInstanceOf[Iterable[A]]) } // !@! /** Removes the first <code>n</code> elements. * diff --git a/src/library/scalax/collection/mutable/ResizableArray.scala b/src/library/scalax/collection/mutable/ResizableArray.scala index e4dd8bd47d..97d1ba2d6d 100644 --- a/src/library/scalax/collection/mutable/ResizableArray.scala +++ b/src/library/scalax/collection/mutable/ResizableArray.scala @@ -55,7 +55,7 @@ trait ResizableArray[A] extends Vector[A] { * @param The buffer to which elements are copied */ override def copyToBuffer[B >: A](dest: Buffer[B]) { - dest ++= array.asInstanceOf[Iterable[A]] // !!! + dest ++= array.asInstanceOf[Iterable[A]] // !@! } override def foreach(f: A => Unit) { diff --git a/src/library/scalax/collection/mutable/Vector.scala b/src/library/scalax/collection/mutable/Vector.scala index b181e93303..91a50b5300 100644 --- a/src/library/scalax/collection/mutable/Vector.scala +++ b/src/library/scalax/collection/mutable/Vector.scala @@ -15,6 +15,6 @@ trait Vector[A] extends collection.Vector[A] with generic.mutable.VectorTemplate object Vector extends generic.nonvariant.SequenceFactory[Vector] { /** The empty iterable */ - def apply[A](args: A*): Vector[A] = null // !!! + def apply[A](args: A*): Vector[A] = new ArrayBuffer[A] ++ args.asInstanceOf[Iterable[A]] // !@! } diff --git a/src/library/scalax/util/control/TailRec.scala b/src/library/scalax/util/control/TailRec.scala new file mode 100644 index 0000000000..db6cbfa2ed --- /dev/null +++ b/src/library/scalax/util/control/TailRec.scala @@ -0,0 +1,24 @@ +package scala.util.control + +abstract class TailRec[+A] + +object TailRec { + + case class Call[A](rest: () => TailRec[A]) extends TailRec[A] + case class Done[A](result: A) extends TailRec[A] + + def tailcall[A](rest: => TailRec[A]) = new Call(() => rest) + def done [A](result: A) = new Done(result) + def trampoline[A](body: TailRec[A]): A = { + def loop(body: TailRec[A]): A = body match { + case Call(rest) => loop(rest()) + case Done(result) => result + } + loop(body) + } + def loop[A](body: TailRec[A]): A = body match { + case Call(rest) => loop[A](rest()) + case Done(result) => result + } +} + |