org.openimaj.util.queue

Class BoundedPriorityQueue<T>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<E>

java.util.PriorityQueue<T>

org.openimaj.util.queue.InvertedPriorityQueue<T>

org.openimaj.util.queue.BoundedPriorityQueue<T>

Type Parameters:

T -

All Implemented Interfaces:

Serializable, Iterable<T>, Collection<T>, Queue<T>

public class BoundedPriorityQueue<T>
extends InvertedPriorityQueue<T>

A bounded priority queue based on an InvertedPriorityQueue. Insertions to the queue are worst-case O(log(N)) and O(1) if the insertion is rejected. peek() and poll() are very inefficient (O(N)) as they have to search for the head of the queue. peekTail() and pollTail() have complexity O(1) and O(log(N)) respectively.

This implementation is ideally suited for storing the top-N items of a process; that is, where items are constantly added, but not removed very often.

The class contains a number of utility methods to get a sorted copy of the queue.

The Iterator provided in method PriorityQueue.iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
BoundedPriorityQueue(int maxSize) Creates a BoundedPriorityQueue with the specified initial capacity that orders its elements according to their inverse natural ordering.
BoundedPriorityQueue(int maxSize, Comparator<? super T> comparator) Creates a BoundedPriorityQueue with the specified initial capacity that orders its elements according to the inverse of the specified comparator.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	isFull() Is the BoundedPriorityQueue full?
boolean	offer(T e)
T	offerItem(T item) Inserts the specified element into this priority queue if possible.
T	peek() Peak at the head of the queue.
T	peekTail() Retrieves, but does not remove, the tail of this queue, or returns null if this queue is empty.
T	poll() Poll the head of the queue.
T	pollTail() Retrieves and remove the tail of this queue, or returns null if this queue is empty.
Object[]	toOrderedArray() Returns an array containing all of the elements in this queue.
T[]	toOrderedArray(T[] a) Returns a sorted array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.
Object[]	toOrderedArrayDestructive() Returns an array containing all of the elements in this queue.
T[]	toOrderedArrayDestructive(T[] a) Returns a sorted array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.
List<T>	toOrderedList() Create a new list with the contents of the queue and sort them into their natural order, or the order specified by the Comparator used in constructing the queue.
List<T>	toOrderedListDestructive() Create a new list with the contents of the queue with the elements inserted in their natural order, or the order specified by the Comparator used in constructing the queue.

Methods inherited from class org.openimaj.util.queue.InvertedPriorityQueue

originalComparator

Methods inherited from class java.util.PriorityQueue

add, clear, comparator, contains, iterator, remove, size, toArray, toArray

Methods inherited from class java.util.AbstractQueue

addAll, element, remove

Methods inherited from class java.util.AbstractCollection

containsAll, isEmpty, removeAll, retainAll, 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

containsAll, equals, hashCode, isEmpty, removeAll, retainAll

Constructor Detail

BoundedPriorityQueue

public BoundedPriorityQueue(int maxSize,
                    Comparator<? super T> comparator)

Creates a BoundedPriorityQueue with the specified initial capacity that orders its elements according to the inverse of the specified comparator.

Parameters:

maxSize - the maximum number of elements in this priority queue

comparator - the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used. Internally, the comparator is inverted to reverse its meaning.

Throws:

IllegalArgumentException - if initialCapacity is less than 1

BoundedPriorityQueue

public BoundedPriorityQueue(int maxSize)

Creates a BoundedPriorityQueue with the specified initial capacity that orders its elements according to their inverse natural ordering.

Parameters:

maxSize - the maximum number of elements in this priority queue

Throws:

IllegalArgumentException - if initialCapacity is less than 1

Method Detail

offer

public boolean offer(T e)

Specified by:

offer in interface Queue<T>

Overrides:

offer in class PriorityQueue<T>

peek

public T peek()

Peak at the head of the queue. To maintain the semantics of a PriorityQueue, this is the least element with respect to the specified ordering.

Peeking at the head is an expensive (O(n)) operation as the BoundedPriorityQueue only maintains the tail for fast insertions.

Specified by:

peek in interface Queue<T>

Overrides:

peek in class PriorityQueue<T>

See Also:

PriorityQueue.peek()

poll

public T poll()

Poll the head of the queue. To maintain the semantics of a PriorityQueue, this is the least element with respect to the specified ordering.

Polling the head is an expensive (O(n)) operation as the BoundedPriorityQueue only maintains the tail for fast insertions.

Specified by:

poll in interface Queue<T>

Overrides:

poll in class PriorityQueue<T>

See Also:

PriorityQueue.poll()

toOrderedList

public List<T> toOrderedList()

Create a new list with the contents of the queue and sort them into their natural order, or the order specified by the Comparator used in constructing the queue. The list constructed in O(N) time, and the sorting takes O(log(N)) time.

Returns:

a sorted list containing contents of the queue.

toOrderedArray

public Object[] toOrderedArray()

Returns an array containing all of the elements in this queue. The elements are in sorted into their natural order, or the order specified by the Comparator used in constructing the queue. The array is constructed in O(N) time, and the sorting takes O(log(N)) time.

The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Returns:

a sorted array containing all of the elements in this queue

toOrderedArray

public T[] toOrderedArray(T[] a)

Returns a sorted array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.

The elements are in sorted into their natural order, or the order specified by the Comparator used in constructing the queue. The array is constructed in O(N) time, and the sorting takes O(log(N)) time.

If the queue fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this queue.

If the queue fits in the specified array with room to spare (i.e., the array has more elements than the queue), the element in the array immediately following the end of the collection is set to null.

Like the PriorityQueue.toArray() method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

Suppose x is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of String:

 String[] y = x.toArray(new String[0]);
 

Note that toArray(new Object[0]) is identical in function to toArray().

Parameters:

a - the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.

Returns:

an array containing all of the elements in this queue

Throws:

ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue

NullPointerException - if the specified array is null

toOrderedListDestructive

public List<T> toOrderedListDestructive()

Create a new list with the contents of the queue with the elements inserted in their natural order, or the order specified by the Comparator used in constructing the queue.

This method destroys the queue; after the operation completes, the queue will be empty. The operation completes in O(Nlog(N)) time.

Returns:

a sorted list containing contents of the queue.

toOrderedArrayDestructive

public Object[] toOrderedArrayDestructive()

Returns an array containing all of the elements in this queue. The elements are in sorted into their natural order, or the order specified by the Comparator used in constructing the queue.

This method destroys the queue; after the operation completes, the queue will be empty. The operation completes in O(Nlog(N)) time.

The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Returns:

a sorted array containing all of the elements in this queue

toOrderedArrayDestructive

public T[] toOrderedArrayDestructive(T[] a)

Returns a sorted array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.

The elements are in sorted into their natural order, or the order specified by the Comparator used in constructing the queue.

This method destroys the queue; after the operation completes, the queue will be empty. The operation completes in O(Nlog(N)) time.

If the queue fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this queue.

If the queue fits in the specified array with room to spare (i.e., the array has more elements than the queue), the element in the array immediately following the end of the collection is set to null.

Like the PriorityQueue.toArray() method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

Suppose x is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of String:

 String[] y = x.toArray(new String[0]);
 

Note that toArray(new Object[0]) is identical in function to toArray().

Parameters:

a - the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.

Returns:

an array containing all of the elements in this queue

Throws:

ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue

NullPointerException - if the specified array is null

peekTail

public T peekTail()

Retrieves, but does not remove, the tail of this queue, or returns null if this queue is empty.

This operation is performed in O(1) time.

Returns:

the tail of this queue, or null if this queue is empty.

pollTail

public T pollTail()

Retrieves and remove the tail of this queue, or returns null if this queue is empty.

This operation is performed in O(1) time.

Returns:

the tail of this queue, or null if this queue is empty.

offerItem

public T offerItem(T item)

Inserts the specified element into this priority queue if possible. This method is the same as calling PriorityQueue.add(Object) or offer(Object), but returns a different value depending on the queue size and whether the item was successfully added.

Specifically, if the item was not added, then it is returned. If the item was added to a queue that has not reached its capacity, then null is returned. If the item was added to a queue at capacity, then the item that was removed to make space is returned.

Parameters:

item - The item to attempt to add.

Returns:

The item if it couldn't be added to the queue; null if the item was added without needing to remove anything; or the removed item if space had to be made to add the item.

Throws:

ClassCastException - if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering

NullPointerException - if the specified element is null

isFull

public boolean isFull()

Is the BoundedPriorityQueue full?

Returns:

true if full; false otherwise