diff options
author | Martin Odersky <odersky@gmail.com> | 2008-10-20 10:06:37 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2008-10-20 10:06:37 +0000 |
commit | e5868320d48d38687d67c8c3ffc2954815b2f14f (patch) | |
tree | 0eb944e22c5f65c2c076b85876318b32cf235df9 /src/library/scalax/collection/Iterator.scala | |
parent | 9b7039e9462676d608685fb1e6242228649b21ac (diff) | |
download | scala-e5868320d48d38687d67c8c3ffc2954815b2f14f.tar.gz scala-e5868320d48d38687d67c8c3ffc2954815b2f14f.tar.bz2 scala-e5868320d48d38687d67c8c3ffc2954815b2f14f.zip |
initial collection library fragments
Diffstat (limited to 'src/library/scalax/collection/Iterator.scala')
-rwxr-xr-x | src/library/scalax/collection/Iterator.scala | 965 |
1 files changed, 965 insertions, 0 deletions
diff --git a/src/library/scalax/collection/Iterator.scala b/src/library/scalax/collection/Iterator.scala new file mode 100755 index 0000000000..dc80c10f6b --- /dev/null +++ b/src/library/scalax/collection/Iterator.scala @@ -0,0 +1,965 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterator.scala 15939 2008-08-26 14:33:17Z stepancheg $ + + +package scalax.collection + +import scala.collection.mutable.{Buffer, ListBuffer, ArrayBuffer} + +/** The <code>Iterator</code> object provides various functions for + * creating specialized iterators. + * + * @author Martin Odersky + * @author Matthias Zenger + * @version 2.8 + */ +object Iterator { + + val empty = new Iterator[Nothing] { + def hasNext: Boolean = false + def next(): Nothing = throw new NoSuchElementException("next on empty iterator") + } + + def apply[A](args: A*): Iterator[A] = args.asInstanceOf[Iterable[A]].elements // !!! + + /** Concatenate all the argument iterators into a single iterator. + * + * @param xss the lists that are to be concatenated + * @return the concatenation of all the lists + */ + def concat[A](xss: Iterator[A]*): Iterator[A] = + xss.asInstanceOf[Iterable[Iterator[A]]].elements.flatten // !!! + + /** An iterator that returns the same element a number of times + * @param len The number of elements returned + * @param elem The element returned each time + */ + def fill[A](len: Int)(elem: => A) = new Iterator[A] { + private var i = 0 + def hasNext: Boolean = i < len + def next(): A = + if (hasNext) { i += 1; elem } + else empty.next() + } + + /** An iterator that returns values of a function <code>f(0), ..., f(n-1)</code>, + * for given `f` and `n`. + */ + def tabulate[A](n: Int)(f: Int => A) = new Iterator[A] { + private var i = 0 + def hasNext: Boolean = i < n + def next(): A = + if (hasNext) { val result = f(i); i += 1; result } + else empty.next() + } + + /** Nn iterator with elements + * <code>e<sub>n+1</sub> = e<sub>n</sub> + 1</code> + * where <code>e<sub>0</sub> = start</code> + * and <code>e<sub>i</sub> < end</code>. However, + * if <code>start ≥ end</code>, then it will return an empty range. + * + * @param start the start value of the iterator + * @param end the end value of the iterator + * @return the iterator with values in range <code>[start;end)</code>. + */ + def range(start: Int, end: Int): Iterator[Int] = range(start, end, 1) + + /** Create an iterator with elements + * <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code> + * where <code>e<sub>0</sub> = start</code> + * and elements are in the range between <code>start</code> (inclusive) + * and <code>end</code> (exclusive) + * + * @param start the start value of the iterator + * @param end the end value of the iterator + * @param step the increment value of the iterator (must be positive or negative) + * @return the iterator with values in range <code>[start;end)</code>. + */ + def range(start: Int, end: Int, step: Int) = new Iterator[Int] { + private var i = start + def hasNext: Boolean = (step <= 0 || i < end) && (step >= 0 || i > end) + def next(): Int = + if (hasNext) { val result = i; i += step; result } + else empty.next() + } + + /** An iterator that repeatedly applies a given function to a start value. + * + * @param start the start value of the iteratpr + * @param len the number of elements returned by the iterator + * @param f the function that's repeatedly applied + * @return the iterator returning values <code>(start, f(start), f(f(start)), ..., f<sup>len-1</sup>(start))</code> + */ + def iterate(start: Int, len: Int)(f: Int => Int) = new Iterator[Int] { + private var acc = start + private var i = 0 + def hasNext: Boolean = i < len + def next(): Int = + if (hasNext) { val result = f(acc); i += 1; result } + else empty.next() + } + + /** An infinite iterator that repeatedly applies a given function to a start value. + * + * @param start the start value of the iteratpr + * @param f the function that's repeatedly applied + * @return the iterator returning values <code>(start, f(start), f(f(start)), ..., f<sup>len-1</sup>(start))</code> + */ + def iterate(start: Int)(f: Int => Int) = new Iterator[Int] { + private var acc = start + private var i = 0 + def hasNext: Boolean = true + def next(): Int = { val result = f(acc); i += 1; result } + } + + /** Create an iterator with elements + * <code>e<sub>n+1</sub> = e<sub>n</sub> + 1</code> + * where <code>e<sub>0</sub> = start</code>. + * + * @param start the start value of the iterator + * @return the iterator starting at value <code>start</code>. + */ + def from(start: Int): Iterator[Int] = from(start, 1) + + /** Create an iterator with elements + * <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code> + * where <code>e<sub>0</sub> = start</code>. + * + * @param start the start value of the iterator + * @param step the increment value of the iterator + * @return the iterator starting at value <code>start</code>. + */ + def from(start: Int, step: Int): Iterator[Int] = new Iterator[Int] { + private var i = 0 + def hasNext: Boolean = true + def next(): Int = { val result = i; i += 1; result } + } + + class IteratorIteratorOps[A](its: Iterator[Iterator[A]]) { + /** Create an iterator that is the concantenation of all iterators + * returned by a given iterator of iterators. + * @param its The iterator which returns on each call to next + * a new iterator whose elements are to be concatenated to the result. + */ + def flatten: Iterator[A] = new Iterator[A] { + private var it = its.next + def hasNext: Boolean = { + while (!it.hasNext && its.hasNext) it = its.next + it.hasNext + } + def next(): A = + if (hasNext) it.next + else empty.next() + } + } + + implicit def iteratorIteratorWrapper[A](its: Iterator[Iterator[A]]): IteratorIteratorOps[A] = + new IteratorIteratorOps[A](its) + + /** + * @param x the element + * @return the iterator with one single element + * @deprecated use Iterator(x) instead + */ + @deprecated def single[a](x: a) = new Iterator[a] { + private var hasnext = true + def hasNext: Boolean = hasnext + def next(): a = + if (hasnext) { hasnext = false; x } + else empty.next() + } + + /** @deprecated use `xs.elements` instead + */ + @deprecated def fromValues[a](xs: a*) = xs.elements + + /** + * @param xs the array of elements + * @see also: RandomAccessSeq.elements and slice + * @deprecated use `xs.elements` instead + */ + @deprecated def fromArray[a](xs: Array[a]): Iterator[a] = + fromArray(xs, 0, xs.length) + + /** + * @param xs the array of elements + * @param start the start index + * @param length the length + * @see also: RandomAccessSeq.elements and slice + * @deprecated use `xs.slice(start, start + length).elements` instead + */ + @deprecated def fromArray[a](xs: Array[a], start: Int, length: Int): Iterator[a] = + xs.slice(start, start + length).elements.asInstanceOf[Iterator[a]] // !!! + + /** + * @param str the given string + * @return the iterator on <code>str</code> + * @deprecated replaced by <code>str.elements</code> + */ + @deprecated def fromString(str: String): Iterator[Char] = + str.elements.asInstanceOf[Iterator[Char]] // !!! + + /** + * @param n the product arity + * @return the iterator on <code>Product<n></code>. + * @deprecated use product.productElements instead + */ + @deprecated def fromProduct(n: Product): Iterator[Any] = new Iterator[Any] { + private var c: Int = 0 + private val cmax = n.productArity + def hasNext = c < cmax + def next() = { val a = n productElement c; c += 1; a } + } + + /** Create an iterator with elements + * <code>e<sub>n+1</sub> = step(e<sub>n</sub>)</code> + * where <code>e<sub>0</sub> = start</code> + * and elements are in the range between <code>start</code> (inclusive) + * and <code>end</code> (exclusive) + * + * @param start the start value of the iterator + * @param end the end value of the iterator + * @param step the increment function of the iterator, must be monotonically increasing or decreasing + * @return the iterator with values in range <code>[start;end)</code>. + * @deprecated use Iterator.iterate(start, end - start)(step) instead + */ + @deprecated def range(start: Int, end: Int, step: Int => Int) = new Iterator[Int] { + private val up = step(start) > start + private val down = step(start) < start + private var i = start + def hasNext: Boolean = (!up || i < end) && (!down || i > end) + def next(): Int = + if (hasNext) { val j = i; i = step(i); j } + else empty.next() + } + + /** Create an iterator with elements + * <code>e<sub>n+1</sub> = step(e<sub>n</sub>)</code> + * where <code>e<sub>0</sub> = start</code>. + * + * @param start the start value of the iterator + * @param step the increment function of the iterator + * @return the iterator starting at value <code>start</code>. + * @deprecated use iterate(start)(step) instead + */ + @deprecated def from(start: Int, step: Int => Int): Iterator[Int] = new Iterator[Int] { + private var i = start + override def hasNext: Boolean = true + def next(): Int = { val j = i; i = step(i); j } + } + + /** Create an iterator that is the concantenation of all iterators + * returned by a given iterator of iterators. + * @param its The iterator which returns on each call to next + * a new iterator whose elements are to be concatenated to the result. + * @deprecated use its.flatten instead + */ + @deprecated def flatten[T](its: Iterator[Iterator[T]]): Iterator[T] = new Iterator[T] { + private var it = its.next + def hasNext: Boolean = { + while (!it.hasNext && its.hasNext) it = its.next + it.hasNext + } + def next(): T = + if (hasNext) it.next + else empty.next() + } +} + +import Iterator.empty + +/** Iterators are data structures that allow to iterate over a sequence + * of elements. They have a <code>hasNext</code> method for checking + * if there is a next element available, and a <code>next</code> method + * which returns the next element and discards it from the iterator. + * + * @author Martin Odersky, Matthias Zenger + * @version 2.8 + */ +trait Iterator[+A] { +self => + + /** Does this iterator provide another element? + */ + def hasNext: Boolean + + /** Returns the next element. + */ + def next(): A + + /** Returns a new iterator that iterates only over the first <code>n</code> + * elements. + * + * @param n the number of elements to take + * @return the new iterator + */ + def take(n: Int): Iterator[A] = new Iterator[A] { + private var remaining = n + def hasNext = remaining > 0 && self.hasNext + def next(): A = + if (hasNext) { remaining -= 1; self.next } + else throw new NoSuchElementException("next on empty iterator") + } + + /** Removes the first <code>n</code> elements from this iterator. + * + * @param n the number of elements to drop + * @return the new iterator + */ + def drop(n: Int): Iterator[A] = + if (n > 0 && hasNext) { next(); drop(n - 1) } else this + + /** A sub-iterator of <code>until - from elements + * starting at index <code>from</code> + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + */ + def slice(from: Int, until: Int): Iterator[A] = drop(from).take(until - from) + + /** Returns a new iterator that maps all elements of this iterator + * to new elements using function <code>f</code>. + */ + def map[B](f: A => B): Iterator[B] = new Iterator[B] { + def hasNext = self.hasNext + def next() = f(self.next()) + } + + /** Returns a new iterator that first yields the elements of this + * iterator followed by the elements provided by iterator <code>that</code>. + * @deprecated use <code>++</code> + */ + def append[B >: A](that: Iterator[B]) = new Iterator[B] { + def hasNext = self.hasNext || that.hasNext + def next() = (if (self.hasNext) self else that).next() + } + + /** Returns a new iterator that first yields the elements of this + * iterator followed by the elements provided by iterator <code>that</code>. + */ + def ++[B >: A](that: => Iterator[B]) = new Iterator[B] { + // optimize a little bit to prevent n log n behavior. + var cur : Iterator[B] = self + def hasNext = cur.hasNext || (cur eq self) && { cur = that; hasNext } + def next() = { hasNext; cur.next } + } + + /** Applies the given function <code>f</code> to each element of + * this iterator, then concatenates the results. + * + * @param f the function to apply on each element. + * @return an iterator over <code>f(a<sub>0</sub>), ... , + * f(a<sub>n</sub>)</code> if this iterator yields the + * elements <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. + */ + def flatMap[B](f: A => Iterator[B]): Iterator[B] = new Iterator[B] { + private var cur: Iterator[B] = empty + def hasNext: Boolean = + cur.hasNext || self.hasNext && { cur = f(self.next); hasNext } + def next(): B = (if (hasNext) cur else empty).next() + } + + /** Returns an iterator over all the elements of this iterator that + * satisfy the predicate <code>p</code>. The order of the elements + * is preserved. + * + * @param p the predicate used to filter the iterator. + * @return the elements of this iterator satisfying <code>p</code>. + */ + def filter(p: A => Boolean): Iterator[A] = { + val self = buffered + new Iterator[A] { + private def skip() = while (self.hasNext && !p(self.head)) self.next() + def hasNext = { skip(); self.hasNext } + def next() = { skip(); self.next() } + } + } + + /** Returns an iterator over the longest prefix of this iterator such that + * all elements of the result satisfy the predicate <code>p</code>. + * The order of the elements is preserved. + * + * The behavior of <code>this</code> iterator is undefined after this method invocation. + * + * @param p the predicate used to filter the iterator. + * @return the longest prefix of this iterator satisfying <code>p</code>. + */ + def takeWhile(p: A => Boolean): Iterator[A] = { + val self = buffered + new Iterator[A] { + def hasNext = { self.hasNext && p(self.head) } + def next() = (if (hasNext) self else empty).next() + } + } + + /** Partitions this iterator in two iterators according to a predicate. + * + * @param p the predicate on which to partition + * @return a pair of iterators: the iterator that satisfies the predicate + * <code>p</code> and the iterator that does not. + * The relative order of the elements in the resulting iterators + * is the same as in the original iterator. + */ + def partition(p: A => Boolean): (Iterator[A], Iterator[A]) = { + val self = buffered + class PartitionIterator(p: A => Boolean) extends Iterator[A] { + var other: PartitionIterator = _ + val lookahead = new scala.collection.mutable.Queue[A] + def skip() = + while (self.hasNext && !p(self.head)) { + other.lookahead += self.next + } + def hasNext = !lookahead.isEmpty || self.hasNext + def next() = if (lookahead.isEmpty) self.next() else lookahead.dequeue() + } + val l = new PartitionIterator(p) + val r = new PartitionIterator(!p(_)) + l.other = r + r.other = l + (l, r) + } + + /** Skips longest sequence of elements of this iterator which satisfy given + * predicate <code>p</code>, and returns an iterator of the remaining elements. + * + * The behavior of <code>this</code> iterator is undefined after this method invocation. + * + * @param p the predicate used to skip elements. + * @return an iterator consisting of the remaining elements + */ + def dropWhile(p: A => Boolean): Iterator[A] = { + val self = buffered + new Iterator[A] { + var dropped = false + private def skip() = + if (!dropped) { + while (self.hasNext && p(self.head)) self.next() + dropped = true + } + def hasNext = { skip(); self.hasNext } + def next() = { skip(); self.next() } + } + } + + /** Return an iterator formed from this iterator and the specified iterator + * <code>that</code> by associating each element of the former with + * the element at the same position in the latter. + * If one of the two iterators is longer than the other, its remaining elements are ignored. + * + * @return an iterator yielding <code>{a<sub>0</sub>,b<sub>0</sub>}, + * {a<sub>1</sub>,b<sub>1</sub>}, ...</code> where + * <code>a<sub>i</sub></code> are the elements from this iterator + * and <code>b<sub>i</sub></code> are the elements from iterator + * <code>that</code>. + */ + def zip[B](that: Iterator[B]) = new Iterator[(A, B)] { + def hasNext = self.hasNext && that.hasNext + def next = (self.next, that.next) + } + + /** Return an iterator that pairs each element of this iterator + * with its index, counting from 0. + * + * @return an iterator yielding <code>{a<sub>0</sub>,0}, + * {a<sub>1</sub>,1}...</code> where <code>a<sub>i</sub></code> + * are the elements from this iterator. + */ + def zipWithIndex = new Iterator[(A, Int)] { + var idx = 0 + def hasNext = self.hasNext + def next = { + val ret = (self.next, idx) + idx += 1 + ret + } + } + + /** Returns an iterator formed from this iterator and the specified iterator + * <code>that</code> by associating each element of the former with + * the element at the same position in the latter. + * + * @param that iterator <code>that</code> may have a different length + * as the self iterator. + * @param thisElem element <code>thisElem</code> is used to fill up the + * resulting iterator if the self iterator is shorter than + * <code>that</code> + * @param thatElem element <code>thatElem</code> is used to fill up the + * resulting iterator if <code>that</code> is shorter than + * the self iterator + * @return <code>Iterator((a<sub>0</sub>,b<sub>0</sub>), ..., + * (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>), + * ..., {elem,b<sub>m</sub>})</code> + * when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip + * [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is + * invoked where <code>m > n</code>. + */ + def zipAll[B, A1 >: A, B1 >: B](that: Iterator[B], thisElem: A1, thatElem: B1) = new Iterator[(A1, B1)] { + def hasNext = self.hasNext || that.hasNext + def next(): (A1, B1) = + if (self.hasNext) { + if (that.hasNext) (self.next(), that.next()) + else (self.next(), thatElem) + } else { + if (that.hasNext) (thisElem, that.next()) + else empty.next() + } + } + + /** Apply a function <code>f</code> to all elements of this + * iterable object. + * + * @param f a function that is applied to every element. + */ + def foreach(f: A => Unit) { while (hasNext) f(next()) } + + /** Apply a predicate <code>p</code> to all elements of this + * iterable object and return <code>true</code> iff the predicate yields + * <code>true</code> for all elements. + * + * @param p the predicate + * @return <code>true</code> iff the predicate yields <code>true</code> + * for all elements. + */ + def forall(p: A => Boolean): Boolean = { + var res = true + while (res && hasNext) res = p(next()) + res + } + + /** Apply a predicate <code>p</code> to all elements of this + * iterable object and return true, iff there is at least one + * element for which <code>p</code> yields <code>true</code>. + * + * @param p the predicate + * @return <code>true</code> iff the predicate yields <code>true</code> + * for at least one element. + */ + def exists(p: A => Boolean): Boolean = { + var res = false + while (!res && hasNext) res = p(next()) + res + } + + /** Tests if the given value <code>elem</code> is a member of this iterator. + * + * @param elem element whose membership has to be tested. + * @return <code>true</code> iff there is an element of this iterator which + * is equal (w.r.t. <code>==</code>) to <code>elem</code>. + */ + def contains(elem: Any): Boolean = exists { _ == elem } + + /** Find and return the first element of the iterable object satisfying a + * predicate, if any. + * + * @param p the predicate + * @return the first element in the iterable object satisfying + * <code>p</code>, or <code>None</code> if none exists. + */ + def find(p: A => Boolean): Option[A] = { + var res: Option[A] = None + while (res.isEmpty && hasNext) { + val e = next() + if (p(e)) res = Some(e) + } + res + } + + /** Returns index of the first element satisying a predicate, or -1. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @return the index of the first element satisfying <code>p</code>, + * or -1 if such an element does not exist + */ + def indexWhere(p: A => Boolean): Int = { + var i = 0 + var found = false + while (!found && hasNext) { + if (p(next())) { + found = true + } else { + i += 1 + } + } + if (found) i else -1 + } + + /** Returns index of the first element satisying a predicate, or -1. + * + * @deprecated use `indexWhere` instead + */ + @deprecated def findIndexOf(p: A => Boolean): Int = indexWhere(p) + + /** Returns the index of the first occurence of the specified + * object in this iterable object. + * + * @note may not terminate for infinite-sized collections. + * @param elem element to search for. + * @return the index in this sequence of the first occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + def indexOf[B >: A](elem: B): Int = { + var i = 0 + var found = false + while (!found && hasNext) { + if (next() == elem) { + found = true + } else { + i += 1 + } + } + if (found) i else -1 + } + + /** Combines the elements of this iterator together using the binary + * operator <code>op</code>, from left to right, and starting with + * the value <code>z</code>. + * + * @return <code>op(... (op(op(z,a<sub>0</sub>),a<sub>1</sub>) ...), + * a<sub>n</sub>)</code> if the iterator yields elements + * <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>. + */ + def foldLeft[B](z: B)(op: (B, A) => B): B = { + var acc = z + while (hasNext) acc = op(acc, next()) + acc + } + + /** Combines the elements of this iterator together using the binary + * operator <code>op</code>, from right to left, and starting with + * the value <code>z</code>. + * + * @return <code>a<sub>0</sub> op (... op (a<sub>n</sub> op z)...)</code> + * if the iterator yields elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., + * a<sub>n</sub></code>. + */ + def foldRight[B](z: B)(op: (A, B) => B): B = { + def fold(z: B): B = if (hasNext) op(next(), fold(z)) else z + fold(z) + } + + /** Similar to <code>foldLeft</code> but can be used as + * an operator with the order of iterator and zero arguments reversed. + * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code>. + * + * @param z the left argument of the first application of <code>op</code> + * (evaluation occurs from left to right). + * @param op the applied operator. + * @return the result value + * @see <code><a href="#foldLeft">foldLeft</a></code>. + */ + def /:[B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) + + /** An alias for <code>foldRight</code>. + * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code>. + * + * @param z the right argument of the first application of <code>op</code> + * (evaluation occurs from right to left). + * @param op the applied operator. + * @return the result value. + * @see <code><a href="#foldRight">foldRight</a></code>. + */ + def :\[B](z: B)(op: (A, B) => B): B = foldRight(z)(op) + + /** Combines the elements of this iterator together using the binary + * operator <code>op</code>, from left to right + * @param op The operator to apply + * @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code> + if the iterator yields elements + * <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>. + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + def reduceLeft[B >: A](op: (B, A) => B): B = { + if (hasNext) foldLeft[B](next())(op) + else throw new UnsupportedOperationException("empty.reduceLeft") + } + + /** Combines the elements of this iterator together using the binary + * operator <code>op</code>, from right to left + * @param op The operator to apply + * + * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> + * if the iterator yields elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., + * a<sub>n</sub></code>. + + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + def reduceRight[B >: A](op: (A, B) => B): B = { + if (!hasNext) throw new UnsupportedOperationException("empty.reduceRight") + foldRight[B](next())(op) + } + + /** Returns a buffered iterator from this iterator. + */ + def buffered = new BufferedIterator[A] { + private var hd: A = _ + private var hdDefined: Boolean = false + + def head: A = { + if (!hdDefined) { + hd = next() + hdDefined = true + } + hd + } + + def hasNext = + hdDefined || self.hasNext + + def next = + if (hdDefined) { + hdDefined = false + hd + } else self.next + } + + /** Returns a counted iterator from this iterator. + * @deprecated use @see zipWithIndex in Iterator + */ + @deprecated def counted = new CountedIterator[A] { + private var cnt = -1 + def count = cnt + def hasNext: Boolean = self.hasNext + def next(): A = { cnt += 1; self.next } + } + + /** Creates two new iterators that both iterate over the same elements + * than this iterator (in the same order). + * + * @return a pair of iterators + */ + def duplicate: (Iterator[A], Iterator[A]) = { + var xs: List[A] = Nil + var ahead: Iterator[A] = null + class Partner extends Iterator[A] { + var ys: List[A] = Nil + def hasNext: Boolean = self.synchronized ( + ((this == ahead) && self.hasNext) || + ((this != ahead) && (!xs.isEmpty || !ys.isEmpty || self.hasNext)) + ) + def next(): A = self.synchronized { + if (this == ahead) { + val e = self.next() + xs = e :: xs; e + } else { + if (ys.isEmpty) { + ys = xs.reverse + xs = Nil + } + ys match { + case Nil => + val e = self.next() + ahead = this + xs = e :: xs; e + case z :: zs => + ys = zs; z + } + } + } + } + ahead = new Partner + (ahead, new Partner) + } + + def patch[B >: A](from: Int, ps: Seq[B], replaced: Int) = new Iterator[B] { + private val plen = ps.length + private var origElems = self + private val patchElems = ps.elements + private var i = 0 + def hasNext: Boolean = + if (i < from) origElems.hasNext + else patchElems.hasNext || origElems.hasNext + def next(): B = { + val result: B = + if (i < from || i >= from + plen) origElems.next() + else patchElems.next() + i += 1 + if (i == from) origElems = origElems drop replaced + result + } + } + + /** Fills the given array <code>xs</code> with at most `len` elements of + * this iterator starting at position `start`. + * Copying will stop once either the end of the current iterable is reached or + * `len` elements have been copied. + * + * @param xs the array to fill. + * @param start starting index. + * @param len number of elements to copy + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int, len: Int): Unit = { + var i = start + val end = start + len + while (hasNext && i < end) { + xs(i) = next() + i += 1 + } + } + + /** Fills the given array <code>xs</code> with the elements of + * this iterator starting at position <code>start</code> + * until either the end of the current iterator or the end of array `xs` is reached. + * + * @param xs the array to fill. + * @param start starting index. + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int): Unit = + copyToArray(xs, start, xs.length - start) + + /** Fills the given array <code>xs</code> with the elements of + * this iterator starting at position <code>0</code> + * until either the end of the current iterator or the end of array `xs` is reached. + * + * @param xs the array to fill. + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B]): Unit = copyToArray(xs, 0, xs.length) + + /** Fills the given array <code>xs</code> with the elements of + * this sequence starting at position <code>start</code>. Like <code>copyToArray</code>, + * but designed to accomodate IO stream operations. + * + * @param xs the array to fill. + * @param start the starting index. + * @param sz the maximum number of elements to be read. + * @pre the array must be large enough to hold <code>sz</code> elements. + * @deprecated use copyToArray instead + */ + @deprecated def readInto[B >: A](xs: Array[B], start: Int, sz: Int) { + var i = start + while (hasNext && i - start < sz) { + xs(i) = next + i += 1 + } + } + @deprecated def readInto[B >: A](xs: Array[B], start: Int) { + readInto(xs, start, xs.length - start) + } + @deprecated def readInto[B >: A](xs: Array[B]) { + readInto(xs, 0, xs.length) + } + + /** Copy all elements to a buffer + * @param The buffer to which elements are copied + */ + def copyToBuffer[B >: A](dest: Buffer[B]) { + while (hasNext) dest += next + } + + /** Transform this iterator into a list of all elements. + * + * @return a list which enumerates all elements of this iterator. + */ + def toList: List[A] = { + val res = new ListBuffer[A] + while (hasNext) res += next + res.toList + } + + /** + * Create a stream which contains all the elements of this iterator. + */ + def toStream: Stream[A] = + if (hasNext) Stream.cons(next, toStream) else Stream.empty + + /** + * Create a sequence which contains all the elements of this iterator. + */ + def toSeq: Seq[A] = { + val buffer = new ArrayBuffer[A] + this copyToBuffer buffer + buffer.readOnly + } + + /** Collect elements into a seq. + * + * @return a sequence which enumerates all elements of this iterator. + * @deprecated use toSeq instead + */ + @deprecated def collect: Seq[A] = { + val buffer = new ArrayBuffer[A] + this copyToBuffer buffer + buffer.readOnly + } + + /** Returns a string representation of the elements in this iterator. The resulting string + * begins with the string <code>start</code> and is finished by the string + * <code>end</code>. Inside, the string representations of elements (w.r.t. + * the method <code>toString()</code>) are separated by the string + * <code>sep</code>. + * <p/> + * Ex: <br/> + * <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code> + * + * @param start starting string. + * @param sep separator string. + * @param end ending string. + * @return a string representation of this iterable object. + */ + def mkString(start: String, sep: String, end: String): String = { + val buf = new StringBuilder + addString(buf, start, sep, end).toString + } + + /** Returns a string representation of this iterable object. The string + * representations of elements (w.r.t. the method <code>toString()</code>) + * are separated by the string <code>sep</code>. + * + * @param sep separator string. + * @return a string representation of this iterable object. + */ + def mkString(sep: String): String = this.mkString("", sep, "") + + /** Returns a string representation of this iterable object. The string + * representations of elements (w.r.t. the method <code>toString()</code>) + * are separated by a comma. + * + * @return a string representation of this iterable object. + */ + def mkString: String = + mkString("") + + /** Write all elements of this iterator into given string builder. + * The written text begins with the string <code>start</code> and is finished by the string + * <code>end</code>. Inside, the string representations of elements (w.r.t. + * the method <code>toString()</code>) are separated by the string + * <code>sep</code>. + */ + def addString(buf: StringBuilder, start: String, sep: String, end: String): StringBuilder = { + buf.append(start) + val elems = this + if (elems.hasNext) buf.append(elems.next) + while (elems.hasNext) { + buf.append(sep); buf.append(elems.next) + } + buf.append(end) + } + + /** Write all elements of this iterator into given string builder. + * The string representations of elements (w.r.t. the method <code>toString()</code>) + * are separated by the string <code>sep</code>. + */ + def addString(buf: StringBuilder, sep: String): StringBuilder = + addString(buf, "", sep, "") + + /** Write all elements of this string into given string builder without using + * any separator between consecutive elements. + */ + def addString(buf: StringBuilder): StringBuilder = + addString(buf, "", "", "") + + override def toString = (if (hasNext) "non-empty" else "empty")+" iterator" + +} |