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