

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object java.util.AbstractCollection<E> java.util.AbstractSet<E> com.aliasi.util.BoundedPriorityQueue<E>
E
 the type of objects stored in the queuepublic class BoundedPriorityQueue<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 nbest 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 nbest 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 heapbased
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 upsidedown 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.
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 

public BoundedPriorityQueue(Comparator<? super E> comparator, int maxSize)
comparator
 Comparator to order elements.maxSize
 Maximum number of elements in the queue.
IllegalArgumentException
 If the maximum size is less than 1.Method Detail 

public E element()
element
in interface Queue<E>
NoSuchElementException
 If the queue is empty.public E poll()
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.
poll
in interface Queue<E>
null
if it is empty.public boolean offer(E e)
This method behaves the same way as add(Object)
.
offer
in interface Queue<E>
e
 Item offered.
true
if the item was inserted.public E remove()
This method differs from poll()
only in
that it throws an exception for an empty queue
instead of returning null
.
remove
in interface Queue<E>
public boolean isEmpty()
true
if this bounded priority
queue has no elements.
isEmpty
in interface Collection<E>
isEmpty
in interface Set<E>
isEmpty
in class AbstractCollection<E>
true
if this bounded priority
queue has no elements.public E peekLast()
null
if the queue is empty.
The behavior with empty queues is what makes this method
different than the sorted set method last()
.
public E last()
null
if the queue is empty.
last
in interface SortedSet<E>
public SortedSet<E> headSet(E toElement)
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.
headSet
in interface SortedSet<E>
toElement
 Exclusive upper bound on returned elements.
ClassCastException
 If the upper bound is not compatible with
this queue's comparator.
NullPointerException
 If the upper bound is null.public SortedSet<E> tailSet(E fromElement)
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.
tailSet
in interface SortedSet<E>
fromElement
 Inclusive lower bound on returned elements.
ClassCastException
 If the lower bound is not compatible with
this queue's comparator.
NullPointerException
 If the lower bound is null.public SortedSet<E> subSet(E fromElement, E toElement)
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.
subSet
in interface SortedSet<E>
fromElement
 Inclusive lower bound on returned elements.toElement
 Exclusive upper bound on returned elements.
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.public Comparator<? super E> comparator()
comparator
in interface SortedSet<E>
@Deprecated public E first()
remove()
instead.
first
in interface SortedSet<E>
NoSuchElementException
 If the queue is empty.public E peek()
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.
peek
in interface PriorityQueue<E>
peek
in interface Queue<E>
@Deprecated public E pop()
poll()
instead.
null
if it is empty.
pop
in interface PriorityQueue<E>
null
if the queue is empty.public boolean remove(Object obj)
remove
in interface Collection<E>
remove
in interface Set<E>
remove
in class AbstractCollection<E>
obj
 Object to remove from priority queue.
true
if the object was removed.
ClassCastException
 If the specified object is not
compatible with this collection.public boolean removeAll(Collection<?> c)
removeAll
in interface Collection<E>
removeAll
in interface Set<E>
removeAll
in class AbstractSet<E>
public void setMaxSize(int maxSize)
Note that this operation is not thread safe and should not be called concurrently with any other operations on this queue.
maxSize
 New maximum size for this queue.@Deprecated public boolean add(E o)
offer(Object)
instead. In the next
release, this will be redefined to match the collection
interface.
The current implementation violates the contract of
Collection
by not throwing an exception
if the item fails to add.
add
in interface Collection<E>
add
in interface Set<E>
add
in class AbstractCollection<E>
o
 Object to add to queue.
true
if the object was added.public void clear()
clear
in interface Collection<E>
clear
in interface Set<E>
clear
in class AbstractCollection<E>
public int size()
size
in interface Collection<E>
size
in interface Set<E>
size
in class AbstractCollection<E>
public int maxSize()
public Iterator<E> iterator()
iterator
in interface Iterable<E>
iterator
in interface Collection<E>
iterator
in interface Set<E>
iterator
in class AbstractCollection<E>


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 