#no-std #ranges #disjoint-set #union-find

no-std range_union_find

A union-find data structure for ranges

9 releases

0.4.4 Jan 3, 2023
0.4.3 Oct 23, 2022
0.4.2 May 19, 2022
0.4.1 Jul 2, 2021

#391 in Data structures

50 downloads per month

MIT/Apache

74KB
1.5K SLoC

range_union_find

Crates.io Crates.io License License

This crate implements a union-find data structure for ranges. Currently we support ranges of PrimInts, but we may extend this to other types in the future.

See the API documentation for more information.


lib.rs:

Provides a data structure backed by a vector for unioning ranges of integers. We intelligently merge inserted ranges to minimize required storage.

Example usage:

# use range_union_find::*;
let mut range_holder = IntRangeUnionFind::<u32>::new();
range_holder.insert_range(&(4..=8))?;
range_holder.insert_range(&(6..=10))?;
assert_eq!(range_holder.has_range(&(2..=12))?, OverlapType::Partial(7));
assert_eq!(range_holder.has_range(&(5..=9))?, OverlapType::Contained);
# Ok::<(), RangeOperationError>(())

All the functionality is in the [IntRangeUnionFind] struct (though we may add RangeUnionFind structs for different element types in the future).

Dependencies

~145–420KB