binary-tree 0.0.1

Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#![feature(box_syntax)]

use std::ops::DerefMut;

pub mod cow;

/// Generic methods on binary trees. Calling any of these methods directly on a
/// self-balancing binary tree can make it imbalanced.
pub trait BinaryTree: Sized {
    type Subtree: Sized + DerefMut<Target=Self>;

    /// Try to detach the left sub-tree
    fn detach_left(&mut self) -> Option<Self::Subtree>;

    /// Try to detach the right sub-tree
    fn detach_right(&mut self) -> Option<Self::Subtree>;

    /// Replace the left subtree with `tree` and return the old one.
    fn insert_left(&mut self, tree: Option<Self::Subtree>) -> Option<Self::Subtree>;

    /// Replace the right subtree with `tree` and return the old one.
    fn insert_right(&mut self, tree: Option<Self::Subtree>) -> Option<Self::Subtree>;

    /// Consumes the tree, rotates it left if right subtree exists, otherwise
    /// returns the original with an error.
    fn rotate_left(mut this: Self::Subtree) -> Result<Self::Subtree, Self::Subtree> {
        if let Some(mut new_root) = this.detach_right() {
            let mid = new_root.detach_left();
            this.insert_right(mid);
            new_root.insert_left(Some(this));
            Ok(new_root)
        } else {
            Err(this)
        }
    }

    /// Consumes the tree, rotates it right if left subtree exists, otherwise
    /// returns the original with an error.
    fn rotate_right(mut this: Self::Subtree) -> Result<Self::Subtree, Self::Subtree> {
        if let Some(mut new_root) = this.detach_left() {
            let mid = new_root.detach_right();
            this.insert_left(mid);
            new_root.insert_right(Some(this));
            Ok(new_root)
        } else {
            Err(this)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::BinaryTree;

    #[derive(Debug)]
    struct TestTree {
        val: u32,
        left: Option<Box<TestTree>>,
        right: Option<Box<TestTree>>,
    }

    impl TestTree {
        fn new(val: u32) -> TestTree {
            TestTree {
                val: val,
                left: None,
                right: None,
            }
        }
    }

    impl BinaryTree for TestTree {
        type Subtree = Box<TestTree>;

        fn detach_left(&mut self) -> Option<Self::Subtree> {
            self.left.take()
        }
        fn detach_right(&mut self) -> Option<Self::Subtree> {
            self.right.take()
        }
        fn insert_left(&mut self, tree: Option<Self::Subtree>) -> Option<Self::Subtree> {
            let old = self.left.take();
            self.left = tree;
            old
        }
        fn insert_right(&mut self, tree: Option<Self::Subtree>) -> Option<Self::Subtree> {
            let old = self.right.take();
            self.right = tree;
            old
        }
    }

    #[test]
    fn rotate() {
        let mut tt = TestTree::new(20);
        tt.insert_left(Some(box TestTree::new(10)));
        let mut tt_r = TestTree::new(30);
        tt_r.insert_left(Some(box TestTree::new(25)));
        tt.insert_right(Some(box tt_r));

        let tt_lrot: Box<TestTree> = TestTree::rotate_left(box tt).unwrap();
        assert_eq!(tt_lrot.val,                         30);
        assert_eq!(tt_lrot.left.as_ref().unwrap().val,  20);
        assert_eq!(tt_lrot.left.as_ref().unwrap()
                          .left.as_ref().unwrap().val,  10);
        assert_eq!(tt_lrot.left.as_ref().unwrap()
                          .right.as_ref().unwrap().val, 25);

        let tt: Box<TestTree> = TestTree::rotate_right(tt_lrot).unwrap();
        assert_eq!(tt.val,                         20);
        assert_eq!(tt.left.as_ref().unwrap().val,  10);
        assert_eq!(tt.right.as_ref().unwrap().val, 30);
        assert_eq!(tt.right.as_ref().unwrap()
                     .left.as_ref().unwrap().val,  25);
    }
}