Struct IntervalTree 

pub struct IntervalTree<K, V> { /* private fields */ }

A simple and generic implementation of an immutable interval tree.

To build it, always use FromIterator. This is not very optimized as it takes O(log n) stack (it uses recursion) but runs in O(n log n).

Implementations

impl<K: Ord, V> IntervalTree<K, V>

pub fn query(&self, range: Range<K>) -> QueryIter<'_, K, V>

Queries the interval tree for all elements overlapping a given interval.

This runs in O(log n + m).

pub fn query_point(&self, point: K) -> QueryIter<'_, K, V>

Queries the interval tree for all elements containing a given point.

This runs in O(log n + m).

pub fn iter(&self) -> TreeIter<'_, K, V>

Returns an iterator over all elements in the tree (in no particular order).

pub fn iter_sorted(&self) -> impl Iterator<Item = &Element<K, V>>

Returns an iterator over all elements in the tree, sorted by Element.range.start.

This is currently identical to IntervalTree::iter because the internal structure is already sorted this way, but may not be in the future.

Trait Implementations

impl<K: Clone, V: Clone> Clone for IntervalTree<K, V>

fn clone(&self) -> IntervalTree<K, V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for IntervalTree<K, V>

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

Formats the value using the given formatter.

impl<K: Ord + Clone, V, I: Into<Element<K, V>>> FromIterator<I> for IntervalTree<K, V>

fn from_iter<T: IntoIterator<Item = I>>(iter: T) -> Self

Creates a value from an iterator.

impl<K: Hash, V: Hash> Hash for IntervalTree<K, V>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<'a, K: 'a + Ord, V: 'a> IntoIterator for &'a IntervalTree<K, V>

type Item = &'a Element<K, V>

The type of the elements being iterated over.

type IntoIter = TreeIter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> TreeIter<'a, K, V>

Creates an iterator from a value.

impl<K, V> IntoIterator for IntervalTree<K, V>

type Item = Element<K, V>

The type of the elements being iterated over.

type IntoIter = TreeIntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> TreeIntoIter<K, V>

Creates an iterator from a value.