Struct IntervalTree

pub struct IntervalTree<T, D>
where
    T: IntervalType,
{ /* private fields */ }

An Interval Tree.

Implementations

impl<T, D> IntervalTree<T, D>

where T: IntervalType,

pub fn new_from_entry<I>(entry: I) -> Self

where I: Into<IntervalTreeEntry<T, D>>,

Creates a new IntervalTree from a root entry.

Parameters

• entry - The first entry.

Example

use space_partitioning::IntervalTree;
let tree = IntervalTree::new_from_entry((15..=20, "data"));
assert_eq!(tree.len(), 1);

pub fn insert<I>(&mut self, entry: I) -> &Self

where I: Into<IntervalTreeEntry<T, D>>,

Inserts a new entry to the IntervalTree.

Parameters

• entry - The entry to insert.

Example

use space_partitioning::IntervalTree;
let mut tree = IntervalTree::default();
tree.insert((15..=20, "data"));
assert_eq!(tree.len(), 1);

pub fn len(&self) -> usize

Returns the number of elements in the IntervalTree.

Example

use space_partitioning::IntervalTree;
let tree = IntervalTree::new_from_entry((15..=20, "data"));
assert_eq!(tree.len(), 1);

pub fn is_empty(&self) -> bool

Returns whether the tree is empty, i.e., whether it has no elements.

Example

use space_partitioning::IntervalTree;
let tree = IntervalTree::<i32, ()>::default();
assert!(tree.is_empty());

pub fn overlap_search<I>(&self, interval: I) -> Option<&IntervalTreeEntry<T, D>>

where I: Into<Interval<T>>,

Queries the tree for overlaps with the specified interval.

/// # Parameters

• interval - The interval to query for.

Example

use space_partitioning::IntervalTree;
use space_partitioning::interval_tree::Interval;

let mut tree = IntervalTree::new_from_entry((15..=20, "A"));
tree.insert((100..=101, "B"));

let matched_a = tree.overlap_search(&(18..=25).into()).unwrap();
assert_eq!(matched_a.interval.start, 15);
assert_eq!(matched_a.interval.end, 20);
assert_eq!(matched_a.data, "A");

let matched_b = tree.overlap_search(&(100..=100).into()).unwrap();
assert_eq!(matched_b.interval.start, 100);
assert_eq!(matched_b.interval.end, 101);
assert_eq!(matched_b.data, "B");

let no_match = tree.overlap_search(0..=5);
assert!(no_match.is_none());

pub fn iter_inorder(&self) -> InorderIterator<'_, T, D>

Returns an InorderIterator<T, D> that iterates the tree elements in order of their interval starts.

Example

use space_partitioning::IntervalTree;
use std::iter::FromIterator;

let tree = IntervalTree::from_iter([(18..=25, "abc"), (0..=20, "xyz")]);
let mut iter = tree.iter_inorder();

let first = iter.next().unwrap();
assert_eq!(first.interval.start, 0);
assert_eq!(first.interval.end, 20);
assert_eq!(first.data, "xyz");

let second = iter.next().unwrap();
assert_eq!(second.interval.start, 18);
assert_eq!(second.interval.end, 25);
assert_eq!(second.data, "abc");

assert!(iter.next().is_none());

Trait Implementations

impl<T, D> Debug for IntervalTree<T, D>

where T: Debug + IntervalType,

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

Formats the value using the given formatter.

impl<T, D> Default for IntervalTree<T, D>

where T: IntervalType,

fn default() -> Self

Returns an empty IntervalTree<T, D>.

Example

use space_partitioning::IntervalTree;
let tree = IntervalTree::<i32, ()>::default();
assert_eq!(tree.len(), 0);

impl<T, D> From<(Interval<T>, D)> for IntervalTree<T, D>

where T: IntervalType,

fn from(value: (Interval<T>, D)) -> Self

Converts to this type from the input type.

impl<T> From<Interval<T>> for IntervalTree<T, ()>

where T: IntervalType,

fn from(interval: Interval<T>) -> Self

Converts to this type from the input type.

impl<I, T, D> FromIterator<I> for IntervalTree<T, D>

where I: Into<IntervalTreeEntry<T, D>>, T: IntervalType,

fn from_iter<Iter>(iter: Iter) -> Self

where Iter: IntoIterator<Item = I>,

Creates a value from an iterator.