Crate nested_containment_list

Implementation of a Nested Containment List.

A Nested Containment List is a data structure for storing types that implement the core::ops::RangeBounds trait. Elements stored in a NestedContainmentList are stored in a nested structure to allow for easy querying using other RangeBounds queries.

Construction

Construction of NestedContainmentLists can be done using either the new() or from_iter() methods. Construction from from_iter() has temporal complexity O(n log(n)), where n is the length of the slice.

use nested_containment_list::NestedContainmentList;
use std::ops::Range;

let nclist = NestedContainmentList::<Range<usize>, usize>::new();

use nested_containment_list::NestedContainmentList;
use std::iter::FromIterator;

let nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 5..7]);

Mutation

A NestedContainmentList allows for insertion and removal of RangeBounds types. Both of these methods have a temporal complexity of O(log(n)), where n is the number of RangeBounds stored in the data structure.

use nested_containment_list::NestedContainmentList;

let mut nclist = NestedContainmentList::new();

nclist.insert(1..5);
nclist.remove(&(1..5));

Iteration

Iterating over a NestedContainmentList is done in a nested manner. An Iterator is obtained from the overlapping() method. It is used to iterate directly over the top-most sublist, returning values which overlap with the query range, with nested intervals contained within the top-most elements being accessed through nested sublists.

For example, iterating over all elements can be done as follows:

use nested_containment_list::NestedContainmentList;
use std::iter::FromIterator;

let nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 6..7]);
let mut sublist = nclist.overlapping(&(..));

// The first element in the top-most sublist, 1..5.
let first_element = sublist.next().unwrap();
assert_eq!(first_element.value, &(1..5));

// Contained inside the element's sublist is the interval 2..4.
assert_eq!(first_element.sublist().next().unwrap().value, &(2..4));

// The next element in the top-most sublist is 6..7, so it is obtained like the first element.
let second_element = sublist.next().unwrap();
assert_eq!(second_element.value, &(6..7));

To remove a single level of nesting, one may use the Iterator::flatten() method.

no_std

This crate is usable in no_std environments when compiled on stable rustc 1.36.0 or higher. The version limitation is due to the use of alloc, allowing for heap allocation without use of std.

Structs

Iter

An Iterator over all elements in a NestedContainmentList.

IterElement

An element obtained from Iter.

NestedContainmentList

Data structure for efficient storage and querying of RangeBounds.

Overlapping

An Iterator over elements in a NestedContainmentList that overlap a query.

OverlappingElement

An element contained within an Overlapping.