simple.util
Class PriorityQueue

java.lang.Object
  extended by simple.util.PriorityQueue
All Implemented Interfaces:
java.io.Serializable

public class PriorityQueue
extends java.lang.Object
implements java.io.Serializable

This class implements a PriorityQueue. This class is implemented in such a way that objects are added using an add function. The add function takes two paramaters an object and a long.

The object represents an item in the queue, the long indicates its priority in the queue. The remove function in this class returns the object first in the queue and that object is removed from the queue permentaly.

Author:
Niall Gallagher
See Also:
Serialized Form

Field Summary
protected  int capacity
          This holds the number elements this queue can have.
protected  int count
          Holds the number of elements currently in the queue.
protected  java.lang.Object[] data
          This contains the list of objects in the queue.
protected  long maxPriority
          The maximum priority possible in this priority queue.
protected  long[] value
          This contains the list of prioritys in the queue.
 
Constructor Summary
PriorityQueue()
          Creates a new PriorityQueue object.
PriorityQueue(int capacity)
          Creates a new PriorityQueue object.
PriorityQueue(int capacity, long maxPriority)
          Creates a new PriorityQueue object.
 
Method Summary
 void add(java.lang.Object element, long priority)
          This function adds the given object into the PriorityQueue, its priority is the long priority.
protected  void bubbleDown(int pos)
          Bubble down is used to put the element at subscript 'pos' into it's rightfull place in the heap (a heap is another name used for PriorityQueue).
protected  void bubbleUp(int pos)
          Bubble up is used to place an element relatively low in the queue to it's rightful place higher in the queue, but only if it's priority allows it to do so, similar to bubbleDown only in the other directon this swaps out its parents.
 void clear()
          This method will empty the queue.
protected  void expandCapacity()
          This ensures that there is enough space to keep adding elements to the priority queue.
 int length()
          The number of elements in the queue.
 java.lang.Object remove()
          Remove is a function to remove the element in the queue with the maximum priority.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

maxPriority

protected long maxPriority
The maximum priority possible in this priority queue.


data

protected java.lang.Object[] data
This contains the list of objects in the queue.


value

protected long[] value
This contains the list of prioritys in the queue.


count

protected int count
Holds the number of elements currently in the queue.


capacity

protected int capacity
This holds the number elements this queue can have.

Constructor Detail

PriorityQueue

public PriorityQueue()
Creates a new PriorityQueue object. The PriorityQueue object allows objects to be entered into the queue and to leave in the order of priority, the highest priority get's to leave first.


PriorityQueue

public PriorityQueue(int capacity)
Creates a new PriorityQueue object. The PriorityQueue object allows objects to be entered into the queue an to leave in the order of priority, the highest priority get's to leave first.

Parameters:
capacity - the initial capacity of the queue before a resize

PriorityQueue

public PriorityQueue(int capacity,
                     long maxPriority)
Creates a new PriorityQueue object. The PriorityQueue object allows objects to be entered into the queue an to leave in the order of priority, the highest priority get's to leave first.

Parameters:
capacity - the initial capacity of the queue before a resize
maxPriority - is the maximum possible priority for an object
Method Detail

add

public void add(java.lang.Object element,
                long priority)
This function adds the given object into the PriorityQueue, its priority is the long priority. The way in which priority can be associated with the elements of the queue is by keeping the priority and the elements array entrys parallel.

Parameters:
element - is the object that is to be entered into this PriorityQueue
priority - this is the priority that the object holds in the PriorityQueue

remove

public java.lang.Object remove()
Remove is a function to remove the element in the queue with the maximum priority. Once the element is removed then it can never be recovered from the queue with further calls. The lowest priority object will leave last.

Returns:
the object with the highest priority or, if empty, null

bubbleDown

protected void bubbleDown(int pos)
Bubble down is used to put the element at subscript 'pos' into it's rightfull place in the heap (a heap is another name used for PriorityQueue). If the priority of an element at subscript 'pos' is less than it's children then it must be put under one of these children, that is, the ones with the maximum priority must come first.

Parameters:
pos - the position the bubble down procedure starts from

bubbleUp

protected void bubbleUp(int pos)
Bubble up is used to place an element relatively low in the queue to it's rightful place higher in the queue, but only if it's priority allows it to do so, similar to bubbleDown only in the other directon this swaps out its parents.

Parameters:
pos - the position the bubble up procedure starts from

expandCapacity

protected void expandCapacity()
This ensures that there is enough space to keep adding elements to the priority queue. It is however advised to make the capacity of the queue large enough so that this will not be used as it is an expensive method. This will copy across from 0 as 'off' equals 0 is contains some important data.


clear

public void clear()
This method will empty the queue. This also helps garbage collection by releasing any reference it has to the elements in the queue. This starts from offset 1 as off equals 0 for the elements array.


length

public int length()
The number of elements in the queue. The length indicates the number of elements that are currently in the queue.

Returns:
the number of elements in the queue