diff options
author | Paul Phillips <paulp@improving.org> | 2010-09-20 03:47:39 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2010-09-20 03:47:39 +0000 |
commit | 54b5eacb56d21664e53b92d1e5c58195538caef4 (patch) | |
tree | 533cfa9d585e835f57d50c881dfd896caf2121b1 /src | |
parent | 9563f21b20a03d3c36e3eac20b563a0c3900faac (diff) | |
download | scala-54b5eacb56d21664e53b92d1e5c58195538caef4.tar.gz scala-54b5eacb56d21664e53b92d1e5c58195538caef4.tar.bz2 scala-54b5eacb56d21664e53b92d1e5c58195538caef4.zip |
Tail recursive implementation of mapConserve, s...
Tail recursive implementation of mapConserve, submitted by Eric
Willigers. Closes #2411, review by malayeri.
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/immutable/List.scala | 39 |
1 files changed, 21 insertions, 18 deletions
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index 7785d73175..93c3134fd7 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -107,29 +107,32 @@ sealed abstract class List[+A] extends LinearSeq[A] * `f` to each element of this list and collecting the results. * @usecase def mapConserve(f: A => A): List[A] */ - def mapConserve[B >: A <: AnyRef] (f: A => B): List[B] = { - def loop(ys: List[A]): List[B] = - if (ys.isEmpty) this + def mapConserve[B >: A <: AnyRef](f: A => B): List[B] = { + @tailrec + def loop(mapped: ListBuffer[B], unchanged: List[A], pending: List[A]): List[B] = + if (pending.isEmpty) { + if (mapped eq null) unchanged + else mapped.prependToList(unchanged) + } else { - val head0 = ys.head + val head0 = pending.head val head1 = f(head0) - if (head1 eq head0.asInstanceOf[AnyRef]) { - loop(ys.tail) - } else { - val ys1 = head1 :: ys.tail.mapConserve(f) - if (this eq ys) ys1 - else { - val b = new ListBuffer[B] - var xc = this - while (xc ne ys) { - b += xc.head - xc = xc.tail - } - b.prependToList(ys1) + + if (head1 == head0) + loop(mapped, unchanged, pending.tail) + else { + val b = if (mapped eq null) new ListBuffer[B] else mapped + var xc = unchanged + while (xc ne pending) { + b += xc.head + xc = xc.tail } + b += head1 + val tail0 = pending.tail + loop(b, tail0, tail0) } } - loop(this) + loop(null, this, this) } // Overridden methods from IterableLike and SeqLike or overloaded variants of such methods |