Last time I had to do something similar (for TCP reassembly) I simply used a sorted array.
I didn't think it though fully, but did you consider using a bit set only storing gap/non-gap transitions and vice versa then compressing it in a rank-select data structure? The even-odd result of a rank query will tell you if you are in a gap or not. It should also be possible to use select to find the closest hole.
The problem is that AFAIK rank-select structures cannot be modified, so you will need to regenerate it from scratch at every update. That (or an hybrid scheme) will work only if updates are rare enough.
That makes sense. I tried dense bit sets but storing a transition bitset could be interesting. That sounds similar to an inversion list compressed into a bitset.
The rank-select sounds like a great idea and seems like it would work great for mostly static intervals, but updates are pretty common in my case.
Comments
Last time I had to do something similar (for TCP reassembly) I simply used a sorted array.
I didn't think it though fully, but did you consider using a bit set only storing gap/non-gap transitions and vice versa then compressing it in a rank-select data structure? The even-odd result of a rank query will tell you if you are in a gap or not. It should also be possible to use select to find the closest hole.
The problem is that AFAIK rank-select structures cannot be modified, so you will need to regenerate it from scratch at every update. That (or an hybrid scheme) will work only if updates are rare enough.
That makes sense. I tried dense bit sets but storing a transition bitset could be interesting. That sounds similar to an inversion list compressed into a bitset.
The rank-select sounds like a great idea and seems like it would work great for mostly static intervals, but updates are pretty common in my case.