1 // Copyright 2017-2018 By tickdream125@hotmail.com. 2 // 3 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or 4 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license 5 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your 6 // option. This file may not be copied, modified, or distributed 7 // except according to those terms. 8 9 // This file brings from https://github.com/tickbh/rbtree-rs/blob/master/src/lib.rs 10 // Thanks to the author tickbh 11 12 #![allow(dead_code)] 13 14 use core::cmp::Ord; 15 use core::cmp::Ordering; 16 use core::fmt::{self, Debug}; 17 use core::iter::{FromIterator, IntoIterator}; 18 use core::marker; 19 use core::mem; 20 use core::mem::swap; 21 use core::ops::Index; 22 use core::ptr; 23 24 use alloc::boxed::Box; 25 use log::debug; 26 27 #[derive(Debug, Copy, Clone, PartialEq, Eq)] 28 enum Color { 29 Red, 30 Black, 31 } 32 33 /*****************RBTreeNode***************************/ 34 struct RBTreeNode<K: Ord + Debug, V: Debug> { 35 color: Color, 36 left: NodePtr<K, V>, 37 right: NodePtr<K, V>, 38 parent: NodePtr<K, V>, 39 key: K, 40 value: V, 41 } 42 43 impl<K: Ord + Debug, V: Debug> RBTreeNode<K, V> { 44 #[inline] pair(self) -> (K, V)45 fn pair(self) -> (K, V) { 46 (self.key, self.value) 47 } 48 } 49 50 impl<K, V> Debug for RBTreeNode<K, V> 51 where 52 K: Ord + Debug, 53 V: Debug, 54 { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result55 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 56 write!(f, "k:{:?} v:{:?} c:{:?}", self.key, self.value, self.color) 57 } 58 } 59 60 /*****************NodePtr***************************/ 61 #[derive(Debug)] 62 struct NodePtr<K: Ord + Debug, V: Debug>(*mut RBTreeNode<K, V>); 63 64 impl<K: Ord + Debug, V: Debug> Clone for NodePtr<K, V> { clone(&self) -> NodePtr<K, V>65 fn clone(&self) -> NodePtr<K, V> { 66 *self 67 } 68 } 69 70 impl<K: Ord + Debug, V: Debug> Copy for NodePtr<K, V> {} 71 72 impl<K: Ord + Debug, V: Debug> Ord for NodePtr<K, V> { cmp(&self, other: &NodePtr<K, V>) -> Ordering73 fn cmp(&self, other: &NodePtr<K, V>) -> Ordering { 74 unsafe { (*self.0).key.cmp(&(*other.0).key) } 75 } 76 } 77 78 impl<K: Ord + Debug, V: Debug> PartialOrd for NodePtr<K, V> { partial_cmp(&self, other: &NodePtr<K, V>) -> Option<Ordering>79 fn partial_cmp(&self, other: &NodePtr<K, V>) -> Option<Ordering> { 80 Some(self.cmp(other)) 81 } 82 } 83 84 impl<K: Ord + Debug, V: Debug> PartialEq for NodePtr<K, V> { eq(&self, other: &NodePtr<K, V>) -> bool85 fn eq(&self, other: &NodePtr<K, V>) -> bool { 86 self.0 == other.0 87 } 88 } 89 90 impl<K: Ord + Debug, V: Debug> Eq for NodePtr<K, V> {} 91 92 impl<K: Ord + Debug, V: Debug> NodePtr<K, V> { new(k: K, v: V) -> NodePtr<K, V>93 fn new(k: K, v: V) -> NodePtr<K, V> { 94 let node = RBTreeNode { 95 color: Color::Black, 96 left: NodePtr::null(), 97 right: NodePtr::null(), 98 parent: NodePtr::null(), 99 key: k, 100 value: v, 101 }; 102 NodePtr(Box::into_raw(Box::new(node))) 103 } 104 105 #[inline] set_color(&mut self, color: Color)106 fn set_color(&mut self, color: Color) { 107 if self.is_null() { 108 return; 109 } 110 unsafe { 111 (*self.0).color = color; 112 } 113 } 114 115 #[inline] set_red_color(&mut self)116 fn set_red_color(&mut self) { 117 self.set_color(Color::Red); 118 } 119 120 #[inline] set_black_color(&mut self)121 fn set_black_color(&mut self) { 122 self.set_color(Color::Black); 123 } 124 125 #[inline] get_color(&self) -> Color126 fn get_color(&self) -> Color { 127 if self.is_null() { 128 return Color::Black; 129 } 130 unsafe { (*self.0).color } 131 } 132 133 #[inline] is_red_color(&self) -> bool134 fn is_red_color(&self) -> bool { 135 if self.is_null() { 136 return false; 137 } 138 unsafe { (*self.0).color == Color::Red } 139 } 140 141 #[inline] is_black_color(&self) -> bool142 fn is_black_color(&self) -> bool { 143 if self.is_null() { 144 return true; 145 } 146 unsafe { (*self.0).color == Color::Black } 147 } 148 149 #[inline] is_left_child(&self) -> bool150 fn is_left_child(&self) -> bool { 151 self.parent().left() == *self 152 } 153 154 #[inline] is_right_child(&self) -> bool155 fn is_right_child(&self) -> bool { 156 self.parent().right() == *self 157 } 158 159 #[inline] min_node(self) -> NodePtr<K, V>160 fn min_node(self) -> NodePtr<K, V> { 161 let mut temp = self; 162 while !temp.left().is_null() { 163 temp = temp.left(); 164 } 165 return temp; 166 } 167 168 #[inline] max_node(self) -> NodePtr<K, V>169 fn max_node(self) -> NodePtr<K, V> { 170 let mut temp = self; 171 while !temp.right().is_null() { 172 temp = temp.right(); 173 } 174 return temp; 175 } 176 177 #[inline] next(self) -> NodePtr<K, V>178 fn next(self) -> NodePtr<K, V> { 179 if !self.right().is_null() { 180 self.right().min_node() 181 } else { 182 let mut temp = self; 183 loop { 184 if temp.parent().is_null() { 185 return NodePtr::null(); 186 } 187 if temp.is_left_child() { 188 return temp.parent(); 189 } 190 temp = temp.parent(); 191 } 192 } 193 } 194 195 #[inline] prev(self) -> NodePtr<K, V>196 fn prev(self) -> NodePtr<K, V> { 197 if !self.left().is_null() { 198 self.left().max_node() 199 } else { 200 let mut temp = self; 201 loop { 202 if temp.parent().is_null() { 203 return NodePtr::null(); 204 } 205 if temp.is_right_child() { 206 return temp.parent(); 207 } 208 temp = temp.parent(); 209 } 210 } 211 } 212 213 #[inline] set_parent(&mut self, parent: NodePtr<K, V>)214 fn set_parent(&mut self, parent: NodePtr<K, V>) { 215 if self.is_null() { 216 return; 217 } 218 unsafe { (*self.0).parent = parent } 219 } 220 221 #[inline] set_left(&mut self, left: NodePtr<K, V>)222 fn set_left(&mut self, left: NodePtr<K, V>) { 223 if self.is_null() { 224 return; 225 } 226 unsafe { (*self.0).left = left } 227 } 228 229 #[inline] set_right(&mut self, right: NodePtr<K, V>)230 fn set_right(&mut self, right: NodePtr<K, V>) { 231 if self.is_null() { 232 return; 233 } 234 unsafe { (*self.0).right = right } 235 } 236 237 #[inline] parent(&self) -> NodePtr<K, V>238 fn parent(&self) -> NodePtr<K, V> { 239 if self.is_null() { 240 return NodePtr::null(); 241 } 242 unsafe { (*self.0).parent } 243 } 244 245 #[inline] left(&self) -> NodePtr<K, V>246 fn left(&self) -> NodePtr<K, V> { 247 if self.is_null() { 248 return NodePtr::null(); 249 } 250 unsafe { (*self.0).left } 251 } 252 253 #[inline] right(&self) -> NodePtr<K, V>254 fn right(&self) -> NodePtr<K, V> { 255 if self.is_null() { 256 return NodePtr::null(); 257 } 258 unsafe { (*self.0).right } 259 } 260 261 #[inline] null() -> NodePtr<K, V>262 fn null() -> NodePtr<K, V> { 263 NodePtr(ptr::null_mut()) 264 } 265 266 #[inline] is_null(&self) -> bool267 fn is_null(&self) -> bool { 268 self.0.is_null() 269 } 270 } 271 272 impl<K: Ord + Clone + Debug, V: Clone + Debug> NodePtr<K, V> { deep_clone(&self) -> NodePtr<K, V>273 unsafe fn deep_clone(&self) -> NodePtr<K, V> { 274 let mut node = NodePtr::new((*self.0).key.clone(), (*self.0).value.clone()); 275 if !self.left().is_null() { 276 node.set_left(self.left().deep_clone()); 277 node.left().set_parent(node); 278 } 279 if !self.right().is_null() { 280 node.set_right(self.right().deep_clone()); 281 node.right().set_parent(node); 282 } 283 node 284 } 285 } 286 287 /// A red black tree implemented with Rust 288 /// It is required that the keys implement the [`Ord`] traits. 289 290 /// # Examples 291 /// ```rust 292 /// use rbtree::RBTree; 293 /// // type inference lets us omit an explicit type signature (which 294 /// // would be `RBTree<&str, &str>` in this example). 295 /// let mut book_reviews = RBTree::new(); 296 /// 297 /// // review some books. 298 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book."); 299 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece."); 300 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable."); 301 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot."); 302 /// 303 /// // check for a specific one. 304 /// if !book_reviews.contains_key(&"Les Misérables") { 305 /// debug!( 306 /// "We've got {} reviews, but Les Misérables ain't one.", 307 /// book_reviews.len() 308 /// ); 309 /// } 310 /// 311 /// // oops, this review has a lot of spelling mistakes, let's delete it. 312 /// book_reviews.remove(&"The Adventures of Sherlock Holmes"); 313 /// 314 /// // look up the values associated with some keys. 315 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; 316 /// for book in &to_find { 317 /// match book_reviews.get(book) { 318 /// Some(review) => debug!("{}: {}", book, review), 319 /// None => debug!("{} is unreviewed.", book), 320 /// } 321 /// } 322 /// 323 /// // iterate over everything. 324 /// for (book, review) in book_reviews.iter() { 325 /// debug!("{}: \"{}\"", book, review); 326 /// } 327 /// 328 /// book_reviews.print_tree(); 329 /// ``` 330 /// 331 /// // A `RBTree` with fixed list of elements can be initialized from an array: 332 /// ``` 333 /// use rbtree::RBTree; 334 /// let timber_resources: RBTree<&str, i32> = 335 /// [("Norway", 100), 336 /// ("Denmark", 50), 337 /// ("Iceland", 10)] 338 /// .iter().cloned().collect(); 339 /// // use the values stored in rbtree 340 /// ``` 341 pub struct RBTree<K: Ord + Debug, V: Debug> { 342 root: NodePtr<K, V>, 343 len: usize, 344 } 345 346 unsafe impl<K: Ord + Debug, V: Debug> Send for RBTree<K, V> {} 347 unsafe impl<K: Ord + Debug, V: Debug> Sync for RBTree<K, V> {} 348 349 // Drop all owned pointers if the tree is dropped 350 impl<K: Ord + Debug, V: Debug> Drop for RBTree<K, V> { 351 #[inline] drop(&mut self)352 fn drop(&mut self) { 353 self.clear(); 354 } 355 } 356 357 /// If key and value are both impl Clone, we can call clone to get a copy. 358 impl<K: Ord + Clone + Debug, V: Clone + Debug> Clone for RBTree<K, V> { clone(&self) -> RBTree<K, V>359 fn clone(&self) -> RBTree<K, V> { 360 unsafe { 361 let mut new = RBTree::new(); 362 new.root = self.root.deep_clone(); 363 new.len = self.len; 364 new 365 } 366 } 367 } 368 369 impl<K, V> Debug for RBTree<K, V> 370 where 371 K: Ord + Debug, 372 V: Debug, 373 { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result374 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 375 f.debug_map().entries(self.iter()).finish() 376 } 377 } 378 379 /// This is a method to help us to get inner struct. 380 impl<K: Ord + Debug, V: Debug> RBTree<K, V> { 381 #[allow(clippy::only_used_in_recursion)] tree_print(&self, node: NodePtr<K, V>, direction: i32)382 fn tree_print(&self, node: NodePtr<K, V>, direction: i32) { 383 if node.is_null() { 384 return; 385 } 386 if direction == 0 { 387 unsafe { 388 debug!("'{:?}' is root node", (*node.0)); 389 } 390 } else { 391 let direct = if direction == -1 { "left" } else { "right" }; 392 unsafe { 393 debug!( 394 "{:?} is {:?}'s {:?} child ", 395 (*node.0), 396 *node.parent().0, 397 direct 398 ); 399 } 400 } 401 self.tree_print(node.left(), -1); 402 self.tree_print(node.right(), 1); 403 } 404 print_tree(&self)405 pub fn print_tree(&self) { 406 if self.root.is_null() { 407 debug!("This is a empty tree"); 408 return; 409 } 410 debug!("This tree size = {:?}, begin:-------------", self.len()); 411 self.tree_print(self.root, 0); 412 debug!("end--------------------------"); 413 } 414 } 415 416 /// all key be same, but it has multi key, if has multi key, it perhaps no correct 417 impl<K, V> PartialEq for RBTree<K, V> 418 where 419 K: Eq + Ord + Debug, 420 V: PartialEq + Debug, 421 { eq(&self, other: &RBTree<K, V>) -> bool422 fn eq(&self, other: &RBTree<K, V>) -> bool { 423 if self.len() != other.len() { 424 return false; 425 } 426 427 self.iter() 428 .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) 429 } 430 } 431 432 impl<K: Eq + Ord + Debug, V: Eq + Debug> Eq for RBTree<K, V> {} 433 434 impl<'a, K: Ord + Debug, V: Debug> Index<&'a K> for RBTree<K, V> { 435 type Output = V; 436 437 #[inline] index(&self, index: &K) -> &V438 fn index(&self, index: &K) -> &V { 439 self.get(index).expect("no entry found for key") 440 } 441 } 442 443 impl<K: Ord + Debug, V: Debug> FromIterator<(K, V)> for RBTree<K, V> { from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> RBTree<K, V>444 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> RBTree<K, V> { 445 let mut tree = RBTree::new(); 446 tree.extend(iter); 447 tree 448 } 449 } 450 451 /// RBTree into iter 452 impl<K: Ord + Debug, V: Debug> Extend<(K, V)> for RBTree<K, V> { extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)453 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { 454 let iter = iter.into_iter(); 455 for (k, v) in iter { 456 self.insert(k, v); 457 } 458 } 459 } 460 461 /// provide the rbtree all keys 462 /// # Examples 463 /// ``` 464 /// use rbtree::RBTree; 465 /// let mut m = RBTree::new(); 466 /// for i in 1..6 { 467 /// m.insert(i, i); 468 /// } 469 /// let vec = vec![1, 2, 3, 4, 5]; 470 /// let key_vec: Vec<_> = m.keys().cloned().collect(); 471 /// assert_eq!(vec, key_vec); 472 /// ``` 473 pub struct Keys<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 474 inner: Iter<'a, K, V>, 475 } 476 477 impl<'a, K: Ord + Debug, V: Debug> Clone for Keys<'a, K, V> { clone(&self) -> Keys<'a, K, V>478 fn clone(&self) -> Keys<'a, K, V> { 479 Keys { 480 inner: self.inner.clone(), 481 } 482 } 483 } 484 485 impl<'a, K: Ord + Debug, V: Debug> fmt::Debug for Keys<'a, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result486 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 487 f.debug_list().entries(self.clone()).finish() 488 } 489 } 490 491 impl<'a, K: Ord + Debug, V: Debug> Iterator for Keys<'a, K, V> { 492 type Item = &'a K; 493 494 #[inline] next(&mut self) -> Option<&'a K>495 fn next(&mut self) -> Option<&'a K> { 496 self.inner.next().map(|(k, _)| k) 497 } 498 499 #[inline] size_hint(&self) -> (usize, Option<usize>)500 fn size_hint(&self) -> (usize, Option<usize>) { 501 self.inner.size_hint() 502 } 503 } 504 505 /// provide the rbtree all values order by key 506 /// # Examples 507 /// ``` 508 /// use rbtree::RBTree; 509 /// let mut m = RBTree::new(); 510 /// m.insert(2, 5); 511 /// m.insert(1, 6); 512 /// m.insert(3, 8); 513 /// m.insert(4, 9); 514 /// let vec = vec![6, 5, 8, 9]; 515 /// let key_vec: Vec<_> = m.values().cloned().collect(); 516 /// assert_eq!(vec, key_vec); 517 /// ``` 518 pub struct Values<'a, K: Ord + Debug, V: Debug> { 519 inner: Iter<'a, K, V>, 520 } 521 522 impl<'a, K: Ord + Debug, V: Debug> Clone for Values<'a, K, V> { clone(&self) -> Values<'a, K, V>523 fn clone(&self) -> Values<'a, K, V> { 524 Values { 525 inner: self.inner.clone(), 526 } 527 } 528 } 529 530 impl<'a, K: Ord + Debug, V: Debug> fmt::Debug for Values<'a, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result531 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 532 f.debug_list().entries(self.clone()).finish() 533 } 534 } 535 536 impl<'a, K: Ord + Debug, V: Debug> Iterator for Values<'a, K, V> { 537 type Item = &'a V; 538 539 #[inline] next(&mut self) -> Option<&'a V>540 fn next(&mut self) -> Option<&'a V> { 541 self.inner.next().map(|(_, v)| v) 542 } 543 544 #[inline] size_hint(&self) -> (usize, Option<usize>)545 fn size_hint(&self) -> (usize, Option<usize>) { 546 self.inner.size_hint() 547 } 548 } 549 550 /// provide the rbtree all values and it can be modify 551 /// # Examples 552 /// ``` 553 /// use rbtree::RBTree; 554 /// let mut m = RBTree::new(); 555 /// for i in 0..32 { 556 /// m.insert(i, i); 557 /// } 558 /// assert_eq!(m.len(), 32); 559 /// for v in m.values_mut() { 560 /// *v *= 2; 561 /// } 562 /// for i in 0..32 { 563 /// assert_eq!(m.get(&i).unwrap(), &(i * 2)); 564 /// } 565 /// ``` 566 pub struct ValuesMut<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 567 inner: IterMut<'a, K, V>, 568 } 569 570 impl<'a, K: Ord + Debug, V: Debug> Clone for ValuesMut<'a, K, V> { clone(&self) -> ValuesMut<'a, K, V>571 fn clone(&self) -> ValuesMut<'a, K, V> { 572 ValuesMut { 573 inner: self.inner.clone(), 574 } 575 } 576 } 577 578 impl<'a, K: Ord + Debug, V: Debug> fmt::Debug for ValuesMut<'a, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result579 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 580 f.debug_list().entries(self.clone()).finish() 581 } 582 } 583 584 impl<'a, K: Ord + Debug, V: Debug> Iterator for ValuesMut<'a, K, V> { 585 type Item = &'a mut V; 586 587 #[inline] next(&mut self) -> Option<&'a mut V>588 fn next(&mut self) -> Option<&'a mut V> { 589 self.inner.next().map(|(_, v)| v) 590 } 591 592 #[inline] size_hint(&self) -> (usize, Option<usize>)593 fn size_hint(&self) -> (usize, Option<usize>) { 594 self.inner.size_hint() 595 } 596 } 597 598 /// Convert RBTree to iter, move out the tree. 599 pub struct IntoIter<K: Ord + Debug, V: Debug> { 600 head: NodePtr<K, V>, 601 tail: NodePtr<K, V>, 602 len: usize, 603 } 604 605 // Drop all owned pointers if the collection is dropped 606 impl<K: Ord + Debug, V: Debug> Drop for IntoIter<K, V> { 607 #[inline] drop(&mut self)608 fn drop(&mut self) { 609 for (_, _) in self {} 610 } 611 } 612 613 impl<K: Ord + Debug, V: Debug> Iterator for IntoIter<K, V> { 614 type Item = (K, V); 615 next(&mut self) -> Option<(K, V)>616 fn next(&mut self) -> Option<(K, V)> { 617 if self.len == 0 { 618 return None; 619 } 620 621 if self.head.is_null() { 622 return None; 623 } 624 625 let next = self.head.next(); 626 let (k, v) = unsafe { 627 ( 628 core::ptr::read(&(*self.head.0).key), 629 core::ptr::read(&(*self.head.0).value), 630 ) 631 }; 632 self.head = next; 633 self.len -= 1; 634 Some((k, v)) 635 } 636 size_hint(&self) -> (usize, Option<usize>)637 fn size_hint(&self) -> (usize, Option<usize>) { 638 (self.len, Some(self.len)) 639 } 640 } 641 642 impl<K: Ord + Debug, V: Debug> DoubleEndedIterator for IntoIter<K, V> { 643 #[inline] next_back(&mut self) -> Option<(K, V)>644 fn next_back(&mut self) -> Option<(K, V)> { 645 if self.len == 0 { 646 return None; 647 } 648 649 if self.tail.is_null() { 650 return None; 651 } 652 653 let prev = self.tail.prev(); 654 let obj = unsafe { Box::from_raw(self.tail.0) }; 655 let (k, v) = obj.pair(); 656 self.tail = prev; 657 self.len -= 1; 658 Some((k, v)) 659 } 660 } 661 662 /// provide iter ref for RBTree 663 /// # Examples 664 /// ``` 665 /// use rbtree::RBTree; 666 /// let mut m = RBTree::new(); 667 /// for i in 0..32 { 668 /// m.insert(i, i * 2); 669 /// } 670 /// assert_eq!(m.len(), 32); 671 /// let mut observed: u32 = 0; 672 /// for (k, v) in m.iter() { 673 /// assert_eq!(*v, *k * 2); 674 /// observed |= 1 << *k; 675 /// } 676 /// assert_eq!(observed, 0xFFFF_FFFF); 677 /// ``` 678 pub struct Iter<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 679 head: NodePtr<K, V>, 680 tail: NodePtr<K, V>, 681 len: usize, 682 _marker: marker::PhantomData<&'a ()>, 683 } 684 685 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Clone for Iter<'a, K, V> { clone(&self) -> Iter<'a, K, V>686 fn clone(&self) -> Iter<'a, K, V> { 687 Iter { 688 head: self.head, 689 tail: self.tail, 690 len: self.len, 691 _marker: self._marker, 692 } 693 } 694 } 695 696 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Iterator for Iter<'a, K, V> { 697 type Item = (&'a K, &'a V); 698 next(&mut self) -> Option<(&'a K, &'a V)>699 fn next(&mut self) -> Option<(&'a K, &'a V)> { 700 if self.len == 0 { 701 return None; 702 } 703 704 if self.head.is_null() { 705 return None; 706 } 707 708 let (k, v) = unsafe { (&(*self.head.0).key, &(*self.head.0).value) }; 709 self.head = self.head.next(); 710 self.len -= 1; 711 Some((k, v)) 712 } 713 size_hint(&self) -> (usize, Option<usize>)714 fn size_hint(&self) -> (usize, Option<usize>) { 715 (self.len, Some(self.len)) 716 } 717 } 718 719 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> DoubleEndedIterator for Iter<'a, K, V> { 720 #[inline] next_back(&mut self) -> Option<(&'a K, &'a V)>721 fn next_back(&mut self) -> Option<(&'a K, &'a V)> { 722 // debug!("len = {:?}", self.len); 723 if self.len == 0 { 724 return None; 725 } 726 727 let (k, v) = unsafe { (&(*self.tail.0).key, &(*self.tail.0).value) }; 728 self.tail = self.tail.prev(); 729 self.len -= 1; 730 Some((k, v)) 731 } 732 } 733 734 /// provide iter mut ref for RBTree 735 /// # Examples 736 /// ``` 737 /// use rbtree::RBTree; 738 /// let mut m = RBTree::new(); 739 /// for i in 0..32 { 740 /// m.insert(i, i); 741 /// } 742 /// assert_eq!(m.len(), 32); 743 /// for (_, v) in m.iter_mut() { 744 /// *v *= 2; 745 /// } 746 /// for i in 0..32 { 747 /// assert_eq!(m.get(&i).unwrap(), &(i * 2)); 748 /// } 749 /// ``` 750 pub struct IterMut<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 751 head: NodePtr<K, V>, 752 tail: NodePtr<K, V>, 753 len: usize, 754 _marker: marker::PhantomData<&'a ()>, 755 } 756 757 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Clone for IterMut<'a, K, V> { clone(&self) -> IterMut<'a, K, V>758 fn clone(&self) -> IterMut<'a, K, V> { 759 IterMut { 760 head: self.head, 761 tail: self.tail, 762 len: self.len, 763 _marker: self._marker, 764 } 765 } 766 } 767 768 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Iterator for IterMut<'a, K, V> { 769 type Item = (&'a K, &'a mut V); 770 next(&mut self) -> Option<(&'a K, &'a mut V)>771 fn next(&mut self) -> Option<(&'a K, &'a mut V)> { 772 if self.len == 0 { 773 return None; 774 } 775 776 if self.head.is_null() { 777 return None; 778 } 779 780 let (k, v) = unsafe { (&(*self.head.0).key, &mut (*self.head.0).value) }; 781 self.head = self.head.next(); 782 self.len -= 1; 783 Some((k, v)) 784 } 785 size_hint(&self) -> (usize, Option<usize>)786 fn size_hint(&self) -> (usize, Option<usize>) { 787 (self.len, Some(self.len)) 788 } 789 } 790 791 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> DoubleEndedIterator for IterMut<'a, K, V> { 792 #[inline] next_back(&mut self) -> Option<(&'a K, &'a mut V)>793 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { 794 if self.len == 0 { 795 return None; 796 } 797 798 if self.tail == self.head { 799 return None; 800 } 801 802 let (k, v) = unsafe { (&(*self.tail.0).key, &mut (*self.tail.0).value) }; 803 self.tail = self.tail.prev(); 804 self.len -= 1; 805 Some((k, v)) 806 } 807 } 808 809 impl<K: Ord + Debug, V: Debug> IntoIterator for RBTree<K, V> { 810 type Item = (K, V); 811 type IntoIter = IntoIter<K, V>; 812 813 #[inline] into_iter(mut self) -> IntoIter<K, V>814 fn into_iter(mut self) -> IntoIter<K, V> { 815 let iter = if self.root.is_null() { 816 IntoIter { 817 head: NodePtr::null(), 818 tail: NodePtr::null(), 819 len: self.len, 820 } 821 } else { 822 IntoIter { 823 head: self.first_child(), 824 tail: self.last_child(), 825 len: self.len, 826 } 827 }; 828 self.fast_clear(); 829 iter 830 } 831 } 832 833 impl<K: Ord + Debug, V: Debug> RBTree<K, V> { 834 /// Creates an empty `RBTree`. new() -> RBTree<K, V>835 pub fn new() -> RBTree<K, V> { 836 RBTree { 837 root: NodePtr::null(), 838 len: 0, 839 } 840 } 841 842 /// Returns the len of `RBTree`. 843 #[inline] len(&self) -> usize844 pub fn len(&self) -> usize { 845 self.len 846 } 847 848 /// Returns `true` if the `RBTree` is empty. 849 #[inline] is_empty(&self) -> bool850 pub fn is_empty(&self) -> bool { 851 self.root.is_null() 852 } 853 854 /* 855 * 对红黑树的节点(x)进行左旋转 856 * 857 * 左旋示意图(对节点x进行左旋)： 858 * px px 859 * / / 860 * x y 861 * / \ --(左旋)--> / \ # 862 * lx y x ry 863 * / \ / \ 864 * ly ry lx ly 865 * 866 * 867 */ 868 #[inline] left_rotate(&mut self, mut node: NodePtr<K, V>)869 unsafe fn left_rotate(&mut self, mut node: NodePtr<K, V>) { 870 let mut temp = node.right(); 871 node.set_right(temp.left()); 872 873 if !temp.left().is_null() { 874 temp.left().set_parent(node); 875 } 876 877 temp.set_parent(node.parent()); 878 if node == self.root { 879 self.root = temp; 880 } else if node == node.parent().left() { 881 node.parent().set_left(temp); 882 } else { 883 node.parent().set_right(temp); 884 } 885 886 temp.set_left(node); 887 node.set_parent(temp); 888 } 889 890 /* 891 * 对红黑树的节点(y)进行右旋转 892 * 893 * 右旋示意图(对节点y进行左旋)： 894 * py py 895 * / / 896 * y x 897 * / \ --(右旋)--> / \ # 898 * x ry lx y 899 * / \ / \ # 900 * lx rx rx ry 901 * 902 */ 903 #[inline] right_rotate(&mut self, mut node: NodePtr<K, V>)904 unsafe fn right_rotate(&mut self, mut node: NodePtr<K, V>) { 905 let mut temp = node.left(); 906 node.set_left(temp.right()); 907 908 if !temp.right().is_null() { 909 temp.right().set_parent(node); 910 } 911 912 temp.set_parent(node.parent()); 913 if node == self.root { 914 self.root = temp; 915 } else if node == node.parent().right() { 916 node.parent().set_right(temp); 917 } else { 918 node.parent().set_left(temp); 919 } 920 921 temp.set_right(node); 922 node.set_parent(temp); 923 } 924 925 /// replace value if key exist, if not exist insert it. 926 /// # Examples 927 /// ``` 928 /// use rbtree::RBTree; 929 /// let mut m = RBTree::new(); 930 /// assert_eq!(m.len(), 0); 931 /// m.insert(2, 4); 932 /// assert_eq!(m.len(), 1); 933 /// assert_eq!(m.replace_or_insert(2, 6).unwrap(), 4); 934 /// assert_eq!(m.len(), 1); 935 /// assert_eq!(*m.get(&2).unwrap(), 6); 936 /// ``` 937 #[inline] replace_or_insert(&mut self, k: K, mut v: V) -> Option<V>938 pub fn replace_or_insert(&mut self, k: K, mut v: V) -> Option<V> { 939 let node = self.find_node(&k); 940 if node.is_null() { 941 self.insert(k, v); 942 return None; 943 } 944 945 unsafe { 946 mem::swap(&mut v, &mut (*node.0).value); 947 } 948 949 Some(v) 950 } 951 952 #[inline] insert_fixup(&mut self, mut node: NodePtr<K, V>)953 unsafe fn insert_fixup(&mut self, mut node: NodePtr<K, V>) { 954 let mut parent; 955 let mut gparent; 956 957 while node.parent().is_red_color() { 958 parent = node.parent(); 959 gparent = parent.parent(); 960 //若“父节点”是“祖父节点的左孩子” 961 if parent == gparent.left() { 962 // Case 1条件：叔叔节点是红色 963 let mut uncle = gparent.right(); 964 if !uncle.is_null() && uncle.is_red_color() { 965 uncle.set_black_color(); 966 parent.set_black_color(); 967 gparent.set_red_color(); 968 node = gparent; 969 continue; 970 } 971 972 // Case 2条件：叔叔是黑色，且当前节点是右孩子 973 if parent.right() == node { 974 self.left_rotate(parent); 975 swap(&mut parent, &mut node); 976 } 977 978 // Case 3条件：叔叔是黑色，且当前节点是左孩子。 979 parent.set_black_color(); 980 gparent.set_red_color(); 981 self.right_rotate(gparent); 982 } else { 983 // Case 1条件：叔叔节点是红色 984 let mut uncle = gparent.left(); 985 if !uncle.is_null() && uncle.is_red_color() { 986 uncle.set_black_color(); 987 parent.set_black_color(); 988 gparent.set_red_color(); 989 node = gparent; 990 continue; 991 } 992 993 // Case 2条件：叔叔是黑色，且当前节点是右孩子 994 if parent.left() == node { 995 self.right_rotate(parent); 996 swap(&mut parent, &mut node); 997 } 998 999 // Case 3条件：叔叔是黑色，且当前节点是左孩子。 1000 parent.set_black_color(); 1001 gparent.set_red_color(); 1002 self.left_rotate(gparent); 1003 } 1004 } 1005 self.root.set_black_color(); 1006 } 1007 1008 #[inline] insert(&mut self, k: K, v: V)1009 pub fn insert(&mut self, k: K, v: V) { 1010 self.len += 1; 1011 let mut node = NodePtr::new(k, v); 1012 let mut y = NodePtr::null(); 1013 let mut x = self.root; 1014 1015 while !x.is_null() { 1016 y = x; 1017 match node.cmp(&x) { 1018 Ordering::Less => { 1019 x = x.left(); 1020 } 1021 _ => { 1022 x = x.right(); 1023 } 1024 }; 1025 } 1026 node.set_parent(y); 1027 1028 if y.is_null() { 1029 self.root = node; 1030 } else { 1031 match node.cmp(&y) { 1032 Ordering::Less => { 1033 y.set_left(node); 1034 } 1035 _ => { 1036 y.set_right(node); 1037 } 1038 }; 1039 } 1040 1041 node.set_red_color(); 1042 unsafe { 1043 self.insert_fixup(node); 1044 } 1045 } 1046 1047 #[inline] find_node(&self, k: &K) -> NodePtr<K, V>1048 fn find_node(&self, k: &K) -> NodePtr<K, V> { 1049 if self.root.is_null() { 1050 return NodePtr::null(); 1051 } 1052 let mut temp = &self.root; 1053 unsafe { 1054 loop { 1055 let next = match k.cmp(&(*temp.0).key) { 1056 Ordering::Less => &mut (*temp.0).left, 1057 Ordering::Greater => &mut (*temp.0).right, 1058 Ordering::Equal => return *temp, 1059 }; 1060 if next.is_null() { 1061 break; 1062 } 1063 temp = next; 1064 } 1065 } 1066 NodePtr::null() 1067 } 1068 1069 #[inline] first_child(&self) -> NodePtr<K, V>1070 fn first_child(&self) -> NodePtr<K, V> { 1071 if self.root.is_null() { 1072 NodePtr::null() 1073 } else { 1074 let mut temp = self.root; 1075 while !temp.left().is_null() { 1076 temp = temp.left(); 1077 } 1078 return temp; 1079 } 1080 } 1081 1082 #[inline] last_child(&self) -> NodePtr<K, V>1083 fn last_child(&self) -> NodePtr<K, V> { 1084 if self.root.is_null() { 1085 NodePtr::null() 1086 } else { 1087 let mut temp = self.root; 1088 while !temp.right().is_null() { 1089 temp = temp.right(); 1090 } 1091 return temp; 1092 } 1093 } 1094 1095 #[inline] get_first(&self) -> Option<(&K, &V)>1096 pub fn get_first(&self) -> Option<(&K, &V)> { 1097 let first = self.first_child(); 1098 if first.is_null() { 1099 return None; 1100 } 1101 unsafe { Some((&(*first.0).key, &(*first.0).value)) } 1102 } 1103 1104 #[inline] get_last(&self) -> Option<(&K, &V)>1105 pub fn get_last(&self) -> Option<(&K, &V)> { 1106 let last = self.last_child(); 1107 if last.is_null() { 1108 return None; 1109 } 1110 unsafe { Some((&(*last.0).key, &(*last.0).value)) } 1111 } 1112 1113 #[inline] pop_first(&mut self) -> Option<(K, V)>1114 pub fn pop_first(&mut self) -> Option<(K, V)> { 1115 let first = self.first_child(); 1116 if first.is_null() { 1117 return None; 1118 } 1119 unsafe { Some(self.delete(first)) } 1120 } 1121 1122 #[inline] pop_last(&mut self) -> Option<(K, V)>1123 pub fn pop_last(&mut self) -> Option<(K, V)> { 1124 let last = self.last_child(); 1125 if last.is_null() { 1126 return None; 1127 } 1128 unsafe { Some(self.delete(last)) } 1129 } 1130 1131 #[inline] get_first_mut(&mut self) -> Option<(&K, &mut V)>1132 pub fn get_first_mut(&mut self) -> Option<(&K, &mut V)> { 1133 let first = self.first_child(); 1134 if first.is_null() { 1135 return None; 1136 } 1137 unsafe { Some((&(*first.0).key, &mut (*first.0).value)) } 1138 } 1139 1140 #[inline] get_last_mut(&mut self) -> Option<(&K, &mut V)>1141 pub fn get_last_mut(&mut self) -> Option<(&K, &mut V)> { 1142 let last = self.last_child(); 1143 if last.is_null() { 1144 return None; 1145 } 1146 unsafe { Some((&(*last.0).key, &mut (*last.0).value)) } 1147 } 1148 1149 #[inline] get(&self, k: &K) -> Option<&V>1150 pub fn get(&self, k: &K) -> Option<&V> { 1151 let node = self.find_node(k); 1152 if node.is_null() { 1153 return None; 1154 } 1155 1156 unsafe { Some(&(*node.0).value) } 1157 } 1158 1159 #[inline] get_mut(&mut self, k: &K) -> Option<&mut V>1160 pub fn get_mut(&mut self, k: &K) -> Option<&mut V> { 1161 let node = self.find_node(k); 1162 if node.is_null() { 1163 return None; 1164 } 1165 1166 unsafe { Some(&mut (*node.0).value) } 1167 } 1168 1169 #[inline] contains_key(&self, k: &K) -> bool1170 pub fn contains_key(&self, k: &K) -> bool { 1171 let node = self.find_node(k); 1172 if node.is_null() { 1173 return false; 1174 } 1175 true 1176 } 1177 1178 #[allow(clippy::only_used_in_recursion)] 1179 #[inline] clear_recurse(&mut self, current: NodePtr<K, V>)1180 fn clear_recurse(&mut self, current: NodePtr<K, V>) { 1181 if !current.is_null() { 1182 unsafe { 1183 self.clear_recurse(current.left()); 1184 self.clear_recurse(current.right()); 1185 drop(Box::from_raw(current.0)); 1186 } 1187 } 1188 } 1189 1190 /// clear all red back tree elements. 1191 /// # Examples 1192 /// ``` 1193 /// use rbtree::RBTree; 1194 /// let mut m = RBTree::new(); 1195 /// for i in 0..6 { 1196 /// m.insert(i, i); 1197 /// } 1198 /// assert_eq!(m.len(), 6); 1199 /// m.clear(); 1200 /// assert_eq!(m.len(), 0); 1201 /// ``` 1202 #[inline] clear(&mut self)1203 pub fn clear(&mut self) { 1204 let root = self.root; 1205 self.root = NodePtr::null(); 1206 self.clear_recurse(root); 1207 self.len = 0; 1208 } 1209 1210 /// Empties the `RBTree` without freeing objects in it. 1211 #[inline] fast_clear(&mut self)1212 fn fast_clear(&mut self) { 1213 self.root = NodePtr::null(); 1214 self.len = 0; 1215 } 1216 1217 #[inline] remove(&mut self, k: &K) -> Option<V>1218 pub fn remove(&mut self, k: &K) -> Option<V> { 1219 let node = self.find_node(k); 1220 if node.is_null() { 1221 return None; 1222 } 1223 unsafe { Some(self.delete(node).1) } 1224 } 1225 1226 #[inline] delete_fixup(&mut self, mut node: NodePtr<K, V>, mut parent: NodePtr<K, V>)1227 unsafe fn delete_fixup(&mut self, mut node: NodePtr<K, V>, mut parent: NodePtr<K, V>) { 1228 let mut other; 1229 while node != self.root && node.is_black_color() { 1230 if parent.left() == node { 1231 other = parent.right(); 1232 //x的兄弟w是红色的 1233 if other.is_red_color() { 1234 other.set_black_color(); 1235 parent.set_red_color(); 1236 self.left_rotate(parent); 1237 other = parent.right(); 1238 } 1239 1240 //x的兄弟w是黑色，且w的俩个孩子也都是黑色的 1241 if other.left().is_black_color() && other.right().is_black_color() { 1242 other.set_red_color(); 1243 node = parent; 1244 parent = node.parent(); 1245 } else { 1246 //x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 1247 if other.right().is_black_color() { 1248 other.left().set_black_color(); 1249 other.set_red_color(); 1250 self.right_rotate(other); 1251 other = parent.right(); 1252 } 1253 //x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 1254 other.set_color(parent.get_color()); 1255 parent.set_black_color(); 1256 other.right().set_black_color(); 1257 self.left_rotate(parent); 1258 node = self.root; 1259 break; 1260 } 1261 } else { 1262 other = parent.left(); 1263 //x的兄弟w是红色的 1264 if other.is_red_color() { 1265 other.set_black_color(); 1266 parent.set_red_color(); 1267 self.right_rotate(parent); 1268 other = parent.left(); 1269 } 1270 1271 //x的兄弟w是黑色，且w的俩个孩子也都是黑色的 1272 if other.left().is_black_color() && other.right().is_black_color() { 1273 other.set_red_color(); 1274 node = parent; 1275 parent = node.parent(); 1276 } else { 1277 //x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 1278 if other.left().is_black_color() { 1279 other.right().set_black_color(); 1280 other.set_red_color(); 1281 self.left_rotate(other); 1282 other = parent.left(); 1283 } 1284 //x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 1285 other.set_color(parent.get_color()); 1286 parent.set_black_color(); 1287 other.left().set_black_color(); 1288 self.right_rotate(parent); 1289 node = self.root; 1290 break; 1291 } 1292 } 1293 } 1294 1295 node.set_black_color(); 1296 } 1297 1298 #[inline] delete(&mut self, node: NodePtr<K, V>) -> (K, V)1299 unsafe fn delete(&mut self, node: NodePtr<K, V>) -> (K, V) { 1300 let mut child; 1301 let mut parent; 1302 let color; 1303 1304 self.len -= 1; 1305 // 被删除节点的"左右孩子都不为空"的情况。 1306 if !node.left().is_null() && !node.right().is_null() { 1307 // 被删节点的后继节点。(称为"取代节点") 1308 // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。 1309 let mut replace = node.right().min_node(); 1310 if node == self.root { 1311 self.root = replace; 1312 } else if node.parent().left() == node { 1313 node.parent().set_left(replace); 1314 } else { 1315 node.parent().set_right(replace); 1316 } 1317 1318 // child是"取代节点"的右孩子，也是需要"调整的节点"。 1319 // "取代节点"肯定不存在左孩子！因为它是一个后继节点。 1320 child = replace.right(); 1321 parent = replace.parent(); 1322 color = replace.get_color(); 1323 if parent == node { 1324 parent = replace; 1325 } else { 1326 if !child.is_null() { 1327 child.set_parent(parent); 1328 } 1329 parent.set_left(child); 1330 replace.set_right(node.right()); 1331 node.right().set_parent(replace); 1332 } 1333 1334 replace.set_parent(node.parent()); 1335 replace.set_color(node.get_color()); 1336 replace.set_left(node.left()); 1337 node.left().set_parent(replace); 1338 1339 if color == Color::Black { 1340 self.delete_fixup(child, parent); 1341 } 1342 1343 let obj = Box::from_raw(node.0); 1344 return obj.pair(); 1345 } 1346 1347 if !node.left().is_null() { 1348 child = node.left(); 1349 } else { 1350 child = node.right(); 1351 } 1352 1353 parent = node.parent(); 1354 color = node.get_color(); 1355 if !child.is_null() { 1356 child.set_parent(parent); 1357 } 1358 1359 if self.root == node { 1360 self.root = child 1361 } else if parent.left() == node { 1362 parent.set_left(child); 1363 } else { 1364 parent.set_right(child); 1365 } 1366 1367 if color == Color::Black { 1368 self.delete_fixup(child, parent); 1369 } 1370 1371 let obj = Box::from_raw(node.0); 1372 return obj.pair(); 1373 } 1374 1375 /// Return the keys iter 1376 #[inline] keys(&self) -> Keys<K, V>1377 pub fn keys(&self) -> Keys<K, V> { 1378 Keys { inner: self.iter() } 1379 } 1380 1381 /// Return the value iter 1382 #[inline] values(&self) -> Values<K, V>1383 pub fn values(&self) -> Values<K, V> { 1384 Values { inner: self.iter() } 1385 } 1386 1387 /// Return the value iter mut 1388 #[inline] values_mut(&mut self) -> ValuesMut<K, V>1389 pub fn values_mut(&mut self) -> ValuesMut<K, V> { 1390 ValuesMut { 1391 inner: self.iter_mut(), 1392 } 1393 } 1394 1395 /// Return the key and value iter 1396 #[inline] iter(&self) -> Iter<K, V>1397 pub fn iter(&self) -> Iter<K, V> { 1398 Iter { 1399 head: self.first_child(), 1400 tail: self.last_child(), 1401 len: self.len, 1402 _marker: marker::PhantomData, 1403 } 1404 } 1405 1406 /// Return the key and mut value iter 1407 #[inline] iter_mut(&mut self) -> IterMut<K, V>1408 pub fn iter_mut(&mut self) -> IterMut<K, V> { 1409 IterMut { 1410 head: self.first_child(), 1411 tail: self.last_child(), 1412 len: self.len, 1413 _marker: marker::PhantomData, 1414 } 1415 } 1416 } 1417 1418 #[cfg(test)] 1419 mod tests { 1420 1421 #[test] test_insert()1422 fn test_insert() { 1423 use crate::libs::rbtree::RBTree; 1424 let mut m = RBTree::new(); 1425 assert_eq!(m.len(), 0); 1426 m.insert(1, 2); 1427 assert_eq!(m.len(), 1); 1428 m.insert(2, 4); 1429 assert_eq!(m.len(), 2); 1430 m.insert(2, 6); 1431 assert_eq!(m.len(), 3); 1432 assert_eq!(*m.get(&1).unwrap(), 2); 1433 assert_eq!(*m.get(&2).unwrap(), 4); 1434 assert_eq!(*m.get(&2).unwrap(), 4); 1435 } 1436 1437 #[test] test_replace()1438 fn test_replace() { 1439 use crate::libs::rbtree::RBTree; 1440 let mut m = RBTree::new(); 1441 assert_eq!(m.len(), 0); 1442 m.insert(2, 4); 1443 assert_eq!(m.len(), 1); 1444 assert_eq!(m.replace_or_insert(2, 6).unwrap(), 4); 1445 assert_eq!(m.len(), 1); 1446 assert_eq!(*m.get(&2).unwrap(), 6); 1447 } 1448 1449 #[test] test_clone()1450 fn test_clone() { 1451 use crate::libs::rbtree::RBTree; 1452 let mut m = RBTree::new(); 1453 assert_eq!(m.len(), 0); 1454 m.insert(1, 2); 1455 assert_eq!(m.len(), 1); 1456 m.insert(2, 4); 1457 assert_eq!(m.len(), 2); 1458 let m2 = m.clone(); 1459 m.clear(); 1460 assert_eq!(*m2.get(&1).unwrap(), 2); 1461 assert_eq!(*m2.get(&2).unwrap(), 4); 1462 assert_eq!(m2.len(), 2); 1463 } 1464 1465 #[test] test_empty_remove()1466 fn test_empty_remove() { 1467 use crate::libs::rbtree::RBTree; 1468 let mut m: RBTree<isize, bool> = RBTree::new(); 1469 assert_eq!(m.remove(&0), None); 1470 } 1471 1472 #[test] test_empty_iter()1473 fn test_empty_iter() { 1474 use crate::libs::rbtree::RBTree; 1475 let mut m: RBTree<isize, bool> = RBTree::new(); 1476 assert_eq!(m.iter().next(), None); 1477 assert_eq!(m.iter_mut().next(), None); 1478 assert_eq!(m.len(), 0); 1479 assert!(m.is_empty()); 1480 assert_eq!(m.into_iter().next(), None); 1481 } 1482 1483 #[test] test_lots_of_insertions()1484 fn test_lots_of_insertions() { 1485 use crate::libs::rbtree::RBTree; 1486 let mut m = RBTree::new(); 1487 1488 // Try this a few times to make sure we never screw up the hashmap's 1489 // internal state. 1490 for _ in 0..10 { 1491 assert!(m.is_empty()); 1492 1493 for i in 1..101 { 1494 m.insert(i, i); 1495 1496 for j in 1..i + 1 { 1497 let r = m.get(&j); 1498 assert_eq!(r, Some(&j)); 1499 } 1500 1501 for j in i + 1..101 { 1502 let r = m.get(&j); 1503 assert_eq!(r, None); 1504 } 1505 } 1506 1507 for i in 101..201 { 1508 assert!(!m.contains_key(&i)); 1509 } 1510 1511 // remove forwards 1512 for i in 1..101 { 1513 assert!(m.remove(&i).is_some()); 1514 1515 for j in 1..i + 1 { 1516 assert!(!m.contains_key(&j)); 1517 } 1518 1519 for j in i + 1..101 { 1520 assert!(m.contains_key(&j)); 1521 } 1522 } 1523 1524 for i in 1..101 { 1525 assert!(!m.contains_key(&i)); 1526 } 1527 1528 for i in 1..101 { 1529 m.insert(i, i); 1530 } 1531 1532 // remove backwards 1533 for i in (1..101).rev() { 1534 assert!(m.remove(&i).is_some()); 1535 1536 for j in i..101 { 1537 assert!(!m.contains_key(&j)); 1538 } 1539 1540 for j in 1..i { 1541 assert!(m.contains_key(&j)); 1542 } 1543 } 1544 } 1545 } 1546 1547 #[test] test_find_mut()1548 fn test_find_mut() { 1549 use crate::libs::rbtree::RBTree; 1550 let mut m = RBTree::new(); 1551 m.insert(1, 12); 1552 m.insert(2, 8); 1553 m.insert(5, 14); 1554 let new = 100; 1555 match m.get_mut(&5) { 1556 None => panic!(), 1557 Some(x) => *x = new, 1558 } 1559 assert_eq!(m.get(&5), Some(&new)); 1560 } 1561 1562 #[test] test_remove()1563 fn test_remove() { 1564 use crate::libs::rbtree::RBTree; 1565 let mut m = RBTree::new(); 1566 m.insert(1, 2); 1567 assert_eq!(*m.get(&1).unwrap(), 2); 1568 m.insert(5, 3); 1569 assert_eq!(*m.get(&5).unwrap(), 3); 1570 m.insert(9, 4); 1571 assert_eq!(*m.get(&1).unwrap(), 2); 1572 assert_eq!(*m.get(&5).unwrap(), 3); 1573 assert_eq!(*m.get(&9).unwrap(), 4); 1574 assert_eq!(m.remove(&1).unwrap(), 2); 1575 assert_eq!(m.remove(&5).unwrap(), 3); 1576 assert_eq!(m.remove(&9).unwrap(), 4); 1577 assert_eq!(m.len(), 0); 1578 } 1579 1580 #[test] test_is_empty()1581 fn test_is_empty() { 1582 use crate::libs::rbtree::RBTree; 1583 let mut m = RBTree::new(); 1584 m.insert(1, 2); 1585 assert!(!m.is_empty()); 1586 assert!(m.remove(&1).is_some()); 1587 assert!(m.is_empty()); 1588 } 1589 1590 #[test] test_pop()1591 fn test_pop() { 1592 use crate::libs::rbtree::RBTree; 1593 let mut m = RBTree::new(); 1594 m.insert(2, 4); 1595 m.insert(1, 2); 1596 m.insert(3, 6); 1597 assert_eq!(m.len(), 3); 1598 assert_eq!(m.pop_first(), Some((1, 2))); 1599 assert_eq!(m.len(), 2); 1600 assert_eq!(m.pop_last(), Some((3, 6))); 1601 assert_eq!(m.len(), 1); 1602 assert_eq!(m.get_first(), Some((&2, &4))); 1603 assert_eq!(m.get_last(), Some((&2, &4))); 1604 } 1605 1606 #[test] test_iterate()1607 fn test_iterate() { 1608 use crate::libs::rbtree::RBTree; 1609 let mut m = RBTree::new(); 1610 for i in 0..32 { 1611 m.insert(i, i * 2); 1612 } 1613 assert_eq!(m.len(), 32); 1614 1615 let mut observed: u32 = 0; 1616 1617 for (k, v) in m.iter() { 1618 assert_eq!(*v, *k * 2); 1619 observed |= 1 << *k; 1620 } 1621 assert_eq!(observed, 0xFFFF_FFFF); 1622 } 1623 1624 #[test] test_keys()1625 fn test_keys() { 1626 use crate::libs::rbtree::RBTree; 1627 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; 1628 let map: RBTree<_, _> = vec.into_iter().collect(); 1629 let keys: Vec<_> = map.keys().cloned().collect(); 1630 assert_eq!(keys.len(), 3); 1631 assert!(keys.contains(&1)); 1632 assert!(keys.contains(&2)); 1633 assert!(keys.contains(&3)); 1634 } 1635 1636 #[test] test_values()1637 fn test_values() { 1638 use crate::libs::rbtree::RBTree; 1639 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; 1640 let map: RBTree<_, _> = vec.into_iter().collect(); 1641 let values: Vec<_> = map.values().cloned().collect(); 1642 assert_eq!(values.len(), 3); 1643 assert!(values.contains(&'a')); 1644 assert!(values.contains(&'b')); 1645 assert!(values.contains(&'c')); 1646 } 1647 1648 #[test] test_values_mut()1649 fn test_values_mut() { 1650 use crate::libs::rbtree::RBTree; 1651 let vec = vec![(1, 1), (2, 2), (3, 3)]; 1652 let mut map: RBTree<_, _> = vec.into_iter().collect(); 1653 for value in map.values_mut() { 1654 *value = (*value) * 2 1655 } 1656 let values: Vec<_> = map.values().cloned().collect(); 1657 assert_eq!(values.len(), 3); 1658 assert!(values.contains(&2)); 1659 assert!(values.contains(&4)); 1660 assert!(values.contains(&6)); 1661 } 1662 1663 #[test] test_find()1664 fn test_find() { 1665 use crate::libs::rbtree::RBTree; 1666 let mut m = RBTree::new(); 1667 assert!(m.get(&1).is_none()); 1668 m.insert(1, 2); 1669 match m.get(&1) { 1670 None => panic!(), 1671 Some(v) => assert_eq!(*v, 2), 1672 } 1673 } 1674 1675 #[test] test_eq()1676 fn test_eq() { 1677 use crate::libs::rbtree::RBTree; 1678 let mut m1 = RBTree::new(); 1679 m1.insert(1, 2); 1680 m1.insert(2, 3); 1681 m1.insert(3, 4); 1682 1683 let mut m2 = RBTree::new(); 1684 m2.insert(1, 2); 1685 m2.insert(2, 3); 1686 1687 assert!(m1 != m2); 1688 1689 m2.insert(3, 4); 1690 1691 assert_eq!(m1, m2); 1692 } 1693 1694 #[test] test_show()1695 fn test_show() { 1696 use crate::libs::rbtree::RBTree; 1697 let mut map = RBTree::new(); 1698 let empty: RBTree<i32, i32> = RBTree::new(); 1699 1700 map.insert(1, 2); 1701 map.insert(3, 4); 1702 1703 let map_str = format!("{:?}", map); 1704 1705 assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}"); 1706 assert_eq!(format!("{:?}", empty), "{}"); 1707 } 1708 1709 #[test] test_from_iter()1710 fn test_from_iter() { 1711 use crate::libs::rbtree::RBTree; 1712 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1713 1714 let map: RBTree<_, _> = xs.iter().cloned().collect(); 1715 1716 for &(k, v) in &xs { 1717 assert_eq!(map.get(&k), Some(&v)); 1718 } 1719 } 1720 1721 #[test] test_size_hint()1722 fn test_size_hint() { 1723 use crate::libs::rbtree::RBTree; 1724 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1725 1726 let map: RBTree<_, _> = xs.iter().cloned().collect(); 1727 1728 let mut iter = map.iter(); 1729 1730 for _ in iter.by_ref().take(3) {} 1731 1732 assert_eq!(iter.size_hint(), (3, Some(3))); 1733 } 1734 1735 #[test] test_iter_len()1736 fn test_iter_len() { 1737 use crate::libs::rbtree::RBTree; 1738 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1739 1740 let map: RBTree<_, _> = xs.iter().cloned().collect(); 1741 1742 let mut iter = map.iter(); 1743 1744 for _ in iter.by_ref().take(3) {} 1745 1746 assert_eq!(iter.count(), 3); 1747 } 1748 1749 #[test] test_mut_size_hint()1750 fn test_mut_size_hint() { 1751 use crate::libs::rbtree::RBTree; 1752 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1753 1754 let mut map: RBTree<_, _> = xs.iter().cloned().collect(); 1755 1756 let mut iter = map.iter_mut(); 1757 1758 for _ in iter.by_ref().take(3) {} 1759 1760 assert_eq!(iter.size_hint(), (3, Some(3))); 1761 } 1762 1763 #[test] test_iter_mut_len()1764 fn test_iter_mut_len() { 1765 use crate::libs::rbtree::RBTree; 1766 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1767 1768 let mut map: RBTree<_, _> = xs.iter().cloned().collect(); 1769 1770 let mut iter = map.iter_mut(); 1771 1772 for _ in iter.by_ref().take(3) {} 1773 1774 assert_eq!(iter.count(), 3); 1775 } 1776 1777 #[test] test_index()1778 fn test_index() { 1779 use crate::libs::rbtree::RBTree; 1780 let mut map = RBTree::new(); 1781 1782 map.insert(1, 2); 1783 map.insert(2, 1); 1784 map.insert(3, 4); 1785 1786 assert_eq!(map[&2], 1); 1787 } 1788 1789 #[test] 1790 #[should_panic] test_index_nonexistent()1791 fn test_index_nonexistent() { 1792 use crate::libs::rbtree::RBTree; 1793 let mut map = RBTree::new(); 1794 1795 map.insert(1, 2); 1796 map.insert(2, 1); 1797 map.insert(3, 4); 1798 1799 map[&4]; 1800 } 1801 1802 #[test] test_extend_iter()1803 fn test_extend_iter() { 1804 use crate::libs::rbtree::RBTree; 1805 let mut a = RBTree::new(); 1806 a.insert(1, "one"); 1807 let mut b = RBTree::new(); 1808 b.insert(2, "two"); 1809 b.insert(3, "three"); 1810 1811 a.extend(b.into_iter()); 1812 1813 assert_eq!(a.len(), 3); 1814 assert_eq!(a[&1], "one"); 1815 assert_eq!(a[&2], "two"); 1816 assert_eq!(a[&3], "three"); 1817 } 1818 1819 #[test] test_rev_iter()1820 fn test_rev_iter() { 1821 let mut a = RBTree::new(); 1822 a.insert(1, 1); 1823 a.insert(2, 2); 1824 a.insert(3, 3); 1825 1826 assert_eq!(a.len(), 3); 1827 let mut cache = vec![]; 1828 for e in a.iter().rev() { 1829 cache.push(e.0.clone()); 1830 } 1831 assert_eq!(&cache, &vec![3, 2, 1]); 1832 } 1833 } 1834