OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
| 5 /// Import `collection.dart` instead. |
| 6 @Deprecated("Will be removed in collection 2.0.0.") |
5 library dart.pkg.collection.priority_queue; | 7 library dart.pkg.collection.priority_queue; |
6 | 8 |
7 import "dart:collection" show SplayTreeSet; | 9 export "src/priority_queue.dart"; |
8 | |
9 /** | |
10 * A priority queue is a priority based work-list of elements. | |
11 * | |
12 * The queue allows adding elements, and removing them again in priority order. | |
13 */ | |
14 abstract class PriorityQueue<E> { | |
15 /** | |
16 * Creates an empty [PriorityQueue]. | |
17 * | |
18 * The created [PriorityQueue] is a plain [HeapPriorityQueue]. | |
19 * | |
20 * The [comparison] is a [Comparator] used to compare the priority of | |
21 * elements. An element that compares as less than another element has | |
22 * a higher priority. | |
23 * | |
24 * If [comparison] is omitted, it defaults to [Comparable.compare]. | |
25 */ | |
26 factory PriorityQueue([int comparison(E e1, E e2)]) = HeapPriorityQueue<E>; | |
27 | |
28 /** | |
29 * Number of elements in the queue. | |
30 */ | |
31 int get length; | |
32 | |
33 /** | |
34 * Whether the queue is empty. | |
35 */ | |
36 bool get isEmpty; | |
37 | |
38 /** | |
39 * Whether the queue has any elements. | |
40 */ | |
41 bool get isNotEmpty; | |
42 | |
43 /** | |
44 * Checks if [object] is in the queue. | |
45 * | |
46 * Returns true if the element is found. | |
47 */ | |
48 bool contains(E object); | |
49 | |
50 /** | |
51 * Adds element to the queue. | |
52 * | |
53 * The element will become the next to be removed by [removeFirst] | |
54 * when all elements with higher priority have been removed. | |
55 */ | |
56 void add(E element); | |
57 | |
58 /** | |
59 * Adds all [elements] to the queue. | |
60 */ | |
61 void addAll(Iterable<E> elements); | |
62 | |
63 /** | |
64 * Returns the next element that will be returned by [removeFirst]. | |
65 * | |
66 * The element is not removed from the queue. | |
67 * | |
68 * The queue must not be empty when this method is called. | |
69 */ | |
70 E get first; | |
71 | |
72 /** | |
73 * Removes and returns the element with the highest priority. | |
74 * | |
75 * Repeatedly calling this method, without adding element in between, | |
76 * is guaranteed to return elements in non-decreasing order as, specified by | |
77 * [comparison]. | |
78 * | |
79 * The queue must not be empty when this method is called. | |
80 */ | |
81 E removeFirst(); | |
82 | |
83 /** | |
84 * Removes an element that compares equal to [element] in the queue. | |
85 * | |
86 * Returns true if an element is found and removed, | |
87 * and false if no equal element is found. | |
88 */ | |
89 bool remove(E element); | |
90 | |
91 /** | |
92 * Removes all the elements from this queue and returns them. | |
93 * | |
94 * The returned iterable has no specified order. | |
95 */ | |
96 Iterable<E> removeAll(); | |
97 | |
98 /** | |
99 * Removes all the elements from this queue. | |
100 */ | |
101 void clear(); | |
102 | |
103 /** | |
104 * Returns a list of the elements of this queue in priority order. | |
105 * | |
106 * The queue is not modified. | |
107 * | |
108 * The order is the order that the elements would be in if they were | |
109 * removed from this queue using [removeFirst]. | |
110 */ | |
111 List<E> toList(); | |
112 | |
113 /** | |
114 * Return a comparator based set using the comparator of this queue. | |
115 * | |
116 * The queue is not modified. | |
117 * | |
118 * The returned [Set] is currently a [SplayTreeSet], | |
119 * but this may change as other ordered sets are implemented. | |
120 * | |
121 * The set contains all the elements of this queue. | |
122 * If an element occurs more than once in the queue, | |
123 * the set will contain it only once. | |
124 */ | |
125 Set<E> toSet(); | |
126 } | |
127 | |
128 /** | |
129 * Heap based priority queue. | |
130 * | |
131 * The elements are kept in a heap structure, | |
132 * where the element with the highest priority is immediately accessible, | |
133 * and modifying a single element takes | |
134 * logarithmic time in the number of elements on average. | |
135 * | |
136 * * The [add] and [removeFirst] operations take amortized logarithmic time, | |
137 * O(log(n)), but may occasionally take linear time when growing the capacity | |
138 * of the heap. | |
139 * * The [addAll] operation works as doing repeated [add] operations. | |
140 * * The [first] getter takes constant time, O(1). | |
141 * * The [clear] and [removeAll] methods also take constant time, O(1). | |
142 * * The [contains] and [remove] operations may need to search the entire | |
143 * queue for the elements, taking O(n) time. | |
144 * * The [toList] operation effectively sorts the elements, taking O(n*log(n)) | |
145 * time. | |
146 * * The [toSet] operation effectively adds each element to the new set, taking | |
147 * an expected O(n*log(n)) time. | |
148 */ | |
149 class HeapPriorityQueue<E> implements PriorityQueue<E> { | |
150 /** | |
151 * Initial capacity of a queue when created, or when added to after a [clear]. | |
152 * | |
153 * Number can be any positive value. Picking a size that gives a whole | |
154 * number of "tree levels" in the heap is only done for aesthetic reasons. | |
155 */ | |
156 static const int _INITIAL_CAPACITY = 7; | |
157 | |
158 /** | |
159 * The comparison being used to compare the priority of elements. | |
160 */ | |
161 final Comparator comparison; | |
162 | |
163 /** | |
164 * List implementation of a heap. | |
165 */ | |
166 List<E> _queue = new List<E>(_INITIAL_CAPACITY); | |
167 | |
168 /** | |
169 * Number of elements in queue. | |
170 * | |
171 * The heap is implemented in the first [_length] entries of [_queue]. | |
172 */ | |
173 int _length = 0; | |
174 | |
175 /** | |
176 * Create a new priority queue. | |
177 * | |
178 * The [comparison] is a [Comparator] used to compare the priority of | |
179 * elements. An element that compares as less than another element has | |
180 * a higher priority. | |
181 * | |
182 * If [comparison] is omitted, it defaults to [Comparable.compare]. | |
183 */ | |
184 HeapPriorityQueue([int comparison(E e1, E e2)]) | |
185 : comparison = (comparison != null) ? comparison : Comparable.compare; | |
186 | |
187 void add(E element) { | |
188 _add(element); | |
189 } | |
190 | |
191 void addAll(Iterable<E> elements) { | |
192 for (E element in elements) { | |
193 _add(element); | |
194 } | |
195 } | |
196 | |
197 void clear() { | |
198 _queue = const []; | |
199 _length = 0; | |
200 } | |
201 | |
202 bool contains(E object) { | |
203 return _locate(object) >= 0; | |
204 } | |
205 | |
206 E get first { | |
207 if (_length == 0) throw new StateError("No such element"); | |
208 return _queue[0]; | |
209 } | |
210 | |
211 bool get isEmpty => _length == 0; | |
212 | |
213 bool get isNotEmpty => _length != 0; | |
214 | |
215 int get length => _length; | |
216 | |
217 bool remove(E element) { | |
218 int index = _locate(element); | |
219 if (index < 0) return false; | |
220 E last = _removeLast(); | |
221 if (index < _length) { | |
222 int comp = comparison(last, element); | |
223 if (comp <= 0) { | |
224 _bubbleUp(last, index); | |
225 } else { | |
226 _bubbleDown(last, index); | |
227 } | |
228 } | |
229 return true; | |
230 } | |
231 | |
232 Iterable<E> removeAll() { | |
233 List<E> result = _queue; | |
234 int length = _length; | |
235 _queue = const []; | |
236 _length = 0; | |
237 return result.take(length); | |
238 } | |
239 | |
240 E removeFirst() { | |
241 if (_length == 0) throw new StateError("No such element"); | |
242 E result = _queue[0]; | |
243 E last = _removeLast(); | |
244 if (_length > 0) { | |
245 _bubbleDown(last, 0); | |
246 } | |
247 return result; | |
248 } | |
249 | |
250 List<E> toList() { | |
251 List<E> list = new List<E>()..length = _length; | |
252 list.setRange(0, _length, _queue); | |
253 list.sort(comparison); | |
254 return list; | |
255 } | |
256 | |
257 Set<E> toSet() { | |
258 Set<E> set = new SplayTreeSet<E>(comparison); | |
259 for (int i = 0; i < _length; i++) { | |
260 set.add(_queue[i]); | |
261 } | |
262 return set; | |
263 } | |
264 | |
265 /** | |
266 * Returns some representation of the queue. | |
267 * | |
268 * The format isn't significant, and may change in the future. | |
269 */ | |
270 String toString() { | |
271 return _queue.take(_length).toString(); | |
272 } | |
273 | |
274 /** | |
275 * Add element to the queue. | |
276 * | |
277 * Grows the capacity if the backing list is full. | |
278 */ | |
279 void _add(E element) { | |
280 if (_length == _queue.length) _grow(); | |
281 _bubbleUp(element, _length++); | |
282 } | |
283 | |
284 /** | |
285 * Find the index of an object in the heap. | |
286 * | |
287 * Returns -1 if the object is not found. | |
288 */ | |
289 int _locate(E object) { | |
290 if (_length == 0) return -1; | |
291 // Count positions from one instead of zero. This gives the numbers | |
292 // some nice properties. For example, all right children are odd, | |
293 // their left sibling is even, and the parent is found by shifting | |
294 // right by one. | |
295 // Valid range for position is [1.._length], inclusive. | |
296 int position = 1; | |
297 // Pre-order depth first search, omit child nodes if the current | |
298 // node has lower priority than [object], because all nodes lower | |
299 // in the heap will also have lower priority. | |
300 do { | |
301 int index = position - 1; | |
302 E element = _queue[index]; | |
303 int comp = comparison(element, object); | |
304 if (comp == 0) return index; | |
305 if (comp < 0) { | |
306 // Element may be in subtree. | |
307 // Continue with the left child, if it is there. | |
308 int leftChildPosition = position * 2; | |
309 if (leftChildPosition <= _length) { | |
310 position = leftChildPosition; | |
311 continue; | |
312 } | |
313 } | |
314 // Find the next right sibling or right ancestor sibling. | |
315 do { | |
316 while (position.isOdd) { | |
317 // While position is a right child, go to the parent. | |
318 position >>= 1; | |
319 } | |
320 // Then go to the right sibling of the left-child. | |
321 position += 1; | |
322 } while (position > _length); // Happens if last element is a left child. | |
323 } while (position != 1); // At root again. Happens for right-most element. | |
324 return -1; | |
325 } | |
326 | |
327 E _removeLast() { | |
328 int newLength = _length - 1; | |
329 E last = _queue[newLength]; | |
330 _queue[newLength] = null; | |
331 _length = newLength; | |
332 return last; | |
333 } | |
334 | |
335 /** | |
336 * Place [element] in heap at [index] or above. | |
337 * | |
338 * Put element into the empty cell at `index`. | |
339 * While the `element` has higher priority than the | |
340 * parent, swap it with the parent. | |
341 */ | |
342 void _bubbleUp(E element, int index) { | |
343 while (index > 0) { | |
344 int parentIndex = (index - 1) ~/ 2; | |
345 E parent = _queue[parentIndex]; | |
346 if (comparison(element, parent) > 0) break; | |
347 _queue[index] = parent; | |
348 index = parentIndex; | |
349 } | |
350 _queue[index] = element; | |
351 } | |
352 | |
353 /** | |
354 * Place [element] in heap at [index] or above. | |
355 * | |
356 * Put element into the empty cell at `index`. | |
357 * While the `element` has lower priority than either child, | |
358 * swap it with the highest priority child. | |
359 */ | |
360 void _bubbleDown(E element, int index) { | |
361 int rightChildIndex = index * 2 + 2; | |
362 while (rightChildIndex < _length) { | |
363 int leftChildIndex = rightChildIndex - 1; | |
364 E leftChild = _queue[leftChildIndex]; | |
365 E rightChild = _queue[rightChildIndex]; | |
366 int comp = comparison(leftChild, rightChild); | |
367 int minChildIndex; | |
368 E minChild; | |
369 if (comp < 0) { | |
370 minChild = leftChild; | |
371 minChildIndex = leftChildIndex; | |
372 } else { | |
373 minChild = rightChild; | |
374 minChildIndex = rightChildIndex; | |
375 } | |
376 comp = comparison(element, minChild); | |
377 if (comp <= 0) { | |
378 _queue[index] = element; | |
379 return; | |
380 } | |
381 _queue[index] = minChild; | |
382 index = minChildIndex; | |
383 rightChildIndex = index * 2 + 2; | |
384 } | |
385 int leftChildIndex = rightChildIndex - 1; | |
386 if (leftChildIndex < _length) { | |
387 E child = _queue[leftChildIndex]; | |
388 int comp = comparison(element, child); | |
389 if (comp > 0) { | |
390 _queue[index] = child; | |
391 index = leftChildIndex; | |
392 } | |
393 } | |
394 _queue[index] = element; | |
395 } | |
396 | |
397 /** | |
398 * Grows the capacity of the list holding the heap. | |
399 * | |
400 * Called when the list is full. | |
401 */ | |
402 void _grow() { | |
403 int newCapacity = _queue.length * 2 + 1; | |
404 if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY; | |
405 List<E> newQueue = new List<E>(newCapacity); | |
406 newQueue.setRange(0, _length, _queue); | |
407 _queue = newQueue; | |
408 } | |
409 } | |
OLD | NEW |