RedblackTree (Java Libraries for Stochastic Simulation)

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()

Constructors
Constructor and Description
`RedblackTree()`

Method Summary

Methods
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

- 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

Class RedblackTree

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

RedblackTree

Method Detail

clear

add

addFirst

addBefore

addAfter

getFirst

getFirstOfClass

getFirstOfClass

remove

removeFirst

toString

iterator

listIterator

isEmpty