From e5868320d48d38687d67c8c3ffc2954815b2f14f Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Mon, 20 Oct 2008 10:06:37 +0000 Subject: initial collection library fragments --- src/library/scalax/Fractional.scala | 5 + src/library/scalax/Integral.scala | 6 + src/library/scalax/Numeric.scala | 79 ++ .../scalax/collection/BufferedIterator.scala | 27 + src/library/scalax/collection/Builder.scala | 19 + src/library/scalax/collection/Iterable.scala | 1063 ++++++++++++++++++++ src/library/scalax/collection/Iterator.scala | 965 ++++++++++++++++++ src/library/scalax/collection/SeqFactory.scala | 111 ++ src/library/scalax/util/control/Break.scala | 15 + 9 files changed, 2290 insertions(+) create mode 100755 src/library/scalax/Fractional.scala create mode 100755 src/library/scalax/Integral.scala create mode 100755 src/library/scalax/Numeric.scala create mode 100755 src/library/scalax/collection/BufferedIterator.scala create mode 100755 src/library/scalax/collection/Builder.scala create mode 100755 src/library/scalax/collection/Iterable.scala create mode 100755 src/library/scalax/collection/Iterator.scala create mode 100755 src/library/scalax/collection/SeqFactory.scala create mode 100755 src/library/scalax/util/control/Break.scala diff --git a/src/library/scalax/Fractional.scala b/src/library/scalax/Fractional.scala new file mode 100755 index 0000000000..b29a903519 --- /dev/null +++ b/src/library/scalax/Fractional.scala @@ -0,0 +1,5 @@ +package scalax + +trait Fractional[T] extends Numeric[T] { + def div(x: T, y: T): T +} diff --git a/src/library/scalax/Integral.scala b/src/library/scalax/Integral.scala new file mode 100755 index 0000000000..2e80b1bb7b --- /dev/null +++ b/src/library/scalax/Integral.scala @@ -0,0 +1,6 @@ +package scalax + +trait Integral[T] extends Numeric[T] { + def quot(x: T, y: T): T + def rem(x: T, y: T): T +} diff --git a/src/library/scalax/Numeric.scala b/src/library/scalax/Numeric.scala new file mode 100755 index 0000000000..6e61851dc5 --- /dev/null +++ b/src/library/scalax/Numeric.scala @@ -0,0 +1,79 @@ +package scalax + +object Numeric { + implicit object IntIsIntegral extends Integral[Int] { + def plus(x: Int, y: Int): Int = x + y + def minus(x: Int, y: Int): Int = x - y + def times(x: Int, y: Int): Int = x * y + def quot(x: Int, y: Int): Int = x / y + def rem(x: Int, y: Int): Int = x % y + def negate(x: Int): Int = -x + def abs(x: Int): Int = if (x < 0) -x else x + def signum(x: Int): Int = if (x < 0) -1 else if (x > 0) 1 else 0 + def fromInt(x: Int): Int = x + def toInt(x: Int): Int = x + def toLong(x: Int): Long = x + def toFloat(x: Int): Float = x + def toDouble(x: Int): Double = x + } + implicit object LongIsIntegral extends Integral[Long] { + def plus(x: Long, y: Long): Long = x + y + def minus(x: Long, y: Long): Long = x - y + def times(x: Long, y: Long): Long = x * y + def quot(x: Long, y: Long): Long = x / y + def rem(x: Long, y: Long): Long = x % y + def negate(x: Long): Long = -x + def abs(x: Long): Long = if (x < 0) -x else x + def signum(x: Long): Long = if (x < 0) -1 else if (x > 0) 1 else 0 + def fromInt(x: Int): Long = x + def toInt(x: Long): Int = x.toInt + def toLong(x: Long): Long = x + def toFloat(x: Long): Float = x + def toDouble(x: Long): Double = x + } + implicit object FloatIsFractional extends Fractional[Float] { + def plus(x: Float, y: Float): Float = x + y + def minus(x: Float, y: Float): Float = x - y + def times(x: Float, y: Float): Float = x * y + def div(x: Float, y: Float): Float = x / y + def negate(x: Float): Float = -x + def abs(x: Float): Float = if (x < 0) -x else x + def signum(x: Float): Float = if (x < 0) -1 else if (x > 0) 1 else 0 + def fromInt(x: Int): Float = x + def toInt(x: Float): Int = x.toInt + def toLong(x: Float): Long = x.toLong + def toFloat(x: Float): Float = x + def toDouble(x: Float): Double = x + } + implicit object DoubleIsFractional extends Fractional[Double] { + def plus(x: Double, y: Double): Double = x + y + def minus(x: Double, y: Double): Double = x - y + def times(x: Double, y: Double): Double = x * y + def div(x: Double, y: Double): Double = x / y + def negate(x: Double): Double = -x + def abs(x: Double): Double = if (x < 0) -x else x + def signum(x: Double): Double = if (x < 0) -1 else if (x > 0) 1 else 0 + def fromInt(x: Int): Double = x + def toInt(x: Double): Int = x.toInt + def toLong(x: Double): Long = x.toLong + def toFloat(x: Double): Float = x.toFloat + def toDouble(x: Double): Double = x + } +} + + +trait Numeric[T] { + def plus(x: T, y: T): T + def minus(x: T, y: T): T + def times(x: T, y: T): T + def negate(x: T): T + def abs(x: T): T + def signum(x: T): T + def fromInt(x: Int): T + def toInt(x: T): Int + def toLong(x: T): Long + def toFloat(x: T): Float + def toDouble(x: T): Double + def zero = fromInt(0) + def one = fromInt(1) +} diff --git a/src/library/scalax/collection/BufferedIterator.scala b/src/library/scalax/collection/BufferedIterator.scala new file mode 100755 index 0000000000..07509c2758 --- /dev/null +++ b/src/library/scalax/collection/BufferedIterator.scala @@ -0,0 +1,27 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: BufferedIterator.scala 12641 2007-08-22 16:01:57Z mcdirmid $ + + +package scalax.collection + +/** Buffered iterators are iterators which allow to inspect the next + * element without discarding it. + * + * @author Martin Odersky + * @version 2.8 + */ +trait BufferedIterator[+A] extends Iterator[A] { + + /** Returns current element of iterator without advancing beyond it. + */ + def head: A + + override def buffered: this.type = this +} diff --git a/src/library/scalax/collection/Builder.scala b/src/library/scalax/collection/Builder.scala new file mode 100755 index 0000000000..c6ba104c4d --- /dev/null +++ b/src/library/scalax/collection/Builder.scala @@ -0,0 +1,19 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $ + +package scalax.collection + + +trait Builder[+C[B], A] extends Iterable[A] { + def +=(x: A) + def ++=(xs: Iterator[A]) + def ++=(xs: Iterable[A]) + def result: C[A] +} diff --git a/src/library/scalax/collection/Iterable.scala b/src/library/scalax/collection/Iterable.scala new file mode 100755 index 0000000000..0ffcdea1a5 --- /dev/null +++ b/src/library/scalax/collection/Iterable.scala @@ -0,0 +1,1063 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + + +package scalax.collection + +import scala.collection.mutable.{Buffer, ArrayBuffer, ListBuffer} +import util.control.Break._ + +/** Various utilities for instances of Iterable. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 + */ +object Iterable extends SeqFactory[Iterable] { + + type IterableOf[+C[+B] <: Iterable[B], A] = Iterable[A] { type CC[+B] = C[B] } + + /** The empty iterable */ + val empty = new Iterable[Nothing] { + type CC[+B] = Iterable[B] + def elements = Iterator.empty + def newBuilder[B]: Builder[Iterable, B] = null // !!! + } + + class OrderedIterableOps[A](seq: Iterable[A], cmp: Ordering[A]) { + def min: A = { + require(!seq.isEmpty, "min()") + var acc = seq.first + for (x <- seq) + if (cmp.lt(x, acc)) acc = x + acc + } + def max: A = { + require(!seq.isEmpty, "max()") + var acc = seq.first + for (x <- seq) + if (cmp.gt(x, acc)) acc = x + acc + } + } + + class NumericIterableOps[A](seq: Iterable[A], num: Numeric[A]) { + def sum: A = { + var acc = num.zero + for (x <- seq) acc = num.plus(acc, x) + acc + } + def product: A = { + var acc = num.one + for (x <- seq) acc = num.times(acc, x) + acc + } + } + + class PairIterableOps[C[+B] <: Iterable[B], A1, A2](self: C[(A1, A2)]) { + def unzip: (C[A1], C[A2]) = { + val as = self.newBuilder[A1].asInstanceOf[Builder[C, A1]] + val bs = self.newBuilder[A2].asInstanceOf[Builder[C, A2]] + for ((a, b) <- self) { + as += a + bs += b + } + (as.result, bs.result) + } + } + + class IterableIterableOps[C[+B] <: Iterable[B], A](self: C[Iterable[A]]) { + def flatten: C[A] = { + val b = self.newBuilder[A].asInstanceOf[Builder[C, A]] + for (xs <- self) + b ++= xs + b.result + } + } + + implicit def orderedIterableWrapper[A](seq: Iterable[A])(implicit cmp: Ordering[A]) = + new OrderedIterableOps(seq, cmp) + implicit def numericIterableWrapper[A](seq: Iterable[A])(implicit num: Numeric[A]) = + new NumericIterableOps(seq, num) + implicit def pairIterableWrapper[C[+B] <: Iterable[B], A1, A2](seq: C[(A1, A2)]) = + new PairIterableOps[C, A1, A2](seq) + implicit def iterableIterableWrapper[C[+B] <: Iterable[B], A](seq: C[Iterable[A]]) = + new IterableIterableOps[C, A](seq) + + /** The minimum element of a non-empty sequence of ordered elements + * @deprecated use seq.min instead + */ + @deprecated def min[A <% Ordered[A]](seq: Iterable[A]): A = { + val xs = seq.elements + if (!xs.hasNext) throw new IllegalArgumentException("min()") + var min = xs.next + while (xs.hasNext) { + val x = xs.next + if (x < min) min = x + } + min + } + + /** The maximum element of a non-empty sequence of ordered elements + * @deprecated use seq.max instead + */ + @deprecated def max[A <% Ordered[A]](seq: Iterable[A]): A = { + val xs = seq.elements + if (!xs.hasNext) throw new IllegalArgumentException("max()") + var max = xs.next + while (xs.hasNext) { + val x = xs.next + if (max < x) max = x + } + max + } + + /** A non-strict projection of an iterable. + * @author Sean McDirmid + * @author Martin Odersky + abstract class View[+C[+B] <: Iterable[B], +A] extends Iterable[A] { self => + + type CC[+B] <: View[C, A] + + def origin: IterableOf[C, _] + def elements: Iterator[A] + + override val underlying: IterableOf[C, _] = origin.underlying + + private[this] var forced: Option[C[A]] = None + + def force: C[A] = forced match { + case Some(c) => c + case None => + val isDelay = elements eq origin.elements + val result = + if (isDelay) origin.force.asInstanceOf[C[A]] + else { + val b = newBuilder[A] + for (x <- elements) + b += x + b.result + } + this.forced = Some(result) + result + } + + def newBuilder[B]: Builder[C, B] = underlying.newBuilder[B] + + /** The builds a new view object */ + protected def newView[B](elems: Iterator[B]): View[C, B] = new View[C, B] { + val previous = self + val elements = elems + } + + /** Non-strict variant of @see IterableLike.++ */ + override def ++[B >: A](that: Iterator[B]): View[C, B] = newView(elements ++ that) + + /** Non-strict variant of @see IterableLike.++ */ + override def ++[B >: A](that: Iterable[B]): View[C, B] = newView(elements ++ that.elements) + + /** Non-strict variant of @see IterableLike.map */ + override def map[B](f: A => B): View[I, B] = newView(elements map f) + + /** Non-strict variant of @see IterableLike.flatMap */ + override def flatMap[B](f: A => Iterable[B]): View[C, B] = newView(elements flatMap (f(_).elements)) + + /** Non-strict variant of @see IterableLike.filter */ + override def filter(p: A => Boolean): View[C, A] = newView(elements filter p) + + /** Non-strict variant of @see IterableLike.partition */ + override def partition(p: A => Boolean): (View[C, A], View[C, A]) = { + val (li, ri) = elements partition p + (newView(li), newView(ri)) + } + + /** Non-strict variant of @see IterableLike.take */ + override def take(n: Int): View[C, A] = newView(elements take n) + + /** Non-strict variant of @see IterableLike.drop */ + override def drop(n: Int): View[C, A] = newView(elements drop n) + + /** Non-strict variant of @see IterableLike.slice */ + override def slice(from: Int, until: Int): View[C, A] = newView(elements slice (from, until)) + + /** Non-strict variant of @see IterableLike.takeWhile */ + override def takeWhile(p: A => Boolean): View[C, A] = newView(elements takeWhile p) + + /** Non-strict variant of @see IterableLike.dropWhile */ + override def dropWhile(p: A => Boolean): View[C, A] = newView(elements dropWhile p) + + /** Non-strict variant of @see IterableLike.zip */ + override def zip[B](other: Iterable[B]): C[(A, B)] = newView(elements zip other.elements) + + /** Non-strict variant of @see IterableLike.indices */ + override def indices: C[Int] = newView(elements.zipWithIndex map (_._2)) + + /** Non-strict variant of @see IterableLike.zipWithIndex */ + override def zipWithIndex: C[(A, Int)] = newView(elements.zipWithIndex) + + /** Non-strict variant of @see IterableLike.zipAll */ + override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): C[(A1, B1)] = + newView(elements zipAll (that.elements, thisElem, thatElem)) + + /** The projection resulting from the concatenation of this projection with the rest projection. + * @param rest The projection that gets appended to this projection + * @deprecated Use ++ instead + */ + @deprecated def append[B >: A](rest : => Iterable[B]): View[C, B] = this ++ rest.elements + + override def stringPrefix = origin.stringPrefix+"D" + } + */ +/* + /** A non-strict projection of an iterable. + * @author Sean McDirmid + */ + @deprecated trait Projection[+A] extends Iterable[A] { + override def projection = this + /** convert to a copied strict collection */ + def force : Iterable[A] = toList.asInstanceOf[Iterable[A]] //!!! + + /** non-strict */ + override def filter(p : A => Boolean) : Projection[A] = new Projection[A] { + def elements = Projection.this.elements.filter(p) + } + /** non-strict */ + override def map[B](f: A => B) : Projection[B] = new Projection[B] { + def elements = Projection.this.elements.map(f) + } + /** non-strict */ + override def flatMap[B](f: A => Iterable[B]) : Projection[B] = new Projection[B] { + def elements = Projection.this.elements.flatMap(a => f(a).elements) + } + /** non-strict */ + override def takeWhile(p: A => Boolean): Projection[A] = new Projection[A] { + def elements = Projection.this.elements.takeWhile(p) + } + /** The projection resulting from the concatenation of this projection with the rest projection. + * @param rest The projection that gets appended to this projection + */ + def append[B >: A](rest : => Iterable[B]): Projection[B] = new Projection[B] { + def elements = Projection.this.elements ++ rest.elements + } + } +*/ +} + +import Iterable._ + +/** Collection classes mixing in this class provide a method + * elements which returns an iterator over all the + * elements contained in the collection. + * + * @note If a collection has a known size, it should also sub-type Collection. + * Only potentially unbounded collections should directly sub-class Iterable. + * @author Matthias Zenger + * @version 1.1, 04/02/2004 + */ +trait Iterable[+A] { + + /** The type of the underlying iterable object + */ + type CC[+B] <: Iterable[B] + + /** This iterable seen as a CC-typed value */ + def thisCC: CC[A] = this.asInstanceOf[CC[A]] + + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ + def elements: Iterator[A] + + /** Create a new builder for this IterableType + */ + def newBuilder[B]: Builder[CC, B] + + /** Creates a view of this iterable @see Iterable.View + def view: Iterable.View[C, A] = new Iterable.View { + val previous = self + val elements = self.elements + } + */ + + /** Is this collection empty? */ + def isEmpty: Boolean = !elements.hasNext + + /** returns true iff this collection has a bound size. + * Many APIs in this trait will not work on collections of + * unbound sizes. + */ + def hasDefiniteSize = true + + /** Create a new sequence of type CC which contains all elements of this sequence + * followed by all elements of Iterable `that' + */ + def ++[B >: A](that: Iterable[B]): CC[B] = { + val b = newBuilder[B] + b ++= this + b ++= that + b.result + } + + /** Create a new sequence of type IterableType which contains all elements of this sequence + * followed by all elements of Iterator `that' + */ + def ++[B >: A](that: Iterator[B]): CC[B] = { + val b = newBuilder[B] + b ++= this + b ++= that + b.result + } + + /** Returns the sequence resulting from applying the given function + * f to each element of this sequence. + * + * @param f function to apply to each element. + * @return f(a0), ..., f(an) if this + * sequence is a0, ..., an. + */ + def map[B](f: A => B): CC[B] = { + val b = newBuilder[B] + for (x <- this) b += f(x) + b.result + } + + /** Applies the given function f to each element of + * this sequence, then concatenates the results. + * + * @param f the function to apply on each element. + * @return f(a0) ::: ... ::: f(an) if + * this sequence is a0, ..., an. + */ + def flatMap[B](f: A => Iterable[B]): CC[B] = { + val b = newBuilder[B] + for (x <- this) b ++= f(x) + b.result + } + + /** Returns all the elements of this sequence that satisfy the + * predicate p. The order of the elements is preserved. + * It is guaranteed that the receiver iterable + * itself is returned iff all its elements satisfy the predicate `p'. + * Hence the following equality is valid: + * + * (xs filter p) eq xs == xs forall p + * + * @param p the predicate used to filter the list. + * @return the elements of this list satisfying p. + */ + def filter(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + var allTrue = true + for (x <- this) + if (p(x)) b += x + else allTrue = false + if (allTrue) thisCC + else b.result + } + + /** Removes all elements of the iterable which satisfy the predicate + * p. This is like filter with the + * predicate inversed. + * + * @param p the predicate to use to test elements + * @return the list without all elements which satisfy p + */ + def remove(p: A => Boolean): CC[A] = filter(!p(_)) + + /** Partitions this iterable in two iterables according to a predicate. + * + * @param p the predicate on which to partition + * @return a pair of iterables: the iterable that satisfies the predicate + * p and the iterable that does not. + * The relative order of the elements in the resulting iterables + * is the same as in the original iterable. + */ + def partition(p: A => Boolean): (CC[A], CC[A]) = { + val l, r = newBuilder[A] + for (x <- this) (if (p(x)) l else r) += x + (l.result, r.result) + } + + /** Apply a function f to all elements of this + * iterable object. + * + * @note Will not terminate for infinite-sized collections. + * @param f a function that is applied to every element. + * Note this function underlies the implementation of most other bulk operations. + * It should be overridden in concrete collectionc classes with efficient implementations. + */ + def foreach(f: A => Unit): Unit = elements.foreach(f) + + /** The first element of this sequence. + * + * @throws Predef.NoSuchAentException if the sequence is empty. + */ + def first: A = if (isEmpty) throw new NoSuchElementException else elements.next + + /** Returns as an option the first element of this list or + * None if list is empty. + */ + def firstOption: Option[A] = if (isEmpty) None else Some(first) + + /** Return an iterable consisting only over the first n + * elements of this iterable, or else the whole iterable, if it has less + * than n elements. + * + * @param n the number of elements to take + * @return a possibly projected sequence + */ + def take(n: Int): CC[A] = { + val b = newBuilder[A] + var i = 0 + breakable { + for (x <- this) { + b += x + i += 1 + if (i == n) break + } + } + b.result + } + + /** Returns this collection without its n first elements + * If this collection has less than n elements, the empty + * collection is returned. + * + * @param n the number of elements to drop + * @return the new collection + */ + def drop(n: Int): CC[A] = { + val b = newBuilder[A] + var i = 0 + for (x <- this) { + if (i >= n) b += x + i += 1 + } + b.result + } + + /** A sub-sequence starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the returned subsequence + * @param until The index of the element following the returned subsequence + * @throws IndexOutOfBoundsException if from < 0 + * or length < from + len + */ + def slice(from: Int, until: Int): CC[A] = { + val b = newBuilder[A] + var i = 0 + breakable { + for (x <- this) { + if (i >= from) b += x + i += 1 + if (i == until) break + } + } + b.result + } + + /** A sub-sequence view starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + * @note The difference between `subseq` and `slice` is that `slice` produces + * a view of the current sequence, whereas `subseq` produces a new sequence. + * !!! + def view(from: Int, until: Int) = subseq(from, until) + // : Iterable.View[C, A] = view.slice(from, until) + */ + + /** An iterable consisting of all elements of this iterable except the last one. + */ + def init: CC[A] = { + var last: A = first + val b = newBuilder[A] + for (x <- this) { + b += last + last = x + } + b.result + } + + /** Returns the rightmost n elements from this iterable. + * + * @param n the number of elements to take + */ + def takeRight(n: Int): CC[A] = { + val b = newBuilder[A] + val lead = elements drop n + var go = false + for (x <- this) { + if (go) b += x + else if (lead.hasNext) lead.next + else go = true + } + b.result + } + + /** Returns the iterable wihtout its rightmost n elements. + * + * @param n the number of elements to take + */ + def dropRight(n: Int): CC[A] = { + val b = newBuilder[A] + val lead = elements drop n + breakable { + for (x <- this) { + if (!lead.hasNext) break + lead.next + b += x + } + } + b.result + } + + /** Split the iterable at a given point and return the two parts thus + * created. + * + * @param n the position at which to split + * @return a pair of iterables composed of the first n + * elements, and the other elements. + */ + def splitAt(n: Int): (CC[A], CC[A]) = { + val l, r = newBuilder[A] + var i = 0 + for (x <- this) + (if (i < n) l else r) += x + (l.result, r.result) + } + + /** Returns the longest prefix of this sequence whose elements satisfy + * the predicate p. + * + * @param p the test predicate. + * @return the longest prefix of this sequence whose elements satisfy + * the predicate p. + */ + def takeWhile(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + breakable { + for (x <- this) { + if (!p(x)) break + b += x + } + } + b.result + } + + /** Returns the longest suffix of this sequence whose first element + * does not satisfy the predicate p. + * + * @param p the test predicate. + * @return the longest suffix of the sequence whose first element + * does not satisfy the predicate p. + */ + def dropWhile(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + var go = false + for (x <- this) { + if (go) b += x + else if (!p(x)) { go = true; b += x } + } + b.result + } + + /** Returns a pair consisting of the longest prefix of the list whose + * elements all satisfy the given predicate, and the rest of the list. + * + * @param p the test predicate + * @return a pair consisting of the longest prefix of the list whose + * elements all satisfy p, and the rest of the list. + */ + def span(p: A => Boolean): (CC[A], CC[A]) = { + val l, r = newBuilder[A] + var toLeft = true + for (x <- this) { + toLeft = toLeft && p(x) + (if (toLeft) l else r) += x + } + (l.result, r.result) + } + + /** Return true iff the given predicate `p` yields true for all elements + * of this iterable. + * + * @note May not terminate for infinite-sized collections. + * @param p the predicate + */ + def forall(p: A => Boolean): Boolean = { + var result = true + breakable { + for (x <- this) + if (!p(x)) { result = false; break } + } + result + } + + /** Return true iff there is an element in this iterable for which the + * given predicate `p` yields true. + * + * @note May not terminate for infinite-sized collections. + * @param p the predicate + */ + def exists(p: A => Boolean): Boolean = { + var result = false + breakable { + for (x <- this) + if (p(x)) { result = true; break } + } + result + } + + /** Count the number of elements in the iterable which satisfy a predicate. + * + * @param p the predicate for which to count + * @return the number of elements satisfying the predicate p. + */ + def count(p: A => Boolean): Int = { + var cnt = 0 + for (x <- this) { + if (p(x)) cnt += 1 + } + cnt + } + + /** Find and return the first element of the iterable object satisfying a + * predicate, if any. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @return an option containing the first element in the iterable object + * satisfying p, or None if none exists. + */ + def find(p: A => Boolean): Option[A] = { + var result: Option[A] = None + breakable { + for (x <- this) + if (p(x)) { result = Some(x); break } + } + result + } + + /** Returns index of the first element satisying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + */ + def indexWhere(p: A => Boolean): Int = indexWhere(p, 0) + + /** Returns index of the first element starting from a start index + * satisying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @param from the start index + */ + def indexWhere(p: A => Boolean, from: Int): Int = { + var result = -1 + var i = from + breakable { + for (x <- this) { + if (i >= from && p(x)) { result = i; break } + else i += 1 + } + } + result + } + + /** Returns index of the first element satisying a predicate, or -1. + * + * @deprecated Use `indexWhere` instead + */ + @deprecated def findIndexOf(p: A => Boolean): Int = indexWhere(p) + + /** Returns the index of the first occurence of the specified + * object in this iterable object. + * + * @note may not terminate for infinite-sized collections. + * @param elem element to search for. + * @return the index in this sequence of the first occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + def indexOf[B >: A](elem: B): Int = indexOf(elem, 0) + + /** Returns the index of the first occurence of the specified + * object in this iterable object, starting from a start index, or + * -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param elem element to search for. + */ + def indexOf[B >: A](elem: B, from: Int): Int = { + var result = -1 + var i = from + breakable { + for (x <- this) { + if (x == elem) { result = i; break } + else i += 1 + } + } + result + } + + /** Combines the elements of this iterable object together using the binary + * function f, from left to right, and starting with + * the value z. + * + * @note Will not terminate for infinite-sized collections. + * @return f(... (f(f(z, a0), a1) ...), + * an) if the list is + * [a0, a1, ..., an]. + */ + def foldLeft[B](z: B)(op: (B, A) => B): B = { + var result = z + for (x <- this) + result = op(result, x) + result + } + + /** Combines the elements of this list together using the binary + * function f, from right to left, and starting with + * the value z. + * + * @note Will not terminate for infinite-sized collections. + * @return f(a0, f(a1, f(..., f(an, z)...))) + * if the list is [a0, a1, ..., an]. + */ + def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op) + + /** Similar to foldLeft but can be used as + * an operator with the order of list and zero arguments reversed. + * That is, z /: xs is the same as xs foldLeft z + * @note Will not terminate for infinite-sized collections. + */ + def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) + + /** An alias for foldRight. + * That is, xs :\ z is the same as xs foldRight z + * @note Will not terminate for infinite-sized collections. + */ + def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op) + + /** Combines the elements of this iterable object together using the binary + * operator op, from left to right + * @note Will not terminate for infinite-sized collections. + * @param op The operator to apply + * @return op(... op(a0,a1), ..., an) + if the iterable object has elements + * a0, a1, ..., an. + * @throws Predef.UnsupportedOperationException if the iterable object is empty. + */ + def reduceLeft[B >: A](op: (B, A) => B): B = { + if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") + var result: B = elements.next + var first = true + for (x <- this) + if (first) first = false + else result = op(result, x) + result + } + + /** Combines the elements of this iterable object together using the binary + * operator op, from right to left + * @note Will not terminate for infinite-sized collections. + * @param op The operator to apply + * + * @return a0 op (... op (an-1 op an)...) + * if the iterable object has elements a0, a1, ..., + * an. + * + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + def reduceRight[B >: A](op: (A, B) => B): B = + elements.reduceRight(op) + + /** Returns an iterable formed from this iterable and the specified list + * `other` by associating each element of the former with + * the element at the same position in the latter. + * If one of the two iterables is longer than the other, its remaining elements are ignored. + */ + def zip[B](that: Iterable[B]): CC[(A, B)] = { + val these = this.elements + val those = that.elements + val b = this.newBuilder[(A, B)] + while (these.hasNext && those.hasNext) + b += ((these.next, those.next)) + b.result + } + + /** Returns a iterable formed from this iterable and the specified iterable + * that by associating each element of the former with + * the element at the same position in the latter. + * + * @param that iterable that may have a different length + * as the self iterable. + * @param thisElem element thisElem is used to fill up the + * resulting iterable if the self iterable is shorter than + * that +b * @param thatElem element thatElem is used to fill up the + * resulting iterable if that is shorter than + * the self iterable + * @return Iterable((a0,b0), ..., + * (an,bn), (elem,bn+1), + * ..., {elem,bm}) + * when [a0, ..., an] zip + * [b0, ..., bm] is + * invoked where m > n. + */ + def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): CC[(A1, B1)] = { + val these = this.elements + val those = that.elements + val b = newBuilder[(A1, B1)] + while (these.hasNext && those.hasNext) + b += ((these.next, those.next)) + while (these.hasNext) + b += ((these.next, thatElem)) + while (those.hasNext) + b += ((thisElem, those.next)) + b.result + } + + /** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to + * `s zip s.indices`, but is usually more efficient. + */ + def zipWithIndex: CC[(A, Int)] = { + val b = newBuilder[(A, Int)] + var i = 0 + for (x <- this) { + b += (x, i) + i +=1 + } + b.result + } + + /** Copy all elements to a given buffer + * @note Will not terminate for infinite-sized collections. + * @param dest The buffer to which elements are copied + */ + def copyToBuffer[B >: A](dest: Buffer[B]) { + for (x <- this) dest += x + } + + /** Fills the given array xs with at most `len` elements of + * this sequence starting at position `start`. + * Copying will stop oce either the end of the current iterable is reached or + * `len` elements have been copied. + * + * @note Will not terminate for infinite-sized collections. + * @param xs the array to fill. + * @param start starting index. + * @param len number of elements to copy + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int, len: Int): Unit = { + var i = start + val end = (start + len) min xs.length + for (x <- this) { + if (i < end) { + xs(i) = x + i += 1 + } + } + } + + /** Fills the given array xs with the elements of + * this sequence starting at position start + * until either the end of the current iterable or the end of array `xs` is reached. + * + * @note Will not terminate for infinite-sized collections. + * @param xs the array to fill. + * @param start starting index. + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int): Unit = + copyToArray(xs, start, xs.length - start) + + /** Converts this collection to a fresh Array with size elements. + * @note Will not terminate for infinite-sized collections. + */ + def toArray[B >: A]: Array[B] = { + var size = 0 + for (x <- this) size += 1 + val result = new Array[B](size) + copyToArray(result, 0) + result + } + + /** Checks if the other iterable object contains the same elements. + * + * @note will not terminate for infinite-sized collections. + * @param that the other iterable object + * @return true, iff both iterable objects contain the same elements. + */ + def sameElements[B >: A](that: Iterable[B]): Boolean = { + val ita = this.elements + val itb = that.elements + var res = true + while (res && ita.hasNext && itb.hasNext) { + res = (ita.next == itb.next) + } + !ita.hasNext && !itb.hasNext && res + } + + /** + * Create a fresh list with all the elements of this iterable object. + * @note Will not terminate for infinite-sized collections. + */ + def toList: List[A] = { + val b = new ListBuffer[A]() + b ++= this.asInstanceOf[scala.Iterable[A]] // !!! + b.toList + } + + /** + * Returns a sequence containing all of the elements in this iterable object. + * @note Will not terminate for infinite-sized collections. + */ + def toSeq: Seq[A] = toList + + /** + * Create a stream which contains all the elements of this iterable object. + * @note consider using projection for lazy behavior. + */ + def toStream: Stream[A] = elements.toStream + + /** Sort the iterable according to the comparison function + * <(e1: a, e2: a) => Boolean, + * which should be true iff e1 is smaller than + * e2. + * The sort is stable. That is elements that are equal wrt `lt` appear in the + * same order in the sorted iterable as in the original. + * + * @param lt the comparison function + * @return a list sorted according to the comparison function + * <(e1: a, e2: a) => Boolean. + * @ex 
+   *    List("Steve", "Tom", "John", "Bob")
+   *      .sort((e1, e2) => (e1 compareTo e2) < 0) =
+   *    List("Bob", "John", "Steve", "Tom")
+ * !!! + def sortWith(lt : (A,A) => Boolean): CC[A] = { + val arr = toArray + Array.sortWith(arr, lt) + val b = newBuilder[A] + for (x <- arr) b += x + b.result + } + */ + + /** Returns a string representation of this iterable object. The resulting string + * begins with the string start and is finished by the string + * end. Inside, the string representations of elements (w.r.t. + * the method toString()) are separated by the string + * sep. + * + * @ex List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)" + * @note Will not terminate for infinite-sized collections. + * @param start starting string. + * @param sep separator string. + * @param end ending string. + * @return a string representation of this iterable object. + */ + def mkString(start: String, sep: String, end: String): String = + addString(new StringBuilder(), start, sep, end).toString + + /** Returns a string representation of this iterable object. The string + * representations of elements (w.r.t. the method toString()) + * are separated by the string sep. + * + * @note Will not terminate for infinite-sized collections. + * @param sep separator string. + * @return a string representation of this iterable object. + */ + def mkString(sep: String): String = + addString(new StringBuilder(), sep).toString + + /** Converts a collection into a flat String by each element's toString method. + * @note Will not terminate for infinite-sized collections. + */ + def mkString = + addString(new StringBuilder()).toString + + /** Write all elements of this iterable into given string builder. + * The written text begins with the string start and is finished by the string + * end. Inside, the string representations of elements (w.r.t. + * the method toString()) are separated by the string + * sep. + * @note Will not terminate for infinite-sized collections. + */ + def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = { + b append start + var first = true + for (x <- this) { + if (first) first = false + else b append sep + b append x + } + b append end + } + + /** Write all elements of this string into given string builder. + * The string representations of elements (w.r.t. the method toString()) + * are separated by the string sep. + * @note Will not terminate for infinite-sized collections. + */ + def addString(b: StringBuilder, sep: String): StringBuilder = { + var first = true + for (x <- this) { + if (first) first = false + else b append sep + b append x + } + b + } + + /** Write all elements of this string into given string builder without using + * any separator between consecutive elements. + * @note Will not terminate for infinite-sized collections. + */ + def addString(b: StringBuilder): StringBuilder = { + for (x <- this) { + b append x + } + b + } + + /** + * returns a projection that can be used to call non-strict filter, + * map, and flatMap methods that build projections + * of the collection. + def projection : Iterable.Projection[A] = new Iterable.Projection[A] { + def elements = Iterable.this.elements + override def force = Iterable.this + } + */ + + override def toString = mkString(stringPrefix + "(", ", ", ")") + + /** Defines the prefix of this object's toString representation. + */ + protected def stringPrefix : String = { + var string = this.getClass.getName + val idx1 = string.lastIndexOf('.' : Int) + if (idx1 != -1) string = string.substring(idx1 + 1) + val idx2 = string.indexOf('$') + if (idx2 != -1) string = string.substring(0, idx2) + string + } +} + + + diff --git a/src/library/scalax/collection/Iterator.scala b/src/library/scalax/collection/Iterator.scala new file mode 100755 index 0000000000..dc80c10f6b --- /dev/null +++ b/src/library/scalax/collection/Iterator.scala @@ -0,0 +1,965 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterator.scala 15939 2008-08-26 14:33:17Z stepancheg $ + + +package scalax.collection + +import scala.collection.mutable.{Buffer, ListBuffer, ArrayBuffer} + +/** The Iterator object provides various functions for + * creating specialized iterators. + * + * @author Martin Odersky + * @author Matthias Zenger + * @version 2.8 + */ +object Iterator { + + val empty = new Iterator[Nothing] { + def hasNext: Boolean = false + def next(): Nothing = throw new NoSuchElementException("next on empty iterator") + } + + def apply[A](args: A*): Iterator[A] = args.asInstanceOf[Iterable[A]].elements // !!! + + /** Concatenate all the argument iterators into a single iterator. + * + * @param xss the lists that are to be concatenated + * @return the concatenation of all the lists + */ + def concat[A](xss: Iterator[A]*): Iterator[A] = + xss.asInstanceOf[Iterable[Iterator[A]]].elements.flatten // !!! + + /** An iterator that returns the same element a number of times + * @param len The number of elements returned + * @param elem The element returned each time + */ + def fill[A](len: Int)(elem: => A) = new Iterator[A] { + private var i = 0 + def hasNext: Boolean = i < len + def next(): A = + if (hasNext) { i += 1; elem } + else empty.next() + } + + /** An iterator that returns values of a function f(0), ..., f(n-1), + * for given `f` and `n`. + */ + def tabulate[A](n: Int)(f: Int => A) = new Iterator[A] { + private var i = 0 + def hasNext: Boolean = i < n + def next(): A = + if (hasNext) { val result = f(i); i += 1; result } + else empty.next() + } + + /** Nn iterator with elements + * en+1 = en + 1 + * where e0 = start + * and ei < end. However, + * if start ≥ end, then it will return an empty range. + * + * @param start the start value of the iterator + * @param end the end value of the iterator + * @return the iterator with values in range [start;end). + */ + def range(start: Int, end: Int): Iterator[Int] = range(start, end, 1) + + /** Create an iterator with elements + * en+1 = en + step + * where e0 = start + * and elements are in the range between start (inclusive) + * and end (exclusive) + * + * @param start the start value of the iterator + * @param end the end value of the iterator + * @param step the increment value of the iterator (must be positive or negative) + * @return the iterator with values in range [start;end). + */ + def range(start: Int, end: Int, step: Int) = new Iterator[Int] { + private var i = start + def hasNext: Boolean = (step <= 0 || i < end) && (step >= 0 || i > end) + def next(): Int = + if (hasNext) { val result = i; i += step; result } + else empty.next() + } + + /** An iterator that repeatedly applies a given function to a start value. + * + * @param start the start value of the iteratpr + * @param len the number of elements returned by the iterator + * @param f the function that's repeatedly applied + * @return the iterator returning values (start, f(start), f(f(start)), ..., flen-1(start)) + */ + def iterate(start: Int, len: Int)(f: Int => Int) = new Iterator[Int] { + private var acc = start + private var i = 0 + def hasNext: Boolean = i < len + def next(): Int = + if (hasNext) { val result = f(acc); i += 1; result } + else empty.next() + } + + /** An infinite iterator that repeatedly applies a given function to a start value. + * + * @param start the start value of the iteratpr + * @param f the function that's repeatedly applied + * @return the iterator returning values (start, f(start), f(f(start)), ..., flen-1(start)) + */ + def iterate(start: Int)(f: Int => Int) = new Iterator[Int] { + private var acc = start + private var i = 0 + def hasNext: Boolean = true + def next(): Int = { val result = f(acc); i += 1; result } + } + + /** Create an iterator with elements + * en+1 = en + 1 + * where e0 = start. + * + * @param start the start value of the iterator + * @return the iterator starting at value start. + */ + def from(start: Int): Iterator[Int] = from(start, 1) + + /** Create an iterator with elements + * en+1 = en + step + * where e0 = start. + * + * @param start the start value of the iterator + * @param step the increment value of the iterator + * @return the iterator starting at value start. + */ + def from(start: Int, step: Int): Iterator[Int] = new Iterator[Int] { + private var i = 0 + def hasNext: Boolean = true + def next(): Int = { val result = i; i += 1; result } + } + + class IteratorIteratorOps[A](its: Iterator[Iterator[A]]) { + /** Create an iterator that is the concantenation of all iterators + * returned by a given iterator of iterators. + * @param its The iterator which returns on each call to next + * a new iterator whose elements are to be concatenated to the result. + */ + def flatten: Iterator[A] = new Iterator[A] { + private var it = its.next + def hasNext: Boolean = { + while (!it.hasNext && its.hasNext) it = its.next + it.hasNext + } + def next(): A = + if (hasNext) it.next + else empty.next() + } + } + + implicit def iteratorIteratorWrapper[A](its: Iterator[Iterator[A]]): IteratorIteratorOps[A] = + new IteratorIteratorOps[A](its) + + /** + * @param x the element + * @return the iterator with one single element + * @deprecated use Iterator(x) instead + */ + @deprecated def single[a](x: a) = new Iterator[a] { + private var hasnext = true + def hasNext: Boolean = hasnext + def next(): a = + if (hasnext) { hasnext = false; x } + else empty.next() + } + + /** @deprecated use `xs.elements` instead + */ + @deprecated def fromValues[a](xs: a*) = xs.elements + + /** + * @param xs the array of elements + * @see also: RandomAccessSeq.elements and slice + * @deprecated use `xs.elements` instead + */ + @deprecated def fromArray[a](xs: Array[a]): Iterator[a] = + fromArray(xs, 0, xs.length) + + /** + * @param xs the array of elements + * @param start the start index + * @param length the length + * @see also: RandomAccessSeq.elements and slice + * @deprecated use `xs.slice(start, start + length).elements` instead + */ + @deprecated def fromArray[a](xs: Array[a], start: Int, length: Int): Iterator[a] = + xs.slice(start, start + length).elements.asInstanceOf[Iterator[a]] // !!! + + /** + * @param str the given string + * @return the iterator on str + * @deprecated replaced by str.elements + */ + @deprecated def fromString(str: String): Iterator[Char] = + str.elements.asInstanceOf[Iterator[Char]] // !!! + + /** + * @param n the product arity + * @return the iterator on Product<n>. + * @deprecated use product.productElements instead + */ + @deprecated def fromProduct(n: Product): Iterator[Any] = new Iterator[Any] { + private var c: Int = 0 + private val cmax = n.productArity + def hasNext = c < cmax + def next() = { val a = n productElement c; c += 1; a } + } + + /** Create an iterator with elements + * en+1 = step(en) + * where e0 = start + * and elements are in the range between start (inclusive) + * and end (exclusive) + * + * @param start the start value of the iterator + * @param end the end value of the iterator + * @param step the increment function of the iterator, must be monotonically increasing or decreasing + * @return the iterator with values in range [start;end). + * @deprecated use Iterator.iterate(start, end - start)(step) instead + */ + @deprecated def range(start: Int, end: Int, step: Int => Int) = new Iterator[Int] { + private val up = step(start) > start + private val down = step(start) < start + private var i = start + def hasNext: Boolean = (!up || i < end) && (!down || i > end) + def next(): Int = + if (hasNext) { val j = i; i = step(i); j } + else empty.next() + } + + /** Create an iterator with elements + * en+1 = step(en) + * where e0 = start. + * + * @param start the start value of the iterator + * @param step the increment function of the iterator + * @return the iterator starting at value start. + * @deprecated use iterate(start)(step) instead + */ + @deprecated def from(start: Int, step: Int => Int): Iterator[Int] = new Iterator[Int] { + private var i = start + override def hasNext: Boolean = true + def next(): Int = { val j = i; i = step(i); j } + } + + /** Create an iterator that is the concantenation of all iterators + * returned by a given iterator of iterators. + * @param its The iterator which returns on each call to next + * a new iterator whose elements are to be concatenated to the result. + * @deprecated use its.flatten instead + */ + @deprecated def flatten[T](its: Iterator[Iterator[T]]): Iterator[T] = new Iterator[T] { + private var it = its.next + def hasNext: Boolean = { + while (!it.hasNext && its.hasNext) it = its.next + it.hasNext + } + def next(): T = + if (hasNext) it.next + else empty.next() + } +} + +import Iterator.empty + +/** Iterators are data structures that allow to iterate over a sequence + * of elements. They have a hasNext method for checking + * if there is a next element available, and a next method + * which returns the next element and discards it from the iterator. + * + * @author Martin Odersky, Matthias Zenger + * @version 2.8 + */ +trait Iterator[+A] { +self => + + /** Does this iterator provide another element? + */ + def hasNext: Boolean + + /** Returns the next element. + */ + def next(): A + + /** Returns a new iterator that iterates only over the first n + * elements. + * + * @param n the number of elements to take + * @return the new iterator + */ + def take(n: Int): Iterator[A] = new Iterator[A] { + private var remaining = n + def hasNext = remaining > 0 && self.hasNext + def next(): A = + if (hasNext) { remaining -= 1; self.next } + else throw new NoSuchElementException("next on empty iterator") + } + + /** Removes the first n elements from this iterator. + * + * @param n the number of elements to drop + * @return the new iterator + */ + def drop(n: Int): Iterator[A] = + if (n > 0 && hasNext) { next(); drop(n - 1) } else this + + /** A sub-iterator of until - from elements + * starting at index from + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + */ + def slice(from: Int, until: Int): Iterator[A] = drop(from).take(until - from) + + /** Returns a new iterator that maps all elements of this iterator + * to new elements using function f. + */ + def map[B](f: A => B): Iterator[B] = new Iterator[B] { + def hasNext = self.hasNext + def next() = f(self.next()) + } + + /** Returns a new iterator that first yields the elements of this + * iterator followed by the elements provided by iterator that. + * @deprecated use ++ + */ + def append[B >: A](that: Iterator[B]) = new Iterator[B] { + def hasNext = self.hasNext || that.hasNext + def next() = (if (self.hasNext) self else that).next() + } + + /** Returns a new iterator that first yields the elements of this + * iterator followed by the elements provided by iterator that. + */ + def ++[B >: A](that: => Iterator[B]) = new Iterator[B] { + // optimize a little bit to prevent n log n behavior. + var cur : Iterator[B] = self + def hasNext = cur.hasNext || (cur eq self) && { cur = that; hasNext } + def next() = { hasNext; cur.next } + } + + /** Applies the given function f to each element of + * this iterator, then concatenates the results. + * + * @param f the function to apply on each element. + * @return an iterator over f(a0), ... , + * f(an) if this iterator yields the + * elements a0, ..., an. + */ + def flatMap[B](f: A => Iterator[B]): Iterator[B] = new Iterator[B] { + private var cur: Iterator[B] = empty + def hasNext: Boolean = + cur.hasNext || self.hasNext && { cur = f(self.next); hasNext } + def next(): B = (if (hasNext) cur else empty).next() + } + + /** Returns an iterator over all the elements of this iterator that + * satisfy the predicate p. The order of the elements + * is preserved. + * + * @param p the predicate used to filter the iterator. + * @return the elements of this iterator satisfying p. + */ + def filter(p: A => Boolean): Iterator[A] = { + val self = buffered + new Iterator[A] { + private def skip() = while (self.hasNext && !p(self.head)) self.next() + def hasNext = { skip(); self.hasNext } + def next() = { skip(); self.next() } + } + } + + /** Returns an iterator over the longest prefix of this iterator such that + * all elements of the result satisfy the predicate p. + * The order of the elements is preserved. + * + * The behavior of this iterator is undefined after this method invocation. + * + * @param p the predicate used to filter the iterator. + * @return the longest prefix of this iterator satisfying p. + */ + def takeWhile(p: A => Boolean): Iterator[A] = { + val self = buffered + new Iterator[A] { + def hasNext = { self.hasNext && p(self.head) } + def next() = (if (hasNext) self else empty).next() + } + } + + /** Partitions this iterator in two iterators according to a predicate. + * + * @param p the predicate on which to partition + * @return a pair of iterators: the iterator that satisfies the predicate + * p and the iterator that does not. + * The relative order of the elements in the resulting iterators + * is the same as in the original iterator. + */ + def partition(p: A => Boolean): (Iterator[A], Iterator[A]) = { + val self = buffered + class PartitionIterator(p: A => Boolean) extends Iterator[A] { + var other: PartitionIterator = _ + val lookahead = new scala.collection.mutable.Queue[A] + def skip() = + while (self.hasNext && !p(self.head)) { + other.lookahead += self.next + } + def hasNext = !lookahead.isEmpty || self.hasNext + def next() = if (lookahead.isEmpty) self.next() else lookahead.dequeue() + } + val l = new PartitionIterator(p) + val r = new PartitionIterator(!p(_)) + l.other = r + r.other = l + (l, r) + } + + /** Skips longest sequence of elements of this iterator which satisfy given + * predicate p, and returns an iterator of the remaining elements. + * + * The behavior of this iterator is undefined after this method invocation. + * + * @param p the predicate used to skip elements. + * @return an iterator consisting of the remaining elements + */ + def dropWhile(p: A => Boolean): Iterator[A] = { + val self = buffered + new Iterator[A] { + var dropped = false + private def skip() = + if (!dropped) { + while (self.hasNext && p(self.head)) self.next() + dropped = true + } + def hasNext = { skip(); self.hasNext } + def next() = { skip(); self.next() } + } + } + + /** Return an iterator formed from this iterator and the specified iterator + * that by associating each element of the former with + * the element at the same position in the latter. + * If one of the two iterators is longer than the other, its remaining elements are ignored. + * + * @return an iterator yielding {a0,b0}, + * {a1,b1}, ... where + * ai are the elements from this iterator + * and bi are the elements from iterator + * that. + */ + def zip[B](that: Iterator[B]) = new Iterator[(A, B)] { + def hasNext = self.hasNext && that.hasNext + def next = (self.next, that.next) + } + + /** Return an iterator that pairs each element of this iterator + * with its index, counting from 0. + * + * @return an iterator yielding {a0,0}, + * {a1,1}... where ai + * are the elements from this iterator. + */ + def zipWithIndex = new Iterator[(A, Int)] { + var idx = 0 + def hasNext = self.hasNext + def next = { + val ret = (self.next, idx) + idx += 1 + ret + } + } + + /** Returns an iterator formed from this iterator and the specified iterator + * that by associating each element of the former with + * the element at the same position in the latter. + * + * @param that iterator that may have a different length + * as the self iterator. + * @param thisElem element thisElem is used to fill up the + * resulting iterator if the self iterator is shorter than + * that + * @param thatElem element thatElem is used to fill up the + * resulting iterator if that is shorter than + * the self iterator + * @return Iterator((a0,b0), ..., + * (an,bn), (elem,bn+1), + * ..., {elem,bm}) + * when [a0, ..., an] zip + * [b0, ..., bm] is + * invoked where m > n. + */ + def zipAll[B, A1 >: A, B1 >: B](that: Iterator[B], thisElem: A1, thatElem: B1) = new Iterator[(A1, B1)] { + def hasNext = self.hasNext || that.hasNext + def next(): (A1, B1) = + if (self.hasNext) { + if (that.hasNext) (self.next(), that.next()) + else (self.next(), thatElem) + } else { + if (that.hasNext) (thisElem, that.next()) + else empty.next() + } + } + + /** Apply a function f to all elements of this + * iterable object. + * + * @param f a function that is applied to every element. + */ + def foreach(f: A => Unit) { while (hasNext) f(next()) } + + /** Apply a predicate p to all elements of this + * iterable object and return true iff the predicate yields + * true for all elements. + * + * @param p the predicate + * @return true iff the predicate yields true + * for all elements. + */ + def forall(p: A => Boolean): Boolean = { + var res = true + while (res && hasNext) res = p(next()) + res + } + + /** Apply a predicate p to all elements of this + * iterable object and return true, iff there is at least one + * element for which p yields true. + * + * @param p the predicate + * @return true iff the predicate yields true + * for at least one element. + */ + def exists(p: A => Boolean): Boolean = { + var res = false + while (!res && hasNext) res = p(next()) + res + } + + /** Tests if the given value elem is a member of this iterator. + * + * @param elem element whose membership has to be tested. + * @return true iff there is an element of this iterator which + * is equal (w.r.t. ==) to elem. + */ + def contains(elem: Any): Boolean = exists { _ == elem } + + /** Find and return the first element of the iterable object satisfying a + * predicate, if any. + * + * @param p the predicate + * @return the first element in the iterable object satisfying + * p, or None if none exists. + */ + def find(p: A => Boolean): Option[A] = { + var res: Option[A] = None + while (res.isEmpty && hasNext) { + val e = next() + if (p(e)) res = Some(e) + } + res + } + + /** Returns index of the first element satisying a predicate, or -1. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @return the index of the first element satisfying p, + * or -1 if such an element does not exist + */ + def indexWhere(p: A => Boolean): Int = { + var i = 0 + var found = false + while (!found && hasNext) { + if (p(next())) { + found = true + } else { + i += 1 + } + } + if (found) i else -1 + } + + /** Returns index of the first element satisying a predicate, or -1. + * + * @deprecated use `indexWhere` instead + */ + @deprecated def findIndexOf(p: A => Boolean): Int = indexWhere(p) + + /** Returns the index of the first occurence of the specified + * object in this iterable object. + * + * @note may not terminate for infinite-sized collections. + * @param elem element to search for. + * @return the index in this sequence of the first occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + def indexOf[B >: A](elem: B): Int = { + var i = 0 + var found = false + while (!found && hasNext) { + if (next() == elem) { + found = true + } else { + i += 1 + } + } + if (found) i else -1 + } + + /** Combines the elements of this iterator together using the binary + * operator op, from left to right, and starting with + * the value z. + * + * @return op(... (op(op(z,a0),a1) ...), + * an) if the iterator yields elements + * a0, a1, ..., an. + */ + def foldLeft[B](z: B)(op: (B, A) => B): B = { + var acc = z + while (hasNext) acc = op(acc, next()) + acc + } + + /** Combines the elements of this iterator together using the binary + * operator op, from right to left, and starting with + * the value z. + * + * @return a0 op (... op (an op z)...) + * if the iterator yields elements a0, a1, ..., + * an. + */ + def foldRight[B](z: B)(op: (A, B) => B): B = { + def fold(z: B): B = if (hasNext) op(next(), fold(z)) else z + fold(z) + } + + /** Similar to foldLeft but can be used as + * an operator with the order of iterator and zero arguments reversed. + * That is, z /: xs is the same as xs foldLeft z. + * + * @param z the left argument of the first application of op + * (evaluation occurs from left to right). + * @param op the applied operator. + * @return the result value + * @see foldLeft. + */ + def /:[B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) + + /** An alias for foldRight. + * That is, xs :\ z is the same as xs foldRight z. + * + * @param z the right argument of the first application of op + * (evaluation occurs from right to left). + * @param op the applied operator. + * @return the result value. + * @see foldRight. + */ + def :\[B](z: B)(op: (A, B) => B): B = foldRight(z)(op) + + /** Combines the elements of this iterator together using the binary + * operator op, from left to right + * @param op The operator to apply + * @return op(... op(a0,a1), ..., an) + if the iterator yields elements + * a0, a1, ..., an. + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + def reduceLeft[B >: A](op: (B, A) => B): B = { + if (hasNext) foldLeft[B](next())(op) + else throw new UnsupportedOperationException("empty.reduceLeft") + } + + /** Combines the elements of this iterator together using the binary + * operator op, from right to left + * @param op The operator to apply + * + * @return a0 op (... op (an-1 op an)...) + * if the iterator yields elements a0, a1, ..., + * an. + + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + def reduceRight[B >: A](op: (A, B) => B): B = { + if (!hasNext) throw new UnsupportedOperationException("empty.reduceRight") + foldRight[B](next())(op) + } + + /** Returns a buffered iterator from this iterator. + */ + def buffered = new BufferedIterator[A] { + private var hd: A = _ + private var hdDefined: Boolean = false + + def head: A = { + if (!hdDefined) { + hd = next() + hdDefined = true + } + hd + } + + def hasNext = + hdDefined || self.hasNext + + def next = + if (hdDefined) { + hdDefined = false + hd + } else self.next + } + + /** Returns a counted iterator from this iterator. + * @deprecated use @see zipWithIndex in Iterator + */ + @deprecated def counted = new CountedIterator[A] { + private var cnt = -1 + def count = cnt + def hasNext: Boolean = self.hasNext + def next(): A = { cnt += 1; self.next } + } + + /** Creates two new iterators that both iterate over the same elements + * than this iterator (in the same order). + * + * @return a pair of iterators + */ + def duplicate: (Iterator[A], Iterator[A]) = { + var xs: List[A] = Nil + var ahead: Iterator[A] = null + class Partner extends Iterator[A] { + var ys: List[A] = Nil + def hasNext: Boolean = self.synchronized ( + ((this == ahead) && self.hasNext) || + ((this != ahead) && (!xs.isEmpty || !ys.isEmpty || self.hasNext)) + ) + def next(): A = self.synchronized { + if (this == ahead) { + val e = self.next() + xs = e :: xs; e + } else { + if (ys.isEmpty) { + ys = xs.reverse + xs = Nil + } + ys match { + case Nil => + val e = self.next() + ahead = this + xs = e :: xs; e + case z :: zs => + ys = zs; z + } + } + } + } + ahead = new Partner + (ahead, new Partner) + } + + def patch[B >: A](from: Int, ps: Seq[B], replaced: Int) = new Iterator[B] { + private val plen = ps.length + private var origElems = self + private val patchElems = ps.elements + private var i = 0 + def hasNext: Boolean = + if (i < from) origElems.hasNext + else patchElems.hasNext || origElems.hasNext + def next(): B = { + val result: B = + if (i < from || i >= from + plen) origElems.next() + else patchElems.next() + i += 1 + if (i == from) origElems = origElems drop replaced + result + } + } + + /** Fills the given array xs with at most `len` elements of + * this iterator starting at position `start`. + * Copying will stop once either the end of the current iterable is reached or + * `len` elements have been copied. + * + * @param xs the array to fill. + * @param start starting index. + * @param len number of elements to copy + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int, len: Int): Unit = { + var i = start + val end = start + len + while (hasNext && i < end) { + xs(i) = next() + i += 1 + } + } + + /** Fills the given array xs with the elements of + * this iterator starting at position start + * until either the end of the current iterator or the end of array `xs` is reached. + * + * @param xs the array to fill. + * @param start starting index. + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int): Unit = + copyToArray(xs, start, xs.length - start) + + /** Fills the given array xs with the elements of + * this iterator starting at position 0 + * until either the end of the current iterator or the end of array `xs` is reached. + * + * @param xs the array to fill. + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B]): Unit = copyToArray(xs, 0, xs.length) + + /** Fills the given array xs with the elements of + * this sequence starting at position start. Like copyToArray, + * but designed to accomodate IO stream operations. + * + * @param xs the array to fill. + * @param start the starting index. + * @param sz the maximum number of elements to be read. + * @pre the array must be large enough to hold sz elements. + * @deprecated use copyToArray instead + */ + @deprecated def readInto[B >: A](xs: Array[B], start: Int, sz: Int) { + var i = start + while (hasNext && i - start < sz) { + xs(i) = next + i += 1 + } + } + @deprecated def readInto[B >: A](xs: Array[B], start: Int) { + readInto(xs, start, xs.length - start) + } + @deprecated def readInto[B >: A](xs: Array[B]) { + readInto(xs, 0, xs.length) + } + + /** Copy all elements to a buffer + * @param The buffer to which elements are copied + */ + def copyToBuffer[B >: A](dest: Buffer[B]) { + while (hasNext) dest += next + } + + /** Transform this iterator into a list of all elements. + * + * @return a list which enumerates all elements of this iterator. + */ + def toList: List[A] = { + val res = new ListBuffer[A] + while (hasNext) res += next + res.toList + } + + /** + * Create a stream which contains all the elements of this iterator. + */ + def toStream: Stream[A] = + if (hasNext) Stream.cons(next, toStream) else Stream.empty + + /** + * Create a sequence which contains all the elements of this iterator. + */ + def toSeq: Seq[A] = { + val buffer = new ArrayBuffer[A] + this copyToBuffer buffer + buffer.readOnly + } + + /** Collect elements into a seq. + * + * @return a sequence which enumerates all elements of this iterator. + * @deprecated use toSeq instead + */ + @deprecated def collect: Seq[A] = { + val buffer = new ArrayBuffer[A] + this copyToBuffer buffer + buffer.readOnly + } + + /** Returns a string representation of the elements in this iterator. The resulting string + * begins with the string start and is finished by the string + * end. Inside, the string representations of elements (w.r.t. + * the method toString()) are separated by the string + * sep. + *

+ * Ex:
+ * List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)" + * + * @param start starting string. + * @param sep separator string. + * @param end ending string. + * @return a string representation of this iterable object. + */ + def mkString(start: String, sep: String, end: String): String = { + val buf = new StringBuilder + addString(buf, start, sep, end).toString + } + + /** Returns a string representation of this iterable object. The string + * representations of elements (w.r.t. the method toString()) + * are separated by the string sep. + * + * @param sep separator string. + * @return a string representation of this iterable object. + */ + def mkString(sep: String): String = this.mkString("", sep, "") + + /** Returns a string representation of this iterable object. The string + * representations of elements (w.r.t. the method toString()) + * are separated by a comma. + * + * @return a string representation of this iterable object. + */ + def mkString: String = + mkString("") + + /** Write all elements of this iterator into given string builder. + * The written text begins with the string start and is finished by the string + * end. Inside, the string representations of elements (w.r.t. + * the method toString()) are separated by the string + * sep. + */ + def addString(buf: StringBuilder, start: String, sep: String, end: String): StringBuilder = { + buf.append(start) + val elems = this + if (elems.hasNext) buf.append(elems.next) + while (elems.hasNext) { + buf.append(sep); buf.append(elems.next) + } + buf.append(end) + } + + /** Write all elements of this iterator into given string builder. + * The string representations of elements (w.r.t. the method toString()) + * are separated by the string sep. + */ + def addString(buf: StringBuilder, sep: String): StringBuilder = + addString(buf, "", sep, "") + + /** Write all elements of this string into given string builder without using + * any separator between consecutive elements. + */ + def addString(buf: StringBuilder): StringBuilder = + addString(buf, "", "", "") + + override def toString = (if (hasNext) "non-empty" else "empty")+" iterator" + +} diff --git a/src/library/scalax/collection/SeqFactory.scala b/src/library/scalax/collection/SeqFactory.scala new file mode 100755 index 0000000000..c5c3ed3afb --- /dev/null +++ b/src/library/scalax/collection/SeqFactory.scala @@ -0,0 +1,111 @@ +package scalax.collection + +abstract class SeqFactory[CC[+A] <: Iterable[A]] { + + /** The empty collection of type CC */ + val empty: CC[Nothing] + + private def newBuilder[A]: Builder[CC, A] = + empty.newBuilder[A].asInstanceOf[Builder[CC, A]] + + /** Create CC collection of specified elements */ + def apply[A](args: A*): CC[A] = + (empty ++ args.asInstanceOf[Iterable[A]]).asInstanceOf[CC[A]] // !!! + + /** Concatenate all the argument lists into a single list. + * + * @param xss the lists that are to be concatenated + * @return the concatenation of all the lists + */ + def concat[A](xss: CC[A]*): CC[A] = + Iterable.iterableIterableWrapper[CC, A](xss.asInstanceOf[CC[CC[A]]]).flatten // !!! + + /** An iterable that contains the same element a number of times + * @param n The number of elements returned + * @param elem The element returned each time + */ + def fill[A](n: Int)(elem: => A): CC[A] = { + val b = newBuilder[A] + var i = 0 + while (i < n) { + b += elem + i += 1 + } + b.result + } + + def fill[A](n1: Int, n2: Int)(elem: A): CC[CC[A]] = + tabulate(n1)(_ => fill(n2)(elem)) + + def fill[A](n1: Int, n2: Int, n3: Int)(elem: A): CC[CC[CC[A]]] = + tabulate(n1)(_ => fill(n2, n3)(elem)) + + def tabulate[A](n: Int)(f: Int => A): CC[A] = { + val b = newBuilder[A] + var i = 0 + while (i < n) { + b += f(i) + i += 1 + } + b.result + } + + def tabulate[A](n1: Int, n2: Int)(f: (Int, Int) => A): CC[CC[A]] = + tabulate(n1)(i1 => tabulate(n2)(i2 => f(i1, i2))) + + def tabulate[A](n1: Int, n2: Int, n3: Int)(f: (Int, Int, Int) => A): CC[CC[CC[A]]] = + tabulate(n1)(i1 => tabulate(n2)(i2 => tabulate(n3)(i3 => f(i1, i2, i3)))) +// todo: go up to 5(?) + + /** Create a sequence of increasing integers in a range. + * + * @param from the start value of the sequence + * @param end the end value of the sequence + * @return the sorted list of all from `from` (inclusive) + * up to, but exclusding, `end`. + */ + def range[A](start: Int, end: Int): CC[Int] = range(start, end, 1) + + /** Create a sequence of increasing integers in a range. + * + * @param from the start value of the sequence + * @param end the end value of the sequence + * @param step the increment value of successive elements + * @return a list of values from + n * step for + * increasing n. If `step > 0` the sequence terminates + * with the largest value less than `end`. If `step < 0` + * the sequence terminates with the smallest value greater than `end`. + * If `step == 0`, the sequence gors on infinitely (in that + * case the `range` operation might not terminate. + */ + def range(start: Int, end: Int, step: Int): CC[Int] = { + val b = newBuilder[Int] + var i = start + while ((step <= 0 || i < end) && (step >= 0 || i > end)) { + b += i + i += step + } + b.result + } + + /** Create a sequence by repeatedly applying a given function to a start value. + * + * @param start the start value of the sequence + * @param len the length of the sequence + * @param f the function that's repeatedly applied + * @return the sequence with elements (start, f(start), f(f(start)), ..., flen-1(start)) + */ + def iterate(start: Int, len: Int)(f: Int => Int): CC[Int] = { + val b = newBuilder[Int] + var acc = start + var i = 0 + while (i < len) { + b += acc + acc = f(acc) + i += 1 + } + b.result + } + + +} diff --git a/src/library/scalax/util/control/Break.scala b/src/library/scalax/util/control/Break.scala new file mode 100755 index 0000000000..4d43490a87 --- /dev/null +++ b/src/library/scalax/util/control/Break.scala @@ -0,0 +1,15 @@ +package scala.util.control + +object Break { + private class BreakException extends RuntimeException + private val breakException = new BreakException + def break { throw breakException } + def breakable(op: => Unit) { + try { + op + } catch { + case ex: BreakException => + } + } +} + -- cgit v1.2.3