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

vortex_array/expr/stats/
bound.rs
