stats/
minmax.rs

1use serde::{Deserialize, Serialize};
2use std::cmp::Ordering;
3use std::fmt;
4
5use crate::Commute;
6
7/// Represents the current sort order of the data.
8#[derive(Clone, Copy, Debug, PartialEq, Eq, Deserialize, Serialize)]
9pub enum SortOrder {
10    Unsorted,
11    Ascending,
12    Descending,
13}
14
15/// A commutative data structure for tracking minimum and maximum values
16/// and detecting sort order in a stream of data.
17#[derive(Clone, Copy, Deserialize, Serialize, Eq, PartialEq)]
18pub struct MinMax<T> {
19    len: u32,
20    min: Option<T>,
21    max: Option<T>,
22    first_value: Option<T>,
23    last_value: Option<T>,
24    ascending_pairs: u32,
25    descending_pairs: u32,
26}
27
28impl<T: PartialOrd + Clone> MinMax<T> {
29    /// Create an empty state where min and max values do not exist.
30    #[must_use]
31    pub fn new() -> MinMax<T> {
32        Default::default()
33    }
34
35    /// Add a sample to the data and track min/max, the sort order & "sortiness".
36    #[inline]
37    pub fn add(&mut self, sample: T) {
38        match self.len {
39            // this comes first because it's the most common case
40            2.. => {
41                if let Some(ref last) = self.last_value {
42                    #[allow(clippy::match_same_arms)]
43                    match sample.partial_cmp(last) {
44                        Some(Ordering::Greater) => self.ascending_pairs += 1,
45                        Some(Ordering::Less) => self.descending_pairs += 1,
46                        // this comes last because it's the least common case
47                        Some(Ordering::Equal) => self.ascending_pairs += 1,
48                        None => {}
49                    }
50                }
51            }
52            0 => {
53                // first sample
54                self.first_value = Some(sample.clone());
55                self.min = Some(sample.clone());
56                self.max = Some(sample);
57                self.len = 1;
58                return;
59            }
60            1 => {
61                // second sample
62                if let Some(ref first) = self.first_value {
63                    match sample.partial_cmp(first) {
64                        Some(Ordering::Greater | Ordering::Equal) => self.ascending_pairs = 1,
65                        Some(Ordering::Less) => self.descending_pairs = 1,
66                        None => {}
67                    }
68                }
69            }
70        }
71
72        // Update min/max
73        if self.min.as_ref().is_none_or(|v| &sample < v) {
74            self.min = Some(sample.clone());
75        } else if self.max.as_ref().is_none_or(|v| &sample > v) {
76            self.max = Some(sample.clone());
77        }
78
79        // Update last value and number of samples
80        self.last_value = Some(sample);
81        self.len += 1;
82    }
83
84    /// Returns the minimum of the data set.
85    ///
86    /// `None` is returned if and only if the number of samples is `0`.
87    #[inline]
88    #[must_use]
89    pub const fn min(&self) -> Option<&T> {
90        self.min.as_ref()
91    }
92
93    /// Returns the maximum of the data set.
94    ///
95    /// `None` is returned if and only if the number of samples is `0`.
96    #[inline]
97    #[must_use]
98    pub const fn max(&self) -> Option<&T> {
99        self.max.as_ref()
100    }
101
102    /// Returns the number of data points.
103    #[inline]
104    #[must_use]
105    pub const fn len(&self) -> usize {
106        self.len as usize
107    }
108
109    /// Returns true if there are no data points.
110    #[inline]
111    #[must_use]
112    pub const fn is_empty(&self) -> bool {
113        self.len == 0
114    }
115
116    /// Returns the current sort order of the data.
117    #[inline]
118    #[must_use]
119    pub fn sort_order(&self) -> SortOrder {
120        match self.sortiness() {
121            1.0 => SortOrder::Ascending,
122            -1.0 => SortOrder::Descending,
123            _ => SortOrder::Unsorted,
124        }
125    }
126
127    /// Calculates a "sortiness" score for the data, indicating how close it is to being sorted.
128    ///
129    /// Returns a value between -1.0 and 1.0:
130    /// * 1.0 indicates perfectly ascending order
131    /// * -1.0 indicates perfectly descending order
132    /// * Values in between indicate the general tendency towards ascending or descending order
133    /// * 0.0 indicates either no clear ordering or empty/single-element collections
134    ///
135    /// # Examples
136    /// ```
137    /// use stats::MinMax;
138    ///
139    /// let mut asc: MinMax<i32> = vec![1, 2, 3, 4, 5].into_iter().collect();
140    /// assert_eq!(asc.sortiness(), 1.0);
141    ///
142    /// let mut desc: MinMax<i32> = vec![5, 4, 3, 2, 1].into_iter().collect();
143    /// assert_eq!(desc.sortiness(), -1.0);
144    ///
145    /// let mut mostly_asc: MinMax<i32> = vec![1, 2, 4, 3, 5].into_iter().collect();
146    /// assert!(mostly_asc.sortiness() > 0.0); // Positive but less than 1.0
147    /// ```
148    #[inline]
149    #[must_use]
150    pub fn sortiness(&self) -> f64 {
151        if let 0 | 1 = self.len {
152            0.0
153        } else {
154            let total_pairs = self.ascending_pairs + self.descending_pairs;
155            if total_pairs == 0 {
156                0.0
157            } else {
158                (self.ascending_pairs as f64 - self.descending_pairs as f64) / total_pairs as f64
159            }
160        }
161    }
162}
163
164impl<T: PartialOrd + Clone> Commute for MinMax<T> {
165    #[inline]
166    fn merge(&mut self, v: MinMax<T>) {
167        self.len += v.len;
168        if self.min.is_none() || (v.min.is_some() && v.min < self.min) {
169            self.min = v.min;
170        }
171        if self.max.is_none() || (v.max.is_some() && v.max > self.max) {
172            self.max = v.max;
173        }
174
175        // Merge pair counts
176        self.ascending_pairs += v.ascending_pairs;
177        self.descending_pairs += v.descending_pairs;
178
179        // Handle merging of first_value and last_value
180        if self.len > 1 && v.len > 0 {
181            if self.first_value.is_none() {
182                self.first_value.clone_from(&v.first_value);
183            }
184            if let (Some(last), Some(v_first)) = (&self.last_value, &v.first_value) {
185                match v_first.partial_cmp(last) {
186                    Some(Ordering::Greater | Ordering::Equal) => self.ascending_pairs += 1,
187                    Some(Ordering::Less) => self.descending_pairs += 1,
188                    None => {}
189                }
190            }
191            self.last_value = v.last_value;
192        }
193    }
194}
195
196impl<T: PartialOrd> Default for MinMax<T> {
197    #[inline]
198    fn default() -> MinMax<T> {
199        MinMax {
200            len: 0,
201            min: None,
202            max: None,
203            first_value: None,
204            last_value: None,
205            ascending_pairs: 0,
206            descending_pairs: 0,
207        }
208    }
209}
210
211#[cfg(debug_assertions)]
212impl<T: fmt::Debug> fmt::Debug for MinMax<T> {
213    #[inline]
214    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
215        match (&self.min, &self.max) {
216            (Some(min), Some(max)) => {
217                let sort_status = if let 0 | 1 = self.len {
218                    SortOrder::Unsorted
219                } else {
220                    let total_pairs = self.ascending_pairs + self.descending_pairs;
221                    if total_pairs == 0 {
222                        SortOrder::Unsorted
223                    } else {
224                        let sortiness = (self.ascending_pairs as f64
225                            - self.descending_pairs as f64)
226                            / total_pairs as f64;
227                        match sortiness {
228                            1.0 => SortOrder::Ascending,
229                            -1.0 => SortOrder::Descending,
230                            _ => SortOrder::Unsorted,
231                        }
232                    }
233                };
234                write!(f, "[{min:?}, {max:?}], sort_order: {sort_status:?}")
235            }
236            (&None, &None) => write!(f, "N/A"),
237            _ => unreachable!(),
238        }
239    }
240}
241
242impl fmt::Display for SortOrder {
243    #[inline]
244    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
245        match self {
246            SortOrder::Unsorted => write!(f, "Unsorted"),
247            SortOrder::Ascending => write!(f, "Ascending"),
248            SortOrder::Descending => write!(f, "Descending"),
249        }
250    }
251}
252
253impl<T: PartialOrd + Clone> FromIterator<T> for MinMax<T> {
254    #[inline]
255    fn from_iter<I: IntoIterator<Item = T>>(it: I) -> MinMax<T> {
256        let mut v = MinMax::new();
257        v.extend(it);
258        v
259    }
260}
261
262impl<T: PartialOrd + Clone> Extend<T> for MinMax<T> {
263    #[inline]
264    fn extend<I: IntoIterator<Item = T>>(&mut self, it: I) {
265        for sample in it {
266            self.add(sample);
267        }
268    }
269}
270
271#[cfg(test)]
272mod test {
273    use super::{MinMax, SortOrder};
274    use crate::Commute;
275
276    #[test]
277    fn minmax() {
278        let minmax: MinMax<u32> = vec![1u32, 4, 2, 3, 10].into_iter().collect();
279        assert_eq!(minmax.min(), Some(&1u32));
280        assert_eq!(minmax.max(), Some(&10u32));
281        assert_eq!(minmax.sort_order(), SortOrder::Unsorted);
282    }
283
284    #[test]
285    fn minmax_sorted_ascending() {
286        let minmax: MinMax<u32> = vec![1u32, 2, 3, 4, 5].into_iter().collect();
287        assert_eq!(minmax.min(), Some(&1u32));
288        assert_eq!(minmax.max(), Some(&5u32));
289        assert_eq!(minmax.sort_order(), SortOrder::Ascending);
290    }
291
292    #[test]
293    fn minmax_sorted_descending() {
294        let minmax: MinMax<u32> = vec![5u32, 4, 3, 2, 1].into_iter().collect();
295        assert_eq!(minmax.min(), Some(&1u32));
296        assert_eq!(minmax.max(), Some(&5u32));
297        assert_eq!(minmax.sort_order(), SortOrder::Descending);
298    }
299
300    #[test]
301    fn minmax_empty() {
302        let minmax: MinMax<u32> = MinMax::new();
303        assert!(minmax.is_empty());
304        assert_eq!(minmax.sort_order(), SortOrder::Unsorted);
305    }
306
307    #[test]
308    fn minmax_merge_empty() {
309        let mut mx1: MinMax<u32> = vec![1, 4, 2, 3, 10].into_iter().collect();
310        assert_eq!(mx1.min(), Some(&1u32));
311        assert_eq!(mx1.max(), Some(&10u32));
312        assert_eq!(mx1.sort_order(), SortOrder::Unsorted);
313
314        mx1.merge(MinMax::default());
315        assert_eq!(mx1.min(), Some(&1u32));
316        assert_eq!(mx1.max(), Some(&10u32));
317        assert_eq!(mx1.sort_order(), SortOrder::Unsorted);
318    }
319
320    #[test]
321    fn minmax_merge_diffsorts() {
322        let mut mx1: MinMax<u32> = vec![1, 2, 2, 2, 3, 3, 4, 10].into_iter().collect();
323        assert_eq!(mx1.min(), Some(&1u32));
324        assert_eq!(mx1.max(), Some(&10u32));
325        assert_eq!(mx1.sort_order(), SortOrder::Ascending);
326
327        let mx2: MinMax<u32> = vec![5, 4, 3, 2, 1].into_iter().collect();
328        assert_eq!(mx2.min(), Some(&1u32));
329        assert_eq!(mx2.max(), Some(&5u32));
330        assert_eq!(mx2.sort_order(), SortOrder::Descending);
331        mx1.merge(mx2);
332        assert_eq!(mx1.min(), Some(&1u32));
333        assert_eq!(mx1.max(), Some(&10u32));
334        assert_eq!(mx1.sort_order(), SortOrder::Unsorted);
335    }
336
337    #[test]
338    fn minmax_merge_asc_sorts() {
339        let mut mx1: MinMax<u32> = vec![2, 2, 2, 5, 10].into_iter().collect();
340        assert_eq!(mx1.min(), Some(&2u32));
341        assert_eq!(mx1.max(), Some(&10u32));
342        assert_eq!(mx1.sort_order(), SortOrder::Ascending);
343
344        let mx2: MinMax<u32> = vec![11, 14, 23, 32, 41].into_iter().collect();
345        assert_eq!(mx2.min(), Some(&11u32));
346        assert_eq!(mx2.max(), Some(&41u32));
347        assert_eq!(mx2.sort_order(), SortOrder::Ascending);
348        mx1.merge(mx2);
349        assert_eq!(mx1.min(), Some(&2u32));
350        assert_eq!(mx1.max(), Some(&41u32));
351        assert_eq!(mx1.sort_order(), SortOrder::Ascending);
352    }
353
354    #[test]
355    fn test_sortiness() {
356        // Test empty
357        let minmax: MinMax<u32> = MinMax::new();
358        assert_eq!(minmax.sortiness(), 0.0);
359
360        // Test single element
361        let minmax: MinMax<u32> = vec![1].into_iter().collect();
362        assert_eq!(minmax.sortiness(), 0.0);
363
364        // Test perfectly ascending
365        let minmax: MinMax<u32> = vec![1, 2, 3, 4, 5].into_iter().collect();
366        assert_eq!(minmax.sortiness(), 1.0);
367
368        // Test perfectly descending
369        let minmax: MinMax<u32> = vec![5, 4, 3, 2, 1].into_iter().collect();
370        assert_eq!(minmax.sortiness(), -1.0);
371
372        // Test all equal
373        let minmax: MinMax<u32> = vec![1, 1, 1, 1].into_iter().collect();
374        assert_eq!(minmax.sortiness(), 1.0); // Equal pairs are considered ascending
375
376        // Test mostly ascending
377        let minmax: MinMax<u32> = vec![1, 2, 4, 3, 5].into_iter().collect();
378        assert!(minmax.sortiness() > 0.0 && minmax.sortiness() < 1.0);
379        assert_eq!(minmax.sortiness(), 0.5); // 2 ascending pairs, 1 descending pair
380
381        // Test mostly descending
382        let minmax: MinMax<u32> = vec![5, 4, 3, 4, 2].into_iter().collect();
383        assert!(minmax.sortiness() < 0.0 && minmax.sortiness() > -1.0);
384        assert_eq!(minmax.sortiness(), -0.5); // 1 ascending pair, 3 descending pairs
385    }
386
387    #[test]
388    fn test_sortiness_merge() {
389        let mut mx1: MinMax<u32> = vec![1, 2, 3].into_iter().collect();
390        let mx2: MinMax<u32> = vec![4, 5, 6].into_iter().collect();
391        assert_eq!(mx1.sortiness(), 1.0);
392        assert_eq!(mx2.sortiness(), 1.0);
393
394        mx1.merge(mx2);
395        assert_eq!(mx1.sortiness(), 1.0); // Should remain perfectly sorted after merge
396
397        let mut mx3: MinMax<u32> = vec![1, 2, 3].into_iter().collect();
398        let mx4: MinMax<u32> = vec![2, 1, 0].into_iter().collect();
399        mx3.merge(mx4);
400        assert_eq!(mx3, vec![1, 2, 3, 2, 1, 0].into_iter().collect());
401        assert!(mx3.sortiness() < 1.0); // Should show mixed sorting after merge
402        assert_eq!(mx3.sortiness(), -0.2);
403    }
404}
stats/minmax.rs

stats/
minmax.rs
