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 /// # Examples 290 /// ```rust 291 /// use rbtree::RBTree; 292 /// // type inference lets us omit an explicit type signature (which 293 /// // would be `RBTree<&str, &str>` in this example). 294 /// let mut book_reviews = RBTree::new(); 295 /// 296 /// // review some books. 297 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book."); 298 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece."); 299 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable."); 300 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot."); 301 /// 302 /// // check for a specific one. 303 /// if !book_reviews.contains_key(&"Les Misérables") { 304 /// debug!( 305 /// "We've got {} reviews, but Les Misérables ain't one.", 306 /// book_reviews.len() 307 /// ); 308 /// } 309 /// 310 /// // oops, this review has a lot of spelling mistakes, let's delete it. 311 /// book_reviews.remove(&"The Adventures of Sherlock Holmes"); 312 /// 313 /// // look up the values associated with some keys. 314 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; 315 /// for book in &to_find { 316 /// match book_reviews.get(book) { 317 /// Some(review) => debug!("{}: {}", book, review), 318 /// None => debug!("{} is unreviewed.", book), 319 /// } 320 /// } 321 /// 322 /// // iterate over everything. 323 /// for (book, review) in book_reviews.iter() { 324 /// debug!("{}: \"{}\"", book, review); 325 /// } 326 /// 327 /// book_reviews.print_tree(); 328 /// ``` 329 /// 330 /// // A `RBTree` with fixed list of elements can be initialized from an array: 331 /// ``` 332 /// use rbtree::RBTree; 333 /// let timber_resources: RBTree<&str, i32> = 334 /// [("Norway", 100), 335 /// ("Denmark", 50), 336 /// ("Iceland", 10)] 337 /// .iter().cloned().collect(); 338 /// // use the values stored in rbtree 339 /// ``` 340 pub struct RBTree<K: Ord + Debug, V: Debug> { 341 root: NodePtr<K, V>, 342 len: usize, 343 } 344 345 unsafe impl<K: Ord + Debug, V: Debug> Send for RBTree<K, V> {} 346 unsafe impl<K: Ord + Debug, V: Debug> Sync for RBTree<K, V> {} 347 348 // Drop all owned pointers if the tree is dropped 349 impl<K: Ord + Debug, V: Debug> Drop for RBTree<K, V> { 350 #[inline] drop(&mut self)351 fn drop(&mut self) { 352 self.clear(); 353 } 354 } 355 356 /// If key and value are both impl Clone, we can call clone to get a copy. 357 impl<K: Ord + Clone + Debug, V: Clone + Debug> Clone for RBTree<K, V> { clone(&self) -> RBTree<K, V>358 fn clone(&self) -> RBTree<K, V> { 359 unsafe { 360 let mut new = RBTree::new(); 361 new.root = self.root.deep_clone(); 362 new.len = self.len; 363 new 364 } 365 } 366 } 367 368 impl<K, V> Debug for RBTree<K, V> 369 where 370 K: Ord + Debug, 371 V: Debug, 372 { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result373 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 374 f.debug_map().entries(self.iter()).finish() 375 } 376 } 377 378 /// This is a method to help us to get inner struct. 379 impl<K: Ord + Debug, V: Debug> RBTree<K, V> { 380 #[allow(clippy::only_used_in_recursion)] tree_print(&self, node: NodePtr<K, V>, direction: i32)381 fn tree_print(&self, node: NodePtr<K, V>, direction: i32) { 382 if node.is_null() { 383 return; 384 } 385 if direction == 0 { 386 unsafe { 387 debug!("'{:?}' is root node", (*node.0)); 388 } 389 } else { 390 let direct = if direction == -1 { "left" } else { "right" }; 391 unsafe { 392 debug!( 393 "{:?} is {:?}'s {:?} child ", 394 (*node.0), 395 *node.parent().0, 396 direct 397 ); 398 } 399 } 400 self.tree_print(node.left(), -1); 401 self.tree_print(node.right(), 1); 402 } 403 print_tree(&self)404 pub fn print_tree(&self) { 405 if self.root.is_null() { 406 debug!("This is a empty tree"); 407 return; 408 } 409 debug!("This tree size = {:?}, begin:-------------", self.len()); 410 self.tree_print(self.root, 0); 411 debug!("end--------------------------"); 412 } 413 } 414 415 /// all key be same, but it has multi key, if has multi key, it perhaps no correct 416 impl<K, V> PartialEq for RBTree<K, V> 417 where 418 K: Eq + Ord + Debug, 419 V: PartialEq + Debug, 420 { eq(&self, other: &RBTree<K, V>) -> bool421 fn eq(&self, other: &RBTree<K, V>) -> bool { 422 if self.len() != other.len() { 423 return false; 424 } 425 426 self.iter() 427 .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) 428 } 429 } 430 431 impl<K: Eq + Ord + Debug, V: Eq + Debug> Eq for RBTree<K, V> {} 432 433 impl<K: Ord + Debug, V: Debug> Index<&K> for RBTree<K, V> { 434 type Output = V; 435 436 #[inline] index(&self, index: &K) -> &V437 fn index(&self, index: &K) -> &V { 438 self.get(index).expect("no entry found for key") 439 } 440 } 441 442 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>443 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> RBTree<K, V> { 444 let mut tree = RBTree::new(); 445 tree.extend(iter); 446 tree 447 } 448 } 449 450 /// RBTree into iter 451 impl<K: Ord + Debug, V: Debug> Extend<(K, V)> for RBTree<K, V> { extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)452 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { 453 let iter = iter.into_iter(); 454 for (k, v) in iter { 455 self.insert(k, v); 456 } 457 } 458 } 459 460 /// provide the rbtree all keys 461 /// # Examples 462 /// ``` 463 /// use rbtree::RBTree; 464 /// let mut m = RBTree::new(); 465 /// for i in 1..6 { 466 /// m.insert(i, i); 467 /// } 468 /// let vec = vec![1, 2, 3, 4, 5]; 469 /// let key_vec: Vec<_> = m.keys().cloned().collect(); 470 /// assert_eq!(vec, key_vec); 471 /// ``` 472 pub struct Keys<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 473 inner: Iter<'a, K, V>, 474 } 475 476 impl<'a, K: Ord + Debug, V: Debug> Clone for Keys<'a, K, V> { clone(&self) -> Keys<'a, K, V>477 fn clone(&self) -> Keys<'a, K, V> { 478 Keys { 479 inner: self.inner.clone(), 480 } 481 } 482 } 483 484 impl<K: Ord + Debug, V: Debug> fmt::Debug for Keys<'_, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result485 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 486 f.debug_list().entries(self.clone()).finish() 487 } 488 } 489 490 impl<'a, K: Ord + Debug, V: Debug> Iterator for Keys<'a, K, V> { 491 type Item = &'a K; 492 493 #[inline] next(&mut self) -> Option<&'a K>494 fn next(&mut self) -> Option<&'a K> { 495 self.inner.next().map(|(k, _)| k) 496 } 497 498 #[inline] size_hint(&self) -> (usize, Option<usize>)499 fn size_hint(&self) -> (usize, Option<usize>) { 500 self.inner.size_hint() 501 } 502 } 503 504 /// provide the rbtree all values order by key 505 /// # Examples 506 /// ``` 507 /// use rbtree::RBTree; 508 /// let mut m = RBTree::new(); 509 /// m.insert(2, 5); 510 /// m.insert(1, 6); 511 /// m.insert(3, 8); 512 /// m.insert(4, 9); 513 /// let vec = vec![6, 5, 8, 9]; 514 /// let key_vec: Vec<_> = m.values().cloned().collect(); 515 /// assert_eq!(vec, key_vec); 516 /// ``` 517 pub struct Values<'a, K: Ord + Debug, V: Debug> { 518 inner: Iter<'a, K, V>, 519 } 520 521 impl<'a, K: Ord + Debug, V: Debug> Clone for Values<'a, K, V> { clone(&self) -> Values<'a, K, V>522 fn clone(&self) -> Values<'a, K, V> { 523 Values { 524 inner: self.inner.clone(), 525 } 526 } 527 } 528 529 impl<K: Ord + Debug, V: Debug> fmt::Debug for Values<'_, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result530 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 531 f.debug_list().entries(self.clone()).finish() 532 } 533 } 534 535 impl<'a, K: Ord + Debug, V: Debug> Iterator for Values<'a, K, V> { 536 type Item = &'a V; 537 538 #[inline] next(&mut self) -> Option<&'a V>539 fn next(&mut self) -> Option<&'a V> { 540 self.inner.next().map(|(_, v)| v) 541 } 542 543 #[inline] size_hint(&self) -> (usize, Option<usize>)544 fn size_hint(&self) -> (usize, Option<usize>) { 545 self.inner.size_hint() 546 } 547 } 548 549 /// provide the rbtree all values and it can be modify 550 /// # Examples 551 /// ``` 552 /// use rbtree::RBTree; 553 /// let mut m = RBTree::new(); 554 /// for i in 0..32 { 555 /// m.insert(i, i); 556 /// } 557 /// assert_eq!(m.len(), 32); 558 /// for v in m.values_mut() { 559 /// *v *= 2; 560 /// } 561 /// for i in 0..32 { 562 /// assert_eq!(m.get(&i).unwrap(), &(i * 2)); 563 /// } 564 /// ``` 565 pub struct ValuesMut<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 566 inner: IterMut<'a, K, V>, 567 } 568 569 impl<'a, K: Ord + Debug, V: Debug> Clone for ValuesMut<'a, K, V> { clone(&self) -> ValuesMut<'a, K, V>570 fn clone(&self) -> ValuesMut<'a, K, V> { 571 ValuesMut { 572 inner: self.inner.clone(), 573 } 574 } 575 } 576 577 impl<K: Ord + Debug, V: Debug> fmt::Debug for ValuesMut<'_, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result578 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 579 f.debug_list().entries(self.clone()).finish() 580 } 581 } 582 583 impl<'a, K: Ord + Debug, V: Debug> Iterator for ValuesMut<'a, K, V> { 584 type Item = &'a mut V; 585 586 #[inline] next(&mut self) -> Option<&'a mut V>587 fn next(&mut self) -> Option<&'a mut V> { 588 self.inner.next().map(|(_, v)| v) 589 } 590 591 #[inline] size_hint(&self) -> (usize, Option<usize>)592 fn size_hint(&self) -> (usize, Option<usize>) { 593 self.inner.size_hint() 594 } 595 } 596 597 /// Convert RBTree to iter, move out the tree. 598 pub struct IntoIter<K: Ord + Debug, V: Debug> { 599 head: NodePtr<K, V>, 600 tail: NodePtr<K, V>, 601 len: usize, 602 } 603 604 // Drop all owned pointers if the collection is dropped 605 impl<K: Ord + Debug, V: Debug> Drop for IntoIter<K, V> { 606 #[inline] drop(&mut self)607 fn drop(&mut self) { 608 for (_, _) in self {} 609 } 610 } 611 612 impl<K: Ord + Debug, V: Debug> Iterator for IntoIter<K, V> { 613 type Item = (K, V); 614 next(&mut self) -> Option<(K, V)>615 fn next(&mut self) -> Option<(K, V)> { 616 if self.len == 0 { 617 return None; 618 } 619 620 if self.head.is_null() { 621 return None; 622 } 623 624 let next = self.head.next(); 625 let (k, v) = unsafe { 626 ( 627 core::ptr::read(&(*self.head.0).key), 628 core::ptr::read(&(*self.head.0).value), 629 ) 630 }; 631 self.head = next; 632 self.len -= 1; 633 Some((k, v)) 634 } 635 size_hint(&self) -> (usize, Option<usize>)636 fn size_hint(&self) -> (usize, Option<usize>) { 637 (self.len, Some(self.len)) 638 } 639 } 640 641 impl<K: Ord + Debug, V: Debug> DoubleEndedIterator for IntoIter<K, V> { 642 #[inline] next_back(&mut self) -> Option<(K, V)>643 fn next_back(&mut self) -> Option<(K, V)> { 644 if self.len == 0 { 645 return None; 646 } 647 648 if self.tail.is_null() { 649 return None; 650 } 651 652 let prev = self.tail.prev(); 653 let obj = unsafe { Box::from_raw(self.tail.0) }; 654 let (k, v) = obj.pair(); 655 self.tail = prev; 656 self.len -= 1; 657 Some((k, v)) 658 } 659 } 660 661 /// provide iter ref for RBTree 662 /// # Examples 663 /// ``` 664 /// use rbtree::RBTree; 665 /// let mut m = RBTree::new(); 666 /// for i in 0..32 { 667 /// m.insert(i, i * 2); 668 /// } 669 /// assert_eq!(m.len(), 32); 670 /// let mut observed: u32 = 0; 671 /// for (k, v) in m.iter() { 672 /// assert_eq!(*v, *k * 2); 673 /// observed |= 1 << *k; 674 /// } 675 /// assert_eq!(observed, 0xFFFF_FFFF); 676 /// ``` 677 pub struct Iter<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 678 head: NodePtr<K, V>, 679 tail: NodePtr<K, V>, 680 len: usize, 681 _marker: marker::PhantomData<&'a ()>, 682 } 683 684 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Clone for Iter<'a, K, V> { clone(&self) -> Iter<'a, K, V>685 fn clone(&self) -> Iter<'a, K, V> { 686 Iter { 687 head: self.head, 688 tail: self.tail, 689 len: self.len, 690 _marker: self._marker, 691 } 692 } 693 } 694 695 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Iterator for Iter<'a, K, V> { 696 type Item = (&'a K, &'a V); 697 next(&mut self) -> Option<(&'a K, &'a V)>698 fn next(&mut self) -> Option<(&'a K, &'a V)> { 699 if self.len == 0 { 700 return None; 701 } 702 703 if self.head.is_null() { 704 return None; 705 } 706 707 let (k, v) = unsafe { (&(*self.head.0).key, &(*self.head.0).value) }; 708 self.head = self.head.next(); 709 self.len -= 1; 710 Some((k, v)) 711 } 712 size_hint(&self) -> (usize, Option<usize>)713 fn size_hint(&self) -> (usize, Option<usize>) { 714 (self.len, Some(self.len)) 715 } 716 } 717 718 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> DoubleEndedIterator for Iter<'a, K, V> { 719 #[inline] next_back(&mut self) -> Option<(&'a K, &'a V)>720 fn next_back(&mut self) -> Option<(&'a K, &'a V)> { 721 // debug!("len = {:?}", self.len); 722 if self.len == 0 { 723 return None; 724 } 725 726 let (k, v) = unsafe { (&(*self.tail.0).key, &(*self.tail.0).value) }; 727 self.tail = self.tail.prev(); 728 self.len -= 1; 729 Some((k, v)) 730 } 731 } 732 733 /// provide iter mut ref for RBTree 734 /// # Examples 735 /// ``` 736 /// use rbtree::RBTree; 737 /// let mut m = RBTree::new(); 738 /// for i in 0..32 { 739 /// m.insert(i, i); 740 /// } 741 /// assert_eq!(m.len(), 32); 742 /// for (_, v) in m.iter_mut() { 743 /// *v *= 2; 744 /// } 745 /// for i in 0..32 { 746 /// assert_eq!(m.get(&i).unwrap(), &(i * 2)); 747 /// } 748 /// ``` 749 pub struct IterMut<'a, K: Ord + Debug + 'a, V: Debug + 'a> { 750 head: NodePtr<K, V>, 751 tail: NodePtr<K, V>, 752 len: usize, 753 _marker: marker::PhantomData<&'a ()>, 754 } 755 756 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Clone for IterMut<'a, K, V> { clone(&self) -> IterMut<'a, K, V>757 fn clone(&self) -> IterMut<'a, K, V> { 758 IterMut { 759 head: self.head, 760 tail: self.tail, 761 len: self.len, 762 _marker: self._marker, 763 } 764 } 765 } 766 767 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> Iterator for IterMut<'a, K, V> { 768 type Item = (&'a K, &'a mut V); 769 next(&mut self) -> Option<(&'a K, &'a mut V)>770 fn next(&mut self) -> Option<(&'a K, &'a mut V)> { 771 if self.len == 0 { 772 return None; 773 } 774 775 if self.head.is_null() { 776 return None; 777 } 778 779 let (k, v) = unsafe { (&(*self.head.0).key, &mut (*self.head.0).value) }; 780 self.head = self.head.next(); 781 self.len -= 1; 782 Some((k, v)) 783 } 784 size_hint(&self) -> (usize, Option<usize>)785 fn size_hint(&self) -> (usize, Option<usize>) { 786 (self.len, Some(self.len)) 787 } 788 } 789 790 impl<'a, K: Ord + Debug + 'a, V: Debug + 'a> DoubleEndedIterator for IterMut<'a, K, V> { 791 #[inline] next_back(&mut self) -> Option<(&'a K, &'a mut V)>792 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { 793 if self.len == 0 { 794 return None; 795 } 796 797 if self.tail == self.head { 798 return None; 799 } 800 801 let (k, v) = unsafe { (&(*self.tail.0).key, &mut (*self.tail.0).value) }; 802 self.tail = self.tail.prev(); 803 self.len -= 1; 804 Some((k, v)) 805 } 806 } 807 808 impl<K: Ord + Debug, V: Debug> IntoIterator for RBTree<K, V> { 809 type Item = (K, V); 810 type IntoIter = IntoIter<K, V>; 811 812 #[inline] into_iter(mut self) -> IntoIter<K, V>813 fn into_iter(mut self) -> IntoIter<K, V> { 814 let iter = if self.root.is_null() { 815 IntoIter { 816 head: NodePtr::null(), 817 tail: NodePtr::null(), 818 len: self.len, 819 } 820 } else { 821 IntoIter { 822 head: self.first_child(), 823 tail: self.last_child(), 824 len: self.len, 825 } 826 }; 827 self.fast_clear(); 828 iter 829 } 830 } 831 832 impl<K: Ord + Debug, V: Debug> RBTree<K, V> { 833 /// Creates an empty `RBTree`. new() -> RBTree<K, V>834 pub fn new() -> RBTree<K, V> { 835 RBTree { 836 root: NodePtr::null(), 837 len: 0, 838 } 839 } 840 841 /// Returns the len of `RBTree`. 842 #[inline] len(&self) -> usize843 pub fn len(&self) -> usize { 844 self.len 845 } 846 847 /// Returns `true` if the `RBTree` is empty. 848 #[inline] is_empty(&self) -> bool849 pub fn is_empty(&self) -> bool { 850 self.root.is_null() 851 } 852 853 /* 854 * 对红黑树的节点(x)进行左旋转 855 * 856 * 左旋示意图(对节点x进行左旋)： 857 * px px 858 * / / 859 * x y 860 * / \ --(左旋)--> / \ # 861 * lx y x ry 862 * / \ / \ 863 * ly ry lx ly 864 * 865 * 866 */ 867 #[inline] left_rotate(&mut self, mut node: NodePtr<K, V>)868 unsafe fn left_rotate(&mut self, mut node: NodePtr<K, V>) { 869 let mut temp = node.right(); 870 node.set_right(temp.left()); 871 872 if !temp.left().is_null() { 873 temp.left().set_parent(node); 874 } 875 876 temp.set_parent(node.parent()); 877 if node == self.root { 878 self.root = temp; 879 } else if node == node.parent().left() { 880 node.parent().set_left(temp); 881 } else { 882 node.parent().set_right(temp); 883 } 884 885 temp.set_left(node); 886 node.set_parent(temp); 887 } 888 889 /* 890 * 对红黑树的节点(y)进行右旋转 891 * 892 * 右旋示意图(对节点y进行左旋)： 893 * py py 894 * / / 895 * y x 896 * / \ --(右旋)--> / \ # 897 * x ry lx y 898 * / \ / \ # 899 * lx rx rx ry 900 * 901 */ 902 #[inline] right_rotate(&mut self, mut node: NodePtr<K, V>)903 unsafe fn right_rotate(&mut self, mut node: NodePtr<K, V>) { 904 let mut temp = node.left(); 905 node.set_left(temp.right()); 906 907 if !temp.right().is_null() { 908 temp.right().set_parent(node); 909 } 910 911 temp.set_parent(node.parent()); 912 if node == self.root { 913 self.root = temp; 914 } else if node == node.parent().right() { 915 node.parent().set_right(temp); 916 } else { 917 node.parent().set_left(temp); 918 } 919 920 temp.set_right(node); 921 node.set_parent(temp); 922 } 923 924 /// replace value if key exist, if not exist insert it. 925 /// # Examples 926 /// ``` 927 /// use rbtree::RBTree; 928 /// let mut m = RBTree::new(); 929 /// assert_eq!(m.len(), 0); 930 /// m.insert(2, 4); 931 /// assert_eq!(m.len(), 1); 932 /// assert_eq!(m.replace_or_insert(2, 6).unwrap(), 4); 933 /// assert_eq!(m.len(), 1); 934 /// assert_eq!(*m.get(&2).unwrap(), 6); 935 /// ``` 936 #[inline] replace_or_insert(&mut self, k: K, mut v: V) -> Option<V>937 pub fn replace_or_insert(&mut self, k: K, mut v: V) -> Option<V> { 938 let node = self.find_node(&k); 939 if node.is_null() { 940 self.insert(k, v); 941 return None; 942 } 943 944 unsafe { 945 mem::swap(&mut v, &mut (*node.0).value); 946 } 947 948 Some(v) 949 } 950 951 #[inline] insert_fixup(&mut self, mut node: NodePtr<K, V>)952 unsafe fn insert_fixup(&mut self, mut node: NodePtr<K, V>) { 953 let mut parent; 954 let mut gparent; 955 956 while node.parent().is_red_color() { 957 parent = node.parent(); 958 gparent = parent.parent(); 959 //若“父节点”是“祖父节点的左孩子” 960 if parent == gparent.left() { 961 // Case 1条件：叔叔节点是红色 962 let mut uncle = gparent.right(); 963 if !uncle.is_null() && uncle.is_red_color() { 964 uncle.set_black_color(); 965 parent.set_black_color(); 966 gparent.set_red_color(); 967 node = gparent; 968 continue; 969 } 970 971 // Case 2条件：叔叔是黑色，且当前节点是右孩子 972 if parent.right() == node { 973 self.left_rotate(parent); 974 swap(&mut parent, &mut node); 975 } 976 977 // Case 3条件：叔叔是黑色，且当前节点是左孩子。 978 parent.set_black_color(); 979 gparent.set_red_color(); 980 self.right_rotate(gparent); 981 } else { 982 // Case 1条件：叔叔节点是红色 983 let mut uncle = gparent.left(); 984 if !uncle.is_null() && uncle.is_red_color() { 985 uncle.set_black_color(); 986 parent.set_black_color(); 987 gparent.set_red_color(); 988 node = gparent; 989 continue; 990 } 991 992 // Case 2条件：叔叔是黑色，且当前节点是右孩子 993 if parent.left() == node { 994 self.right_rotate(parent); 995 swap(&mut parent, &mut node); 996 } 997 998 // Case 3条件：叔叔是黑色，且当前节点是左孩子。 999 parent.set_black_color(); 1000 gparent.set_red_color(); 1001 self.left_rotate(gparent); 1002 } 1003 } 1004 self.root.set_black_color(); 1005 } 1006 1007 #[inline] insert(&mut self, k: K, v: V)1008 pub fn insert(&mut self, k: K, v: V) { 1009 self.len += 1; 1010 let mut node = NodePtr::new(k, v); 1011 let mut y = NodePtr::null(); 1012 let mut x = self.root; 1013 1014 while !x.is_null() { 1015 y = x; 1016 match node.cmp(&x) { 1017 Ordering::Less => { 1018 x = x.left(); 1019 } 1020 _ => { 1021 x = x.right(); 1022 } 1023 }; 1024 } 1025 node.set_parent(y); 1026 1027 if y.is_null() { 1028 self.root = node; 1029 } else { 1030 match node.cmp(&y) { 1031 Ordering::Less => { 1032 y.set_left(node); 1033 } 1034 _ => { 1035 y.set_right(node); 1036 } 1037 }; 1038 } 1039 1040 node.set_red_color(); 1041 unsafe { 1042 self.insert_fixup(node); 1043 } 1044 } 1045 1046 #[inline] find_node(&self, k: &K) -> NodePtr<K, V>1047 fn find_node(&self, k: &K) -> NodePtr<K, V> { 1048 if self.root.is_null() { 1049 return NodePtr::null(); 1050 } 1051 let mut temp = &self.root; 1052 unsafe { 1053 loop { 1054 let next = match k.cmp(&(*temp.0).key) { 1055 Ordering::Less => &mut (*temp.0).left, 1056 Ordering::Greater => &mut (*temp.0).right, 1057 Ordering::Equal => return *temp, 1058 }; 1059 if next.is_null() { 1060 break; 1061 } 1062 temp = next; 1063 } 1064 } 1065 NodePtr::null() 1066 } 1067 1068 #[inline] first_child(&self) -> NodePtr<K, V>1069 fn first_child(&self) -> NodePtr<K, V> { 1070 if self.root.is_null() { 1071 NodePtr::null() 1072 } else { 1073 let mut temp = self.root; 1074 while !temp.left().is_null() { 1075 temp = temp.left(); 1076 } 1077 return temp; 1078 } 1079 } 1080 1081 #[inline] last_child(&self) -> NodePtr<K, V>1082 fn last_child(&self) -> NodePtr<K, V> { 1083 if self.root.is_null() { 1084 NodePtr::null() 1085 } else { 1086 let mut temp = self.root; 1087 while !temp.right().is_null() { 1088 temp = temp.right(); 1089 } 1090 return temp; 1091 } 1092 } 1093 1094 #[inline] get_first(&self) -> Option<(&K, &V)>1095 pub fn get_first(&self) -> Option<(&K, &V)> { 1096 let first = self.first_child(); 1097 if first.is_null() { 1098 return None; 1099 } 1100 unsafe { Some((&(*first.0).key, &(*first.0).value)) } 1101 } 1102 1103 #[inline] get_last(&self) -> Option<(&K, &V)>1104 pub fn get_last(&self) -> Option<(&K, &V)> { 1105 let last = self.last_child(); 1106 if last.is_null() { 1107 return None; 1108 } 1109 unsafe { Some((&(*last.0).key, &(*last.0).value)) } 1110 } 1111 1112 #[inline] pop_first(&mut self) -> Option<(K, V)>1113 pub fn pop_first(&mut self) -> Option<(K, V)> { 1114 let first = self.first_child(); 1115 if first.is_null() { 1116 return None; 1117 } 1118 unsafe { Some(self.delete(first)) } 1119 } 1120 1121 #[inline] pop_last(&mut self) -> Option<(K, V)>1122 pub fn pop_last(&mut self) -> Option<(K, V)> { 1123 let last = self.last_child(); 1124 if last.is_null() { 1125 return None; 1126 } 1127 unsafe { Some(self.delete(last)) } 1128 } 1129 1130 #[inline] get_first_mut(&mut self) -> Option<(&K, &mut V)>1131 pub fn get_first_mut(&mut self) -> Option<(&K, &mut V)> { 1132 let first = self.first_child(); 1133 if first.is_null() { 1134 return None; 1135 } 1136 unsafe { Some((&(*first.0).key, &mut (*first.0).value)) } 1137 } 1138 1139 #[inline] get_last_mut(&mut self) -> Option<(&K, &mut V)>1140 pub fn get_last_mut(&mut self) -> Option<(&K, &mut V)> { 1141 let last = self.last_child(); 1142 if last.is_null() { 1143 return None; 1144 } 1145 unsafe { Some((&(*last.0).key, &mut (*last.0).value)) } 1146 } 1147 1148 #[inline] get(&self, k: &K) -> Option<&V>1149 pub fn get(&self, k: &K) -> Option<&V> { 1150 let node = self.find_node(k); 1151 if node.is_null() { 1152 return None; 1153 } 1154 1155 unsafe { Some(&(*node.0).value) } 1156 } 1157 1158 #[inline] get_mut(&mut self, k: &K) -> Option<&mut V>1159 pub fn get_mut(&mut self, k: &K) -> Option<&mut V> { 1160 let node = self.find_node(k); 1161 if node.is_null() { 1162 return None; 1163 } 1164 1165 unsafe { Some(&mut (*node.0).value) } 1166 } 1167 1168 #[inline] contains_key(&self, k: &K) -> bool1169 pub fn contains_key(&self, k: &K) -> bool { 1170 let node = self.find_node(k); 1171 if node.is_null() { 1172 return false; 1173 } 1174 true 1175 } 1176 1177 #[allow(clippy::only_used_in_recursion)] 1178 #[inline] clear_recurse(&mut self, current: NodePtr<K, V>)1179 fn clear_recurse(&mut self, current: NodePtr<K, V>) { 1180 if !current.is_null() { 1181 unsafe { 1182 self.clear_recurse(current.left()); 1183 self.clear_recurse(current.right()); 1184 drop(Box::from_raw(current.0)); 1185 } 1186 } 1187 } 1188 1189 /// clear all red back tree elements. 1190 /// # Examples 1191 /// ``` 1192 /// use rbtree::RBTree; 1193 /// let mut m = RBTree::new(); 1194 /// for i in 0..6 { 1195 /// m.insert(i, i); 1196 /// } 1197 /// assert_eq!(m.len(), 6); 1198 /// m.clear(); 1199 /// assert_eq!(m.len(), 0); 1200 /// ``` 1201 #[inline] clear(&mut self)1202 pub fn clear(&mut self) { 1203 let root = self.root; 1204 self.root = NodePtr::null(); 1205 self.clear_recurse(root); 1206 self.len = 0; 1207 } 1208 1209 /// Empties the `RBTree` without freeing objects in it. 1210 #[inline] fast_clear(&mut self)1211 fn fast_clear(&mut self) { 1212 self.root = NodePtr::null(); 1213 self.len = 0; 1214 } 1215 1216 #[inline] remove(&mut self, k: &K) -> Option<V>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] delete_fixup(&mut self, mut node: NodePtr<K, V>, mut parent: NodePtr<K, V>)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] delete(&mut self, node: NodePtr<K, V>) -> (K, V)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] keys(&self) -> Keys<K, V>1376 pub fn keys(&self) -> Keys<K, V> { 1377 Keys { inner: self.iter() } 1378 } 1379 1380 /// Return the value iter 1381 #[inline] values(&self) -> Values<K, V>1382 pub fn values(&self) -> Values<K, V> { 1383 Values { inner: self.iter() } 1384 } 1385 1386 /// Return the value iter mut 1387 #[inline] values_mut(&mut self) -> ValuesMut<K, V>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] iter(&self) -> Iter<K, V>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] iter_mut(&mut self) -> IterMut<K, V>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] test_insert()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] test_replace()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] test_clone()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] test_empty_remove()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] test_empty_iter()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] test_lots_of_insertions()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] test_find_mut()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] test_remove()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] test_is_empty()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] test_pop()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] test_iterate()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] test_keys()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] test_values()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] test_values_mut()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 *= 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] test_find()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] test_eq()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] test_show()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] test_from_iter()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] test_size_hint()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] test_iter_len()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] test_mut_size_hint()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] test_iter_mut_len()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] test_index()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] test_index_nonexistent()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] test_extend_iter()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); 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 #[test] test_rev_iter()1819 fn test_rev_iter() { 1820 use crate::libs::rbtree::RBTree; 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); 1830 } 1831 assert_eq!(&cache, &vec![3, 2, 1]); 1832 } 1833 } 1834