Struct unbounded_interval_tree::IntervalTree

pub struct IntervalTree<Q: Ord + Clone> { /* fields omitted */ }

The interval tree storing all the underlying intervals.

Methods

impl<Q> IntervalTree<Q> where
    Q: Ord + Clone, 

Important traits for IntervalTreeIter<'a, Q>

impl<'a, Q> Iterator for IntervalTreeIter<'a, Q> where
    Q: Ord + Clone,  type Item = &'a (Bound<Q>, Bound<Q>);

pub fn iter<'a>(&'a self) -> IntervalTreeIter<'a, Q>

Produces an inorder iterator for the interval tree.

Examples

use std::ops::Bound::Included;

let mut tree = unbounded_interval_tree::IntervalTree::default();

tree.insert((Included(0), Included(10)));
tree.insert((Included(-5), Included(-1)));
tree.insert((Included(20), Included(30)));

let mut iter = tree.iter();
assert_eq!(iter.next(), Some(&(Included(-5), Included(-1))));
assert_eq!(iter.next(), Some(&(Included(0), Included(10))));
assert_eq!(iter.next(), Some(&(Included(20), Included(30))));
assert_eq!(iter.next(), None);

pub fn insert(&mut self, range: (Bound<Q>, Bound<Q>))

Inserts an interval range into the interval tree. Insertions respect the binary search properties of this tree. An improvement to come is to rebalance the tree (following an AVL or a red-black scheme).

Examples

use std::ops::Bound::{Included, Excluded, Unbounded};

let mut int_tree = unbounded_interval_tree::IntervalTree::default();

int_tree.insert((Included(5), Excluded(9)));
int_tree.insert((Unbounded, Included(10)));

let mut str_tree = unbounded_interval_tree::IntervalTree::default();

str_tree.insert((Included("Noria"), Unbounded));

pub fn contains_point(&self, q: &Q) -> bool

A "stabbing query" in the jargon: returns whether or not a point q is contained in any of the intervals stored in the tree.

Examples

use std::ops::Bound::{Excluded, Unbounded};

let mut int_tree = unbounded_interval_tree::IntervalTree::default();

int_tree.insert((Excluded(5), Unbounded));

assert!(int_tree.contains_point(&100));
assert!(!int_tree.contains_point(&5));

Note that we can work with any type that implements the Ord+Clone traits, so we are not limited to just integers.

use std::ops::Bound::{Excluded, Unbounded};

let mut str_tree = unbounded_interval_tree::IntervalTree::default();

str_tree.insert((Excluded("Noria"), Unbounded));

assert!(str_tree.contains_point(&"Zebra"));
assert!(!str_tree.contains_point(&"Noria"));

pub fn contains_interval(&self, q: &(Bound<Q>, Bound<Q>)) -> bool

An alternative "stabbing query": returns whether or not an interval q is fully covered by the intervals stored in the tree.

Examples

use std::ops::Bound::{Included, Excluded, Unbounded};

let mut tree = unbounded_interval_tree::IntervalTree::default();

tree.insert((Included(20), Included(30)));
tree.insert((Excluded(30), Excluded(50)));

assert!(tree.contains_interval(&(Included(20), Included(40))));
assert!(!tree.contains_interval(&(Included(30), Included(50))));

pub fn get_interval_overlaps(
    &self,
    q: &(Bound<Q>, Bound<Q>)
) -> Vec<&(Bound<Q>, Bound<Q>)>

Returns the inorder list of all intervals stored in the tree that overlaps with a given range q (partially or completely).

Examples

use std::ops::Bound::{Included, Excluded, Unbounded};

let mut tree = unbounded_interval_tree::IntervalTree::default();

tree.insert((Included(0), Included(5)));
tree.insert((Included(7), Excluded(10)));

assert_eq!(tree.get_interval_overlaps(&(Included(-5), Excluded(7))),
           vec![&(Included(0), Included(5))]);
assert!(tree.get_interval_overlaps(&(Included(10), Unbounded)).is_empty());

pub fn get_interval_difference<'a>(
    &'a self,
    q: &'a (Bound<Q>, Bound<Q>)
) -> Vec<(Bound<&'a Q>, Bound<&'a Q>)>

Returns the ordered list of subintervals in q that are not covered by the tree. This is useful to compute what subsegments of q that are not covered by the intervals stored in the tree.

Examples

use std::ops::Bound::{Included, Excluded, Unbounded};

let mut tree = unbounded_interval_tree::IntervalTree::default();

tree.insert((Included(0), Excluded(10)));
tree.insert((Excluded(10), Included(30)));
tree.insert((Excluded(50), Unbounded));

assert_eq!(tree.get_interval_difference(&(Included(-5), Included(30))),
           vec![(Included(&-5), Excluded(&0)),
                (Included(&10), Included(&10))]);
assert_eq!(tree.get_interval_difference(&(Unbounded, Excluded(10))),
           vec![(Unbounded, Excluded(&0))]);
assert!(tree.get_interval_difference(&(Included(100), Unbounded)).is_empty());

Trait Implementations

impl<Q: Clone + Ord> Clone for IntervalTree<Q>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Q> Default for IntervalTree<Q> where
    Q: Ord + Clone, 

fn default() -> IntervalTree<Q>

Returns the "default value" for a type.