diff options
| -rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 28 | ||||
| -rw-r--r-- | test/files/run/stream_flatmap_odds.check | 1 | ||||
| -rw-r--r-- | test/files/run/stream_flatmap_odds.scala | 4 | ||||
| -rw-r--r-- | test/files/run/t153.check | 1 | ||||
| -rw-r--r-- | test/files/run/t153.scala | 5 | ||||
| -rw-r--r-- | test/files/run/t498.check | 1 | ||||
| -rw-r--r-- | test/files/run/t498.scala | 5 |
7 files changed, 34 insertions, 11 deletions
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 9855ce8a41..8694dfd615 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -144,18 +144,24 @@ self => * @return <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if * this stream is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>. */ - override final def flatMap[B, That](f: A => Traversable[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = { + override final def flatMap[B, That](f: A => Traversable[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = // we assume there is no other builder factory on streams and therefore know that That = Stream[B] - // optimization: drop A's for which f yields no B - var rest = this - var seg: Traversable[B] = null - do { - if (rest.isEmpty) return Stream.Empty.asInstanceOf[That] - seg = f(rest.head) - rest = rest.tail - } while (seg.isEmpty) - (seg.toStream append (rest flatMap f).asInstanceOf[Stream[B]]).asInstanceOf[That] - } + // optimisations are not for speed, but for functionality + // see tickets #153, #498, #2147, and corresponding tests in run/ (as well as run/stream_flatmap_odds.scala) + (if (isEmpty) Stream.Empty + else { + // establish !prefix.isEmpty || nonEmptyPrefix.isEmpty + 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 (nonEmptyPrefix.tail flatMap f).asInstanceOf[Stream[B]] + }).asInstanceOf[That] /** Returns all the elements of this stream that satisfy the * predicate <code>p</code>. The order of the elements is preserved. diff --git a/test/files/run/stream_flatmap_odds.check b/test/files/run/stream_flatmap_odds.check new file mode 100644 index 0000000000..2b945e7c64 --- /dev/null +++ b/test/files/run/stream_flatmap_odds.check @@ -0,0 +1 @@ +Stream(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83) diff --git a/test/files/run/stream_flatmap_odds.scala b/test/files/run/stream_flatmap_odds.scala new file mode 100644 index 0000000000..ed1a537bd9 --- /dev/null +++ b/test/files/run/stream_flatmap_odds.scala @@ -0,0 +1,4 @@ +object Test extends Application { + lazy val odds: Stream[Int] = Stream(1) append ( odds flatMap {x => Stream(x + 2)} ) + println(odds take 42 force) +}
\ No newline at end of file diff --git a/test/files/run/t153.check b/test/files/run/t153.check new file mode 100644 index 0000000000..504fd7fc7f --- /dev/null +++ b/test/files/run/t153.check @@ -0,0 +1 @@ +Stream(524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1) diff --git a/test/files/run/t153.scala b/test/files/run/t153.scala new file mode 100644 index 0000000000..c7b3c1c762 --- /dev/null +++ b/test/files/run/t153.scala @@ -0,0 +1,5 @@ +object Test extends Application { + def powers(x: Int) = if ((x&(x-1))==0) Some(x) else None + val res = (Stream.range(1, 1000000) flatMap powers).reverse + println(res take 42 force) +}
\ No newline at end of file diff --git a/test/files/run/t498.check b/test/files/run/t498.check new file mode 100644 index 0000000000..b1ce75e80b --- /dev/null +++ b/test/files/run/t498.check @@ -0,0 +1 @@ +Stream(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) diff --git a/test/files/run/t498.scala b/test/files/run/t498.scala new file mode 100644 index 0000000000..50be317c4c --- /dev/null +++ b/test/files/run/t498.scala @@ -0,0 +1,5 @@ +object Test extends Application { +// the function passed to flatMap produces lots of empty streams, but this should not overflow the stack + val res = Stream.from(1).flatMap(i => if (i < 3000) Stream.empty else List(1)) + println(res take 42 force) +}
\ No newline at end of file |