mt_dom/patch/
tree_path.rs

1use crate::Node;
2use alloc::vec;
3use alloc::vec::Vec;
4use core::fmt::Debug;
5
6/// Describe the path traversal of a Node starting from the root node
7///
8/// The figure below shows `node_idx` in a depth first traversal.
9///
10/// ```text
11///            .─.
12///           ( 0 )
13///            `-'
14///           /   \
15///          /     \
16///         /       \
17///        ▼         ▼
18///       .─.         .─.
19///      ( 1 )       ( 4 )
20///       `-'         `-'
21///      /  \          | \ '.
22///     /    \         |  \  '.
23///    ▼      ▼        |   \   '.
24///  .─.      .─.      ▼    ▼     ▼
25/// ( 2 )    ( 3 )    .─.   .─.   .─.
26///  `─'      `─'    ( 5 ) ( 6 ) ( 7 )
27///                   `─'   `─'   `─'
28/// ```
29///
30/// The figure below shows the index of each child node relative to their parent node
31///
32/// ```text
33///             .─.
34///            ( 0 )
35///             `-'
36///            /   \
37///           /     \
38///          /       \
39///         ▼         ▼
40///        .─.         .─.
41///       ( 0 )       ( 1 )
42///        `-'         `-'
43///       /  \          | \ '.
44///      /    \         |  \  '.
45///     ▼      ▼        |   \   '.
46///   .─.      .─.      ▼    ▼     ▼
47///  ( 0 )    ( 1 )    .─.   .─.   .─.
48///   `─'      `─'    ( 0 ) ( 1 ) ( 2 )
49///                    `─'   `─'   `─'
50/// ```
51/// The equivalent idx and path are as follows:
52/// ```text
53///    0 = []
54///    1 = [0]
55///    2 = [0,0]
56///    3 = [0,1]
57///    4 = [1]
58///    5 = [1,0]
59///    6 = [1,1]
60///    7 = [1,2]
61/// ```
62#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord)]
63pub struct TreePath {
64    /// An array of child index at each level of the dom tree.
65    /// The children of the nodes at each child index is traverse
66    /// at each traversal the first element of path is removed until
67    /// the path becomes empty.
68    /// If the path has become empty the node is said to be found.
69    ///
70    /// Empty path means root node
71    pub path: Vec<usize>,
72}
73
74impl TreePath {
75    /// create a TreePath with node index `node_idx` and traversal path `path`
76    pub fn new(path: impl IntoIterator<Item = usize>) -> Self {
77        Self {
78            path: path.into_iter().collect(),
79        }
80    }
81
82    /// create a TreePath which starts at empty vec which is the root node of a DOM tree
83    pub fn root() -> Self {
84        Self { path: vec![] }
85    }
86
87    /// add a path node idx
88    pub fn push(&mut self, node_idx: usize) {
89        self.path.push(node_idx)
90    }
91
92    /// create a new TreePath with an added node_index
93    /// This is used for traversing into child elements
94    pub fn traverse(&self, node_idx: usize) -> Self {
95        let mut new_path = self.clone();
96        new_path.push(node_idx);
97        new_path
98    }
99
100    /// backtrack to the parent node path
101    pub fn backtrack(&self) -> Self {
102        let mut new_path = self.clone();
103        new_path.path.pop();
104        new_path
105    }
106
107    /// remove first node index of this treepath
108    /// Everytime a node is traversed, the first element should be removed
109    /// until no more index is in this path
110    pub fn remove_first(&mut self) -> usize {
111        self.path.remove(0)
112    }
113
114    /// pluck the next in line node index in this treepath
115    pub fn pluck(&mut self) -> usize {
116        self.remove_first()
117    }
118
119    /// returns tree if the path is empty
120    /// This is used for checking if the path has been traversed
121    pub fn is_empty(&self) -> bool {
122        self.path.is_empty()
123    }
124
125    /// find the node using the path of this tree path
126    pub fn find_node_by_path<'a, Ns, Tag, Leaf, Att, Val>(
127        &self,
128        node: &'a Node<Ns, Tag, Leaf, Att, Val>,
129    ) -> Option<&'a Node<Ns, Tag, Leaf, Att, Val>>
130    where
131        Ns: PartialEq + Clone + Debug,
132        Tag: PartialEq + Clone + Debug,
133        Leaf: PartialEq + Clone + Debug,
134        Att: PartialEq + Clone + Debug,
135        Val: PartialEq + Clone + Debug,
136    {
137        let mut path = self.clone();
138        traverse_node_by_path(node, &mut path)
139    }
140}
141
142impl<const N: usize> From<[usize; N]> for TreePath {
143    fn from(array: [usize; N]) -> Self {
144        Self {
145            path: array.to_vec(),
146        }
147    }
148}
149
150impl From<Vec<usize>> for TreePath {
151    fn from(vec: Vec<usize>) -> Self {
152        Self { path: vec }
153    }
154}
155
156fn traverse_node_by_path<'a, Ns, Tag, Leaf, Att, Val>(
157    node: &'a Node<Ns, Tag, Leaf, Att, Val>,
158    path: &mut TreePath,
159) -> Option<&'a Node<Ns, Tag, Leaf, Att, Val>>
160where
161    Ns: PartialEq + Clone + Debug,
162    Tag: PartialEq + Clone + Debug,
163    Leaf: PartialEq + Clone + Debug,
164    Att: PartialEq + Clone + Debug,
165    Val: PartialEq + Clone + Debug,
166{
167    if path.path.is_empty() {
168        Some(node)
169    } else {
170        let idx = path.path.remove(0);
171        if let Some(child) = node.children().get(idx) {
172            traverse_node_by_path(child, path)
173        } else {
174            None
175        }
176    }
177}
178
179
180#[cfg(test)]
181mod tests {
182    use super::*;
183    use crate::*;
184    use alloc::format;
185    use alloc::string::String;
186    use alloc::string::ToString;
187
188    type MyNode = Node<
189        &'static str,
190        &'static str,
191        &'static str,
192        &'static str,
193        &'static str,
194    >;
195
196    #[test]
197    fn test_traverse() {
198        let path = TreePath::from([0]);
199
200        assert_eq!(path.traverse(1), TreePath::from([0, 1]));
201    }
202
203    fn sample_node() -> MyNode {
204        let node: MyNode = element(
205            "div",
206            vec![attr("class", "[]"), attr("id", "0")],
207            vec![
208                element(
209                    "div",
210                    vec![attr("class", "[0]"), attr("id", "1")],
211                    vec![
212                        element(
213                            "div",
214                            vec![attr("class", "[0,0]"), attr("id", "2")],
215                            vec![],
216                        ),
217                        element(
218                            "div",
219                            vec![attr("class", "[0,1]"), attr("id", "3")],
220                            vec![],
221                        ),
222                    ],
223                ),
224                element(
225                    "div",
226                    vec![attr("class", "[1]"), attr("id", "4")],
227                    vec![
228                        element(
229                            "div",
230                            vec![attr("class", "[1,0]"), attr("id", "5")],
231                            vec![],
232                        ),
233                        element(
234                            "div",
235                            vec![attr("class", "[1,1]"), attr("id", "6")],
236                            vec![],
237                        ),
238                        element(
239                            "div",
240                            vec![attr("class", "[1,2]"), attr("id", "7")],
241                            vec![],
242                        ),
243                    ],
244                ),
245            ],
246        );
247        node
248    }
249
250    // index is the index of this code with respect to it's sibling
251    fn assert_traverse_match(
252        node: &MyNode,
253        node_idx: &mut usize,
254        path: Vec<usize>,
255    ) {
256        let id = node.attribute_value(&"id").unwrap()[0];
257        let class = node.attribute_value(&"class").unwrap()[0];
258        assert_eq!(id.to_string(), node_idx.to_string());
259        assert_eq!(class.to_string(), format_vec(&path));
260        for (i, child) in node.children().iter().enumerate() {
261            *node_idx += 1;
262            let mut child_path = path.clone();
263            child_path.push(i);
264            assert_traverse_match(child, node_idx, child_path);
265        }
266    }
267
268    fn traverse_tree_path(
269        node: &MyNode,
270        path: &TreePath,
271        node_idx: &mut usize,
272    ) {
273        let id = node.attribute_value(&"id").unwrap()[0];
274        let class = node.attribute_value(&"class").unwrap()[0];
275        assert_eq!(id.to_string(), node_idx.to_string());
276        assert_eq!(class.to_string(), format_vec(&path.path));
277        for (i, child) in node.children().iter().enumerate() {
278            *node_idx += 1;
279            let mut child_path = path.clone();
280            child_path.path.push(i);
281            traverse_tree_path(child, &child_path, node_idx);
282        }
283    }
284
285    fn format_vec(v: &[usize]) -> String {
286        format!(
287            "[{}]",
288            v.iter()
289                .map(|v| v.to_string())
290                .collect::<Vec<_>>()
291                .join(",")
292        )
293    }
294
295    #[test]
296    fn should_match_paths() {
297        let node = sample_node();
298        assert_traverse_match(&node, &mut 0, vec![]);
299        traverse_tree_path(&node, &TreePath::new(vec![]), &mut 0);
300    }
301
302    #[test]
303    fn should_find_root_node() {
304        let node = sample_node();
305        let path = TreePath::new(vec![]);
306        let root = path.find_node_by_path(&node);
307        assert_eq!(Some(&node), root);
308    }
309
310    #[test]
311    fn should_find_node1() {
312        let node = sample_node();
313        let path = TreePath::new(vec![0]);
314        let found = path.find_node_by_path(&node);
315        let expected = element(
316            "div",
317            vec![attr("class", "[0]"), attr("id", "1")],
318            vec![
319                element(
320                    "div",
321                    vec![attr("class", "[0,0]"), attr("id", "2")],
322                    vec![],
323                ),
324                element(
325                    "div",
326                    vec![attr("class", "[0,1]"), attr("id", "3")],
327                    vec![],
328                ),
329            ],
330        );
331        assert_eq!(Some(&expected), found);
332    }
333
334    #[test]
335    fn should_find_node2() {
336        let node = sample_node();
337        let path = TreePath::new(vec![0, 0]);
338        let found = path.find_node_by_path(&node);
339        let expected = element(
340            "div",
341            vec![attr("class", "[0,0]"), attr("id", "2")],
342            vec![],
343        );
344        assert_eq!(Some(&expected), found);
345    }
346
347    #[test]
348    fn should_find_node3() {
349        let node = sample_node();
350        let path = TreePath::new(vec![0, 1]);
351        let found = path.find_node_by_path(&node);
352        let expected = element(
353            "div",
354            vec![attr("class", "[0,1]"), attr("id", "3")],
355            vec![],
356        );
357        assert_eq!(Some(&expected), found);
358    }
359
360    #[test]
361    fn should_find_node4() {
362        let node = sample_node();
363        let path = TreePath::new(vec![1]);
364        let found = path.find_node_by_path(&node);
365        let expected = element(
366            "div",
367            vec![attr("class", "[1]"), attr("id", "4")],
368            vec![
369                element(
370                    "div",
371                    vec![attr("class", "[1,0]"), attr("id", "5")],
372                    vec![],
373                ),
374                element(
375                    "div",
376                    vec![attr("class", "[1,1]"), attr("id", "6")],
377                    vec![],
378                ),
379                element(
380                    "div",
381                    vec![attr("class", "[1,2]"), attr("id", "7")],
382                    vec![],
383                ),
384            ],
385        );
386        assert_eq!(Some(&expected), found);
387    }
388
389    #[test]
390    fn should_find_node5() {
391        let node = sample_node();
392        let path = TreePath::new(vec![1, 0]);
393        let found = path.find_node_by_path(&node);
394        let expected = element(
395            "div",
396            vec![attr("class", "[1,0]"), attr("id", "5")],
397            vec![],
398        );
399        assert_eq!(Some(&expected), found);
400    }
401
402    #[test]
403    fn should_find_node6() {
404        let node = sample_node();
405        let path = TreePath::new(vec![1, 1]);
406        let found = path.find_node_by_path(&node);
407        let expected = element(
408            "div",
409            vec![attr("class", "[1,1]"), attr("id", "6")],
410            vec![],
411        );
412        assert_eq!(Some(&expected), found);
413    }
414
415    #[test]
416    fn should_find_none_in_013() {
417        let node = sample_node();
418        let path = TreePath::new(vec![0, 1, 3]);
419        let found = path.find_node_by_path(&node);
420        assert_eq!(None, found);
421    }
422
423    #[test]
424    fn should_find_none_in_00000() {
425        let node = sample_node();
426        let path = TreePath::new(vec![0, 0, 0, 0]);
427        let found = path.find_node_by_path(&node);
428        assert_eq!(None, found);
429    }
430
431    #[test]
432    fn should_find_none_in_007() {
433        let node = sample_node();
434        let path = TreePath::new(vec![0, 0, 7]);
435        let bond = path.find_node_by_path(&node);
436        assert_eq!(None, bond);
437    }
438}
mt_dom/patch/tree_path.rs

mt_dom/patch/
tree_path.rs
