// Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | |

// 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. | |

import "dart:collection"; | |

import "utils.dart"; | |

/// 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]. If this | |

/// is the case, `E` must implement [Comparable], and this is checked at | |

/// runtime for every comparison. | |

factory PriorityQueue([int comparison(E e1, E e2)]) = HeapPriorityQueue<E>; | |

/// Number of elements in the queue. | |

int get length; | |

/// Whether the queue is empty. | |

bool get isEmpty; | |

/// Whether the queue has any elements. | |

bool get isNotEmpty; | |

/// 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. | |

void add(E element); | |

/// 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. | |

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. | |

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. | |

bool remove(E element); | |

/// 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. | |

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]. | |

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. | |

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. | |

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. | |

static const int _INITIAL_CAPACITY = 7; | |

/// The comparison being used to compare the priority of elements. | |

final Comparator<E> comparison; | |

/// 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]. | |

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]. If this | |

/// is the case, `E` must implement [Comparable], and this is checked at | |

/// runtime for every comparison. | |

HeapPriorityQueue([int comparison(E e1, E e2)]) | |

: comparison = comparison ?? defaultCompare/*<E>*/(); | |

void add(E element) { | |

_add(element); | |

} | |

void addAll(Iterable<E> elements) { | |

for (E element in elements) { | |

_add(element); | |

} | |

} | |

void clear() { | |

_queue = const []; | |

_length = 0; | |

} | |

bool contains(E object) { | |

return _locate(object) >= 0; | |

} | |

E get first { | |

if (_length == 0) throw new StateError("No such element"); | |

return _queue[0]; | |

} | |

bool get isEmpty => _length == 0; | |

bool get isNotEmpty => _length != 0; | |

int get length => _length; | |

bool remove(E element) { | |

int index = _locate(element); | |

if (index < 0) return false; | |

E last = _removeLast(); | |

if (index < _length) { | |

int comp = comparison(last, element); | |

if (comp <= 0) { | |

_bubbleUp(last, index); | |

} else { | |

_bubbleDown(last, index); | |

} | |

} | |

return true; | |

} | |

Iterable<E> removeAll() { | |

List<E> result = _queue; | |

int length = _length; | |

_queue = const []; | |

_length = 0; | |

return result.take(length); | |

} | |

E removeFirst() { | |

if (_length == 0) throw new StateError("No such element"); | |

E result = _queue[0]; | |

E last = _removeLast(); | |

if (_length > 0) { | |

_bubbleDown(last, 0); | |

} | |

return result; | |

} | |

List<E> toList() { | |

List<E> list = new List<E>()..length = _length; | |

list.setRange(0, _length, _queue); | |

list.sort(comparison); | |

return list; | |

} | |

Set<E> toSet() { | |

Set<E> set = new SplayTreeSet<E>(comparison); | |

for (int i = 0; i < _length; i++) { | |

set.add(_queue[i]); | |

} | |

return set; | |

} | |

/// 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. | |

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. | |

int _locate(E object) { | |

if (_length == 0) return -1; | |

// Count positions from one instead of zero. This gives the numbers | |

// some nice properties. For example, all right children are odd, | |

// their left sibling is even, and the parent is found by shifting | |

// right by one. | |

// Valid range for position is [1.._length], inclusive. | |

int position = 1; | |

// Pre-order depth first search, omit child nodes if the current | |

// node has lower priority than [object], because all nodes lower | |

// in the heap will also have lower priority. | |

do { | |

int index = position - 1; | |

E element = _queue[index]; | |

int comp = comparison(element, object); | |

if (comp == 0) return index; | |

if (comp < 0) { | |

// Element may be in subtree. | |

// Continue with the left child, if it is there. | |

int leftChildPosition = position * 2; | |

if (leftChildPosition <= _length) { | |

position = leftChildPosition; | |

continue; | |

} | |

} | |

// Find the next right sibling or right ancestor sibling. | |

do { | |

while (position.isOdd) { | |

// While position is a right child, go to the parent. | |

position >>= 1; | |

} | |

// Then go to the right sibling of the left-child. | |

position += 1; | |

} while (position > _length); // Happens if last element is a left child. | |

} while (position != 1); // At root again. Happens for right-most element. | |

return -1; | |

} | |

E _removeLast() { | |

int newLength = _length - 1; | |

E last = _queue[newLength]; | |

_queue[newLength] = null; | |

_length = newLength; | |

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. | |

void _bubbleUp(E element, int index) { | |

while (index > 0) { | |

int parentIndex = (index - 1) ~/ 2; | |

E parent = _queue[parentIndex]; | |

if (comparison(element, parent) > 0) break; | |

_queue[index] = parent; | |

index = parentIndex; | |

} | |

_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. | |

void _bubbleDown(E element, int index) { | |

int rightChildIndex = index * 2 + 2; | |

while (rightChildIndex < _length) { | |

int leftChildIndex = rightChildIndex - 1; | |

E leftChild = _queue[leftChildIndex]; | |

E rightChild = _queue[rightChildIndex]; | |

int comp = comparison(leftChild, rightChild); | |

int minChildIndex; | |

E minChild; | |

if (comp < 0) { | |

minChild = leftChild; | |

minChildIndex = leftChildIndex; | |

} else { | |

minChild = rightChild; | |

minChildIndex = rightChildIndex; | |

} | |

comp = comparison(element, minChild); | |

if (comp <= 0) { | |

_queue[index] = element; | |

return; | |

} | |

_queue[index] = minChild; | |

index = minChildIndex; | |

rightChildIndex = index * 2 + 2; | |

} | |

int leftChildIndex = rightChildIndex - 1; | |

if (leftChildIndex < _length) { | |

E child = _queue[leftChildIndex]; | |

int comp = comparison(element, child); | |

if (comp > 0) { | |

_queue[index] = child; | |

index = leftChildIndex; | |

} | |

} | |

_queue[index] = element; | |

} | |

/// 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; | |

List<E> newQueue = new List<E>(newCapacity); | |

newQueue.setRange(0, _length, _queue); | |

_queue = newQueue; | |

} | |

} |