Comment by eru | Hacker News Reader

Comment by eru | Hacker News Reader

> In Rust this might look something like `BTreeMap<u32, u32>` with start being the key and the end being the value.

This approach would indeed be slow. You can improve your approach by switching to a `BTreeMap<u32, bool>` with the key being a border between intervals and the value telling you whether the next interval is 'in' or 'out'. (And the interval starting at logical minus infinity being eg 'out' by default.)

You can test whether a specific point is 'in' or 'out' by using something like `upper_bound` [0] to find the key just before your query point (and the value associated with that key tells you whether your query point is 'in' or 'out'.)

See https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...

Insert and remove are pretty simple to code up too, and looking for next availability after a query point is almost trivial: take the cursor you get from `upper_bound`, and if it's not already `out`, advance the cursor by one. (This is assuming you keep the invariant that `in` and `out` intervals interleave. Ie you merge any adjacent intervals of the same kind, by just removing the key-value pair for the second interval from the BTreeMap. Otherwise, you might have to advance your cursor a few more times, perhaps cleaning up your intervals as you go to restore the invariant.) You can also implement merging of two interval maps represented this way pretty efficiently.

I read elsewhere that you also want eg the next free block that's at least n items long, or the next occupied block of at least some minimum size.

You can do these operations by augmenting your tree nodes with caches of eg what's the longest free block under and the longest occupied block under them.

You can use that cache to find the next free interval of at least some specified size quickly, and you can rebuild that cache quickly, too, whenever you make any modification to the tree. (Quickly here meaning in O(number of layers).)

This sounds interesting! From my understanding it’s similar to an inversion list but storing explicit in/out instead of deriving it from the element’s rank (i.e., index if it’s stored as an ordered `Vec`) mod 2.

I’m not too worried about storage requirements though so I wonder if having to search the adjacent node to determine the duration vs. The current representation. I could see how this could improve update performance though.

Augmenting tree nodes and/or keeping track of min/max duration across coarser regions seems like a good approach. I could see each layer being represented in-tree like you described, or as separate layers each with their own granularity, where they could help to tighten bounds during range queries.

Do you know of any libraries implementing this?

Yes, it's basically an inversion list, but organised as a tree.

If you write your own btree, you can drop storing the explicit in/out and get it from the element's rank. I was suggesting the explicit value mostly to be able to re-use Rust's existing standard library BTreeMap, where you don't have access to the rank (as far as I can tell).

You could also use something like a 'log structured merge tree' to store inversion lists as (a collection of) Rust vectors.

> I could see each layer being represented in-tree like you described, or as separate layers each with their own granularity, where they could help to tighten bounds during range queries.

I would suggest keeping them in-tree, so you only need to chase pointers once. And your invariants are much simpler, because whenever you make any changes to the btree you are already touching exactly the same nodes you might need to update for the cache.

> Do you know of any libraries implementing this?

I've looked around a bit, but didn't find much for Rust. There's https://codeforces.com/blog/entry/68419 which comes close.

For Haskell, https://hackage.haskell.org/package/dual-tree should do pretty much exactly what we talked about.

I've only looked very briefly. So I'm sure there's lot I missed that you can maybe find with different keywords or so.

I briefly considered implementing my own version for Rust by hacking up the standard library's BTreeMap. I got as far as extracting the BTreeMap code from the standard library and making it compile and pass tests in its own crate, but then got distracted by actual work. :)

> I’m not too worried about storage requirements though so I wonder if having to search the adjacent node to determine the duration vs. The current representation. I could see how this could improve update performance though.

Well, going to the next node (or previous node) should be cheap on average.

You could cache the duration in the nodes, if you wanted to, at the cost of making your invariants a bit more annoying (and slightly more expensive to update).

Because getting to the next node should be so cheap on average, I can't really predict whether storing your durations also with your nodes would actually improve performance.

Btw, what I described as a 'cache' is explored in the discussion at https://news.ycombinator.com/item?id=24385095 as 'Monoid cached trees'.

Reply on news.ycombinator.com