flange_flat_tree/tree/
tree_trait.rs

1use crate::navigator::Navigator;
2use crate::{FlangedTree, Subtree};
3
4use super::tree_data::TreeData;
5use super::MappedTree;
6
7/**
8Trait for everything that can be handled as a tree.
9*/
10pub trait Tree<'a>: Sized
11where
12    Self: 'a,
13    &'a Self: TreeData<Node = Self::Node>,
14{
15    /// The type of the trees nodes
16    type Node;
17    /// The type of the subtree, returned by `root()`
18    type SubtreeType: Subtree<Node = Self::Node>;
19
20    /// Direct access to a node in the tree via its position in the flat map
21    fn at_pos(&'a self, index: usize) -> Self::SubtreeType;
22
23    /// Direct access to the `Navigator` storing the neighboring information of the tree
24    fn get_nav(&self) -> &Navigator;
25
26    /// The root node of the tree.
27    fn root(&'a self) -> Self::SubtreeType {
28        self.at_pos(0)
29    }
30
31    /// The number of nodes in the tree.
32    fn node_count(&'a self) -> usize {
33        self.count()
34    }
35
36    /** Create a new tree using a function to map from the nodes of this tree.
37    The map function can also include external data sources.
38
39    # Example
40    ```
41    use flange_flat_tree::{Builder, Tree, Subtree};
42
43    let mut builder = Builder::with_capacity(2);
44    builder.start_element("one");
45    builder.start_end_element("two");
46    builder.end_element();
47    let tree = builder.build();
48
49    struct FlangedNode<'a> {
50        pub name: &'a str,
51        pub value: u32, // we don't use a reference for u32, because copying the value itself is fine
52    }
53
54    // The data we are going to flange
55    let data: Vec<u32> = vec![1,2];
56
57    let tree_with_values = tree.map(
58        |i,v| FlangedNode {
59            name: v,
60            value: data[i],
61        }
62    );
63
64    assert_eq!(tree_with_values.root().value().name, "one");
65    assert_eq!(tree_with_values.root().value().value, 1);
66    ```
67    */
68    fn map<B, M>(&'a self, m: M) -> MappedTree<Self::Node, B, M, &'a Self>
69    where
70        M: Fn(usize, Self::Node) -> B,
71    {
72        MappedTree::new(self, m)
73    }
74
75    /** Flange data to the nodes.
76    A new tree is created, that references the old tree and whos
77    `Node` type is a typle with a reference to the old data
78    and a reference to the new data from the inserted `data` vector.
79    */
80    fn flange<B>(&'a self, data: Vec<B>) -> FlangedTree<&'a Self, B> {
81        FlangedTree::new(self, data)
82    }
83
84    /** Use `flange`, but create the data using the `mapf` function*/
85    fn flange_map<B, F>(&'a self, mapf: F) -> FlangedTree<&'a Self, B>
86    where
87        B: 'a,
88        B: Clone,
89        F: Fn(Self::Node) -> B,
90    {
91        let mut res = Vec::with_capacity(self.node_count());
92
93        for index in 0..self.count() {
94            let new_val = mapf(self.get(index));
95            res.push(new_val);
96        }
97        FlangedTree::new(self, res)
98    }
99
100    fn for_each<F>(&'a self, mut f: F)
101    where
102        F: FnMut(Self::SubtreeType),
103    {
104        for i in 0..self.count() {
105            f(self.at_pos(i))
106        }
107    }
108
109    /** Flange data to the nodes using a map function in a depth first order.
110
111    This means the children are available (already created) when a node
112    is created and can be used to calculate the nodes value.
113
114    # Example
115    ```
116    use flange_flat_tree::{Builder, Tree, Subtree};
117
118    let mut builder = Builder::with_capacity(2);
119    builder.start_element("one");
120    builder.start_element("two");
121    builder.start_end_element("three");
122    builder.start_end_element("four");
123    builder.end_element();
124    builder.end_element();
125    let tree = builder.build();
126
127    // The data we are going to flange
128    let data: Vec<u32> = vec![1,2];
129
130    let tree_with_values = tree.depth_first_flange(
131        |v, childs| {
132            // Calculate the total number of children
133            childs.iter().fold(childs.len(), |l,c| l+*c )
134        }
135    );
136
137    assert_eq!(tree_with_values.root().value().1, &3);
138    assert_eq!(tree_with_values.root().children()[0].value(), (&"two", &2));
139    ```
140     */
141    fn depth_first_flange<B, F>(&'a self, mapf: F) -> FlangedTree<&'a Self, B>
142    where
143        B: 'a,
144        B: Default,
145        B: Clone,
146        F: Fn(Self::Node, Vec<&B>) -> B,
147    {
148        // Uninitialized vector
149        let mut res = vec![B::default(); self.node_count()];
150
151        self.get_nav().for_each_depth_first(|i, childs| {
152            let new_val = mapf(self.get(i), childs.iter().map(|&c| &res[c]).collect());
153            res[i] = new_val;
154        });
155        FlangedTree::new(self, res)
156    }
157}
158
159// impl<A: Sized, Node> Tree for A
160// where
161//     for<'a> &'a A: TreeData<Node = &'a Node>,
162//     for<'a> Node: 'a,
163// {
164//     fn root(&self) -> SubtreeImpl<A> {
165//         SubtreeImpl::new(self, 0)
166//     }
167// }
flange_flat_tree/tree/tree_trait.rs

flange_flat_tree/tree/
tree_trait.rs
