- NSTimer can be used conceptually similar to `setTimeout` - CADiplayLink is conceptually similar to `requestAnimationFrame`
I will be using iOS terminology to convey some different approaches I am thinking of.
This would seem to be the most naive means to accomplish this. Simply read the data representing the timeline and and schedule actions to run based on the time they were set. If the timeline is paused or restated, invalidate and reschedule the events accordingly. I am aware that NSTimer has resolution restrictions though I do not think 100ms +/- in the case of this application would be consequential.
2. CADisplayLink + Queue
Using CADisplayLink to calculate elapsed time invalidating as appropriate for pause/play.
The idea I am toying with here is reading the start time sorted data from the timeline and dropping that into a Queue. So now I have a FIFO queue of events inserted by earliest time to latest time. Every tick of the CADisplayLink handler, calculate the elapsed time and peek at the queue to see if the next item in the queue is less than or equal to the current time. If this is true, then remove the item from the queue and continue for every tick testing the next item in the queue.
This seems like it would provide the best resolution. In the case where we jump in time, the Queue would need to be rebuilt accordingly.
3. CADisplayLink + Binary Search Tree
Similar to the Queue implementation above to get the elapsed time, but instead of reading a queue, search a Binary Tree for an event that is less than or equal to the elapsed time. The BST removes the need to reconstruct anything for pause / play or jumping in time however we would not want to repeat playing events for example, if an event takes place at time 5 that has been triggered and we are now at time 7 and no other events were scheduled, then the "nearest less than or equal event would be the event at time 5, but it has already been played.
Perhaps storing the "triggered" events into a dictionary would work. If the lookup into that dictionary is affirmed, then ignore the event. The act of scrubbing the timeline would invalidate the event storage so the "closest" in time event would be played next if that feature was desirable.
4. CADisplayLink + Binary Search Tree + Array
This would be a modification on the use of the Binary Search Tree, the idea here would be to build the BST from the Sorted Array of markers. Now instead of searching the BST every tick, we can basically determine the
Next Marker based on the elapsed time/play head time. So the values associated to the BST would be the index in the array for that time. Thus if we are just letting things play the next marker is
array[current index + 1]. If the user scrubs the timeline we go back to the BST to find the nearest marker to their time and then we know what the next marker is once they resume playback. We can also then determine if we would like to apply the event if there scrubbed between 2 events/markers
These are four ideas I have been mulling over, I am curious if there are any other techniques or alternative ways to think about that problem that I have missed.
Right now I'm thinking 4 has the the most benefits. BST provides a faster search than going O(N) though the array of markers. While at the same time the array gives us O(1) access to the next event once we find where we are in time. There is of course the initial overhead of build the BST to begin with, so that's a down side. It should save on time searches though, so it should be worth it.