com.aliasi.util
Class ShortPriorityQueue<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<E>
          com.aliasi.util.ShortPriorityQueue<E>

Type Parameters:

E - the type of objects stored in this queue

All Implemented Interfaces:

Iterable<E>, Collection<E>, Queue<E>, Set<E>, SortedSet<E>

public class ShortPriorityQueue<E>
extends AbstractSet<E>
implements Queue<E>, SortedSet<E>

A ShortPriorityQueue<E> is a length-bounded priority queue optimized for short lengths. Rather than maintaining tree or heap data structures, it keeps elements in an array and uses a simple bubble sort.

This class is different than BoundedPriorityQueue in that it does not attempt enforce the uniqueness required by the Set interface.

For large queues, use BoundedPriorityQueue. For large queues of Scored instances, use MinMaxHeap.

The head-, tail- and sub-set operations violate the sorted set interface's requirements that they be views onto the queue itself; instead, they are static snapshots.

Implementation Notes

The queue allocates an array for the elements of the maximum size specified in the constructor. Items are added using bubblesort, so that adding or removing elements may take up the current size's number of operations (that is, it's O(n) where n is the number of elements in the queue). The peek methods and first- and last-element methods are all constant time, as is the iterator's next method.

Since:

Lingpipe3.8

Version:

4.0.0

Author:

Bob Carpenter

Constructor Summary

ShortPriorityQueue(Comparator<? super E> comparator, int maxSize)
Construct a short priority queue that compares elements using the specified comparator with the specified maximum size.

Method Summary

void	clear() Removes all the elements from the priority queue.
Comparator<? super E>	comparator() Returns the comparator for this priority queue.
E	element() Returns the largest element in this queue according to the comparator, throwing an exception if the queue is empty.
E	first() Returns the largest element in the queue.
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 the queue is empty.
Iterator<E>	iterator() Returns an iterator over the elements in this queue.
E	last() Returns the smallest element in the queue.
int	maxSize() Returns the maximum size of this queue.
boolean	offer(E elt) Return true if the specified element may be added to the queue.
E	peek() Returns the largest element in this queue according to the comparator, or null if the queue is empty.
E	peekLast() Returns the smallest element in this queue according to the comparator, or null if the queue is empty.
E	poll() Removes and returns the largest element in this queue, or returns null if the queue is empty.
E	remove() Returns and removes the head of this queue, throwing an exception if it is empty.
boolean	remove(Object obj) Return true and remove the largest element in the queue equal to the specified object, or return false if the specified object is not in the queue.
int	size() Returns the current number of elements in the 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.
String	toString() Returns a string-based representation of the elements in this queue.

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

add, addAll, contains, 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.Queue

add

Methods inherited from interface java.util.Set

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

Constructor Detail

ShortPriorityQueue

public ShortPriorityQueue(Comparator<? super E> comparator,
                          int maxSize)

Construct a short priority queue that compares elements using the specified comparator with the specified maximum size. If adding an element would exceed the maximum size of the queue, the lowest ordered element is dropped.

Parameters:

comparator - Element comparator for this queue.

maxSize - Maximum number of elements in the queue.

Method Detail

maxSize

public int maxSize()

Returns the maximum size of this queue.

Returns:

The maximum size of this queue.

size

public int size()

Returns the current 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:

The size of the queue.

iterator

public Iterator<E> iterator()

Returns an iterator over the elements in this queue. The elements are returned from largest to smallest according to the comparator.

The iterator is not concurrent-modification safe, nor are there any heuristic checks to check for modifications and throw exceptions.

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:

The iterator over elements of this queue.

clear

public void clear()

Removes all the elements from the priority queue. This takes time proportional to the size of the queue in order to null out the references to elements in the queue so as not to leak memory.

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface Set<E>

Overrides:

clear in class AbstractCollection<E>

peek

public E peek()

Returns the largest element in this queue according to the comparator, or null if the queue is empty.

This method differs from element() only in that it throws an returns null if the queue is empty rather than throwing an exception.

Specified by:

peek in interface Queue<E>

Returns:

The largest element in the queue.

element

public E element()

Returns the largest element in this queue according to the comparator, throwing an exception if the queue is empty.

This method differs from peek() only in that it throws an exception if the queue is empty rather than returning null.

Specified by:

element in interface Queue<E>

Returns:

The largest element in this queue.

Throws:

NoSuchElementException - If the queue is empty.

peekLast

public E peekLast()

Returns the smallest element in this queue according to the comparator, or null if the queue is empty.

Returns:

The smallest element in the queue.

first

public E first()

Returns the largest element in the queue. Unlike peek(), this method throws an exception if the queue is empty.

Specified by:

first in interface SortedSet<E>

Returns:

The largest element in the queue.

Throws:

IllegalArgumentException - If the queue is empty.

last

public E last()

Returns the smallest element in the queue. Unlike peekLast(), this method throws an exception if the queue is empty.

Specified by:

last in interface SortedSet<E>

Returns:

The smallest element in the queue.

Throws:

IllegalArgumentException - If the queue is empty.

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.

comparator

public Comparator<? super E> comparator()

Returns the comparator for this priority queue.

Specified by:

comparator in interface SortedSet<E>

Returns:

The comparator for this priority queue.

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.

poll

public E poll()

Removes and returns the largest element in this queue, or returns null if the queue is empty.

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

Specified by:

poll in interface Queue<E>

Returns:

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

remove

public E remove()

Returns and removes the head of this queue, throwing an exception if it is empty.

This method differs from poll() only in that it throws an exception if the queue is empty rather than returning null.

Specified by:

remove in interface Queue<E>

Returns:

The head of this queue.

Throws:

NoSuchElementException - If the queue is emtpy.

isEmpty

public boolean isEmpty()

Returns true 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:

true if the queue is size zero.

offer

public boolean offer(E elt)

Return true if the specified element may be added to the queue. An element may be added to the queue if the queue is not full (its size is less than the maximum size), or if the smallest element in the queue is strictly smaller than the specified element according to this queue's comparator.

Specified by:

offer in interface Queue<E>

Parameters:

elt - Element to try to add to the queue.

Returns:

true if the element was added.

remove

public boolean remove(Object obj)

Return true and remove the largest element in the queue equal to the specified object, or return false if the specified object is not in the queue.

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.

Returns:

true if the object was in the queue and was removed.

toString

public String toString()

Returns a string-based representation of the elements in this queue.

Overrides:

toString in class AbstractCollection<E>

Returns:

A string-based representation of the elements in this queue.