flange_flat_tree/navigator/
navigator_impl.rs

1use super::neighbors::Neighbors;
2
3#[derive(Debug)]
4/** The navigator stores the structure of the tree.
5It knows which nodes are neighbors, parents and children
6of a node and allows navigating to them.
7With "navigation" we mean that the index in the flat Vector storing all the nodes
8is returned.
9
10# Example:
11
12```
13use flange_flat_tree::navigator::Builder;
14
15// A navigator just stores neigbors, so we provide no values
16let mut b = Builder::default();
17let root = b.start_element();
18let child1 = b.start_end_element();
19let child2 = b.start_end_element();
20
21let nav = b.build();
22
23assert_eq!(nav.children(root), [child1,child2]);
24assert_eq!(nav.next_sibling(child1), Some(child2));
25assert_eq!(nav.prev_sibling(child2), Some(child1));
26```
27
28*/
29pub struct Navigator {
30    neighbors: Vec<Neighbors<usize>>,
31}
32
33impl Navigator {
34    /** Create a navigator given its internal data.
35     * is and should only be used by the builder.
36     */
37    pub(crate) fn new(neighbors: Vec<Neighbors<usize>>) -> Navigator {
38        Navigator { neighbors }
39    }
40
41    /** Iterates through all nodes in a depth-first order.
42    That means the children of a node are garuanteed to be
43    visited before the node itself.
44
45    # Example
46    ```
47    use flange_flat_tree::navigator::Builder;
48
49    // A navigator just stores neigbors, so we provide no values
50    let mut b = Builder::default();
51    let root = b.start_element();
52    let child1 = b.start_end_element();
53    let child2 = b.start_end_element();
54    // ...
55
56    let nav = b.build();
57    let mut visited = vec![false;3];
58
59     nav.for_each_depth_first(|i, childs| {
60         visited[i] = true;
61         for c in childs {
62             assert!(visited[c]);
63         }
64     });
65    ```
66    */
67    pub fn for_each_depth_first<F>(&self, mut f: F)
68    where
69        F: FnMut(usize, Vec<usize>),
70    {
71        (0..self.neighbors.len())
72            .rev()
73            .for_each(|i| f(i, self.children(i)))
74    }
75
76    /** Returns the neighbors structure for a node.
77     *
78     * # Arguments
79     *
80     * - index - The index to find the neighbors of.
81     *
82     * # Result
83     *
84     * The neighbors of the nodes (in a Neighbors<usize> structure).
85     */
86    pub fn get_neighbors(&self, index: usize) -> &Neighbors<usize> {
87        &self.neighbors[index]
88    }
89
90    /** Return the index of the parent (if any).
91     *
92     * # Arguments
93     *
94     * - index - The index to find the parent of.
95     *
96     * # Result
97     *
98     * The index of the parent or none if the node has no parent.
99     */
100    pub fn parent(&self, index: usize) -> Option<usize> {
101        self.neighbors.get(index).and_then(|n| n.parent)
102    }
103
104    /** Return the index of the first child (if any).
105     *
106     * # Arguments
107     *
108     * - index - The index to find the first child of.
109     *
110     * # Result
111     *
112     * The index of the first child or none if the node has no first child.
113     */
114    pub fn first_child(&self, index: usize) -> Option<usize> {
115        // the first child is the next node
116        self.neighbors.get(index + 1).and_then(|i| {
117            if i.parent.unwrap() != index {
118                None
119            } else {
120                Some(index + 1)
121            }
122        })
123    }
124
125    /** Return the indices of the all children.
126     *
127     * # Arguments
128     *
129     * - index - The index to find the children of.
130     *
131     * # Result
132     *
133     * The indices of the childre in a `Vec`.
134     */
135    pub fn children(&self, index: usize) -> Vec<usize> {
136        let mut res = Vec::new();
137        let mut opt_cindex = self.first_child(index);
138        while let Some(cindex) = opt_cindex {
139            res.push(cindex);
140            opt_cindex = self.neighbors.get(cindex).unwrap().next_sibling;
141        }
142        res
143    }
144
145    /** Return the index of the the next sibling (if any).
146     *
147     * The next sibling is the next node that has the same parent
148     * as the given node.
149     *
150     * # Arguments
151     *
152     * - index - The index to find the next sibling of.
153     *
154     * # Result
155     *
156     * The index of the next sibling or none if the node has no next sibling.
157     */
158    pub fn prev_sibling(&self, index: usize) -> Option<usize> {
159        self.neighbors.get(index).and_then(|n| n.prev_sibling)
160    }
161
162    /** Return the index of the the prev sibling (if any).
163     *
164     * The prev sibling is the prev node that has the same parent
165     * as the given node.
166     *
167     * # Arguments
168     *
169     * - index - The index to find the prev sibling of.
170     *
171     * # Result
172     *
173     * The index of the prev sibling or none if the node has no prev sibling.
174     */
175    pub fn next_sibling(&self, index: usize) -> Option<usize> {
176        self.neighbors.get(index).and_then(|n| n.next_sibling)
177    }
178}
flange_flat_tree/navigator/navigator_impl.rs

flange_flat_tree/navigator/
navigator_impl.rs
