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