flange_flat_tree/navigator/
builder.rs

1use super::navigator_impl::Navigator;
2use super::neighbors::Neighbors;
3
4/** Create a FlatTree using simple commands
5A flat tree itself is immutable, so we use the builder pattern.
6## Example
7
8```
9use flange_flat_tree::navigator::Builder;
10
11// A navigator just stores neigbors, so we provide no values
12let mut b = Builder::default();
13let root = b.start_element();
14let child = b.start_end_element();
15
16let nav = b.build();
17
18assert_eq!(nav.children(root), [child]);
19assert_eq!(nav.parent(child), Some(root));
20```
21 */
22pub struct Builder {
23    // current_depth: usize,
24
25    // List of the parents at the different levels (so the last one is always
26    // the current parent).
27    parents_stack: Vec<usize>,
28    // The last sibling for our current position (if any).
29    last_sibling: Option<usize>,
30
31    // Internal data for the final tree.
32    cur_neighbors: Vec<Neighbors<usize>>,
33}
34
35impl Default for Builder {
36    /// Create a new builder
37    fn default() -> Builder {
38        Builder {
39            cur_neighbors: Vec::new(),
40            // current_depth: 0,
41            parents_stack: Vec::new(),
42            last_sibling: None,
43        }
44    }
45}
46
47impl Builder {
48    /// Create a new builder and pre-allocate memory
49    pub fn with_capacity(c: usize) -> Builder {
50        Builder {
51            cur_neighbors: Vec::with_capacity(c),
52            // current_depth: 0,
53            parents_stack: Vec::new(),
54            last_sibling: None,
55        }
56    }
57
58    /** Start a new element.
59     *
60     * This element will be the child of the last element
61     * that was not finished with `end_element`.
62     */
63    pub fn start_element(&mut self) -> usize {
64        let my_index = self.cur_neighbors.len();
65        self.cur_neighbors.push(Neighbors {
66            me: Some(my_index),
67            parent: self.parents_stack.last().cloned(),
68            first_child: None,
69            next_sibling: None,
70            prev_sibling: self.last_sibling,
71        });
72        // Update last sibling
73        if let Some(ls) = self.last_sibling {
74            self.cur_neighbors[ls].next_sibling = Some(my_index);
75        }
76        // Update parent
77        if let Some(&parent_index) = self.parents_stack.last() {
78            if self.cur_neighbors[parent_index].first_child.is_none() {
79                self.cur_neighbors[parent_index].first_child = Some(my_index);
80            }
81        }
82        // Update state
83        self.parents_stack.push(my_index);
84        self.last_sibling = None;
85        my_index
86    }
87
88    /** End and element.
89     *
90     * No more children will be added to this element.
91     * The next element would be a sibling of this element.
92     */
93    pub fn end_element(&mut self) -> usize {
94        self.last_sibling = self.parents_stack.pop();
95        self.last_sibling.unwrap()
96    }
97
98    /** Start and imidiatly end an element.
99     *
100     * This is the same as calling `start_element` and `end_element`
101     * after each other.
102     */
103    pub fn start_end_element(&mut self) -> usize {
104        let my_index = self.cur_neighbors.len();
105        self.cur_neighbors.push(Neighbors {
106            me: Some(my_index),
107            first_child: None,
108            parent: self.parents_stack.last().cloned(),
109            next_sibling: None,
110            prev_sibling: self.last_sibling,
111        });
112        // Update last sibling
113        if let Some(ls) = self.last_sibling {
114            self.cur_neighbors[ls].next_sibling = Some(my_index);
115        }
116        // Update parent
117        if let Some(&parent_index) = self.parents_stack.last() {
118            if self.cur_neighbors[parent_index].first_child.is_none() {
119                self.cur_neighbors[parent_index].first_child = Some(my_index);
120            }
121        }
122        // Update state
123        self.last_sibling = Some(my_index);
124        my_index
125    }
126
127    /** Finish the building and create the `Navigator`.
128     *
129     * The navigator will be created and the buidler destructed.
130     */
131    pub fn build(self) -> Navigator {
132        Navigator::new(self.cur_neighbors)
133    }
134}
flange_flat_tree/navigator/builder.rs

flange_flat_tree/navigator/
builder.rs
