Fixes #3970 and a bunch of other issues.

Review by extempore.

1 files changed, 76 insertions, 6 deletions

diff --git a/src/library/scala/collection/mutable/DoubleLinkedListLike.scala b/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
index 9112ade5af..6236afa89b 100644
--- a/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
+++ b/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
@@ -11,11 +11,40 @@
 package scala.collection
 package mutable
 
+import annotation.migration
+
 /** This extensible class may be used as a basis for implementing double
  *  linked lists. Type variable `A` refers to the element type
  *  of the list, type variable `This` is used to model self
  *  types of linked lists.
  *
+ *  The invariant of this data structure is that `prev` is always a reference to
+ *  the previous node in the list. If `this` is the first node of the list, `prev`
+ *  will be `null`.
+ *  Field `next` is set to `this` iff the list is empty.
+ *
+ *  Examples (right arrow represents `next`, left arrow represents `prev`,
+ *  `_` represents no value):
+ *
+ *  {{{
+ *
+ *     Empty:
+ *
+ *     null <-- [ _ ] --,
+ *              [   ] <-`
+ *
+ *     Single element:
+ *
+ *     null <-- [ x ] --> [ _ ] --,
+ *              [   ] <-- [   ] <-`
+ *
+ *     More elements:
+ *
+ *     null <-- [ x ] --> [ y ] --> [ z ] --> [ _ ] --,
+ *              [   ] <-- [   ] <-- [   ] <-- [   ] <-`
+ *
+ *  }}}
+ *
  *  @author  Matthias Zenger
  *  @version 1.0, 08/07/2003
  *  @since   2.8
@@ -26,11 +55,13 @@ package mutable
  *  @define Coll DoubleLinkedList
  *  @define coll double linked list
  */
-trait DoubleLinkedListLike[A, This <: Seq[A] with DoubleLinkedListLike[A, This]] extends LinkedListLike[A, This] { self =>
+trait DoubleLinkedListLike[A, This <: Seq[A] with DoubleLinkedListLike[A, This]] extends SeqLike[A, This] with LinkedListLike[A, This] { self =>
 
   /** A reference to the node in the linked list preceeding the current node. */
   var prev: This = _
 
+  // returns that list if this list is empty
+  // otherwise modifies this list
   override def append(that: This): This =
     if (isEmpty)
       that
@@ -44,15 +75,54 @@ trait DoubleLinkedListLike[A, This <: Seq[A] with DoubleLinkedListLike[A, This]]
       repr
     }
 
+  // cannot be called on empty lists
   override def insert(that: This): Unit = {
     super.insert(that)
     if (that.nonEmpty) that.prev = repr
   }
 
-  def remove() {
-    if (next.nonEmpty)
-      next.prev = prev
-    if (prev.nonEmpty)
-      prev.next = next
+  /** Removes the current node from the double linked list.
+   *  If the node was chained into a double linked list, it will no longer
+   *  be a part of it.
+   *  If the node was the last node in the list, i.e. a sentinel, this method
+   *  does nothing.
+   *
+   *  '''Note:''' this method will not set the fields `elem`, `next` or `prev` of the
+   *  current node, i.e. `this` node itself will still point "into" the list it
+   *  was in.
+   */
+  @migration(2, 9, "Double linked list now removes the current node from the list.")
+  def remove(): Unit = if (nonEmpty) {
+    next.prev = prev
+    if (prev ne null) prev.next = next // because this could be the first node
   }
+
+  private def getAtLocation(n: Int): This = if (this.isEmpty) null.asInstanceOf[This] else {
+    var loc = repr
+    var left = n
+    while (left > 0) {
+      loc = loc.next
+      left -= 1
+      if (loc.isEmpty) return null.asInstanceOf[This]
+    }
+    loc
+  }
+
+  private def atLocation[T](n: Int)(f: This => T) = {
+    val node = getAtLocation(n)
+    if (node eq null) f(node)
+    else throw new IndexOutOfBoundsException(n.toString)
+  }
+
+  override def drop(n: Int): This = super[SeqLike].drop(n)
+
+  override def apply(n: Int): A   = atLocation(n)(_.elem)
+  override def update(n: Int, x: A): Unit  = atLocation(n)(_.elem = x)
+
+  override def get(n: Int): Option[A] = {
+    val loc = getAtLocation(n)
+    if (loc ne null) Some(loc.elem)
+    else None
+  }
+
 }