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 library dart.pkg.collection.priority_queue; |
6 | 6 |
7 import "dart:collection" show SplayTreeSet; | 7 import "dart:collection" show SplayTreeSet; |
8 | 8 |
9 /** | 9 /** |
10 * A priority queue is a priority based work-list of elements. | 10 * A priority queue is a priority based work-list of elements. |
(...skipping 17 matching lines...) Expand all Loading... |
28 bool get isNotEmpty; | 28 bool get isNotEmpty; |
29 | 29 |
30 /** | 30 /** |
31 * Checks if [object] is in the queue. | 31 * Checks if [object] is in the queue. |
32 * | 32 * |
33 * Returns true if the element is found. | 33 * Returns true if the element is found. |
34 */ | 34 */ |
35 bool contains(E object); | 35 bool contains(E object); |
36 | 36 |
37 /** | 37 /** |
| 38 * Adds element to the queue. |
| 39 * |
| 40 * The element will become the next to be removed by [removeFirst] |
| 41 * when all elements with higher priority have been removed. |
| 42 */ |
| 43 void add(E element); |
| 44 |
| 45 /** |
| 46 * Adds all [elements] to the queue. |
| 47 */ |
| 48 void addAll(Iterable<E> elements); |
| 49 |
| 50 /** |
38 * Returns the next element that will be returned by [removeFirst]. | 51 * Returns the next element that will be returned by [removeFirst]. |
39 * | 52 * |
40 * The element is not removed from the queue. | 53 * The element is not removed from the queue. |
41 * | 54 * |
42 * The queue must not be empty when this method is called. | 55 * The queue must not be empty when this method is called. |
43 */ | 56 */ |
44 E get first; | 57 E get first; |
45 | 58 |
46 /** | 59 /** |
47 * Removes and returns the element with the highest priority. | 60 * Removes and returns the element with the highest priority. |
48 * | 61 * |
49 * Repeatedly calling this method, without adding element in between, | 62 * Repeatedly calling this method, without adding element in between, |
50 * 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 |
51 * [comparison]. | 64 * [comparison]. |
52 * | 65 * |
53 * The queue must not be empty when this method is called. | 66 * The queue must not be empty when this method is called. |
54 */ | 67 */ |
55 E removeFirst(); | 68 E removeFirst(); |
56 | 69 |
57 /** | 70 /** |
58 * Removes an element that compares equal to [element] in the queue. | 71 * Removes an element that compares equal to [element] in the queue. |
59 * | 72 * |
60 * Returns true if an element is found and removed, | 73 * Returns true if an element is found and removed, |
61 * and false if not equal element is found. | 74 * and false if no equal element is found. |
62 */ | 75 */ |
63 bool remove(E element); | 76 bool remove(E element); |
64 | 77 |
65 /** | 78 /** |
66 * Removes all the elements from this queue and returns them. | 79 * Removes all the elements from this queue and returns them. |
67 * | 80 * |
68 * The returned iterable has no specified order. | 81 * The returned iterable has no specified order. |
69 */ | 82 */ |
70 Iterable<E> removeAll(); | 83 Iterable<E> removeAll(); |
71 | 84 |
(...skipping 302 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
374 * Called when the list is full. | 387 * Called when the list is full. |
375 */ | 388 */ |
376 void _grow() { | 389 void _grow() { |
377 int newCapacity = _queue.length * 2 + 1; | 390 int newCapacity = _queue.length * 2 + 1; |
378 if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY; | 391 if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY; |
379 List<E> newQueue = new List<E>(newCapacity); | 392 List<E> newQueue = new List<E>(newCapacity); |
380 newQueue.setRange(0, _length, _queue); | 393 newQueue.setRange(0, _length, _queue); |
381 _queue = newQueue; | 394 _queue = newQueue; |
382 } | 395 } |
383 } | 396 } |
OLD | NEW |