Bring back List filter/filterNot optimization to 2.13

ackratos · retronym · commit dc1da28d9eed · 2018-03-12T15:32:13.000+10:00
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
@@ -391,6 +391,88 @@ sealed abstract class List[+A] extends AbstractSeq[A]
     }
   }
 
+  override def filter(p: A => Boolean): List[A] = filterImpl(p, isFlipped = false)
+
+  override def filterNot(p: A => Boolean): List[A] = filterImpl(p, isFlipped = true)
+
+  private[this] def filterImpl(p: A => Boolean, isFlipped: Boolean): List[A] = {
+
+    // everything seen so far so far is not included
+    @tailrec def noneIn(l: List[A]): List[A] = {
+      if (l.isEmpty)
+        Nil
+      else {
+        val h = l.head
+        val t = l.tail
+        if (p(h) != isFlipped)
+          allIn(l, t)
+        else
+          noneIn(t)
+      }
+    }
+
+    // everything from 'start' is included, if everything from this point is in we can return the origin
+    // start otherwise if we discover an element that is out we must create a new partial list.
+    @tailrec def allIn(start: List[A], remaining: List[A]): List[A] = {
+      if (remaining.isEmpty)
+        start
+      else {
+        val x = remaining.head
+        if (p(x) != isFlipped)
+          allIn(start, remaining.tail)
+        else
+          partialFill(start, remaining)
+      }
+    }
+
+    // we have seen elements that should be included then one that should be excluded, start building
+    def partialFill(origStart: List[A], firstMiss: List[A]): List[A] = {
+      val newHead = new ::(origStart.head, Nil)
+      var toProcess = origStart.tail
+      var currentLast = newHead
+
+      // we know that all elements are :: until at least firstMiss.tail
+      while (!(toProcess eq firstMiss)) {
+        val newElem = new ::(toProcess.head, Nil)
+        currentLast.tl = newElem
+        currentLast = newElem
+        toProcess = toProcess.tail
+      }
+
+      // at this point newHead points to a list which is a duplicate of all the 'in' elements up to the first miss.
+      // currentLast is the last element in that list.
+
+      // now we are going to try and share as much of the tail as we can, only moving elements across when we have to.
+      var next = firstMiss.tail
+      var nextToCopy = next // the next element we would need to copy to our list if we cant share.
+      while (!next.isEmpty) {
+        // generally recommended is next.isNonEmpty but this incurs an extra method call.
+        val head: A = next.head
+        if (p(head) != isFlipped) {
+          next = next.tail
+        } else {
+          // its not a match - do we have outstanding elements?
+          while (!(nextToCopy eq next)) {
+            val newElem = new ::(nextToCopy.head, Nil)
+            currentLast.tl = newElem
+            currentLast = newElem
+            nextToCopy = nextToCopy.tail
+          }
+          nextToCopy = next.tail
+          next = next.tail
+        }
+      }
+
+      // we have remaining elements - they are unchanged attach them to the end
+      if (!nextToCopy.isEmpty)
+        currentLast.tl = nextToCopy
+
+      newHead
+    }
+
+    noneIn(repr)
+  }
+
   override def reverse: List[A] = {
     var result: List[A] = Nil
     var these = this
