#map #interval-tree #library #data

nightly range_bounds_map

This crate provides [RangeBoundsMap] and [RangeBoundsSet], Data Structures for storing non-overlapping intervals based of [BTreeMap]

15 unstable releases (3 breaking)

0.4.0 Apr 24, 2023
0.3.3 Jan 5, 2024
0.3.2 Apr 19, 2023
0.2.2 Apr 10, 2023
0.0.6 Dec 29, 2022

#756 in Data structures

AGPL-3.0-or-later

120KB
2.5K SLoC

range_bounds_map

License Docs Maintained Crates.io

range_bounds_map_logo

This crate has been renamed to nodit

This crate was renamed from range_bounds_map to discrete_range_map to now nodit due to the old names becoming inaccurate. Please switch to the nodit crate as this crate will no longer be receiving updates.

Old Readme

This crate provides RangeBoundsMap and RangeBoundsSet, Data Structures for storing non-overlapping intervals based of BTreeMap.

Example using Ranges

use range_bounds_map::test_ranges::ie;
use range_bounds_map::RangeBoundsMap;

let mut map = RangeBoundsMap::new();

map.insert_strict(ie(0, 5), true);
map.insert_strict(ie(5, 10), false);

assert_eq!(map.overlaps(ie(-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::test_ranges::ie;
use range_bounds_map::RangeBoundsMap;

#[derive(Debug, Copy, Clone)]
enum Reservation {
	// Start, End (Inclusive-Inclusive)
	Finite(i8, i8),
	// Start (Exclusive)
	Infinite(i8),
}

// First, we need to implement RangeBounds
impl RangeBounds<i8> for Reservation {
	fn start_bound(&self) -> Bound<&i8> {
		match self {
			Reservation::Finite(start, _) => {
				Bound::Included(start)
			}
			Reservation::Infinite(start) => {
				Bound::Excluded(start)
			}
		}
	}
	fn end_bound(&self) -> Bound<&i8> {
		match self {
			Reservation::Finite(_, end) => Bound::Included(end),
			Reservation::Infinite(_) => Bound::Unbounded,
		}
	}
}

// Next we can create a custom typed RangeBoundsMap
let reservation_map = RangeBoundsMap::from_slice_strict([
	(Reservation::Finite(10, 20), "Ferris".to_string()),
	(Reservation::Infinite(20), "Corro".to_string()),
])
.unwrap();

for (reservation, name) in reservation_map.overlapping(ie(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 using TryFrom<(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 full-code 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 RangeBoundss 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:

nodit https://docs.rs/nodit

Dependencies

~1–1.6MB
~34K SLoC