use crate::data::lod::{f32_down, f32_up};
use crate::error::{Error, Result};
#[derive(Clone, Debug, Default)]
pub struct MinMaxIndex {
base: Vec<(f64, f64)>,
levels: Vec<Vec<(f32, f32)>>,
}
const EMPTY32: (f32, f32) = (f32::INFINITY, f32::NEG_INFINITY);
fn widen(a: (f32, f32), b: (f32, f32)) -> (f32, f32) {
(a.0.min(b.0), a.1.max(b.1))
}
fn round(p: (f64, f64)) -> (f32, f32) {
if p.0.is_nan() || p.1.is_nan() {
EMPTY32
} else {
(f32_down(p.0), f32_up(p.1))
}
}
impl MinMaxIndex {
pub const fn new() -> Self {
Self {
base: Vec::new(),
levels: Vec::new(),
}
}
pub fn len(&self) -> usize {
self.base.len()
}
pub fn is_empty(&self) -> bool {
self.base.is_empty()
}
pub fn clear(&mut self) {
self.base.clear();
for l in &mut self.levels {
l.clear();
}
}
pub fn heap_bytes(&self) -> usize {
self.base.capacity() * 16 + self.levels.iter().map(|l| l.capacity() * 8).sum::<usize>()
}
pub fn push(&mut self, min: f64, max: f64) -> Result<()> {
self.base.try_reserve(1).map_err(|_| Error::OutOfMemory)?;
self.base.push((min, max));
let n = self.base.len();
let mut k = 1;
while n > (1 << (k - 1)) {
if self.levels.len() < k {
self.levels.try_reserve(1).map_err(|_| Error::OutOfMemory)?;
self.levels.push(Vec::new());
}
let level = &mut self.levels[k - 1];
let want = (n - 1) / (1 << k) + 1;
if level.len() < want {
level.try_reserve(1).map_err(|_| Error::OutOfMemory)?;
level.push(EMPTY32);
}
k += 1;
}
self.refresh_last();
Ok(())
}
pub fn set_last(&mut self, min: f64, max: f64) {
if let Some(last) = self.base.last_mut() {
*last = (min, max);
self.refresh_last();
}
}
fn refresh_last(&mut self) {
let Some(last) = self.base.len().checked_sub(1) else {
return;
};
for k in 1..=self.levels.len() {
let i = last >> k;
let child = |j: usize| -> (f32, f32) {
if k == 1 {
self.base.get(j).copied().map_or(EMPTY32, round)
} else {
self.levels[k - 2].get(j).copied().unwrap_or(EMPTY32)
}
};
let v = widen(child(2 * i), child(2 * i + 1));
if let Some(slot) = self.levels[k - 1].get_mut(i) {
*slot = v;
}
}
}
pub fn query(&self, from: usize, to: usize) -> Option<(f64, f64)> {
let (mut a, mut b) = (from, to.min(self.base.len()));
let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
let mut take = |p: (f64, f64)| {
if !(p.0.is_nan() || p.1.is_nan()) {
lo = lo.min(p.0);
hi = hi.max(p.1);
}
};
let mut k = 0;
while a < b {
let at = |i: usize| -> (f64, f64) {
if k == 0 {
self.base[i]
} else {
let (l, h) = self.levels[k - 1][i];
if l > h {
(f64::NAN, f64::NAN)
} else {
(f64::from(l), f64::from(h))
}
}
};
if k > self.levels.len() {
break;
}
if a & 1 == 1 {
take(at(a));
a += 1;
}
if b & 1 == 1 {
b -= 1;
take(at(b));
}
if a >= b {
break;
}
if k == self.levels.len() {
for i in a..b {
take(at(i));
}
break;
}
a >>= 1;
b >>= 1;
k += 1;
}
(lo <= hi).then_some((lo, hi))
}
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
proptest! {
#[test]
fn queries_cover_the_exact_extremes(
pairs in prop::collection::vec((-1e6f64..1e6, 0.0f64..1e3, prop::bool::weighted(0.1)), 1..300),
last in (-1e6f64..1e6, 0.0f64..1e3),
ranges in prop::collection::vec((0usize..300, 0usize..300), 1..20),
) {
let mut idx = MinMaxIndex::new();
let mut exact: Vec<(f64, f64)> = Vec::new();
for &(lo, w, gap) in &pairs {
let p = if gap { (f64::NAN, f64::NAN) } else { (lo, lo + w) };
idx.push(p.0, p.1).unwrap();
exact.push(p);
}
idx.set_last(last.0, last.0 + last.1);
*exact.last_mut().unwrap() = (last.0, last.0 + last.1);
for (x, y) in ranges {
let (a, b) = (x.min(y), x.max(y));
let want = exact.get(a..b.min(exact.len())).unwrap_or(&[])
.iter()
.filter(|p| !p.0.is_nan())
.fold(None, |acc: Option<(f64, f64)>, p| Some(match acc {
None => *p,
Some(q) => (q.0.min(p.0), q.1.max(p.1)),
}));
let got = idx.query(a, b);
match (want, got) {
(None, None) => {}
(Some(w), Some(g)) => {
prop_assert!(g.0 <= w.0 && g.1 >= w.1, "{g:?} {w:?}");
prop_assert!(f64::from(f32_down(w.0)) <= g.0 && g.1 <= f64::from(f32_up(w.1)), "{g:?} {w:?}");
}
_ => prop_assert!(false, "{want:?} {got:?}"),
}
}
}
}
}