Mercurial > hg > blitz_condensed

comparison src/EDU/oswego/cs/dl/util/concurrent/BoundedPriorityQueue.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial checkin of blitz 2.0 fcs - no installer yet.
author Dan Creswell <dan.creswell@gmail.com>
date Sat, 21 Mar 2009 11:00:06 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
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 }