Eliminating more allocations in the collections.

2 files changed, 18 insertions, 9 deletions

diff --git a/src/library/scala/collection/IndexedSeqOptimized.scala b/src/library/scala/collection/IndexedSeqOptimized.scala
index 09c4b14ba0..9721a42e91 100755
--- a/src/library/scala/collection/IndexedSeqOptimized.scala
+++ b/src/library/scala/collection/IndexedSeqOptimized.scala
@@ -33,11 +33,17 @@ trait IndexedSeqOptimized[+A, +Repr] extends Any with IndexedSeqLike[A, Repr] {
     while (i < len) { f(this(i)); i += 1 }
   }
 
+  private def prefixLengthImpl(p: A => Boolean, expectTrue: Boolean): Int = {
+    var i = 0
+    while (i < length && p(apply(i)) == expectTrue) i += 1
+    i
+  }
+
   override /*IterableLike*/
-  def forall(p: A => Boolean): Boolean = prefixLength(p(_)) == length
+  def forall(p: A => Boolean): Boolean = prefixLengthImpl(p, expectTrue = true) == length
 
   override /*IterableLike*/
-  def exists(p: A => Boolean): Boolean = prefixLength(!p(_)) != length
+  def exists(p: A => Boolean): Boolean = prefixLengthImpl(p, expectTrue = false) != length
 
   override /*IterableLike*/
   def find(p: A => Boolean): Option[A] = {
diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala
index c1a68b6b16..a55257d128 100644
--- a/src/library/scala/collection/TraversableLike.scala
+++ b/src/library/scala/collection/TraversableLike.scala
@@ -252,18 +252,21 @@ trait TraversableLike[+A, +Repr] extends Any
     b.result
   }
 
+  private def filterImpl(p: A => Boolean, isFlipped: Boolean): Repr = {
+    val b = newBuilder
+    for (x <- this)
+      if (p(x) != isFlipped) b += x
+
+    b.result
+  }
+
   /** Selects all elements of this $coll which satisfy a predicate.
    *
    *  @param p     the predicate used to test elements.
    *  @return      a new $coll consisting of all elements of this $coll that satisfy the given
    *               predicate `p`. The order of the elements is preserved.
    */
-  def filter(p: A => Boolean): Repr = {
-    val b = newBuilder
-    for (x <- this)
-      if (p(x)) b += x
-    b.result
-  }
+  def filter(p: A => Boolean): Repr = filterImpl(p, isFlipped = false)
 
   /** Selects all elements of this $coll which do not satisfy a predicate.
    *
@@ -271,7 +274,7 @@ trait TraversableLike[+A, +Repr] extends Any
    *  @return      a new $coll consisting of all elements of this $coll that do not satisfy the given
    *               predicate `p`. The order of the elements is preserved.
    */
-  def filterNot(p: A => Boolean): Repr = filter(!p(_))
+  def filterNot(p: A => Boolean): Repr = filterImpl(p, isFlipped = true)
 
   def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
     val b = bf(repr)