edu.stanford.nlp.util
Class BinaryHeapPriorityQueue<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<E>
          edu.stanford.nlp.util.BinaryHeapPriorityQueue<E>

All Implemented Interfaces:

PriorityQueue<E>, Iterable<E>, Collection<E>, Iterator<E>, Set<E>

public class BinaryHeapPriorityQueue<E>
extends AbstractSet<E>
implements PriorityQueue<E>, Iterator<E>

PriorityQueue with explicit double priority values. Larger doubles are higher priorities. BinaryHeap-backed.

Author:

Dan Klein, Christopher Manning For each entry, uses ~ 24 (entry) + 16? (Map.Entry) + 4 (List entry) = 44 bytes?

Constructor Summary

BinaryHeapPriorityQueue()

BinaryHeapPriorityQueue(MapFactory mapFactory)

Method Summary

boolean	add(E key) Adds an object to the queue with the minimum priority (Double.NEGATIVE_INFINITY).
boolean	add(E key, double priority) Convenience method for if you want to pretend relaxPriority doesn't exist, or if you really want add's return conditions.
boolean	changePriority(E key, double priority) Changes a priority, either up or down, adding the key it if it wasn't there already.
void	clear() Clears the queue.
boolean	contains(Object key) Returns whether the queue contains the given key.
boolean	decreasePriority(E key, double priority) Demotes a key in the queue, adding it if it wasn't there already.
BinaryHeapPriorityQueue	deepCopy()
BinaryHeapPriorityQueue	deepCopy(MapFactory mapFactory)
E	getFirst() Finds the object with the highest priority and returns it, without modifying the queue.
Object	getObject(Object key) Searches for the object in the queue and returns it.
double	getPriority(Object key) Get the priority of a key -- if the key is not in the queue, Double.NEGATIVE_INFINITY is returned.
boolean	hasNext()
boolean	isEmpty() Checks if the queue is empty.
Iterator	iterator()
static void	main(String[] args)
E	next()
boolean	relaxPriority(E key, double priority) Promotes a key in the queue, adding it if it wasn't there already.
void	remove()
boolean	remove(Object key)
E	removeFirst() Finds the object with the highest priority, removes it, and returns it.
int	size() Get the number of elements in the queue.
List	toSortedList()
String	toString()

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

addAll, containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

Constructor Detail

BinaryHeapPriorityQueue

public BinaryHeapPriorityQueue()

BinaryHeapPriorityQueue

public BinaryHeapPriorityQueue(MapFactory mapFactory)

Method Detail

hasNext

public boolean hasNext()

Specified by:

hasNext in interface Iterator<E>

next

public E next()

Specified by:

next in interface Iterator<E>

remove

public void remove()

Specified by:

remove in interface Iterator<E>

removeFirst

public E removeFirst()

Finds the object with the highest priority, removes it, and returns it.

Specified by:

removeFirst in interface PriorityQueue<E>

Returns:

the object with highest priority

getFirst

public E getFirst()

Finds the object with the highest priority and returns it, without modifying the queue.

Specified by:

getFirst in interface PriorityQueue<E>

Returns:

the object with minimum key

getObject

public Object getObject(Object key)

Searches for the object in the queue and returns it. May be useful if you can create a new object that is .equals() to an object in the queue but is not actually identical, or if you want to modify an object that is in the queue.

Returns:

null if the object is not in the queue, otherwise returns the object.

getPriority

public double getPriority(Object key)

Get the priority of a key -- if the key is not in the queue, Double.NEGATIVE_INFINITY is returned.

Specified by:

getPriority in interface PriorityQueue<E>

Parameters:

key -

Returns:

add

public boolean add(E key)

Adds an object to the queue with the minimum priority (Double.NEGATIVE_INFINITY). If the object is already in the queue with worse priority, this does nothing. If the object is already present, with better priority, it will NOT cause an a decreasePriority.

Specified by:

add in interface Collection<E>

Specified by:

add in interface Set<E>

Overrides:

add in class AbstractCollection<E>

Parameters:

key - an Object value

Returns:

whether the key was present before

add

public boolean add(E key,
                   double priority)

Convenience method for if you want to pretend relaxPriority doesn't exist, or if you really want add's return conditions.

Specified by:

add in interface PriorityQueue<E>

Returns:

true if this set did not already contain the specified element.

remove

public boolean remove(Object key)

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface Set<E>

Overrides:

remove in class AbstractCollection<E>

relaxPriority

public boolean relaxPriority(E key,
                             double priority)

Promotes a key in the queue, adding it if it wasn't there already. If the specified priority is worse than the current priority, nothing happens. Faster than add if you don't care about whether the key is new.

Specified by:

relaxPriority in interface PriorityQueue<E>

Parameters:

key - an Object value

Returns:

whether the priority actually improved.

decreasePriority

public boolean decreasePriority(E key,
                                double priority)

Demotes a key in the queue, adding it if it wasn't there already. If the specified priority is better than the current priority, nothing happens. If you decrease the priority on a non-present key, it will get added, but at it's old implicit priority of Double.NEGATIVE_INFINITY.

Parameters:

key - an Object value

Returns:

whether the priority actually improved.

changePriority

public boolean changePriority(E key,
                              double priority)

Changes a priority, either up or down, adding the key it if it wasn't there already.

Specified by:

changePriority in interface PriorityQueue<E>

Parameters:

key - an Object value

Returns:

whether the priority actually changed.

isEmpty

public boolean isEmpty()

Checks if the queue is empty.

Specified by:

isEmpty in interface Collection<E>

Specified by:

isEmpty in interface Set<E>

Overrides:

isEmpty in class AbstractCollection<E>

Returns:

a boolean value

size

public int size()

Get the number of elements in the queue.

Specified by:

size in interface Collection<E>

Specified by:

size in interface Set<E>

Specified by:

size in class AbstractCollection<E>

Returns:

queue size

contains

public boolean contains(Object key)

Returns whether the queue contains the given key.

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface Set<E>

Overrides:

contains in class AbstractCollection<E>

toSortedList

public List toSortedList()

Specified by:

toSortedList in interface PriorityQueue<E>

deepCopy

public BinaryHeapPriorityQueue deepCopy(MapFactory mapFactory)

deepCopy

public BinaryHeapPriorityQueue deepCopy()

iterator

public Iterator iterator()

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Set<E>

Specified by:

iterator in class AbstractCollection<E>

clear

public void clear()

Clears the queue.

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface Set<E>

Overrides:

clear in class AbstractCollection<E>

toString

public String toString()

Overrides:

toString in class AbstractCollection<E>

main

public static void main(String[] args)