Package org.simplesim.core.scheduling

Interface EventQueue<E>

Type Parameters:
E - type of events to be stored in the queue
All Known Implementing Classes:
HashedBucketQueue, HeapBucketQueue, HeapEventQueue, MultiLevelBucketQueue, MultiLevelEventQueue, SortedBucketQueue, SortedEventQueue
public interface EventQueue<E>
Basic event queue interface for all queue implementations of the scheduling package.

Event queues are priority queue data structures. In the realm of discrete event simulation, the scheduling of events has been identified as a major bottleneck (taking up to 40% computing time in large simulation models). Thus, this interface is designed to cover all necessary functionality in a minimalistic way. During simulation #enqueue(E, Time), #dequeueAll(Time) and #getMin() are used most often, presumably. A requeue operation can be done by dequeuing an event and then enqueuing it again with a different time stamp.

Event queues might not be synchronized. Accessing unsynchronized event queues from different threads may result in non-deterministic behavior. Please check the documentation of the event queue you are going to use or synchronize externally.

Please note that event queues have (injective) one-to-one mapping: There may be several events with equal time stamps, but no two events that are equal. In other words: There must be only one time stamp per event!

  • Method Summary

    Modifier and Type
    Method
    Description
    E
    dequeue()
    Dequeues the event with the smallest time stamp.
    Time
    dequeue(E event)
    Removes the entry of the given event.
    List<E>
    dequeueAll()
    Dequeues all elements with the smallest time stamp.
    List<E>
    dequeueAll(Time time)
    Dequeues all elements with the given time stamp.
    void
    enqueue(E event, Time time)
    Enqueues an event at the given time.
    Time
    getMin()
    Gets the minimal time stamp.
    Time
    getTime(E event)
    Gets the time of the given event but does not dequeue it.
    boolean
    isEmpty()
    Checks if the queue is empty.
    int
    size()
    Returns the number of elements in the queue.

  • Method Details

    • getMin

      Time getMin()
      Gets the minimal time stamp.

      An empty event queue may result in non-deterministic behavior and is not checked!

      Returns:
      current minimal time stamp (does not test if queue is empty!)

    • isEmpty

      boolean isEmpty()
      Checks if the queue is empty.
      Returns:
      true if the queue is empty, false otherwise

    • size

      int size()
      Returns the number of elements in the queue.
      Returns:
      number of queue entries

    • getTime

      Time getTime(E event)
      Gets the time of the given event but does not dequeue it.
      Parameters:
      event - the event to retrieve the time for
      Returns:
      time stamp of the event or null if the event does not exist

    • enqueue

      void enqueue(E event, Time time)
      Enqueues an event at the given time.

      Note that only distinct events may be added to the queue. If the very same event already exists, it may be overwritten.

      Parameters:
      event - the event to be added to the queue
      time - the time stamp of the event, must be a future time

    • dequeue

      Time dequeue(E event)
      Removes the entry of the given event.
      Parameters:
      event - the event to be removed from the queue
      Returns:
      time stamp of the dequeued event or null if the event was not part of the queue

    • dequeue

      E dequeue()
      Dequeues the event with the smallest time stamp.

      If there are several events with the same time stamp, the result can be any of these events

      Returns:
      event with the smallest time stamp or null if the queue is empty
      See Also:

    • dequeueAll

      List<E> dequeueAll()
      Dequeues all elements with the smallest time stamp. A call to this method is equivalent to dequeueAll(getMin()).

      An empty event queue may result in non-deterministic behavior and is not checked!

      Returns:
      a list containing all events with the minimum time stamp or an empty list if the event queue is empty.
      See Also:

    • dequeueAll

      List<E> dequeueAll(Time time)
      Dequeues all elements with the given time stamp.

      An empty event queue may result in non-deterministic behavior and is not checked!

      Parameters:
      time - the time stamp of the events to dequeue
      Returns:
      a list containing all events with this time stamp or an empty list if there are not events at the given time