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
NestedContainmentLists can be done using either the
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]);
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));
Iterating over a
NestedContainmentList is done in a nested manner. An
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
An element obtained from
Data structure for efficient storage and querying of
An element contained within an