Struct IntervalTree 

pub struct IntervalTree<T> { /* private fields */ }

A static augmented interval tree using an implicit BST layout.

Built once from a set of intervals, then supports efficient overlap queries. The tree cannot be modified after construction.

Implementations

impl<T> IntervalTree<T>

pub fn from_unsorted(intervals: Vec<Interval<T>>) -> Self

Build an interval tree from unsorted intervals. O(n log n).

pub fn from_sorted(intervals: Vec<Interval<T>>) -> Self

Build an interval tree from intervals sorted by start coordinate. O(n).

pub fn query(&self, start: u64, end: u64) -> Vec<&Interval<T>>

Query all intervals overlapping the range [start, end).

Returns references to all intervals where interval.start < end && interval.end > start.

pub fn count_overlaps(&self, start: u64, end: u64) -> usize

Count intervals overlapping the range [start, end) without allocating.

pub fn nearest(&self, point: u64) -> Option<&Interval<T>>

Find the nearest interval to a point.

Returns the interval whose midpoint is closest to point. If multiple intervals are equidistant, returns one arbitrarily.

pub fn preceding(&self, point: u64) -> Option<&Interval<T>>

Find the nearest interval that ends at or before point.

Returns the interval with the largest end that is <= point.

pub fn following(&self, point: u64) -> Option<&Interval<T>>

Find the nearest interval that starts at or after point.

Returns the interval with the smallest start that is >= point.

pub fn len(&self) -> usize

Number of intervals in the tree.

pub fn is_empty(&self) -> bool

Whether the tree contains no intervals.

pub fn iter(&self) -> impl Iterator<Item = &Interval<T>>

Iterate over all intervals in the tree (in-order traversal).

Trait Implementations

impl<T: Clone> Clone for IntervalTree<T>

fn clone(&self) -> IntervalTree<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for IntervalTree<T>

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

Formats the value using the given formatter.