jsim.queue
Class TemporalQueue

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

All Implemented Interfaces:

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

public class TemporalQueue
extends PriorityQueue

TemporalQueue class maintains a priority queue using self-adjusting binary tree (splay tree). The code is based on Daniel Sleator's C implementation of splay tree data structure (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/07/16

Author:

John Miller, Zhiwei Zhang

Field Summary

Fields inherited from class jsim.queue.PriorityQueue

root

Fields inherited from class jsim.queue.Queue

capacity, size

Constructor Summary

TemporalQueue()
Constructs an empty temporal queue with unlimited capacity.

TemporalQueue(int capacity)
Constructs an empty temporal queue with limited capacity.

Method Summary

Q_Node	addAt(java.lang.Object item, double time) Insert item into the queue with default priority.
Q_Node	addAt(java.lang.Object item, double time, int priority) Insert an item, its activation time and priority into the temporal queue.

Methods inherited from class jsim.queue.PriorityQueue

addAt, addAt, first, printQueue, remove, splayForInsert, splayLeft, splayRight

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

Constructor Detail

TemporalQueue

public TemporalQueue()

Constructs an empty temporal queue with unlimited capacity.

TemporalQueue

public TemporalQueue(int capacity)

Constructs an empty temporal queue with limited capacity.

Parameters:

capacity - the maximum number of items queue can hold

Method Detail

addAt

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

Insert item into the queue with default priority.

Parameters:

item - new item to be inserted

Returns:

Q_Node node holding the new item

Throws:

FullQueueException - if the queue is full

addAt

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

Insert an item, its activation time and priority into the temporal queue.

Parameters:

item - new item to be inserted

time - the activation time of the new item

priority - the priority associated with the new item

Returns:

Q_Node node holding the new item

Throws:

FullQueueException - if the queue is full