### 9 releases

0.1.8 | Nov 22, 2020 |
---|---|

0.1.7 | Sep 7, 2020 |

0.1.6 | Jul 14, 2020 |

0.1.5 | Jun 23, 2020 |

0.1.3 | Feb 25, 2019 |

#**87** in Data structures

**62** downloads per month

Used in bupstash

**MIT/Apache**

115KB

2K
SLoC

# rangemap

and `RangeMap`

are map data structures whose keys
are stored as ranges. Contiguous and overlapping ranges that map to the same
value are coalesced into a single range.`RangeInclusiveMap`

Corresponding

and `RangeSet`

structures are also provided.`RangeInclusiveSet`

## Different kinds of ranges

and `RangeMap`

correspond to the `RangeInclusiveMap`

and `Range`

types from the standard library respectively.
For some applications the choice of range type may be obvious,
or even be dictated by pre-existing design decisions. For other applications
the choice may seem arbitrary, and be guided instead by convenience or
aesthetic preference.`RangeInclusive`

If the choice is not obvious in your case, consider these differences:

- If your key type

represents points on a continuum (e.g.`K`

), and the choice of which of two adjacent ranges "owns" the value where they touch is largely arbitrary, then it may be more natural to work with half-open`f64`

s like`Range`

and`0.``0``..``1.``0`

. If you were to use closed`1.``0``..``2.``0`

s here instead, then to represent two such adjacent ranges you would need to subtract some infinitesimal (which may depend, as it does in the case of`RangeInclusive`

, on the specific value of`f64`

) from the end of the earlier range. (See the last point below for more on this problem.)`K` - If you need to represent ranges that
*include*the maximum value in the key domain (e.g.

) then you will probably want to use`255``u8`

s like`RangeInclusive`

. Sometimes it may be possible to instead work around this by using a wider key type than the values you are actually trying to represent (`128``u8``..``=``255``u8`

even though you are only trying to represent ranges covering`K``=``u16`

) but in these cases the key domain often represents discrete objects rather than points on a continuum, and so`u8`

may be a more natural way to express these ranges anyway.`RangeInclusive` - If you are using

, then it must be possible to define`RangeInclusive`*successor*and*predecessor*functions for your key type

, because adjacent ranges can not be detected (and thereby coalesced) simply by testing their ends for equality. For key types that represent points on a continuum, defining these functions may be awkward and error-prone. For key types that represent discrete objects, this is usually much more straightforward.`K`

## Example: use with Chrono

`use` `chrono``::``offset``::`TimeZone`;`
`use` `chrono``::``{`Duration`,` Utc`}``;`
`use` `rangemap``::`RangeMap`;`
`fn` `main``(``)`` ``{`
`let` people `=` `[``"`Alice`"``,` `"`Bob`"``,` `"`Carol`"``]``;`
`let` `mut` roster `=` `RangeMap``::`new`(``)``;`
`//` Set up initial roster.
`let` start_of_roster `=` Utc`.``ymd``(``2019``,` `1``,` `7``)``;`
`let` `mut` week_start `=` start_of_roster`;`
`for` `_` `in` `0``..``3` `{`
`for` person `in` `&`people `{`
`let` next_week `=` week_start `+` `Duration``::`weeks`(``1``)``;`
roster`.``insert``(`week_start`..`next_week`,` person`)``;`
week_start `=` next_week`;`
`}`
`}`
`//` Bob is covering Alice's second shift (the fourth shift overall).
`let` fourth_shift_start `=` start_of_roster `+` `Duration``::`weeks`(``3``)``;`
`let` fourth_shift_end `=` fourth_shift_start `+` `Duration``::`weeks`(``1``)``;`
roster`.``insert``(`fourth_shift_start`..`fourth_shift_end`,` `&``"`Bob`"``)``;`
`for` `(`range`,` person`)` `in` roster`.``iter``(``)` `{`
`println!``(``"``{}` (`{}`): `{}``"``,` range`.`start`,` range`.`end `-` range`.`start`,` person`)``;`
`}`
`//` Output:
`//` 2019-01-07UTC (P7D): Alice
`//` 2019-01-14UTC (P7D): Bob
`//` 2019-01-21UTC (P7D): Carol
`//` 2019-01-28UTC (P14D): Bob
`//` 2019-02-11UTC (P7D): Carol
`//` 2019-02-18UTC (P7D): Alice
`//` 2019-02-25UTC (P7D): Bob
`//` 2019-03-04UTC (P7D): Carol
`}`