1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection
package immutable
import scala.annotation.tailrec
object Queue {
val Empty: Queue[Nothing] = new Queue(Nil, Nil)
def apply[A](elems: A*) = new Queue(Nil, elems.toList)
}
/** <code>Queue</code> objects implement data structures that allow to
* insert and retrieve elements in a first-in-first-out (FIFO) manner.
*
* @author Erik Stenman
* @version 1.0, 08/07/2003
* @since 1
*/
@serializable
@SerialVersionUID(-7622936493364270175L)
class Queue[+A] protected(
protected val in: List[A],
protected val out: List[A]) extends Seq[A]
{
/** Returns the <code>n</code>-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 <code>n</code> in this queue.
* @throws Predef.NoSuchElementException if the queue is too short.
*/
def apply(n: Int): A = {
val len = out.length
if (n < len) out.apply(n)
else {
val m = n - len
if (m < in.length) in.reverse.apply(m)
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
/** Returns the length of the queue.
*/
def length = in.length + out.length
/** Creates a new queue with element added at the end
* of the old queue.
*
* @param elem the element to insert
*/
@deprecated("Use the method <code>enqueue</code> from now on.")
def +[B >: A](elem: B) = enqueue(elem)
/** 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 all elements provided by
* an <code>Iterable</code> 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
*/
@deprecated("Use the method <code>enqueue</code> from now on.")
def +[B >: A](iter: Iterable[B]) = enqueue(iter)
/** Returns a new queue with all elements provided by
* an <code>Iterable</code> 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.iterator.toList.reverse ::: in, out)
/** Returns a tuple with the first element in the queue,
* and a new queue with this element removed.
*
* @throws Predef.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")
}
/** Returns the first element in the queue, or throws an error if there
* is no element contained in the queue.
*
* @throws Predef.NoSuchElementException
* @return the first element.
*/
def front: A =
if (!out.isEmpty) out.head
else if (!in.isEmpty) in.last
else throw new NoSuchElementException("front on empty queue")
/** Returns a string representation of this queue.
*/
override def toString() = mkString("Queue(", ", ", ")")
}
|
