package scala.collection
package immutable
import generic._
import mutable.{Builder, StringBuilder, LazyBuilder, ListBuffer}
import scala.annotation.tailrec
import Stream.cons
abstract class Stream[+A] extends LinearSeq[A]
with GenericTraversableTemplate[A, Stream]
with LinearSeqOptimized[A, Stream[A]] {
self =>
override def companion: GenericCompanion[Stream] = Stream
import scala.collection.{Traversable, Iterable, Seq, IndexedSeq}
def isEmpty: Boolean
def head: A
def tail: Stream[A]
protected def tailDefined: Boolean
def append[B >: A](rest: => TraversableOnce[B]): Stream[B] =
if (isEmpty) rest.toStream else cons(head, tail append rest)
def force: Stream[A] = {
var these = this
while (!these.isEmpty) these = these.tail
this
}
def print() { print(", ") }
def print(sep: String) {
def loop(these: Stream[A], start: String) {
Console.print(start)
if (these.isEmpty) Console.print("empty")
else {
Console.print(these.head)
loop(these.tail, sep)
}
}
loop(this, "")
}
override def length: Int = {
var len = 0
var left = this
while (!left.isEmpty) {
len += 1
left = left.tail
}
len
}
@inline private def asThat[That](x: AnyRef): That = x.asInstanceOf[That]
@inline private def asStream[B](x: AnyRef): Stream[B] = x.asInstanceOf[Stream[B]]
@inline private def isStreamBuilder[B, That](bf: CanBuildFrom[Stream[A], B, That]) =
bf(repr).isInstanceOf[Stream.StreamBuilder[_]]
override def toStream: Stream[A] = this
override def hasDefiniteSize = {
def loop(s: Stream[A]): Boolean = s.isEmpty || s.tailDefined && loop(s.tail)
loop(this)
}
override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That =
if (isStreamBuilder(bf)) asThat(
if (isEmpty) that.toStream
else cons(head, asStream[A](tail ++ that))
)
else super.++(that)(bf)
override def +:[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That =
if (isStreamBuilder(bf)) asThat(cons(elem, this))
else super.+:(elem)(bf)
override final def scanLeft[B, That](z: B)(op: (B, A) => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That =
if (isStreamBuilder(bf)) asThat(
if (isEmpty) Stream(z)
else cons(z, asStream[B](tail.scanLeft(op(z, head))(op)))
)
else super.scanLeft(z)(op)(bf)
override final def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = {
if (isStreamBuilder(bf)) asThat(
if (isEmpty) Stream.Empty
else cons(f(head), asStream[B](tail map f))
)
else super.map(f)(bf)
}
override final def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = {
if (!isStreamBuilder(bf)) super.collect(pf)(bf)
else {
var rest: Stream[A] = this
while (rest.nonEmpty && !pf.isDefinedAt(rest.head)) rest = rest.tail
if (rest.isEmpty) Stream.Empty.asInstanceOf[That]
else Stream.collectedTail(rest, pf, bf).asInstanceOf[That]
}
}
override final def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That =
if (isStreamBuilder(bf)) asThat(
if (isEmpty) Stream.Empty
else {
var nonEmptyPrefix = this
var prefix = f(nonEmptyPrefix.head).toStream
while (!nonEmptyPrefix.isEmpty && prefix.isEmpty) {
nonEmptyPrefix = nonEmptyPrefix.tail
if(!nonEmptyPrefix.isEmpty)
prefix = f(nonEmptyPrefix.head).toStream
}
if (nonEmptyPrefix.isEmpty) Stream.empty
else prefix append asStream[B](nonEmptyPrefix.tail flatMap f)
}
)
else super.flatMap(f)(bf)
override def filter(p: A => Boolean): Stream[A] = {
var rest = this
while (!rest.isEmpty && !p(rest.head)) rest = rest.tail
if (rest.nonEmpty) Stream.filteredTail(rest, p)
else Stream.Empty
}
override final def withFilter(p: A => Boolean): StreamWithFilter = new StreamWithFilter(p)
final class StreamWithFilter(p: A => Boolean) extends WithFilter(p) {
override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = {
def tailMap = asStream[B](tail withFilter p map f)
if (isStreamBuilder(bf)) asThat(
if (isEmpty) Stream.Empty
else if (p(head)) cons(f(head), tailMap)
else tailMap
)
else super.map(f)(bf)
}
override def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = {
def tailFlatMap = asStream[B](tail withFilter p flatMap f)
if (isStreamBuilder(bf)) asThat(
if (isEmpty) Stream.Empty
else if (p(head)) f(head).toStream append tailFlatMap
else tailFlatMap
)
else super.flatMap(f)(bf)
}
override def foreach[B](f: A => B) =
for (x <- self)
if (p(x)) f(x)
override def withFilter(q: A => Boolean): StreamWithFilter =
new StreamWithFilter(x => p(x) && q(x))
}
override def iterator: Iterator[A] = new StreamIterator(self)
@tailrec
override final def foreach[B](f: A => B) {
if (!this.isEmpty) {
f(head)
tail.foreach(f)
}
}
@tailrec
override final def foldLeft[B](z: B)(op: (B, A) => B): B = {
if (this.isEmpty) z
else tail.foldLeft(op(z, head))(op)
}
override final def reduceLeft[B >: A](f: (B, A) => B): B = {
if (this.isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
else {
var reducedRes: B = this.head
var left = this.tail
while (!left.isEmpty) {
reducedRes = f(reducedRes, left.head)
left = left.tail
}
reducedRes
}
}
override def partition(p: A => Boolean): (Stream[A], Stream[A]) = (filter(p(_)), filterNot(p(_)))
override final def zip[A1 >: A, B, That](that: collection.GenIterable[B])(implicit bf: CanBuildFrom[Stream[A], (A1, B), That]): That =
if (isStreamBuilder(bf)) asThat(
if (this.isEmpty || that.isEmpty) Stream.Empty
else cons((this.head, that.head), asStream[(A1, B)](this.tail zip that.tail))
)
else super.zip(that)(bf)
override def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Stream[A], (A1, Int), That]): That =
this.zip[A1, Int, That](Stream.from(0))
override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
def loop(pre: String, these: Stream[A]) {
if (these.isEmpty) b append end
else {
b append pre append these.head
if (these.tailDefined) loop(sep, these.tail)
else b append sep append "?" append end
}
}
b append start
loop("", this)
b
}
override def mkString(sep: String): String = mkString("", sep, "")
override def mkString: String = mkString("")
override def mkString(start: String, sep: String, end: String): String = {
this.force
super.mkString(start, sep, end)
}
override def toString = super.mkString(stringPrefix + "(", ", ", ")")
override def splitAt(n: Int): (Stream[A], Stream[A]) = (take(n), drop(n))
override def take(n: Int): Stream[A] =
if (n <= 0 || isEmpty) Stream.empty
else if (n == 1) cons(head, Stream.empty)
else cons(head, tail take n-1)
@tailrec final override def drop(n: Int): Stream[A] =
if (n <= 0 || isEmpty) this
else tail drop n-1
override def slice(from: Int, until: Int): Stream[A] = {
val lo = from max 0
if (until <= lo || isEmpty) Stream.empty
else this drop lo take (until - lo)
}
override def init: Stream[A] =
if (isEmpty) super.init
else if (tail.isEmpty) Stream.Empty
else cons(head, tail.init)
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
}
override def takeWhile(p: A => Boolean): Stream[A] =
if (!isEmpty && p(head)) cons(head, tail takeWhile p)
else Stream.Empty
override def dropWhile(p: A => Boolean): Stream[A] = {
var these: Stream[A] = this
while (!these.isEmpty && p(these.head)) these = these.tail
these
}
override def distinct: Stream[A] =
if (isEmpty) this
else cons(head, tail.filter(head !=).distinct)
override def padTo[B >: A, That](len: Int, elem: B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = {
def loop(len: Int, these: Stream[A]): Stream[B] =
if (these.isEmpty) Stream.fill(len)(elem)
else cons(these.head, loop(len - 1, these.tail))
if (isStreamBuilder(bf)) asThat(loop(len, this))
else super.padTo(len, elem)(bf)
}
override def reverse: Stream[A] = {
var result: Stream[A] = Stream.Empty
var these = this
while (!these.isEmpty) {
val r = Stream.consWrapper(result).#::(these.head)
r.tail
result = r
these = these.tail
}
result
}
override def flatten[B](implicit asTraversable: A => TraversableOnce[B]): Stream[B] = {
def flatten1(t: Traversable[B]): Stream[B] =
if (!t.isEmpty)
cons(t.head, flatten1(t.tail))
else
tail.flatten
if (isEmpty) Stream.empty
else flatten1(asTraversable(head).toTraversable)
}
override def view = new StreamView[A, Stream[A]] {
protected lazy val underlying = self.repr
override def iterator = self.iterator
override def length = self.length
override def apply(idx: Int) = self.apply(idx)
}
override def stringPrefix = "Stream"
}
final class StreamIterator[+A](self: Stream[A]) extends Iterator[A] {
class LazyCell(st: => Stream[A]) {
lazy val v = st
}
private var these = new LazyCell(self)
def hasNext: Boolean = these.v.nonEmpty
def next: A =
if (isEmpty) Iterator.empty.next
else {
val cur = these.v
val result = cur.head
these = new LazyCell(cur.tail)
result
}
override def toStream = {
val result = these.v
these = new LazyCell(Stream.empty)
result
}
override def toList = toStream.toList
}
object Stream extends SeqFactory[Stream] {
class StreamCanBuildFrom[A] extends GenericCanBuildFrom[A]
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Stream[A]] = new StreamCanBuildFrom[A]
def newBuilder[A]: Builder[A, Stream[A]] = new StreamBuilder[A]
import scala.collection.{Iterable, Seq, IndexedSeq}
class StreamBuilder[A] extends scala.collection.mutable.LazyBuilder[A, Stream[A]] {
def result: Stream[A] = parts.toStream flatMap (_.toStream)
}
object Empty extends Stream[Nothing] {
override def isEmpty = true
override def head = throw new NoSuchElementException("head of empty stream")
override def tail = throw new UnsupportedOperationException("tail of empty stream")
def tailDefined = false
}
override def empty[A]: Stream[A] = Empty
override def apply[A](xs: A*): Stream[A] = xs.toStream
class ConsWrapper[A](tl: => Stream[A]) {
def #::(hd: A): Stream[A] = 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", "2.8.0")
lazy val lazy_:: = #::
object cons {
def apply[A](hd: A, tl: => Stream[A]) = new Cons(hd, tl)
def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = #::.unapply(xs)
}
@SerialVersionUID(-602202424901551803L)
final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] with Serializable {
override def isEmpty = false
override def head = hd
@volatile private[this] var tlVal: Stream[A] = _
def tailDefined: Boolean = tlVal ne null
override def tail: Stream[A] = {
if (!tailDefined)
synchronized {
if (!tailDefined) tlVal = tl
}
tlVal
}
}
def iterate[A](start: A)(f: A => A): Stream[A] = cons(start, iterate(f(start))(f))
override def iterate[A](start: A, len: Int)(f: A => A): Stream[A] =
iterate(start)(f) take len
def from(start: Int, step: Int): Stream[Int] =
cons(start, from(start+step, step))
def from(start: Int): Stream[Int] = from(start, 1)
def continually[A](elem: => A): Stream[A] = cons(elem, continually(elem))
override def fill[A](n: Int)(elem: => A): Stream[A] =
if (n <= 0) Empty else cons(elem, fill(n-1)(elem))
override def tabulate[A](n: Int)(f: Int => A): Stream[A] = {
def loop(i: Int): Stream[A] =
if (i >= n) Empty else cons(f(i), loop(i+1))
loop(0)
}
override def range[T: Integral](start: T, end: T, step: T): Stream[T] = {
val num = implicitly[Integral[T]]
import num._
if (if (step < zero) start <= end else end <= start) Empty
else cons(start, range(start + step, end, step))
}
private[immutable] def filteredTail[A](stream: Stream[A], p: A => Boolean) = {
cons(stream.head, stream.tail filter p)
}
private[immutable] def collectedTail[A, B, That](stream: Stream[A], pf: PartialFunction[A, B], bf: CanBuildFrom[Stream[A], B, That]) = {
cons(pf(stream.head), stream.tail.collect(pf)(bf).asInstanceOf[Stream[B]])
}
@deprecated("use it.toStream instead", "2.8.0")
def fromIterator[A](it: Iterator[A]): Stream[A] = it.toStream
@deprecated("use xs.flatten instead", "2.8.0")
def concat[A](xs: Iterable[Stream[A]]): Stream[A] = concat(xs.iterator)
@deprecated("use xs.toStream.flatten instead", "2.8.0")
def concat[A](xs: Iterator[Stream[A]]): Stream[A] = xs.toStream.flatten
@deprecated("use `iterate' instead.", "2.8.0")
def range(start: Int, end: Int, step: Int => Int): Stream[Int] =
iterate(start, end - start)(step)
@deprecated("use `continually' instead", "2.8.0")
def const[A](elem: A): Stream[A] = cons(elem, const(elem))
@deprecated("use fill(n, elem) instead", "2.8.0")
def make[A](n: Int, elem: A): Stream[A] = fill(n)(elem)
}