numeric_domains/
range_set.rs

1use core::ops::Add;
2
3/// A bounded union of at most `K` disjoint, inclusive unsigned intervals.
4///
5/// Operations first compute their exact interval pieces and, when there are
6/// too many, fill the smallest gaps until the result fits. Thus `K` is a
7/// compile-time precision/storage knob.
8///
9/// References:
10/// - GCC's bounded multi-range (`irange`) design:
11///   <https://gcc.gnu.org/pipermail/gcc/2020-September/233620.html>
12/// - Bagnara, Hill, and Zaffanella, "Widening Operators for Powerset Domains":
13///   <https://www.cs.unipr.it/~zaffanella/Papers/Abstracts/Q349>
14#[derive(Debug, Clone, Copy, PartialEq, Eq)]
15pub struct RangeSet<const K: usize = 2> {
16    ranges: [(u64, u64); K],
17    len: usize,
18}
19
20impl<const K: usize> RangeSet<K> {
21    pub const fn empty() -> Self {
22        assert!(K > 0, "a range set needs positive capacity");
23        Self {
24            ranges: [(0, 0); K],
25            len: 0,
26        }
27    }
28
29    pub fn full() -> Self {
30        Self::from_range(0, u64::MAX)
31    }
32
33    pub fn from_value(value: u64) -> Self {
34        Self::from_range(value, value)
35    }
36
37    pub fn from_range(low: u64, high: u64) -> Self {
38        assert!(low <= high, "linear range bounds must be ordered");
39        let mut result = Self::empty();
40        result.ranges[0] = (low, high);
41        result.len = 1;
42        result
43    }
44
45    pub fn ranges(&self) -> &[(u64, u64)] {
46        &self.ranges[..self.len]
47    }
48
49    pub fn is_empty(&self) -> bool {
50        self.len == 0
51    }
52
53    pub fn contains_value(&self, value: u64) -> bool {
54        self.ranges()
55            .iter()
56            .any(|&(low, high)| low <= value && value <= high)
57    }
58
59    pub fn union(self, other: Self) -> Self {
60        let mut pieces = Vec::with_capacity(self.len + other.len);
61        pieces.extend_from_slice(self.ranges());
62        pieces.extend_from_slice(other.ranges());
63        Self::from_pieces(pieces)
64    }
65
66    pub fn intersection(self, other: Self) -> Self {
67        let mut pieces = Vec::with_capacity(self.len * other.len);
68        for &(a, b) in self.ranges() {
69            for &(c, d) in other.ranges() {
70                let low = a.max(c);
71                let high = b.min(d);
72                if low <= high {
73                    pieces.push((low, high));
74                }
75            }
76        }
77        Self::from_pieces(pieces)
78    }
79
80    /// The number of represented values. `2^64` is representable in `u128`.
81    pub fn cardinality(&self) -> u128 {
82        self.ranges()
83            .iter()
84            .map(|&(low, high)| u128::from(high) - u128::from(low) + 1)
85            .sum()
86    }
87
88    fn from_pieces(mut pieces: Vec<(u64, u64)>) -> Self {
89        if pieces.is_empty() {
90            return Self::empty();
91        }
92        pieces.sort_unstable();
93        let mut merged: Vec<(u64, u64)> = Vec::with_capacity(pieces.len());
94        for (low, high) in pieces {
95            if let Some(last) = merged.last_mut() {
96                if low <= last.1.saturating_add(1) {
97                    last.1 = last.1.max(high);
98                    continue;
99                }
100            }
101            merged.push((low, high));
102        }
103
104        while merged.len() > K {
105            let gap = (0..merged.len() - 1)
106                .min_by_key(|&i| u128::from(merged[i + 1].0) - u128::from(merged[i].1) - 1)
107                .expect("more than one interval");
108            let high = merged[gap + 1].1;
109            merged[gap].1 = high;
110            merged.remove(gap + 1);
111        }
112
113        let mut result = Self::empty();
114        result.len = merged.len();
115        result.ranges[..result.len].copy_from_slice(&merged);
116        result
117    }
118
119    fn add_linear(a: (u64, u64), b: (u64, u64), out: &mut Vec<(u64, u64)>) {
120        let low = u128::from(a.0) + u128::from(b.0);
121        let high = u128::from(a.1) + u128::from(b.1);
122        let modulus = 1_u128 << 64;
123        if high - low + 1 >= modulus {
124            out.push((0, u64::MAX));
125        } else if high < modulus {
126            out.push((low as u64, high as u64));
127        } else if low >= modulus {
128            out.push(((low - modulus) as u64, (high - modulus) as u64));
129        } else {
130            out.push((low as u64, u64::MAX));
131            out.push((0, (high - modulus) as u64));
132        }
133    }
134}
135
136impl<const K: usize> Default for RangeSet<K> {
137    fn default() -> Self {
138        Self::full()
139    }
140}
141
142impl<const K: usize> Add for RangeSet<K> {
143    type Output = Self;
144
145    fn add(self, other: Self) -> Self {
146        if self.is_empty() || other.is_empty() {
147            return Self::empty();
148        }
149        let mut pieces = Vec::with_capacity(self.len * other.len * 2);
150        for &left in self.ranges() {
151            for &right in other.ranges() {
152                Self::add_linear(left, right, &mut pieces);
153            }
154        }
155        Self::from_pieces(pieces)
156    }
157}
numeric_domains/range_set.rs

numeric_domains/
range_set.rs
