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 + Debug, V: Debug> { 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 + Debug, V: Debug> 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 + Debug, V: Debug>(*mut RBTreeNode<K, V>); 64 65 impl<K: Ord + Debug, V: Debug> Clone for NodePtr<K, V> { 66 fn clone(&self) -> NodePtr<K, V> { 67 *self 68 } 69 } 70 71 impl<K: Ord + Debug, V: Debug> Copy for NodePtr<K, V> {} 72 73 impl<K: Ord + Debug, V: Debug> 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 + Debug, V: Debug> 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 + Debug, V: Debug> 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 + Debug, V: Debug> Eq for NodePtr<K, V> {} 92 93 impl<K: Ord + Debug, V: Debug> 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 + Debug, V: Clone + Debug> 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 + Debug, V: Debug> { 343 root: NodePtr<K, V>, 344 len: usize, 345 } 346 347 unsafe impl<K: Ord + Debug, V: Debug> Send for RBTree<K, V> {} 348 unsafe impl<K: Ord + Debug, V: Debug> Sync for RBTree<K, V> {} 349 350 // Drop all owned pointers if the tree is dropped 351 impl<K: Ord + Debug, V: Debug> 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 + Debug, V: Clone + Debug> 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 + Debug, 421 V: PartialEq + Debug, 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: Eq + Ord + Debug, V: Eq + Debug> Eq for RBTree<K, V> {} 434 435 impl<'a, K: Ord + Debug, V: Debug> Index<&'a K> for RBTree<K, V> { 436 type Output = V; 437 438 #[inline] 439 fn index(&self, index: &K) -> &V { 440 self.get(index).expect("no entry found for key") 441 } 442 } 443 444 impl<K: Ord + Debug, V: Debug> FromIterator<(K, V)> for RBTree<K, V> { 445 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> RBTree<K, V> { 446 let mut tree = RBTree::new(); 447 tree.extend(iter); 448 tree 449 } 450 } 451 452 /// RBTree into iter 453 impl<K: Ord + Debug, V: Debug> Extend<(K, V)> for RBTree<K, V> { 454 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { 455 let iter = iter.into_iter(); 456 for (k, v) in iter { 457 self.insert(k, v); 458 } 459 } 460 } 461 462 /// provide the rbtree all keys 463 /// # Examples 464 /// ``` 465 /// use rbtree::RBTree; 466 /// let mut m = RBTree::new(); 467 /// for i in 1..6 { 468 /// m.insert(i, i); 469 /// } 470 /// let vec = vec![1, 2, 3, 4, 5]; 471 /// let key_vec: Vec<_> = m.keys().cloned().collect(); 472 /// assert_eq!(vec, key_vec); 473 /// ``` 474 pub struct Keys<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 475 inner: Iter<'a, K, V>, 476 } 477 478 impl<'a, K: Ord + Debug, V: Debug> Clone for Keys<'a, K, V> { 479 fn clone(&self) -> Keys<'a, K, V> { 480 Keys { 481 inner: self.inner.clone(), 482 } 483 } 484 } 485 486 impl<'a, K: Ord + Debug, V: Debug> fmt::Debug for Keys<'a, K, V> { 487 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 488 f.debug_list().entries(self.clone()).finish() 489 } 490 } 491 492 impl<'a, K: Ord + Debug, V: Debug> Iterator for Keys<'a, K, V> { 493 type Item = &'a K; 494 495 #[inline] 496 fn next(&mut self) -> Option<&'a K> { 497 self.inner.next().map(|(k, _)| k) 498 } 499 500 #[inline] 501 fn size_hint(&self) -> (usize, Option<usize>) { 502 self.inner.size_hint() 503 } 504 } 505 506 /// provide the rbtree all values order by key 507 /// # Examples 508 /// ``` 509 /// use rbtree::RBTree; 510 /// let mut m = RBTree::new(); 511 /// m.insert(2, 5); 512 /// m.insert(1, 6); 513 /// m.insert(3, 8); 514 /// m.insert(4, 9); 515 /// let vec = vec![6, 5, 8, 9]; 516 /// let key_vec: Vec<_> = m.values().cloned().collect(); 517 /// assert_eq!(vec, key_vec); 518 /// ``` 519 pub struct Values<'a, K: Ord + Debug, V: Debug> { 520 inner: Iter<'a, K, V>, 521 } 522 523 impl<'a, K: Ord + Debug, V: Debug> Clone for Values<'a, K, V> { 524 fn clone(&self) -> Values<'a, K, V> { 525 Values { 526 inner: self.inner.clone(), 527 } 528 } 529 } 530 531 impl<'a, K: Ord + Debug, V: Debug> fmt::Debug for Values<'a, K, V> { 532 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 533 f.debug_list().entries(self.clone()).finish() 534 } 535 } 536 537 impl<'a, K: Ord + Debug, V: Debug> Iterator for Values<'a, K, V> { 538 type Item = &'a V; 539 540 #[inline] 541 fn next(&mut self) -> Option<&'a V> { 542 self.inner.next().map(|(_, v)| v) 543 } 544 545 #[inline] 546 fn size_hint(&self) -> (usize, Option<usize>) { 547 self.inner.size_hint() 548 } 549 } 550 551 /// provide the rbtree all values and it can be modify 552 /// # Examples 553 /// ``` 554 /// use rbtree::RBTree; 555 /// let mut m = RBTree::new(); 556 /// for i in 0..32 { 557 /// m.insert(i, i); 558 /// } 559 /// assert_eq!(m.len(), 32); 560 /// for v in m.values_mut() { 561 /// *v *= 2; 562 /// } 563 /// for i in 0..32 { 564 /// assert_eq!(m.get(&i).unwrap(), &(i * 2)); 565 /// } 566 /// ``` 567 pub struct ValuesMut<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 568 inner: IterMut<'a, K, V>, 569 } 570 571 impl<'a, K: Ord + Debug, V: Debug> Clone for ValuesMut<'a, K, V> { 572 fn clone(&self) -> ValuesMut<'a, K, V> { 573 ValuesMut { 574 inner: self.inner.clone(), 575 } 576 } 577 } 578 579 impl<'a, K: Ord + Debug, V: Debug> fmt::Debug for ValuesMut<'a, K, V> { 580 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 581 f.debug_list().entries(self.clone()).finish() 582 } 583 } 584 585 impl<'a, K: Ord + Debug, V: Debug> Iterator for ValuesMut<'a, K, V> { 586 type Item = &'a mut V; 587 588 #[inline] 589 fn next(&mut self) -> Option<&'a mut V> { 590 self.inner.next().map(|(_, v)| v) 591 } 592 593 #[inline] 594 fn size_hint(&self) -> (usize, Option<usize>) { 595 self.inner.size_hint() 596 } 597 } 598 599 /// Convert RBTree to iter, move out the tree. 600 pub struct IntoIter<K: Ord + Debug, V: Debug> { 601 head: NodePtr<K, V>, 602 tail: NodePtr<K, V>, 603 len: usize, 604 } 605 606 // Drop all owned pointers if the collection is dropped 607 impl<K: Ord + Debug, V: Debug> Drop for IntoIter<K, V> { 608 #[inline] 609 fn drop(&mut self) { 610 for (_, _) in self {} 611 } 612 } 613 614 impl<K: Ord + Debug, V: Debug> Iterator for IntoIter<K, V> { 615 type Item = (K, V); 616 617 fn next(&mut self) -> Option<(K, V)> { 618 if self.len == 0 { 619 return None; 620 } 621 622 if self.head.is_null() { 623 return None; 624 } 625 626 let next = self.head.next(); 627 let (k, v) = unsafe { 628 ( 629 core::ptr::read(&(*self.head.0).key), 630 core::ptr::read(&(*self.head.0).value), 631 ) 632 }; 633 self.head = next; 634 self.len -= 1; 635 Some((k, v)) 636 } 637 638 fn size_hint(&self) -> (usize, Option<usize>) { 639 (self.len, Some(self.len)) 640 } 641 } 642 643 impl<K: Ord + Debug, V: Debug> DoubleEndedIterator for IntoIter<K, V> { 644 #[inline] 645 fn next_back(&mut self) -> Option<(K, V)> { 646 if self.len == 0 { 647 return None; 648 } 649 650 if self.tail.is_null() { 651 return None; 652 } 653 654 let prev = self.tail.prev(); 655 let obj = unsafe { Box::from_raw(self.tail.0) }; 656 let (k, v) = obj.pair(); 657 self.tail = prev; 658 self.len -= 1; 659 Some((k, v)) 660 } 661 } 662 663 /// provide iter ref for RBTree 664 /// # Examples 665 /// ``` 666 /// use rbtree::RBTree; 667 /// let mut m = RBTree::new(); 668 /// for i in 0..32 { 669 /// m.insert(i, i * 2); 670 /// } 671 /// assert_eq!(m.len(), 32); 672 /// let mut observed: u32 = 0; 673 /// for (k, v) in m.iter() { 674 /// assert_eq!(*v, *k * 2); 675 /// observed |= 1 << *k; 676 /// } 677 /// assert_eq!(observed, 0xFFFF_FFFF); 678 /// ``` 679 pub struct Iter<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 680 head: NodePtr<K, V>, 681 tail: NodePtr<K, V>, 682 len: usize, 683 _marker: marker::PhantomData<&'a ()>, 684 } 685 686 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Clone for Iter<'a, K, V> { 687 fn clone(&self) -> Iter<'a, K, V> { 688 Iter { 689 head: self.head, 690 tail: self.tail, 691 len: self.len, 692 _marker: self._marker, 693 } 694 } 695 } 696 697 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Iterator for Iter<'a, K, V> { 698 type Item = (&'a K, &'a V); 699 700 fn next(&mut self) -> Option<(&'a K, &'a V)> { 701 if self.len == 0 { 702 return None; 703 } 704 705 if self.head.is_null() { 706 return None; 707 } 708 709 let (k, v) = unsafe { (&(*self.head.0).key, &(*self.head.0).value) }; 710 self.head = self.head.next(); 711 self.len -= 1; 712 Some((k, v)) 713 } 714 715 fn size_hint(&self) -> (usize, Option<usize>) { 716 (self.len, Some(self.len)) 717 } 718 } 719 720 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> DoubleEndedIterator for Iter<'a, K, V> { 721 #[inline] 722 fn next_back(&mut self) -> Option<(&'a K, &'a V)> { 723 // kdebug!("len = {:?}", self.len); 724 if self.len == 0 { 725 return None; 726 } 727 728 let (k, v) = unsafe { (&(*self.tail.0).key, &(*self.tail.0).value) }; 729 self.tail = self.tail.prev(); 730 self.len -= 1; 731 Some((k, v)) 732 } 733 } 734 735 /// provide iter mut ref for RBTree 736 /// # Examples 737 /// ``` 738 /// use rbtree::RBTree; 739 /// let mut m = RBTree::new(); 740 /// for i in 0..32 { 741 /// m.insert(i, i); 742 /// } 743 /// assert_eq!(m.len(), 32); 744 /// for (_, v) in m.iter_mut() { 745 /// *v *= 2; 746 /// } 747 /// for i in 0..32 { 748 /// assert_eq!(m.get(&i).unwrap(), &(i * 2)); 749 /// } 750 /// ``` 751 pub struct IterMut<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 752 head: NodePtr<K, V>, 753 tail: NodePtr<K, V>, 754 len: usize, 755 _marker: marker::PhantomData<&'a ()>, 756 } 757 758 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Clone for IterMut<'a, K, V> { 759 fn clone(&self) -> IterMut<'a, K, V> { 760 IterMut { 761 head: self.head, 762 tail: self.tail, 763 len: self.len, 764 _marker: self._marker, 765 } 766 } 767 } 768 769 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Iterator for IterMut<'a, K, V> { 770 type Item = (&'a K, &'a mut V); 771 772 fn next(&mut self) -> Option<(&'a K, &'a mut V)> { 773 if self.len == 0 { 774 return None; 775 } 776 777 if self.head.is_null() { 778 return None; 779 } 780 781 let (k, v) = unsafe { (&(*self.head.0).key, &mut (*self.head.0).value) }; 782 self.head = self.head.next(); 783 self.len -= 1; 784 Some((k, v)) 785 } 786 787 fn size_hint(&self) -> (usize, Option<usize>) { 788 (self.len, Some(self.len)) 789 } 790 } 791 792 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> DoubleEndedIterator for IterMut<'a, K, V> { 793 #[inline] 794 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { 795 if self.len == 0 { 796 return None; 797 } 798 799 if self.tail == self.head { 800 return None; 801 } 802 803 let (k, v) = unsafe { (&(*self.tail.0).key, &mut (*self.tail.0).value) }; 804 self.tail = self.tail.prev(); 805 self.len -= 1; 806 Some((k, v)) 807 } 808 } 809 810 impl<K: Ord + Debug, V: Debug> IntoIterator for RBTree<K, V> { 811 type Item = (K, V); 812 type IntoIter = IntoIter<K, V>; 813 814 #[inline] 815 fn into_iter(mut self) -> IntoIter<K, V> { 816 let iter = if self.root.is_null() { 817 IntoIter { 818 head: NodePtr::null(), 819 tail: NodePtr::null(), 820 len: self.len, 821 } 822 } else { 823 IntoIter { 824 head: self.first_child(), 825 tail: self.last_child(), 826 len: self.len, 827 } 828 }; 829 self.fast_clear(); 830 iter 831 } 832 } 833 834 impl<K: Ord + Debug, V: Debug> RBTree<K, V> { 835 /// Creates an empty `RBTree`. 836 pub fn new() -> RBTree<K, V> { 837 RBTree { 838 root: NodePtr::null(), 839 len: 0, 840 } 841 } 842 843 /// Returns the len of `RBTree`. 844 #[inline] 845 pub fn len(&self) -> usize { 846 self.len 847 } 848 849 /// Returns `true` if the `RBTree` is empty. 850 #[inline] 851 pub fn is_empty(&self) -> bool { 852 self.root.is_null() 853 } 854 855 /* 856 * 对红黑树的节点(x)进行左旋转 857 * 858 * 左旋示意图(对节点x进行左旋)： 859 * px px 860 * / / 861 * x y 862 * / \ --(左旋)--> / \ # 863 * lx y x ry 864 * / \ / \ 865 * ly ry lx ly 866 * 867 * 868 */ 869 #[inline] 870 unsafe fn left_rotate(&mut self, mut node: NodePtr<K, V>) { 871 let mut temp = node.right(); 872 node.set_right(temp.left()); 873 874 if !temp.left().is_null() { 875 temp.left().set_parent(node); 876 } 877 878 temp.set_parent(node.parent()); 879 if node == self.root { 880 self.root = temp; 881 } else if node == node.parent().left() { 882 node.parent().set_left(temp); 883 } else { 884 node.parent().set_right(temp); 885 } 886 887 temp.set_left(node); 888 node.set_parent(temp); 889 } 890 891 /* 892 * 对红黑树的节点(y)进行右旋转 893 * 894 * 右旋示意图(对节点y进行左旋)： 895 * py py 896 * / / 897 * y x 898 * / \ --(右旋)--> / \ # 899 * x ry lx y 900 * / \ / \ # 901 * lx rx rx ry 902 * 903 */ 904 #[inline] 905 unsafe fn right_rotate(&mut self, mut node: NodePtr<K, V>) { 906 let mut temp = node.left(); 907 node.set_left(temp.right()); 908 909 if !temp.right().is_null() { 910 temp.right().set_parent(node); 911 } 912 913 temp.set_parent(node.parent()); 914 if node == self.root { 915 self.root = temp; 916 } else if node == node.parent().right() { 917 node.parent().set_right(temp); 918 } else { 919 node.parent().set_left(temp); 920 } 921 922 temp.set_right(node); 923 node.set_parent(temp); 924 } 925 926 /// replace value if key exist, if not exist insert it. 927 /// # Examples 928 /// ``` 929 /// use rbtree::RBTree; 930 /// let mut m = RBTree::new(); 931 /// assert_eq!(m.len(), 0); 932 /// m.insert(2, 4); 933 /// assert_eq!(m.len(), 1); 934 /// assert_eq!(m.replace_or_insert(2, 6).unwrap(), 4); 935 /// assert_eq!(m.len(), 1); 936 /// assert_eq!(*m.get(&2).unwrap(), 6); 937 /// ``` 938 #[inline] 939 pub fn replace_or_insert(&mut self, k: K, mut v: V) -> Option<V> { 940 let node = self.find_node(&k); 941 if node.is_null() { 942 self.insert(k, v); 943 return None; 944 } 945 946 unsafe { 947 mem::swap(&mut v, &mut (*node.0).value); 948 } 949 950 Some(v) 951 } 952 953 #[inline] 954 unsafe fn insert_fixup(&mut self, mut node: NodePtr<K, V>) { 955 let mut parent; 956 let mut gparent; 957 958 while node.parent().is_red_color() { 959 parent = node.parent(); 960 gparent = parent.parent(); 961 //若“父节点”是“祖父节点的左孩子” 962 if parent == gparent.left() { 963 // Case 1条件：叔叔节点是红色 964 let mut uncle = gparent.right(); 965 if !uncle.is_null() && uncle.is_red_color() { 966 uncle.set_black_color(); 967 parent.set_black_color(); 968 gparent.set_red_color(); 969 node = gparent; 970 continue; 971 } 972 973 // Case 2条件：叔叔是黑色，且当前节点是右孩子 974 if parent.right() == node { 975 self.left_rotate(parent); 976 swap(&mut parent, &mut node); 977 } 978 979 // Case 3条件：叔叔是黑色，且当前节点是左孩子。 980 parent.set_black_color(); 981 gparent.set_red_color(); 982 self.right_rotate(gparent); 983 } else { 984 // Case 1条件：叔叔节点是红色 985 let mut uncle = gparent.left(); 986 if !uncle.is_null() && uncle.is_red_color() { 987 uncle.set_black_color(); 988 parent.set_black_color(); 989 gparent.set_red_color(); 990 node = gparent; 991 continue; 992 } 993 994 // Case 2条件：叔叔是黑色，且当前节点是右孩子 995 if parent.left() == node { 996 self.right_rotate(parent); 997 swap(&mut parent, &mut node); 998 } 999 1000 // Case 3条件：叔叔是黑色，且当前节点是左孩子。 1001 parent.set_black_color(); 1002 gparent.set_red_color(); 1003 self.left_rotate(gparent); 1004 } 1005 } 1006 self.root.set_black_color(); 1007 } 1008 1009 #[inline] 1010 pub fn insert(&mut self, k: K, v: V) { 1011 self.len += 1; 1012 let mut node = NodePtr::new(k, v); 1013 let mut y = NodePtr::null(); 1014 let mut x = self.root; 1015 1016 while !x.is_null() { 1017 y = x; 1018 match node.cmp(&x) { 1019 Ordering::Less => { 1020 x = x.left(); 1021 } 1022 _ => { 1023 x = x.right(); 1024 } 1025 }; 1026 } 1027 node.set_parent(y); 1028 1029 if y.is_null() { 1030 self.root = node; 1031 } else { 1032 match node.cmp(&y) { 1033 Ordering::Less => { 1034 y.set_left(node); 1035 } 1036 _ => { 1037 y.set_right(node); 1038 } 1039 }; 1040 } 1041 1042 node.set_red_color(); 1043 unsafe { 1044 self.insert_fixup(node); 1045 } 1046 } 1047 1048 #[inline] 1049 fn find_node(&self, k: &K) -> NodePtr<K, V> { 1050 if self.root.is_null() { 1051 return NodePtr::null(); 1052 } 1053 let mut temp = &self.root; 1054 unsafe { 1055 loop { 1056 let next = match k.cmp(&(*temp.0).key) { 1057 Ordering::Less => &mut (*temp.0).left, 1058 Ordering::Greater => &mut (*temp.0).right, 1059 Ordering::Equal => return *temp, 1060 }; 1061 if next.is_null() { 1062 break; 1063 } 1064 temp = next; 1065 } 1066 } 1067 NodePtr::null() 1068 } 1069 1070 #[inline] 1071 fn first_child(&self) -> NodePtr<K, V> { 1072 if self.root.is_null() { 1073 NodePtr::null() 1074 } else { 1075 let mut temp = self.root; 1076 while !temp.left().is_null() { 1077 temp = temp.left(); 1078 } 1079 return temp; 1080 } 1081 } 1082 1083 #[inline] 1084 fn last_child(&self) -> NodePtr<K, V> { 1085 if self.root.is_null() { 1086 NodePtr::null() 1087 } else { 1088 let mut temp = self.root; 1089 while !temp.right().is_null() { 1090 temp = temp.right(); 1091 } 1092 return temp; 1093 } 1094 } 1095 1096 #[inline] 1097 pub fn get_first(&self) -> Option<(&K, &V)> { 1098 let first = self.first_child(); 1099 if first.is_null() { 1100 return None; 1101 } 1102 unsafe { Some((&(*first.0).key, &(*first.0).value)) } 1103 } 1104 1105 #[inline] 1106 pub fn get_last(&self) -> Option<(&K, &V)> { 1107 let last = self.last_child(); 1108 if last.is_null() { 1109 return None; 1110 } 1111 unsafe { Some((&(*last.0).key, &(*last.0).value)) } 1112 } 1113 1114 #[inline] 1115 pub fn pop_first(&mut self) -> Option<(K, V)> { 1116 let first = self.first_child(); 1117 if first.is_null() { 1118 return None; 1119 } 1120 unsafe { Some(self.delete(first)) } 1121 } 1122 1123 #[inline] 1124 pub fn pop_last(&mut self) -> Option<(K, V)> { 1125 let last = self.last_child(); 1126 if last.is_null() { 1127 return None; 1128 } 1129 unsafe { Some(self.delete(last)) } 1130 } 1131 1132 #[inline] 1133 pub fn get_first_mut(&mut self) -> Option<(&K, &mut V)> { 1134 let first = self.first_child(); 1135 if first.is_null() { 1136 return None; 1137 } 1138 unsafe { Some((&(*first.0).key, &mut (*first.0).value)) } 1139 } 1140 1141 #[inline] 1142 pub fn get_last_mut(&mut self) -> Option<(&K, &mut V)> { 1143 let last = self.last_child(); 1144 if last.is_null() { 1145 return None; 1146 } 1147 unsafe { Some((&(*last.0).key, &mut (*last.0).value)) } 1148 } 1149 1150 #[inline] 1151 pub fn get(&self, k: &K) -> Option<&V> { 1152 let node = self.find_node(k); 1153 if node.is_null() { 1154 return None; 1155 } 1156 1157 unsafe { Some(&(*node.0).value) } 1158 } 1159 1160 #[inline] 1161 pub fn get_mut(&mut self, k: &K) -> Option<&mut V> { 1162 let node = self.find_node(k); 1163 if node.is_null() { 1164 return None; 1165 } 1166 1167 unsafe { Some(&mut (*node.0).value) } 1168 } 1169 1170 #[inline] 1171 pub fn contains_key(&self, k: &K) -> bool { 1172 let node = self.find_node(k); 1173 if node.is_null() { 1174 return false; 1175 } 1176 true 1177 } 1178 1179 #[allow(clippy::only_used_in_recursion)] 1180 #[inline] 1181 fn clear_recurse(&mut self, current: NodePtr<K, V>) { 1182 if !current.is_null() { 1183 unsafe { 1184 self.clear_recurse(current.left()); 1185 self.clear_recurse(current.right()); 1186 drop(Box::from_raw(current.0)); 1187 } 1188 } 1189 } 1190 1191 /// clear all red back tree elements. 1192 /// # Examples 1193 /// ``` 1194 /// use rbtree::RBTree; 1195 /// let mut m = RBTree::new(); 1196 /// for i in 0..6 { 1197 /// m.insert(i, i); 1198 /// } 1199 /// assert_eq!(m.len(), 6); 1200 /// m.clear(); 1201 /// assert_eq!(m.len(), 0); 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 self.len = 0; 1209 } 1210 1211 /// Empties the `RBTree` without freeing objects in it. 1212 #[inline] 1213 fn fast_clear(&mut self) { 1214 self.root = NodePtr::null(); 1215 self.len = 0; 1216 } 1217 1218 #[inline] 1219 pub fn remove(&mut self, k: &K) -> Option<V> { 1220 let node = self.find_node(k); 1221 if node.is_null() { 1222 return None; 1223 } 1224 unsafe { Some(self.delete(node).1) } 1225 } 1226 1227 #[inline] 1228 unsafe fn delete_fixup(&mut self, mut node: NodePtr<K, V>, mut parent: NodePtr<K, V>) { 1229 let mut other; 1230 while node != self.root && node.is_black_color() { 1231 if parent.left() == node { 1232 other = parent.right(); 1233 //x的兄弟w是红色的 1234 if other.is_red_color() { 1235 other.set_black_color(); 1236 parent.set_red_color(); 1237 self.left_rotate(parent); 1238 other = parent.right(); 1239 } 1240 1241 //x的兄弟w是黑色，且w的俩个孩子也都是黑色的 1242 if other.left().is_black_color() && other.right().is_black_color() { 1243 other.set_red_color(); 1244 node = parent; 1245 parent = node.parent(); 1246 } else { 1247 //x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 1248 if other.right().is_black_color() { 1249 other.left().set_black_color(); 1250 other.set_red_color(); 1251 self.right_rotate(other); 1252 other = parent.right(); 1253 } 1254 //x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 1255 other.set_color(parent.get_color()); 1256 parent.set_black_color(); 1257 other.right().set_black_color(); 1258 self.left_rotate(parent); 1259 node = self.root; 1260 break; 1261 } 1262 } else { 1263 other = parent.left(); 1264 //x的兄弟w是红色的 1265 if other.is_red_color() { 1266 other.set_black_color(); 1267 parent.set_red_color(); 1268 self.right_rotate(parent); 1269 other = parent.left(); 1270 } 1271 1272 //x的兄弟w是黑色，且w的俩个孩子也都是黑色的 1273 if other.left().is_black_color() && other.right().is_black_color() { 1274 other.set_red_color(); 1275 node = parent; 1276 parent = node.parent(); 1277 } else { 1278 //x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 1279 if other.left().is_black_color() { 1280 other.right().set_black_color(); 1281 other.set_red_color(); 1282 self.left_rotate(other); 1283 other = parent.left(); 1284 } 1285 //x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 1286 other.set_color(parent.get_color()); 1287 parent.set_black_color(); 1288 other.left().set_black_color(); 1289 self.right_rotate(parent); 1290 node = self.root; 1291 break; 1292 } 1293 } 1294 } 1295 1296 node.set_black_color(); 1297 } 1298 1299 #[inline] 1300 unsafe fn delete(&mut self, node: NodePtr<K, V>) -> (K, V) { 1301 let mut child; 1302 let mut parent; 1303 let color; 1304 1305 self.len -= 1; 1306 // 被删除节点的"左右孩子都不为空"的情况。 1307 if !node.left().is_null() && !node.right().is_null() { 1308 // 被删节点的后继节点。(称为"取代节点") 1309 // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。 1310 let mut replace = node.right().min_node(); 1311 if node == self.root { 1312 self.root = replace; 1313 } else if node.parent().left() == node { 1314 node.parent().set_left(replace); 1315 } else { 1316 node.parent().set_right(replace); 1317 } 1318 1319 // child是"取代节点"的右孩子，也是需要"调整的节点"。 1320 // "取代节点"肯定不存在左孩子！因为它是一个后继节点。 1321 child = replace.right(); 1322 parent = replace.parent(); 1323 color = replace.get_color(); 1324 if parent == node { 1325 parent = replace; 1326 } else { 1327 if !child.is_null() { 1328 child.set_parent(parent); 1329 } 1330 parent.set_left(child); 1331 replace.set_right(node.right()); 1332 node.right().set_parent(replace); 1333 } 1334 1335 replace.set_parent(node.parent()); 1336 replace.set_color(node.get_color()); 1337 replace.set_left(node.left()); 1338 node.left().set_parent(replace); 1339 1340 if color == Color::Black { 1341 self.delete_fixup(child, parent); 1342 } 1343 1344 let obj = Box::from_raw(node.0); 1345 return obj.pair(); 1346 } 1347 1348 if !node.left().is_null() { 1349 child = node.left(); 1350 } else { 1351 child = node.right(); 1352 } 1353 1354 parent = node.parent(); 1355 color = node.get_color(); 1356 if !child.is_null() { 1357 child.set_parent(parent); 1358 } 1359 1360 if self.root == node { 1361 self.root = child 1362 } else if parent.left() == node { 1363 parent.set_left(child); 1364 } else { 1365 parent.set_right(child); 1366 } 1367 1368 if color == Color::Black { 1369 self.delete_fixup(child, parent); 1370 } 1371 1372 let obj = Box::from_raw(node.0); 1373 return obj.pair(); 1374 } 1375 1376 /// Return the keys iter 1377 #[inline] 1378 pub fn keys(&self) -> Keys<K, V> { 1379 Keys { inner: self.iter() } 1380 } 1381 1382 /// Return the value iter 1383 #[inline] 1384 pub fn values(&self) -> Values<K, V> { 1385 Values { inner: self.iter() } 1386 } 1387 1388 /// Return the value iter mut 1389 #[inline] 1390 pub fn values_mut(&mut self) -> ValuesMut<K, V> { 1391 ValuesMut { 1392 inner: self.iter_mut(), 1393 } 1394 } 1395 1396 /// Return the key and value iter 1397 #[inline] 1398 pub fn iter(&self) -> Iter<K, V> { 1399 Iter { 1400 head: self.first_child(), 1401 tail: self.last_child(), 1402 len: self.len, 1403 _marker: marker::PhantomData, 1404 } 1405 } 1406 1407 /// Return the key and mut value iter 1408 #[inline] 1409 pub fn iter_mut(&mut self) -> IterMut<K, V> { 1410 IterMut { 1411 head: self.first_child(), 1412 tail: self.last_child(), 1413 len: self.len, 1414 _marker: marker::PhantomData, 1415 } 1416 } 1417 } 1418 1419 #[cfg(test)] 1420 mod tests { 1421 1422 #[test] 1423 fn test_insert() { 1424 use crate::libs::rbtree::RBTree; 1425 let mut m = RBTree::new(); 1426 assert_eq!(m.len(), 0); 1427 m.insert(1, 2); 1428 assert_eq!(m.len(), 1); 1429 m.insert(2, 4); 1430 assert_eq!(m.len(), 2); 1431 m.insert(2, 6); 1432 assert_eq!(m.len(), 3); 1433 assert_eq!(*m.get(&1).unwrap(), 2); 1434 assert_eq!(*m.get(&2).unwrap(), 4); 1435 assert_eq!(*m.get(&2).unwrap(), 4); 1436 } 1437 1438 #[test] 1439 fn test_replace() { 1440 use crate::libs::rbtree::RBTree; 1441 let mut m = RBTree::new(); 1442 assert_eq!(m.len(), 0); 1443 m.insert(2, 4); 1444 assert_eq!(m.len(), 1); 1445 assert_eq!(m.replace_or_insert(2, 6).unwrap(), 4); 1446 assert_eq!(m.len(), 1); 1447 assert_eq!(*m.get(&2).unwrap(), 6); 1448 } 1449 1450 #[test] 1451 fn test_clone() { 1452 use crate::libs::rbtree::RBTree; 1453 let mut m = RBTree::new(); 1454 assert_eq!(m.len(), 0); 1455 m.insert(1, 2); 1456 assert_eq!(m.len(), 1); 1457 m.insert(2, 4); 1458 assert_eq!(m.len(), 2); 1459 let m2 = m.clone(); 1460 m.clear(); 1461 assert_eq!(*m2.get(&1).unwrap(), 2); 1462 assert_eq!(*m2.get(&2).unwrap(), 4); 1463 assert_eq!(m2.len(), 2); 1464 } 1465 1466 #[test] 1467 fn test_empty_remove() { 1468 use crate::libs::rbtree::RBTree; 1469 let mut m: RBTree<isize, bool> = RBTree::new(); 1470 assert_eq!(m.remove(&0), None); 1471 } 1472 1473 #[test] 1474 fn test_empty_iter() { 1475 use crate::libs::rbtree::RBTree; 1476 let mut m: RBTree<isize, bool> = RBTree::new(); 1477 assert_eq!(m.iter().next(), None); 1478 assert_eq!(m.iter_mut().next(), None); 1479 assert_eq!(m.len(), 0); 1480 assert!(m.is_empty()); 1481 assert_eq!(m.into_iter().next(), None); 1482 } 1483 1484 #[test] 1485 fn test_lots_of_insertions() { 1486 use crate::libs::rbtree::RBTree; 1487 let mut m = RBTree::new(); 1488 1489 // Try this a few times to make sure we never screw up the hashmap's 1490 // internal state. 1491 for _ in 0..10 { 1492 assert!(m.is_empty()); 1493 1494 for i in 1..101 { 1495 m.insert(i, i); 1496 1497 for j in 1..i + 1 { 1498 let r = m.get(&j); 1499 assert_eq!(r, Some(&j)); 1500 } 1501 1502 for j in i + 1..101 { 1503 let r = m.get(&j); 1504 assert_eq!(r, None); 1505 } 1506 } 1507 1508 for i in 101..201 { 1509 assert!(!m.contains_key(&i)); 1510 } 1511 1512 // remove forwards 1513 for i in 1..101 { 1514 assert!(m.remove(&i).is_some()); 1515 1516 for j in 1..i + 1 { 1517 assert!(!m.contains_key(&j)); 1518 } 1519 1520 for j in i + 1..101 { 1521 assert!(m.contains_key(&j)); 1522 } 1523 } 1524 1525 for i in 1..101 { 1526 assert!(!m.contains_key(&i)); 1527 } 1528 1529 for i in 1..101 { 1530 m.insert(i, i); 1531 } 1532 1533 // remove backwards 1534 for i in (1..101).rev() { 1535 assert!(m.remove(&i).is_some()); 1536 1537 for j in i..101 { 1538 assert!(!m.contains_key(&j)); 1539 } 1540 1541 for j in 1..i { 1542 assert!(m.contains_key(&j)); 1543 } 1544 } 1545 } 1546 } 1547 1548 #[test] 1549 fn test_find_mut() { 1550 use crate::libs::rbtree::RBTree; 1551 let mut m = RBTree::new(); 1552 m.insert(1, 12); 1553 m.insert(2, 8); 1554 m.insert(5, 14); 1555 let new = 100; 1556 match m.get_mut(&5) { 1557 None => panic!(), 1558 Some(x) => *x = new, 1559 } 1560 assert_eq!(m.get(&5), Some(&new)); 1561 } 1562 1563 #[test] 1564 fn test_remove() { 1565 use crate::libs::rbtree::RBTree; 1566 let mut m = RBTree::new(); 1567 m.insert(1, 2); 1568 assert_eq!(*m.get(&1).unwrap(), 2); 1569 m.insert(5, 3); 1570 assert_eq!(*m.get(&5).unwrap(), 3); 1571 m.insert(9, 4); 1572 assert_eq!(*m.get(&1).unwrap(), 2); 1573 assert_eq!(*m.get(&5).unwrap(), 3); 1574 assert_eq!(*m.get(&9).unwrap(), 4); 1575 assert_eq!(m.remove(&1).unwrap(), 2); 1576 assert_eq!(m.remove(&5).unwrap(), 3); 1577 assert_eq!(m.remove(&9).unwrap(), 4); 1578 assert_eq!(m.len(), 0); 1579 } 1580 1581 #[test] 1582 fn test_is_empty() { 1583 use crate::libs::rbtree::RBTree; 1584 let mut m = RBTree::new(); 1585 m.insert(1, 2); 1586 assert!(!m.is_empty()); 1587 assert!(m.remove(&1).is_some()); 1588 assert!(m.is_empty()); 1589 } 1590 1591 #[test] 1592 fn test_pop() { 1593 use crate::libs::rbtree::RBTree; 1594 let mut m = RBTree::new(); 1595 m.insert(2, 4); 1596 m.insert(1, 2); 1597 m.insert(3, 6); 1598 assert_eq!(m.len(), 3); 1599 assert_eq!(m.pop_first(), Some((1, 2))); 1600 assert_eq!(m.len(), 2); 1601 assert_eq!(m.pop_last(), Some((3, 6))); 1602 assert_eq!(m.len(), 1); 1603 assert_eq!(m.get_first(), Some((&2, &4))); 1604 assert_eq!(m.get_last(), Some((&2, &4))); 1605 } 1606 1607 #[test] 1608 fn test_iterate() { 1609 use crate::libs::rbtree::RBTree; 1610 let mut m = RBTree::new(); 1611 for i in 0..32 { 1612 m.insert(i, i * 2); 1613 } 1614 assert_eq!(m.len(), 32); 1615 1616 let mut observed: u32 = 0; 1617 1618 for (k, v) in m.iter() { 1619 assert_eq!(*v, *k * 2); 1620 observed |= 1 << *k; 1621 } 1622 assert_eq!(observed, 0xFFFF_FFFF); 1623 } 1624 1625 #[test] 1626 fn test_keys() { 1627 use crate::libs::rbtree::RBTree; 1628 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; 1629 let map: RBTree<_, _> = vec.into_iter().collect(); 1630 let keys: Vec<_> = map.keys().cloned().collect(); 1631 assert_eq!(keys.len(), 3); 1632 assert!(keys.contains(&1)); 1633 assert!(keys.contains(&2)); 1634 assert!(keys.contains(&3)); 1635 } 1636 1637 #[test] 1638 fn test_values() { 1639 use crate::libs::rbtree::RBTree; 1640 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; 1641 let map: RBTree<_, _> = vec.into_iter().collect(); 1642 let values: Vec<_> = map.values().cloned().collect(); 1643 assert_eq!(values.len(), 3); 1644 assert!(values.contains(&'a')); 1645 assert!(values.contains(&'b')); 1646 assert!(values.contains(&'c')); 1647 } 1648 1649 #[test] 1650 fn test_values_mut() { 1651 use crate::libs::rbtree::RBTree; 1652 let vec = vec![(1, 1), (2, 2), (3, 3)]; 1653 let mut map: RBTree<_, _> = vec.into_iter().collect(); 1654 for value in map.values_mut() { 1655 *value = (*value) * 2 1656 } 1657 let values: Vec<_> = map.values().cloned().collect(); 1658 assert_eq!(values.len(), 3); 1659 assert!(values.contains(&2)); 1660 assert!(values.contains(&4)); 1661 assert!(values.contains(&6)); 1662 } 1663 1664 #[test] 1665 fn test_find() { 1666 use crate::libs::rbtree::RBTree; 1667 let mut m = RBTree::new(); 1668 assert!(m.get(&1).is_none()); 1669 m.insert(1, 2); 1670 match m.get(&1) { 1671 None => panic!(), 1672 Some(v) => assert_eq!(*v, 2), 1673 } 1674 } 1675 1676 #[test] 1677 fn test_eq() { 1678 use crate::libs::rbtree::RBTree; 1679 let mut m1 = RBTree::new(); 1680 m1.insert(1, 2); 1681 m1.insert(2, 3); 1682 m1.insert(3, 4); 1683 1684 let mut m2 = RBTree::new(); 1685 m2.insert(1, 2); 1686 m2.insert(2, 3); 1687 1688 assert!(m1 != m2); 1689 1690 m2.insert(3, 4); 1691 1692 assert_eq!(m1, m2); 1693 } 1694 1695 #[test] 1696 fn test_show() { 1697 use crate::libs::rbtree::RBTree; 1698 let mut map = RBTree::new(); 1699 let empty: RBTree<i32, i32> = RBTree::new(); 1700 1701 map.insert(1, 2); 1702 map.insert(3, 4); 1703 1704 let map_str = format!("{:?}", map); 1705 1706 assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}"); 1707 assert_eq!(format!("{:?}", empty), "{}"); 1708 } 1709 1710 #[test] 1711 fn test_from_iter() { 1712 use crate::libs::rbtree::RBTree; 1713 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1714 1715 let map: RBTree<_, _> = xs.iter().cloned().collect(); 1716 1717 for &(k, v) in &xs { 1718 assert_eq!(map.get(&k), Some(&v)); 1719 } 1720 } 1721 1722 #[test] 1723 fn test_size_hint() { 1724 use crate::libs::rbtree::RBTree; 1725 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1726 1727 let map: RBTree<_, _> = xs.iter().cloned().collect(); 1728 1729 let mut iter = map.iter(); 1730 1731 for _ in iter.by_ref().take(3) {} 1732 1733 assert_eq!(iter.size_hint(), (3, Some(3))); 1734 } 1735 1736 #[test] 1737 fn test_iter_len() { 1738 use crate::libs::rbtree::RBTree; 1739 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1740 1741 let map: RBTree<_, _> = xs.iter().cloned().collect(); 1742 1743 let mut iter = map.iter(); 1744 1745 for _ in iter.by_ref().take(3) {} 1746 1747 assert_eq!(iter.count(), 3); 1748 } 1749 1750 #[test] 1751 fn test_mut_size_hint() { 1752 use crate::libs::rbtree::RBTree; 1753 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1754 1755 let mut map: RBTree<_, _> = xs.iter().cloned().collect(); 1756 1757 let mut iter = map.iter_mut(); 1758 1759 for _ in iter.by_ref().take(3) {} 1760 1761 assert_eq!(iter.size_hint(), (3, Some(3))); 1762 } 1763 1764 #[test] 1765 fn test_iter_mut_len() { 1766 use crate::libs::rbtree::RBTree; 1767 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; 1768 1769 let mut map: RBTree<_, _> = xs.iter().cloned().collect(); 1770 1771 let mut iter = map.iter_mut(); 1772 1773 for _ in iter.by_ref().take(3) {} 1774 1775 assert_eq!(iter.count(), 3); 1776 } 1777 1778 #[test] 1779 fn test_index() { 1780 use crate::libs::rbtree::RBTree; 1781 let mut map = RBTree::new(); 1782 1783 map.insert(1, 2); 1784 map.insert(2, 1); 1785 map.insert(3, 4); 1786 1787 assert_eq!(map[&2], 1); 1788 } 1789 1790 #[test] 1791 #[should_panic] 1792 fn test_index_nonexistent() { 1793 use crate::libs::rbtree::RBTree; 1794 let mut map = RBTree::new(); 1795 1796 map.insert(1, 2); 1797 map.insert(2, 1); 1798 map.insert(3, 4); 1799 1800 map[&4]; 1801 } 1802 1803 #[test] 1804 fn test_extend_iter() { 1805 use crate::libs::rbtree::RBTree; 1806 let mut a = RBTree::new(); 1807 a.insert(1, "one"); 1808 let mut b = RBTree::new(); 1809 b.insert(2, "two"); 1810 b.insert(3, "three"); 1811 1812 a.extend(b.into_iter()); 1813 1814 assert_eq!(a.len(), 3); 1815 assert_eq!(a[&1], "one"); 1816 assert_eq!(a[&2], "two"); 1817 assert_eq!(a[&3], "three"); 1818 } 1819 1820 #[test] 1821 fn test_rev_iter() { 1822 let mut a = RBTree::new(); 1823 a.insert(1, 1); 1824 a.insert(2, 2); 1825 a.insert(3, 3); 1826 1827 assert_eq!(a.len(), 3); 1828 let mut cache = vec![]; 1829 for e in a.iter().rev() { 1830 cache.push(e.0.clone()); 1831 } 1832 assert_eq!(&cache, &vec![3, 2, 1]); 1833 } 1834 } 1835