Allocation-free min priority queue which schedules a finite set of events.

event_queue.h

#pragma once

#include <cstdint>
#include <limits>
#include <type_traits>

namespace audio {

/**
Allocation-free min priority queue which schedules a finite set of events.
Used to find the first event (smallest timestamp) to happen now or in the future.

Template parameters:
- EventID must be an (old or new-style) enum with a final COUNT field.
  By convention, the first element is EndOfCallback.

If you use this as an object field in a callback class,
you can schedule events ("end of callback", tracker ticks, wavetable steps, etc.)
which persist across callback method calls.

The callback method can act like a state machine (or possibly coroutine)
which simulates executing 1 cycle at a time and handling events as they occur,
and suspending at arbitrary points in time (using EventID::EndOfCallback).

----

Generally, in the owner callback object's constructor:
- Enqueue (set_timeout()) recurring events like engine ticks

Every time the owner callback is called:
- call reset_now()
- Enqueue (set_timeout()) EndOfCallback after a known number of cycles
- Use an infinite loop to call next_event():
    - If EndOfCallback is returned, return.
    - For other events, perform processing and enqueue more events as needed.

An attempt for me to do the same thing as FamiTracker, but in an understandable way.
*/
template<typename EventID>
class EventQueue {
public:
    // Types
    using EventInt = std::underlying_type_t<EventID>;

    // (or u64?)
    using CycleT = uint32_t;

    // private:
    // Fields
    static CycleT const NEVER = std::numeric_limits<CycleT>::max();
    CycleT times[EventID::COUNT];   // fill with NEVER
    CycleT now = 0;

public:
    EventQueue() {
        for (auto & time : times) {
            time = NEVER;
        }
    }

    // Methods

    /**
    Prevents internal integer overflow. Has no other effect, and is idempotent.

    Generally, call this method every time you resume the state machine
    (AKA when the owner callback is called), before you set timeout for EventID::EndOfCallback.
    */
    void reset_now() {
        for (auto & time_cyc : times) {
            if (time_cyc != NEVER) {
                time_cyc -= now;
            }
        }
        now = 0;
    }

    /**
    Schedules an event to happen now (t=0) or in the future.
    This event_id will be returned in a future call to next_event().

    If you call set_timeout on the same event ID twice without dequeueing the old one,
    the previous event schedule will be dropped.
    */
    void set_timeout(EventID event_id, CycleT in_how_long) {
        times[(EventInt) event_id] = now + in_how_long;
    }

    // TODO rename set_timeout to queue_event?
    // TODO add unqueue_event()? remove_event?

    struct RelativeEvent {
        EventID event_id;
        CycleT cyc_elapsed;
    };

    /**
    Finds the first event (smallest timestamp) to happen now or in the future.
    Returns (event ID, cycles since previous event returned by next_event()).
    The returned event is descheduled (moved to the end of time, or NEVER).

    If multiple events happen at the same time, the smallest event ID is returned.
    If no events are queued (all events occur at NEVER),
    the smallest event ID is returned (but you really shouldn't do this).
    */
    RelativeEvent next_event() {
        struct AbsoluteEvent {
            EventInt event_id;
            CycleT time;
        };

        // do I rewrite this in terms of some reduce function instead of a manual loop?
        AbsoluteEvent out;
        {
            EventInt event_id = 0;
            out = {event_id, times[event_id]};
        }

        for (EventInt event_id = 1; event_id < (EventInt) EventID::COUNT; event_id++) {
            if (times[event_id] < out.time) {
                out = {event_id, times[event_id]};
            }
        }

        times[out.event_id] = NEVER;

        CycleT cyc_elapsed = out.time - now;
        now = out.time;

        return RelativeEvent{(EventID) out.event_id, cyc_elapsed};
    }
};

// end namespace
}

test_event_queue.cpp

#include "audio/event_queue.h"

#include "doctest.h"

namespace Event_ {
enum Event {
    EndOfCallback,
    Test1,
    Test2,
    COUNT,
};
}
using Event_::Event;


TEST_CASE("Test that EventQueue is filled with time=NEVER, instead of 0.") {
    using PQ = audio::EventQueue<Event>;
    PQ pq;
    {
        auto event = pq.next_event();
        CHECK(event.event_id == 0);
        CHECK(event.cyc_elapsed == PQ::NEVER);
    }
}


TEST_CASE("Test enqueueing events at t=0.") {
    using PQ = audio::EventQueue<Event>;
    PQ pq;

    pq.set_timeout(Event::EndOfCallback, 10);
    pq.set_timeout(Event::Test1, 30);

    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::EndOfCallback);
        CHECK(event.cyc_elapsed == 10);
    }
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::Test1);
        CHECK(event.cyc_elapsed == 20);
    }
}

TEST_CASE("Test enqueueing events at t=0 with reset_now().") {
    using PQ = audio::EventQueue<Event>;
    PQ pq;

    pq.reset_now();
    pq.set_timeout(Event::EndOfCallback, 10);
    pq.set_timeout(Event::Test1, 30);

    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::EndOfCallback);
        CHECK(event.cyc_elapsed == 10);
    }
    pq.reset_now();
    pq.reset_now();  // This method should be idempotent.
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::Test1);
        CHECK(event.cyc_elapsed == 20);
    }
}


TEST_CASE("Test enqueueing events later in time.") {
    using PQ = audio::EventQueue<Event>;
    PQ pq;

    pq.set_timeout(Event::EndOfCallback, 10);
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::EndOfCallback);
        CHECK(event.cyc_elapsed == 10);
    }
    // now == 10
    pq.set_timeout(Event::Test1, 30);
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::Test1);
        CHECK(event.cyc_elapsed == 30);
    }
    // now == 40
}

TEST_CASE("Test enqueueing events later in time with reset_now().") {
    using PQ = audio::EventQueue<Event>;
    PQ pq;

    pq.reset_now();
    pq.set_timeout(Event::EndOfCallback, 10);
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::EndOfCallback);
        CHECK(event.cyc_elapsed == 10);
    }

    pq.reset_now();
    pq.set_timeout(Event::Test1, 30);
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::Test1);
        CHECK(event.cyc_elapsed == 30);
    }
}


TEST_CASE("Test that identically timed events are dequeued in order of increasing EventID.") {
    using PQ = audio::EventQueue<Event>;
    PQ pq;

    pq.reset_now();

    // Enqueue events out of order.
    pq.set_timeout(Event::Test2, 10);
    pq.set_timeout(Event::EndOfCallback, 10);
    pq.set_timeout(Event::Test1, 10);

    // Assert they're dequeued in increasing order.
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::EndOfCallback);
        CHECK(event.cyc_elapsed == 10);
    }
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::Test1);
        CHECK(event.cyc_elapsed == 0);
    }
    {
        auto event = pq.next_event();
        CHECK(event.event_id == Event::Test2);
        CHECK(event.cyc_elapsed == 0);
    }
}


enum class EventClass {
    EndOfCallback,
    Test1,
    Test2,
    COUNT,
};

TEST_CASE("Test PQ with an enum class.") {
    using PQ = audio::EventQueue<EventClass>;
    PQ pq;

    pq.reset_now();
    pq.set_timeout(EventClass::EndOfCallback, 10);
    {
        auto event = pq.next_event();
        CHECK(event.event_id == EventClass::EndOfCallback);
        CHECK(event.cyc_elapsed == 10);
    }
}