SSJ
V. 1.2.5.

umontreal.iro.lecuyer.simevents.eventlist
Class BinaryTree

java.lang.Object
  extended by umontreal.iro.lecuyer.simevents.eventlist.BinaryTree
All Implemented Interfaces:
EventList

public class BinaryTree
extends Object
implements EventList

An implementation of EventList using a binary search tree. Every event is stored into a tree node which has left and right children. Using the event time as a comparator, the left child is always smaller than its parent whereas the right is greater or equal. This allows an average O(log(n)) time for adding an event and searching the first event, where n is the number of events in the structure. There is less overhead for adding and removing events than splay tree or red black tree. However, in the worst case, adding or removing could be done in time proportional to n because the binary search tree can be turned into a linked list.


Constructor Summary
BinaryTree()
           
 
Method Summary
 void add(Event ev)
          Adds a new event in the event list, according to the time of ev.
 void addAfter(Event ev, Event other)
          Same as add, but adds the new event ev immediately after the event other in the list.
 void addBefore(Event ev, Event other)
          Same as add, but adds the new event ev immediately before the event other in the list.
 void addFirst(Event ev)
          Adds a new event at the beginning of the event list.
 void clear()
          Empties the event list, i.e., cancels all events.
 Event getFirst()
          Returns the first event in the event list.
 Event getFirstOfClass(String cl)
          Returns the first event of the class cl (a subclass of Event) in the event list.
 boolean isEmpty()
          Returns true if and only if the event list is empty (no event is scheduled).
 ListIterator listIterator()
          Returns a list iterator over the elements of the class Event in this list.
 boolean remove(Event ev)
          Removes the event ev from the event list (cancels this event).
 Event removeFirst()
          Removes the first event from the event list (to cancel or execute this event).
 String toString()
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

BinaryTree

public BinaryTree()
Method Detail

isEmpty

public boolean isEmpty()
Description copied from interface: EventList
Returns true if and only if the event list is empty (no event is scheduled).

Specified by:
isEmpty in interface EventList
Returns:
true if the event list is empty

clear

public void clear()
Description copied from interface: EventList
Empties the event list, i.e., cancels all events.

Specified by:
clear in interface EventList

add

public void add(Event ev)
Description copied from interface: EventList
Adds a new event in the event list, according to the time of ev. If the event list contains events scheduled to happen at the same time as ev, ev must be added after all these events.

Specified by:
add in interface EventList
Parameters:
ev - event to be added

addFirst

public void addFirst(Event ev)
Description copied from interface: EventList
Adds a new event at the beginning of the event list. The given event ev will occur at the current simulation time.

Specified by:
addFirst in interface EventList
Parameters:
ev - event to be added

addBefore

public void addBefore(Event ev,
                      Event other)
Description copied from interface: EventList
Same as add, but adds the new event ev immediately before the event other in the list.

Specified by:
addBefore in interface EventList
Parameters:
ev - event to be added
other - reference event before which ev will be added

addAfter

public void addAfter(Event ev,
                     Event other)
Description copied from interface: EventList
Same as add, but adds the new event ev immediately after the event other in the list.

Specified by:
addAfter in interface EventList
Parameters:
ev - event to be added
other - reference event after which ev will be added

getFirst

public Event getFirst()
Description copied from interface: EventList
Returns the first event in the event list. If the event list is empty, returns null.

Specified by:
getFirst in interface EventList
Returns:
the first event in the event list, or null if the list is empty

getFirstOfClass

public Event getFirstOfClass(String cl)
Description copied from interface: EventList
Returns the first event of the class cl (a subclass of Event) in the event list. If no such event are found, returns null.

Specified by:
getFirstOfClass in interface EventList
Returns:
the first event of class cl, or null if no such event exists in the list

listIterator

public ListIterator listIterator()
Description copied from interface: EventList
Returns a list iterator over the elements of the class Event in this list.

Specified by:
listIterator in interface EventList
Returns:
a list iterator over the elements of the class Event in this list

remove

public boolean remove(Event ev)
Description copied from interface: EventList
Removes the event ev from the event list (cancels this event). Returns true if and only if the event removal has succeeded.

Specified by:
remove in interface EventList
Parameters:
ev - event to be removed
Returns:
true if the event was successfully removed from the list

removeFirst

public Event removeFirst()
Description copied from interface: EventList
Removes the first event from the event list (to cancel or execute this event). Returns the removed event. If the list is empty, then null is returned.

Specified by:
removeFirst in interface EventList
Returns:
the first event removed from the list, or null if the list is empty

toString

public String toString()
Overrides:
toString in class Object

SSJ
V. 1.2.5.

To submit a bug or ask questions, send an e-mail to Pierre L'Ecuyer.