lib/src/priority_queue.dart - collection - Git at Google

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