14 unstable releases (3 breaking)
0.4.0 


0.3.2  Apr 19, 2023 
0.2.2  Apr 10, 2023 
0.1.1  Jan 5, 2023 
0.0.6  Dec 29, 2022 
#156 in Data structures
64 downloads per month
120KB
2.5K
SLoC
range_bounds_map
This crate provides RangeBoundsMap
and RangeBoundsSet
, Data
Structures for storing nonoverlapping intervals based of BTreeMap
.
Example using Range
s
use range_bounds_map::RangeBoundsMap;
let mut map = RangeBoundsMap::new();
map.insert_strict(0..5, true);
map.insert_strict(5..10, false);
assert_eq!(map.overlaps(&(2..12)), true);
assert_eq!(map.contains_point(&20), false);
assert_eq!(map.contains_point(&5), true);
Example using a custom RangeBounds
type
use std::ops::{Bound, RangeBounds};
use range_bounds_map::RangeBoundsMap;
#[derive(Debug)]
enum Reservation {
// Start, End (InclusiveInclusive)
Finite(u8, u8),
// Start (Exclusive)
Infinite(u8),
}
// First, we need to implement RangeBounds
impl RangeBounds<u8> for Reservation {
fn start_bound(&self) > Bound<&u8> {
match self {
Reservation::Finite(start, _) => {
Bound::Included(start)
}
Reservation::Infinite(start) => {
Bound::Excluded(start)
}
}
}
fn end_bound(&self) > Bound<&u8> {
match self {
Reservation::Finite(_, end) => Bound::Included(end),
Reservation::Infinite(_) => Bound::Unbounded,
}
}
}
// Next we can create a custom typed RangeBoundsMap
let reservation_map = RangeBoundsMap::try_from([
(Reservation::Finite(10, 20), "Ferris".to_string()),
(Reservation::Infinite(20), "Corro".to_string()),
])
.unwrap();
for (reservation, name) in reservation_map.overlapping(&(16..17))
{
println!(
"{name} has reserved {reservation:?} inside the range 16..17"
);
}
for (reservation, name) in reservation_map.iter() {
println!("{name} has reserved {reservation:?}");
}
assert_eq!(
reservation_map.overlaps(&Reservation::Infinite(0)),
true
);
Key Definitions:
Invalid Ranges
Within this crate, not all ranges are considered valid ranges. The definition of the validity of a range used within this crate is that a range is only valid if it contains at least one value of the underlying domain.
For example, 4..6
is considered valid as it contains the values
4
and 5
, however, 4..4
is considered invalid as it contains
no values. Another example of invalid range are those whose start
values are greater than their end values. such as 5..2
or
100..=40
.
Here are a few examples of ranges and whether they are valid:
range  valid 

0..=0  YES 
0..0  NO 
0..1  YES 
9..8  NO 
(0.4)..=(0.2)  NO 
..(3)  YES 
0.0003..  YES 
..  YES 
400..=400  YES 
Overlap
Two ranges are "overlapping" if there exists a point that is contained within both ranges.
Touching
Two ranges are "touching" if they do not overlap and there exists no
value between them. For example, 2..4
and 4..6
are touching but
2..4
and 6..8
are not, neither are 2..6
and 4..8
.
Merging
When a range "merges" other ranges it absorbs them to become larger.
Further Reading
See Wikipedia's article on mathematical Intervals: https://en.wikipedia.org/wiki/Interval_(mathematics)
Improvements/Caveats
 I had to create a new trait: [
TryFromBounds
] rather than usingTryFrom<(Bound, Bound)>
(relys on upstream to impl, see this thread)
Credit
I originally came up with the StartBound
: Ord
bodge on my own,
however, I later stumbled across rangemap
which also used a
StartBound
: Ord
bodge. rangemap
then became my main source
of inspiration.
Later I then undid the Ord
bodge and switched to my own fullcode
port of BTreeMap
, inspired and forked from copse
, for it's
increased flexibility.
Origin
The aim for this library was to become a more generic superset of
rangemap
, following from this
issue and this
pull request in
which I changed rangemap
's RangeMap
to use RangeBounds
s as
keys before I realized it might be easier and simpler to just write it
all from scratch.
Similar Crates
Here are some relevant crates I found whilst searching around the topic area:
 https://docs.rs/rangemap
Very similar to this crate but can only use
Range
s andRangeInclusive
s as keys in it'smap
andset
structs (separately).  https://docs.rs/btreerangemap
 https://docs.rs/ranges
Cool library for fullygeneric ranges (unlike std::ops ranges), along
with a
Ranges
datastructure for storing them (Vecbased unfortunately)  https://docs.rs/intervaltree Allows overlapping intervals but is immutable unfortunately
 https://docs.rs/nonoverlapping_interval_tree
Very similar to rangemap except without a
gaps()
function and only forRange
s and notRangeInclusive
s. And also no fancy merging functions.  https://docs.rs/unboundedintervaltree
A data structure based off of a 2007 published paper! It supports any
RangeBounds as keys too, except it is implemented with a nonbalancing
Box<Node>
based tree, however it also supports overlapping RangeBounds which my library does not.  https://docs.rs/rangetree I'm not entirely sure what this library is or isn't, but it looks like a custom redblack tree/BTree implementation used specifically for a Range Tree. Interesting but also quite old (5 years) and uses unsafe.
Dependencies
~1.2–1.7MB
~38K SLoC