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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.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
*/
@serializable
class Queue[+A] protected(
protected val in: List[A],
protected val out: List[A])
extends immutable.Sequence[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 = {
@tailrec
def walk(i: Int, inlist: List[A], outlist: List[A]): A =
(i == 0, inlist.isEmpty, outlist.isEmpty) match {
case (_, true, true) => throw new NoSuchElementException("index out of range")
case (true, _, false) => outlist.head
case (true, _, true) => inlist.last
case (false, _, false) => walk(i - 1, inlist, outlist.tail)
case (false, false, true) => walk(i - 1, Nil, inlist.reverse.tail)
}
walk(n, in, out)
}
/** 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("queue empty")
}
/** 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("queue empty")
/** Returns a string representation of this queue.
*/
override def toString() = mkString("Queue(", ", ", ")")
/** Compares two queues for equality by comparing
* each element in the queues.
*
* @return true, iff the two queues are structurally equal.
*/
override def equals(o: Any): Boolean = o match {
case q: Queue[_] => this sameElements q
case _ => false
}
override lazy val hashCode: Int =
if (isEmpty) 0
else dequeue match { case (x,y) => x.hashCode + y.hashCode }
}
|
