Stream provides helper functions
* to manipulate streams.
*
* @author Martin Odersky, Matthias Zenger
* @version 1.1 08/08/03
*/
object Stream extends SequenceFactory[Stream] {
import collection.{Iterable, OrderedIterable, Sequence, Vector}
override val empty: Stream[Nothing] = Nil
override def apply[A](xs: A*) = xs.asInstanceOf[Iterable[A]].toList // !@!
override def newBuilder[B]: Builder[Stream, B] = new ListBuffer[B]
class ConsWrapper[A](tl: => Stream[A]) {
def #::(hd: A): Stream[A] = new Cons(hd, tl)
def #:::(prefix: Stream[A]): Stream[A] = prefix append tl
}
implicit def consWrapper[A](stream: => Stream[A]): ConsWrapper[A] =
new ConsWrapper[A](stream)
object #:: {
def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] =
if (xs.isEmpty) None
else Some(xs.head, xs.tail)
}
/** @deprecated use #:: instead */
@deprecated lazy val lazy_:: = #::
/** An alternative way of building and matching Streams using Stream.cons(hd, tl).
*/
object cons {
/** A stream consisting of a given first element and remaining elements
* @param hd The first element of the result stream
* @param tl The remaining elements of the result stream
*/
def apply[A](hd: A, tl: => Stream[A]) = new Cons(hd, tl)
/** Maps a stream to its head and tail */
def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = #::.unapply(xs)
}
final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] {
override def isEmpty = false
override def head = hd
private[this] var tlVal: Stream[A] = _
private def tlDefined = tlVal ne null
override def tail: Stream[A] = {
if (!tlDefined) { tlVal = tl }
tlVal
}
override def hasDefiniteSize = tlDefined && tlVal.hasDefiniteSize
// Overridden methods from IterableTemplate or overloaded variants of such methods
/** Create a new stream which contains all elements of this stream
* followed by all elements of Iterable `that'
*/
override def ++[B >: A](that: Iterable[B]): Stream[B] = this append that
/** Create a new stream which contains all elements of this stream
* followed by all elements of Iterator `that'
*/
override def ++[B >: A](that: Iterator[B]): Stream[B] = this append that.toStream
/** Returns the stream resulting from applying the given function
* f to each element of this stream.
*
* @param f function to apply to each element.
* @return f(a0), ..., f(an) if this
* sequence is a0, ..., an.
*/
override def map[B](f: A => B): Stream[B] =
new Cons(f(head), tail map f)
/** Applies the given function f to each element of
* this stream, then concatenates the results.
*
* @param f the function to apply on each element.
* @return f(a0) ::: ... ::: f(an) if
* this stream is [a0, ..., an].
*/
override def flatMap[B](f: A => Iterable[B]): Stream[B] = {
// drops A's for which f yields an empty Iterable[B]
def loop(s: Stream[A]): Stream[B] =
if (s.isEmpty) Nil
else {
val i = f(s.head)
if (i.isEmpty) loop(s.tail)
else i.toStream append loop(s.tail)
}
loop(this)
}
/** Returns all the elements of this stream that satisfy the
* predicate p. The order of the elements is preserved.
*
* @param p the predicate used to filter the stream.
* @return the elements of this stream satisfying p.
*/
override def filter(p: A => Boolean): Stream[A] = {
// drops A's for which p yields false
def loop(s: Stream[A]): Stream[A] =
if (s.isEmpty) Nil
else {
val b = p(s.head)
if (!b) loop(s.tail)
else new Cons(s.head, tail filter p)
}
loop(this)
}
/** Returns all the elements of this stream that satisfy the
* predicate p. The order of the elements is preserved.
*
* @param p the predicate used to filter the stream.
* @return the elements of this stream satisfying p.
*/
override def partition(p: A => Boolean): (Stream[A], Stream[A]) = (filter(p(_)), remove(p(_)))
/** Returns a stream formed from this stream and the specified stream
* that by associating each element of the former with
* the element at the same position in the latter.
* If one of the two streams is longer than the other, its remaining elements are ignored.
*
* @return Stream({a0,b0}, ...,
* {amin(m,n),bmin(m,n))} when
* Stream(a0, ..., am)
* zip Stream(b0, ..., bn) is invoked.
*/
def zip[B](that: Stream[B]): Stream[(A, B)] =
if (that.isEmpty) empty
else new Cons((this.head, that.head), this.tail zip that.tail)
/** Returns a list formed from this list and the specified list
* that by associating each element of the former with
* the element at the same position in the latter.
*
* @param that list that may have a different length
* as the self list.
* @param thisElem element thisElem is used to fill up the
* resulting list if the self list is shorter than
* that
* @param thatElem element thatElem is used to fill up the
* resulting list if that is shorter than
* the self list
* @return List((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: Stream[B], thisElem: A1, thatElem: B1): Stream[(A1, B1)] = {
if (that.isEmpty) new Cons((this.head, thatElem), this.tail.zipAll(that, thisElem, thatElem))
else new Cons((this.head, that.head), this.tail.zipAll(that.tail, thisElem, thatElem))
}
/** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to
* `s zip s.indices`
*/
override def zipWithIndex = this zip (Iterator.from(0).toStream)
/** Write all defined elements of this iterable into given string builder.
* The written text begins with the string start and is finished by the string
* end. Inside, the string representations of defined elements (w.r.t.
* the method toString()) are separated by the string
* sep. The method will not force evaluation of undefined elements. A
* tail of such elements will be represented by a "?" instead.
*/
override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
b append start append hd
if (tlDefined) tlVal.addString(b, sep, sep, end)
else b append ", ?" append end
}
/** Returns the n first elements of this stream, or else the whole
* stream, if it has less than n elements.
*
* @param n the number of elements to take.
* @return the n first elements of this stream.
*/
override def take(n: Int): Stream[A] =
if (n <= 0) Nil else new Cons(head, tail take (n-1))
/** Returns the stream without its n first elements.
* If the stream has less than n elements, the empty stream is returned.
*
* @param n the number of elements to drop.
* @return the stream without its n first elements.
*/
override def drop(n: Int): Stream[A] = {
var these: Stream[A] = this
var i = n
while (!these.isEmpty && i > 0) {
these = these.tail
i -= 1
}
these
}
/** A substream starting at index `from`
* and extending up to (but not including) index `until`.
*
* @This is equivalent to (but possibly more efficient than)
* c.drop(from).take(to - from)
*
* @param from The index of the first element of the returned subsequence
* @param until The index of the element following the returned subsequence
* @throws IndexOutOfBoundsException if from < 0
* or length < from + len
* @note Might return different results for different runs, unless this iterable is ordered
*/
override def slice(from: Int, to: Int): Stream[A] =
this.drop(from).take(to - from)
/** The stream without its last element.
* @throws Predef.UnsupportedOperationException if the stream is empty.
*/
override def init: Stream[A] =
if (tail.isEmpty) Nil
else new Cons(head, tail.init)
/** Returns the rightmost n elements from this iterable.
* @param n the number of elements to take
*/
override def takeRight(n: Int): Stream[A] = {
var these: Stream[A] = this
var lead = this drop n
while (!lead.isEmpty) {
these = these.tail
lead = lead.tail
}
these
}
/** Returns the longest prefix of this stream whose elements satisfy
* the predicate p.
*
* @param p the test predicate.
*/
override def takeWhile(p: A => Boolean): Stream[A] =
if (p(head)) new Cons(head, tail takeWhile p) else Nil
/** Returns the longest suffix of this iterable whose first element
* does not satisfy the predicate p.
*
* @param p the test predicate.
*/
override def dropWhile(p: A => Boolean): Stream[A] = {
var these: Stream[A] = this
while (!these.isEmpty && p(these.head)) these = these.tail
these
}
/** Returns a pair consisting of the longest prefix of the stream whose
* elements all satisfy the given predicate, and the rest of the stream.
*
* @param p the test predicate
*/
override def span(p: A => Boolean): (List[A], Stream[A]) = {
var these: Stream[A] = this
val l = new ListBuffer[A]
while (!these.isEmpty && p(these.head)) {
l += these.head
these = these.tail
}
(l.toList, these)
}
// Overridden methods from Sequence
/** Builds a new stream from this stream in which any duplicates (wrt to ==) removed.
* Among duplicate elements, only the first one is retained in the result stream
*/
override def removeDuplicates: Stream[A] =
new Cons(head, tail.filter(head !=).removeDuplicates)
/** Returns a new sequence of given length containing the elements of this sequence followed by zero
* or more occurrences of given elements.
*/
override def padTo[B >: A](len: Int, elem: B): Stream[B] =
new Cons(head, tail.padTo(len - 1, elem))
}
/**
* Create an infinite stream starting at start
* and incrementing by step step
*
* @param start the start value of the stream
* @param step the increment value of the stream
* @return the stream starting at value start.
*/
def from(start: Int, step: Int): Stream[Int] =
new Cons(start, from(start+step, step))
/**
* Create an infinite stream starting at start
* and incrementing by 1.
*
* @param start the start value of the stream
* @return the stream starting at value start.
*/
def from(start: Int): Stream[Int] = from(start, 1)
/**
* Create an infinite stream containing the given element expression (which is computed for each
* occurrence)
* @param elem the element composing the resulting stream
* @return the stream containing an inifinite number of elem
* @deprecated use fill instead
*/
@deprecated def fill[A](elem: => A): Stream[A] = new Cons(elem, fill(elem))
/** A stream containing all elements of a given iterator, in the order they are produced.
* @param it The iterator producing the stream's elements
* @deprecated use it.toStream instead
*/
@deprecated def fromIterator[A](it: Iterator[A]): Stream[A] =
if (it.hasNext) cons(it.next, fromIterator(it)) else empty
/** The concatenation of a sequence of streams
* @deprecated use xs.flatten instead
*/
@deprecated def concat[A](xs: Iterable[Stream[A]]): Stream[A] = concat(xs.elements)
/** The concatenation of all streams returned by an iterator
* @deprecated use xs.toStream.flatten instead
*/
@deprecated def concat[A](xs: Iterator[Stream[A]]): Stream[A] =
if (xs.hasNext) xs.next append concat(xs)
else empty
/**
* Create a stream with element values
* vn+1 = step(vn)
* where v0 = start
* and elements are in the range between start (inclusive)
* and end (exclusive)
* @deprecated use @see iterate instead.
* @param start the start value of the stream
* @param end the end value of the stream
* @param step the increment function of the stream, must be monotonically increasing or decreasing
* @return the stream starting at value start.
*/
@deprecated def range(start: Int, end: Int, step: Int => Int): Stream[Int] = {
val up = step(start) > start
val down = step(start) < start
def loop(lo: Int): Stream[Int] =
if ((!up || lo < end) && (!down || lo > end)) cons(lo, loop(step(lo)))
else empty
loop(start)
}
/**
* Create an infinite stream containing the given element.
*
* @param elem the element composing the resulting stream
* @return the stream containing an inifinite number of elem
* @deprecated use fill(elem) instead
*/
@deprecated def const[A](elem: A): Stream[A] = cons(elem, const(elem))
/** Create a stream containing several copies of an element.
*
* @param n the length of the resulting stream
* @param elem the element composing the resulting stream
* @return the stream composed of n elements all equal to elem
* @deprecated use fill(n, elem) instead
*/
@deprecated def make[A](n: Int, elem: A): Stream[A] =
const(elem) take n
}
import Stream._
/**
* The class Stream implements lazy lists where elements
* are only evaluated when they are needed. Here is an example:
*
* object Main extends Application {
*
* def from(n: Int): Stream[Int] =
* Stream.cons(n, from(n + 1))
*
* def sieve(s: Stream[Int]): Stream[Int] =
* Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))
*
* def primes = sieve(from(2))
*
* primes take 10 print
* }
*
*
* @author Martin Odersky, Matthias Zenger
* @version 1.1 08/08/03
*/
abstract class Stream[+A] extends Sequence[A] with SequenceTemplate[Stream, A] {
self =>
import collection.{Iterable, OrderedIterable, Sequence, Vector}
/** is this stream empty? */
def isEmpty: Boolean
/** The first element of this stream
* @throws Predef.NoSuchElementException if the stream is empty.
*/
def head: A
/** A stream consisting of the remaining elements of this stream after the first one.
* @throws Predef.UnsupportedOperationException if the stream is empty.
*/
def tail: Stream[A]
// Implementation of abstract methods
/** Create a new @see LazyBuilder to build a stream */
def newBuilder[B]: Builder[Stream, B] = new LazyBuilder[Stream, B] {
def result: Stream[B] = elements.toStream
}
/** Returns the number of elements in the list.
*/
def length: Int = {
var these = self
var len = 0
while (!these.isEmpty) {
len += 1
these = these.tail
}
len
}
/** Returns the n-th element of this stream. The first element
* (head of the stream) is at position 0.
*
* @param n index of the element to return
* @return the element at position n in this stream.
* @throws Predef.NoSuchElementException if the stream is too short.
*/
override def apply(n: Int): A = drop(n).head
// New methods in Stream
/** The stream resulting from the concatenation of this stream with the argument stream.
* @param rest The stream that gets appended to this stream
*/
def append[B >: A](rest: => Iterable[B]): Stream[B] =
if (isEmpty) rest.toStream else new Cons(head, tail append rest)
/** Force evaluation of the whole stream and return it */
def force: Stream[A] = {
var these = this
while (!isEmpty) these = these.tail
this
}
/** Prints elements of this stream one by one, separated by commas */
def print() { print(", ") }
/** Prints elements of this stream one by one, separated by sep
* @param sep The separator string printed between consecutive elements.
*/
def print(sep: String) {
def loop(these: Stream[A], start: String) {
Console.print(start)
if (isEmpty) Console.print("empty")
else {
Console.print(these.head)
loop(these.tail, sep)
}
}
loop(this, "")
}
// Overridden methods from IterableTemplate or overloaded variants of such methods
/** Returns the elements in the sequence as an iterator
*/
override def elements: Iterator[A] = new Iterator[A] {
var these = self
def hasNext: Boolean = !these.isEmpty
def next: A =
if (hasNext) {
val result = these.head; these = these.tail; result
} else Iterator.empty.next
override def toList: List[A] = these.toList
}
/** Apply the given function f to each element of this stream
* (while respecting the order of the elements).
*
* @param f the treatment to apply to each element.
*/
override def foreach(f: A => Unit) {
var these = this
while (!these.isEmpty) {
f(these.head)
these = these.tail
}
}
/** Tests if the predicate p is satisfied by all elements
* in this list.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @param p the test predicate.
* @return true iff all elements of this list satisfy the
* predicate p.
*/
override def forall(p: A => Boolean): Boolean = {
var these = this
while (!these.isEmpty) {
if (!p(these.head)) return false
these = these.tail
}
true
}
/** Tests the existence in this list of an element that satisfies the
* predicate p.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @param p the test predicate.
* @return true iff there exists an element in this list that
* satisfies the predicate p.
*/
override def exists(p: A => Boolean): Boolean = {
var these = this
while (!these.isEmpty) {
if (p(these.head)) return true
these = these.tail
}
false
}
/** Count the number of elements in the iterable which satisfy a predicate.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @param p the predicate for which to count
* @return the number of elements satisfying the predicate p.
*/
override def count(p: A => Boolean): Int = {
var these = this
var cnt = 0
while (!these.isEmpty) {
if (p(these.head)) cnt += 1
these = these.tail
}
cnt
}
/** Find and return the first element of the list satisfying a
* predicate, if any.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @param p the predicate
* @return the first element in the list satisfying p,
* or None if none exists.
*/
override def find(p: A => Boolean): Option[A] = {
var these = this
while (!these.isEmpty) {
if (p(these.head)) return Some(these.head)
these = these.tail
}
None
}
/** Combines the elements of this list together using the binary
* function f, from left to right, and starting with
* the value z.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @return f(... (f(f(z, a0), a1) ...),
* an) if the list is
* [a0, a1, ..., an].
*/
override def foldLeft[B](z: B)(f: (B, A) => B): B = {
var acc = z
var these = this
while (!these.isEmpty) {
acc = f(acc, these.head)
these = these.tail
}
acc
}
/** Combines the elements of this list together using the binary
* function f, from right to left, and starting with
* the value z.
*
* @return f(a0, f(a1, f(..., f(an, z)...)))
* if the list is [a0, a1, ..., an].
*/
override def foldRight[B](z: B)(f: (A, B) => B): B =
if (this.isEmpty) z
else f(head, tail.foldRight(z)(f))
/** Combines the elements of this list together using the binary
* operator op, from left to right
* @param op The operator to apply
* @return op(... op(a0,a1), ..., an)
if the list has elements
* a0, a1, ..., an.
* @throws Predef.UnsupportedOperationException if the list is empty.
*/
override def reduceLeft[B >: A](f: (B, A) => B): B =
if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
else tail.foldLeft[B](head)(f)
/** Combines the elements of this iterable object together using the binary
* operator 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.
*/
override def reduceRight[B >: A](op: (A, B) => B): B =
if (isEmpty) throw new UnsupportedOperationException("Nil.reduceRight")
else if (tail.isEmpty) head
else op(head, tail.reduceRight(op))
/**
* Create a stream which contains all the elements of this iterable object.
* @note consider using projection for lazy behavior.
*/
override def toStream: Stream[A] = this
/** Defines the prefix of this object's toString representation as ``Stream''.
*/
override def stringPrefix = "Stream"
/** The last element of this stream.
*
* @throws Predef.NoSuchElementException if the stream is empty.
*/
override def last: A = {
if (isEmpty) throw new NoSuchElementException
var these = this
var nx = these.tail
while (!nx.isEmpty) {
these = nx
nx = nx.tail
}
these.head
}
/** Returns the rightmost n elements from this iterable.
* @param n the number of elements to take
*/
override def dropRight(n: Int): List[A] = {
val b = new ListBuffer[A]
var these = this
var lead = this drop n
while (!lead.isEmpty) {
b += these.head
these = these.tail
lead = lead.tail
}
b.toList
}
/** Returns true iff the other stream contains the same elements as this one.
*
* @note will not terminate for two infinite-sized streams.
* @param that the other stream
*/
def sameElements[B >: A](that: Stream[B]): Boolean = {
val these = this
val those = that
while (!these.isEmpty && !those.isEmpty && these.head == those.head) {}
these.isEmpty && those.isEmpty
}
// Overridden methods from Sequence
/** Result of comparing length with operand len.
* returns x where
* x < 0 iff this.length < len
* x == 0 iff this.length == len
* x > 0 iff this.length > len.
*/
override def lengthCompare(len: Int): Int = {
var i = 0
var these = self
while (!these.isEmpty && i <= len) {
i += 1
these = these.tail
}
i - len
}
/** Is this partial function defined for the index x?
*/
override def isDefinedAt(x: Int): Boolean = x >= 0 && lengthCompare(x) >= 0
/** Returns length of longest segment starting from a start index `from`
* such that every element of the segment satisfies predicate `p`.
* @note may not terminate for infinite-sized collections.
* @param p the predicate
* @param from the start index
*/
override def segmentLength(p: A => Boolean, from: Int): Int = {
var i = from
var these = this drop from
while (!these.isEmpty && p(these.head)) {
i += 1
these = these.tail
}
i
}
/** Returns index of the first element starting from a start index
* satisying a predicate, or -1, if none exists.
*
* @note may not terminate for infinite-sized streams.
* @param p the predicate
* @param from the start index
*/
override def indexWhere(p: A => Boolean, from: Int): Int = {
var i = from
var these = this drop from
while (!these.isEmpty && !p(these.head)) {
i += 1
these = these.tail
}
if (these.isEmpty) -1 else i
}
/** Returns index of the last element satisying a predicate, or -1, if none exists.
*
* @param p the predicate
* @return the index of the last element satisfying p,
* or -1 if such an element does not exist
*/
override def lastIndexWhere(p: A => Boolean, end: Int): Int = {
var i = 0
var these = this
var last = -1
while (!these.isEmpty && i <= end) {
if (p(these.head)) last = i
}
i
}
/** A list consisting of all elements of this list in reverse order.
*/
override def reverse: List[A] = {
var result: List[A] = Nil
var these = this
while (!these.isEmpty) {
result = these.head :: result
these = these.tail
}
result
}
}