Tag Object

Interval-tree-less interval search on sorted array of linked MIDI events

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

The piano roll editor in my DAW project is based on this interval-tree-less interval search of MIDI … (read more)