Package org.simplesim.core.scheduling

Class HeapEventQueue<E>

java.lang.Object
org.simplesim.core.scheduling.HeapEventQueue<E>
Type Parameters:
E - event type
All Implemented Interfaces:
EventQueue<E>
public class HeapEventQueue<E> extends Object
Priority queue implementation of the EventQueue interface.

Adapter class wrapping a PriorityQueue to hold the data, internally stored in a binary heap structure. Most operations are done in O(log n), but searches like dequeue(E) and getTime(E) take O(n). Look up of the minimal time getMin() is done in O(1) but dequeuing has a complexity of O(log n).

Note: This queue type seems to perform best for dequeuing (and requeuing) single events with minimal time stamp (dequeue()). It might be suitable as local and global event queue.

See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    HeapEventQueue()
    Default constructor initializing the queue

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

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • HeapEventQueue

      public HeapEventQueue()
      Default constructor initializing the queue

  • Method Details

    • getMin

      public Time getMin()
      Description copied from interface: EventQueue
      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!)

    • dequeue

      public E dequeue()
      Description copied from interface: EventQueue
      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:

    • getTime

      public Time getTime(E event)
      Description copied from interface: EventQueue
      Gets the time of the given event but does not dequeue it.
      Specified by:
      getTime in interface EventQueue<E>
      Parameters:
      event - the event to retrieve the time for
      Returns:
      time stamp of the event or null if the event does not exist

    • isEmpty

      public boolean isEmpty()
      Description copied from interface: EventQueue
      Checks if the queue is empty.
      Specified by:
      isEmpty in interface EventQueue<E>
      Returns:
      true if the queue is empty, false otherwise

    • size

      public int size()
      Description copied from interface: EventQueue
      Returns the number of elements in the queue.
      Specified by:
      size in interface EventQueue<E>
      Returns:
      number of queue entries

    • dequeue

      public Time dequeue(E event)
      Description copied from interface: EventQueue
      Removes the entry of the given event.
      Specified by:
      dequeue in interface EventQueue<E>
      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

    • enqueue

      public void enqueue(E event, Time time)
      Description copied from interface: EventQueue
      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.

      Specified by:
      enqueue in interface EventQueue<E>
      Parameters:
      event - the event to be added to the queue
      time - the time stamp of the event, must be a future time

    • dequeueAll

      public List<E> dequeueAll(Time time)
      Description copied from interface: EventQueue
      Dequeues all elements with the given time stamp.

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

      Specified by:
      dequeueAll in interface EventQueue<E>
      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

    • dequeueAll

      public List<E> dequeueAll()
      Description copied from interface: EventQueue
      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!

      Specified by:
      dequeueAll in interface EventQueue<E>
      Returns:
      a list containing all events with the minimum time stamp or an empty list if the event queue is empty.
      See Also:

    • toString

      public String toString()
      Overrides:
      toString in class Object