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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags