### 5 releases

new 0.0.5 | Jun 18, 2021 |
---|---|

0.0.4 | Jun 9, 2021 |

0.0.3 | Mar 20, 2020 |

0.0.2 | Mar 18, 2020 |

0.0.1 | Mar 17, 2020 |

#**114** in Data structures

**1,231** downloads per month

**MIT**license

63KB

1.5K
SLoC

This crates implements map and set with interval keys (ranges

).`x ..y`

is implemented using red-black binary tree, where each node contains
information about the smallest start and largest end in its subtree.
The tree takes `IntervalMap`*O(N)* space and allows insertion in *O(log N)*.

allows to search for all entries overlapping a query (interval or a point,
output would be sorted by keys). Search takes `IntervalMap`*O(log N + K)* where *K* is the size of the output.
Additionally, you can extract smallest/largest interval with its value in *O(log N)*.

is a newtype over `IntervalSet`

with empty values.`IntervalMap`

Any iterator that goes over the

or `IntervalMap`

returns intervals/values sorted lexicographically by intervals.`IntervalSet`

## Usage

The following code constructs a small interval map and search for intervals/values overlapping various queries.

`let` `mut` map `=` `iset``::``IntervalMap``::`new`(``)``;`
map`.``insert``(``20``..``30``,` `"`a`"``)``;`
map`.``insert``(``15``..``25``,` `"`b`"``)``;`
map`.``insert``(``10``..``20``,` `"`c`"``)``;`
`//` Iterate over (interval, &value) pairs that overlap query (.. here).
`//` Output is sorted by intervals.
`let` a`:` `Vec``<``_``>` `=` map`.``iter``(``..``)``.``collect``(``)``;`
`assert_eq!``(`a`,` `&``[``(``10``..``20``,` `&``"`c`"``)``,` `(``15``..``25``,` `&``"`b`"``)``,` `(``20``..``30``,` `&``"`a`"``)``]``)``;`
`//` Iterate over intervals that overlap query (..20 here). Output is sorted.
`let` b`:` `Vec``<``_``>` `=` map`.``intervals``(``..``20``)``.``collect``(``)``;`
`assert_eq!``(`b`,` `&``[``10``..``20``,` `15``..``25``]``)``;`
`//` Iterate over values that overlap query (20.. here). Output is sorted by intervals.
`let` c`:` `Vec``<``_``>` `=` map`.``values``(``20``..``)``.``collect``(``)``;`
`assert_eq!``(`c`,` `&``[``&``"`b`"``,` `&``"`a`"``]``)``;`
`println!``(``"``{:?}``"``,` map`)``;`
`//` {10..20: "c", 15..25: "b", 20..30: "a"}

You can find more detailed usage here.

## Future features:

- Remove intervals from

and`IntervalMap`

.`IntervalSet` - Get all (interval, value) pairs by exact match with the query.
- Join two maps/sets, split map/set into two.

## Changelog

You can find changelog here.

## Issues

Please submit issues here or send them to

.`timofey .prodanov[at]gmail.com`

#### Dependencies

~77–285KB