org.metasyntactic.utilities
Class PriorityQueue

java.lang.Object
  |
  +--org.metasyntactic.utilities.PriorityQueue

public class PriorityQueue
extends java.lang.Object

A heap-based priority queue, without any concurrency control (i.e., no blocking on empty/full states). This class provides the data structure mechanics for BoundedPriorityQueue.

The class currently uses a standard array-based heap, In the future, it may instead use structures permitting finer-grained locking.


Field Summary
protected  java.util.Comparator comparator
          Used for Ordering
protected  int count
          The number of slots
protected  java.lang.Object[] nodes
          The element in this heap.
 
Constructor Summary
PriorityQueue(int capacity)
          Create a Heap with the given capacity, and relying on natural ordering.
PriorityQueue(int capacity, java.util.Comparator cmp)
          Create a Heap with the given initial capacity and comparator
 
Method Summary
 void clear()
          remove all elements
protected  int compare(java.lang.Object a, java.lang.Object b)
          perform element comparisons using comparator or natural ordering.
 java.lang.Object extractMax()
          Return and remove least element, or null if empty
 void insert(java.lang.Object x)
          insert an element, resize if necessary
protected  int left(int k)
          Returns the element to the left of this element
 java.lang.Object maximum()
           
protected  int parent(int k)
          Returns the parent of this element
 java.lang.Object peek()
          Return least element without removing it, or null if empty
protected  int right(int k)
          Returns the element to the right of this element
 int size()
          Return number of elements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

nodes

protected java.lang.Object[] nodes
The element in this heap. Elements in the nodes are from 0 -> count - 1


count

protected int count
The number of slots


comparator

protected final java.util.Comparator comparator
Used for Ordering

Constructor Detail

PriorityQueue

public PriorityQueue(int capacity,
                     java.util.Comparator cmp)
              throws java.lang.IllegalArgumentException
Create a Heap with the given initial capacity and comparator

Parameters:
capacity - The initial capacity of the heap. Note!! This is not the maximum capcity of the heap, the heap can grow as large as necessary
cmp - A comparator used to determine the order of the nodes in the heap
Throws:
java.lang.IllegalArgumentException - if capacity less or equal to zero

PriorityQueue

public PriorityQueue(int capacity)
Create a Heap with the given capacity, and relying on natural ordering.

Parameters:
capacity -
Method Detail

compare

protected int compare(java.lang.Object a,
                      java.lang.Object b)
               throws java.lang.IllegalArgumentException
perform element comparisons using comparator or natural ordering. Note, if natural ordering is used then all Objects inserted to the heap must implement the Comparable interface

Parameters:
a -
b -
Returns:
Throws:
java.lang.ClassCastException
java.lang.IllegalArgumentException - If natural ordering is being used, and 'a' does not implement Comparable

parent

protected final int parent(int k)
Returns the parent of this element

Parameters:
k -
Returns:

left

protected final int left(int k)
Returns the element to the left of this element

Parameters:
k -
Returns:

right

protected final int right(int k)
Returns the element to the right of this element

Parameters:
k -
Returns:

insert

public void insert(java.lang.Object x)
insert an element, resize if necessary

Parameters:
x -

maximum

public java.lang.Object maximum()
                         throws HeapUnderflowException
HeapUnderflowException

extractMax

public java.lang.Object extractMax()
                            throws HeapUnderflowException
Return and remove least element, or null if empty

Returns:
HeapUnderflowException

peek

public java.lang.Object peek()
Return least element without removing it, or null if empty

Returns:

size

public int size()
Return number of elements

Returns:

clear

public void clear()
remove all elements