diff options
author | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2012-08-22 09:00:16 -0700 |
---|---|---|
committer | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2012-08-22 09:00:16 -0700 |
commit | 6e344bc3d323a42589f8bd6f74af623a87b573db (patch) | |
tree | afbb758425ff83f2c8c91754c5c0dd4a22417535 /src | |
parent | 376427590178989e1eefd2bf12123399169c3235 (diff) | |
parent | 8d770a78731fa72ae227fc020195910aee34304a (diff) | |
download | scala-6e344bc3d323a42589f8bd6f74af623a87b573db.tar.gz scala-6e344bc3d323a42589f8bd6f74af623a87b573db.tar.bz2 scala-6e344bc3d323a42589f8bd6f74af623a87b573db.zip |
Merge pull request #1167 from Blaisorblade/topic/stream-const-space
Make Stream.withFilter.{map,flatMap} run in constant stack space
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 42 |
1 files changed, 30 insertions, 12 deletions
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 1bf1e20694..97707d4f7c 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -479,22 +479,40 @@ 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 = 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 - ) + 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() + } + + 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 = 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 - ) + 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() + } + + if (isStreamBuilder(bf)) asThat(tailFlatMap(Stream.this)) else super.flatMap(f)(bf) } |