com.aliasi.util
Class BoundedPriorityQueue<E>

java.lang.Object
  java.util.AbstractCollection<E>
      com.aliasi.util.BoundedPriorityQueue<E>

All Implemented Interfaces:

PriorityQueue<E>, Iterable<E>, Collection<E>

public class BoundedPriorityQueue<E>
extends AbstractCollection<E>
implements PriorityQueue<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.0

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) Conditionally add the specified element to this queue.
void	clear() Removes all elements from this queue.
boolean	isEmpty()
Iterator<E>	iterator() Returns an iterator over the elements in this bounded priority queue.
int	maxSize() Returns the maximum size allowed for this queue.
E	peek() Returns the largest element in the queue or null if the queue is empty.
E	pop() Remove and return the largest element in the queue or return null if the queue is empty.
boolean	remove(Object obj) Removes the specified object from the priority queue.
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.

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

addAll, contains, containsAll, equals, hashCode, removeAll, 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

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<E>

Overrides:

isEmpty in class AbstractCollection<E>

peek

public E peek()

Description copied from interface: PriorityQueue

Returns the largest element in the queue or null if the queue is empty.

Specified by:

peek in interface PriorityQueue<E>

Returns:

The largest element in the queue or null if the queue is empty.

pop

public E pop()

Description copied from interface: PriorityQueue

Remove and return the largest element in the queue or return null if the queue is empty.

Specified by:

pop in interface PriorityQueue<E>

Returns:

The largest element in the queue.

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>

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.

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

public boolean add(E o)

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.

Specified by:

add in interface Collection<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>

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 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 class AbstractCollection<E>

Returns:

Ordered iterator over the elements in this queue.