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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2006, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.mutable
//import Predef.{NoSuchElementException, UnsupportedOperationException}
/** This class implements priority queues using a heap. The
* elements of the queue have to be ordered in terms of the
* <code>Ordered[T]</code> class.
*
* @author Matthias Zenger
* @version 1.0, 03/05/2004
*/
[serializable, cloneable]
class PriorityQueue[A <% Ordered[A]] extends ResizableArray[A] {
size = size + 1 // we do not use array(0)
protected def fixUp(as: Array[A], m: Int): Unit = {
var k: Int = m
while ((k > 1) && (as(k / 2) < as(k))) {
swap(k, k / 2)
k = k / 2
}
}
protected def fixDown(as: Array[A], m: Int, n: Int): Unit = {
var k: Int = m
var loop: Boolean = true
while (loop && (n >= 2 * k)) {
var j = 2 * k
if ((j < n) && (as(j) < as(j + 1)))
j = j + 1;
if (!(as(k) < as(j)))
loop = false
else {
val h = as(k)
as(k) = as(j)
as(j) = h
k = j
}
}
}
/** Checks if the queue is empty.
*
* @return true, iff there is no element in the queue.
*/
override def isEmpty: Boolean = size < 2
/** Inserts a single element into the priority queue.
*
* @param elem the element to insert
*/
def +=(elem: A): Unit = {
ensureSize(size+1)
array(size) = elem
fixUp(array, size)
size = size + 1
}
def +(elem: A): PriorityQueue[A] = { this += elem; this }
/** Add two or more elements to this set.
* @param elem1 the first element.
* @param kv2 the second element.
* @param kvs the remaining elements.
*/
def += (elem1: A, elem2: A, elems: A*) { this += elem1; this += elem2; this ++= elems }
def + (elem1: A, elem2: A, elems: A*) = { this.+=(elem1, elem2, elems: _*); this }
/** Adds all elements provided by an <code>Iterable</code> object
* into the priority queue.
*
* @param iter an iterable object
*/
def ++=(iter: Iterable[A]): Unit = this ++= iter.elements
/** Adds all elements provided by an iterator into the priority queue.
*
* @param it an iterator
*/
def ++=(it: Iterator[A]): Unit = it foreach { e => this += e }
def ++(iter: Iterable[A]): PriorityQueue[A] = { this ++= iter; this }
def ++(iter: Iterator[A]): PriorityQueue[A] = { this ++= iter; this }
/** Adds all elements to the queue.
*
* @param elems the elements to add.
*/
def enqueue(elems: A*): Unit = (this ++= elems)
/** Returns the element with the highest priority in the queue,
* and removes this element from the queue.
*
* @throws Predef.NoSuchElementException
* @return the element with the highest priority.
*/
def dequeue: A =
if (size > 1) {
size = size - 1
swap(1, size)
fixDown(array, 1, size - 1)
array(size)
} else
throw new NoSuchElementException("no element to remove from heap")
/** Returns the element with the highest priority in the queue,
* or throws an error if there is no element contained in the queue.
*
* @return the element with the highest priority.
*/
def max: A = if (size > 1) array(1) else throw new NoSuchElementException("queue is empty")
/** Removes all elements from the queue. After this operation is completed,
* the queue will be empty.
*/
def clear: Unit = { size = 1 }
/** Returns an iterator which yiels all the elements of the priority
* queue in descending priority order.
*
* @return an iterator over all elements sorted in descending order.
*/
override def elements: Iterator[A] = new Iterator[A] {
val as: Array[A] = new Array[A](size)
Array.copy(array, 0, as, 0, size)
var i = size - 1
def hasNext: Boolean = i > 0
def next: A = {
val res = as(1)
as(1) = as(i)
i = i - 1
fixDown(as, 1, i)
res
}
}
/** Checks if two queues are structurally identical.
*
* @return true, iff both queues contain the same sequence of elements.
*/
override def equals(that: Any): Boolean =
that.isInstanceOf[PriorityQueue[A]] &&
{ val other = that.asInstanceOf[PriorityQueue[A]]
elements.zip(other.elements).forall {
case Pair(thiselem, thatelem) => thiselem == thatelem
}}
/** The hashCode method always yields an error, since it is not
* safe to use mutable queues as keys in hash tables.
*
* @return never.
*/
override def hashCode(): Int = throw new UnsupportedOperationException("unsuitable as hash key")
/** Returns a regular queue containing the same elements.
*/
def toQueue: Queue[A] = {
val res = new Queue[A]
res ++= this
res
}
/** Returns a textual representation of a queue as a string.
*
* @return the string representation of this queue.
*/
override def toString() = toList.mkString("PriorityQueue(", ", ", ")")
/** This method clones the priority queue.
*
* @return a priority queue with the same elements.
*/
override def clone(): PriorityQueue[A] = {
val res = new PriorityQueue[A]
res ++= this
res
}
}
|
