umontreal.iro.lecuyer.simevents.eventlist

Class RedblackTree

java.lang.Object

umontreal.iro.lecuyer.simevents.eventlist.RedblackTree

All Implemented Interfaces:

java.lang.Iterable<Event>, EventList

public class RedblackTree
extends java.lang.Object
implements EventList

An implementation of EventList using a red black tree, which is similar to a binary search tree except that every node is colored red or black. When modifying the structure, the tree is reorganized for the colors to satisfy rules that give an average O(log(n)) time for removing the first event or inserting a new event, where n is the number of elements in the structure. However, adding or removing events imply reorganizing the tree and requires more overhead than a binary search tree.

The present implementation uses the Java 2 TreeMap class which implements a red black tree for general usage. This event list implementation is not efficient.

Constructor Summary

Constructors

Constructor and Description
RedblackTree()

Method Summary

Modifier and Type	Method and Description
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.
<E extends Event> E	getFirstOfClass(java.lang.Class<E> cl) Returns the first event of the class E (a subclass of Event) in the event list.
Event	getFirstOfClass(java.lang.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).
java.util.Iterator<Event>	iterator()
java.util.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).
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

RedblackTree

public RedblackTree()

Method Detail

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(java.lang.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 is 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

getFirstOfClass

public <E extends Event> E getFirstOfClass(java.lang.Class<E> cl)

Description copied from interface: EventList

Returns the first event of the class E (a subclass of Event) in the event list. If no such event is 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

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 java.lang.String toString()

Overrides:

toString in class java.lang.Object

iterator

public java.util.Iterator<Event> iterator()

Specified by:

iterator in interface java.lang.Iterable<Event>

listIterator

public java.util.ListIterator<Event> 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

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