vortex_array/stats/
bound.rs

1use std::cmp::Ordering;
2
3use vortex_error::{VortexError, VortexResult};
4
5use crate::partial_ord::{partial_max, partial_min};
6use crate::stats::Precision::{Exact, Inexact};
7use crate::stats::{Precision, StatBound};
8
9/// Interpret the value as a lower bound.
10/// These form a partial order over successively more precise bounds
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub struct LowerBound<T>(pub(crate) Precision<T>);
13
14impl<T> LowerBound<T> {
15    pub(crate) fn min_value(self) -> T {
16        self.0.into_inner()
17    }
18}
19
20impl<T> LowerBound<T> {
21    pub fn is_exact(&self) -> bool {
22        self.0.is_exact()
23    }
24}
25
26/// The result of the fallible intersection of two bound, defined to avoid `Option`
27/// `IntersectionResult` mixup.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub enum IntersectionResult<T> {
30    /// An intersection result was found
31    Value(T),
32    /// Values has no intersection.
33    None,
34}
35
36impl<T> IntersectionResult<T> {
37    pub fn ok_or_else<F>(self, err: F) -> VortexResult<T>
38    where
39        F: FnOnce() -> VortexError,
40    {
41        match self {
42            IntersectionResult::Value(v) => Ok(v),
43            IntersectionResult::None => Err(err()),
44        }
45    }
46}
47
48impl<T: PartialOrd + Clone> StatBound<T> for LowerBound<T> {
49    fn lift(value: Precision<T>) -> Self {
50        Self(value)
51    }
52
53    fn union(&self, other: &Self) -> Option<LowerBound<T>> {
54        Some(LowerBound(match (&self.0, &other.0) {
55            (Exact(lhs), Exact(rhs)) => Exact(partial_min(lhs, rhs)?.clone()),
56            (Inexact(lhs), Inexact(rhs)) => Inexact(partial_min(lhs, rhs)?.clone()),
57            (Inexact(lhs), Exact(rhs)) => {
58                if rhs <= lhs {
59                    Exact(rhs.clone())
60                } else {
61                    Inexact(lhs.clone())
62                }
63            }
64            (Exact(lhs), Inexact(rhs)) => {
65                if rhs >= lhs {
66                    Exact(lhs.clone())
67                } else {
68                    Inexact(rhs.clone())
69                }
70            }
71        }))
72    }
73
74    // The join of the smallest intersection of both bounds, this can fail.
75    fn intersection(&self, other: &Self) -> Option<IntersectionResult<LowerBound<T>>> {
76        Some(match (&self.0, &other.0) {
77            (Exact(lhs), Exact(rhs)) => {
78                if lhs == rhs {
79                    IntersectionResult::Value(LowerBound(Exact(lhs.clone())))
80                } else {
81                    // The two intervals do not overlap
82                    IntersectionResult::None
83                }
84            }
85            (Inexact(lhs), Inexact(rhs)) => {
86                IntersectionResult::Value(LowerBound(Inexact(partial_max(lhs, rhs)?.clone())))
87            }
88            (Inexact(lhs), Exact(rhs)) => {
89                if rhs >= lhs {
90                    IntersectionResult::Value(LowerBound(Exact(rhs.clone())))
91                } else {
92                    // The two intervals do not overlap
93                    IntersectionResult::None
94                }
95            }
96            (Exact(lhs), Inexact(rhs)) => {
97                if rhs <= lhs {
98                    IntersectionResult::Value(LowerBound(Exact(lhs.clone())))
99                } else {
100                    // The two intervals do not overlap
101                    IntersectionResult::None
102                }
103            }
104        })
105    }
106
107    fn to_exact(&self) -> Option<&T> {
108        self.0.to_exact()
109    }
110
111    fn into_value(self) -> Precision<T> {
112        self.0
113    }
114}
115
116impl<T: PartialOrd> PartialEq<T> for LowerBound<T> {
117    fn eq(&self, other: &T) -> bool {
118        match &self.0 {
119            Exact(lhs) => lhs == other,
120            _ => false,
121        }
122    }
123}
124
125// We can only compare exact values with values and Precision::inexact values can only be greater than a value
126impl<T: PartialOrd> PartialOrd<T> for LowerBound<T> {
127    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
128        match &self.0 {
129            Exact(lhs) => lhs.partial_cmp(other),
130            Inexact(lhs) => lhs
131                .partial_cmp(other)
132                .and_then(|o| if o == Ordering::Less { None } else { Some(o) }),
133        }
134    }
135}
136
137/// Interpret the value as an upper bound, see `LowerBound` for more details.
138#[derive(Debug, Clone, PartialEq, Eq)]
139pub struct UpperBound<T>(pub(crate) Precision<T>);
140
141impl<T> UpperBound<T> {
142    pub(crate) fn max_value(self) -> T {
143        self.0.into_inner()
144    }
145}
146
147impl<T: PartialOrd + Clone> StatBound<T> for UpperBound<T> {
148    fn lift(value: Precision<T>) -> Self {
149        Self(value)
150    }
151
152    /// The meet or tightest covering bound
153    fn union(&self, other: &Self) -> Option<UpperBound<T>> {
154        Some(UpperBound(match (&self.0, &other.0) {
155            (Exact(lhs), Exact(rhs)) => Exact(partial_max(lhs, rhs)?.clone()),
156            (Inexact(lhs), Inexact(rhs)) => Inexact(partial_max(lhs, rhs)?.clone()),
157            (Inexact(lhs), Exact(rhs)) => {
158                if rhs >= lhs {
159                    Exact(rhs.clone())
160                } else {
161                    Inexact(lhs.clone())
162                }
163            }
164            (Exact(lhs), Inexact(rhs)) => {
165                if rhs <= lhs {
166                    Exact(lhs.clone())
167                } else {
168                    Inexact(rhs.clone())
169                }
170            }
171        }))
172    }
173
174    fn intersection(&self, other: &Self) -> Option<IntersectionResult<UpperBound<T>>> {
175        Some(match (&self.0, &other.0) {
176            (Exact(lhs), Exact(rhs)) => {
177                if lhs == rhs {
178                    IntersectionResult::Value(UpperBound(Exact(lhs.clone())))
179                } else {
180                    // The two intervals do not overlap
181                    IntersectionResult::None
182                }
183            }
184            (Inexact(lhs), Inexact(rhs)) => {
185                IntersectionResult::Value(UpperBound(Inexact(partial_min(lhs, rhs)?.clone())))
186            }
187            (Inexact(lhs), Exact(rhs)) => {
188                if rhs <= lhs {
189                    IntersectionResult::Value(UpperBound(Exact(rhs.clone())))
190                } else {
191                    // The two intervals do not overlap
192                    IntersectionResult::None
193                }
194            }
195            (Exact(lhs), Inexact(rhs)) => {
196                if rhs >= lhs {
197                    IntersectionResult::Value(UpperBound(Exact(lhs.clone())))
198                } else {
199                    // The two intervals do not overlap
200                    IntersectionResult::None
201                }
202            }
203        })
204    }
205
206    fn to_exact(&self) -> Option<&T> {
207        self.0.to_exact()
208    }
209
210    fn into_value(self) -> Precision<T> {
211        self.0
212    }
213}
214
215impl<T: PartialOrd> PartialEq<T> for UpperBound<T> {
216    fn eq(&self, other: &T) -> bool {
217        match &self.0 {
218            Exact(lhs) => lhs == other,
219            _ => false,
220        }
221    }
222}
223
224// We can only compare exact values with values and Precision::inexact values can only be greater than a value
225impl<T: PartialOrd> PartialOrd<T> for UpperBound<T> {
226    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
227        match &self.0 {
228            Exact(lhs) => lhs.partial_cmp(other),
229            Inexact(lhs) => lhs.partial_cmp(other).and_then(|o| {
230                if o == Ordering::Greater {
231                    None
232                } else {
233                    Some(o)
234                }
235            }),
236        }
237    }
238}
239
240#[cfg(test)]
241mod tests {
242    use crate::stats::bound::IntersectionResult;
243    use crate::stats::{LowerBound, Precision, StatBound, UpperBound};
244
245    #[test]
246    fn test_upper_bound_cmp() {
247        let ub = UpperBound(Precision::exact(10i32));
248
249        assert_eq!(ub, 10);
250        assert!(ub > 9);
251        assert!(ub <= 10);
252        assert!(ub <= 10);
253
254        let ub = UpperBound(Precision::inexact(10i32));
255
256        assert_ne!(ub, 10);
257        assert!(ub < 11);
258        // We cannot say anything about a value in the bound.
259        assert!(!(ub >= 9));
260    }
261
262    #[test]
263    fn test_upper_bound_union() {
264        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
265        let ub2 = UpperBound(Precision::exact(12i32));
266
267        assert_eq!(Some(ub2.clone()), ub1.union(&ub2));
268
269        let ub1: UpperBound<i32> = UpperBound(Precision::inexact(10i32));
270        let ub2 = UpperBound(Precision::exact(12i32));
271
272        assert_eq!(Some(ub2.clone()), ub1.union(&ub2));
273
274        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
275        let ub2 = UpperBound(Precision::inexact(12i32));
276
277        assert_eq!(Some(ub2.clone()), ub1.union(&ub2));
278
279        let ub1: UpperBound<i32> = UpperBound(Precision::inexact(10i32));
280        let ub2 = UpperBound(Precision::inexact(12i32));
281
282        assert_eq!(Some(ub2.clone()), ub1.union(&ub2))
283    }
284
285    #[test]
286    fn test_upper_bound_intersection() {
287        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
288        let ub2 = UpperBound(Precision::inexact(12i32));
289
290        assert_eq!(
291            Some(IntersectionResult::Value(ub1.clone())),
292            ub1.intersection(&ub2)
293        );
294
295        let ub1: UpperBound<i32> = UpperBound(Precision::exact(13i32));
296        let ub2 = UpperBound(Precision::inexact(12i32));
297
298        assert_eq!(Some(IntersectionResult::None), ub1.intersection(&ub2));
299    }
300
301    #[test]
302    fn test_lower_bound_intersection() {
303        let lb1: LowerBound<i32> = LowerBound(Precision::exact(12i32));
304        let lb2 = LowerBound(Precision::inexact(10i32));
305
306        assert_eq!(
307            Some(IntersectionResult::Value(lb1.clone())),
308            lb1.intersection(&lb2)
309        );
310
311        let lb1: LowerBound<i32> = LowerBound(Precision::exact(12i32));
312        let lb2 = LowerBound(Precision::inexact(13i32));
313
314        assert_eq!(Some(IntersectionResult::None), lb1.intersection(&lb2));
315    }
316}
vortex_array/stats/bound.rs

vortex_array/stats/
bound.rs
