BinaryTree (Java Libraries for Stochastic Simulation)

java.lang.Object
- umontreal.iro.lecuyer.simevents.eventlist.BinaryTree

All Implemented Interfaces:

java.lang.Iterable<Event>, EventList
```
public class BinaryTree
extends java.lang.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

Constructors
Constructor and Description

BinaryTree()

Constructors
Constructor and Description
`BinaryTree()`

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

Class BinaryTree

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

BinaryTree

Method Detail

isEmpty

clear

add

addFirst

addBefore

addAfter

getFirst

getFirstOfClass

getFirstOfClass

iterator

listIterator

remove

removeFirst

toString