### 6 releases

0.5.1 | Jul 1, 2023 |
---|---|

0.5.0 | Jul 1, 2023 |

0.4.3 | Jun 17, 2023 |

0.4.1 | May 16, 2023 |

0.4.0 | Apr 24, 2023 |

#**162** in Data structures

**69** downloads per month

Used in gap_query_interval_tree

**AGPL-3.0-or-later**

96KB

2K
SLoC

# discrete_range_map

This crate provides

and `DiscreteRangeMap`

,
Data Structures for storing non-overlapping discrete intervals based
off `DiscreteRangeSet`

.`BTreeMap`

## You must implement `Copy`

`Copy`Due to implementation complications with non-

types the
datastructures currently require both the range type and the points
the ranges are over to be `Copy`

.`Copy`

## Example using an Inclusive-Exclusive range

`use` `discrete_range_map``::``test_ranges``::`ie`;`
`use` `discrete_range_map``::`DiscreteRangeMap`;`
`let` `mut` map `=` `DiscreteRangeMap``::`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 range type

`use` `discrete_range_map``::``test_ranges``::`ie`;`
`use` `discrete_range_map``::``{`
DiscreteFinite`,` Interval`,` DiscreteRangeMap`,`
FiniteRange`,`
`}``;`
`#``[``derive``(``Debug``,` Copy`,` Clone`)``]`
`enum` `Reservation` `{`
`//` Start, End (Inclusive-Exclusive)
Finite`(``i8``,` `i8``)``,`
`//` Start (Inclusive-Forever)
Infinite`(``i8``)``,`
`}`
`//` First, we need to implement FiniteRange
`impl` `FiniteRange``<``i8``>` `for`` ``Reservation` `{`
`fn` `start``(``&``self``)`` ``->` `i8` `{`
`match` `self` `{`
`Reservation``::`Finite`(`start`,` `_``)` `=>` `*`start`,`
`Reservation``::`Infinite`(`start`)` `=>` `*`start`,`
`}`
`}`
`fn` `end``(``&``self``)`` ``->` `i8` `{`
`match` `self` `{`
`//`the end is exclusive so we take off 1 with checking
`//`for compile time error overflow detection
`Reservation``::`Finite`(``_``,` end`)` `=>` end`.``down``(``)``.``unwrap``(``)``,`
`Reservation``::`Infinite`(``_``)` `=>` `i8``::``MAX``,`
`}`
`}`
`}`
`//` Second, we need to implement From<Interval<i8>>
`impl` `From``<`Interval`<``i8``>``>` `for`` ``Reservation` `{`
`fn` `from``(``bounds``:` `Interval``<``i8``>``)`` ``->` `Self` `{`
`if` bounds`.`end `==` `i8``::``MAX` `{`
`Reservation``::`Infinite`(`bounds`.`start`)`
`}` `else` `{`
`Reservation``::`Finite`(`
bounds`.`start`,`
bounds`.`end`.``up``(``)``.``unwrap``(``)``,`
`)`
`}`
`}`
`}`
`//` Next we can create a custom typed DiscreteRangeMap
`let` reservation_map `=` `DiscreteRangeMap``::`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 Understandings and Philosophies:

### Discrete-ness

This crate is designed to work with

types as compared to
`Discrete`

types. For example, `Continuous`

is a `u8`

type, but
`Discrete`

is a `String`

if you try to parse it as a decimal value.`Continuous`

The reason for this is that common

operations
differ depending on wether the underlying type is `interval-Mathematics`

or
`Discrete`

. For example `Continuous`

touches `5``..``=``6`

since integers are
`7``..``=``8`

but `Discrete`

does `5.``0``..``=``6.``0`**not** touch

since the
value `7.``0``..``=``8.``0`

exists.`6.``5`

### Finite-ness

This crate is also designed to work with

types since it is
much easier to implement and it is not restrictive to users since you
can still represent `Finite`

numbers in `Infinite`

types paradoxically
using the concept of `Finite`

.`Actual Infinity`

For example you could define

for `Infinite`

as `u8`

or if
you still want to use `u8``::``MAX`

as a `u8``::``MAX`

number you could define
a wrapper type for `Finite`

that adds an `u8`

value to the
`Actual Infinity`

set.`u8`

### 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,

is considered valid as it contains the values
`4``..``6`

and `4`

, however, `5`

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 `4``..``4`

or
`5``..``2`

.`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 |

(Bound::Exluded(3), Bound::Exluded(4)) | NO |

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,

and `2``..``4`

are touching but
`4``..``6`

and `2``..``4`

are not, neither are `6``..``8`

and `2``..``6`

.`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)

# Credit

I originally came up with the

: `StartBound`

bodge on my own,
however, I later stumbled across `Ord`

which also used a
`rangemap`

: `StartBound`

bodge. `Ord`

then became my main source
of inspiration.`rangemap`

Later I then undid the

bodge and switched to my own full-code
port of `Ord`

, inspired and forked from `BTreeMap`

, for it's
increased flexibility.`copse`

# Origin

The aim for this library was to become a more generic superset of

, following from this
issue and this
pull request in
which I changed `rangemap`

's `rangemap`

to use `RangeMap`

s as
keys before I realized it might be easier and simpler to just write it
all from scratch.`RangeBounds`

It is however worth noting the library eventually expanded and evolved from it's origins.

This crate was previously named

.`range_bounds_map`

# 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

s and`Range`

s as keys in it's`RangeInclusive`

and`map`

structs (separately).`set` - https://docs.rs/btree-range-map
- https://docs.rs/ranges
Cool library for fully-generic ranges (unlike std::ops ranges), along
with a

datastructure for storing them (Vec-based unfortunately)`Ranges` - https://docs.rs/intervaltree Allows overlapping intervals but is immutable unfortunately
- https://docs.rs/nonoverlapping_interval_tree
Very similar to rangemap except without a

function and only for`gaps``(``)`

s and not`Range`

s. And also no fancy merging functions.`RangeInclusive` - https://docs.rs/unbounded-interval-tree
A data structure based off of a 2007 published paper! It supports
any range as keys, unfortunately, it is implemented with a
non-balancing

based tree, however it also supports overlapping ranges which my library does not.`Box``<`Node`>` - 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.

#### Dependencies

~1.3–2MB

~41K SLoC