====== Events Data Structure ======

This page is to make a suggestion for a new events data structure to achieve the following goals:
  * avoid the usage of std::list
  * store events such that we can quickly retrieve the k-th last event for a specific instrument (for variable k)
  * generally make this part of the code more beautiful and usable

=== Abstraction ===

Currently we just use a plain std::list<Event*>. Probably we should give it a dedicated type to make the code clearer and also facilitate future refactoring and avoiding bugs. I suggest EventsDS as the type name.

=== Replacement of std::list ===

As the events don't need to be in a specific order, we can replace std::list by a std::vector using a standard technique of swapping the element to be removed to the back and doing a pop_back(). This is only possible if the swapping is cheap. Currently the std::list contains pointers, so swapping is cheap. Also Event contains only some bytes (something around 30 maybe), so swapping is also still reasonably cheap.

=== Access to the k-th last event ===

To access the k-th last event, we have two extreme (with respect to running time and memory tradeoff) options:
  * for each instrument store its last events
  * just give IDs to each event and then linearly search for the k-th largest ID

If we know that we only need the query for the k-th last event for specific instruments, we can restrict storing this information to those instruments.

=== Misc Comments ===

  * The list currently contains pointers because of polymorphism of Event.
  * IRC conversation: [[https://www.drumgizmo.org/irc-logs/drumgizmo.log.2020_01_11|here]]