Struct IntervalTree

Source

pub struct IntervalTree<T: Ord + Clone> { /* private fields */ }

Expand description

An immutable data structure for storing and querying a collection of intervals

§Example

use std::ops::Bound::*;
use im_interval_tree::{IntervalTree, Interval};

// Construct a tree of intervals
let tree : IntervalTree<u8> = IntervalTree::new();
let tree = tree.insert(Interval::new(Included(1), Excluded(3)));
let tree = tree.insert(Interval::new(Included(2), Excluded(4)));
let tree = tree.insert(Interval::new(Included(5), Unbounded));
let tree = tree.insert(Interval::new(Excluded(7), Included(8)));

// Query for overlapping intervals
let query = tree.query_interval(&Interval::new(Included(3), Included(6)));
assert_eq!(
    query.collect::<Vec<Interval<u8>>>(),
    vec![
        Interval::new(Included(2), Excluded(4)),
        Interval::new(Included(5), Unbounded)
    ]
);

// Query for a specific point
let query = tree.query_point(&2);
assert_eq!(
    query.collect::<Vec<Interval<u8>>>(),
    vec![
        Interval::new(Included(2), Excluded(4)),
        Interval::new(Included(1), Excluded(3))
    ]
);

Implementations§

Source §

impl<T: Ord + Clone> IntervalTree<T>

Source

pub fn new() -> IntervalTree<T>

Construct an empty IntervalTree

Source

pub fn insert(&self, interval: Interval<T>) -> IntervalTree<T>

Construct a new IntervalTree with the given Interval added

§Example

let tree : IntervalTree<u8> = IntervalTree::new();
let tree = tree.insert(Interval::new(Included(1), Included(2)));
assert_eq!(
    tree.iter().collect::<Vec<Interval<u8>>>(),
    vec![Interval::new(Included(1), Included(2))]
);

Source

pub fn remove(&self, interval: &Interval<T>) -> IntervalTree<T>

Construct a new IntervalTree minus the given Interval, if present

§Example

let tree : IntervalTree<u8> = IntervalTree::new();
let tree = tree.insert(Interval::new(Included(1), Included(2)));
let tree = tree.insert(Interval::new(Included(1), Included(3)));

let tree = tree.remove(&Interval::new(Included(1), Included(2)));
assert_eq!(
    tree.iter().collect::<Vec<Interval<u8>>>(),
    vec![Interval::new(Included(1), Included(3))]
);

Source

pub fn query_interval( &self, interval: &Interval<T>, ) -> impl Iterator<Item = Interval<T>> + '_

Return an Iterator over all the intervals in the tree that overlap with the given interval

§Example

let tree : IntervalTree<u8> = IntervalTree::new();
let tree = tree.insert(Interval::new(Included(1), Excluded(3)));
let tree = tree.insert(Interval::new(Included(5), Unbounded));

let query = tree.query_interval(&Interval::new(Included(3), Included(6)));
assert_eq!(
    query.collect::<Vec<Interval<u8>>>(),
    vec![Interval::new(Included(5), Unbounded)]
);

Source

pub fn query_point(&self, point: &T) -> impl Iterator<Item = Interval<T>> + '_

Return an Iterator over all the intervals in the tree that contain the given point

This is equivalent to tree.query_interval(Interval::new(Included(point), Included(point)))

§Example

let tree : IntervalTree<u8> = IntervalTree::new();
let tree = tree.insert(Interval::new(Included(1), Excluded(3)));
let tree = tree.insert(Interval::new(Included(5), Unbounded));

let query = tree.query_point(&2);
assert_eq!(
    query.collect::<Vec<Interval<u8>>>(),
    vec![Interval::new(Included(1), Excluded(3))]
);

Source

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

Return an Iterator over all the intervals in the tree

This is equivalent to tree.query_interval(Unbounded, Unbounded)

§Example

let tree : IntervalTree<u8> = IntervalTree::new();
let tree = tree.insert(Interval::new(Included(2), Excluded(4)));
let tree = tree.insert(Interval::new(Included(5), Unbounded));

let iter = tree.iter();
assert_eq!(
    iter.collect::<Vec<Interval<u8>>>(),
    vec![
        Interval::new(Included(2), Excluded(4)),
        Interval::new(Included(5), Unbounded),
    ]
);