I built a project that implemented intervaltree in Rust and exposed PyO3 bindings as a drop-in replacement for Python's native intervaltree. It is significantly faster, and I will be adding more features, such as AVL and red-black trees for balancing.
eru 4 days ago [-]
If you want balanced trees, have a look at what Rust's standard library does with BTreeMap.
jeffparsons 4 days ago [-]
And with a little work you can even use them to map ranges of keys to values in a way that's reminiscent of interval trees — e.g. https://crates.io/crates/rangemap. (Disclosure: that's my crate.)
eru 4 days ago [-]
Nice! I was only suggesting considering BTrees because they also play nice with caches, instead of the more conventional binary tree balancing mechanisms.
airstrike 4 days ago [-]
I love that crate! Kudos
Epa095 4 days ago [-]
What is the native intervaltree, is it [1] you mean? Do you also support the set operations? And can it be pickled safely?
Unfortunately it’s implemented on top of std::set/std::map and I’ve had problems with heap blow up on large maps. This project looks like it uses 32 bit indices into a vector for backing store.
2Pacalypse- 4 days ago [-]
Pretty cool to have this in Rust, might be useful if/when I decide to move some functionality from TS -> Rust.
1: https://pypi.org/project/intervaltree/
Unfortunately it’s implemented on top of std::set/std::map and I’ve had problems with heap blow up on large maps. This project looks like it uses 32 bit indices into a vector for backing store.
In the meantime, I have this impelemented in TypeScript in case anyone else will find it useful: https://github.com/ShieldBattery/node-interval-tree
Plus, the account of the one you're linking to only has that one comment in their comment history. So I think the shenanigans lie there
https://en.wikipedia.org/wiki/Interval_tree