jsim.queue
Class PriorityQueue

java.lang.Object
  jsim.queue.Queue
      jsim.queue.PriorityQueue

All Implemented Interfaces:

java.lang.Iterable, java.util.Collection, java.util.List

Direct Known Subclasses:

TemporalQueue

public class PriorityQueue
extends Queue

PriorityQueue class maintains a priority queue using self-adjusting binary tree (splay tree). The splay part is based on Daniel Sleator's C implementation of splay tree (http://gs213.sp.cs.cmu.edu/prog/splay/). The data structure is first proposed by Sleator and Tarjan in their article "Self-adjusting Binary Search Tree", JACM, 32(3):652-686, 1985.

Version:

1.0 96/06/20

Author:

John Miller, Zhiwei Zhang

Field Summary

protected PQ_Node

root Root (front) of the queue

Fields inherited from class jsim.queue.Queue

capacity, size

Constructor Summary

PriorityQueue()
Constructs an empty priority queue with unlimited capacity.

PriorityQueue(int capacity)
Constructs an empty priority queue with limited capacity.

Method Summary

Q_Node	addAt(java.lang.Object item) Insert item into the queue with default priority.
Q_Node	addAt(java.lang.Object item, int priority) Insert item and its priority into the queue.
Q_Node	first() Iteratively splay left until the root has no left child.
void	printQueue() Print the tree holding the prior queue.
Q_Node	remove() Remove and return the first element in the queue.
protected void	splayForInsert(PQ_Node newNode) Splay the tree until newNode can be inserted either between lChild and root, or root and rChild.
protected PQ_Node	splayLeft(PQ_Node node, PQ_Node lChild) Splay node with its left child.
protected PQ_Node	splayRight(PQ_Node node, PQ_Node rChild) Splay node with its right child.

Methods inherited from class jsim.queue.Queue

add, add, addAll, addAll, cancel, clear, contains, containsAll, get, indexOf, isEmpty, isFull, iterator, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, removeMin, retainAll, set, size, subList, toArray, toArray

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.List

equals, hashCode

Field Detail

root

protected PQ_Node root

Root (front) of the queue

Constructor Detail

PriorityQueue

public PriorityQueue()

Constructs an empty priority queue with unlimited capacity.

PriorityQueue

public PriorityQueue(int capacity)

Constructs an empty priority queue with limited capacity.

Parameters:

capacity - maximum number of items queue can hold

Method Detail

printQueue

public void printQueue()

Print the tree holding the prior queue. Indent based on level of tree.

addAt

public Q_Node addAt(java.lang.Object item)
             throws FullQueueException

Insert item into the queue with default priority.

Specified by:

addAt in class Queue

Parameters:

item - new item to be inserted

Returns:

Q_Node node holding new item

Throws:

FullQueueException - if the queue is full

addAt

public Q_Node addAt(java.lang.Object item,
                    int priority)
             throws FullQueueException

Insert item and its priority into the queue.

Parameters:

item - new item to be inserted

priority - priority associated with the new item

Returns:

Q_Node node holding new item

Throws:

FullQueueException - if the queue is full

splayLeft

protected PQ_Node splayLeft(PQ_Node node,
                            PQ_Node lChild)

Splay node with its left child.

Parameters:

node - node to splay

lChild - left child node

Returns:

PQ_Node left child

splayRight

protected PQ_Node splayRight(PQ_Node node,
                             PQ_Node rChild)

Splay node with its right child.

Parameters:

node - node to splay

lChild - right child node

Returns:

PQ_Node right child

splayForInsert

protected void splayForInsert(PQ_Node newNode)

Splay the tree until newNode can be inserted either between lChild and root, or root and rChild.

Parameters:

newNode - node to be inserted

remove

public Q_Node remove()
              throws java.util.NoSuchElementException

Remove and return the first element in the queue. If first node has been cancelled (not present), continue to remove.

Overrides:

remove in class Queue

Returns:

Q_Node first node (holds min item)

Throws:

java.util.NoSuchElementException - if the queue is empty

first

public Q_Node first()
             throws java.util.NoSuchElementException

Iteratively splay left until the root has no left child. This means that the root will be the minimum element in the tree.

Overrides:

first in class Queue

Returns:

PQ_Node root after splaying (holds min item)

Throws:

java.util.NoSuchElementException - if the queue is empty.