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

vortex_array/stats/
bound.rs
