From 4c1cae0ef2772574a85d49f939b12c0e515aa6bd Mon Sep 17 00:00:00 2001 From: Aleksandar Pokopec Date: Wed, 17 Nov 2010 17:04:15 +0000 Subject: Fixes #3970 and a bunch of other issues. Review by extempore. --- .../collection/mutable/DoubleLinkedList.scala | 1 + .../collection/mutable/DoubleLinkedListLike.scala | 82 ++++++++++++++++++++-- .../scala/collection/mutable/LinkedListLike.scala | 24 +++++++ 3 files changed, 101 insertions(+), 6 deletions(-) (limited to 'src/library') diff --git a/src/library/scala/collection/mutable/DoubleLinkedList.scala b/src/library/scala/collection/mutable/DoubleLinkedList.scala index d3c86953c8..f71bc12570 100644 --- a/src/library/scala/collection/mutable/DoubleLinkedList.scala +++ b/src/library/scala/collection/mutable/DoubleLinkedList.scala @@ -53,6 +53,7 @@ class DoubleLinkedList[A]() extends LinearSeq[A] if (next != null) { this.elem = elem this.next = next + this.next.prev = this } } 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 + } + } diff --git a/src/library/scala/collection/mutable/LinkedListLike.scala b/src/library/scala/collection/mutable/LinkedListLike.scala index d7ad8cf367..c15841720f 100644 --- a/src/library/scala/collection/mutable/LinkedListLike.scala +++ b/src/library/scala/collection/mutable/LinkedListLike.scala @@ -19,6 +19,30 @@ import annotation.tailrec * list, type variable `This` is used to model self types of * linked lists. * + * If the list is empty `next` must be set to `this`. The last node in every + * mutable linked list is empty. + * + * Examples (`_` represents no value): + * + * {{{ + * + * Empty: + * + * [ _ ] --, + * [ ] <-` + * + * Single element: + * + * [ x ] --> [ _ ] --, + * [ ] <-` + * + * More elements: + * + * [ x ] --> [ y ] --> [ z ] --> [ _ ] --, + * [ ] <-` + * + * }}} + * * @author Matthias Zenger * @author Martin Odersky * @version 1.0, 08/07/2003 -- cgit v1.2.3