anyxml-automata 0.1.2

simple automaton library for XML
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

use crate::Atom;

pub fn normalize_ranges<A: Atom>(
    iter: impl Iterator<Item = (A, A)>,
) -> impl Iterator<Item = (A, A)> {
    let mut buf = iter.collect::<Vec<_>>();
    buf.sort_unstable();

    let mut ret = vec![];
    for (start, end) in buf {
        assert!(start <= end);
        match ret.last_mut() {
            Some((_, e)) if start <= *e || Some(start) == e.next() => {
                *e = end;
            }
            _ => ret.push((start, end)),
        }
    }

    ret.into_iter()
}

/// perform `iter | other`
pub fn union_ranges<A: Atom>(
    iter: impl Iterator<Item = (A, A)>,
    other: impl Iterator<Item = (A, A)>,
) -> impl Iterator<Item = (A, A)> {
    normalize_ranges(iter.chain(other))
}

/// performe `not iter`
pub fn complement_ranges<A: Atom>(
    iter: impl Iterator<Item = (A, A)>,
) -> impl Iterator<Item = (A, A)> {
    let mut iter = normalize_ranges(iter);
    let mut prev = Some(A::MIN);
    std::iter::from_fn(move || {
        for (end, next) in iter.by_ref() {
            let start = prev?;
            prev = next.next();
            if let Some(end) = end.previous().filter(|end| &start <= end) {
                return Some((start, end));
            }
        }
        prev.take().map(|start| (start, A::MAX))
    })
}

/// perform `iter - other`
pub fn difference_ranges<A: Atom>(
    iter: impl Iterator<Item = (A, A)>,
    other: impl Iterator<Item = (A, A)>,
) -> impl Iterator<Item = (A, A)> {
    let mut iter = normalize_ranges(iter);
    let mut other = normalize_ranges(other);

    let mut next = iter.next();
    let mut bad = other.next();
    std::iter::from_fn(move || {
        while let Some((bs, be)) = bad {
            let (start, end) = next?;
            if be < start {
                bad = other.next();
            } else if end < bs {
                next = iter.next();
                return Some((start, end));
            } else if bs <= start {
                if end <= be {
                    // bs - start - end - be
                    next = iter.next();
                } else {
                    // bs - start - be - end
                    next = Some((be.next().unwrap(), end));
                    bad = other.next();
                }
            } else if end <= be {
                // start - bs - end - be
                next = iter.next();
                return Some((start, bs.previous().unwrap()));
            } else {
                // start - bs - be - end
                next = Some((be.next().unwrap(), end));
                bad = other.next();
                return Some((start, bs.previous().unwrap()));
            }
        }
        let (start, end) = next?;
        next = iter.next();
        Some((start, end))
    })
}