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_value()
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    // The meet or tightest covering bound
54    fn union(&self, other: &Self) -> Option<LowerBound<T>> {
55        Some(LowerBound(match (&self.0, &other.0) {
56            (Exact(lhs), Exact(rhs)) => Exact(partial_min(lhs, rhs)?.clone()),
57            (Inexact(lhs), Inexact(rhs)) => Inexact(partial_min(lhs, rhs)?.clone()),
58            (Inexact(lhs), Exact(rhs)) => {
59                if rhs <= lhs {
60                    Exact(rhs.clone())
61                } else {
62                    Inexact(lhs.clone())
63                }
64            }
65            (Exact(lhs), Inexact(rhs)) => {
66                if rhs >= lhs {
67                    Exact(lhs.clone())
68                } else {
69                    Inexact(rhs.clone())
70                }
71            }
72        }))
73    }
74
75    // The join of the smallest intersection of both bounds, this can fail.
76    fn intersection(&self, other: &Self) -> Option<IntersectionResult<LowerBound<T>>> {
77        Some(match (&self.0, &other.0) {
78            (Exact(lhs), Exact(rhs)) => {
79                if lhs == rhs {
80                    IntersectionResult::Value(LowerBound(Exact(lhs.clone())))
81                } else {
82                    // The two intervals do not overlap
83                    IntersectionResult::None
84                }
85            }
86            (Inexact(lhs), Inexact(rhs)) => {
87                IntersectionResult::Value(LowerBound(Inexact(partial_max(lhs, rhs)?.clone())))
88            }
89            (Inexact(lhs), Exact(rhs)) => {
90                if rhs >= lhs {
91                    IntersectionResult::Value(LowerBound(Exact(rhs.clone())))
92                } else {
93                    // The two intervals do not overlap
94                    IntersectionResult::None
95                }
96            }
97            (Exact(lhs), Inexact(rhs)) => {
98                if rhs <= lhs {
99                    IntersectionResult::Value(LowerBound(Exact(rhs.clone())))
100                } else {
101                    // The two intervals do not overlap
102                    IntersectionResult::None
103                }
104            }
105        })
106    }
107
108    fn to_exact(&self) -> Option<&T> {
109        self.0.to_exact()
110    }
111}
112
113impl<T: PartialOrd> PartialEq<T> for LowerBound<T> {
114    fn eq(&self, other: &T) -> bool {
115        match &self.0 {
116            Exact(lhs) => lhs == other,
117            _ => false,
118        }
119    }
120}
121
122// We can only compare exact values with values and Precision::inexact values can only be greater than a value
123impl<T: PartialOrd> PartialOrd<T> for LowerBound<T> {
124    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
125        match &self.0 {
126            Exact(lhs) => lhs.partial_cmp(other),
127            Inexact(lhs) => lhs
128                .partial_cmp(other)
129                .and_then(|o| if o == Ordering::Less { None } else { Some(o) }),
130        }
131    }
132}
133
134/// Interpret the value as an upper bound, see `LowerBound` for more details.
135#[derive(Debug, Clone, PartialEq, Eq)]
136pub struct UpperBound<T>(pub(crate) Precision<T>);
137
138impl<T> UpperBound<T> {
139    pub(crate) fn max_value(self) -> T {
140        self.0.into_value()
141    }
142}
143
144impl<T> UpperBound<T> {
145    pub fn into_value(self) -> Precision<T> {
146        self.0
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
214impl<T: PartialOrd> PartialEq<T> for UpperBound<T> {
215    fn eq(&self, other: &T) -> bool {
216        match &self.0 {
217            Exact(lhs) => lhs == other,
218            _ => false,
219        }
220    }
221}
222
223// We can only compare exact values with values and Precision::inexact values can only be greater than a value
224impl<T: PartialOrd> PartialOrd<T> for UpperBound<T> {
225    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
226        match &self.0 {
227            Exact(lhs) => lhs.partial_cmp(other),
228            Inexact(lhs) => lhs.partial_cmp(other).and_then(|o| {
229                if o == Ordering::Greater {
230                    None
231                } else {
232                    Some(o)
233                }
234            }),
235        }
236    }
237}
238
239#[cfg(test)]
240mod tests {
241    use crate::stats::bound::IntersectionResult;
242    use crate::stats::{Precision, StatBound, UpperBound};
243
244    #[test]
245    fn test_upper_bound_cmp() {
246        let ub = UpperBound(Precision::exact(10i32));
247
248        assert_eq!(ub, 10);
249        assert!(ub > 9);
250        assert!(ub <= 10);
251        assert!(ub <= 10);
252
253        let ub = UpperBound(Precision::inexact(10i32));
254
255        assert_ne!(ub, 10);
256        assert!(ub < 11);
257        // We cannot say anything about a value in the bound.
258        assert!(!(ub >= 9));
259    }
260
261    #[test]
262    fn test_upper_bound_union() {
263        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
264        let ub2 = UpperBound(Precision::exact(12i32));
265
266        assert_eq!(Some(ub2.clone()), ub1.union(&ub2));
267
268        let ub1: UpperBound<i32> = UpperBound(Precision::inexact(10i32));
269        let ub2 = UpperBound(Precision::exact(12i32));
270
271        assert_eq!(Some(ub2.clone()), ub1.union(&ub2));
272
273        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
274        let ub2 = UpperBound(Precision::inexact(12i32));
275
276        assert_eq!(Some(ub2.clone()), ub1.union(&ub2));
277
278        let ub1: UpperBound<i32> = UpperBound(Precision::inexact(10i32));
279        let ub2 = UpperBound(Precision::inexact(12i32));
280
281        assert_eq!(Some(ub2.clone()), ub1.union(&ub2))
282    }
283
284    #[test]
285    fn test_upper_bound_intersection() {
286        let ub1: UpperBound<i32> = UpperBound(Precision::exact(10i32));
287        let ub2 = UpperBound(Precision::inexact(12i32));
288
289        assert_eq!(
290            Some(IntersectionResult::Value(ub1.clone())),
291            ub1.intersection(&ub2)
292        );
293
294        let ub1: UpperBound<i32> = UpperBound(Precision::exact(13i32));
295        let ub2 = UpperBound(Precision::inexact(12i32));
296
297        assert_eq!(Some(IntersectionResult::None), ub1.intersection(&ub2));
298    }
299}
vortex_array/stats/bound.rs

vortex_array/stats/
bound.rs
