Class EventQueue

java.lang.Object
  |
  +--EventQueue

public class EventQueue

extends java.lang.Object

A simple heap to represent the event queue

See Also:

Event

Constructor Summary

EventQueue()
Construct a new queue

Method Summary

boolean	empty() Returns true if the queue is empty (there are no pending events).
Event	getNext() Returns the next event (the one with the earliest time) and removes it from the queue.
void	insert(Event e) Inserts an event into the queue.
Event	peekNext() Returns the next event (the one with the earliest time) without removing it from the queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

EventQueue

public EventQueue()

Construct a new queue

Method Detail

empty

public boolean empty()

Returns true if the queue is empty (there are no pending events).

insert

public void insert(Event e)
            throws TimeInconsistencyException

Inserts an event into the queue. The queue implementation is a heap stored as an array. Insertion is done by appending the new element at the end of the array (i.e., as a new leaf in the heap) and "bubbling" it up as long as it is smaller than its parent. When storing a heap (remember, a heap is a tree) as a zero-based array, the parent of node I is node (I-1)/2. This function runs in O(lg n) time, where n is the number of events in the heap.

Parameters:

e - The event to insert

Throws:

TimeInconsistencyException - Thrown when the new event being inserted occurs in the past (i.e., before any event already retrieved with getNext).

peekNext

public Event peekNext()

Returns the next event (the one with the earliest time) without removing it from the queue. The minimum element in a heap is the root of the heap; when using an array for storage, the root is the first element of the array. This function runs in constant time.

getNext

public Event getNext()

Returns the next event (the one with the earliest time) and removes it from the queue. The queue implementation is a heap stored as an array. Finding the minimum element is easy -- it's the first element of the array (see peekNext, above). Removing it is done by copying the last leaf of the heap over the root, removing the last leaf, and "bubbling" the new root (which was the last leaf) down as long as it is larger than either of its children. When storing a heap (remember, a heap is a tree) as a zero-based array, the children of node I are nodes (I*2)+1 and (I*2)+2. This function runs in O(lg n) time, where n is the number of events in the heap.