001: /*
002: File: BoundedPriorityQueue.java
003:
004: Originally written by Doug Lea and released into the public domain.
005: This may be used for any purposes whatsoever without acknowledgment.
006: Thanks for the assistance and support of Sun Microsystems Labs,
007: and everyone contributing, testing, and using this code.
008:
009: History:
010: Date Who What
011: 16Jun1998 dl Create public version
012: 25aug1998 dl added peek
013: 29aug1998 dl pulled heap mechanics into separate class
014: */
015:
016: package EDU.oswego.cs.dl.util.concurrent;
017:
018: import java.util.Comparator;
019: import java.lang.reflect.*;
020:
021: /**
022: * A heap-based priority queue, using semaphores for
023: * concurrency control.
024: * The take operation returns the <em>least</em> element
025: * with respect to the given ordering. (If more than
026: * one element is tied for least value, one of them is
027: * arbitrarily chosen to be returned -- no guarantees
028: * are made for ordering across ties.)
029: * Ordering follows the JDK1.2 collection
030: * conventions: Either the elements must be Comparable, or
031: * a Comparator must be supplied. Comparison failures throw
032: * ClassCastExceptions during insertions and extractions.
033: * The implementation uses a standard array-based heap algorithm,
034: * as described in just about any data structures textbook.
035: * <p>
036: * Put and take operations may throw ClassCastException
037: * if elements are not Comparable, or
038: * not comparable using the supplied comparator.
039: * Since not all elements are compared on each operation
040: * it is possible that an exception will not be thrown
041: * during insertion of non-comparable element, but will later be
042: * encountered during another insertion or extraction.
043: * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
044: **/
045:
046: public class BoundedPriorityQueue extends SemaphoreControlledChannel {
047: protected final Heap heap_;
048:
049: /**
050: * Create a priority queue with the given capacity and comparator
051: * @exception IllegalArgumentException if capacity less or equal to zero
052: **/
053:
054: public BoundedPriorityQueue(int capacity, Comparator cmp)
055: throws IllegalArgumentException {
056: super (capacity);
057: heap_ = new Heap(capacity, cmp);
058: }
059:
060: /**
061: * Create a priority queue with the current default capacity
062: * and the given comparator
063: **/
064:
065: public BoundedPriorityQueue(Comparator comparator) {
066: this (DefaultChannelCapacity.get(), comparator);
067: }
068:
069: /**
070: * Create a priority queue with the given capacity,
071: * and relying on natural ordering.
072: **/
073:
074: public BoundedPriorityQueue(int capacity) {
075: this (capacity, null);
076: }
077:
078: /**
079: * Create a priority queue with the current default capacity
080: * and relying on natural ordering.
081: **/
082:
083: public BoundedPriorityQueue() {
084: this (DefaultChannelCapacity.get(), null);
085: }
086:
087: /**
088: * Create a priority queue with the given capacity and comparator, using
089: * the supplied Semaphore class for semaphores.
090: * @exception IllegalArgumentException if capacity less or equal to zero
091: * @exception NoSuchMethodException If class does not have constructor
092: * that intializes permits
093: * @exception SecurityException if constructor information
094: * not accessible
095: * @exception InstantiationException if semaphore class is abstract
096: * @exception IllegalAccessException if constructor cannot be called
097: * @exception InvocationTargetException if semaphore constructor throws an
098: * exception
099: **/
100:
101: public BoundedPriorityQueue(int capacity, Comparator cmp,
102: Class semaphoreClass) throws IllegalArgumentException,
103: NoSuchMethodException, SecurityException,
104: InstantiationException, IllegalAccessException,
105: InvocationTargetException {
106: super (capacity, semaphoreClass);
107: heap_ = new Heap(capacity, cmp);
108: }
109:
110: protected void insert(Object x) {
111: heap_.insert(x);
112: }
113:
114: protected Object extract() {
115: return heap_.extract();
116: }
117:
118: public Object peek() {
119: return heap_.peek();
120: }
121:
122: }
|