Struct store_interval_tree::IntervalTree
source · pub struct IntervalTree<T: Ord, V> { /* private fields */ }
Expand description
An interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.
This data structure is backed by a store_interval_tree:IntervalTree
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
// initialize an interval tree with end points of type usize
let mut interval_tree = IntervalTree::<usize, ()>::new();
// insert interval into the tree
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
let interval1 = Interval::new(Excluded(23), Included(26));
// interval (25, 30] is overlapped with interval (23,26]
assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
// there is no interval in the tree that has interval with (10,15)
assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
// find all overlaps with an interval
let interval = Interval::new(Included(8), Included(26));
// intervals are: (8,9], [6,10],(19,20], [16,21), (15,23), [17,19), (25,30], [26,26]
let intervals = interval_tree.find_overlaps(&interval);
// delete interval
let interval = Interval::new(Included(15), Included(18));
let overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
interval_tree.delete(&overlapped_interval);
// find all intervals between two intervals/points
let low = Interval::point(14);
let high = Interval::point(24);
// intervals are: (15,23), [16,21), [17,19), (19,20]
let intervals = interval_tree.intervals_between(&low, &high);
Implementations
sourceimpl<T: Ord, V> IntervalTree<T, V>
impl<T: Ord, V> IntervalTree<T, V>
sourcepub fn new() -> IntervalTree<T, V>
pub fn new() -> IntervalTree<T, V>
Initialize an interval tree with end points of type usize
Examples
use store_interval_tree::IntervalTree;
let mut interval_tree = IntervalTree::<usize, ()>::new();
sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Returns true if there are no intervals in the tree, false otherwise
sourcepub fn query<'a, 'v, 'i>(
&'a self,
interval: &'i Interval<T>
) -> IntervalTreeIterator<'v, 'i, T, V> ⓘwhere
'a: 'v,
'a: 'i,
pub fn query<'a, 'v, 'i>(
&'a self,
interval: &'i Interval<T>
) -> IntervalTreeIterator<'v, 'i, T, V> ⓘwhere
'a: 'v,
'a: 'i,
Find overlapping intervals in the tree and returns an
IntervalTreeIterator
that allows access to the stored value
Arguments
interval
: interval to be searched for any overlaps
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
// insert interval into the tree
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
let interval1 = Interval::new(Excluded(23), Included(26));
// interval (25, 30] is overlapped with interval (23,26]
assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
// there is no interval in the tree that has interval with (10,15)
assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
sourcepub fn query_mut<'a, 'v, 'i>(
&'a mut self,
interval: &'i Interval<T>
) -> IntervalTreeIteratorMut<'v, 'i, T, V> ⓘwhere
'a: 'v,
'a: 'i,
pub fn query_mut<'a, 'v, 'i>(
&'a mut self,
interval: &'i Interval<T>
) -> IntervalTreeIteratorMut<'v, 'i, T, V> ⓘwhere
'a: 'v,
'a: 'i,
Find overlapping intervals in the tree and returns an
IntervalTreeIteratorMut
that allows mutable access to the stored value
Arguments
interval
: interval to be searched for any overlaps
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
// insert interval into the tree
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
let interval1 = Interval::new(Excluded(23), Included(26));
// interval (25, 30] is overlapped with interval (23,26]
assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
// there is no interval in the tree that has interval with (10,15)
assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
sourcepub fn overlaps(&self, interval: &Interval<T>) -> bool
pub fn overlaps(&self, interval: &Interval<T>) -> bool
Returns true if there exists an interval in the tree that overlaps with specified interval
Arguments
interval
: interval to be searched for any overlaps
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
assert!(!interval_tree.overlaps(&Interval::new(Included(4), Excluded(6))));
assert!(interval_tree.overlaps(&Interval::new(Included(4), Included(6))));
sourcepub fn find_overlap(&self, interval: &Interval<T>) -> Option<Interval<T>>
pub fn find_overlap(&self, interval: &Interval<T>) -> Option<Interval<T>>
Returns first interval that overlaps with specified interval
Arguments:
interval
: interval to be searched for any overlaps
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
// initialize an interval tree with end points of type usize
let mut interval_tree = IntervalTree::<usize, ()>::new();
// insert interval into the tree
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
let interval1 = Interval::new(Excluded(23), Included(26));
// interval (25, 30] is overlapped with interval (23,26]
assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
// there is no interval in the tree that has interval with (10,15)
assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
sourcepub fn find_overlaps(&self, interval: &Interval<T>) -> Vec<Interval<T>>
pub fn find_overlaps(&self, interval: &Interval<T>) -> Vec<Interval<T>>
Returns all intervals that overlap with the specified interval
Arguments
interval
: interval to be searched for any overlaps
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
// initialize an interval tree with end points of type usize
let mut interval_tree = IntervalTree::<usize, ()>::new();
// insert interval into the tree
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
// find all overlaps with an interval
let interval = Interval::new(Included(8), Included(26));
// intervals are: (8,9], [6,10],(19,20], [16,21), (15,23), [17,19), (25,30], [26,26]
let intervals = interval_tree.find_overlaps(&interval);
sourcepub fn insert(&mut self, interval: Interval<T>, value: V)
pub fn insert(&mut self, interval: Interval<T>, value: V)
Inserts an interval in the tree. if interval already exists, interval
will be ignored
Arguments
interval
: interval to be inserted in the tree
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
// initialize an interval tree with end points of type usize
let mut interval_tree = IntervalTree::<usize, ()>::new();
// insert interval into the tree
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
sourcepub fn delete(&mut self, interval: &Interval<T>)
pub fn delete(&mut self, interval: &Interval<T>)
Delete the specified interval
if found
Arguments
interval
: interval to be deleted
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
// initialize an interval tree with end points of type usize
let mut interval_tree = IntervalTree::<usize, ()>::new();
// insert interval into the tree
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
// delete interval
let interval = Interval::new(Included(15), Included(18));
let overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
interval_tree.delete(&overlapped_interval);
sourcepub fn delete_min(&mut self)
pub fn delete_min(&mut self)
Deletes minimum interval in the tree
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
interval_tree.delete_min();
interval_tree.delete_min();
assert!(interval_tree.find_overlap(&Interval::new(Included(1), Excluded(6))).is_none());
sourcepub fn delete_max(&mut self)
pub fn delete_max(&mut self)
Deletes maximum interval in the tree
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
interval_tree.delete_max();
interval_tree.delete_max();
assert!(interval_tree.find_overlap(&Interval::new(Included(25), Excluded(30))).is_none());
sourcepub fn select(&self, k: usize) -> Option<Interval<T>>
pub fn select(&self, k: usize) -> Option<Interval<T>>
Returns the kth smallest interval
Arguments
k
: the order statistic
Panics
- panics if k is not in range: 0 <= k <= size - 1
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
assert!(format!("{}", interval_tree.select(0).unwrap()) == String::from("[0,3)"));
assert!(format!("{}", interval_tree.select(1).unwrap()) == String::from("(0,1]"));
assert!(format!("{}", interval_tree.select(2).unwrap()) == String::from("[6,10]"));
assert!(format!("{}", interval_tree.select(3).unwrap()) == String::from("(8,9]"));
sourcepub fn intervals_between(
&self,
low_bound: &Interval<T>,
high_bound: &Interval<T>
) -> Vec<&Interval<T>>
pub fn intervals_between(
&self,
low_bound: &Interval<T>,
high_bound: &Interval<T>
) -> Vec<&Interval<T>>
Returns all intervals between two intervals/points
Arguments
low_bound
: lowest interval of the rangehigh_bound
: highest interval of the range
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
let low = Interval::new(Included(14), Included(14));
let high = Interval::new(Included(24), Included(24));
let intervals = interval_tree.intervals_between(&low, &high);
let accept = String::from("(15,23)[16,21)[17,19)(19,20]");
let mut result = String::from("");
for interval in intervals {
result.push_str(&format!("{}", interval))
}
assert_eq!(result, accept);
sourcepub fn intervals(&self) -> Vec<Interval<T>>
pub fn intervals(&self) -> Vec<Interval<T>>
Returns all intervals in the tree following an in-order traversal. Therefore intervals are sorted from smallest to largest
sourcepub fn rank(&self, interval: &Interval<T>) -> usize
pub fn rank(&self, interval: &Interval<T>) -> usize
Returns the number of intervals in the tree less than interval
Arguments
interval
: interval to be searched for
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
assert_eq!(interval_tree.rank(&Interval::point(5)), 1);
sourcepub fn size_between(
&self,
low_bound: &Interval<T>,
high_bound: &Interval<T>
) -> usize
pub fn size_between(
&self,
low_bound: &Interval<T>,
high_bound: &Interval<T>
) -> usize
Returns the number of intervals in the tree between low_bound
and high_bound
Arguments
low_bound
: lowest interval of the rangehigh_bound
: highest interval of the range
Examples
use store_interval_tree::IntervalTree;
use store_interval_tree::Interval;
use std::ops::Bound::*;
let mut interval_tree = IntervalTree::<usize, ()>::new();
interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
interval_tree.insert(Interval::new(Included(6), Included(10)), ());
interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
interval_tree.insert(Interval::new(Included(26), Included(26)), ());
let low = Interval::point(10);
let high = Interval::point(25);
assert_eq!(interval_tree.size_between(&low, &high), 5);
Trait Implementations
sourceimpl<T: Clone + Ord, V: Clone> Clone for IntervalTree<T, V>
impl<T: Clone + Ord, V: Clone> Clone for IntervalTree<T, V>
sourcefn clone(&self) -> IntervalTree<T, V>
fn clone(&self) -> IntervalTree<T, V>
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read more