com.aliasi.util
Class BoundedPriorityQueue<E>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractSet<E>
          extended by com.aliasi.util.BoundedPriorityQueue<E>
Type Parameters:
E - the type of objects stored in the queue
All Implemented Interfaces:
PriorityQueue<E>, Iterable<E>, Collection<E>, Queue<E>, Set<E>, SortedSet<E>

public class BoundedPriorityQueue<E>
extends AbstractSet<E>
implements PriorityQueue<E>, Queue<E>, SortedSet<E>

A BoundedPriorityQueue implements a priority queue with an upper bound on the number of elements. If the queue is not full, added elements are always added. If the queue is full and the added element is greater than the smallest element in the queue, the smallest element is removed and the new element is added. If the queue is full and the added element is not greater than the smallest element in the queue, the new element is not added.

Bounded priority queues are the ideal data structure with which to implement n-best accumulators. A priority queue of bound n can find the n-best elements of a collection of m elements using O(n) space and O(m n log n) time.

Bounded priority queues may also be used as the basis of a search implementation with the bound implementing heuristic n-best pruning.

Because bounded priority queues require a comparator and a maximum size constraint, they do not comply with the recommendation in the Collection interface in that they neither implement a nullary constructor nor a constructor taking a single collection. Instead, they are constructed with a comparator and a maximum size bound.

Implementation Note: Priority queues are implemented on top of TreeSet with element wrappers to adapt object equality and the priority comparator. Because tree sets implement balanced trees, the priority queue operations, add(Object), pop() and peek(), all require O(log n) time where n is the size of the queue. A standard heap-based implementation of a queue implements peeks in constant time and adds and pops in O(log n) time. For our intended applications, pops are more likely than peeks and we need access to the worst element in the queue. An upside-down ordered heap implementation of priority queues implements bounded adds most efficiently, but requires up to O(n) for a pop or peek and an O(n log n) sort before iteration.

Since:
LingPipe2.0
Version:
3.8
Author:
Bob Carpenter

Constructor Summary
BoundedPriorityQueue(Comparator<? super E> comparator, int maxSize)
          Construct a bounded priority queue which uses the specified comparator to order elements and allows up to the specified maximum number of elements.
 
Method Summary
 boolean add(E o)
          Deprecated. Use offer(Object) instead. In the next release, this will be redefined to match the collection interface.
 void clear()
          Removes all elements from this queue.
 Comparator<? super E> comparator()
          Returns the comparator for this sorted set.
 E element()
          Returns the highest scoring object in this priority queue, throwing an exception if the queue is empty.
 E first()
          Deprecated. Use remove() instead.
 SortedSet<E> headSet(E toElement)
          Return the set of elements in this queue strictly less than the specified element according to the comparator for this queue.
 boolean isEmpty()
          Returns true if this bounded priority queue has no elements.
 Iterator<E> iterator()
          Returns an iterator over the elements in this bounded priority queue.
 E last()
          Returns the lowest scoring object in the priority queue, or null if the queue is empty.
 int maxSize()
          Returns the maximum size allowed for this queue.
 boolean offer(E e)
          Insert the specified element into the queue if possible.
 E peek()
          Returns the highest scoring object in the priority queue, or null if the queue is empty.
 E peekLast()
          Returns the lowest scoring object in the priority queue, or null if the queue is empty.
 E poll()
          Returns and removes the highest scoring element in this queue, or null if it is empty.
 E pop()
          Deprecated. Use poll() instead.
 E remove()
          Returns and removes the highest scoring element in this queue, throwing an exception if it is empty.
 boolean remove(Object obj)
          Removes the specified object from the priority queue.
 boolean removeAll(Collection<?> c)
           
 void setMaxSize(int maxSize)
          Sets the maximum size of this bounded priority queue to the specified maximum size.
 int size()
          Returns the current number of elements in this priority queue.
 SortedSet<E> subSet(E fromElement, E toElement)
          Return the set of elements in this queue greater than or equal to the specified lower bound and strictly less than the upper bound element according to the comparator for this queue.
 SortedSet<E> tailSet(E fromElement)
          Return the set of elements in this queue grearer than or equal to the specified element according to the comparator for this queue.
 
Methods inherited from class java.util.AbstractSet
equals, hashCode
 
Methods inherited from class java.util.AbstractCollection
addAll, contains, containsAll, retainAll, toArray, toArray, toString
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Set
addAll, contains, containsAll, equals, hashCode, retainAll, toArray, toArray
 

Constructor Detail

BoundedPriorityQueue

public BoundedPriorityQueue(Comparator<? super E> comparator,
                            int maxSize)
Construct a bounded priority queue which uses the specified comparator to order elements and allows up to the specified maximum number of elements.

Parameters:
comparator - Comparator to order elements.
maxSize - Maximum number of elements in the queue.
Throws:
IllegalArgumentException - If the maximum size is less than 1.
Method Detail

element

public E element()
Returns the highest scoring object in this priority queue, throwing an exception if the queue is empty.

Specified by:
element in interface Queue<E>
Returns:
The highest scoring object in this queue.
Throws:
NoSuchElementException - If the queue is empty.

poll

public E poll()
Returns and removes the highest scoring element in this queue, or null if it is empty.

This method differs from remove() only in that it returns null rather than throwing an exception for an empty queue.

Specified by:
poll in interface Queue<E>
Returns:
The highest scoring element in this queue, or null if it is empty.

offer

public boolean offer(E e)
Insert the specified element into the queue if possible. Insertion will be possible if the queue has not yet reached its capacity, or if the offered element is greater than the smallest element in the queue.

This method behaves the same way as add(Object).

Specified by:
offer in interface Queue<E>
Parameters:
e - Item offered.
Returns:
true if the item was inserted.

remove

public E remove()
Returns and removes the highest scoring element in this queue, throwing an exception if it is empty.

This method differs from poll() only in that it throws an exception for an empty queue instead of returning null.

Specified by:
remove in interface Queue<E>
Returns:
The highest scoring element in this queue.

isEmpty

public boolean isEmpty()
Returns true if this bounded priority queue has no elements.

Specified by:
isEmpty in interface Collection<E>
Specified by:
isEmpty in interface Set<E>
Overrides:
isEmpty in class AbstractCollection<E>
Returns:
true if this bounded priority queue has no elements.

peekLast

public E peekLast()
Returns the lowest scoring object in the priority queue, or null if the queue is empty.

The behavior with empty queues is what makes this method different than the sorted set method last().

Returns:
Lowest scoring object in the queue.

last

public E last()
Returns the lowest scoring object in the priority queue, or null if the queue is empty.

Specified by:
last in interface SortedSet<E>
Returns:
Lowest scoring object in the queue.

headSet

public SortedSet<E> headSet(E toElement)
Return the set of elements in this queue strictly less than the specified element according to the comparator for this queue.

In violation of the SortedSet interface specification, the result of this method is not a view onto this queue, but rather a static snapshot of the queue.

Specified by:
headSet in interface SortedSet<E>
Parameters:
toElement - Exclusive upper bound on returned elements.
Returns:
The set of elements less than the upper bound.
Throws:
ClassCastException - If the upper bound is not compatible with this queue's comparator.
NullPointerException - If the upper bound is null.

tailSet

public SortedSet<E> tailSet(E fromElement)
Return the set of elements in this queue grearer than or equal to the specified element according to the comparator for this queue.

In violation of the SortedSet interface specification, the result of this method is not a view onto this queue, but rather a static snapshot of the queue.

Specified by:
tailSet in interface SortedSet<E>
Parameters:
fromElement - Inclusive lower bound on returned elements.
Returns:
The set of elements greater than or equal to the lower bound.
Throws:
ClassCastException - If the lower bound is not compatible with this queue's comparator.
NullPointerException - If the lower bound is null.

subSet

public SortedSet<E> subSet(E fromElement,
                           E toElement)
Return the set of elements in this queue greater than or equal to the specified lower bound and strictly less than the upper bound element according to the comparator for this queue.

In violation of the SortedSet interface specification, the result of this method is not a view onto this queue, but rather a static snapshot of the queue.

Specified by:
subSet in interface SortedSet<E>
Parameters:
fromElement - Inclusive lower bound on returned elements.
toElement - Exclusive upper bound on returned elements.
Returns:
The set of elements greater than or equal to the lower bound.
Throws:
ClassCastException - If the lower bound is not compatible with this queue's comparator.
NullPointerException - If the lower bound is null.
IllegalArgumentException - If the lower bound is greater than the upper bound.

comparator

public Comparator<? super E> comparator()
Returns the comparator for this sorted set. The result will always be non-null.

Specified by:
comparator in interface SortedSet<E>
Returns:
This set's comparator.

first

@Deprecated
public E first()
Deprecated. Use remove() instead.

Returns the highest scoring object in the priority queue.

Specified by:
first in interface SortedSet<E>
Returns:
The highest scoring object in the queue.
Throws:
NoSuchElementException - If the queue is empty.

peek

public E peek()
Returns the highest scoring object in the priority queue, or null if the queue is empty.

This method is different than the sorted set method first(), which throws an exception if there is an empty queue.

Specified by:
peek in interface PriorityQueue<E>
Specified by:
peek in interface Queue<E>
Returns:
The highest scoring object in the queue.

pop

@Deprecated
public E pop()
Deprecated. Use poll() instead.

Return and remove the highest scoring element in this queue, or return null if it is empty.

Specified by:
pop in interface PriorityQueue<E>
Returns:
The highest scoring element in this queue, or null if the queue is empty.

remove

public boolean remove(Object obj)
Removes the specified object from the priority queue. Note that the object is removed using identity conditions defined by the comparator specified for this queue, not the natural equality or comparator.

Specified by:
remove in interface Collection<E>
Specified by:
remove in interface Set<E>
Overrides:
remove in class AbstractCollection<E>
Parameters:
obj - Object to remove from priority queue.
Returns:
true if the object was removed.
Throws:
ClassCastException - If the specified object is not compatible with this collection.

removeAll

public boolean removeAll(Collection<?> c)
Specified by:
removeAll in interface Collection<E>
Specified by:
removeAll in interface Set<E>
Overrides:
removeAll in class AbstractSet<E>

setMaxSize

public void setMaxSize(int maxSize)
Sets the maximum size of this bounded priority queue to the specified maximum size. If there are more than the specified number of elements in the queue, they are popped one by one until the queue is of the maximum size.

Note that this operation is not thread safe and should not be called concurrently with any other operations on this queue.

Parameters:
maxSize - New maximum size for this queue.

add

@Deprecated
public boolean add(E o)
Deprecated. Use offer(Object) instead. In the next release, this will be redefined to match the collection interface.

Conditionally add the specified element to this queue. If the queue is smaller than its maximum size, the element is added. If the queue is at its maximum size, the element is added only if it is larger than the smallest element, in which case the smallest element in the queue is removed.

The current implementation violates the contract of Collection by not throwing an exception if the item fails to add.

Specified by:
add in interface Collection<E>
Specified by:
add in interface Set<E>
Overrides:
add in class AbstractCollection<E>
Parameters:
o - Object to add to queue.
Returns:
true if the object was added.

clear

public void clear()
Removes all elements from this queue. The queue will be empty after this call.

Specified by:
clear in interface Collection<E>
Specified by:
clear in interface Set<E>
Overrides:
clear in class AbstractCollection<E>

size

public int size()
Returns the current number of elements in this priority queue.

Specified by:
size in interface Collection<E>
Specified by:
size in interface Set<E>
Specified by:
size in class AbstractCollection<E>
Returns:
Number of elements in this priority queue.

maxSize

public int maxSize()
Returns the maximum size allowed for this queue.

Returns:
The maximum size allowed for this queue.

iterator

public Iterator<E> iterator()
Returns an iterator over the elements in this bounded priority queue. The elements are returned in order. The returned iterator implements a fail-fast deletion in the same way as Java's collections framework.

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>
Returns:
Ordered iterator over the elements in this queue.