Enum NestedIntervalTree

pub enum NestedIntervalTree<T> {
    Node(IntervalMap<usize, Box<NestedIntervalTree<T>>>),
    Leaf(T),
}

An enumeration representing a recursive interval tree that can contain either an inner node with associated intervals or a terminal leaf with a stored value.

The inner node variant encapsulates an interval map associating ranges (identified by usize keys) to boxed nested trees, enabling hierarchical and ordered organization of intervals. In contrast, the leaf variant holds a direct value, serving as the base case in this nested tree structure.

Variants

Node(IntervalMap<usize, Box<NestedIntervalTree<T>>>)

Leaf(T)

Implementations

impl<T: Clone> NestedIntervalTree<T>

pub fn build( ranges: impl Iterator<Item = impl Iterator<Item = Range<usize>>> + Clone, value: T, ) -> Self

Builds a nested interval tree by recursively processing an iterator of range iterators and embedding a terminal value when no more ranges remain.

Recursively processes the outer iterator such that if a current iterator exists, it iterates over its ranges and creates subtrees for each by cloning the remaining iterators and value; otherwise, it produces a leaf containing the provided value. This design constructs a hierarchical structure where each node associates intervals with nested subtrees, culminating in leaves holding the synthesized value.

pub fn insert_using_iter<'a: 'b, 'b>( &'a mut self, ranges: impl Iterator<Item = impl Iterator<Item = Range<usize>> + 'b> + Clone + 'b, update: &impl Fn(&mut T), default: T, )

Inserts elements into a nested interval structure by recursively traversing an iterator over iterators of range indices to either update existing leaf values or create new branches with default values.

The function operates by taking an iterator of iterators of ranges, a function to update leaf values, and a default value. For an internal node, it iterates over each range from the provided iterator: if a corresponding child exists, it recurses into that child with cloned iterators; if not, it creates a new branch using the default value. When a leaf node is reached and there are no more ranges, it applies the update function to modify the leaf’s contained value. The function will panic if the provided range structure does not match the depth of the tree.

pub fn insert_multiple<'a: 'b, 'b>( &'a mut self, ranges: &Vec<Vec<Range<usize>>>, value: T, )

Inserts a value at a nested tree leaf corresponding to a multi-dimensional sequence of interval ranges.

Uses a vector of interval range vectors to represent the nesting levels, delegating recursive insertion to a helper that traverses and builds intermediate nodes as needed, while using a no-op update function for branch nodes.

pub fn insert<'a: 'b, 'b>(&'a mut self, ranges: &[Range<usize>], value: T)

Inserts a value into the nested interval tree using a provided slice of ranges. This function transforms the slice of ranges into an iterator of one-item iterators and then delegates to the internal insertion procedure that supports multi-level range specifications.

impl<T> NestedIntervalTree<T>

pub fn new() -> Self

Creates an empty nested interval tree by initializing it as a node containing an empty interval map. This function serves as a constructor for the tree structure, providing a starting point for inserting ranges and associated values in later operations.

pub fn get(&self, ranges: &[Range<usize>]) -> Option<&T>

Retrieves a stored value by following a sequence of interval ranges across a nested data structure.

This function accepts a slice of range indices that represent a traversal path through nested intervals. It navigates the structure by, for non-empty range sequences, using the first range to determine which subtree to search and recursing with the remaining ranges, while returning the leaf’s value if there are no ranges left. If the provided path does not match the structure, it results in a None.

pub fn superrange_using_iter<'a: 'b, 'b>( &'a self, ranges: impl Iterator<Item = impl Iterator<Item = Range<usize>> + 'b> + Clone + 'b, ) -> Box<dyn Iterator<Item = &'b T> + 'b>

Returns an iterator over all values in the tree that are reachable via a chain of intervals where each enclosing interval is a superrange of the corresponding query range.

This method recursively traverses a nested interval structure using an iterator of iterators of ranges; in internal nodes it filters subintervals that fully contain the query interval and descends recursively, while at a leaf node with no remaining query ranges it yields the stored value. It panics if the depth of provided range sequences does not match the tree structure.

pub fn subrange_using_iter<'a: 'b, 'b>( &'a self, ranges: impl Iterator<Item = impl Iterator<Item = Range<usize>> + 'b> + Clone + 'b, ) -> Box<dyn Iterator<Item = &'b T> + 'b>

Returns an iterator over subrange-matching values from a nested interval tree structure based on a sequence of range iterators.

Processes a cloned iterator yielding iterators over range indices, where at each node it filters for entries whose ranges are completely contained within the provided range, and recursively applies the same filtering on the resulting subtrees. In the leaf case when no further range iterator is provided, it yields the leaf value, while differing iterator depths result in a runtime panic.

pub fn superrange_multiple<'a: 'b, 'b>( &'a self, ranges: &'b Vec<Vec<Range<usize>>>, ) -> Box<dyn Iterator<Item = &'b T> + 'b>

Returns an iterator over all values whose associated intervals contain the specified super ranges.

Delegates to a lower-level iterator implementation by mapping the provided vector of range vectors into an appropriate iterator form for traversing the nested interval structure, ultimately yielding references to values that satisfy the super-range condition.

pub fn subrange_multiple<'a: 'b, 'b>( &'a self, ranges: &'b Vec<Vec<Range<usize>>>, ) -> Box<dyn Iterator<Item = &'b T> + 'b>

Returns an iterator over elements from nested intervals that are enclosed by the specified multiple subrange lists provided as a vector of vectors.

Invokes an internal subrange retrieval function by mapping the provided vector of range lists into an iterator of cloned ranges, thereby allowing the caller to iterate over all matching elements in the tree that fall within the prescribed nested subranges.

pub fn superrange<'a: 'b, 'b>( &'a self, ranges: Vec<Range<usize>>, ) -> Box<dyn Iterator<Item = &'b T> + 'b>

Return an iterator yielding references to values whose associated intervals form a superrange of the provided sequence of index ranges. This function converts a vector of ranges into the expected single-element iterators and delegates the lookup to the underlying superrange retrieval logic, thereby providing access to all elements that satisfy the defined superrange condition.

pub fn subrange<'a: 'b, 'b>( &'a self, ranges: Vec<Range<usize>>, ) -> Box<dyn Iterator<Item = &'b T> + 'b>

Returns a boxed iterator over references to values matching the provided subrange specification.

Maps the given vector of ranges into the expected iterator form and delegates to an underlying iterator-based subrange retrieval method to extract matching elements from the nested structure.

Trait Implementations

impl<T> Default for NestedIntervalTree<T>

fn default() -> Self

Returns a default instance by invoking the constructor for a new instance. This implementation enables the use of default() to create an object with initial empty configuration without the need for manual initialization.