store_interval_tree

Struct 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§

Source§

impl<T: Ord, V> IntervalTree<T, V>

Source

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();
Source

pub fn is_empty(&self) -> bool

Returns true if there are no intervals in the tree, false otherwise

Source

pub fn size(&self) -> usize

Returns total number of intervals in the tree

Source

pub fn height(&self) -> i64

Returns height of the tree

Source

pub fn query<'a, 'v, 'i>( &'a self, interval: &'i Interval<T>, ) -> IntervalTreeIterator<'v, 'i, T, V> ⓘ
where 'a: 'v + '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());
Source

pub fn query_mut<'a, 'v, 'i>( &'a mut self, interval: &'i Interval<T>, ) -> IntervalTreeIteratorMut<'v, 'i, T, V> ⓘ
where 'a: 'v + '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());
Source

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))));
Source

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());
Source

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);
Source

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)), ());
Source

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);
Source

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());
Source

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());
Source

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]"));
Source

pub fn min(&self) -> Option<Interval<T>>

Returns minimum interval in the tree

Source

pub fn max(&self) -> Option<Interval<T>>

Returns maximum interval in the tree

Source

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 range
  • high_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);
Source

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

Source

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);
Source

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 range
  • high_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§

Source§

impl<T: Clone + Ord, V: Clone> Clone for IntervalTree<T, V>

Source§

fn clone(&self) -> IntervalTree<T, V>

Returns a duplicate of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<T: Debug + Ord, V: Debug> Debug for IntervalTree<T, V>

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<T: Default + Ord, V: Default> Default for IntervalTree<T, V>

Source§

fn default() -> IntervalTree<T, V>

Returns the “default value” for a type. Read more
Source§

impl<T: Hash + Ord, V: Hash> Hash for IntervalTree<T, V>

Source§

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher. Read more
1.3.0 · Source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more

Auto Trait Implementations§

§

impl<T, V> Freeze for IntervalTree<T, V>

§

impl<T, V> RefUnwindSafe for IntervalTree<T, V>
where V: RefUnwindSafe, T: RefUnwindSafe,

§

impl<T, V> !Send for IntervalTree<T, V>

§

impl<T, V> !Sync for IntervalTree<T, V>

§

impl<T, V> Unpin for IntervalTree<T, V>

§

impl<T, V> UnwindSafe for IntervalTree<T, V>
where V: UnwindSafe, T: RefUnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.