KickJava.com: Code - Class EDU.oswego.cs.dl.util.concurrent.BoundedPriorityQueue

Java API By Example, From Geeks To Geeks.

| Browse | Search | Books |

Code - Class 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;
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 cmp)
54    throws IllegalArgumentException {
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 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 cmp,
102                               Class semaphoreClass)
103    throws IllegalArgumentException,
104           NoSuchMethodException,
105           SecurityException,
106           InstantiationException,
107           IllegalAccessException,
108           InvocationTargetException {
109     super(capacity, semaphoreClass);
110     heap_ = new Heap(capacity, cmp);
111   }
112
113   protected void insert(Object x) { heap_.insert(x); }
114   protected Object extract() { return heap_.extract(); }
115   public Object peek() { return heap_.peek(); }
116
117 }
118