#datastructure #interval #tree #map

theban_interval_tree

A simple Interval Tree implementation

3 unstable releases

0.7.1 May 30, 2017
0.7.0 Apr 30, 2016
0.6.2 Apr 27, 2016

#434 in Data structures

Download history 279/week @ 2019-12-02 187/week @ 2019-12-09 226/week @ 2019-12-16 93/week @ 2019-12-23 95/week @ 2019-12-30 209/week @ 2020-01-06 212/week @ 2020-01-13 190/week @ 2020-01-20 209/week @ 2020-01-27 184/week @ 2020-02-03 216/week @ 2020-02-10 231/week @ 2020-02-17 254/week @ 2020-02-24 199/week @ 2020-03-02 316/week @ 2020-03-09 237/week @ 2020-03-16

782 downloads per month
Used in 10 crates (4 directly)

Custom license

27KB
510 lines

IntervalTree

A simple crate that implements a interval tree datastructure. An IntervalTree maps ranges of u64 to any value. We can than use the tree to perform querys such as "what key/value pairs are intersecting the range (x,y)?" does "does the tree contain the range (X,Y)?". Insertion, deletion and lookup are in O(log(n)). Iterating over all m solutions to a query is in O(m*log(n)).

extern crate theban_interval_tree;
extern crate rand;
extern crate time;
extern crate memrange;

use memrange::Range;

fn main(){
    let data = 4221;
    let mut t = theban_interval_tree::IntervalTree::<i32>::new();

    assert!(t.empty());
    assert!{t.min().is_none()};

    t.insert(Range::new(1,1), data);
    t.insert(Range::new(2,2), data+1);
    t.insert(Range::new(3,3), data+2);

    assert_eq!{t.min().expect("get min"),(&Range::new(1,1),&data)};

    assert!(!t.empty());
    assert!(t.get_or(Range::new(1,1), &0) == &data);
    assert!(!t.contains(Range::new(0,0)));

    t.delete(Range::new(1,1));

    assert!(!t.contains(Range::new(1,1)));

    for (i,pair) in t.iter().enumerate() {
        //[...]
    }

    for (i,pair) in t.range(34, 36).enumerate() {
        //[...]
    }
}

Dependencies

~1MB
~19K SLoC