xot 0.31.2

Full-featured XML tree library for Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

use genawaiter::rc::gen;
use genawaiter::yield_;

use std::collections::VecDeque;

use crate::xotdata::{Node, Xot};

/// Node in level order
///
/// Used by [`Xot::level_order`].
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum LevelOrder {
    /// A node
    Node(Node),
    /// The end of a sequence of nodes.
    End,
}

// traverse the tree in level order, meaning subsequent children are traversed first
// when a sequence of children comes to an end, a LevelOrder::End is yielded
pub(crate) fn level_order_traverse(xot: &Xot, node: Node) -> impl Iterator<Item = LevelOrder> + '_ {
    gen!({
        let mut queue = VecDeque::new();
        queue.push_back(node);
        // we make last node the current node; that's okay as it's
        // popped right away and thus has the same parent as the current node
        let mut last_node = node;
        while let Some(node) = queue.pop_front() {
            if xot.parent(last_node) != xot.parent(node) {
                yield_!(LevelOrder::End);
            }
            yield_!(LevelOrder::Node(node));

            last_node = node;
            for child in xot.children(node) {
                queue.push_back(child);
            }
        }
        yield_!(LevelOrder::End);
    })
    .into_iter()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_level_order_traverse() {
        let mut xot = Xot::new();
        let root = xot
            .parse("<doc><a><b/><b/></a><a><b><c/><c/><c/></b><b/></a></doc>")
            .unwrap();
        let doc = xot.document_element(root).unwrap();
        let a0 = xot.first_child(doc).unwrap();
        let a1 = xot.next_sibling(a0).unwrap();
        let b0 = xot.first_child(a0).unwrap();
        let b1 = xot.next_sibling(b0).unwrap();
        let b2 = xot.first_child(a1).unwrap();
        let b3 = xot.next_sibling(b2).unwrap();
        let c0 = xot.first_child(b2).unwrap();
        let c1 = xot.next_sibling(c0).unwrap();
        let c2 = xot.next_sibling(c1).unwrap();

        let iter = level_order_traverse(&xot, root);

        let v = iter.collect::<Vec<_>>();
        assert_eq!(
            v,
            vec![
                LevelOrder::Node(root),
                LevelOrder::End,
                LevelOrder::Node(doc),
                LevelOrder::End,
                LevelOrder::Node(a0),
                LevelOrder::Node(a1),
                LevelOrder::End,
                LevelOrder::Node(b0),
                LevelOrder::Node(b1),
                LevelOrder::End,
                LevelOrder::Node(b2),
                LevelOrder::Node(b3),
                LevelOrder::End,
                LevelOrder::Node(c0),
                LevelOrder::Node(c1),
                LevelOrder::Node(c2),
                LevelOrder::End,
            ]
        );
    }

    #[test]
    fn test_level_order_traverse_with_text() {
        let mut xot = Xot::new();
        let root = xot.parse("<doc><a>X</a><a>X<b/>X</a></doc>").unwrap();
        let doc = xot.document_element(root).unwrap();
        let a0 = xot.first_child(doc).unwrap();
        let a1 = xot.next_sibling(a0).unwrap();
        let x0 = xot.first_child(a0).unwrap();
        let x1 = xot.first_child(a1).unwrap();
        let b0 = xot.next_sibling(x1).unwrap();
        let x2 = xot.next_sibling(b0).unwrap();

        let iter = level_order_traverse(&xot, root);

        let v = iter.collect::<Vec<_>>();
        assert_eq!(
            v,
            vec![
                LevelOrder::Node(root),
                LevelOrder::End,
                LevelOrder::Node(doc),
                LevelOrder::End,
                LevelOrder::Node(a0),
                LevelOrder::Node(a1),
                LevelOrder::End,
                LevelOrder::Node(x0),
                LevelOrder::End,
                LevelOrder::Node(x1),
                LevelOrder::Node(b0),
                LevelOrder::Node(x2),
                LevelOrder::End,
            ]
        );
    }
}