Struct IST 

pub struct IST<K: Ord + Copy, V> { /* private fields */ }

Interval Query data type based on augmented binary search tree, written as IST but pronounced ‘Interval Search Tree’. IST is balanced using RBTree.

IST support handling overlapping intervals, non-overlapping intervals, as well as keeping track of multiple insertions into same interval.

Implementations

impl<K: Ord + Copy, V> IST<K, V>

pub fn new() -> IST<K, V>

Returns new Interval Search Tree

Example

use rtrees::ist::IST;
let mut ist: IST<u64, &'static str> = IST::new();

pub fn size(&self) -> u64

Returns the number of elements in the IST

Example

use rtrees::ist::IST;
let mut ist: IST<u64, &'static str> = IST::new();
assert_eq!(ist.size(), 0);
ist.insert(0, 5, &"[0, 5]");
assert_eq!(ist.size(), 1);
ist.insert(30, 34, &"[30, 34]");
assert_eq!(ist.size(), 2);
ist.insert(4, 11, &"[4, 11]");
assert_eq!(ist.size(), 3);

pub fn get_level(&self) -> u64

0 will be returned in case of empty IST. If IST has nodes, then get_level returns 1 + the number of connections between root and the farthest node from it.

Example

use rtrees::ist::IST;
let mut ist: IST<u64, &'static str> = IST::new();
assert_eq!(ist.get_level(), 0);
ist.insert(4, 11, &"[4, 11]");
assert_eq!(ist.get_level(), 1);
ist.insert(30, 34, &"[30, 34]");
assert_eq!(ist.get_level(), 2);
ist.insert(0, 5, &"[0, 5]");
assert_eq!(ist.get_level(), 2);
ist.insert(0, 3, &"[0, 3]");
assert_eq!(ist.get_level(), 3);

pub fn insert(&mut self, lo: K, hi: K, data: V)

Inserts an element into closed interval [ lo, hi ]. Insertion guarantess $𝒪\left(\log n\right)$ time. Insertion supports inserting multiple time into the same interval, and keeps track of all inserted data.

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(0,10, "First Insertion");
assert_eq!(ist.at(0), [&"First Insertion"]);
assert_eq!(ist.at(2), [&"First Insertion"]);
assert_eq!(ist.at(10), [&"First Insertion"]);

pub fn at(&self, point: K) -> Vec<&V>

Returns a vector of non mutable references of all values belogning to intervals that cover point. The vector is ordered based on intervals’ total order.

#example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(0,10, "First Insertion");
ist.insert(5, 20, "Second Insertion");
assert_eq!(ist.at(2), [&"First Insertion"]);
assert_eq!(ist.at(15), [&"Second Insertion"]);
assert_eq!(ist.at(9), [&"First Insertion", &"Second Insertion"]);
let empty_vector :Vec<&&str> = Vec::new();
assert_eq!(ist.at(21), empty_vector);

pub fn at_mut(&mut self, point: K) -> Vec<&mut V>

Returns a vector of mutable references of all values belogning to intervals that cover point. The vector is ordered based on intervals’ total order.

#example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(0,10, String::from("First Insertion"));
ist.at_mut(5)[0].push_str(" Modified");
assert_eq!(ist.at(5), [&"First Insertion Modified"]);

pub fn envelop(&self, lo: K, hi: K) -> Vec<&V>

Returns a vector of non mutable references of all values that belongs to intervals that envelop the interval specified by [ lo, hi ]. The vector is ordered based on intervals’ total order.

An interval [ A, B ] is said to be envloping interval [ lo, hi ] IFF lo ≥ A and lo ≤ B and hi ≥ A and hi ≤ B.

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(0,10, "First Insertion");
ist.insert(5, 20, "Second Insertion");
assert_eq!(ist.envelop(8, 12), [&"Second Insertion"]);
assert_eq!(ist.envelop(5, 10), [&"First Insertion", &"Second Insertion"]);
assert_eq!(ist.envelop(0, 3), [&"First Insertion"]);
let empty_vector :Vec<&&str> = Vec::new();
assert_eq!(ist.envelop(0, 30), empty_vector);

pub fn envelop_mut(&mut self, lo: K, hi: K) -> Vec<&mut V>

Returns a vector of mutable references of all values that belongs to intervals that envelop the interval specified by [ lo, hi ]. The vector is ordered based on intervals’ total order.

An interval [ A, B ] is said to be envloping interval [ lo, hi ] IFF lo ≥ A and lo ≤ B and hi ≥ A and hi ≤ B.

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(0,10, String::from("First Insertion"));
ist.envelop_mut(7, 10)[0].push_str(" Modified");
assert_eq!(ist.envelop(2, 4), [&"First Insertion Modified"]);

pub fn inverse_envelop(&self, lo: K, hi: K) -> Vec<&V>

Returns a vector of non mutable references of all values that belongs to intervals that is enveloped interval specified by [ lo, hi ]. The vector is ordered based on intervals’ total order.

An interval [ A, B ] is said to be envloped by interval [ lo, hi ] IFF lo ≤ A and lo ≤ B and hi ≥ A and hi ≥ B.

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(5,10, "First Insertion");
ist.insert(15, 20, "Second Insertion");
assert_eq!(ist.inverse_envelop(0, 12), [&"First Insertion"]);
assert_eq!(ist.inverse_envelop(0, 20), [&"First Insertion", &"Second Insertion"]);
assert_eq!(ist.inverse_envelop(12, 21), [&"Second Insertion"]);
let empty_vector :Vec<&&str> = Vec::new();
assert_eq!(ist.envelop(0, 7), empty_vector);

pub fn inverse_envelop_mut(&mut self, lo: K, hi: K) -> Vec<&mut V>

Returns a vector of non mutable references of all values that belongs to intervals that is enveloped interval specified by [ lo, hi ]. The vector is ordered based on intervals’ total order.

An interval [ A, B ] is said to be envloped by interval [ lo, hi ] IFF lo ≤ A and lo ≤ B and hi ≥ A and hi ≥ B.

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(2,10, String::from("First Insertion"));
ist.inverse_envelop_mut(0, 20)[0].push_str(" Modified");
assert_eq!(ist.envelop(3, 5), [&"First Insertion Modified"]);

pub fn overlap(&self, lo: K, hi: K) -> Vec<&V>

Returns a vector of non mutable references of all values that belongs to intervals that overlap with the interval specified by [ lo, hi ]. The vector is ordered based on intervals’ total order.

Two interval [ A, B ], [ lo, hi ] are said to be overlapping IFF max(A, lo) ≤ min(B, hi).

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(0,20, "First Insertion");
ist.insert(60, 80, "Second Insertion");
assert_eq!(ist.overlap(40, 70), [&"Second Insertion"]);
assert_eq!(ist.overlap(10, 40), [&"First Insertion"]);
assert_eq!(ist.overlap(10, 100), [&"First Insertion", &"Second Insertion"]);
let empty_vector :Vec<&&str> = Vec::new();
assert_eq!(ist.envelop(30, 40), empty_vector);

pub fn overlap_mut(&mut self, lo: K, hi: K) -> Vec<&mut V>

Returns a vector of mutable references of all values that belongs to intervals that overlap with the interval specified by [ lo, hi ]. The vector is ordered based on intervals’ total order.

Two interval [ A, B ], [ lo, hi ] are said to be overlapping IFF max(A, lo) ≤ min(B, hi).

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(10, 20, String::from("First Insertion"));
ist.overlap_mut(7, 13)[0].push_str(" Modified");
assert_eq!(ist.overlap(18, 25), [&"First Insertion Modified"]);

pub fn delete_at(&mut self, point: K) -> Vec<V>

Deletes all Intervals that that cover point. The returned data is a vector of data stored inside the deleted intervals.

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(10, 30, String::from("First Insertion"));
ist.insert(15, 35, String::from("Second Insertion"));
assert_eq!(ist.at(25), [&"First Insertion", &"Second Insertion"]);
assert_eq!(ist.delete_at(20), ["First Insertion", "Second Insertion"]);
let empty_vec: Vec<&&'static str> = Vec::new();
assert_eq!(ist.overlap(0, 50), empty_vec);

pub fn delete_envelop(&mut self, lo: K, hi: K) -> Vec<V>

Deletes all Intervals that envelop the interval specified by [ lo, hi ]. The returned data is a vector of data stored inside the deleted intervals.

An interval [ A, B ] is said to be envloping interval [ lo, hi ] IFF lo ≥ A and lo ≤ B and hi ≥ A and hi ≤ B.

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(10, 30, String::from("First Insertion"));
ist.insert(15, 35, String::from("Second Insertion"));
assert_eq!(ist.envelop(20, 25), [&"First Insertion", &"Second Insertion"]);
assert_eq!(ist.delete_envelop(20, 25), ["First Insertion", "Second Insertion"]);
let empty_vec: Vec<&&'static str> = Vec::new();
assert_eq!(ist.envelop(20, 25), empty_vec);

pub fn delete_overlap(&mut self, lo: K, hi: K) -> Vec<V>

Deletes all Intervals that overlap with the interval specified by [ lo, hi ]. The returned data is a vector of data stored inside the deleted intervals.

Two interval [ A, B ], [ lo, hi ] are said to be overlapping IFF max(A, lo) ≤ min(B, hi).

Panics

Panics if lo > hi

Example

use rtrees::ist::IST;
let mut ist = IST::new();
ist.insert(5, 15, String::from("First Insertion"));
ist.insert(10, 20, String::from("Second Insertion"));
assert_eq!(ist.envelop(10, 15), [&"First Insertion", &"Second Insertion"]);
assert_eq!(ist.delete_overlap(0, 7), ["First Insertion"]);
assert_eq!(ist.delete_overlap(17, 27), ["Second Insertion"]);
let empty_vec: Vec<&&'static str> = Vec::new();
assert_eq!(ist.envelop(20, 25), empty_vec);

Trait Implementations

impl<K: Ord + Copy, V> Default for IST<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, K: Ord + Copy, V> IntoIterator for &'a IST<K, V>

type Item = (K, K, &'a V)

The type of the elements being iterated over.

type IntoIter = ISTRefIterator<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> ISTRefIterator<'a, K, V>

Creates an iterator from a value.

impl<K: Ord + Copy, V> IntoIterator for IST<K, V>

type Item = (K, K, V)

The type of the elements being iterated over.

type IntoIter = ISTIterator<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> ISTIterator<K, V>

Creates an iterator from a value.