vortex_array/expr/stats/
bound.rs

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

vortex_array/expr/stats/
bound.rs
