Struct IntervalTree

Source

pub struct IntervalTree<K> { /* private fields */ }

Expand description

The interval tree storing all the underlying intervals.

There are three ways to create an interval tree.

use unbounded_interval_tree::interval_tree::IntervalTree;

// 1. Create an empty default interval tree.
let mut interval_tree = IntervalTree::default();
assert!(interval_tree.is_empty());
interval_tree.insert(0..9);
interval_tree.insert(27..);
assert_eq!(interval_tree.len(), 2);

// 2. Create an interval tree from an iterator.
let ranges = vec!["hello"..="hi", "Allo"..="Bonjour"];
let interval_tree = ranges.into_iter().collect::<IntervalTree<_>>();
assert_eq!(interval_tree.len(), 2);

// 3. Create an interval tree from an array.
let ranges = [(1, 5)..(1,9), (2, 3)..(3, 7)];
let interval_tree = IntervalTree::from(ranges);
assert_eq!(interval_tree.len(), 2);

Implementations§

Source §

impl<K> IntervalTree<K>

Source

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

Produces an inorder iterator for the interval tree.

§Examples

use std::ops::Bound::Included;
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut 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);

Source

pub fn insert<R>(&mut self, range: R)
where K: Ord + Clone, R: RangeBounds<K>,

Inserts an interval range into the interval tree. Insertions respect the binary search properties of this tree. It is ok to insert a range that overlaps with an existing interval in the 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};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut int_tree = IntervalTree::default();

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

let mut str_tree: IntervalTree<&str> = IntervalTree::default();

str_tree.insert("Noria"..);

Source

pub fn contains_point<Q>(&self, p: &Q) -> bool
where K: Ord + Borrow<Q>, Q: Ord + ?Sized,

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

The given point may be of a borrowed form of the stored type K.

§Examples

use std::ops::Bound::{Excluded, Unbounded};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut int_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 trait, so we are not limited to just integers.

use std::ops::Bound::{Excluded, Unbounded};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut str_tree = IntervalTree::default();

str_tree.insert((Excluded(String::from("Noria")), Unbounded));

// Borrowed form (`str`) of `String`.
assert!(!str_tree.contains_point("Noria"));
// Also works with non-borrowed form.
assert!(str_tree.contains_point(&String::from("Zebra")));

Source

pub fn contains_interval<Q, R>(&self, range: &R) -> bool
where K: Ord + Borrow<Q>, R: RangeBounds<Q>, Q: Ord + ?Sized,

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

The given range may have bounds that are of a borrowed form of the stored type K.

§Examples

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

let mut tree = IntervalTree::default();

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

assert!(tree.contains_interval(&(20..=40)));
// Borrowed form of the key works as well.
assert!(!tree.contains_interval(&(&30..=&50)));

Again, the given range can be any type implementing Ord.

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

let mut tree: IntervalTree<&str> = IntervalTree::default();

let key1 = (Included("a"), Excluded("h"));
let key2 = (Excluded("M"), Excluded("O"));

tree.insert(key1.clone());
tree.insert(key2);

assert!(tree.contains_interval(&("a".."h")));
assert!(!tree.contains_interval(&("N"..="O")));
// Sometimes, we have to disambiguate the key type.
assert!(tree.contains_interval::<&str, _>(&key1));

Source

pub fn get_interval_overlaps<Q, R>( &self, range: &R, ) -> Vec<&(Bound<K>, Bound<K>)>
where K: Ord + Borrow<Q>, R: RangeBounds<Q>, Q: Ord + ?Sized,

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

The given range may have bounds that are of a borrowed form of the stored type K.

§Examples

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

let mut tree = IntervalTree::default();

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

assert_eq!(tree.get_interval_overlaps(&(-5..7)),
           vec![&(Included(0), Included(5))]);
// Borrowed form of the key works as well.
assert!(tree.get_interval_overlaps(&(&10..)).is_empty());

Source

pub fn get_interval_difference<'a, Q, R>( &'a self, range: &'a R, ) -> Vec<(Bound<&'a Q>, Bound<&'a Q>)>
where K: Ord + Borrow<Q>, R: RangeBounds<Q>, Q: Ord + ?Sized,

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

If range is not covered at all, this simply returns a one element vector containing the bounds of range.

The given range may have bounds that are of a borrowed form of the stored type K. Because all the bounds returned are either from the interval tree of from the range, we return references to these bounds rather than clone them.

§Examples

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

let mut 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(&(-5..=30)),
           vec![(Included(&-5), Excluded(&0)),
                (Included(&10), Included(&10))]);
assert_eq!(tree.get_interval_difference(&(..10)),
           vec![(Unbounded, Excluded(&0))]);
assert!(tree.get_interval_difference(&(100..)).is_empty());

Source

pub fn remove_random_leaf(&mut self) -> Option<(Bound<K>, Bound<K>)>
where K: Ord + Clone,

Removes a random leaf from the tree, and returns the range stored in the said node.

The returned value will be None if the tree is empty.

§Examples

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

let mut tree = IntervalTree::default();

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

assert!(tree.contains_point(&10));
assert!(tree.contains_point(&6));

let deleted = tree.remove_random_leaf();
assert!(deleted.is_some());
assert!(!tree.contains_point(&10));
assert!(tree.contains_point(&6));

let deleted = tree.remove_random_leaf();
assert!(deleted.is_some());
assert!(!tree.contains_point(&6));

let deleted = tree.remove_random_leaf();
assert!(deleted.is_none());

Source

pub fn len(&self) -> usize

Returns the number of ranges stored in the interval tree.

§Examples

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

let mut tree = IntervalTree::default();

assert_eq!(tree.len(), 0);

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

assert_eq!(tree.len(), 2);

Source

pub fn is_empty(&self) -> bool

Returns true if the map contains no element.

§Examples

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

let mut tree = IntervalTree::default();

assert!(tree.is_empty());

tree.insert((Included(5), Excluded(9)));

assert!(!tree.is_empty());

Source

pub fn clear(&mut self)

Clear the interval tree, removing all values stored.

§Examples

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

let mut tree = IntervalTree::default();

tree.insert((Included(5), Unbounded));
tree.clear();

assert!(tree.is_empty());