TimeQueue.hpp

A priority queue for timings, always marching forward.

A TimeQueue maintains a fast priority queue where a user inserts a set of items with a time that they should be triggered and can request information of which comes next.

Create a TimeQueue with:

TimeQueue time_queue;

By default TimeQueue operates on unsigned integers (of type size_t), but you can specify a different type with a template parameter, such as:

TimeQueue<std::string> my_string_queue;

Once a TimeQueue is created, you can insert items with their trigger time specified as a double value, such as:

time_queue.Insert(0, 130.0); time_queue.Insert(1, 150.0); time_queue.Insert(2, 140.0);

The internal time of a time_queue starts at 0.0. Whenever you want to know what happens next you can run:

size_t next_id = time_queue.Next();

This will set next_id to the earliest occuring event, removing that event from the queue and updating the current time to the time of that event. You can check the current time with:

double cur_time = time_queue.GetTime();

Important note for EFFICIENCY: You must always insert events for after the current time, but the longer after the current time (and the more other insertions that occuer between each insertion and its trigger) the faster the TimeQueue will run. If an item will be triggered immediately, you should try to avoid putting it in the TimeQueue.

Note

Status: ALPHA

template<typename T = size_t> class TimeQueue

#include <TimeQueue.hpp>

A TimeQueue is used to track when “items” are ready. Insert() items with the time they should be triggered. Must be at least min_wait in the future.

Public Functions

inline TimeQueue(double _min_wait = std::numeric_limits<double>::max() / 2)

inline double GetTime() const

inline double GetMinWait() const

inline size_t GetSize() const

inline void SetTime(double _time)

inline void Clear(): Empty the TimeQueue.

inline void Reset(): Empty the TimeQueue and start over at time zero.

inline void Insert(T in_item, double trigger_time): Add a new item to the TimeQueue.

inline T Front(): Grab the next item from the TimeQueue, but don’t remove it.

inline T Next(): Remove and return the next item from the TimeQueue.

inline bool Next(T &out_item): Remove the next item from TimeQueue, setting argument to it; return whether items remain.

inline std::string AsString()

Private Functions

inline bool RefillQueue()

inline void UpdateMinimum(double new_min)

Private Members

double cur_time = 0.0: What time are we up to?

double min_wait = 1.0: Minimum amount of time for the next event.

vector<ItemInfo> item_queue: Sorted events to be triggered.

vector<ItemInfo> item_buffer: Unsorted events out of current range.

size_t pos = 0: What position are we up to in the item_queue?

struct ItemInfo

Public Functions

inline bool operator<(const ItemInfo &_in) const

Public Members

T item

double timing