Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

177 lines (158 sloc) 5.149 kb
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala.collection
package mutable
import generic._
/** `Queue` objects implement data structures that allow to
* insert and retrieve elements in a first-in-first-out (FIFO) manner.
*
* @author Matthias Zenger
* @author Martin Odersky
* @version 2.8
* @since 1
* @see [[http://docs.scala-lang.org/overviews/collections/concrete-mutable-collection-classes.html#mutable_queues "Scala's Collection Library overview"]]
* section on `Queues` for more information.
*
* @define Coll mutable.Queue
* @define coll mutable queue
* @define orderDependent
* @define orderDependentFold
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
@cloneable
class Queue[A]
extends MutableList[A]
with GenericTraversableTemplate[A, Queue]
with Cloneable[Queue[A]]
with Serializable
{
override def companion: GenericCompanion[Queue] = Queue
override protected[this] def newBuilder = companion.newBuilder[A]
private[mutable] def this(fst: LinkedList[A], lst: LinkedList[A], lng: Int) {
this()
first0 = fst
last0 = lst
len = lng
}
/** Adds all elements to the queue.
*
* @param elems the elements to add.
*/
def enqueue(elems: A*): Unit = this ++= elems
/** Returns the first element in the queue, and removes this element
* from the queue.
*
* @throws Predef.NoSuchElementException
* @return the first element of the queue.
*/
def dequeue(): A =
if (isEmpty)
throw new NoSuchElementException("queue empty")
else {
val res = first0.elem
first0 = first0.next
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 (isEmpty)
None
else if (p(first0.elem)) {
val res: Option[A] = Some(first0.elem)
first0 = first0.next
len -= 1
res
} else {
val optElem = removeFromList(p)
if (optElem != None) len -= 1
optElem
}
private def removeFromList(p: A => Boolean): Option[A] = {
var leftlst = first0
var res: Option[A] = None
while (leftlst.next.nonEmpty && !p(leftlst.next.elem)) {
leftlst = leftlst.next
}
if (leftlst.next.nonEmpty) {
res = Some(leftlst.next.elem)
if (leftlst.next eq last0) last0 = leftlst
leftlst.next = leftlst.next.next
}
res
}
/** 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] = {
if (first0.isEmpty)
Seq.empty
else {
val res = new ArrayBuffer[A]
while ((first0.nonEmpty) && p(first0.elem)) {
res += first0.elem
first0 = first0.next
len -= 1
}
if (first0.isEmpty) res
else removeAllFromList(p, res)
}
}
private def removeAllFromList(p: A => Boolean, res: ArrayBuffer[A]): ArrayBuffer[A] = {
var leftlst = first0
while (leftlst.next.nonEmpty) {
if (p(leftlst.next.elem)) {
res += leftlst.next.elem
if (leftlst.next eq last0) last0 = leftlst
leftlst.next = leftlst.next.next
len -= 1
} else leftlst = leftlst.next
}
res
}
/** 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.nonEmpty) && !p(cell.next.elem)) {
cell = cell.next
}
if (cell.next.isEmpty)
None
else {
val res: Option[LinkedList[A]] = Some(cell.next)
cell.next = cell.next.next
len -= 1
res
}
}
}
/** Returns the first element in the queue, or throws an error if there
* is no element contained in the queue.
*
* @return the first element.
*/
def front: A = head
}
object Queue extends SeqFactory[Queue] {
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Queue[A]] = new GenericCanBuildFrom[A]
def newBuilder[A]: Builder[A, Queue[A]] = new MutableList[A] mapResult { _.toQueue }
}
Jump to Line
Something went wrong with that request. Please try again.