An unbounded priority queue based on a binary heap algorithm. More...

#include <src/main/decaf/util/PriorityQueue.h>

Inheritance diagram for decaf::util::PriorityQueue< E >:

[legend]

Data Structures

class ConstPriorityQueueIterator

class PriorityQueueIterator

Public Member Functions

PriorityQueue ()

Creates a Priority Queue with the default initial capacity.

PriorityQueue (int initialCapacity)

Creates a Priority Queue with the capacity value supplied.

PriorityQueue (int initialCapacity, Comparator< E > *comparator)

Creates a Priority Queue with the default initial capacity.

PriorityQueue (const Collection< E > &source)

Creates a PriorityQueue containing the elements in the specified Collection.

PriorityQueue (const PriorityQueue< E > &source)

Creates a PriorityQueue containing the elements in the specified priority queue.

virtual ~PriorityQueue ()

PriorityQueue< E > & operator= (const Collection< E > &source)

Assignment operator, assign another Collection to this one.

PriorityQueue< E > & operator= (const PriorityQueue< E > &source)

Assignment operator, assign another PriorityQueue to this one.

virtual decaf::util::Iterator
< E > * iterator ()

virtual decaf::util::Iterator
< E > * iterator () const

virtual int size () const

Returns the number of elements in this collection.

virtual void clear ()

Removes all of the elements from this collection (optional operation).The collection will be empty after this method returns.This implementation iterates over this collection, removing each element using the Iterator.remove operation. Most implementations will probably choose to override this method for efficiency.Note that this implementation will throw an UnsupportedOperationException if the iterator returned by this collection's iterator method does not implement the remove method and this collection is non-empty.

Exceptions:

UnsupportedOperationException if the clear operation is not supported by this collection

This implementation repeatedly invokes poll until it returns false.

virtual bool offer (const E &value)

Inserts the specified element into the queue provided that the condition allows such an operation.

virtual bool poll (E &result)

Gets and removes the element in the head of the queue.

virtual bool peek (E &result) const

Gets but not removes the element in the head of the queue.

virtual E remove ()

Gets and removes the element in the head of the queue.Throws a NoSuchElementException if there is no element in the queue.

Returns:: the element in the head of the queue.

Exceptions:

NoSuchElementException if there is no element in the queue.

This implementation returns the result of poll unless the queue is empty.

virtual bool remove (const E &value)

Removes a single instance of the specified element from the collection.More formally, removes an element e such that (value == NULL ? e == NULL : value == e), if this collection contains one or more such elements. Returns true if this collection contained the specified element (or equivalently, if this collection changed as a result of the call).

Parameters:

value The reference to the element to remove from this Collection.

Returns:: true if the collection was changed, false otherwise.

Exceptions:

UnsupportedOperationExceptio	if this is an unmodifiable collection.
NullPointerException	if the Collection is a container of pointers and does not allow NULL values.

This implementation iterates over the collection looking for the specified element. If it finds the element, it removes the element from the collection using the iterator's remove method.Note that this implementation throws an UnsupportedOperationException if the iterator returned by this collection's iterator method does not implement the remove method and this collection contains the specified object.

virtual bool add (const E &value)

Returns true if this collection changed as a result of the call.(Returns false if this collection does not permit duplicates and already contains the specified element.)Collections that support this operation may place limitations on what elements may be added to this collection. In particular, some collections will refuse to add null elements, and others will impose restrictions on the type of elements that may be added. Collection classes should clearly specify in their documentation any restrictions on what elements may be added.If a collection refuses to add a particular element for any reason other than that it already contains the element, it must throw an exception (rather than returning false). This preserves the invariant that a collection always contains the specified element after this call returns.For non-pointer values, i.e. class instances or string's the object will be copied into the collection, thus the object must support being copied, must not hide the copy constructor and assignment operator.

Parameters:

value The reference to the element to add to this Collection.

Returns:: true if the element was added to this Collection.

Exceptions:

UnsupportedOperationExceptio	if this is an unmodifiable collection.
NullPointerException	if the Collection is a container of pointers and does not allow NULL values.
IllegalArgumentException	if some property of the element prevents it from being added to this collection
IllegalStateException	if the element cannot be added at this time due to insertion restrictions.

This implementation returns true if offer succeeds, else throws an IllegalStateException.

decaf::lang::Pointer
< Comparator< E > > comparator () const

obtains a Copy of the Pointer instance that this PriorityQueue is using to compare the elements in the queue with.

Friends

class PriorityQueueIterator

Detailed Description

template<typename E>
class decaf::util::PriorityQueue< E >

An unbounded priority queue based on a binary heap algorithm.

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided to one of the constructors that accepts Comparators. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in a compiler error).

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays::sort( pq.toArray() ).

Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueue class.

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

Since:: 1.0

Constructor & Destructor Documentation

template<typename E>

decaf::util::PriorityQueue< E >::PriorityQueue ( ) [inline]

Creates a Priority Queue with the default initial capacity.

template<typename E>

decaf::util::PriorityQueue< E >::PriorityQueue ( int initialCapacity ) [inline]

Creates a Priority Queue with the capacity value supplied.

Parameters:

initialCapacity The initial number of elements allocated to this PriorityQueue.

template<typename E>

decaf::util::PriorityQueue< E >::PriorityQueue	(	int	initialCapacity,
		Comparator< E > *	comparator
	)		`[inline]`

Creates a Priority Queue with the default initial capacity.

This new PriorityQueue takes ownership of the passed Comparator instance and uses that to determine the ordering of the elements in the Queue.

Parameters:

initialCapacity	The initial number of elements allocated to this PriorityQueue.
comparator	The Comparator instance to use in sorting the elements in the Queue.

Exceptions:

NullPointerException if the passed Comparator is NULL.

template<typename E>

decaf::util::PriorityQueue< E >::PriorityQueue ( const Collection< E > & source ) [inline]

Creates a PriorityQueue containing the elements in the specified Collection.

Parameters:

source the Collection whose elements are to be placed into this priority queue

template<typename E>

decaf::util::PriorityQueue< E >::PriorityQueue ( const PriorityQueue< E > & source ) [inline]

Creates a PriorityQueue containing the elements in the specified priority queue.

This priority queue will be ordered according to the same ordering as the given priority queue.

Parameters:

source the priority queue whose elements are to be placed into this priority queue

template<typename E>

virtual decaf::util::PriorityQueue< E >::~PriorityQueue ( ) [inline, virtual]

Member Function Documentation

template<typename E>

virtual bool decaf::util::PriorityQueue< E >::add ( const E & value ) [inline, virtual]

Returns true if this collection changed as a result of the call.(Returns false if this collection does not permit duplicates and already contains the specified element.)Collections that support this operation may place limitations on what elements may be added to this collection. In particular, some collections will refuse to add null elements, and others will impose restrictions on the type of elements that may be added. Collection classes should clearly specify in their documentation any restrictions on what elements may be added.If a collection refuses to add a particular element for any reason other than that it already contains the element, it must throw an exception (rather than returning false). This preserves the invariant that a collection always contains the specified element after this call returns.For non-pointer values, i.e. class instances or string's the object will be copied into the collection, thus the object must support being copied, must not hide the copy constructor and assignment operator.

Parameters:

value The reference to the element to add to this Collection.

Returns:: true if the element was added to this Collection.

Exceptions:

UnsupportedOperationExceptio	if this is an unmodifiable collection.
NullPointerException	if the Collection is a container of pointers and does not allow NULL values.
IllegalArgumentException	if some property of the element prevents it from being added to this collection
IllegalStateException	if the element cannot be added at this time due to insertion restrictions.

This implementation returns true if offer succeeds, else throws an IllegalStateException.

Reimplemented from decaf::util::AbstractQueue< E >.

References DECAF_CATCH_EXCEPTION_CONVERT, DECAF_CATCH_RETHROW, DECAF_CATCHALL_THROW, and decaf::util::PriorityQueue< E >::offer().

template<typename E>

virtual void decaf::util::PriorityQueue< E >::clear ( ) [inline, virtual]

Removes all of the elements from this collection (optional operation).The collection will be empty after this method returns.This implementation iterates over this collection, removing each element using the Iterator.remove operation. Most implementations will probably choose to override this method for efficiency.Note that this implementation will throw an UnsupportedOperationException if the iterator returned by this collection's iterator method does not implement the remove method and this collection is non-empty.

Exceptions:

UnsupportedOperationException if the clear operation is not supported by this collection

This implementation repeatedly invokes poll until it returns false.

Reimplemented from decaf::util::AbstractQueue< E >.

template<typename E>

decaf::lang::Pointer< Comparator<E> > decaf::util::PriorityQueue< E >::comparator ( ) const [inline]

obtains a Copy of the Pointer instance that this PriorityQueue is using to compare the elements in the queue with.

The returned value is a copy, the caller cannot change the value if the internal Pointer value.

Returns:: a copy of the Comparator Pointer being used by this Queue.

template<typename E>

virtual decaf::util::Iterator<E>* decaf::util::PriorityQueue< E >::iterator ( ) const [inline, virtual]

Implements decaf::lang::Iterable< E >.

template<typename E>

virtual decaf::util::Iterator<E>* decaf::util::PriorityQueue< E >::iterator ( ) [inline, virtual]

Returns:: an iterator over a set of elements of type T.

Implements decaf::lang::Iterable< E >.

References decaf::util::PriorityQueue< E >::PriorityQueueIterator.

template<typename E>

virtual bool decaf::util::PriorityQueue< E >::offer ( const E & value ) [inline, virtual]

Inserts the specified element into the queue provided that the condition allows such an operation.

The method is generally preferable to the collection.add(E), since the latter might throw an exception if the operation fails.

Parameters:

value the specified element to insert into the queue.

Returns:: true if the operation succeeds and false if it fails.

Exceptions:

NullPointerException	if the Queue implementation does not allow Null values to be inserted into the Queue.
IllegalArgumentException	if some property of the specified element prevents it from being added to this queue

Implements decaf::util::Queue< E >.

Referenced by decaf::util::PriorityQueue< E >::add().

template<typename E>

PriorityQueue<E>& decaf::util::PriorityQueue< E >::operator= ( const PriorityQueue< E > & source ) [inline]

Assignment operator, assign another PriorityQueue to this one.

Parameters:

source The PriorityQueue to copy to this one.

template<typename E>

PriorityQueue<E>& decaf::util::PriorityQueue< E >::operator= ( const Collection< E > & source ) [inline]

Assignment operator, assign another Collection to this one.

Parameters:

source The Collection to copy to this one.

template<typename E>

virtual bool decaf::util::PriorityQueue< E >::peek ( E & result ) const [inline, virtual]

Gets but not removes the element in the head of the queue.

The result if successful is assigned to the result parameter.

Parameters:

result Reference to an instance of the contained type to assigned the removed value to.

Returns:: true if the element at the head of the queue was removed and assigned to the result parameter.

Implements decaf::util::Queue< E >.

References decaf::util::AbstractCollection< E >::isEmpty().

template<typename E>

virtual bool decaf::util::PriorityQueue< E >::poll ( E & result ) [inline, virtual]

Gets and removes the element in the head of the queue.

If the operation succeeds the value of the element at the head of the Queue is assigned to the result parameter and the method returns true. If the operation fails the method returns false and the value of the result parameter is undefined.

Parameters:

result Reference to an instance of the contained type to assigned the removed value to.

Returns:: true if the element at the head of the queue was removed and assigned to the result parameter.

Implements decaf::util::Queue< E >.

References decaf::util::AbstractCollection< E >::isEmpty().

template<typename E>

virtual E decaf::util::PriorityQueue< E >::remove ( ) [inline, virtual]

Gets and removes the element in the head of the queue.Throws a NoSuchElementException if there is no element in the queue.

Returns:: the element in the head of the queue.

Exceptions:

NoSuchElementException if there is no element in the queue.

This implementation returns the result of poll unless the queue is empty.

Reimplemented from decaf::util::AbstractQueue< E >.

References decaf::util::AbstractCollection< E >::isEmpty().

template<typename E>

virtual bool decaf::util::PriorityQueue< E >::remove ( const E & value ) [inline, virtual]

Removes a single instance of the specified element from the collection.More formally, removes an element e such that (value == NULL ? e == NULL : value == e), if this collection contains one or more such elements. Returns true if this collection contained the specified element (or equivalently, if this collection changed as a result of the call).

Parameters:

value The reference to the element to remove from this Collection.

Returns:: true if the collection was changed, false otherwise.

Exceptions:

UnsupportedOperationExceptio	if this is an unmodifiable collection.
NullPointerException	if the Collection is a container of pointers and does not allow NULL values.

This implementation iterates over the collection looking for the specified element. If it finds the element, it removes the element from the collection using the iterator's remove method.Note that this implementation throws an UnsupportedOperationException if the iterator returned by this collection's iterator method does not implement the remove method and this collection contains the specified object.

This implementation iterates over the collection looking for the specified element. If it finds the element, it removes the element from the collection using the iterator's remove method.

Note that this implementation throws an UnsupportedOperationException if the iterator returned by this collection's iterator method does not implement the remove method and this collection contains the specified object.

Reimplemented from decaf::util::AbstractCollection< E >.

template<typename E>

virtual int decaf::util::PriorityQueue< E >::size ( ) const [inline, virtual]

Returns the number of elements in this collection.

If this collection contains more than Integer::MAX_VALUE elements, returns Integer::MAX_VALUE.

Returns:: the number of elements in this collection

Implements decaf::util::Collection< E >.

Friends And Related Function Documentation

template<typename E>

friend class PriorityQueueIterator [friend]

Referenced by decaf::util::PriorityQueue< E >::iterator().

The documentation for this class was generated from the following file:

src/main/decaf/util/PriorityQueue.h

decaf::util::PriorityQueue< E > Class Template Reference

Data Structures

Public Member Functions

Friends

Detailed Description

template<typename E> class decaf::util::PriorityQueue< E >

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

template<typename E>
class decaf::util::PriorityQueue< E >