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