Package EDU.oswego.cs.dl.util.concurrent
Class BoundedPriorityQueue
java.lang.Object
EDU.oswego.cs.dl.util.concurrent.SemaphoreControlledChannel
EDU.oswego.cs.dl.util.concurrent.BoundedPriorityQueue
- All Implemented Interfaces:
BoundedChannel
,Channel
,Puttable
,Takable
A heap-based priority queue, using semaphores for
concurrency control.
The take operation returns the least element
with respect to the given ordering. (If more than
one element is tied for least value, one of them is
arbitrarily chosen to be returned -- no guarantees
are made for ordering across ties.)
Ordering follows the JDK1.2 collection
conventions: Either the elements must be Comparable, or
a Comparator must be supplied. Comparison failures throw
ClassCastExceptions during insertions and extractions.
The implementation uses a standard array-based heap algorithm,
as described in just about any data structures textbook.
Put and take operations may throw ClassCastException if elements are not Comparable, or not comparable using the supplied comparator. Since not all elements are compared on each operation it is possible that an exception will not be thrown during insertion of non-comparable element, but will later be encountered during another insertion or extraction.
-
Field Summary
FieldsFields inherited from class EDU.oswego.cs.dl.util.concurrent.SemaphoreControlledChannel
capacity_, putGuard_, takeGuard_
-
Constructor Summary
ConstructorsConstructorDescriptionCreate a priority queue with the current default capacity and relying on natural ordering.BoundedPriorityQueue
(int capacity) Create a priority queue with the given capacity, and relying on natural ordering.BoundedPriorityQueue
(int capacity, Comparator cmp) Create a priority queue with the given capacity and comparatorBoundedPriorityQueue
(int capacity, Comparator cmp, Class semaphoreClass) Create a priority queue with the given capacity and comparator, using the supplied Semaphore class for semaphores.BoundedPriorityQueue
(Comparator comparator) Create a priority queue with the current default capacity and the given comparator -
Method Summary
-
Field Details
-
heap_
-
-
Constructor Details
-
BoundedPriorityQueue
Create a priority queue with the given capacity and comparator- Throws:
IllegalArgumentException
- if capacity less or equal to zero
-
BoundedPriorityQueue
Create a priority queue with the current default capacity and the given comparator -
BoundedPriorityQueue
public BoundedPriorityQueue(int capacity) Create a priority queue with the given capacity, and relying on natural ordering. -
BoundedPriorityQueue
public BoundedPriorityQueue()Create a priority queue with the current default capacity and relying on natural ordering. -
BoundedPriorityQueue
public BoundedPriorityQueue(int capacity, Comparator cmp, Class semaphoreClass) throws IllegalArgumentException, NoSuchMethodException, SecurityException, InstantiationException, IllegalAccessException, InvocationTargetException Create a priority queue with the given capacity and comparator, using the supplied Semaphore class for semaphores.- Throws:
IllegalArgumentException
- if capacity less or equal to zeroNoSuchMethodException
- If class does not have constructor that intializes permitsSecurityException
- if constructor information not accessibleInstantiationException
- if semaphore class is abstractIllegalAccessException
- if constructor cannot be calledInvocationTargetException
- if semaphore constructor throws an exception
-
-
Method Details
-
insert
Description copied from class:SemaphoreControlledChannel
Internal mechanics of put.- Specified by:
insert
in classSemaphoreControlledChannel
-
extract
Description copied from class:SemaphoreControlledChannel
Internal mechanics of take.- Specified by:
extract
in classSemaphoreControlledChannel
-
peek
Description copied from interface:Channel
Return, but do not remove object at head of Channel, or null if it is empty.
-