diff options
Diffstat (limited to 'src/reflect')
-rw-r--r-- | src/reflect/scala/reflect/internal/util/Collections.scala | 38 |
1 files changed, 31 insertions, 7 deletions
diff --git a/src/reflect/scala/reflect/internal/util/Collections.scala b/src/reflect/scala/reflect/internal/util/Collections.scala index f32825252c..59af819dad 100644 --- a/src/reflect/scala/reflect/internal/util/Collections.scala +++ b/src/reflect/scala/reflect/internal/util/Collections.scala @@ -53,17 +53,41 @@ trait Collections { } lb.toList } + /** like map2, but returns list `xs` itself - instead of a copy - if function * `f` maps all elements to themselves. */ - final def map2Conserve[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] = - if (xs.isEmpty || ys.isEmpty) xs - else { - val x1 = f(xs.head, ys.head) - val xs1 = map2Conserve(xs.tail, ys.tail)(f) - if ((x1 eq xs.head) && (xs1 eq xs.tail)) xs - else x1 :: xs1 + final def map2Conserve[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] = { + // Note to developers: there exists a duplication between this function and `List#mapConserve`. + // If any successful optimization attempts or other changes are made, please rehash them there too. + @tailrec + def loop(mapped: ListBuffer[A], unchanged: List[A], pending0: List[A], pending1: List[B]): List[A] = { + if (pending0.isEmpty || pending1.isEmpty) { + if (mapped eq null) unchanged + else mapped.prependToList(unchanged) + } else { + val head00 = pending0.head + val head01 = pending1.head + val head1 = f(head00, head01) + + if ((head1 eq head00.asInstanceOf[AnyRef])) { + loop(mapped, unchanged, pending0.tail, pending1.tail) + } else { + val b = if (mapped eq null) new ListBuffer[A] else mapped + var xc = unchanged + while ((xc ne pending0) && (xc ne pending1)) { + b += xc.head + xc = xc.tail + } + b += head1 + val tail0 = pending0.tail + val tail1 = pending1.tail + loop(b, tail0, tail0, tail1) + } + } } + loop(null, xs, xs, ys) + } final def map3[A, B, C, D](xs1: List[A], xs2: List[B], xs3: List[C])(f: (A, B, C) => D): List[D] = { if (xs1.isEmpty || xs2.isEmpty || xs3.isEmpty) Nil |