Index: lib/src/priority_queue.dart |
diff --git a/lib/priority_queue.dart b/lib/src/priority_queue.dart |
similarity index 53% |
copy from lib/priority_queue.dart |
copy to lib/src/priority_queue.dart |
index 62724457a7c4c88e9792fa7a494b42c4cd6b3ce7..64fd84f03bea8a0dae8124a07f7b03ccf2a43bbf 100644 |
--- a/lib/priority_queue.dart |
+++ b/lib/src/priority_queue.dart |
@@ -2,185 +2,142 @@ |
// for details. All rights reserved. Use of this source code is governed by a |
// BSD-style license that can be found in the LICENSE file. |
-library dart.pkg.collection.priority_queue; |
+import "dart:collection"; |
-import "dart:collection" show SplayTreeSet; |
- |
-/** |
- * A priority queue is a priority based work-list of elements. |
- * |
- * The queue allows adding elements, and removing them again in priority order. |
- */ |
+/// A priority queue is a priority based work-list of elements. |
+/// |
+/// The queue allows adding elements, and removing them again in priority order. |
abstract class PriorityQueue<E> { |
- /** |
- * Creates an empty [PriorityQueue]. |
- * |
- * The created [PriorityQueue] is a plain [HeapPriorityQueue]. |
- * |
- * The [comparison] is a [Comparator] used to compare the priority of |
- * elements. An element that compares as less than another element has |
- * a higher priority. |
- * |
- * If [comparison] is omitted, it defaults to [Comparable.compare]. |
- */ |
+ /// Creates an empty [PriorityQueue]. |
+ /// |
+ /// The created [PriorityQueue] is a plain [HeapPriorityQueue]. |
+ /// |
+ /// The [comparison] is a [Comparator] used to compare the priority of |
+ /// elements. An element that compares as less than another element has |
+ /// a higher priority. |
+ /// |
+ /// If [comparison] is omitted, it defaults to [Comparable.compare]. |
factory PriorityQueue([int comparison(E e1, E e2)]) = HeapPriorityQueue<E>; |
- /** |
- * Number of elements in the queue. |
- */ |
+ /// Number of elements in the queue. |
int get length; |
- /** |
- * Whether the queue is empty. |
- */ |
+ /// Whether the queue is empty. |
bool get isEmpty; |
- /** |
- * Whether the queue has any elements. |
- */ |
+ /// Whether the queue has any elements. |
bool get isNotEmpty; |
- /** |
- * Checks if [object] is in the queue. |
- * |
- * Returns true if the element is found. |
- */ |
+ /// Checks if [object] is in the queue. |
+ /// |
+ /// Returns true if the element is found. |
bool contains(E object); |
- /** |
- * Adds element to the queue. |
- * |
- * The element will become the next to be removed by [removeFirst] |
- * when all elements with higher priority have been removed. |
- */ |
+ /// Adds element to the queue. |
+ /// |
+ /// The element will become the next to be removed by [removeFirst] |
+ /// when all elements with higher priority have been removed. |
void add(E element); |
- /** |
- * Adds all [elements] to the queue. |
- */ |
+ /// Adds all [elements] to the queue. |
void addAll(Iterable<E> elements); |
- /** |
- * Returns the next element that will be returned by [removeFirst]. |
- * |
- * The element is not removed from the queue. |
- * |
- * The queue must not be empty when this method is called. |
- */ |
+ /// Returns the next element that will be returned by [removeFirst]. |
+ /// |
+ /// The element is not removed from the queue. |
+ /// |
+ /// The queue must not be empty when this method is called. |
E get first; |
- /** |
- * Removes and returns the element with the highest priority. |
- * |
- * Repeatedly calling this method, without adding element in between, |
- * is guaranteed to return elements in non-decreasing order as, specified by |
- * [comparison]. |
- * |
- * The queue must not be empty when this method is called. |
- */ |
+ /// Removes and returns the element with the highest priority. |
+ /// |
+ /// Repeatedly calling this method, without adding element in between, |
+ /// is guaranteed to return elements in non-decreasing order as, specified by |
+ /// [comparison]. |
+ /// |
+ /// The queue must not be empty when this method is called. |
E removeFirst(); |
- /** |
- * Removes an element that compares equal to [element] in the queue. |
- * |
- * Returns true if an element is found and removed, |
- * and false if no equal element is found. |
- */ |
+ /// Removes an element that compares equal to [element] in the queue. |
+ /// |
+ /// Returns true if an element is found and removed, |
+ /// and false if no equal element is found. |
bool remove(E element); |
- /** |
- * Removes all the elements from this queue and returns them. |
- * |
- * The returned iterable has no specified order. |
- */ |
+ /// Removes all the elements from this queue and returns them. |
+ /// |
+ /// The returned iterable has no specified order. |
Iterable<E> removeAll(); |
- /** |
- * Removes all the elements from this queue. |
- */ |
+ /// Removes all the elements from this queue. |
void clear(); |
- /** |
- * Returns a list of the elements of this queue in priority order. |
- * |
- * The queue is not modified. |
- * |
- * The order is the order that the elements would be in if they were |
- * removed from this queue using [removeFirst]. |
- */ |
+ /// Returns a list of the elements of this queue in priority order. |
+ /// |
+ /// The queue is not modified. |
+ /// |
+ /// The order is the order that the elements would be in if they were |
+ /// removed from this queue using [removeFirst]. |
List<E> toList(); |
- /** |
- * Return a comparator based set using the comparator of this queue. |
- * |
- * The queue is not modified. |
- * |
- * The returned [Set] is currently a [SplayTreeSet], |
- * but this may change as other ordered sets are implemented. |
- * |
- * The set contains all the elements of this queue. |
- * If an element occurs more than once in the queue, |
- * the set will contain it only once. |
- */ |
+ /// Return a comparator based set using the comparator of this queue. |
+ /// |
+ /// The queue is not modified. |
+ /// |
+ /// The returned [Set] is currently a [SplayTreeSet], |
+ /// but this may change as other ordered sets are implemented. |
+ /// |
+ /// The set contains all the elements of this queue. |
+ /// If an element occurs more than once in the queue, |
+ /// the set will contain it only once. |
Set<E> toSet(); |
} |
-/** |
- * Heap based priority queue. |
- * |
- * The elements are kept in a heap structure, |
- * where the element with the highest priority is immediately accessible, |
- * and modifying a single element takes |
- * logarithmic time in the number of elements on average. |
- * |
- * * The [add] and [removeFirst] operations take amortized logarithmic time, |
- * O(log(n)), but may occasionally take linear time when growing the capacity |
- * of the heap. |
- * * The [addAll] operation works as doing repeated [add] operations. |
- * * The [first] getter takes constant time, O(1). |
- * * The [clear] and [removeAll] methods also take constant time, O(1). |
- * * The [contains] and [remove] operations may need to search the entire |
- * queue for the elements, taking O(n) time. |
- * * The [toList] operation effectively sorts the elements, taking O(n*log(n)) |
- * time. |
- * * The [toSet] operation effectively adds each element to the new set, taking |
- * an expected O(n*log(n)) time. |
- */ |
+/// Heap based priority queue. |
+/// |
+/// The elements are kept in a heap structure, |
+/// where the element with the highest priority is immediately accessible, |
+/// and modifying a single element takes |
+/// logarithmic time in the number of elements on average. |
+/// |
+/// * The [add] and [removeFirst] operations take amortized logarithmic time, |
+/// O(log(n)), but may occasionally take linear time when growing the capacity |
+/// of the heap. |
+/// * The [addAll] operation works as doing repeated [add] operations. |
+/// * The [first] getter takes constant time, O(1). |
+/// * The [clear] and [removeAll] methods also take constant time, O(1). |
+/// * The [contains] and [remove] operations may need to search the entire |
+/// queue for the elements, taking O(n) time. |
+/// * The [toList] operation effectively sorts the elements, taking O(n*log(n)) |
+/// time. |
+/// * The [toSet] operation effectively adds each element to the new set, taking |
+/// an expected O(n*log(n)) time. |
class HeapPriorityQueue<E> implements PriorityQueue<E> { |
- /** |
- * Initial capacity of a queue when created, or when added to after a [clear]. |
- * |
- * Number can be any positive value. Picking a size that gives a whole |
- * number of "tree levels" in the heap is only done for aesthetic reasons. |
- */ |
+ /// Initial capacity of a queue when created, or when added to after a |
+ /// [clear]. |
+ /// |
+ /// Number can be any positive value. Picking a size that gives a whole |
+ /// number of "tree levels" in the heap is only done for aesthetic reasons. |
static const int _INITIAL_CAPACITY = 7; |
- /** |
- * The comparison being used to compare the priority of elements. |
- */ |
+ /// The comparison being used to compare the priority of elements. |
final Comparator comparison; |
- /** |
- * List implementation of a heap. |
- */ |
+ /// List implementation of a heap. |
List<E> _queue = new List<E>(_INITIAL_CAPACITY); |
- /** |
- * Number of elements in queue. |
- * |
- * The heap is implemented in the first [_length] entries of [_queue]. |
- */ |
+ /// Number of elements in queue. |
+ /// |
+ /// The heap is implemented in the first [_length] entries of [_queue]. |
int _length = 0; |
- /** |
- * Create a new priority queue. |
- * |
- * The [comparison] is a [Comparator] used to compare the priority of |
- * elements. An element that compares as less than another element has |
- * a higher priority. |
- * |
- * If [comparison] is omitted, it defaults to [Comparable.compare]. |
- */ |
+ /// Create a new priority queue. |
+ /// |
+ /// The [comparison] is a [Comparator] used to compare the priority of |
+ /// elements. An element that compares as less than another element has |
+ /// a higher priority. |
+ /// |
+ /// If [comparison] is omitted, it defaults to [Comparable.compare]. |
HeapPriorityQueue([int comparison(E e1, E e2)]) |
: comparison = (comparison != null) ? comparison : Comparable.compare; |
@@ -262,30 +219,24 @@ class HeapPriorityQueue<E> implements PriorityQueue<E> { |
return set; |
} |
- /** |
- * Returns some representation of the queue. |
- * |
- * The format isn't significant, and may change in the future. |
- */ |
+ /// Returns some representation of the queue. |
+ /// |
+ /// The format isn't significant, and may change in the future. |
String toString() { |
return _queue.take(_length).toString(); |
} |
- /** |
- * Add element to the queue. |
- * |
- * Grows the capacity if the backing list is full. |
- */ |
+ /// Add element to the queue. |
+ /// |
+ /// Grows the capacity if the backing list is full. |
void _add(E element) { |
if (_length == _queue.length) _grow(); |
_bubbleUp(element, _length++); |
} |
- /** |
- * Find the index of an object in the heap. |
- * |
- * Returns -1 if the object is not found. |
- */ |
+ /// Find the index of an object in the heap. |
+ /// |
+ /// Returns -1 if the object is not found. |
int _locate(E object) { |
if (_length == 0) return -1; |
// Count positions from one instead of zero. This gives the numbers |
@@ -332,13 +283,11 @@ class HeapPriorityQueue<E> implements PriorityQueue<E> { |
return last; |
} |
- /** |
- * Place [element] in heap at [index] or above. |
- * |
- * Put element into the empty cell at `index`. |
- * While the `element` has higher priority than the |
- * parent, swap it with the parent. |
- */ |
+ /// Place [element] in heap at [index] or above. |
+ /// |
+ /// Put element into the empty cell at `index`. |
+ /// While the `element` has higher priority than the |
+ /// parent, swap it with the parent. |
void _bubbleUp(E element, int index) { |
while (index > 0) { |
int parentIndex = (index - 1) ~/ 2; |
@@ -350,13 +299,11 @@ class HeapPriorityQueue<E> implements PriorityQueue<E> { |
_queue[index] = element; |
} |
- /** |
- * Place [element] in heap at [index] or above. |
- * |
- * Put element into the empty cell at `index`. |
- * While the `element` has lower priority than either child, |
- * swap it with the highest priority child. |
- */ |
+ /// Place [element] in heap at [index] or above. |
+ /// |
+ /// Put element into the empty cell at `index`. |
+ /// While the `element` has lower priority than either child, |
+ /// swap it with the highest priority child. |
void _bubbleDown(E element, int index) { |
int rightChildIndex = index * 2 + 2; |
while (rightChildIndex < _length) { |
@@ -394,11 +341,9 @@ class HeapPriorityQueue<E> implements PriorityQueue<E> { |
_queue[index] = element; |
} |
- /** |
- * Grows the capacity of the list holding the heap. |
- * |
- * Called when the list is full. |
- */ |
+ /// Grows the capacity of the list holding the heap. |
+ /// |
+ /// Called when the list is full. |
void _grow() { |
int newCapacity = _queue.length * 2 + 1; |
if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY; |