Crates.io | nested_containment_list |

lib.rs | nested_containment_list |

version | 0.3.1 |

source | src |

created_at | 2021-01-23 00:02:22.879472 |

updated_at | 2022-03-26 15:55:40.279008 |

description | A data structure for efficiently storing and querying nested intervals. |

homepage | |

repository | https://github.com/Anders429/nested_containment_list |

max_upload_size | |

id | 345473 |

size | 175,765 |

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.

Nested Containment Lists can store types which implement the
`RangeBounds`

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

s 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())
```

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

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`

.

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.

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.