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