/range_bounds_map

A Data Structure that uses RangeBounds as keys. Based off BTreeMap

Primary LanguageRustGNU Affero General Public License v3.0AGPL-3.0

range_bounds_map

License Docs Maintained Crates.io

range_bounds_map_logo

This crate provides RangeBoundsMap and RangeBoundsSet.

RangeBoundsMap is an ordered map of non-overlapping RangeBounds based on BTreeMap.

RangeBoundsSet is an ordered set of non-overlapping RangeBounds based on RangeBoundsMap.

Example using Ranges

use range_bounds_map::RangeBoundsMap;

let mut range_bounds_map = RangeBoundsMap::new();

range_bounds_map.insert_platonic(0..5, true);
range_bounds_map.insert_platonic(5..10, false);

assert_eq!(range_bounds_map.overlaps(&(-2..12)), true);
assert_eq!(range_bounds_map.contains_point(&20), false);
assert_eq!(range_bounds_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 (Inclusive-Inclusive)
	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:

Overlap

Two RangeBounds are "overlapping" if there exists a point that is contained within both RangeBounds.

Touching

Two RangeBounds 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.

Coalesce

When a RangeBounds "coalesces" other RangeBounds it absorbs them to become larger.

Improvements/Caveats

  • Missing some functions common to BTreeMap and BTreeSet like:
    • clear()
    • is_subset()
    • etc... prob a bunch more
  • Not particularly optimized, (which doesn't mean it's neccessarily slow)
  • Can't use TryFrom<(Bound, Bound)> instead of [TryFromBounds] (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.

The aim for my 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. Which ended up working really well with some simplifications (BoundOrd) I made which made some of the code much easier to work with.

Similar Crates

Here are some relevant crates I found whilst searching around the topic area: