~nerosnm/advela

ref: 34c6397938bf13319ad5e711b9a107fd4006c2de advela/src/tree.rs -rw-r--r-- 4.4 KiB
34c63979Søren Mortensen Initial commit 1 year, 8 days ago
                                                                                
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
//! An AVL tree.

use std::iter::FromIterator;

use crate::node::AvlNode;

pub struct AvlTree<T>
where
    T: Ord,
{
    root: Option<AvlNode<T>>,
}

impl<T> AvlTree<T>
where
    T: Ord,
{
    /// Create a new, empty AVL tree.
    pub fn new() -> Self {
        Self::default()
    }

    /// Insert a value into the tree. Duplicate values will be ignored.
    ///
    /// If the insertion caused the tree to become unbalanced, it will be
    /// balanced afterwards.
    pub fn insert(&mut self, val: T) {
        if let Some(ref mut root) = self.root {
            root.insert(val);
        } else {
            self.root = Some(AvlNode::new(val));
        }
    }

    /// Insert all the values from the given iterator into the tree.
    ///
    /// If the insertions caused the tree to become unbalanced, it will be
    /// balanced after all of the insertions take place.
    pub fn insert_all<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T>,
    {
        for val in iter {
            self.insert(val);
        }
    }

    /// Return whether the given value is present in the tree.
    pub fn contains(&self, val: &T) -> bool {
        if let Some(ref root) = self.root {
            root.contains(val)
        } else {
            false
        }
    }
}

#[cfg(feature = "print")]
impl<T> AvlTree<T>
where
    T: Ord,
    T: std::fmt::Display,
{
    pub fn print(&self) -> String {
        self.root
            .as_ref()
            .map_or_else(|| "".to_string(), |root| root.print())
    }
}

#[cfg(test)]
impl AvlTree<usize> {
    /// Create a balanced test tree containing each of the values in the range
    /// `[1, 7]`.
    #[cfg(test)]
    pub fn test_tree() -> Self {
        use crate::node::AvlNodeBuilder;

        let two = AvlNodeBuilder::new(2).left(1).right(3).build();
        let six = AvlNodeBuilder::new(6).left(5).right(7).build();

        let mut root = AvlNode::new(4);
        root.set_left(two);
        root.set_right(six);

        Self { root: Some(root) }
    }
}

impl<T> Default for AvlTree<T>
where
    T: Ord,
{
    fn default() -> Self {
        Self { root: None }
    }
}

impl<T> FromIterator<T> for AvlTree<T>
where
    T: Ord,
{
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        iter.into_iter().fold(Self::default(), |mut acc, next| {
            acc.insert(next);
            acc
        })
    }
}

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

    /// Test that inserting a single value into an empty tree causes it to be
    /// correctly reported as contained in the tree afterwards.
    #[test]
    fn insert_into_empty() {
        let mut tree = AvlTree::new();
        assert!(!tree.contains(&42), "the tree should be empty");

        tree.insert(42);
        assert!(tree.contains(&42), "the value was not inserted correctly");
    }

    /// Test that inserting values into a tree causes them to be correctly
    /// reported as contained in the tree afterwards.
    #[test]
    fn insert() {
        let mut tree = AvlTree::new();

        for i in 0..10 {
            for j in i..10 {
                assert!(!tree.contains(&j), "{} should not yet be in the tree", j);
            }

            tree.insert(i);

            assert!(tree.contains(&i), "{} was not inserted correctly", i);
        }
    }

    /// Test that inserting an iterator full of values into a tree causes them
    /// to be correctly reported as contained in the tree afterwards.
    #[test]
    fn insert_all() {
        let mut tree = AvlTree::new();

        for i in 0..10 {
            assert!(!tree.contains(&i), "{} should not yet be in the tree", i);
        }

        tree.insert_all(0..10);

        for i in 0..10 {
            assert!(tree.contains(&i), "{} was not inserted correctly", i);
        }
    }

    /// Test that trees correctly report whether they contain values.
    #[test]
    fn contains() {
        let tree = AvlTree::test_tree();

        for i in 1..=7 {
            assert!(
                tree.contains(&i),
                "the value {} should have been reported as contained in the tree",
                i
            );
        }
    }

    /// Test that trees print in the expected format.
    #[test]
    #[cfg(feature = "print")]
    fn print() {
        let tree = AvlTree::test_tree();

        let actual = tree.print();
        let expected = "4\n  2\n    1\n    3\n  6\n    5\n    7\n";

        assert_eq!(actual, expected, "the tree did not format correctly");
    }
}