Skip to main content

ferrochart_core/plugin/
min_max.rs

1//! Range extremes for plugins.
2//!
3//! [`crate::plugin::CustomSeries::extremes`] must be O(log n), because auto
4//! scaling queries the visible range every frame. `MinMaxIndex` gives plugins
5//! the same structure the built-in series use: level 0 keeps the exact f64
6//! values, higher levels keep `(min, max)` of blocks of `2^k` points as f32
7//! rounded outward, so a query covers the true extremes.
8
9use crate::data::lod::{f32_down, f32_up};
10use crate::error::{Error, Result};
11
12/// `(min, max)` pairs of a growing column with O(log n) range queries,
13/// O(log n) `push` and `set_last`.
14///
15/// Pairs with a NaN bound are empty (a gap) and never contribute.
16///
17/// # Examples
18///
19/// ```
20/// use ferrochart_core::plugin::MinMaxIndex;
21///
22/// let mut idx = MinMaxIndex::new();
23/// for (lo, hi) in [(1.0, 2.0), (0.5, 3.0), (f64::NAN, f64::NAN), (2.0, 4.0)] {
24///     idx.push(lo, hi)?;
25/// }
26/// assert_eq!(idx.query(0, 2), Some((0.5, 3.0)));
27/// idx.set_last(-1.0, 0.0);
28/// let (lo, hi) = idx.query(0, 4).unwrap();
29/// assert!(lo <= -1.0 && hi >= 3.0);
30/// assert_eq!(idx.query(2, 3), None);
31/// # Ok::<(), ferrochart_core::Error>(())
32/// ```
33#[derive(Clone, Debug, Default)]
34pub struct MinMaxIndex {
35    /// Exact pairs.
36    base: Vec<(f64, f64)>,
37    /// `levels[k - 1][i]`: block `i` of `2^k` points, outward-rounded.
38    levels: Vec<Vec<(f32, f32)>>,
39}
40
41const EMPTY32: (f32, f32) = (f32::INFINITY, f32::NEG_INFINITY);
42
43fn widen(a: (f32, f32), b: (f32, f32)) -> (f32, f32) {
44    (a.0.min(b.0), a.1.max(b.1))
45}
46
47fn round(p: (f64, f64)) -> (f32, f32) {
48    if p.0.is_nan() || p.1.is_nan() {
49        EMPTY32
50    } else {
51        (f32_down(p.0), f32_up(p.1))
52    }
53}
54
55impl MinMaxIndex {
56    /// An empty index.
57    pub const fn new() -> Self {
58        Self {
59            base: Vec::new(),
60            levels: Vec::new(),
61        }
62    }
63
64    /// Number of pairs.
65    pub fn len(&self) -> usize {
66        self.base.len()
67    }
68
69    /// Whether there are no pairs.
70    pub fn is_empty(&self) -> bool {
71        self.base.is_empty()
72    }
73
74    /// Removes all pairs, keeping the memory.
75    pub fn clear(&mut self) {
76        self.base.clear();
77        for l in &mut self.levels {
78            l.clear();
79        }
80    }
81
82    /// Bytes of heap memory in use.
83    pub fn heap_bytes(&self) -> usize {
84        self.base.capacity() * 16 + self.levels.iter().map(|l| l.capacity() * 8).sum::<usize>()
85    }
86
87    /// Appends a pair (`min`, `max`); NaN in either makes it a gap.
88    ///
89    /// # Errors
90    ///
91    /// [`Error::OutOfMemory`] if memory cannot be reserved.
92    pub fn push(&mut self, min: f64, max: f64) -> Result<()> {
93        self.base.try_reserve(1).map_err(|_| Error::OutOfMemory)?;
94        self.base.push((min, max));
95        let n = self.base.len();
96        let mut k = 1;
97        while n > (1 << (k - 1)) {
98            if self.levels.len() < k {
99                self.levels.try_reserve(1).map_err(|_| Error::OutOfMemory)?;
100                self.levels.push(Vec::new());
101            }
102            let level = &mut self.levels[k - 1];
103            let want = (n - 1) / (1 << k) + 1;
104            if level.len() < want {
105                level.try_reserve(1).map_err(|_| Error::OutOfMemory)?;
106                level.push(EMPTY32);
107            }
108            k += 1;
109        }
110        self.refresh_last();
111        Ok(())
112    }
113
114    /// Replaces the last pair (real-time updates); does nothing when empty.
115    /// Does not allocate.
116    pub fn set_last(&mut self, min: f64, max: f64) {
117        if let Some(last) = self.base.last_mut() {
118            *last = (min, max);
119            self.refresh_last();
120        }
121    }
122
123    /// Recomputes the blocks containing the last point from their children.
124    fn refresh_last(&mut self) {
125        let Some(last) = self.base.len().checked_sub(1) else {
126            return;
127        };
128        for k in 1..=self.levels.len() {
129            let i = last >> k;
130            let child = |j: usize| -> (f32, f32) {
131                if k == 1 {
132                    self.base.get(j).copied().map_or(EMPTY32, round)
133                } else {
134                    self.levels[k - 2].get(j).copied().unwrap_or(EMPTY32)
135                }
136            };
137            let v = widen(child(2 * i), child(2 * i + 1));
138            if let Some(slot) = self.levels[k - 1].get_mut(i) {
139                *slot = v;
140            }
141        }
142    }
143
144    /// Minimum and maximum over pairs `from..to` (clamped to the data);
145    /// `None` if they are all gaps. The interior of the range comes from the
146    /// f32 levels, so the result may be wider than the exact extremes by one
147    /// f32 ulp, never narrower.
148    pub fn query(&self, from: usize, to: usize) -> Option<(f64, f64)> {
149        let (mut a, mut b) = (from, to.min(self.base.len()));
150        let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
151        let mut take = |p: (f64, f64)| {
152            if !(p.0.is_nan() || p.1.is_nan()) {
153                lo = lo.min(p.0);
154                hi = hi.max(p.1);
155            }
156        };
157        let mut k = 0;
158        while a < b {
159            let at = |i: usize| -> (f64, f64) {
160                if k == 0 {
161                    self.base[i]
162                } else {
163                    let (l, h) = self.levels[k - 1][i];
164                    if l > h {
165                        (f64::NAN, f64::NAN)
166                    } else {
167                        (f64::from(l), f64::from(h))
168                    }
169                }
170            };
171            if k > self.levels.len() {
172                break;
173            }
174            if a & 1 == 1 {
175                take(at(a));
176                a += 1;
177            }
178            if b & 1 == 1 {
179                b -= 1;
180                take(at(b));
181            }
182            if a >= b {
183                break;
184            }
185            if k == self.levels.len() {
186                // Top level: the rest is a plain scan of at most two blocks.
187                for i in a..b {
188                    take(at(i));
189                }
190                break;
191            }
192            a >>= 1;
193            b >>= 1;
194            k += 1;
195        }
196        (lo <= hi).then_some((lo, hi))
197    }
198}
199
200#[cfg(test)]
201mod tests {
202    use super::*;
203    use proptest::prelude::*;
204
205    proptest! {
206        #[test]
207        fn queries_cover_the_exact_extremes(
208            pairs in prop::collection::vec((-1e6f64..1e6, 0.0f64..1e3, prop::bool::weighted(0.1)), 1..300),
209            last in (-1e6f64..1e6, 0.0f64..1e3),
210            ranges in prop::collection::vec((0usize..300, 0usize..300), 1..20),
211        ) {
212            let mut idx = MinMaxIndex::new();
213            let mut exact: Vec<(f64, f64)> = Vec::new();
214            for &(lo, w, gap) in &pairs {
215                let p = if gap { (f64::NAN, f64::NAN) } else { (lo, lo + w) };
216                idx.push(p.0, p.1).unwrap();
217                exact.push(p);
218            }
219            idx.set_last(last.0, last.0 + last.1);
220            *exact.last_mut().unwrap() = (last.0, last.0 + last.1);
221            for (x, y) in ranges {
222                let (a, b) = (x.min(y), x.max(y));
223                let want = exact.get(a..b.min(exact.len())).unwrap_or(&[])
224                    .iter()
225                    .filter(|p| !p.0.is_nan())
226                    .fold(None, |acc: Option<(f64, f64)>, p| Some(match acc {
227                        None => *p,
228                        Some(q) => (q.0.min(p.0), q.1.max(p.1)),
229                    }));
230                let got = idx.query(a, b);
231                match (want, got) {
232                    (None, None) => {}
233                    (Some(w), Some(g)) => {
234                        prop_assert!(g.0 <= w.0 && g.1 >= w.1, "{g:?} {w:?}");
235                        prop_assert!(f64::from(f32_down(w.0)) <= g.0 && g.1 <= f64::from(f32_up(w.1)), "{g:?} {w:?}");
236                    }
237                    _ => prop_assert!(false, "{want:?} {got:?}"),
238                }
239            }
240        }
241    }
242}