anyxml_automata/
util.rs

1use crate::Atom;
2
3pub fn normalize_ranges<A: Atom>(
4    iter: impl Iterator<Item = (A, A)>,
5) -> impl Iterator<Item = (A, A)> {
6    let mut buf = iter.collect::<Vec<_>>();
7    buf.sort_unstable();
8
9    let mut ret = vec![];
10    for (start, end) in buf {
11        assert!(start <= end);
12        match ret.last_mut() {
13            Some((_, e)) if start <= *e || Some(start) == e.next() => {
14                *e = end;
15            }
16            _ => ret.push((start, end)),
17        }
18    }
19
20    ret.into_iter()
21}
22
23/// perform `iter | other`
24pub fn union_ranges<A: Atom>(
25    iter: impl Iterator<Item = (A, A)>,
26    other: impl Iterator<Item = (A, A)>,
27) -> impl Iterator<Item = (A, A)> {
28    normalize_ranges(iter.chain(other))
29}
30
31/// performe `not iter`
32pub fn complement_ranges<A: Atom>(
33    iter: impl Iterator<Item = (A, A)>,
34) -> impl Iterator<Item = (A, A)> {
35    let mut iter = normalize_ranges(iter);
36    let mut prev = Some(A::MIN);
37    std::iter::from_fn(move || {
38        for (end, next) in iter.by_ref() {
39            let start = prev?;
40            prev = next.next();
41            if let Some(end) = end.previous().filter(|end| &start <= end) {
42                return Some((start, end));
43            }
44        }
45        prev.take().map(|start| (start, A::MAX))
46    })
47}
48
49/// perform `iter - other`
50pub fn difference_ranges<A: Atom>(
51    iter: impl Iterator<Item = (A, A)>,
52    other: impl Iterator<Item = (A, A)>,
53) -> impl Iterator<Item = (A, A)> {
54    let mut iter = normalize_ranges(iter);
55    let mut other = normalize_ranges(other);
56
57    let mut next = iter.next();
58    let mut bad = other.next();
59    std::iter::from_fn(move || {
60        while let Some((bs, be)) = bad {
61            let (start, end) = next?;
62            if be < start {
63                bad = other.next();
64            } else if end < bs {
65                next = iter.next();
66                return Some((start, end));
67            } else if bs <= start {
68                if end <= be {
69                    // bs - start - end - be
70                    next = iter.next();
71                } else {
72                    // bs - start - be - end
73                    next = Some((be.next().unwrap(), end));
74                    bad = other.next();
75                }
76            } else if end <= be {
77                // start - bs - end - be
78                next = iter.next();
79                return Some((start, bs.previous().unwrap()));
80            } else {
81                // start - bs - be - end
82                next = Some((be.next().unwrap(), end));
83                bad = other.next();
84                return Some((start, bs.previous().unwrap()));
85            }
86        }
87        let (start, end) = next?;
88        next = iter.next();
89        Some((start, end))
90    })
91}
anyxml_automata/util.rs

anyxml_automata/
util.rs
