|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object jsim.queue.Queue jsim.queue.PriorityQueue
public class PriorityQueue
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.
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 |
---|
protected PQ_Node root
Constructor Detail |
---|
public PriorityQueue()
public PriorityQueue(int capacity)
capacity
- maximum number of items queue can holdMethod Detail |
---|
public void printQueue()
public Q_Node addAt(java.lang.Object item) throws FullQueueException
addAt
in class Queue
item
- new item to be inserted
FullQueueException
- if the queue is fullpublic Q_Node addAt(java.lang.Object item, int priority) throws FullQueueException
item
- new item to be insertedpriority
- priority associated with the new item
FullQueueException
- if the queue is fullprotected PQ_Node splayLeft(PQ_Node node, PQ_Node lChild)
node
- node to splaylChild
- left child node
protected PQ_Node splayRight(PQ_Node node, PQ_Node rChild)
node
- node to splaylChild
- right child node
protected void splayForInsert(PQ_Node newNode)
newNode
- node to be insertedpublic Q_Node remove() throws java.util.NoSuchElementException
remove
in class Queue
java.util.NoSuchElementException
- if the queue is emptypublic Q_Node first() throws java.util.NoSuchElementException
first
in class Queue
java.util.NoSuchElementException
- if the queue is empty.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |