Class BoundedPriorityQueue

  • All Implemented Interfaces:
    BoundedChannel, Channel, Puttable, Takable

    public class BoundedPriorityQueue
    extends SemaphoreControlledChannel
    A heap-based priority queue, using semaphores for concurrency control. The take operation returns the least element with respect to the given ordering. (If more than one element is tied for least value, one of them is arbitrarily chosen to be returned -- no guarantees are made for ordering across ties.) Ordering follows the JDK1.2 collection conventions: Either the elements must be Comparable, or a Comparator must be supplied. Comparison failures throw ClassCastExceptions during insertions and extractions. The implementation uses a standard array-based heap algorithm, as described in just about any data structures textbook.

    Put and take operations may throw ClassCastException if elements are not Comparable, or not comparable using the supplied comparator. Since not all elements are compared on each operation it is possible that an exception will not be thrown during insertion of non-comparable element, but will later be encountered during another insertion or extraction.

    [ Introduction to this package. ]

    • Constructor Summary

      Constructors 
      Constructor Description
      BoundedPriorityQueue()
      Create a priority queue with the current default capacity and relying on natural ordering.
      BoundedPriorityQueue​(int capacity)
      Create a priority queue with the given capacity, and relying on natural ordering.
      BoundedPriorityQueue​(int capacity, java.util.Comparator cmp)
      Create a priority queue with the given capacity and comparator
      BoundedPriorityQueue​(int capacity, java.util.Comparator cmp, java.lang.Class semaphoreClass)
      Create a priority queue with the given capacity and comparator, using the supplied Semaphore class for semaphores.
      BoundedPriorityQueue​(java.util.Comparator comparator)
      Create a priority queue with the current default capacity and the given comparator
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected java.lang.Object extract()
      Internal mechanics of take.
      protected void insert​(java.lang.Object x)
      Internal mechanics of put.
      java.lang.Object peek()
      Return, but do not remove object at head of Channel, or null if it is empty.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • heap_

        protected final Heap heap_
    • Constructor Detail

      • BoundedPriorityQueue

        public BoundedPriorityQueue​(int capacity,
                                    java.util.Comparator cmp)
                             throws java.lang.IllegalArgumentException
        Create a priority queue with the given capacity and comparator
        Throws:
        java.lang.IllegalArgumentException - if capacity less or equal to zero
      • BoundedPriorityQueue

        public BoundedPriorityQueue​(java.util.Comparator comparator)
        Create a priority queue with the current default capacity and the given comparator
      • BoundedPriorityQueue

        public BoundedPriorityQueue​(int capacity)
        Create a priority queue with the given capacity, and relying on natural ordering.
      • BoundedPriorityQueue

        public BoundedPriorityQueue()
        Create a priority queue with the current default capacity and relying on natural ordering.
      • BoundedPriorityQueue

        public BoundedPriorityQueue​(int capacity,
                                    java.util.Comparator cmp,
                                    java.lang.Class semaphoreClass)
                             throws java.lang.IllegalArgumentException,
                                    java.lang.NoSuchMethodException,
                                    java.lang.SecurityException,
                                    java.lang.InstantiationException,
                                    java.lang.IllegalAccessException,
                                    java.lang.reflect.InvocationTargetException
        Create a priority queue with the given capacity and comparator, using the supplied Semaphore class for semaphores.
        Throws:
        java.lang.IllegalArgumentException - if capacity less or equal to zero
        java.lang.NoSuchMethodException - If class does not have constructor that intializes permits
        java.lang.SecurityException - if constructor information not accessible
        java.lang.InstantiationException - if semaphore class is abstract
        java.lang.IllegalAccessException - if constructor cannot be called
        java.lang.reflect.InvocationTargetException - if semaphore constructor throws an exception