vj-sim 0.3.0

//! A set of integers as sorted, merged, closed intervals over `i128`.
//!
//! Coverpoints are at most 64 bits wide (signed or unsigned), so every
//! coverpoint value and every bin value fits an `i128` exactly. Bins are kept
//! as interval lists, never as expanded value lists, so `bins b = {[0:$]}` on
//! a 64-bit coverpoint costs one interval.

/// Sorted, non-overlapping, non-adjacent closed intervals `(lo, hi)`.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct IntSet {
    iv: Vec<(i128, i128)>,
}

impl IntSet {
    pub fn new() -> Self {
        IntSet { iv: Vec::new() }
    }

    /// Builds a set from arbitrary (possibly overlapping, unsorted, empty)
    /// intervals; an interval with `lo > hi` is empty and dropped.
    pub fn from_intervals(items: impl IntoIterator<Item = (i128, i128)>) -> Self {
        let mut v: Vec<(i128, i128)> = items.into_iter().filter(|&(lo, hi)| lo <= hi).collect();
        v.sort_unstable();
        let mut out: Vec<(i128, i128)> = Vec::with_capacity(v.len());
        for (lo, hi) in v {
            match out.last_mut() {
                Some(last) if lo <= last.1.saturating_add(1) => {
                    if hi > last.1 {
                        last.1 = hi;
                    }
                }
                _ => out.push((lo, hi)),
            }
        }
        IntSet { iv: out }
    }

    pub fn intervals(&self) -> &[(i128, i128)] {
        &self.iv
    }

    pub fn is_empty(&self) -> bool {
        self.iv.is_empty()
    }

    pub fn contains(&self, v: i128) -> bool {
        match self.iv.binary_search_by(|&(lo, _)| lo.cmp(&v)) {
            Ok(_) => true,
            Err(0) => false,
            Err(i) => self.iv[i - 1].1 >= v,
        }
    }

    /// Number of integers in the set.
    pub fn count(&self) -> u128 {
        self.iv
            .iter()
            .map(|&(lo, hi)| (hi - lo) as u128 + 1)
            .fold(0u128, u128::saturating_add)
    }

    pub fn union(&self, other: &IntSet) -> IntSet {
        IntSet::from_intervals(self.iv.iter().chain(other.iv.iter()).copied())
    }

    /// `self` without the members of `other`.
    pub fn subtract(&self, other: &IntSet) -> IntSet {
        let mut out = Vec::new();
        for &(lo, hi) in &self.iv {
            let mut cur = lo;
            let mut done = false;
            for &(olo, ohi) in &other.iv {
                if ohi < cur {
                    continue;
                }
                if olo > hi {
                    break;
                }
                if olo > cur {
                    out.push((cur, olo - 1));
                }
                if ohi >= hi {
                    done = true;
                    break;
                }
                cur = ohi + 1;
            }
            if !done {
                out.push((cur, hi));
            }
        }
        IntSet { iv: out }
    }

    pub fn intersects(&self, other: &IntSet) -> bool {
        let (mut i, mut j) = (0, 0);
        while i < self.iv.len() && j < other.iv.len() {
            let (alo, ahi) = self.iv[i];
            let (blo, bhi) = other.iv[j];
            if ahi < blo {
                i += 1;
            } else if bhi < alo {
                j += 1;
            } else {
                return true;
            }
        }
        false
    }

    /// The set restricted to `[lo, hi]`.
    pub fn clip(&self, lo: i128, hi: i128) -> IntSet {
        IntSet::from_intervals(self.iv.iter().filter_map(|&(a, b)| {
            let (a, b) = (a.max(lo), b.min(hi));
            (a <= b).then_some((a, b))
        }))
    }

    /// The members as individual values, or `None` when there are more than
    /// `limit` of them.
    pub fn values(&self, limit: u128) -> Option<Vec<i128>> {
        if self.count() > limit {
            return None;
        }
        let mut out = Vec::new();
        for &(lo, hi) in &self.iv {
            let mut v = lo;
            while v <= hi {
                out.push(v);
                v += 1;
            }
        }
        Some(out)
    }
}

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

    #[test]
    fn merges_overlapping_and_adjacent() {
        let s = IntSet::from_intervals([(5, 7), (1, 2), (3, 4), (6, 9), (20, 20)]);
        assert_eq!(s.intervals(), &[(1, 9), (20, 20)]);
        assert_eq!(s.count(), 10);
    }

    #[test]
    fn empty_interval_is_dropped() {
        assert!(IntSet::from_intervals([(3, 2)]).is_empty());
    }

    #[test]
    fn contains_on_boundaries() {
        let s = IntSet::from_intervals([(2, 4), (10, 12)]);
        for v in [2, 3, 4, 10, 11, 12] {
            assert!(s.contains(v), "{v}");
        }
        for v in [1, 5, 9, 13, -1] {
            assert!(!s.contains(v), "{v}");
        }
    }

    #[test]
    fn subtract_splits_and_removes() {
        let a = IntSet::from_intervals([(0, 10)]);
        let b = IntSet::from_intervals([(0, 1), (5, 6), (10, 20)]);
        assert_eq!(a.subtract(&b).intervals(), &[(2, 4), (7, 9)]);
        assert!(a.subtract(&a).is_empty());
    }

    #[test]
    fn intersects_and_clip() {
        let a = IntSet::from_intervals([(0, 3), (10, 12)]);
        assert!(a.intersects(&IntSet::from_intervals([(3, 5)])));
        assert!(!a.intersects(&IntSet::from_intervals([(4, 9)])));
        assert_eq!(a.clip(2, 11).intervals(), &[(2, 3), (10, 11)]);
    }

    #[test]
    fn values_respects_limit() {
        let a = IntSet::from_intervals([(1, 3), (7, 7)]);
        assert_eq!(a.values(10), Some(vec![1, 2, 3, 7]));
        assert_eq!(a.values(3), None);
    }
}