Struct IntervalTree

pub struct IntervalTree<D> {
    pub root: Option<Box<Node<D>>>,
}

Fields

root: Option<Box<Node<D>>>

Implementations

impl<D> IntervalTree<D>

pub fn new() -> IntervalTree<D>

This function will construct a new empty IntervalTree.

Examples

extern crate theban_interval_tree;
let mut t=theban_interval_tree::IntervalTree::<i32>::new();

pub fn insert(&mut self, key: Range, data: D)

This function will insert the key,value pair into the tree, overwriting the old data if the key is allready part of the tree.

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<i32>::new();
t.insert(memrange::Range::new(2,2),25);
assert_eq!(t.get(memrange::Range::new(2,2)), Some(&25));
t.insert(memrange::Range::new(2,2),30);
assert_eq!(t.get(memrange::Range::new(2,2)), Some(&30));

pub fn delete(&mut self, key: Range)

This function will remove the key,value pair from the tree, doing nothing if the key is not part of the tree.

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<i32>::new();
t.insert(memrange::Range::new(2,2),25);
t.delete(memrange::Range::new(2,2));
assert!(t.empty());
// deleting nonexistant keys doesn't do anything
t.delete(memrange::Range::new(3,3));
assert!(t.empty());

pub fn get(&self, key: Range) -> Option<&D>

This function will return the Some(data) stored under the given key or None if the key is not known.

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<i32>::new();
t.insert(memrange::Range::new(2,2),25);
assert_eq!(t.get(memrange::Range::new(2,2)), Some(&25));
assert_eq!(t.get(memrange::Range::new(3,3)), None);

pub fn get_or<'a>(&'a self, key: Range, default: &'a D) -> &D

This function will return the data stored under the given key or the default if the key is not known.

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<i32>::new();
t.insert(memrange::Range::new(2,2),25);
assert_eq!(t.get_or(memrange::Range::new(2,2),&2000), &25);
assert_eq!(t.get_or(memrange::Range::new(3,3),&2000), &2000);

pub fn contains(&self, key: Range) -> bool

This function will return true if the tree contains the given key, false otherwise

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<i32>::new();
t.insert(memrange::Range::new(2,2),25);
assert!(!t.contains(memrange::Range::new(3,3)));
assert!(t.contains(memrange::Range::new(2,2)));

pub fn empty(&self) -> bool

This function will return true if the tree is empty, false otherwise.

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<i32>::new();
assert!(t.empty());
t.insert(memrange::Range::new(2,2),25);
assert!(!t.empty());

pub fn min<'a>(&'a self) -> Option<(&'a Range, &'a D)>

This function will return the key/value pair with the smallest key in the tree, or None if the tree is empty.

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<u64>::new();
t.insert(memrange::Range::new(2,2),25);
t.insert(memrange::Range::new(3,3),50);
assert_eq!(t.min().unwrap().0, &memrange::Range::new(2,2));
assert_eq!(t.min().unwrap().1, &25);

pub fn max<'a>(&'a self) -> Option<(&'a Range, &'a D)>

This function will return the key/value pair with the biggest key in the tree, or None if the tree is empty.

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<i32>::new();
t.insert(memrange::Range::new(2,2),25);
t.insert(memrange::Range::new(3,3),50);
assert_eq!(t.max().unwrap().0, &memrange::Range::new(3,3));
assert_eq!(t.max().unwrap().1, &50);

pub fn height(&self) -> usize

This function will return the hieght of the tree. An empty tree hash height 0, one with only one elemente has height 1 etc.

Examples

extern crate memrange;
extern crate theban_interval_tree;

let mut t=theban_interval_tree::IntervalTree::<i32>::new();
assert_eq!(t.height(), 0);
t.insert(memrange::Range::new(2,2),3);
assert_eq!(t.height(), 1);

pub fn iter(&self) -> RangePairIter<'_, D>

This function will return a read only iterator for all (key,value) pairs in the tree.

Examples

for (key,val) in t.iter() {
    println!("{:?} -> {}",key,val)
}

pub fn range(&self, min: u64, max: u64) -> RangePairIter<'_, D>

This function will return a read only iterator for all (key,value) pairs between the two bounds.

Examples

//[...]
for (key,val) in t.range(9, 100) {
    println!("{:?} -> {}",key,val)
}

Trait Implementations

impl<D: Debug> Debug for IntervalTree<D>

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

Formats the value using the given formatter.