Intervaltree with Rust Back End

athekunal 4 days ago | parent | next [-]

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 a day ago | parent | next [-]

If you want balanced trees, have a look at what Rust's standard library does with BTreeMap.

▲

jeffparsons a day ago | parent [-]

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 a day ago \| parent \| next [-]
		Nice! I was only suggesting considering BTrees because they also play nice with caches, instead of the more conventional binary tree balancing mechanisms.
	▲	airstrike 21 hours ago \| parent \| prev [-]
		I love that crate! Kudos

▲

Epa095 a day ago | parent | prev | next [-]

What is the native intervaltree, is it [1] you mean? Do you also support the set operations? And can it be pickled safely?

1: https://pypi.org/project/intervaltree/

▲

stefanka a day ago | parent | prev [-]

Will you publish it as a crate too?

▲

everybodyknows 10 hours ago | parent | prev | next [-]

It would be helpful to indicate in the README.md which variant of the data structure is used:

https://en.wikipedia.org/wiki/Interval_tree

▲

2Pacalypse- a day ago | parent | prev | next [-]

Pretty cool to have this in Rust, might be useful if/when I decide to move some functionality from TS -> Rust.

In the meantime, I have this impelemented in TypeScript in case anyone else will find it useful: https://github.com/ShieldBattery/node-interval-tree

▲

croemer 20 hours ago | parent [-]

Did you intend this to be a comment on https://news.ycombinator.com/item?id=45821737 with the first line as a quote?

	▲	griffzhowl 15 hours ago \| parent [-]
		The comment you're linking to is younger than the comment you're replying to. 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

▲

vswaroop04 a day ago | parent | prev | next [-]

Pretty nice to have this in Rust could come in handy if I decide to migrate some functionality from TypeScript to Rust later on.

▲

jonstewart 21 hours ago | parent | prev [-]

In C++ there’s the Boost Interval Container Library, which has an excellent API: https://www.boost.org/doc/libs/latest/libs/icl/doc/html/inde...

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.