nested_containment_list

Crates.ionested_containment_list
lib.rsnested_containment_list
version0.3.1
sourcesrc
created_at2021-01-23 00:02:22.879472
updated_at2022-03-26 15:55:40.279008
descriptionA data structure for efficiently storing and querying nested intervals.
homepage
repositoryhttps://github.com/Anders429/nested_containment_list
max_upload_size
id345473
size175,765
Anders Evensen (Anders429)

documentation

README

nested_containment_list

GitHub Workflow Status 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

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

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.

Commit count: 184

cargo fmt