rexact_core/

charset.rs

//! Interval sets of code points and partitions of the alphabet.
//!
//! Invariant: `ranges` is sorted, non-empty ranges are inclusive, and no two
//! ranges overlap or touch, so equal sets have one representation. All values
//! are at most `0x10FFFF`, so `+ 1` cannot overflow `u32`.

/// A set of code points stored as normalised inclusive ranges.
#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug, Default)]
pub struct CharSet {
    ranges: Vec<(u32, u32)>,
}

impl CharSet {
    /// The empty set.
    pub fn empty() -> Self {
        Self::default()
    }

    /// One code point.
    pub fn single(c: u32) -> Self {
        Self {
            ranges: vec![(c, c)],
        }
    }

    /// Inclusive range; empty when `lo > hi`.
    pub fn range(lo: u32, hi: u32) -> Self {
        if lo > hi {
            Self::empty()
        } else {
            Self {
                ranges: vec![(lo, hi)],
            }
        }
    }

    /// Normalise arbitrary ranges (any order, overlapping, touching).
    pub fn from_ranges<I: IntoIterator<Item = (u32, u32)>>(it: I) -> Self {
        let mut v: Vec<(u32, u32)> = it.into_iter().filter(|(l, h)| l <= h).collect();
        v.sort_unstable();
        let mut out: Vec<(u32, u32)> = Vec::with_capacity(v.len());
        for (lo, hi) in v {
            match out.last_mut() {
                Some(last) if lo <= last.1.saturating_add(1) => last.1 = last.1.max(hi),
                _ => out.push((lo, hi)),
            }
        }
        Self { ranges: out }
    }

    /// The normalised ranges.
    pub fn ranges(&self) -> &[(u32, u32)] {
        &self.ranges
    }

    /// True when no code point is a member.
    pub fn is_empty(&self) -> bool {
        self.ranges.is_empty()
    }

    /// Smallest member.
    pub fn smallest(&self) -> Option<u32> {
        self.ranges.first().map(|r| r.0)
    }

    /// Membership test.
    pub fn contains(&self, c: u32) -> bool {
        self.ranges
            .binary_search_by(|&(lo, hi)| {
                if c < lo {
                    std::cmp::Ordering::Greater
                } else if c > hi {
                    std::cmp::Ordering::Less
                } else {
                    std::cmp::Ordering::Equal
                }
            })
            .is_ok()
    }

    /// Number of members.
    pub fn count(&self) -> u64 {
        self.ranges.iter().map(|&(l, h)| u64::from(h - l) + 1).sum()
    }

    /// Set union.
    pub fn union(&self, o: &CharSet) -> CharSet {
        CharSet::from_ranges(self.ranges.iter().chain(o.ranges.iter()).copied())
    }

    /// Set intersection.
    pub fn intersect(&self, o: &CharSet) -> CharSet {
        let (mut i, mut j) = (0, 0);
        let mut out = Vec::new();
        while i < self.ranges.len() && j < o.ranges.len() {
            let (a, b) = (self.ranges[i], o.ranges[j]);
            let (lo, hi) = (a.0.max(b.0), a.1.min(b.1));
            if lo <= hi {
                out.push((lo, hi));
            }
            if a.1 < b.1 {
                i += 1;
            } else {
                j += 1;
            }
        }
        Self { ranges: out }
    }

    /// Members of `self` that are not in `o`.
    pub fn difference(&self, o: &CharSet) -> CharSet {
        let mut out = Vec::new();
        let mut j = 0;
        for &(lo, hi) in &self.ranges {
            let mut cur = lo;
            while j < o.ranges.len() && o.ranges[j].1 < cur {
                j += 1;
            }
            let mut k = j;
            let mut covered = false;
            while k < o.ranges.len() && o.ranges[k].0 <= hi {
                let (blo, bhi) = o.ranges[k];
                if blo > cur {
                    out.push((cur, blo - 1));
                }
                if bhi >= hi {
                    covered = true;
                    break;
                }
                cur = bhi + 1;
                k += 1;
            }
            if !covered && cur <= hi {
                out.push((cur, hi));
            }
        }
        Self { ranges: out }
    }
}

/// Split every block of `p` by membership in `s`, dropping empty pieces.
pub fn refine(p: &[CharSet], s: &CharSet) -> Vec<CharSet> {
    let mut out = Vec::with_capacity(p.len() + 1);
    for b in p {
        let inside = b.intersect(s);
        if inside.is_empty() {
            out.push(b.clone());
        } else {
            let outside = b.difference(s);
            out.push(inside);
            if !outside.is_empty() {
                out.push(outside);
            }
        }
    }
    out
}

/// Common refinement of two partitions, ordered by smallest member.
pub fn refine_all(p: &[CharSet], q: &[CharSet]) -> Vec<CharSet> {
    let mut out = Vec::new();
    for a in p {
        for b in q {
            let x = a.intersect(b);
            if !x.is_empty() {
                out.push(x);
            }
        }
    }
    out.sort_by_key(|s| s.smallest());
    out
}

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

    fn cs(r: &[(u32, u32)]) -> CharSet {
        CharSet::from_ranges(r.iter().copied())
    }

    #[test]
    fn normalisation_merges_overlapping_and_touching() {
        assert_eq!(cs(&[(5, 9), (1, 3), (4, 4), (8, 12)]).ranges(), &[(1, 12)]);
        assert_eq!(cs(&[(1, 2), (4, 5)]).ranges(), &[(1, 2), (4, 5)]);
        assert!(cs(&[(3, 1)]).is_empty());
    }

    #[test]
    fn set_algebra_matches_brute_force_on_a_small_universe() {
        // Exhaustively compare against bit-set semantics on 0..16.
        let sets: Vec<CharSet> = (0u32..256)
            .map(|m| {
                CharSet::from_ranges(
                    (0..8)
                        .filter(|b| m >> b & 1 == 1)
                        .map(|b| (b * 2, b * 2 + 1)),
                )
            })
            .collect();
        let bits = |s: &CharSet| (0..16u32).filter(|&c| s.contains(c)).collect::<Vec<_>>();
        for a in sets.iter().step_by(7) {
            for b in sets.iter().step_by(5) {
                let (x, y) = (bits(a), bits(b));
                let u: Vec<u32> = (0..16).filter(|c| x.contains(c) || y.contains(c)).collect();
                let i: Vec<u32> = (0..16).filter(|c| x.contains(c) && y.contains(c)).collect();
                let d: Vec<u32> = (0..16)
                    .filter(|c| x.contains(c) && !y.contains(c))
                    .collect();
                assert_eq!(bits(&a.union(b)), u);
                assert_eq!(bits(&a.intersect(b)), i);
                assert_eq!(bits(&a.difference(b)), d);
            }
        }
    }

    #[test]
    fn difference_handles_holes_and_full_cover() {
        assert_eq!(
            cs(&[(0, 100)])
                .difference(&cs(&[(10, 20), (30, 40)]))
                .ranges(),
            &[(0, 9), (21, 29), (41, 100)]
        );
        assert!(cs(&[(5, 6)]).difference(&cs(&[(0, 10)])).is_empty());
        assert_eq!(
            cs(&[(1, 3), (5, 9)]).difference(&cs(&[(3, 5)])).ranges(),
            &[(1, 2), (6, 9)]
        );
    }

    #[test]
    fn membership_count_and_min() {
        let s = cs(&[(10, 12), (100, 100)]);
        assert!(s.contains(11) && s.contains(100) && !s.contains(13) && !s.contains(9));
        assert_eq!((s.count(), s.smallest()), (4, Some(10)));
    }

    #[test]
    fn refinement_partitions_exactly() {
        let all = CharSet::range(0, 99);
        let p = refine(
            &refine(std::slice::from_ref(&all), &CharSet::range(10, 30)),
            &CharSet::range(20, 50),
        );
        let mut union = CharSet::empty();
        for (i, a) in p.iter().enumerate() {
            for b in &p[i + 1..] {
                assert!(a.intersect(b).is_empty());
            }
            union = union.union(a);
        }
        assert_eq!(union, all);
        // Blocks are sets, not intervals: {10-19} {20-30} {31-50} {0-9,51-99}.
        assert_eq!(p.len(), 4);
    }
}