diff options
author | Paolo Giarrusso <p.giarrusso@gmail.com> | 2012-08-20 19:34:43 +0200 |
---|---|---|
committer | Paolo Giarrusso <p.giarrusso@gmail.com> | 2012-08-20 20:03:05 +0200 |
commit | 80b3f433e5536d086806fa108ccdfacf10719cc2 (patch) | |
tree | def234a64e0a54e61907e1e6760d21bc156b01eb /src/library | |
parent | c32b189a2a2575512d0dc8d91a400d773b53a7f0 (diff) | |
download | scala-80b3f433e5536d086806fa108ccdfacf10719cc2.tar.gz scala-80b3f433e5536d086806fa108ccdfacf10719cc2.tar.bz2 scala-80b3f433e5536d086806fa108ccdfacf10719cc2.zip |
Make Stream.withFilter.{map,flatMap} run in constant stack space
The included test currently fails because `map` and `flatMap` do not
run in constant stack space on a stream returned by `Stream.withFilter`,
as I reported here:
https://groups.google.com/d/msg/scala-language/WqJR38REXnk/saaSiDdmyqoJ
Fix the problem and add a simple testcase.
Note that the stack space consumed when producing an element of this stream is
proportional to the number of elements failing the test before the next
success. The stack space consumed to produce the stream itself is the
space needed to produce the first element, that is, is proportional to
the number of failures before the first success.
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 1bf1e20694..c8e7e7547f 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -479,22 +479,57 @@ self => 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(coll: Stream[A]): Stream[B] = { + var head: A = null.asInstanceOf[A] + var tail: Stream[A] = coll + while (true) { + if (tail.isEmpty) + return Stream.Empty + head = tail.head + tail = tail.tail + if (p(head)) + return cons(f(head), tailMap(tail)) + } + throw new RuntimeException() + } + + /* 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 + //XXX Alternative: what about having a Stream.step constructor? ) + */ + if (isStreamBuilder(bf)) asThat(tailMap(Stream.this)) else super.map(f)(bf) } override def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = { + def tailFlatMap(coll: Stream[A]): Stream[B] = { + var head: A = null.asInstanceOf[A] + var tail: Stream[A] = coll + while (true) { + if (tail.isEmpty) + return Stream.Empty + head = tail.head + tail = tail.tail + if (p(head)) + return f(head).toStream append tailFlatMap(tail) + } + throw new RuntimeException() + } + + /* 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 ) + */ + if (isStreamBuilder(bf)) asThat(tailFlatMap(Stream.this)) else super.flatMap(f)(bf) } |