intervalmap 0.1.0

An interval set/map library inspired by Boost.Icl
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

# intervalmap

A Rust library for working with sets and maps of intervals. Inspired by [Boost.Icl](https://www.boost.org/doc/libs/release/libs/icl/).

## What it does

`IntervalSet` stores non-overlapping intervals and automatically merges them when they touch or overlap:

```rust
use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(5..15);  // merges into [0, 15)

assert!(set.contains(12));
assert_eq!(set.len(), 1);  // just one interval after merge
```

`IntervalMap` associates values with intervals. When you insert overlapping ranges, the new value takes over:

```rust
use intervalmap::IntervalMap;

let mut map = IntervalMap::new();
map.insert(0..10, "a");
map.insert(5..15, "b");

// Result: [0,5) -> "a", [5,15) -> "b"
assert_eq!(map.get(3), Some(&"a"));
assert_eq!(map.get(7), Some(&"b"));
```

Adjacent intervals with the same value get merged automatically.

## Macros

```rust
use intervalmap::{interval_set, interval_map};

let set = interval_set!{ 0..10, 20..30, 40..50 };
let map = interval_map!{ 0..10 => "first", 20..30 => "second" };
```

## Range types

All standard Rust range types work:

```rust
set.insert(0..10);       // [0, 10)
set.insert(0..=10);      // [0, 11)
set.insert(10..);        // [10, MAX)
set.insert(..10);        // [MIN, 10)
set.insert(..);          // [MIN, MAX)
```

## Set operations

`IntervalSet` supports the usual set operations:

```rust
let a = interval_set!{ 0..10, 20..30 };
let b = interval_set!{ 5..25 };

let union = &a | &b;              // or a.union(&b)
let intersection = &a & &b;       // or a.intersection(&b)
let difference = &a - &b;         // or a.difference(&b)
let symmetric_diff = &a ^ &b;     // or a.symmetric_difference(&b)
```

## Other useful bits

```rust
// Query methods
set.first();              // lowest interval
set.last();               // highest interval
set.span();               // bounding range from first.start to last.end
set.overlaps(5..15);      // does any interval overlap this range?
set.covers(5..15);        // is the entire range covered?

// Iteration
set.gaps();               // iterate over gaps between intervals
set.iter_overlapping(5..25);  // only intervals that overlap the range

// Modification
set.retain(|r| r.start >= 10);  // filter intervals
set.split_at(50);               // split interval containing this point
```

## Index types

The default index type is `u32`, but any primitive integer works:

```rust
let set: IntervalSet<i64> = IntervalSet::new();
let set: IntervalSet<u8> = IntervalSet::new();
```

## License

MIT