/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2004, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
** $Id$
\* */
package scala;
import Predef._;
/** The Iterator
object provides various functions for
* creating specialized iterators.
*
* @author Martin Odersky
* @author Matthias Zenger
* @version 1.1, 04/02/2004
*/
object Iterator {
def empty[a] = new Iterator[a] {
def hasNext: Boolean = false;
def next: a = Predef.error("next on empty iterator");
}
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 Predef.error("next on empty iterator");
}
def fromValues[a](xs: a*) = xs.elements;
def fromArray[a](xs: Array[a]) = new Iterator[a] {
private var i = 0;
def hasNext: Boolean = i < xs.length;
def next: a =
if (i < xs.length) { val x = xs(i) ; i = i + 1 ; x }
else Predef.error("next on empty iterator");
}
def fromString(str: String): Iterator[Char] = new Iterator[Char] {
private var i = 0;
private val len = str.length();
def hasNext = i < len;
def next = { val c = str charAt i; i = i + 1; c };
}
def fromCaseClass(n:CaseClass): Iterator[Any] = new Iterator[Any] {
private var c:Int = 0;
private val cmax = n.caseArity;
def hasNext = c < cmax;
def next = { val a = n caseElement c; c = c + 1; a }
}
/** Create an iterator with elements
* en+1 = en + 1
* where e0 = lo
* and ei < end
.
*
* @param lo the start value of the iterator
* @param end the end value of the iterator
* @return the iterator with values in range [lo;end).
*/
def range(lo: Int, end: Int): Iterator[Int] =
range(lo, end, 1);
/** Create an iterator with elements
* en+1 = en + step
* where e0 = lo
* and ei < end
.
*
* @param lo the start value of the iterator
* @param end the end value of the iterator
* @param step the increment value of the iterator
* @return the iterator with values in range [lo;end).
*/
def range(lo: Int, end: Int, step: Int): Iterator[Int] = new Iterator[Int] {
private var i = lo;
def hasNext: Boolean = i < end;
def next: Int =
if (i < end) { val j = i; i = i + step; j } else Predef.error("next on empty iterator");
def head: Int =
if (i < end) i else Predef.error("head on empty iterator");
}
/** Create an iterator with elements
* en+1 = step(en)
* where e0 = lo
* and ei < end
.
*
* @param lo the start value of the iterator
* @param end the end value of the iterator
* @param step the increment function of the iterator
* @return the iterator with values in range [lo;end).
*/
def range(lo: Int, end: Int, step: Int => Int): Iterator[Int] = new Iterator[Int] {
private var i = lo;
def hasNext: Boolean = i < end;
def next: Int =
if (i < end) { val j = i; i = step(i); j } else Predef.error("next on empty iterator");
def head: Int =
if (i < end) i else Predef.error("head on empty iterator");
}
/** Create an iterator with elements
* en+1 = en + 1
* where e0 = lo
.
*
* @param lo the start value of the iterator
* @return the iterator starting at value lo
.
*/
def from(lo: Int): Iterator[Int] =
from(lo, 1);
/** Create an iterator with elements
* en+1 = en + step
* where e0 = lo
.
*
* @param lo the start value of the iterator
* @param step the increment value of the iterator
* @return the iterator starting at value lo
.
*/
def from(lo: Int, step: Int) = new Iterator[Int] {
private var i = lo;
def hasNext: Boolean = true;
def next: Int = { val j = i; i = i + step; j }
}
/** Create an iterator with elements
* en+1 = step(en)
* where e0 = lo
.
*
* @param lo the start value of the iterator
* @param step the increment function of the iterator
* @return the iterator starting at value lo
.
*/
def from(lo: Int, step: Int => Int) = new Iterator[Int] {
private var i = lo;
def hasNext: Boolean = true;
def next: Int = { val j = i; i = step(i); j }
}
}
/** 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
* @author Matthias Zenger
* @version 1.2, 15/03/2004
*/
trait Iterator[+A] {
/** 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.
*/
def take(n: Int) = new Iterator[A] {
var remaining = n;
def hasNext = remaining > 0 && Iterator.this.hasNext;
def next: A =
if (hasNext) { remaining = remaining - 1; Iterator.this.next }
else Predef.error("next on empty iterator");
}
/** Removes the first n
elements from this iterator.
*/
def drop(n: Int): Iterator[A] =
if (n > 0) { next; drop(n - 1) } else this;
/** 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 = Iterator.this.hasNext;
def next = f(Iterator.this.next)
}
/** Returns a new iterator that first yields the elements of this
* iterator followed by the elements provided by iterator that
.
*/
def append[B >: A](that: Iterator[B]) = new Iterator[B] {
def hasNext = Iterator.this.hasNext || that.hasNext;
def next = if (Iterator.this.hasNext) Iterator.this.next else that.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] = Iterator.empty;
def hasNext: Boolean =
if (cur.hasNext) true
else if (Iterator.this.hasNext) {
cur = f(Iterator.this.next);
hasNext
} else false;
def next: B =
if (cur.hasNext) cur.next
else if (Iterator.this.hasNext) {
cur = f(Iterator.this.next);
next
} else Predef.error("next on empty iterator");
}
/** 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 redicate used to filter the iterator.
* @return the elements of this iterator satisfying p
.
*/
def filter(p: A => Boolean): Iterator[A] = new BufferedIterator[A] {
private val source = Iterator.this.buffered;
private def skip: Unit =
while (source.hasNext && !p(source.head)) { source.next; () }
def hasNext: Boolean = { skip; source.hasNext }
def next: A = { skip; source.next }
def head: A = { skip; source.head; }
}
/** 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.
*
* @param that
must have the same number of elements as this
* iterator.
* @return an iterator yielding (a0,b0), ..., (an,bn)
where
* ai
are the elements from this iterator and
* bi
are the elements from iterator that
.
*/
def zip[B](that: Iterator[B]) = new Iterator[Pair[A, B]] {
def hasNext = Iterator.this.hasNext && that.hasNext;
def next = Pair(Iterator.this.next, that.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): 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
* @returns 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
* @returns 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 list.
*
* @param elem element whose membership has to be tested.
* @return True iff there is an element of this list which is
* equal (w.r.t. ==
) to elem
.
*/
def contains(elem: Any): Boolean = exists { x => x == 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
}
/** Combines the elements of this list 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 list
* is List(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 list together using the binary
* operator op
, from rigth to left, and starting with
* the value z
.
* @return a0 op (... op (an op z)...)
if the list
* is [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 list and zero arguments reversed.
* That is, z /: xs
is the same as xs foldLeft z
*/
def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f);
/** An alias for foldRight
.
* That is, xs :\ z
is the same as xs foldRight z
*/
def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f);
/** Returns a buffered iterator from this iterator.
*/
def buffered: BufferedIterator[A] = new BufferedIterator[A] {
private var hd: A = _;
private var ahead: Boolean = false;
def head: A = {
if (!ahead) {
hd = Iterator.this.next;
ahead = true
}
hd
}
def next: A =
if (ahead) { ahead = false; hd } else head;
def hasNext: Boolean = ahead || Iterator.this.hasNext;
override def buffered: BufferedIterator[A] = this;
}
/** Creates two new iterators that both iterate over the same elements
* than this iterator (in the same order).
*/
def duplicate: Pair[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 = Iterator.this.synchronized {
((this == ahead) && Iterator.this.hasNext) ||
((this != ahead) && (!xs.isEmpty || !ys.isEmpty || Iterator.this.hasNext));
}
def next: A = Iterator.this.synchronized {
if (this == ahead) {
val e = Iterator.this.next;
xs = e :: xs; e
} else {
if (ys.isEmpty) {
ys = xs.reverse;
xs = Nil;
}
ys match {
case Nil => val e = Iterator.this.next;
ahead = this;
xs = e :: xs; e
case z :: zs => ys = zs; z
}
}
}
}
ahead = new Partner;
Pair(ahead, new Partner)
}
/** Fills the given array xs
with the elements of
* this sequence starting at position start
.
*
* @param xs the array to fill.
* @param start starting index.
* @return the given array xs
filled with this list.
*/
def copyToArray[B >: A](xs: Array[B], start: Int): Array[B] = {
var i = start;
while (hasNext) {
xs(i) = next;
i = i + 1;
}
xs
}
/** Transform this iterator into a list of all elements.
*
* @return a list which enumerates all elements of this iterator.
*/
def toList: List[A] = {
var res: List[A] = Nil;
while (hasNext) {
res = next :: res;
}
res.reverse
}
}