Class MultiLevelBucketQueue<E>
- Type Parameters:
E
- Event type
- All Implemented Interfaces:
EventQueue<E>
Both multi-level queue implementations are based on the article "MList: An efficient pending event set structure for discrete event simulation" by Rick Siow Mong Goh and Ian Li-Jin Thng. They are structured in three tiers:
- current event tier for events before
minTimerTier2
- near future tier for events since
minTimeTier2
but beforeminTimeTier3
- far future tier for events from
minTimeTier3
tomaxTimeTier3
MultiLevelBucketQueue
uses buckets of events of the same time-stamp.
This is versatile if there are many event with the same time-stamp.
MultiLevelEventQueue
uses EventQueueEntry
to couple time and
events. This is versatile if there are many events with different time-stamps.
- See Also:
-
Constructor Summary
ConstructorsConstructorDescriptionMultiLevelBucketQueue
(int chunkSize) Constructor to enable setting the average chunk size of the second sorting tier. -
Method Summary
Modifier and TypeMethodDescriptiondequeue()
Dequeues the event with the smallest time stamp.Removes the entry of the given event.Dequeues all elements with the smallest time stamp.dequeueAll
(Time time) Dequeues all elements with the given time stamp.void
Enqueues an event at the given time.getMin()
Gets the minimal time stamp.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.
-
Constructor Details
-
MultiLevelBucketQueue
public MultiLevelBucketQueue(int chunkSize) Constructor to enable setting the average chunk size of the second sorting tier.Only for optimization purpose, see documentation in
refillTier2
. Generally, use default constructor.- Parameters:
chunkSize
-
-
MultiLevelBucketQueue
public MultiLevelBucketQueue()
-
-
Method Details
-
isEmpty
public boolean isEmpty()Description copied from interface:EventQueue
Checks if the queue is empty.- Specified by:
isEmpty
in interfaceEventQueue<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 interfaceEventQueue<E>
- Returns:
- number of queue entries
-
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!
- Specified by:
getMin
in interfaceEventQueue<E>
- Returns:
- current minimal time stamp (does not test if queue is empty!)
-
enqueue
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 interfaceEventQueue<E>
- Parameters:
event
- the event to be added to the queuetime
- the time stamp of the event, must be a future time
-
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
- Specified by:
dequeue
in interfaceEventQueue<E>
- Returns:
- event with the smallest time stamp or null if the queue is empty
- See Also:
-
dequeueAll
Description copied from interface:EventQueue
Dequeues all elements with the smallest time stamp. A call to this method is equivalent todequeueAll(getMin())
.An empty event queue may result in non-deterministic behavior and is not checked!
- Specified by:
dequeueAll
in interfaceEventQueue<E>
- Returns:
- a list containing all events with the minimum time stamp or an empty list if the event queue is empty.
- See Also:
-
dequeueAll
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 interfaceEventQueue<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
-
dequeue
Description copied from interface:EventQueue
Removes the entry of the given event.- Specified by:
dequeue
in interfaceEventQueue<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
-
getTime
Description copied from interface:EventQueue
Gets the time of the given event but does not dequeue it.- Specified by:
getTime
in interfaceEventQueue<E>
- Parameters:
event
- the event to retrieve the time for- Returns:
- time stamp of the event or null if the event does not exist
-