I'll explain what my preferred 3D method would look like collapsed to 1D. This was originally for octtrees.
Make a binary tree where node sizes are powers of 2. I'm assuming you can define some "zero" time. To add an interval, first check if it exceeds the tree size and if so, double the size of the tree until it fits inside. Doubling involves making a new root node and inserting the existing tree under it (this was extra fun in 3D). Then decide what node size your interval should reside in. I would use the first power of 2 less than or equal to the interval size. Then insert that interval into all nodes of that determined size. Yes, I allow more than one object in a node, as well as allowing smaller nodes under one containing an object. An object may also span more than one node. In other words the objects (intervals) determine their own position in this tree regardless of others in the tree. It's not perfectly optimal but it allows inserts and deletes in O(logN) as well as intersection checks.
If this sounds not too terrible for the 1D case, I can elaborate on the data structure a bit.
Edit: From another comment "quickly finding the nearest gaps of at least duration X is most important." That possibly invalidates this whole approach.
Thanks! This sounds very similar to the experiment I tried with sieve-tree (https://github.com/Ralith/sieve-tree/) which can store children directly on a node until it reaches some threshold. I had some problems with the nearest query as you mentioned, because children are in arbitrary order and you might have to search multiple tree levels to find the nearest.
Comments
I'll explain what my preferred 3D method would look like collapsed to 1D. This was originally for octtrees.
Make a binary tree where node sizes are powers of 2. I'm assuming you can define some "zero" time. To add an interval, first check if it exceeds the tree size and if so, double the size of the tree until it fits inside. Doubling involves making a new root node and inserting the existing tree under it (this was extra fun in 3D). Then decide what node size your interval should reside in. I would use the first power of 2 less than or equal to the interval size. Then insert that interval into all nodes of that determined size. Yes, I allow more than one object in a node, as well as allowing smaller nodes under one containing an object. An object may also span more than one node. In other words the objects (intervals) determine their own position in this tree regardless of others in the tree. It's not perfectly optimal but it allows inserts and deletes in O(logN) as well as intersection checks.
If this sounds not too terrible for the 1D case, I can elaborate on the data structure a bit.
Edit: From another comment "quickly finding the nearest gaps of at least duration X is most important." That possibly invalidates this whole approach.
Thanks! This sounds very similar to the experiment I tried with sieve-tree (https://github.com/Ralith/sieve-tree/) which can store children directly on a node until it reaches some threshold. I had some problems with the nearest query as you mentioned, because children are in arbitrary order and you might have to search multiple tree levels to find the nearest.