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>

Important traits for QueryIter<'a, K, V>

impl<'a, K: Ord, V> Iterator for QueryIter<'a, K, V> type Item = &'a Element<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).

Important traits for QueryIter<'a, K, V>

impl<'a, K: Ord, V> Iterator for QueryIter<'a, K, V> type Item = &'a Element<K, V>;

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

Important traits for TreeIter<'a, K, V>

impl<'a, K: 'a, V: 'a> Iterator for TreeIter<'a, K, V> type Item = &'a Element<K, V>;

pub 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, f: &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, state: &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?

Important traits for TreeIter<'a, K, V>

impl<'a, K: 'a, V: 'a> Iterator for TreeIter<'a, K, V> type Item = &'a Element<K, V>;

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?

Important traits for TreeIntoIter<K, V>

impl<K, V> Iterator for TreeIntoIter<K, V> type Item = Element<K, V>;

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

Creates an iterator from a value.