diff options
author | Matthias Zenger <mzenger@gmail.com> | 2004-06-08 12:16:03 +0000 |
---|---|---|
committer | Matthias Zenger <mzenger@gmail.com> | 2004-06-08 12:16:03 +0000 |
commit | dea41a5aabd361a4b639045c264d5e7bd1df399e (patch) | |
tree | 31a2e46cc167db77a981db4c9a080373b8bbef37 /sources | |
parent | 368d511247d5be7bd3ae8a1ce4a5be45fd3dcceb (diff) | |
download | scala-dea41a5aabd361a4b639045c264d5e7bd1df399e.tar.gz scala-dea41a5aabd361a4b639045c264d5e7bd1df399e.tar.bz2 scala-dea41a5aabd361a4b639045c264d5e7bd1df399e.zip |
*** empty log message ***
Diffstat (limited to 'sources')
-rw-r--r-- | sources/scala/collection/mutable/Queue.scala | 78 |
1 files changed, 77 insertions, 1 deletions
diff --git a/sources/scala/collection/mutable/Queue.scala b/sources/scala/collection/mutable/Queue.scala index 0584ac0b86..308bed6bad 100644 --- a/sources/scala/collection/mutable/Queue.scala +++ b/sources/scala/collection/mutable/Queue.scala @@ -63,11 +63,87 @@ class Queue[A] extends MutableList[A] with Cloneable { else { val res = first.elem; first = first.next; - len = len - 1; + if (first == null) + last = null; + len = len - 1; res; } } + /** Returns the first element in the queue which satisfies the + * given predicate, and removes this element from the queue. + * + * @param p the predicate used for choosing the first element + * @return the first element of the queue for which p yields true + */ + def dequeueFirst(p: A => Boolean): Option[A] = { + if (first == null) + None + else if (p(first.elem)) { + val res = Some(first.elem); + first = first.next; + len = len - 1; + if (first == null) { + last = null; + } else if (first.next == null) { + last = first; + } + res + } else + extractFirst(first, p) match { + case None => None + case Some(cell) => Some(cell.elem) + } + } + + /** Returns all elements in the queue which satisfy the + * given predicate, and removes those elements from the queue. + * + * @param p the predicate used for choosing elements + * @return a sequence of all elements in the queue for which + * p yields true. + */ + def dequeueAll(p: A => Boolean): Seq[A] = { + val res = new ArrayBuffer[A]; + if (first == null) + res; + else { + while (p(first.elem)) { + res += first.elem; + first = first.next; + len = len - 1; + if (first == null) { + last = null; + } else if (first.next == null) { + last = first; + } + } + var cell: Option[LinkedList[A]] = extractFirst(first, p); + while (!cell.isEmpty) { + res += cell.get.elem; + cell = extractFirst(cell.get, p); + } + res + } + } + + private def extractFirst(start: LinkedList[A], p: A => Boolean): Option[LinkedList[A]] = { + var cell = start; + while ((cell.next != null) && !p(cell.next.elem)) { + cell = cell.next; + } + if (cell.next == null) + None + else { + val res = Some(cell.next); + cell.next = cell.next.next; + if (cell.next == null) + last = cell; + len = len - 1; + res + } + } + /** Returns the first element in the queue, or throws an error if there * is no element contained in the queue. * |