KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > EDU > oswego > cs > dl > util > concurrent > BoundedPriorityQueue


1 /*
2   File: BoundedPriorityQueue.java
3
4   Originally written by Doug Lea and released into the public domain.
5   This may be used for any purposes whatsoever without acknowledgment.
6   Thanks for the assistance and support of Sun Microsystems Labs,
7   and everyone contributing, testing, and using this code.
8
9   History:
10   Date Who What
11   16Jun1998 dl Create public version
12   25aug1998 dl added peek
13   29aug1998 dl pulled heap mechanics into separate class
14 */

15
16 package EDU.oswego.cs.dl.util.concurrent;
17 import java.util.Comparator JavaDoc;
18 import java.lang.reflect.*;
19
20 /**
21  * A heap-based priority queue, using semaphores for
22  * concurrency control.
23  * The take operation returns the <em>least</em> element
24  * with respect to the given ordering. (If more than
25  * one element is tied for least value, one of them is
26  * arbitrarily chosen to be returned -- no guarantees
27  * are made for ordering across ties.)
28  * Ordering follows the JDK1.2 collection
29  * conventions: Either the elements must be Comparable, or
30  * a Comparator must be supplied. Comparison failures throw
31  * ClassCastExceptions during insertions and extractions.
32  * The implementation uses a standard array-based heap algorithm,
33  * as described in just about any data structures textbook.
34  * <p>
35  * Put and take operations may throw ClassCastException
36  * if elements are not Comparable, or
37  * not comparable using the supplied comparator.
38  * Since not all elements are compared on each operation
39  * it is possible that an exception will not be thrown
40  * during insertion of non-comparable element, but will later be
41  * encountered during another insertion or extraction.
42  * <p>[<a HREF="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
43  **/

44
45 public class BoundedPriorityQueue extends SemaphoreControlledChannel {
46   protected final Heap heap_;
47
48   /**
49    * Create a priority queue with the given capacity and comparator
50    * @exception IllegalArgumentException if capacity less or equal to zero
51    **/

52
53   public BoundedPriorityQueue(int capacity, Comparator JavaDoc cmp)
54    throws IllegalArgumentException JavaDoc {
55     super(capacity);
56     heap_ = new Heap(capacity, cmp);
57   }
58
59   /**
60    * Create a priority queue with the current default capacity
61    * and the given comparator
62    **/

63
64   public BoundedPriorityQueue(Comparator JavaDoc comparator) {
65     this(DefaultChannelCapacity.get(), comparator);
66   }
67
68   /**
69    * Create a priority queue with the given capacity,
70    * and relying on natural ordering.
71    **/

72
73   public BoundedPriorityQueue(int capacity) {
74     this(capacity, null);
75   }
76
77   /**
78    * Create a priority queue with the current default capacity
79    * and relying on natural ordering.
80    **/

81
82   public BoundedPriorityQueue() {
83     this(DefaultChannelCapacity.get(), null);
84   }
85
86
87   /**
88    * Create a priority queue with the given capacity and comparator, using
89    * the supplied Semaphore class for semaphores.
90    * @exception IllegalArgumentException if capacity less or equal to zero
91    * @exception NoSuchMethodException If class does not have constructor
92    * that intializes permits
93    * @exception SecurityException if constructor information
94    * not accessible
95    * @exception InstantiationException if semaphore class is abstract
96    * @exception IllegalAccessException if constructor cannot be called
97    * @exception InvocationTargetException if semaphore constructor throws an
98    * exception
99    **/

100
101   public BoundedPriorityQueue(int capacity, Comparator JavaDoc cmp,
102                               Class JavaDoc semaphoreClass)
103    throws IllegalArgumentException JavaDoc,
104           NoSuchMethodException JavaDoc,
105           SecurityException JavaDoc,
106           InstantiationException JavaDoc,
107           IllegalAccessException JavaDoc,
108           InvocationTargetException {
109     super(capacity, semaphoreClass);
110     heap_ = new Heap(capacity, cmp);
111   }
112
113   protected void insert(Object JavaDoc x) { heap_.insert(x); }
114   protected Object JavaDoc extract() { return heap_.extract(); }
115   public Object JavaDoc peek() { return heap_.peek(); }
116
117 }
118
Popular Tags