bin_tree/
lib.rs

1//! Building a binary tree from an iterator.
2//!
3//! # Examples
4//!
5//! ```
6//! use bin_tree::{IteratorEx, Node};
7//!
8//! #[derive(Clone, Default, PartialEq, Eq, Debug)]
9//! struct NodeStr(String);
10//!
11//! impl Node for NodeStr {
12//!     fn new_parent(self, right: Self) -> Self {
13//!         Self("[".to_owned() + &self.0 + ", " + &right.0 + "]")
14//!     }
15//!     fn new_parent_from_single(self) -> Self {
16//!         self
17//!     }
18//! }
19//!
20//! let x = (0..10).map(|v| NodeStr(v.to_string())).build_tree();
21//! assert_eq!(x, Some(NodeStr("[[[[0, 1], [2, 3]], [[4, 5], [6, 7]]], [8, 9]]".to_string())));
22//! ```
23
24#![no_std]
25extern crate alloc;
26
27use build_tree_state::BuildTreeState;
28pub use node::Node;
29use vec_stack::VecStack;
30
31mod build_tree_state;
32mod node;
33mod stack;
34mod vec_stack;
35
36/// The trait extends the functionality of the standard `Iterator` trait by adding
37/// the `build_tree` method.
38pub trait IteratorEx: Iterator + Sized
39where
40    Self::Item: Node,
41{
42    /// Builds a binary tree from an iterator of Nodes
43    ///
44    /// # Arguments
45    ///
46    /// * self - the iterator of Nodes to build the tree from
47    ///
48    /// # Return
49    ///
50    /// The root node of the built tree, if it was successfully built.
51    fn build_tree(self) -> Option<Self::Item> {
52        let state = BuildTreeState::<VecStack<_>>::new(&self);
53        self.fold(state, BuildTreeState::fold_op).collect()
54    }
55}
56
57impl<T: Iterator> IteratorEx for T where T::Item: Node {}
58
59#[cfg(test)]
60mod tests {
61    use alloc::boxed::Box;
62
63    use super::*;
64
65    #[derive(Clone, Default, PartialEq, Eq, Debug)]
66    struct Sum(usize);
67
68    impl Node for Sum {
69        fn new_parent(self, right: Self) -> Self {
70            Sum(self.0 + right.0)
71        }
72
73        fn new_parent_from_single(self) -> Self {
74            self
75        }
76    }
77
78    #[test]
79    fn sum() {
80        let x = (0..10).map(|v| Sum(v)).build_tree();
81        assert_eq!(x, Some(Sum(45)));
82    }
83
84    struct NodeContent {
85        value: usize,
86        children: Option<(NodeRef, NodeRef)>,
87    }
88
89    type NodeRef = Box<NodeContent>;
90
91    fn leaf(value: usize) -> NodeRef {
92        Box::new(NodeContent {
93            value,
94            children: None,
95        })
96    }
97
98    impl Node for NodeRef {
99        fn new_parent(self, right: Self) -> Self {
100            let value = self.value + right.value;
101            Box::new(NodeContent {
102                value,
103                children: Some((self, right)),
104            })
105        }
106
107        fn new_parent_from_single(self) -> Self {
108            self
109        }
110    }
111
112    #[test]
113    fn node() {
114        let root = (0..11).map(leaf).build_tree().unwrap();
115        assert_eq!(55, root.value);
116        // [0..7],[8..10]
117        let (n0, n1) = root.children.unwrap();
118        assert_eq!(28, n0.value);
119        assert_eq!(27, n1.value);
120        // [0..3],[4..7]
121        {
122            let (n00, n01) = n0.children.unwrap();
123            assert_eq!(6, n00.value);
124            assert_eq!(22, n01.value);
125            // [0..1],[2..3]
126            {
127                let (n000, n001) = n00.children.unwrap();
128                assert_eq!(1, n000.value);
129                assert_eq!(5, n001.value);
130                // [0],[1]
131                {
132                    let (n0000, n0001) = n000.children.unwrap();
133                    assert_eq!(0, n0000.value);
134                    assert_eq!(1, n0001.value);
135                    assert!(n0000.children.is_none());
136                    assert!(n0001.children.is_none());
137                }
138                // [2],[3]
139                {
140                    let (n0010, n0011) = n001.children.unwrap();
141                    assert_eq!(2, n0010.value);
142                    assert_eq!(3, n0011.value);
143                    assert!(n0010.children.is_none());
144                    assert!(n0011.children.is_none());
145                }
146            }
147            // [4..5],[6..7]
148            {
149                let (n010, n011) = n01.children.unwrap();
150                assert_eq!(9, n010.value);
151                assert_eq!(13, n011.value);
152                // [4],[5]
153                {
154                    let (n0100, n0101) = n010.children.unwrap();
155                    assert_eq!(4, n0100.value);
156                    assert_eq!(5, n0101.value);
157                    assert!(n0100.children.is_none());
158                    assert!(n0101.children.is_none());
159                }
160                // [6],[7]
161                {
162                    let (n0110, n0111) = n011.children.unwrap();
163                    assert_eq!(6, n0110.value);
164                    assert_eq!(7, n0111.value);
165                    assert!(n0110.children.is_none());
166                    assert!(n0111.children.is_none());
167                }
168            }
169        }
170        // [8..9],[10]
171        {
172            let (n10, n11) = n1.children.unwrap();
173            assert_eq!(17, n10.value);
174            assert_eq!(10, n11.value);
175            assert!(n11.children.is_none());
176            // [8],[9]
177            {
178                let (n100, n101) = n10.children.unwrap();
179                assert_eq!(8, n100.value);
180                assert_eq!(9, n101.value);
181                assert!(n100.children.is_none());
182                assert!(n101.children.is_none());
183            }
184        }
185    }
186}
bin_tree/lib.rs

bin_tree/
lib.rs
