# nested_intervals 0.2.0

nested & overlapping interval set functions, overlap, union, etc
Documentation

## nested_intervals

This crate deals with interval sets which are lists of Ranges that may be both overlapping and nested.

The implementation is based on nested containment lists as proposed by Alekseyenko et al. 2007, which offers the same big-O complexity s interval trees (O(n * log(n)) construction, O(n + m) queries). The construction of the query data structure is lazy and only happens the first time a method relying on it is called.

Each interval has a vec of u32 ids attached, which allows linking back the results to other data structures.

Full documentation at docs.rs Source at GitHub

## Example

Code example:

``````  fn test_example() {
let intervals = vec![0..20, 15..30, 50..100];
let mut interval_set = IntervalSet::new(&intervals);
assert_eq!(interval_set.ids, vec![vec![0], vec![1], vec![2]]); // automatic ids, use new_with_ids otherwise
let hits = interval_set.query_overlapping(10..16);
assert_eq!(hits.intervals, [0..20, 15..30]);
let merged = hits.merge_hull();
assert_eq!(merged.intervals, [0..30]);
assert_eq!(merged.ids, vec![vec![0,1]]);
}
``````

## Not (yet) supported

We currently can not

• find the interval with the closest end

• find the interval with the closest end to the left of a point //going be expensive O(n/2)

• find the interval with the closest end to the right of a point //going be expensiv O(n/2)

• intersect two interval sects (ie. covered units in both sets)

• intersect more than two interval sects (ie. covered units in multiple sets, possibly applying a 'k' threshold)

• merge internally overlapping by intersecting them? What does than even mean for nested sets?