Scala example source code file (Queue.scala)

This example Scala source code file (Queue.scala) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Java - Scala tags/keywords

a, a, arraybuffer, boolean, canbuildfrom, linkedlist, mutablelist, none, none, option, option, queue, queue, seq

The Scala Queue.scala source code

/*                     __                                               *\
**     ________ ___   / /  ___     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
 *  
 *  @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 }
}