Struct nested_containment_list::NestedContainmentList

pub struct NestedContainmentList<R, T> where
    R: RangeBounds<T>,
    T: Ord,  { /* private fields */ }

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 Iterators 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, 

pub fn new() -> Self

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();

pub fn with_capacity(capacity: usize) -> Self

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.

pub fn len(&self) -> usize

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);

pub fn is_empty(&self) -> bool

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());

pub fn capacity(&self) -> usize

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);

pub fn overlapping<'a, S>(&'a self, query: &'a S) -> Overlapping<'a, R, S, T> where
    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 Overlappings 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)

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

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, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<R, T> Default for NestedContainmentList<R, T> where
    R: RangeBounds<T>,
    T: Ord, 

fn default() -> Self

Constructs a new, empty NestedContainmentList. Equivalent to new().

Example

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

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

impl<R, T> Extend<R> for NestedContainmentList<R, T> where
    R: RangeBounds<T>,
    T: Ord, 

fn extend<I>(&mut self, iter: I) where
    I: IntoIterator<Item = R>, 

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<R, T> From<&'_ [R]> for NestedContainmentList<R, T> where
    R: RangeBounds<T> + Clone,
    T: Ord, 

fn from(s: &[R]) -> Self

Converts to this type from the input type.

impl<R, T> From<NestedContainmentList<R, T>> for Vec<R> where
    R: RangeBounds<T>,
    T: Ord, 

Due to orphaning rules, this implementation is only available in rustc 1.41.0 and above. On earlier rustc versions, a direct implementation of Into is provided instead, so that the following example will still work:

use nested_containment_list::NestedContainmentList;

let nclist = NestedContainmentList::from(vec![2..3, 1..4, 3..5]);
let vec: Vec<_> = nclist.into();

See Implementing Into for conversions to external types in old versions of Rust for more information.

fn from(nclist: NestedContainmentList<R, T>) -> Self

Converts to this type from the input type.

impl<R, T> From<Vec<R, Global>> for NestedContainmentList<R, T> where
    R: RangeBounds<T>,
    T: Ord, 

fn from(v: Vec<R>) -> Self

Converts to this type from the input type.

impl<R, T> FromIterator<R> for NestedContainmentList<R, T> where
    R: RangeBounds<T>,
    T: Ord, 

fn from_iter<I>(iter: I) -> Self where
    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, 

type Item = IterElement<R, T>

The type of the elements being iterated over.

type IntoIter = Iter<R, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.