nestedcontainmentlist

travis-ci.org codecov.io crates.io docs.rs MSRV License

Implementation of a Nested Containment List.

A Nested Containment List is a data structure for efficiently storing and querying intervals. It is based on the Nested Containment List data structure set forth by Alexander V. Alekseyenko and Christopher J. Lee in their 2007 Bioinformatics publication. The implementation provided here allows storage and querying of generic types using generical bounds.

Usage

To allow a type to be stored and used with Nested Containment Lists, it must implement the Interval trait.

```rust use nestedcontainmentlist::Interval;

impl Interval for MyStruct { fn start(&self) -> usize { ... }

fn end(&self) -> usize {
    ...
}

} ```

The type can then be stored within a Nested Containment List.

Note that the Interval trait is already implemented for Range. A Range can therefore be used in Nested Containment Lists, like so:

```rust use nestedcontainmentlist::NestedContainmentList;

let nclist = NestedContainmentList::new();

nclist.insert(1..5); nclist.insert(2..4); nclist.insert(6..7); nclist.insert(5..9); ```

Data stored within the Nested Containment List is typically accessed through a nested Iterator structure, obtained by querying using the .overlapping() method.

```rust let query = 3..6; let mut overlapping = nclist.overlapping(&query);

// 1..5 overlaps with 3..6, so it is the first element. let firstelement = overlapping.next().unwrap(); asserteq!(firstelement.value, &(1..5)); // 2..4 is contained inside 1..5 and overlaps with 3..6, so it is accessed through the first // element's sublist. asserteq!(firstelement.sublist().next().unwrap().value, &(2..4)); // 5..9 overlaps with 3..6, so it is the second element. let secondelement = overlapping.next().unwrap(); asserteq!(secondelement.value, &(5..9)); // Even though 6..7 is contained inside 5..9, it does not overlap with 3..6, and therefore is not // contained in the second element's sublist. assert!(secondelement.sublist().next().isnone()) ```

Performance

Construction

Construction of a NestedContainmentList has temporal complexity O(n log(n)). Insertion using NestedContainmentList::insert() has temporal complexity O(log n). Similarly, removal using NestedContainmentList::remove() also has temporal complexity O(log n).

Querying

Querying for overlapping intervals with NestedContainmentList::overlapping() has temporal complexity O(n + log(N)), where N is the number of intervals stored within the Nested Containment List, and n is the number of intervals overlapping with the query.

Minimum Supported Rust Version

This crate is guaranteed to compile on stable rustc 1.0.0 and up. Use in a no_std environment requires stable rustc 1.36.0 and up, due to the use of alloc.

License

This project is licensed under either of

at your option.