Today I will tell you a trick to search an linear pre-sorted array of matching linked MIDI events with an interval without using an interval tree.
Each NoteOn MIDI event has a link pointer to its next NoteOff MIDI event, and each NoteOff MIDI event has a link pointer to its previous NoteOn MIDI event. This is important, because we'll stepping back in time while the search on the base on this interlink-information.
First we'll start at the interval start time with a help of a simple binary search, traverse the array until we'll either hit the interval end time or find a interlink-connection-information for stepping back in the time as new interval start time for a new second iteration (only a single next one!) for to get the full requested interval range.
This is now described here in a very simplified way, but as code it would look like this: https://gist.github.com/BeRo1985/3c50be6480c77dfb320c23f4d88d2f10
Each NoteOn MIDI event has a link pointer to its next NoteOff MIDI event, and each NoteOff MIDI event has a link pointer to its previous NoteOn MIDI event. This is important, because we'll stepping back in time while the search on the base on this interlink-information.
First we'll start at the interval start time with a help of a simple binary search, traverse the array until we'll either hit the interval end time or find a interlink-connection-information for stepping back in the time as new interval start time for a new second iteration (only a single next one!) for to get the full requested interval range.
This is now described here in a very simplified way, but as code it would look like this: https://gist.github.com/BeRo1985/3c50be6480c77dfb320c23f4d88d2f10
The piano roll editor in my DAW project is based on this interval-tree-less interval search of MIDI events. Indeed, it is also possible to work with an self-balanced augmented interval tree here, but that would mean more memory consumption and more maintenance overhead in terms of CPU time.