Cleaner sameElements implementation for linear ...

Cleaner sameElements implementation for linear seq, and fix for #2040.

2 files changed, 27 insertions, 20 deletions

diff --git a/src/library/scala/collection/generic/LinearSequenceTemplate.scala b/src/library/scala/collection/generic/LinearSequenceTemplate.scala
index 2e1f61a36f..c35bc57bac 100644
--- a/src/library/scala/collection/generic/LinearSequenceTemplate.scala
+++ b/src/library/scala/collection/generic/LinearSequenceTemplate.scala
@@ -278,18 +278,23 @@ trait LinearSequenceTemplate[+A, +This <: LinearSequenceTemplate[A, This] with L
    */
   override def sameElements[B >: A](that: Iterable[B]): Boolean = that match {
     case that1: LinearSequence[_] =>
-      var these = this
+      // !!! todo: do the LinearSequence methods need to assume null might be
+      // used to indicate termination or not? The fact that null is checked for
+      // here would seem to indicate "yes", but the comment in LinkedListTemplate is
+      //   !!! todo: integrate with LinearSequence, need to drop null then.
+      // which contradicts the need for null checking here in two different ways:
+      //   1) LinkedList does not currently inherit from LinearSequenceTemplate
+      //   2) According to that comment, if it does it will stop using null
+      //      (but what is the alternative?)
+      def isEmpty(xs: LinearSequence[_]) = xs == null || xs.isEmpty
+      var these = thisCollection
       var those = that1
-      while (these != null && those != null && !these.isEmpty && !those.isEmpty && these.head == those.head) {
+
+      while (!isEmpty(these) && !isEmpty(those) && these.head == those.head) {
         these = these.tail
         those = those.tail
       }
-      if (these == null)
-        those == null
-      else if (those == null)
-        false
-      else
-        these.isEmpty && those.isEmpty
+      isEmpty(these) && isEmpty(those)
     case _ => super.sameElements(that)
   }
 
diff --git a/src/library/scala/collection/generic/LinkedListTemplate.scala b/src/library/scala/collection/generic/LinkedListTemplate.scala
index a368f36b64..ff96da826e 100644
--- a/src/library/scala/collection/generic/LinkedListTemplate.scala
+++ b/src/library/scala/collection/generic/LinkedListTemplate.scala
@@ -11,6 +11,7 @@
 
 package scala.collection.generic
 import scala.collection._
+import annotation.tailrec
 
 /** This extensible class may be used as a basis for implementing linked
  *  list. Type variable <code>A</code> refers to the element type of the
@@ -30,12 +31,17 @@ trait LinkedListTemplate[A, This >: Null <: Sequence[A] with LinkedListTemplate[
 
   override def length: Int = 1 + (if (next eq null) 0 else next.length)
 
-  override def head: A = elem
-
+  override def head: A    = elem
   override def tail: This = next
 
-  def append(that: This): Unit =
-    if (next eq null) next = that else next.append(that)
+  def append(that: This): Unit = {
+    @tailrec
+    def loop(x: This): Unit = {
+      if (x.next eq null) x.next = that
+      else loop(x.next)
+    }
+    loop(thisCollection)
+  }
 
   def insert(that: This): Unit = if (that ne null) {
     that.append(next)
@@ -51,18 +57,14 @@ trait LinkedListTemplate[A, This >: Null <: Sequence[A] with LinkedListTemplate[
     }
     these
   }
-
-  override def apply(n: Int): A = {
+  private def atLocation[T](n: Int)(f: This => T) = {
     val loc = drop(n)
-    if (loc ne null) loc.elem
+    if (loc ne null) f(loc)
     else throw new IndexOutOfBoundsException(n.toString)
   }
 
-  def update(n: Int, x: A) {
-    val loc = drop(n)
-    if (loc ne null) loc.elem = x
-    else throw new IndexOutOfBoundsException(n.toString)
-  }
+  override def apply(n: Int): A   = atLocation(n)(_.elem)
+  def update(n: Int, x: A): Unit  = atLocation(n)(_.elem = x)
 
   def get(n: Int): Option[A] = {
     val loc = drop(n)