plozone 0.1.2

//! Octree hole scanner.
//!
//! A *hole* is a voxel that lies inside a zone but contains no octree points —
//! i.e. unsampled volume. Because empty octree regions never subdivide, holes
//! cannot be read off existing nodes; instead the scanner walks a regular
//! virtual grid over the zone's AABB at the target resolution and tests each
//! voxel for occupancy.

use crate::octree::OctreeNode;
use crate::store::ZoneStore;

/// One unsampled voxel inside a zone.
#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize, serde::Deserialize)]
pub struct Hole {
    /// Voxel centre in ENU metres.
    pub center: [f64; 3],
    /// Voxel edge length in metres.
    pub size_m: f64,
    /// Octree depth this voxel corresponds to.
    pub depth: u8,
}

/// Edge length of a virtual voxel at `depth` for the given octree, or `None`
/// if the octree is degenerate.
fn voxel_size(octree: &OctreeNode, depth: u8) -> Option<f64> {
    let v = octree.half_len * 2.0 / (1u64 << depth) as f64;
    (v > 0.0).then_some(v)
}

/// Visit every virtual voxel of `zone_id` at `depth`, calling `f(min, center)`
/// for each voxel whose centre is inside the zone.
fn for_each_zone_voxel<F: FnMut([f64; 3], [f64; 3])>(
    octree: &OctreeNode,
    store: &ZoneStore,
    zone_id: u32,
    depth: u8,
    mut f: F,
) {
    let Some(aabb) = store.zone_aabb(zone_id) else {
        return;
    };
    let Some(voxel) = voxel_size(octree, depth) else {
        return;
    };

    let mut x = aabb[0];
    while x < aabb[3] {
        let mut y = aabb[1];
        while y < aabb[4] {
            let mut z = aabb[2];
            while z < aabb[5] {
                let center = [x + voxel / 2.0, y + voxel / 2.0, z + voxel / 2.0];
                if store.zone_contains(zone_id, center) {
                    f([x, y, z], center);
                }
                z += voxel;
            }
            y += voxel;
        }
        x += voxel;
    }
}

/// All unsampled voxels of `zone_id` at `depth`.
///
/// Walks a regular *virtual* grid over the zone's AABB at the resolution `depth`
/// implies, testing each in-zone voxel against the octree. This deliberately
/// avoids [`OctreeNode::nodes_at_depth`](crate::octree::OctreeNode::nodes_at_depth):
/// empty regions of an adaptive octree never subdivide, so a hole (an *empty*
/// in-zone voxel) has no materialised node to read off. The virtual grid is the
/// only way to enumerate volume the octree never sampled.
#[must_use]
pub fn scan_holes(octree: &OctreeNode, store: &ZoneStore, zone_id: u32, depth: u8) -> Vec<Hole> {
    let Some(voxel) = voxel_size(octree, depth) else {
        return vec![];
    };
    let mut holes = vec![];
    for_each_zone_voxel(octree, store, zone_id, depth, |min, center| {
        let occupied = !octree
            .range_query(min, [min[0] + voxel, min[1] + voxel, min[2] + voxel])
            .is_empty();
        if !occupied {
            holes.push(Hole { center, size_m: voxel, depth });
        }
    });
    holes
}

/// Total number of virtual voxels covering a zone at `depth` (the denominator
/// for coverage percentages).
pub fn voxel_count_in_zone(octree: &OctreeNode, store: &ZoneStore, zone_id: u32, depth: u8) -> usize {
    let mut count = 0;
    for_each_zone_voxel(octree, store, zone_id, depth, |_, _| count += 1);
    count
}

/// Run [`scan_holes`] at several depths.
#[must_use]
pub fn scan_holes_multiscale(
    octree: &OctreeNode,
    store: &ZoneStore,
    zone_id: u32,
    depths: &[u8],
) -> Vec<(u8, Vec<Hole>)> {
    depths.iter().map(|&d| (d, scan_holes(octree, store, zone_id, d))).collect()
}

/// Scan strategy.
#[derive(Debug, Clone, Copy)]
pub enum ScanMode {
    /// Single-pass scan at a shallow `depth` — fast, low resolution.
    Coarse { depth: u8 },
    /// Single-pass scan at a deeper `depth` — slower, high resolution.
    Precise { depth: u8 },
    /// Scan coarse first; refine only if the hole fraction is high enough.
    Adaptive { coarse_depth: u8, refine_depth: u8, min_hole_frac: f64 },
}

/// Outcome of a scan.
#[derive(Debug, Clone)]
pub struct ScanResult {
    pub holes: Vec<Hole>,
    pub coverage_pct: f64,
    pub depth_used: u8,
    pub node_count: usize,
}

/// Run a hole scan over `zone_id` according to `mode`.
#[must_use]
pub fn run_scan(octree: &OctreeNode, store: &ZoneStore, zone_id: u32, mode: &ScanMode) -> ScanResult {
    let scan = |depth: u8| -> ScanResult {
        let holes = scan_holes(octree, store, zone_id, depth);
        let total = voxel_count_in_zone(octree, store, zone_id, depth);
        ScanResult {
            coverage_pct: 100.0 * (1.0 - holes.len() as f64 / total.max(1) as f64),
            node_count: total,
            depth_used: depth,
            holes,
        }
    };

    match mode {
        ScanMode::Coarse { depth } | ScanMode::Precise { depth } => scan(*depth),
        ScanMode::Adaptive { coarse_depth, refine_depth, min_hole_frac } => {
            let coarse = scan(*coarse_depth);
            let frac = coarse.holes.len() as f64 / coarse.node_count.max(1) as f64;
            if frac >= *min_hole_frac {
                scan(*refine_depth)
            } else {
                coarse
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::coord::EnuConverter;
    use crate::zone::{Zone, ZoneEntry};

    /// A 100 m world with a 40 m-radius cylinder zone centred at the origin.
    fn fixture() -> (OctreeNode, ZoneStore) {
        let conv = EnuConverter::new(0.0, 0.0, 0.0);
        let store = ZoneStore::from_entries(
        &[ZoneEntry::new(
            1,
            Zone::Cylinder { center: [0.0, 0.0], radius_m: 40.0, z_min: -5.0, z_max: 5.0 },
        )],
            &conv,
        );
        let octree = OctreeNode::new([0.0; 3], 64.0); // half_len 64 → 128 m world
        (octree, store)
    }

    #[test]
    fn empty_octree_is_all_holes() {
        let (octree, store) = fixture();
        // depth 4 → 128/16 = 8 m voxels.
        let holes = scan_holes(&octree, &store, 1, 4);
        let total = voxel_count_in_zone(&octree, &store, 1, 4);
        assert!(total > 0);
        assert_eq!(holes.len(), total, "no points → every in-zone voxel is a hole");
    }

    #[test]
    fn occupied_voxel_is_not_a_hole() {
        let (mut octree, store) = fixture();
        let total = voxel_count_in_zone(&octree, &store, 1, 4);
        // Fill one in-zone voxel with a point in its strict interior. The origin
        // would land on shared voxel boundaries (range_query is inclusive on
        // both ends) and register in several neighbouring voxels at once.
        octree.insert([4.0, 4.0, -1.0], 1);
        let holes = scan_holes(&octree, &store, 1, 4);
        assert_eq!(holes.len(), total - 1, "exactly one voxel now occupied");
    }

    #[test]
    fn unknown_zone_yields_nothing() {
        let (octree, store) = fixture();
        assert!(scan_holes(&octree, &store, 99, 4).is_empty());
        assert_eq!(voxel_count_in_zone(&octree, &store, 99, 4), 0);
    }

    #[test]
    fn coverage_full_when_no_holes() {
        let (mut octree, store) = fixture();
        // Densely fill the whole zone footprint so every voxel is occupied.
        let voxel = octree.half_len * 2.0 / (1u64 << 4) as f64;
        let mut x = -40.0;
        while x <= 40.0 {
            let mut y = -40.0;
            while y <= 40.0 {
                octree.insert([x, y, 0.0], 64);
                y += voxel / 2.0;
            }
            x += voxel / 2.0;
        }
        let res = run_scan(&octree, &store, 1, &ScanMode::Coarse { depth: 4 });
        assert!(res.coverage_pct > 99.0, "expected near-full coverage, got {}", res.coverage_pct);
    }

    #[test]
    fn adaptive_refines_when_sparse() {
        let (octree, store) = fixture();
        // Empty octree → 100% holes → fraction 1.0 ≥ threshold → refine.
        let res = run_scan(
            &octree,
            &store,
            1,
            &ScanMode::Adaptive { coarse_depth: 3, refine_depth: 5, min_hole_frac: 0.5 },
        );
        assert_eq!(res.depth_used, 5, "should have refined to depth 5");
    }

    #[test]
    fn multiscale_returns_each_depth() {
        let (octree, store) = fixture();
        let out = scan_holes_multiscale(&octree, &store, 1, &[3, 4]);
        assert_eq!(out.len(), 2);
        assert_eq!(out[0].0, 3);
        assert_eq!(out[1].0, 4);
        // Finer depth → more (smaller) voxels → more holes for an empty octree.
        assert!(out[1].1.len() > out[0].1.len());
    }
}