ferrochart_core/plugin/
min_max.rs1use crate::data::lod::{f32_down, f32_up};
10use crate::error::{Error, Result};
11
12#[derive(Clone, Debug, Default)]
34pub struct MinMaxIndex {
35 base: Vec<(f64, f64)>,
37 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 pub const fn new() -> Self {
58 Self {
59 base: Vec::new(),
60 levels: Vec::new(),
61 }
62 }
63
64 pub fn len(&self) -> usize {
66 self.base.len()
67 }
68
69 pub fn is_empty(&self) -> bool {
71 self.base.is_empty()
72 }
73
74 pub fn clear(&mut self) {
76 self.base.clear();
77 for l in &mut self.levels {
78 l.clear();
79 }
80 }
81
82 pub fn heap_bytes(&self) -> usize {
84 self.base.capacity() * 16 + self.levels.iter().map(|l| l.capacity() * 8).sum::<usize>()
85 }
86
87 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 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 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 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 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}