From aaa4da9f37a154870e39d7b89239019ce5257337 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Tue, 10 Nov 2009 16:31:36 +0000 Subject: tentative re-implementation of LinkedList and s... tentative re-implementation of LinkedList and subclasses --- .../collection/mutable/DoubleLinkedListLike.scala | 35 ++++++++------- .../scala/collection/mutable/LinkedList.scala | 19 +++++--- .../scala/collection/mutable/LinkedListLike.scala | 52 ++++++++++++++-------- .../scala/collection/mutable/MutableList.scala | 35 ++++++++------- src/library/scala/collection/mutable/Queue.scala | 30 +++++-------- 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 scala.List 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 } -- cgit v1.2.3