An implementation of EventList using a binary search tree. More...

Inheritance diagram for umontreal.ssj.simevents.eventlist.BinaryTree:

Public Member Functions
boolean	isEmpty ()
	Returns true if and only if the event list is empty (no event is scheduled).
void	clear ()
	Empties the event list, i.e., cancels all events.
void	add (Event ev)
	Adds a new event in the event list, according to the time of ev.
void	addFirst (Event ev)
	Adds a new event at the beginning of the event 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	addAfter (Event ev, Event other)
	Same as add, but adds the new event ev immediately after the event other in the list.
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.
ListIterator< Event >	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).

Package Functions
public< E extends Event > E	getFirstOfClass (Class< E > cl)
	Returns the first event of the class E (a subclass of Event) in the event list.

Detailed Description

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.

Definition at line 50 of file BinaryTree.java.

Member Function Documentation

◆ add()

void umontreal.ssj.simevents.eventlist.BinaryTree.add ( Event ev )

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.

Parameters

ev	event to be added

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 66 of file BinaryTree.java.

◆ addAfter()

void umontreal.ssj.simevents.eventlist.BinaryTree.addAfter	(	Event	ev,
		Event	other )

Same as add, but adds the new event ev immediately after the event other in the list.

Parameters

ev	event to be added
other	reference event after which ev will be added

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 158 of file BinaryTree.java.

◆ addBefore()

void umontreal.ssj.simevents.eventlist.BinaryTree.addBefore	(	Event	ev,
		Event	other )

Same as add, but adds the new event ev immediately before the event other in the list.

Parameters

ev	event to be added
other	reference event before which ev will be added

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 123 of file BinaryTree.java.

◆ addFirst()

void umontreal.ssj.simevents.eventlist.BinaryTree.addFirst ( Event ev )

Adds a new event at the beginning of the event list.

The given event ev will occur at the current simulation time.

Parameters

ev	event to be added

Ajoute "ev" comme premier evenement dans l'arbre. Donc completement a gauche On met l'ancien premier evenement a droite de ev. (Necessaire quand on a des evenements simultanes)

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 98 of file BinaryTree.java.

◆ clear()

void umontreal.ssj.simevents.eventlist.BinaryTree.clear ( )

Empties the event list, i.e., cancels all events.

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 61 of file BinaryTree.java.

◆ getFirst()

Event umontreal.ssj.simevents.eventlist.BinaryTree.getFirst ( )

Returns the first event in the event list.

If the event list is empty, returns null.

Returns: the first event in the event list, or null if the list is empty

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 177 of file BinaryTree.java.

◆ getFirstOfClass() [1/2]

public< E extends Event > E umontreal.ssj.simevents.eventlist.BinaryTree.getFirstOfClass ( Class< E > cl )

package

Returns the first event of the class E (a subclass of Event) in the event list.

If no such event is found, returns null.

Returns: the first event of class cl, or null if no such event exists in the list

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 201 of file BinaryTree.java.

◆ getFirstOfClass() [2/2]

Event umontreal.ssj.simevents.eventlist.BinaryTree.getFirstOfClass ( String cl )

Returns the first event of the class cl (a subclass of Event) in the event list.

If no such event is found, returns null.

Returns: the first event of class cl, or null if no such event exists in the list

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 186 of file BinaryTree.java.

◆ isEmpty()

boolean umontreal.ssj.simevents.eventlist.BinaryTree.isEmpty ( )

Returns true if and only if the event list is empty (no event is scheduled).

Returns: true if the event list is empty

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 57 of file BinaryTree.java.

◆ listIterator()

ListIterator< Event > umontreal.ssj.simevents.eventlist.BinaryTree.listIterator ( )

Returns a list iterator over the elements of the class Event in this list.

Returns: a list iterator over the elements of the class Event in this list

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 219 of file BinaryTree.java.

◆ remove()

boolean umontreal.ssj.simevents.eventlist.BinaryTree.remove ( Event ev )

Removes the event ev from the event list (cancels this event).

Returns true if and only if the event removal has succeeded.

Parameters

ev	event to be removed

Returns: true if the event was successfully removed from the list

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 223 of file BinaryTree.java.

◆ removeFirst()

Event umontreal.ssj.simevents.eventlist.BinaryTree.removeFirst ( )

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.

Returns: the first event removed from the list, or null if the list is empty

Implements umontreal.ssj.simevents.eventlist.EventList.

Definition at line 231 of file BinaryTree.java.

The documentation for this class was generated from the following file:

src/main/java/umontreal/ssj/simevents/eventlist/BinaryTree.java

SSJ API Documentation Stochastic Simulation in Java

Public Member Functions

Package Functions

Detailed Description

Member Function Documentation

◆ add()

◆ addAfter()

◆ addBefore()

◆ addFirst()

◆ clear()

◆ getFirst()

◆ getFirstOfClass() [1/2]

◆ getFirstOfClass() [2/2]

◆ isEmpty()

◆ listIterator()

◆ remove()

◆ removeFirst()