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