numeric_domains/
wrapped.rs

1use core::ops::Add;
2
3use crate::RangeSet;
4
5/// One inclusive interval on the circle of integers modulo `2^64`.
6///
7/// References:
8/// - Gange et al., "Interval Analysis and Machine Arithmetic: Why Signedness
9///   Ignorance Is Bliss": <https://doi.org/10.1145/2693264>
10/// - LLVM's production `ConstantRange` implementation:
11///   <https://llvm.org/doxygen/classllvm_1_1ConstantRange.html>
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub struct WrappedInterval {
14    low: u64,
15    high: u64,
16    empty: bool,
17    full: bool,
18}
19
20impl WrappedInterval {
21    pub const fn empty() -> Self {
22        Self {
23            low: 0,
24            high: 0,
25            empty: true,
26            full: false,
27        }
28    }
29
30    pub const fn full() -> Self {
31        Self {
32            low: 0,
33            high: u64::MAX,
34            empty: false,
35            full: true,
36        }
37    }
38
39    /// Construct the clockwise arc from `low` through `high`, inclusive.
40    /// `low > high` deliberately denotes a wrapping interval.
41    pub const fn new(low: u64, high: u64) -> Self {
42        Self {
43            low,
44            high,
45            empty: false,
46            full: false,
47        }
48    }
49
50    pub const fn from_value(value: u64) -> Self {
51        Self::new(value, value)
52    }
53
54    pub const fn bounds(&self) -> Option<(u64, u64)> {
55        if self.empty {
56            None
57        } else {
58            Some((self.low, self.high))
59        }
60    }
61
62    pub fn is_wrapping(&self) -> bool {
63        !self.empty && !self.full && self.low > self.high
64    }
65
66    pub fn contains_value(&self, value: u64) -> bool {
67        if self.empty {
68            false
69        } else if self.full {
70            true
71        } else if self.low <= self.high {
72            self.low <= value && value <= self.high
73        } else {
74            value >= self.low || value <= self.high
75        }
76    }
77
78    pub fn cardinality(&self) -> u128 {
79        if self.empty {
80            0
81        } else if self.full {
82            1_u128 << 64
83        } else {
84            u128::from(self.high.wrapping_sub(self.low)) + 1
85        }
86    }
87
88    /// Split at the unsigned zero point. The conversion is exact.
89    pub fn as_range_set(&self) -> RangeSet<2> {
90        if self.empty {
91            RangeSet::empty()
92        } else if self.full {
93            RangeSet::full()
94        } else if self.low <= self.high {
95            RangeSet::from_range(self.low, self.high)
96        } else {
97            RangeSet::from_range(self.low, u64::MAX).union(RangeSet::from_range(0, self.high))
98        }
99    }
100}
101
102impl Default for WrappedInterval {
103    fn default() -> Self {
104        Self::full()
105    }
106}
107
108impl Add for WrappedInterval {
109    type Output = Self;
110
111    fn add(self, other: Self) -> Self {
112        if self.empty || other.empty {
113            return Self::empty();
114        }
115        if self.full || other.full || self.cardinality() + other.cardinality() > (1_u128 << 64) {
116            return Self::full();
117        }
118        Self::new(
119            self.low.wrapping_add(other.low),
120            self.high.wrapping_add(other.high),
121        )
122    }
123}
numeric_domains/wrapped.rs

numeric_domains/
wrapped.rs
