1 use node::Node;
2 use memrange::Range;
3 use node::{insert,delete,search,min_pair, max_pair, height};
4 use iterators::RangePairIter;
5 
6 #[derive(Debug)]
7 pub struct IntervalTree<D> {
8     pub root: Option<Box<Node<D>>>
9 }
10 
11 impl <D> IntervalTree<D>{
12 
13 
14 /// This function will construct a new empty IntervalTree.
15 /// # Examples
16 /// ```
17 /// extern crate theban_interval_tree;
18 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
19 /// ```
new() -> IntervalTree<D>20     pub fn new() -> IntervalTree<D>{
21         IntervalTree{root: None}
22     }
23 
24 /// This function will insert the key,value pair into the tree, overwriting the old data if the key is allready
25 /// part of the tree.
26 /// # Examples
27 /// ```
28 /// extern crate memrange;
29 /// extern crate theban_interval_tree;
30 ///
31 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
32 /// t.insert(memrange::Range::new(2,2),25);
33 /// assert_eq!(t.get(memrange::Range::new(2,2)), Some(&25));
34 /// t.insert(memrange::Range::new(2,2),30);
35 /// assert_eq!(t.get(memrange::Range::new(2,2)), Some(&30));
36 /// ```
insert(&mut self, key: Range, data: D)37     pub fn insert(&mut self, key: Range, data: D) {
38         match self.root.take() {
39             Some(box_to_node) => self.root = Some(insert::<D>(key, data, box_to_node)),
40             None => self.root = Some(Box::new(Node::new(key,data))),
41         }
42     }
43 
44 /// This function will remove the key,value pair from the tree, doing nothing if the key is not
45 /// part of the tree.
46 /// # Examples
47 /// ```
48 /// extern crate memrange;
49 /// extern crate theban_interval_tree;
50 ///
51 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
52 /// t.insert(memrange::Range::new(2,2),25);
53 /// t.delete(memrange::Range::new(2,2));
54 /// assert!(t.empty());
55 /// // deleting nonexistant keys doesn't do anything
56 /// t.delete(memrange::Range::new(3,3));
57 /// assert!(t.empty());
58 /// ```
delete(&mut self, key: Range)59     pub fn delete(&mut self, key: Range){
60         match self.root.take() {
61             Some(box_to_node) => self.root = delete(key,box_to_node),
62             None => return
63         }
64     }
65 
66 /// This function will return the Some(data) stored under the given key or None if the key is not
67 /// known.
68 /// # Examples
69 /// ```
70 /// extern crate memrange;
71 /// extern crate theban_interval_tree;
72 ///
73 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
74 /// t.insert(memrange::Range::new(2,2),25);
75 /// assert_eq!(t.get(memrange::Range::new(2,2)), Some(&25));
76 /// assert_eq!(t.get(memrange::Range::new(3,3)), None);
77 ///
78 /// ```
get(&self, key: Range) -> Option<&D>79     pub fn get(&self, key: Range) -> Option<&D>{
80         match self.root {
81             Some(ref box_to_node) =>search(&key, box_to_node),
82             None => None
83         }
84     }
85 
86 /// This function will return the data stored under the given key or the default if the key is not
87 /// known.
88 /// # Examples
89 /// ```
90 /// extern crate memrange;
91 /// extern crate theban_interval_tree;
92 ///
93 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
94 /// t.insert(memrange::Range::new(2,2),25);
95 /// assert_eq!(t.get_or(memrange::Range::new(2,2),&2000), &25);
96 /// assert_eq!(t.get_or(memrange::Range::new(3,3),&2000), &2000);
97 ///
98 /// ```
get_or<'a>(&'a self, key: Range, default: &'a D) -> &D99     pub fn get_or<'a>(&'a self, key: Range, default: &'a D) -> &D{
100         self.get(key).map_or(default, |data| data)
101     }
102 
103 /// This function will return true if the tree contains the given key, false otherwise
104 /// # Examples
105 /// ```
106 /// extern crate memrange;
107 /// extern crate theban_interval_tree;
108 ///
109 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
110 /// t.insert(memrange::Range::new(2,2),25);
111 /// assert!(!t.contains(memrange::Range::new(3,3)));
112 /// assert!(t.contains(memrange::Range::new(2,2)));
113 ///
114 /// ```
contains(&self, key: Range) -> bool115     pub fn contains(&self, key: Range) -> bool {
116         self.get(key).is_some()
117     }
118 
119 /// This function will return true if the tree is empty, false otherwise.
120 /// # Examples
121 /// ```
122 /// extern crate memrange;
123 /// extern crate theban_interval_tree;
124 ///
125 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
126 /// assert!(t.empty());
127 /// t.insert(memrange::Range::new(2,2),25);
128 /// assert!(!t.empty());
129 ///
130 /// ```
empty(&self) -> bool131     pub fn empty(&self) -> bool { self.root.is_none() }
132 
133 /// This function will return the key/value pair with the smallest key in the tree, or None if the
134 /// tree is empty.
135 /// # Examples
136 /// ```
137 /// extern crate memrange;
138 /// extern crate theban_interval_tree;
139 ///
140 /// let mut t=theban_interval_tree::IntervalTree::<u64>::new();
141 /// t.insert(memrange::Range::new(2,2),25);
142 /// t.insert(memrange::Range::new(3,3),50);
143 /// assert_eq!(t.min().unwrap().0, &memrange::Range::new(2,2));
144 /// assert_eq!(t.min().unwrap().1, &25);
145 ///
146 /// ```
min<'a>(&'a self) -> Option<(&'a Range,&'a D)>147     pub fn min<'a>(&'a self) -> Option<(&'a Range,&'a D)> {
148         match self.root {
149             Some(ref root) => Some(min_pair(root)),
150             None => None
151         }
152     }
153 
154 /// This function will return the key/value pair with the biggest key in the tree, or None if the
155 /// tree is empty.
156 /// # Examples
157 /// ```
158 /// extern crate memrange;
159 /// extern crate theban_interval_tree;
160 ///
161 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
162 /// t.insert(memrange::Range::new(2,2),25);
163 /// t.insert(memrange::Range::new(3,3),50);
164 /// assert_eq!(t.max().unwrap().0, &memrange::Range::new(3,3));
165 /// assert_eq!(t.max().unwrap().1, &50);
166 ///
167 /// ```
max<'a>(&'a self) -> Option<(&'a Range,&'a D)>168     pub fn max<'a>(&'a self) -> Option<(&'a Range,&'a D)> {
169         match self.root {
170             Some(ref root) => Some(max_pair(root)),
171             None => None
172         }
173     }
174 
175 /// This function will return the hieght of the tree. An empty tree hash height 0, one with only
176 /// one elemente has height 1 etc.
177 /// # Examples
178 /// ```
179 /// extern crate memrange;
180 /// extern crate theban_interval_tree;
181 ///
182 /// let mut t=theban_interval_tree::IntervalTree::<i32>::new();
183 /// assert_eq!(t.height(), 0);
184 /// t.insert(memrange::Range::new(2,2),3);
185 /// assert_eq!(t.height(), 1);
186 ///
187 /// ```
height(&self) -> usize188     pub fn height(&self) -> usize {
189         height(&self.root) as usize
190     }
191 
192 /// This function will return a read only iterator for all (key,value) pairs in the tree.
193 /// # Examples
194 /// ```
195 /// # let mut t=theban_interval_tree::IntervalTree::<i32>::new();
196 /// for (key,val) in t.iter() {
197 ///     println!("{:?} -> {}",key,val)
198 /// }
199 ///
200 /// ```
iter(&self) -> RangePairIter<D>201     pub fn iter(&self) -> RangePairIter<D>{
202         RangePairIter::new(self, 0, 0xffff_ffff_ffff_ffff)
203     }
204 
205 /// This function will return a read only iterator for all (key,value) pairs between the two
206 /// bounds.
207 /// # Examples
208 /// ```
209 /// //[...]
210 /// # let mut t=theban_interval_tree::IntervalTree::<i32>::new();
211 /// for (key,val) in t.range(9, 100) {
212 ///     println!("{:?} -> {}",key,val)
213 /// }
214 ///
215 /// ```
range(&self, min: u64, max: u64) -> RangePairIter<D>216     pub fn range(&self, min: u64, max: u64) -> RangePairIter<D>{
217         RangePairIter::new(self, min, max)
218     }
219 
220 }
221 
222 #[cfg(test)]
223 mod tests {
224     use {memrange, rand};
225     use node::is_interval_tree;
226 
random_range() -> memrange::Range227     fn random_range() -> memrange::Range {
228         let offset = rand::random::<u64>()%50;
229         let len: u64;
230         len = rand::random::<u64>()%50;
231         return memrange::Range::new(offset, offset+len)
232     }
233 
234     #[test]
test_fuzz()235     fn test_fuzz(){
236         let mut t = ::IntervalTree::<i32>::new();
237         for _ in 1..5000 {
238             let decision = rand::random::<bool>();
239             let range = random_range();
240             if  decision {
241                 t.insert(range, 1337);
242                 assert!(t.contains(range));
243                 assert!(is_interval_tree(&t.root));
244             } else {
245                 t.delete(range);
246                 assert!(!t.contains(range));
247                 assert!(is_interval_tree(&t.root));
248             };
249         };
250         return;
251     }
252 }
253