tentative re-implementation of LinkedList and s...

tentative re-implementation of LinkedList and subclasses

5 files changed, 95 insertions, 76 deletions

diff --git a/src/library/scala/collection/mutable/DoubleLinkedListLike.scala b/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
index 65b0621b6b..6d89b67719 100644
--- a/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
+++ b/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
@@ -21,29 +21,32 @@ package mutable
  *  @version 1.0, 08/07/2003
  *  @since   2.8
  */
-trait DoubleLinkedListLike[A, This >: Null <: LinearSeq[A] with DoubleLinkedListLike[A, This]] extends LinkedListLike[A, This] { self =>
+trait DoubleLinkedListLike[A, This <: Seq[A] with DoubleLinkedListLike[A, This]] extends LinkedListLike[A, This] { self =>
 
   var prev: This = _
 
-  override def append(that: This): Unit =
-    if (next eq null) {
-      next = that
-      if (that ne null) that.prev = repr
-    } else
-      next.append(that)
-
-  override def insert(that: This): Unit = if (that ne null) {
-    that.append(next)
-    next = that
-    that.prev = repr
+  override def append(that: This): This =
+    if (isEmpty)
+      that
+    else {
+      if (next.isEmpty) {
+        next = that
+        if (that.nonEmpty) that.prev = repr
+      } else {
+        next.append(that)
+      }
+      repr
+    }
+
+  override def insert(that: This): Unit = {
+    super.insert(that)
+    if (that.nonEmpty) that.prev = repr
   }
 
   def remove() {
-    if (next ne null)
+    if (next.nonEmpty)
       next.prev = prev
-    if (prev ne null)
+    if (prev.nonEmpty)
       prev.next = next
-    prev = null
-    next = null
   }
 }
diff --git a/src/library/scala/collection/mutable/LinkedList.scala b/src/library/scala/collection/mutable/LinkedList.scala
index 74fe104a27..8e4dbcc437 100644
--- a/src/library/scala/collection/mutable/LinkedList.scala
+++ b/src/library/scala/collection/mutable/LinkedList.scala
@@ -23,15 +23,24 @@ import generic._
  *  @since   1
  */
 @serializable
-class LinkedList[A](_elem: A, _next: LinkedList[A]) extends LinearSeq[A]
-                                                       with GenericTraversableTemplate[A, LinkedList]
-                                                       with LinkedListLike[A, LinkedList[A]] {
-  elem = _elem
-  next = _next
+class LinkedList[A]() extends LinearSeq[A]
+                         with GenericTraversableTemplate[A, LinkedList]
+                         with LinkedListLike[A, LinkedList[A]] {
+  next = this
+
+  def this(elem: A, next: LinkedList[A]) {
+    this()
+    this.elem = elem
+    this.next = next
+  }
+
   override def companion: GenericCompanion[LinkedList] = LinkedList
 }
 
 object LinkedList extends SeqFactory[LinkedList] {
+
+  override def empty[A]: LinkedList[A] = new LinkedList[A]
+
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, LinkedList[A]] = new GenericCanBuildFrom[A]
   def newBuilder[A]: Builder[A, LinkedList[A]] =
     (new MutableList) mapResult ((l: MutableList[A]) => l.toLinkedList)
diff --git a/src/library/scala/collection/mutable/LinkedListLike.scala b/src/library/scala/collection/mutable/LinkedListLike.scala
index e26735ed23..42f37766b2 100644
--- a/src/library/scala/collection/mutable/LinkedListLike.scala
+++ b/src/library/scala/collection/mutable/LinkedListLike.scala
@@ -24,44 +24,60 @@ import annotation.tailrec
  *  @version 2.8
  *  @since   2.8
  */
-trait LinkedListLike[A, This >: Null <: Seq[A] with LinkedListLike[A, This]] extends SeqLike[A, This] { self =>
+trait LinkedListLike[A, This <: Seq[A] with LinkedListLike[A, This]] extends SeqLike[A, This] { self =>
 
   var elem: A = _
   var next: This = _
 
-  override def isEmpty = false
+  override def isEmpty = next eq this
 
-  override def length: Int = 1 + (if (next eq null) 0 else next.length)
+  override def length: Int = if (isEmpty) 0 else next.length
 
   override def head: A    = elem
-  override def tail: This = next
 
-  def append(that: This): Unit = {
+  override def tail: This = {
+    require(nonEmpty, "tail of empty list")
+    next
+  }
+
+  /** Append linked list `that` at current position of this linked list
+   *  @return the list after append (this is the list itself if nonempty,
+   *  or list `that` if list this is empty. )
+   */
+  def append(that: This): This = {
     @tailrec
-    def loop(x: This): Unit = {
-      if (x.next eq null) x.next = that
+    def loop(x: This) {
+      if (x.next.isEmpty) x.next = that
       else loop(x.next)
     }
-    loop(repr)
+    if (isEmpty) that
+    else { loop(repr); repr }
   }
 
-  def insert(that: This): Unit = if (that ne null) {
-    that.append(next)
-    next = that
+  /** Insert linked list `that` at current position of this linked list
+   *  @pre this linked list is not empty
+   */
+  def insert(that: This): Unit = {
+    require(nonEmpty, "insert into empty list")
+    if (that.nonEmpty) {
+      that.append(next)
+      next = that
+    }
   }
 
   override def drop(n: Int): This = {
     var i = 0
     var these: This = repr
-    while (i < n && (these ne null)) {
+    while (i < n && !these.isEmpty) {
       these = these.next.asInstanceOf[This] // !!! concrete overrides abstract problem
       i += 1
     }
     these
   }
+
   private def atLocation[T](n: Int)(f: This => T) = {
     val loc = drop(n)
-    if (loc ne null) f(loc)
+    if (!loc.isEmpty) f(loc)
     else throw new IndexOutOfBoundsException(n.toString)
   }
 
@@ -70,24 +86,24 @@ trait LinkedListLike[A, This >: Null <: Seq[A] with LinkedListLike[A, This]] ext
 
   def get(n: Int): Option[A] = {
     val loc = drop(n)
-    if (loc ne null) Some(loc.elem)
+    if (loc.nonEmpty) Some(loc.elem)
     else None
   }
 
   override def iterator: Iterator[A] = new Iterator[A] {
     var elems = self
-    def hasNext = (elems ne null)
+    def hasNext = elems.nonEmpty
     def next = {
       val res = elems.elem
       elems = elems.next
-      res;
+      res
     }
   }
 
   override def foreach[B](f: A => B) {
     var these = this
-    while (these ne null) {
-      f(these.elem);
+    while (these.nonEmpty) {
+      f(these.elem)
       these = these.next
     }
   }
diff --git a/src/library/scala/collection/mutable/MutableList.scala b/src/library/scala/collection/mutable/MutableList.scala
index 73b0ec5502..5dabb18215 100644
--- a/src/library/scala/collection/mutable/MutableList.scala
+++ b/src/library/scala/collection/mutable/MutableList.scala
@@ -34,8 +34,8 @@ class MutableList[A] extends LinearSeq[A]
 
   override protected[this] def newBuilder = new MutableList[A]
 
-  protected var first0: LinkedList[A] = null
-  protected var last0: LinkedList[A] = null
+  protected var first0: LinkedList[A] = new LinkedList[A]
+  protected var last0: LinkedList[A] = _ // undefined if first0.isEmpty
   protected var len: Int = 0
 
   /** Is the list empty?
@@ -49,11 +49,10 @@ class MutableList[A] extends LinearSeq[A]
   /** Returns the rest of this list
    */
   override def tail: MutableList[A] = {
+    require(nonEmpty, "tail of empty list")
     val tl = new MutableList[A]
-    if (first0 ne last0) {
-      tl.first0 = first0.tail
-      tl.last0 = last0
-    }
+    tl.first0 = first0.tail
+    tl.last0 = last0
     tl.len = len - 1
     tl
   }
@@ -79,17 +78,17 @@ class MutableList[A] extends LinearSeq[A]
 
   protected def prependElem(elem: A) {
     first0 = new LinkedList[A](elem, first0)
-    if (len == 0)
-      last0 = first0
+    if (len == 0) last0 = first0
     len = len + 1
   }
 
   protected def appendElem(elem: A): Unit =
-    if (len == 0)
+    if (len == 0) {
       prependElem(elem)
-    else {
-      last0.next = new LinkedList[A](elem, null)
+    } else {
+      last0.next = new LinkedList[A]
       last0 = last0.next
+      last0.elem = elem
       len = len + 1
     }
 
@@ -98,15 +97,17 @@ class MutableList[A] extends LinearSeq[A]
 
   /** Returns an iterator over all elements of this list.
    */
-  override def iterator: Iterator[A] =
-    if (first0 eq null) Iterator.empty else first0.iterator
+  override def iterator: Iterator[A] = first0.iterator
 
-  override def last = last0.elem
+  override def last = {
+    if (isEmpty) throw new NoSuchElementException("MutableList.empty.last")
+    last0.elem
+  }
 
   /** Returns an instance of <code>scala.List</code> containing the same
    *  sequence of elements.
    */
-  override def toList: List[A] = if (first0 eq null) Nil else first0.toList
+  override def toList: List[A] = first0.toList
 
   /** Returns the current list of elements as a linked List
    *  sequence of elements.
@@ -120,8 +121,8 @@ class MutableList[A] extends LinearSeq[A]
   def +=(elem: A): this.type = { appendElem(elem); this }
 
   def clear() {
-    first0 = null
-    last0 = null
+    first0 = new LinkedList[A]
+    last0 = first0
     len = 0
   }
 
diff --git a/src/library/scala/collection/mutable/Queue.scala b/src/library/scala/collection/mutable/Queue.scala
index 6316b2d5c6..b0cf9c2dd3 100644
--- a/src/library/scala/collection/mutable/Queue.scala
+++ b/src/library/scala/collection/mutable/Queue.scala
@@ -38,12 +38,11 @@ class Queue[A] extends MutableList[A] with Cloneable[Queue[A]] {
    *  @return the first element of the queue.
    */
   def dequeue(): A =
-    if (first0 eq null)
+    if (isEmpty)
       throw new NoSuchElementException("queue empty")
     else {
       val res = first0.elem
       first0 = first0.next
-      if (first0 eq null) last0 = null
       len -= 1
       res
     }
@@ -55,17 +54,12 @@ class Queue[A] extends MutableList[A] with Cloneable[Queue[A]] {
    *  @return the first element of the queue for which p yields true
    */
   def dequeueFirst(p: A => Boolean): Option[A] =
-    if (first0 eq null)
+    if (isEmpty)
       None
     else if (p(first0.elem)) {
       val res: Option[A] = Some(first0.elem)
       first0 = first0.next
       len -= 1
-      if (first0 eq null) {
-        last0 = null
-      } else if (first0.next eq null) {
-        last0 = first0
-      }
       res
     } else
       extractFirst(first0, p) match {
@@ -81,19 +75,14 @@ class Queue[A] extends MutableList[A] with Cloneable[Queue[A]] {
    *             p yields true.
    */
   def dequeueAll(p: A => Boolean): Seq[A] = {
-    if (first0 eq null)
+    if (first0.nonEmpty)
       Seq.empty
     else {
       val res = new ArrayBuffer[A]
-      while ((first0 ne null) && p(first0.elem)) {
+      while ((first0.nonEmpty) && p(first0.elem)) {
         res += first0.elem
         first0 = first0.next
         len -= 1
-        if (first0 eq null) {
-          last0 = null
-        } else if (first0.next eq null) {
-          last0 = first0
-        }
       }
       var cell: Option[LinkedList[A]] = extractFirst(first0, p)
       while (!cell.isEmpty) {
@@ -104,20 +93,21 @@ class Queue[A] extends MutableList[A] with Cloneable[Queue[A]] {
     }
   }
 
-  private def extractFirst(start: LinkedList[A], p: A => Boolean): Option[LinkedList[A]] = {
+  /** Return the proper suffix of this list which starts with the first element that satisfies `p`.
+   *  That element is unlinked from the list. If no element satisfies `p`, return None.
+   */
+  def extractFirst(start: LinkedList[A], p: A => Boolean): Option[LinkedList[A]] = {
     if (isEmpty) None
     else {
       var cell = start
-      while ((cell.next ne null) && !p(cell.next.elem)) {
+      while ((cell.next.nonEmpty) && !p(cell.next.elem)) {
         cell = cell.next
       }
-      if (cell.next eq null)
+      if (cell.next.isEmpty)
         None
       else {
         val res: Option[LinkedList[A]] = Some(cell.next)
         cell.next = cell.next.next
-        if (cell.next eq null)
-          last0 = cell
         len -= 1
         res
       }