Struct nested_containment_list::NestedContainmentList [−][src]
Data structure for efficient storage and querying of RangeBounds
.
Usage
A NestedContainmentList
is a collection of RangeBounds
, and can be used similar to other
collections. It has a len()
and a capacity()
, allows for mutation through insert()
and remove()
. A main difference between NestedContainmentList
and other Rust collections
is how its contents are accessed: they may be iterated over through overlapping()
. For
further details, see Data Access.
Construction
A NestedContainmentList
stores RangeBounds
in a nested structure to allow for fast querying.
Construction of a NestedContainmentList
has temporal complexity O(n log(n)), where n is
the number of RangeBounds
being stored. Both insertion and removal, with insert()
and
remove()
respectively, into a NestedContainmentList
has temporal complexity O(log(n)),
where n is the number of RangeBounds
currently stored.
Example
Construction of a NestedContainmentList
can be done as follows:
use nested_containment_list::NestedContainmentList; use std::iter::FromIterator; let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 5..7]);
Data Access
When data is stored within a NestedContainmentList
, it is typically accessed by querying for
RangeBounds
overlapping another RangeBounds
, using the overlapping()
method.
Both methods return a nested Iterator
structure, with the difference being that access
through overlapping()
only iterates over RangeBounds
that overlap with the query
value. For details on the Iterator
s returned by these methods, see the documentation for
Overlapping
.
Querying using overlapping()
has temporal complexity O(n + log(N)), where N is the
number of RangeBounds
stored, and n is the number of intervals overlapping with the query
value.
Example
Access using either method can be done as follows:
use nested_containment_list::NestedContainmentList; use std::iter::FromIterator; let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 5..7]); // Creates a Sublist Iterator. let mut sublist = nclist.overlapping(&(..)); // Creates an Overlapping Iterator. let query = 4..6; let mut overlapping = nclist.overlapping(&query);
Implementations
impl<R, T> NestedContainmentList<R, T> where
R: RangeBounds<T>,
T: Ord,
[src]
R: RangeBounds<T>,
T: Ord,
#[must_use]pub fn new() -> Self
[src]
Construct an empty NestedContainmentList
.
Example
The following example constructs a new NestedContainmentList
to hold elements of type
Range<usize>
.
use nested_containment_list::NestedContainmentList; use std::ops::Range; let nclist = NestedContainmentList::<Range<usize>, usize>::new();
#[must_use]pub fn with_capacity(capacity: usize) -> Self
[src]
Construct an empty NestedContainmentList
with the specified capacity.
The NestedContainmentList
will be able to hold exactly capacity
RangeBounds
without
reallocating. If capacity
is 0
, the NestedContainmentList
will not allocate.
Note that capacity
is not the same as len
. len
is how many elements are actually
contained, while capacity
is how many could be contained given the current allocation.
Example
use nested_containment_list::NestedContainmentList; let mut nclist = NestedContainmentList::with_capacity(5); nclist.insert(1..2); // Does not reallocate, since capacity is available.
#[must_use]pub fn len(&self) -> usize
[src]
Returns the number of elements contained in the NestedContainmentList
, also referred to as
its 'length'.
Example
use nested_containment_list::NestedContainmentList; let mut nclist = NestedContainmentList::new(); assert_eq!(nclist.len(), 0); nclist.insert(1..5); assert_eq!(nclist.len(), 1);
#[must_use]pub fn is_empty(&self) -> bool
[src]
Returns true
if the NestedContainmentList
contains no elements.
Example
use nested_containment_list::NestedContainmentList; let mut nclist = NestedContainmentList::new(); assert!(nclist.is_empty()); nclist.insert(1..5); assert!(!nclist.is_empty());
#[must_use]pub fn capacity(&self) -> usize
[src]
Returns the number of elements the NestedContainmentList
can hold without reallocating.
Example
use nested_containment_list::NestedContainmentList; use std::ops::Range; let nclist = NestedContainmentList::<Range<usize>, usize>::with_capacity(10); assert_eq!(nclist.capacity(), 10);
#[must_use]pub fn overlapping<'a, S>(&'a self, query: &'a S) -> Overlapping<'a, R, S, T>ⓘNotable traits for Overlapping<'a, R, S, T>
impl<'a, R, S, T> Iterator for Overlapping<'a, R, S, T> where
R: RangeBounds<T>,
S: RangeBounds<T>,
T: Ord, type Item = OverlappingElement<'a, R, S, T>;
where
S: RangeBounds<T>,
[src]
Notable traits for Overlapping<'a, R, S, T>
impl<'a, R, S, T> Iterator for Overlapping<'a, R, S, T> where
R: RangeBounds<T>,
S: RangeBounds<T>,
T: Ord, type Item = OverlappingElement<'a, R, S, T>;
S: RangeBounds<T>,
Returns an Overlapping
Iterator
over all elements within the
NestedContainmentList
.
The Overlapping
is a nested Iterator
over all values contained in the
NestedContainmentList
that overlap with the query
RangeBounds
. All RangeBounds
contained within other RangeBounds
in the collection that also overlap with the query
are accessed as nested Overlapping
s under their outer-most values.
Example
use nested_containment_list::NestedContainmentList; use std::iter::FromIterator; let nclist = NestedContainmentList::from_iter(vec![1..5, 2..3, 2..4, 5..7]); let query = 3..6; let mut overlapping = nclist.overlapping(&query); let first_element = overlapping.next().unwrap(); let second_element = overlapping.next().unwrap(); // The outermost elements are accessed directly. assert_eq!(first_element.value, &(1..5)); assert_eq!(second_element.value, &(5..7)); // Contained elements are accessed through their containing element's sublist. let mut inner_sublist = first_element.sublist(); let inner_element = inner_sublist.next().unwrap(); assert_eq!(inner_element.value, &(2..4)); // Note that 2..3 is not found within the nested iterators, since 2..3 does not overlap with 3..6.
pub fn insert(&mut self, value: R)
[src]
Insert a new value into the NestedContainmentList
.
This insertion preserves the internal nested structure of the container, and has temporal complexity of O(log(n)).
If the NestedContainmentList
's capacity
is not large enough, the NestedContainmentList
will reallocate.
Example
use nested_containment_list::NestedContainmentList; let mut nclist = NestedContainmentList::new(); nclist.insert(1..2);
pub fn remove<Q>(&mut self, value: &Q) -> bool where
Q: RangeBounds<T>,
R: Borrow<Q>,
[src]
Q: RangeBounds<T>,
R: Borrow<Q>,
Remove the specified value from the NestedContainmentList
.
This removal preserves the internal nested structure of the container, and has temporal complexity O(log(n)).
Example
use nested_containment_list::NestedContainmentList; use std::iter::FromIterator; let mut nclist = NestedContainmentList::from_iter(vec![1..5, 2..4, 3..4]); assert!(nclist.remove(&(2..4)));
Trait Implementations
impl<R: Debug, T: Debug> Debug for NestedContainmentList<R, T> where
R: RangeBounds<T>,
T: Ord,
[src]
R: RangeBounds<T>,
T: Ord,
impl<R, T> Default for NestedContainmentList<R, T> where
R: RangeBounds<T>,
T: Ord,
[src]
R: RangeBounds<T>,
T: Ord,
impl<R, T> FromIterator<R> for NestedContainmentList<R, T> where
R: RangeBounds<T>,
T: Ord,
[src]
R: RangeBounds<T>,
T: Ord,
fn from_iter<I>(iter: I) -> Self where
I: IntoIterator<Item = R>,
[src]
I: IntoIterator<Item = R>,
Construct a NestedContainmentList
from an Iterator
.
This construction has temporal complexity of O(n log(n)), where n is the length of the
Iterator
.
Example
use nested_containment_list::NestedContainmentList; use std::iter::FromIterator; let nclist = NestedContainmentList::from_iter(vec![1..5, 3..4, 2..4, 6..7]);
impl<R, T> IntoIterator for NestedContainmentList<R, T> where
R: RangeBounds<T>,
T: Ord,
[src]
R: RangeBounds<T>,
T: Ord,
Auto Trait Implementations
impl<R, T> Send for NestedContainmentList<R, T> where
R: Send,
T: Send,
[src]
R: Send,
T: Send,
impl<R, T> Sync for NestedContainmentList<R, T> where
R: Sync,
T: Sync,
[src]
R: Sync,
T: Sync,
impl<R, T> Unpin for NestedContainmentList<R, T> where
R: Unpin,
T: Unpin,
[src]
R: Unpin,
T: Unpin,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,