vj_sim/covergroup/
intset.rs

1//! A set of integers as sorted, merged, closed intervals over `i128`.
2//!
3//! Coverpoints are at most 64 bits wide (signed or unsigned), so every
4//! coverpoint value and every bin value fits an `i128` exactly. Bins are kept
5//! as interval lists, never as expanded value lists, so `bins b = {[0:$]}` on
6//! a 64-bit coverpoint costs one interval.
7
8/// Sorted, non-overlapping, non-adjacent closed intervals `(lo, hi)`.
9#[derive(Clone, Debug, Default, PartialEq, Eq)]
10pub struct IntSet {
11    iv: Vec<(i128, i128)>,
12}
13
14impl IntSet {
15    pub fn new() -> Self {
16        IntSet { iv: Vec::new() }
17    }
18
19    /// Builds a set from arbitrary (possibly overlapping, unsorted, empty)
20    /// intervals; an interval with `lo > hi` is empty and dropped.
21    pub fn from_intervals(items: impl IntoIterator<Item = (i128, i128)>) -> Self {
22        let mut v: Vec<(i128, i128)> = items.into_iter().filter(|&(lo, hi)| lo <= hi).collect();
23        v.sort_unstable();
24        let mut out: Vec<(i128, i128)> = Vec::with_capacity(v.len());
25        for (lo, hi) in v {
26            match out.last_mut() {
27                Some(last) if lo <= last.1.saturating_add(1) => {
28                    if hi > last.1 {
29                        last.1 = hi;
30                    }
31                }
32                _ => out.push((lo, hi)),
33            }
34        }
35        IntSet { iv: out }
36    }
37
38    pub fn intervals(&self) -> &[(i128, i128)] {
39        &self.iv
40    }
41
42    pub fn is_empty(&self) -> bool {
43        self.iv.is_empty()
44    }
45
46    pub fn contains(&self, v: i128) -> bool {
47        match self.iv.binary_search_by(|&(lo, _)| lo.cmp(&v)) {
48            Ok(_) => true,
49            Err(0) => false,
50            Err(i) => self.iv[i - 1].1 >= v,
51        }
52    }
53
54    /// Number of integers in the set.
55    pub fn count(&self) -> u128 {
56        self.iv
57            .iter()
58            .map(|&(lo, hi)| (hi - lo) as u128 + 1)
59            .fold(0u128, u128::saturating_add)
60    }
61
62    pub fn union(&self, other: &IntSet) -> IntSet {
63        IntSet::from_intervals(self.iv.iter().chain(other.iv.iter()).copied())
64    }
65
66    /// `self` without the members of `other`.
67    pub fn subtract(&self, other: &IntSet) -> IntSet {
68        let mut out = Vec::new();
69        for &(lo, hi) in &self.iv {
70            let mut cur = lo;
71            let mut done = false;
72            for &(olo, ohi) in &other.iv {
73                if ohi < cur {
74                    continue;
75                }
76                if olo > hi {
77                    break;
78                }
79                if olo > cur {
80                    out.push((cur, olo - 1));
81                }
82                if ohi >= hi {
83                    done = true;
84                    break;
85                }
86                cur = ohi + 1;
87            }
88            if !done {
89                out.push((cur, hi));
90            }
91        }
92        IntSet { iv: out }
93    }
94
95    pub fn intersects(&self, other: &IntSet) -> bool {
96        let (mut i, mut j) = (0, 0);
97        while i < self.iv.len() && j < other.iv.len() {
98            let (alo, ahi) = self.iv[i];
99            let (blo, bhi) = other.iv[j];
100            if ahi < blo {
101                i += 1;
102            } else if bhi < alo {
103                j += 1;
104            } else {
105                return true;
106            }
107        }
108        false
109    }
110
111    /// The set restricted to `[lo, hi]`.
112    pub fn clip(&self, lo: i128, hi: i128) -> IntSet {
113        IntSet::from_intervals(self.iv.iter().filter_map(|&(a, b)| {
114            let (a, b) = (a.max(lo), b.min(hi));
115            (a <= b).then_some((a, b))
116        }))
117    }
118
119    /// The members as individual values, or `None` when there are more than
120    /// `limit` of them.
121    pub fn values(&self, limit: u128) -> Option<Vec<i128>> {
122        if self.count() > limit {
123            return None;
124        }
125        let mut out = Vec::new();
126        for &(lo, hi) in &self.iv {
127            let mut v = lo;
128            while v <= hi {
129                out.push(v);
130                v += 1;
131            }
132        }
133        Some(out)
134    }
135}
136
137#[cfg(test)]
138mod tests {
139    use super::*;
140
141    #[test]
142    fn merges_overlapping_and_adjacent() {
143        let s = IntSet::from_intervals([(5, 7), (1, 2), (3, 4), (6, 9), (20, 20)]);
144        assert_eq!(s.intervals(), &[(1, 9), (20, 20)]);
145        assert_eq!(s.count(), 10);
146    }
147
148    #[test]
149    fn empty_interval_is_dropped() {
150        assert!(IntSet::from_intervals([(3, 2)]).is_empty());
151    }
152
153    #[test]
154    fn contains_on_boundaries() {
155        let s = IntSet::from_intervals([(2, 4), (10, 12)]);
156        for v in [2, 3, 4, 10, 11, 12] {
157            assert!(s.contains(v), "{v}");
158        }
159        for v in [1, 5, 9, 13, -1] {
160            assert!(!s.contains(v), "{v}");
161        }
162    }
163
164    #[test]
165    fn subtract_splits_and_removes() {
166        let a = IntSet::from_intervals([(0, 10)]);
167        let b = IntSet::from_intervals([(0, 1), (5, 6), (10, 20)]);
168        assert_eq!(a.subtract(&b).intervals(), &[(2, 4), (7, 9)]);
169        assert!(a.subtract(&a).is_empty());
170    }
171
172    #[test]
173    fn intersects_and_clip() {
174        let a = IntSet::from_intervals([(0, 3), (10, 12)]);
175        assert!(a.intersects(&IntSet::from_intervals([(3, 5)])));
176        assert!(!a.intersects(&IntSet::from_intervals([(4, 9)])));
177        assert_eq!(a.clip(2, 11).intervals(), &[(2, 3), (10, 11)]);
178    }
179
180    #[test]
181    fn values_respects_limit() {
182        let a = IntSet::from_intervals([(1, 3), (7, 7)]);
183        assert_eq!(a.values(10), Some(vec![1, 2, 3, 7]));
184        assert_eq!(a.values(3), None);
185    }
186}
vj_sim/covergroup/intset.rs

vj_sim/covergroup/
intset.rs
