Dynamic interval tree

[cristiano-belloni]

An interval tree that can be dynamically edited (ie add / delete / modify intervals).

[Yomguithereal]

Hello @cristiano-belloni. Why not. Do you have a precise use case in mind? Also do you have an implementation in mind? Dynamic interval tree can be implemented in many ways and must be tailored to use cases typically.

[cristiano-belloni]

Hello @cristiano-belloni. Why not. Do you have a precise use case in mind? Also do you have an implementation in mind? Dynamic interval tree can be implemented in many ways and must be tailored to use cases typically.

My use case would be dynamically scheduling note events within a multi-track timeline. As the timeline is playing (real-time), a user could move the notes and change the interval data structure. Normally this is implemented with a lookahead firing every n milliseconds, and it'd be cool to have a data structure that can return the notes to be played in the next lookahead interval. In his case, there would be many read requests (one per lookahead) and less writes (one per user interaction), so I guess a computationally read-friendly structure would be optimal.

[Yomguithereal]

So I guess your structure would need to a large amount of items? I am saying this because for some use cases, linear search in an array is sometimes faster in JavaScript if you only keep few items.

[Yomguithereal]

What I mean is that the perf tradeoff is rarely obvious in JavaScript for typical interval tree use cases because their implementations are complex and require a lot of operations that muddle the n factor in empirical complexity analysis.

[cristiano-belloni]

What I mean is that the perf tradeoff is rarely obvious in JavaScript for typical interval tree use cases because their implementations are complex and require a lot of operations that muddle the n factor in empirical complexity analysis.

Ah that's good to know. I guess items could be in the 1000s. Not worth it?

[Yomguithereal]

Ah that's good to know. I guess items could be in the 1000s. Not worth it?

Probably not. But since you are going to fire your search very frequently it might still be. Your mileage may vary. But you should definitely try a naive linear search implementation (maybe using something allowing for easy deletion rather than an array) and see if this is a perf bottleneck or not before trying to roll a dynamic interval tree.