rangeboundsmap

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 [Range]s

```rust use rangeboundsmap::RangeBoundsMap;

let mut rangeboundsmap = RangeBoundsMap::new();

rangeboundsmap.insertplatonic(0..5, true); rangeboundsmap.insertplatonic(5..10, false);

asserteq!(rangeboundsmap.overlaps(&(-2..12)), true); asserteq!(rangeboundsmap.containspoint(&20), false); asserteq!(rangeboundsmap.contains_point(&5), true); ```

Example using a custom [RangeBounds] type

```rust use std::ops::{Bound, RangeBounds};

use rangeboundsmap::RangeBoundsMap;

[derive(Debug)]

enum Reservation { // Start, End (Inclusive-Inclusive) Finite(u8, u8), // Start (Exclusive) Infinite(u8), }

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

// Next we can create a custom typed RangeBoundsMap let reservationmap = RangeBoundsMap::tryfrom([ (Reservation::Finite(10, 20), "Ferris".tostring()), (Reservation::Infinite(20), "Corro".tostring()), ]) .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:?}"); }

asserteq!( reservationmap.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 [RangeBounds]s 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:

• https://docs.rs/rangemap Very similar to this crate but can only use [Range]s and [RangeInclusive]s as keys in it's map and set structs (separately).
• https://docs.rs/ranges Cool library for fully-generic ranges (unlike std::ops ranges), along with a Ranges datastructure for storing them (Vec-based 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 for [Range]s and not [RangeInclusive]s. And also no fancy coalescing functions.
• https://docs.rs/unbounded-interval-tree A data structure based off of a 2007 published paper! It supports any RangeBounds as keys too, except it is implemented with a non-balancing 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 red-black tree/BTree implementation used specifically for a Range Tree. Interesting but also quite old (5 years) and uses unsafe.