[luizfelberti]

Since you're using Rust, the Cranelift JIT compiler implements something like this[0] to construct an e-graph for its expression rewriting subsystem called ISLE, however if I'm not mistaken it is for disjoint sets (not intervals), and therefore it does not deal with ordering.

Maybe you can adapt it for your use case and add those new constraints in?

Keep in mind though that this was not written to be in the hot-path itself, you could probably do significantly better by pouring your soul into the SIMD rabbit hole (though SIMD in Rust is usually very annoying to write)

Best of luck, hope this helps!

[0] https://github.com/bytecodealliance/wasmtime/blob/7dcb9bd6ea...

[grovesNL]

Thanks for the reference! This looks like an implementation of a disjoint set/union-find data structure. I think it could be an interesting direction to explore by adapting union-find to handle intervals efficiently, or maybe apply some of the union-find amortized operations tricks to another interval-based tree or similar.