theban_interval_tree::tree

Struct IntervalTree

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

Fields§

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

Implementations§

Source§

impl<D> IntervalTree<D>

Source

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

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

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

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

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

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

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

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

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

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

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

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§

Source§

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

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<D> Freeze for IntervalTree<D>

§

impl<D> RefUnwindSafe for IntervalTree<D>
where D: RefUnwindSafe,

§

impl<D> Send for IntervalTree<D>
where D: Send,

§

impl<D> Sync for IntervalTree<D>
where D: Sync,

§

impl<D> Unpin for IntervalTree<D>

§

impl<D> UnwindSafe for IntervalTree<D>
where D: UnwindSafe,

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> 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, 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.