"range query" is different from "find next availability".
Do consider to explicitly use 16(-ish) bit pointers instead of native sized ones, and go for a SIMD-friendly binary trie; with some degree of implicitnes where it is addressed as if it was storing a set of mutually prefix-free variable-length (capped to something though, like 32 in your example) bitstrings (no entry is a prefix of another entry), but you're not looking to distinguish `{00, 01}` from `{0}`.
Operations are restricted, but it should be able to be very fast for "find first empty of at least X large starting at or after Y" as well as "clear from X to Y inclusive" and "add/mark from X to Y inclusive".
I think this is an interesting idea. It might have some of the same problems as the dense bitset designs I've tried so far though but I'd like to try it out. Is there a detailed description of this anywhere?
Not yet; I haven't gotten around to doing any of the implementing yet.
The main difference is that this is trying to lock it's big-O's to the number of ranges, assuming that the data will not benefit (much) from dumb dense bitset representation.
Could you separate out the data structure, i.e. keep your BTreeMap<u32, u32> for intervals, but add a Vec<u32> for available slots. Update both on insert/remove, then for range queries use the Vec<u32>?
Sorry if this is dumb I'm a> not a rustian and b> not really a computer scientist lol
Definitely possible! I tried doing something similar which stored the ranges in a single `Vec<(u32, u32)>` but found the performance a bit worse than just using the ordered map.
Do consider to explicitly use 16(-ish) bit pointers instead of native sized ones, and go for a SIMD-friendly binary trie; with some degree of implicitnes where it is addressed as if it was storing a set of mutually prefix-free variable-length (capped to something though, like 32 in your example) bitstrings (no entry is a prefix of another entry), but you're not looking to distinguish `{00, 01}` from `{0}`.
Operations are restricted, but it should be able to be very fast for "find first empty of at least X large starting at or after Y" as well as "clear from X to Y inclusive" and "add/mark from X to Y inclusive".