Crate nested_containment_list[−][src]
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 NestedContainmentList
s 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 |
IterElement | An element obtained from |
NestedContainmentList | Data structure for efficient storage and querying of |
Overlapping | An |
OverlappingElement | An element contained within an |