Queue curve rework - Githubissues

Reworks the curve queue to make it more intuitive to use and more efficient in certain situations.

In the original design by @Tomatower , elements in a curved queue are mostly accessed by requesting all elements in a timespan (e.g. all elements between t1 == 0 and t2 == 5). You could then iterate through these elements to process them. front(t) or pop(t) access (like in "normal" queues) to retrieve/remove the front element at a time t was not possible.

However, there are a few problems with this in practice which made the queue unintuitive to use. If the elements are processed one at a time, the requirement for a timespan puts a burden on the calling code to track which time/elements have already been processed. If the queue is shared by multiple callers, this adds a lot of additional complexity. Furthermore, since popping is not possible, there is no real way to "empty" the queue for a specific timespan, except by tracking this status outside of the queue. Filtering a timespan was also an expensive operation with a complexity of O(n) vs. O(1) for most operations in std::queue.

https://github.com/SFTtech/openage/pull/1609 already introduced a few changes like the addition of front(t), pop_front(t) and empty(t) to address some of these problems, but these only work under the assumption that time is always progressing forward, so they didn't fulfill the basic curve properties. This PR addresses this and also changes the operations logic to make more sense for people familiar with std::queue.

Track lifespan of elements with dead time

Like curve::UnorderedMap, curve::Queue now tracks the lifespan of elements with insertion time (alive) and erasure time (dead). dead is now set when an element is removed by pop_front(t) which makes the element invisible for pops at later times. Elements are also no longer erased from the queue if they are popped.

Change timespan observed by front/pop_front

Previously, the operations front(t) and pop_front(t) only considered elements that were inserted after or at t. However, this meant that e.g. front(2) had no result even if the queue contained elements A and B with insertion times 0 and 1 respectively. Since this was counter-intuitive, these operations will now consider elements inserted until t, i.e. before or at t. In other words, the front element is now the element with the lowest insertion time that is also still alive at t.

Optimizations for common operations

front(t)/pop_front(t)/empty(t)/insert(t) have been optimized for the case that simulation time always progresses forwards, i.e. that the time t always increases for each access, by caching the iterator to the last accessed element. This optimization should cover the normal use case of running a game. Complexity for these operations is then O(1) (vs. O(n) previously).

SFTtech / openage

Queue curve rework #1616