### 6 releases

0.3.1 | Mar 26, 2022 |
---|---|

0.3.0 | Mar 8, 2021 |

0.2.1 | Feb 12, 2021 |

0.1.1 | Jan 24, 2021 |

#**1093** in Data structures

**308** downloads per month

Used in **2** crates
(via word_filter)

**MIT/Apache**

165KB

3K
SLoC

# 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

trait. For example, a
simple Nested Containment List storing
`RangeBounds`

s is constructed as follows:`Range`

`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

structure, obtained by querying
using the
`Iterator`

method.`.``overlapping``(``)`

`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

has temporal complexity `NestedContainmentList`*O(n log(n))*. Insertion using

has temporal complexity `NestedContainmentList ::`insert

`(`

`)`

*O(log n)*. Similarly, removal using

`NestedContainmentList``::`remove`(``)`

also has temporal complexity *O(log n)*.

### Querying

Querying for overlapping intervals with

has temporal complexity `NestedContainmentList ::`overlapping

`(`

`)`

*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

and up. Use in a
`rustc 1.31.0`

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

#### Dependencies

~0–275KB