algorithm/tree/
rbtree.rs

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

algorithm/tree/
rbtree.rs
