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.partial_cmp(other).filter(|&o| o != Ordering::Less),
143            Absent => None,
144        }
145    }
146}
147
148/// Interpret the value as an upper bound, see `LowerBound` for more details.
149#[derive(Debug, Clone, PartialEq, Eq)]
150pub struct UpperBound<T>(pub(crate) Precision<T>);
151
152impl<T> UpperBound<T> {
153    pub(crate) fn max_value(self) -> Option<T> {
154        self.0.into_inner()
155    }
156}
157
158impl<T: PartialOrd + Clone> StatBound<T> for UpperBound<T> {
159    fn lift(value: Precision<T>) -> Self {
160        Self(value)
161    }
162
163    /// The meet or tightest covering bound
164    fn union(&self, other: &Self) -> Option<UpperBound<T>> {
165        Some(UpperBound(match (&self.0, &other.0) {
166            (Exact(lhs), Exact(rhs)) => Exact(partial_max(lhs, rhs)?.clone()),
167            (Inexact(lhs), Inexact(rhs)) => Inexact(partial_max(lhs, rhs)?.clone()),
168            (Inexact(lhs), Exact(rhs)) => {
169                if rhs >= lhs {
170                    Exact(rhs.clone())
171                } else {
172                    Inexact(lhs.clone())
173                }
174            }
175            (Exact(lhs), Inexact(rhs)) => {
176                if rhs <= lhs {
177                    Exact(lhs.clone())
178                } else {
179                    Inexact(rhs.clone())
180                }
181            }
182            (Absent, _) | (_, Absent) => return None,
183        }))
184    }
185
186    fn intersection(&self, other: &Self) -> Option<IntersectionResult<UpperBound<T>>> {
187        Some(match (&self.0, &other.0) {
188            (Exact(lhs), Exact(rhs)) => {
189                if lhs == rhs {
190                    IntersectionResult::Value(UpperBound(Exact(lhs.clone())))
191                } else {
192                    // The two intervals do not overlap
193                    IntersectionResult::Empty
194                }
195            }
196            (Inexact(lhs), Inexact(rhs)) => {
197                IntersectionResult::Value(UpperBound(Inexact(partial_min(lhs, rhs)?.clone())))
198            }
199            (Inexact(lhs), Exact(rhs)) => {
200                if rhs <= lhs {
201                    IntersectionResult::Value(UpperBound(Exact(rhs.clone())))
202                } else {
203                    // The two intervals do not overlap
204                    IntersectionResult::Empty
205                }
206            }
207            (Exact(lhs), Inexact(rhs)) => {
208                if rhs >= lhs {
209                    IntersectionResult::Value(UpperBound(Exact(lhs.clone())))
210                } else {
211                    // The two intervals do not overlap
212                    IntersectionResult::Empty
213                }
214            }
215            (Absent, _) | (_, Absent) => return None,
216        })
217    }
218
219    fn to_exact(&self) -> Option<&T> {
220        self.0.to_exact()
221    }
222
223    fn into_value(self) -> Precision<T> {
224        self.0
225    }
226}
227
228impl<T: PartialOrd> PartialEq<T> for UpperBound<T> {
229    fn eq(&self, other: &T) -> bool {
230        match &self.0 {
231            Exact(lhs) => lhs == other,
232            _ => false,
233        }
234    }
235}
236
237// We can only compare exact values with values and Precision::inexact values can only be greater than a value
238impl<T: PartialOrd> PartialOrd<T> for UpperBound<T> {
239    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
240        match &self.0 {
241            Exact(lhs) => lhs.partial_cmp(other),
242            Inexact(lhs) => lhs.partial_cmp(other).filter(|&o| o != Ordering::Greater),
243            Absent => None,
244        }
245    }
246}
247
248#[cfg(test)]
249mod tests {
250    use crate::expr::stats::LowerBound;
251    use crate::expr::stats::Precision;
252    use crate::expr::stats::StatBound;
253    use crate::expr::stats::UpperBound;
254    use crate::expr::stats::bound::IntersectionResult;
255
256    #[test]
257    fn test_upper_bound_cmp() {
258        let ub = UpperBound(Precision::exact(10i32));
259
260        assert_eq!(ub, 10);
261        assert!(ub > 9);
262        assert!(ub <= 10);
263
264        let ub = UpperBound(Precision::inexact(10i32));
265
266        assert_ne!(ub, 10);
267        assert!(ub < 11);
268        // We cannot say anything about a value in the bound.
269        assert!(!(ub >= 9));
270    }
271
272    #[test]
273    fn test_upper_bound_union() {
274        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
275        let ub2 = UpperBound(Precision::exact(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::exact(12i32));
281
282        assert_eq!(Some(ub2.clone()), ub1.union(&ub2));
283
284        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
285        let ub2 = UpperBound(Precision::inexact(12i32));
286
287        assert_eq!(Some(ub2.clone()), ub1.union(&ub2));
288
289        let ub1: UpperBound<i32> = UpperBound(Precision::inexact(10i32));
290        let ub2 = UpperBound(Precision::inexact(12i32));
291
292        assert_eq!(Some(ub2.clone()), ub1.union(&ub2))
293    }
294
295    #[test]
296    fn test_upper_bound_intersection() {
297        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
298        let ub2 = UpperBound(Precision::inexact(12i32));
299
300        assert_eq!(
301            Some(IntersectionResult::Value(ub1.clone())),
302            ub1.intersection(&ub2)
303        );
304
305        let ub1: UpperBound<i32> = UpperBound(Precision::exact(13i32));
306        let ub2 = UpperBound(Precision::inexact(12i32));
307
308        assert_eq!(Some(IntersectionResult::Empty), ub1.intersection(&ub2));
309    }
310
311    #[test]
312    fn test_lower_bound_intersection() {
313        let lb1: LowerBound<i32> = LowerBound(Precision::exact(12i32));
314        let lb2 = LowerBound(Precision::inexact(10i32));
315
316        assert_eq!(
317            Some(IntersectionResult::Value(lb1.clone())),
318            lb1.intersection(&lb2)
319        );
320
321        let lb1: LowerBound<i32> = LowerBound(Precision::exact(12i32));
322        let lb2 = LowerBound(Precision::inexact(13i32));
323
324        assert_eq!(Some(IntersectionResult::Empty), lb1.intersection(&lb2));
325    }
326}
vortex_array/expr/stats/bound.rs

vortex_array/expr/stats/
bound.rs
