nested_containment_list

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

Nested Containment Lists can store types which implement the RangeBounds trait. For example, a simple Nested Containment List storing Ranges is constructed as follows:

use nested_containment_list::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.

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

// 1..5 overlaps with 3..6, so it is the first element.
let first_element = overlapping.next().unwrap();
assert_eq!(first_element.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.
assert_eq!(first_element.sublist().next().unwrap().value, &(2..4));
// 5..9 overlaps with 3..6, so it is the second element.
let second_element = overlapping.next().unwrap();
assert_eq!(second_element.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!(second_element.sublist().next().is_none())

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.31.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

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.