Struct unbounded_interval_tree::interval_tree::IntervalTree

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

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

impl<K> IntervalTree<K>

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

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"..);

pub fn contains_point<Q>(&self, p: &Q) -> boolwhere
    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")));

pub fn contains_interval<Q, R>(&self, range: &R) -> boolwhere
    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));

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

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

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

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

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

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

Trait Implementations

impl<K: Clone> Clone for IntervalTree<K>

fn clone(&self) -> IntervalTree<K>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug> Debug for IntervalTree<K>

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

Formats the value using the given formatter.

impl<K> Default for IntervalTree<K>

fn default() -> IntervalTree<K>

Returns the “default value” for a type.

impl<K> Display for IntervalTree<K>where
    K: Display,

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

Formats the value using the given formatter.

impl<K, R, const N: usize> From<[R; N]> for IntervalTree<K>where
    K: Ord + Clone,
    R: RangeBounds<K>,

fn from(intervals: [R; N]) -> Self

Converts to this type from the input type.

impl<K, R> FromIterator<R> for IntervalTree<K>where
    K: Ord + Clone,
    R: RangeBounds<K>,

Creates an IntervalTree from an iterator of elements satisfying the RangeBounds trait.

fn from_iter<T: IntoIterator<Item = R>>(iter: T) -> Self

Creates a value from an iterator.

impl<K: PartialEq> PartialEq<IntervalTree<K>> for IntervalTree<K>

fn eq(&self, other: &IntervalTree<K>) -> bool

This method tests for self and other values to be equal, and is used by ==.

const fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K> StructuralPartialEq for IntervalTree<K>