Struct intervaltree::IntervalTree

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

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

Methods

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

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

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

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

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

Trait Implementations

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

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

Returns a copy 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, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

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

fn hash<__HKV: Hasher>(&self, __arg_0: &mut __HKV)

Feeds this value into the given [Hasher].

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

Feeds a slice of this type into the given [Hasher].

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<'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.