scala.collection.immutable.Queue

object Queue extends SeqFactory[Queue] with Serializable

This object provides a set of operations to create immutable.Queue values.

Type Members

type Coll = Queue[_]

The underlying collection type with unknown element type

  • Attributes
    • protected[this]
  • Definition Classes
    • GenericCompanion

class GenericCanBuildFrom[A] extends CanBuildFrom[CC[_], A, CC[A]]

A generic implementation of the CanBuildFrom trait, which forwards all calls to apply(from) to the genericBuilder method of collection from , and which forwards all calls of apply() to the newBuilder method of this factory.

  • Definition Classes
    • GenTraversableFactory

Value Members From scala.collection.generic.GenTraversableFactory

def ReusableCBF: GenericCanBuildFrom[Nothing]

  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def concat[A](xss: collection.Traversable[A]*): Queue[A]

Concatenates all argument collections into a single collection.

  • xss
    • the collections that are to be concatenated.
  • returns
    • the concatenation of all the collections.
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def fill[A](n: Int)(elem: ⇒ A): Queue[A]

Produces a collection containing the results of some element computation a number of times.

  • n
    • the number of elements contained in the collection.
  • elem
    • the element computation
  • returns
    • A collection that contains the results of n evaluations of elem .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def fill[A](n1: Int, n2: Int)(elem: ⇒ A): Queue[Queue[A]]

Produces a two-dimensional collection containing the results of some element computation a number of times.

  • n1
    • the number of elements in the 1st dimension
  • n2
    • the number of elements in the 2nd dimension
  • elem
    • the element computation
  • returns
    • A collection that contains the results of n1 x n2 evaluations of elem .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def fill[A](n1: Int, n2: Int, n3: Int)(elem: ⇒ A): Queue[Queue[Queue[A]]]

Produces a three-dimensional collection containing the results of some element computation a number of times.

  • n1
    • the number of elements in the 1st dimension
  • n2
    • the number of elements in the 2nd dimension
  • n3
    • the number of elements in the 3nd dimension
  • elem
    • the element computation
  • returns
    • A collection that contains the results of n1 x n2 x n3 evaluations of elem .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def fill[A](n1: Int, n2: Int, n3: Int, n4: Int)(elem: ⇒ A): Queue[Queue[Queue[Queue[A]]]]

Produces a four-dimensional collection containing the results of some element computation a number of times.

  • n1
    • the number of elements in the 1st dimension
  • n2
    • the number of elements in the 2nd dimension
  • n3
    • the number of elements in the 3nd dimension
  • n4
    • the number of elements in the 4th dimension
  • elem
    • the element computation
  • returns
    • A collection that contains the results of n1 x n2 x n3 x n4 evaluations of elem .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def fill[A](n1: Int, n2: Int, n3: Int, n4: Int, n5: Int)(elem: ⇒ A): Queue[Queue[Queue[Queue[Queue[A]]]]]

Produces a five-dimensional collection containing the results of some element computation a number of times.

  • n1
    • the number of elements in the 1st dimension
  • n2
    • the number of elements in the 2nd dimension
  • n3
    • the number of elements in the 3nd dimension
  • n4
    • the number of elements in the 4th dimension
  • n5
    • the number of elements in the 5th dimension
  • elem
    • the element computation
  • returns
    • A collection that contains the results of n1 x n2 x n3 x n4 x n5 evaluations of elem .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def iterate[A](start: A, len: Int)(f: (A) ⇒ A): Queue[A]

Produces a collection containing repeated applications of a function to a start value.

  • start
    • the start value of the collection
  • len
    • the number of elements contained inthe collection
  • f
    • the function that’s repeatedly applied
  • returns
    • a collection with len values in the sequence start, f(start), f(f(start)), ...
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def range[T](start: T, end: T)(implicit arg0: Integral[T]): Queue[T]

Produces a collection containing a sequence of increasing of integers.

  • start
    • the first element of the collection
  • end
    • the end value of the collection (the first value NOT contained)
  • returns
    • a collection with values start, start + 1, ..., end - 1
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def range[T](start: T, end: T, step: T)(implicit arg0: Integral[T]): Queue[T]

Produces a collection containing equally spaced values in some integer interval.

  • start
    • the start value of the collection
  • end
    • the end value of the collection (the first value NOT contained)
  • step
    • the difference between successive elements of the collection (must be positive or negative)
  • returns
    • a collection with values start, start + step, ... up to, but excluding end
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def tabulate[A](n: Int)(f: (Int) ⇒ A): Queue[A]

Produces a collection containing values of a given function over a range of integer values starting from 0.

  • n
    • The number of elements in the collection
  • f
    • The function computing element values
  • returns
    • A collection consisting of elements f(0), ..., f(n -1)
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def tabulate[A](n1: Int, n2: Int)(f: (Int, Int) ⇒ A): Queue[Queue[A]]

Produces a two-dimensional collection containing values of a given function over ranges of integer values starting from 0.

  • n1
    • the number of elements in the 1st dimension
  • n2
    • the number of elements in the 2nd dimension
  • f
    • The function computing element values
  • returns
    • A collection consisting of elements f(i1, i2) for 0 <= i1 < n1 and 0 <= i2 < n2 .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def tabulate[A](n1: Int, n2: Int, n3: Int)(f: (Int, Int, Int) ⇒ A): Queue[Queue[Queue[A]]]

Produces a three-dimensional collection containing values of a given function over ranges of integer values starting from 0.

  • n1
    • the number of elements in the 1st dimension
  • n2
    • the number of elements in the 2nd dimension
  • n3
    • the number of elements in the 3nd dimension
  • f
    • The function computing element values
  • returns
    • A collection consisting of elements f(i1, i2, i3) for 0 <= i1 < n1 , 0 <= i2 < n2 , and 0 <= i3 < n3 .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def tabulate[A](n1: Int, n2: Int, n3: Int, n4: Int)(f: (Int, Int, Int, Int) ⇒ A): Queue[Queue[Queue[Queue[A]]]]

Produces a four-dimensional collection containing values of a given function over ranges of integer values starting from 0.

  • n1
    • the number of elements in the 1st dimension
  • n2
    • the number of elements in the 2nd dimension
  • n3
    • the number of elements in the 3nd dimension
  • n4
    • the number of elements in the 4th dimension
  • f
    • The function computing element values
  • returns
    • A collection consisting of elements f(i1, i2, i3, i4) for 0 <= i1 < n1 , 0 <= i2 < n2 , 0 <= i3 < n3 , and 0 <= i4 < n4 .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

def tabulate[A](n1: Int, n2: Int, n3: Int, n4: Int, n5: Int)(f: (Int, Int, Int, Int, Int) ⇒ A): Queue[Queue[Queue[Queue[Queue[A]]]]]

Produces a five-dimensional collection containing values of a given function over ranges of integer values starting from 0.

  • n1
    • the number of elements in the 1st dimension
  • n2
    • the number of elements in the 2nd dimension
  • n3
    • the number of elements in the 3nd dimension
  • n4
    • the number of elements in the 4th dimension
  • n5
    • the number of elements in the 5th dimension
  • f
    • The function computing element values
  • returns
    • A collection consisting of elements f(i1, i2, i3, i4, i5) for 0 <= i1 < n1 , 0 <= i2 < n2 , 0 <= i3 < n3 , 0 <= i4 < n4 , and 0 <= i5 < n5 .
  • Definition Classes
    • GenTraversableFactory

(defined at scala.collection.generic.GenTraversableFactory)

Value Members From scala.collection.generic.SeqFactory

def unapplySeq[A](x: Queue[A]): Some[Queue[A]]

This method is called in a pattern match { case Seq(…) => }.

  • x
    • the selector value
  • returns
    • sequence wrapped in an option, if this is a Seq, otherwise none
  • Definition Classes
    • SeqFactory

(defined at scala.collection.generic.SeqFactory)

Value Members From scala.collection.immutable.Queue

def apply[A](xs: A*): Queue[A]

Creates a immutable queue with the specified elements.

  • A
    • the type of the immutable queue’s elements
  • returns
    • a new immutable queue with elements elems
  • Definition Classes
    • Queue → GenericCompanion

(defined at scala.collection.immutable.Queue)

implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Queue[A]]

The standard CanBuildFrom instance for immutable.Queue objects. The created value is an instance of class GenericCanBuildFrom , which forwards calls to create a new builder to the genericBuilder method of the requesting collection.

(defined at scala.collection.immutable.Queue)

def empty[A]: Queue[A]

An empty collection of type immutable.Queue[A]

  • A
    • the type of the immutable queue’s elements
  • Definition Classes
    • Queue → GenericCompanion

(defined at scala.collection.immutable.Queue)

def newBuilder[A]: Builder[A, Queue[A]]

The default builder for immutable.Queue objects.

  • A
    • the type of the immutable queue’s elements
  • Definition Classes
    • Queue → GenericCompanion (defined at scala.collection.immutable.Queue)

Full Source:

/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */

package scala
package collection
package immutable

import generic._
import mutable.{ Builder, ListBuffer }

/** `Queue` objects implement data structures that allow to
 *  insert and retrieve elements in a first-in-first-out (FIFO) manner.
 *
 *  `Queue` is implemented as a pair of `List`s, one containing the ''in'' elements and the other the ''out'' elements.
 *  Elements are added to the ''in'' list and removed from the ''out'' list. When the ''out'' list runs dry, the
 *  queue is pivoted by replacing the ''out'' list by ''in.reverse'', and ''in'' by ''Nil''.
 *
 *  Adding items to the queue always has cost `O(1)`. Removing items has cost `O(1)`, except in the case
 *  where a pivot is required, in which case, a cost of `O(n)` is incurred, where `n` is the number of elements in the queue. When this happens,
 *  `n` remove operations with `O(1)` cost are guaranteed. Removing an item is on average `O(1)`.
 *
 *  @author  Erik Stenman
 *  @version 1.0, 08/07/2003
 *  @since   1
 *  @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#immutable_queues "Scala's Collection Library overview"]]
 *  section on `Immutable Queues` for more information.
 *
 *  @define Coll `immutable.Queue`
 *  @define coll immutable queue
 *  @define mayNotTerminateInf
 *  @define willNotTerminateInf
 */

@SerialVersionUID(-7622936493364270175L)
@deprecatedInheritance("The implementation details of immutable queues make inheriting from them unwise.", "2.11.0")
class Queue[+A] protected(protected val in: List[A], protected val out: List[A])
         extends AbstractSeq[A]
            with LinearSeq[A]
            with GenericTraversableTemplate[A, Queue]
            with LinearSeqLike[A, Queue[A]]
            with Serializable {

  override def companion: GenericCompanion[Queue] = Queue

  /** Returns the `n`-th element of this queue.
   *  The first element is at position `0`.
   *
   *  @param  n index of the element to return
   *  @return   the element at position `n` in this queue.
   *  @throws java.util.NoSuchElementException if the queue is too short.
   */
  override def apply(n: Int): A = {
    val olen = out.length
    if (n < olen) out.apply(n)
    else {
      val m = n - olen
      val ilen = in.length
      if (m < ilen) in.apply(ilen - m - 1)
      else throw new NoSuchElementException("index out of range")
    }
  }

  /** Returns the elements in the list as an iterator
   */
  override def iterator: Iterator[A] = (out ::: in.reverse).iterator

  /** Checks if the queue is empty.
   *
   *  @return true, iff there is no element in the queue.
   */
  override def isEmpty: Boolean = in.isEmpty && out.isEmpty

  override def head: A =
    if (out.nonEmpty) out.head
    else if (in.nonEmpty) in.last
    else throw new NoSuchElementException("head on empty queue")

  override def tail: Queue[A] =
    if (out.nonEmpty) new Queue(in, out.tail)
    else if (in.nonEmpty) new Queue(Nil, in.reverse.tail)
    else throw new NoSuchElementException("tail on empty queue")

  /** Returns the length of the queue.
   */
  override def length = in.length + out.length

  override def +:[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Queue[A], B, That]): That = bf match {
    case _: Queue.GenericCanBuildFrom[_] => new Queue(in, elem :: out).asInstanceOf[That]
    case _                               => super.+:(elem)(bf)
  }

  override def :+[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Queue[A], B, That]): That = bf match {
    case _: Queue.GenericCanBuildFrom[_] => enqueue(elem).asInstanceOf[That]
    case _                               => super.:+(elem)(bf)
  }

  /** Creates a new queue with element added at the end
   *  of the old queue.
   *
   *  @param  elem        the element to insert
   */
  def enqueue[B >: A](elem: B) = new Queue(elem :: in, out)

  /** Returns a new queue with all elements provided by an `Iterable` object
   *  added at the end of the queue.
   *
   *  The elements are prepended in the order they are given out by the
   *  iterator.
   *
   *  @param  iter        an iterable object
   */
  def enqueue[B >: A](iter: Iterable[B]) =
    new Queue(iter.toList reverse_::: in, out)

  /** Returns a tuple with the first element in the queue,
   *  and a new queue with this element removed.
   *
   *  @throws java.util.NoSuchElementException
   *  @return the first element of the queue.
   */
  def dequeue: (A, Queue[A]) = out match {
    case Nil if !in.isEmpty => val rev = in.reverse ; (rev.head, new Queue(Nil, rev.tail))
    case x :: xs            => (x, new Queue(in, xs))
    case _                  => throw new NoSuchElementException("dequeue on empty queue")
  }

  /** Optionally retrieves the first element and a queue of the remaining elements.
   *
   * @return A tuple of the first element of the queue, and a new queue with this element removed.
   *         If the queue is empty, `None` is returned.
   */
  def dequeueOption: Option[(A, Queue[A])] = if(isEmpty) None else Some(dequeue)

  /** Returns the first element in the queue, or throws an error if there
   *  is no element contained in the queue.
   *
   *  @throws java.util.NoSuchElementException
   *  @return the first element.
   */
  def front: A = head

  /** Returns a string representation of this queue.
   */
  override def toString() = mkString("Queue(", ", ", ")")
}

/** $factoryInfo
 *  @define Coll `immutable.Queue`
 *  @define coll immutable queue
 */
object Queue extends SeqFactory[Queue] {
  /** $genericCanBuildFromInfo */
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Queue[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]
  def newBuilder[A]: Builder[A, Queue[A]] = new ListBuffer[A] mapResult (x => new Queue[A](Nil, x.toList))
  override def empty[A]: Queue[A] = EmptyQueue.asInstanceOf[Queue[A]]
  override def apply[A](xs: A*): Queue[A] = new Queue[A](Nil, xs.toList)

  private object EmptyQueue extends Queue[Nothing](Nil, Nil) { }
}