I am thinking through some techniques where by I have an application with a timeline. The timeline plays in real time and at points on that timeline I would like to trigger some actions. There are no interpolation curves between points. This would be used on iOS though I'm sure other platforms offer similar-ish things, for example in JavaScript:

- 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.

1. NSTimer

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.


I would stick with the KISS principle (Keep it simple, stupid) and YAGNI (You aren't going to need it). Start with the NSTimer. It's dead simple to implement and is probably sufficient. Once you have something up and running, if the resolution of an NSTimer isn't sufficient, then think about more complex solutions. But only as complex as they actually need to be. Personally, I think the BST solutions are way overkill. Depending on how many items you have in your queue, doing a linear search forward when the user skips ahead may not be that expensive. Don't assume it is. Try it out (if it's even necessary) and if it's not sufficient, then think about better ways to implement it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.