3 unstable releases
Uses old Rust 2015
0.7.1 | May 30, 2017 |
---|---|
0.7.0 | Apr 30, 2016 |
0.6.2 | Apr 27, 2016 |
#1968 in Data structures
288 downloads per month
Used in 7 crates
(3 directly)
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
~1.2–1.5MB
~25K SLoC