use crate::storage::spatial_page::{BoundingBox, SpatialPage};
use anyhow::{bail, Context, Result};
use std::collections::BTreeMap;
use std::fs::OpenOptions;
use std::io::{Read, Seek, Write};
use std::path::Path;

#[derive(Debug, Clone)]
pub enum OctreeNode {
    Internal {
        bbox: BoundingBox,
        children: Box<[OctreeNode; 8]>,
        depth: u8,
    },
    Leaf {
        bbox: BoundingBox,
        page_indices: Vec<usize>,
        morton_prefix: u64,
        morton_bits: u8,
    },
}

impl OctreeNode {
    pub fn leaf_from_page(
        bbox: BoundingBox,
        page_idx: usize,
        morton_prefix: u64,
        morton_bits: u8,
    ) -> Self {
        OctreeNode::Leaf {
            bbox,
            page_indices: vec![page_idx],
            morton_prefix,
            morton_bits,
        }
    }

    pub fn bbox(&self) -> &BoundingBox {
        match self {
            OctreeNode::Internal { bbox, .. } => bbox,
            OctreeNode::Leaf { bbox, .. } => bbox,
        }
    }

    pub fn is_leaf(&self) -> bool {
        matches!(self, OctreeNode::Leaf { .. })
    }

    pub fn collect_leaves(&self) -> Vec<&OctreeNode> {
        let mut out = vec![];
        self.collect_leaves_into(&mut out);
        out
    }

    fn collect_leaves_into<'a>(&'a self, out: &mut Vec<&'a OctreeNode>) {
        match self {
            OctreeNode::Internal { children, .. } => {
                for ch in children.iter() {
                    ch.collect_leaves_into(out);
                }
            }
            leaf @ OctreeNode::Leaf { .. } => out.push(leaf),
        }
    }

    pub fn collect_page_indices(&self) -> Vec<usize> {
        let mut out = vec![];
        self.collect_page_indices_into(&mut out);
        out
    }

    fn collect_page_indices_into(&self, out: &mut Vec<usize>) {
        match self {
            OctreeNode::Internal { children, .. } => {
                for ch in children.iter() {
                    ch.collect_page_indices_into(out);
                }
            }
            OctreeNode::Leaf { page_indices, .. } => out.extend(page_indices.iter().copied()),
        }
    }
}

// ---------------------------------------------------------------------------
// Octree Builder
// ---------------------------------------------------------------------------

pub fn build_octree(
    pages: &[SpatialPage],
    max_depth: u8,
    max_pages_per_leaf: usize,
) -> Option<OctreeNode> {
    if pages.is_empty() {
        return None;
    }
    let mut gb = pages[0].header.bbox();
    for p in &pages[1..] {
        gb.expand(&p.header.bbox());
    }
    let refs: Vec<(usize, &SpatialPage)> = pages.iter().enumerate().collect();
    _build(&refs, &gb, 0, max_depth, max_pages_per_leaf)
}

fn _build(
    refs: &[(usize, &SpatialPage)],
    bbox: &BoundingBox,
    depth: u8,
    max_depth: u8,
    max_per_leaf: usize,
) -> Option<OctreeNode> {
    if refs.is_empty() {
        return None;
    }
    if depth >= max_depth || refs.len() <= max_per_leaf {
        let prefix = if refs.len() == 1 {
            refs[0].1.header.morton_prefix
        } else {
            common_prefix(refs)
        };
        let bits = if refs.len() == 1 {
            refs[0].1.header.morton_shift
        } else {
            depth * 3
        };
        return Some(OctreeNode::Leaf {
            bbox: *bbox,
            page_indices: refs.iter().map(|(i, _)| *i).collect(),
            morton_prefix: prefix,
            morton_bits: bits,
        });
    }

    let mx = (bbox.min_x + bbox.max_x) / 2.0;
    let my = (bbox.min_y + bbox.max_y) / 2.0;
    let mz = (bbox.min_z + bbox.max_z) / 2.0;

    let octants = [
        BoundingBox::new(bbox.min_x, mx, bbox.min_y, my, bbox.min_z, mz),
        BoundingBox::new(mx, bbox.max_x, bbox.min_y, my, bbox.min_z, mz),
        BoundingBox::new(bbox.min_x, mx, my, bbox.max_y, bbox.min_z, mz),
        BoundingBox::new(mx, bbox.max_x, my, bbox.max_y, bbox.min_z, mz),
        BoundingBox::new(bbox.min_x, mx, bbox.min_y, my, mz, bbox.max_z),
        BoundingBox::new(mx, bbox.max_x, bbox.min_y, my, mz, bbox.max_z),
        BoundingBox::new(bbox.min_x, mx, my, bbox.max_y, mz, bbox.max_z),
        BoundingBox::new(mx, bbox.max_x, my, bbox.max_y, mz, bbox.max_z),
    ];

    let mut groups: [Vec<(usize, &SpatialPage)>; 8] = Default::default();
    for r in refs {
        let pb = r.1.header.bbox();
        let cx = (pb.min_x + pb.max_x) / 2.0;
        let cy = (pb.min_y + pb.max_y) / 2.0;
        let cz = (pb.min_z + pb.max_z) / 2.0;
        let idx = octant_index(cx, cy, cz, mx, my, mz);
        groups[idx as usize].push(*r);
    }

    let maybe_child = |g: &[(usize, &SpatialPage)], b: &BoundingBox| {
        _build(g, b, depth + 1, max_depth, max_per_leaf)
            .map(Box::new)
            .unwrap_or_else(|| {
                Box::new(OctreeNode::Leaf {
                    bbox: *b,
                    page_indices: vec![],
                    morton_prefix: 0,
                    morton_bits: depth * 3,
                })
            })
    };

    Some(OctreeNode::Internal {
        bbox: *bbox,
        children: Box::new([
            *maybe_child(&groups[0], &octants[0]),
            *maybe_child(&groups[1], &octants[1]),
            *maybe_child(&groups[2], &octants[2]),
            *maybe_child(&groups[3], &octants[3]),
            *maybe_child(&groups[4], &octants[4]),
            *maybe_child(&groups[5], &octants[5]),
            *maybe_child(&groups[6], &octants[6]),
            *maybe_child(&groups[7], &octants[7]),
        ]),
        depth,
    })
}

fn octant_index(x: f32, y: f32, z: f32, mx: f32, my: f32, mz: f32) -> u8 {
    (if x >= mx { 1 } else { 0 }) + (if y >= my { 2 } else { 0 }) + (if z >= mz { 4 } else { 0 })
}

fn common_prefix(refs: &[(usize, &SpatialPage)]) -> u64 {
    if refs.is_empty() {
        return 0;
    }
    let mut p = refs[0].1.header.morton_prefix;
    for (_, page) in &refs[1..] {
        p &= page.header.morton_prefix;
    }
    p
}

// ---------------------------------------------------------------------------
// Spatial Query
// ---------------------------------------------------------------------------

pub fn range_query(node: &OctreeNode, query: &BoundingBox) -> Vec<usize> {
    let mut out = vec![];
    _range(node, query, &mut out);
    out
}

fn _range(node: &OctreeNode, query: &BoundingBox, out: &mut Vec<usize>) {
    match node {
        OctreeNode::Internal { bbox, children, .. } => {
            if !bbox.intersects(query) {
                return;
            }
            for ch in children.iter() {
                _range(ch, query, out);
            }
        }
        OctreeNode::Leaf {
            bbox, page_indices, ..
        } => {
            if bbox.intersects(query) {
                out.extend(page_indices.iter().copied());
            }
        }
    }
}

pub fn point_query(node: &OctreeNode, x: f32, y: f32, z: f32) -> Vec<usize> {
    let mut out = vec![];
    _point(node, x, y, z, &mut out);
    out
}

fn _point(node: &OctreeNode, x: f32, y: f32, z: f32, out: &mut Vec<usize>) {
    match node {
        OctreeNode::Internal { bbox, children, .. } => {
            if !bbox.contains_point(x, y, z) {
                return;
            }
            for ch in children.iter() {
                _point(ch, x, y, z, out);
            }
        }
        OctreeNode::Leaf {
            bbox, page_indices, ..
        } => {
            if bbox.contains_point(x, y, z) {
                out.extend(page_indices.iter().copied());
            }
        }
    }
}

// ---------------------------------------------------------------------------
// Dual Graph
// ---------------------------------------------------------------------------

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum DualEdgeType {
    Face,
    Edge,
    Corner,
}

#[derive(Debug, Clone)]
pub struct DualVertex {
    pub leaf_idx: usize,
    pub bbox: BoundingBox,
    pub page_indices: Vec<usize>,
}

#[derive(Debug, Clone)]
pub struct DualGraph {
    pub vertices: Vec<DualVertex>,
    pub adjacency: Vec<Vec<(usize, DualEdgeType)>>,
}

impl DualGraph {
    pub fn from_octree(octree: &OctreeNode) -> Self {
        let leaves = octree.collect_leaves();
        let n = leaves.len();

        let vertices: Vec<DualVertex> = leaves
            .iter()
            .enumerate()
            .map(|(i, leaf)| match leaf {
                OctreeNode::Leaf {
                    bbox, page_indices, ..
                } => DualVertex {
                    leaf_idx: i,
                    bbox: *bbox,
                    page_indices: page_indices.clone(),
                },
                _ => unreachable!(),
            })
            .collect();

        let mut adjacency: Vec<Vec<(usize, DualEdgeType)>> = vec![vec![]; n];

        for i in 0..n {
            for j in (i + 1)..n {
                if let Some(et) = adjacency_type(&vertices[i].bbox, &vertices[j].bbox) {
                    adjacency[i].push((j, et));
                    adjacency[j].push((i, et));
                }
            }
        }

        DualGraph {
            vertices,
            adjacency,
        }
    }

    pub fn bfs(&self, start_idx: usize) -> Vec<usize> {
        use std::collections::{HashSet, VecDeque};
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        if start_idx < self.vertices.len() {
            visited.insert(start_idx);
            queue.push_back(start_idx);
        }
        while let Some(cur) = queue.pop_front() {
            for (nbr, _) in &self.adjacency[cur] {
                if visited.insert(*nbr) {
                    queue.push_back(*nbr);
                }
            }
        }
        visited.into_iter().collect()
    }

    pub fn connected_components(&self) -> Vec<Vec<usize>> {
        let mut visited = vec![false; self.vertices.len()];
        let mut comps = vec![];
        for i in 0..self.vertices.len() {
            if !visited[i] {
                let comp = self.bfs(i);
                for &v in &comp {
                    visited[v] = true;
                }
                comps.push(comp);
            }
        }
        comps
    }
}

fn adjacency_type(a: &BoundingBox, b: &BoundingBox) -> Option<DualEdgeType> {
    use crate::storage::spatial_page::overlaps;
    let dims = overlaps(a, b);
    if dims == 3 {
        Some(DualEdgeType::Face)
    } else if dims == 2 {
        Some(DualEdgeType::Edge)
    } else if dims == 1 {
        Some(DualEdgeType::Corner)
    } else {
        None
    }
}

// ---------------------------------------------------------------------------
// OctreePageStore
// ---------------------------------------------------------------------------

#[derive(Debug, Clone)]
pub struct OctreePageStore {
    pub pages: Vec<SpatialPage>,
    pub octree: OctreeNode,
    pub dual_graph: DualGraph,
    pub morton_index: BTreeMap<u64, usize>,
}

impl OctreePageStore {
    pub fn new(pages: Vec<SpatialPage>, max_depth: u8, max_pages_per_leaf: usize) -> Self {
        let mut morton_index = BTreeMap::new();
        for (i, page) in pages.iter().enumerate() {
            morton_index.insert(page.header.morton_prefix, i);
        }

        let octree = build_octree(&pages, max_depth, max_pages_per_leaf).unwrap_or_else(|| {
            OctreeNode::Leaf {
                bbox: BoundingBox::new(0.0, 1.0, 0.0, 1.0, 0.0, 1.0),
                page_indices: (0..pages.len()).collect(),
                morton_prefix: 0,
                morton_bits: 0,
            }
        });

        let dual_graph = DualGraph::from_octree(&octree);

        Self {
            pages,
            octree,
            dual_graph,
            morton_index,
        }
    }

    pub fn get_page(&self, idx: usize) -> Option<&SpatialPage> {
        self.pages.get(idx)
    }

    pub fn find_by_morton_prefix(&self, prefix: u64) -> Option<&SpatialPage> {
        self.morton_index
            .get(&prefix)
            .and_then(|idx| self.pages.get(*idx))
    }

    pub fn range_query(&self, query: &BoundingBox) -> Vec<usize> {
        range_query(&self.octree, query)
    }

    pub fn point_query(&self, x: f32, y: f32, z: f32) -> Vec<usize> {
        point_query(&self.octree, x, y, z)
    }

    pub fn total_nodes(&self) -> usize {
        self.pages.iter().map(|p| p.nodes.len()).sum()
    }

    pub fn leaf_count(&self) -> usize {
        self.octree.collect_leaves().len()
    }

    pub fn dual_vertex_count(&self) -> usize {
        self.dual_graph.vertices.len()
    }

    pub fn dual_edge_count(&self) -> usize {
        self.dual_graph.adjacency.iter().map(|v| v.len()).sum()
    }

    // ------------------------------------------------------------------
    // Persistence (compact binary, no serde)
    // ------------------------------------------------------------------

    /// Save all pages + octree to a single file at `path`.
    pub fn save<P: AsRef<Path>>(&self, path: P) -> Result<()> {
        let path = path.as_ref();
        let tmp = path.with_extension("tmp");
        self.save_inner(&tmp)?;
        std::fs::rename(&tmp, path)
            .with_context(|| format!("Failed to rename {:?} to {:?}", tmp, path))?;
        Ok(())
    }

    fn save_inner(&self, path: &Path) -> Result<()> {
        let mut file = OpenOptions::new()
            .write(true)
            .create(true)
            .truncate(true)
            .open(path)
            .with_context(|| format!("Failed to open spatial store for writing: {:?}", path))?;

        // ---- File Header (32 bytes) ----
        file.write_all(&OCTREE_STORE_MAGIC.to_le_bytes())?; // 0..4
        file.write_all(&OCTREE_STORE_VERSION.to_le_bytes())?; // 4..8
        file.write_all(&(0u64).to_le_bytes())?; // page_count placeholder 8..16
        file.write_all(&(0u64).to_le_bytes())?; // octree_offset placeholder 16..24
        file.write_all(&(0u64).to_le_bytes())?; // reserved 24..32

        // ---- Pages ----
        let page_count = self.pages.len() as u64;
        let mut page_offsets: Vec<(u64, u32)> = Vec::with_capacity(self.pages.len());

        for page in &self.pages {
            let packed = page.pack()?;
            let len = packed.len() as u32;
            let offset = file.stream_position()?;
            file.write_all(&len.to_le_bytes())?;
            file.write_all(&packed)?;
            page_offsets.push((offset, len));
        }

        // ---- Octree ----
        let octree_offset = file.stream_position()?;
        let mut octree_buf = Vec::with_capacity(4096); // grow as needed
        write_octree(&mut octree_buf, &self.octree);
        file.write_all(&octree_buf)?;

        // ---- Rewrite placeholders ----
        file.seek(std::io::SeekFrom::Start(8))?;
        file.write_all(&page_count.to_le_bytes())?;
        file.write_all(&octree_offset.to_le_bytes())?;

        file.sync_all()?;
        Ok(())
    }

    /// Open a persisted OctreePageStore from `path`.
    pub fn open<P: AsRef<Path>>(
        path: P,
        _max_depth: u8,
        _max_pages_per_leaf: usize,
    ) -> Result<Self> {
        let path = path.as_ref();
        let mut file = OpenOptions::new()
            .read(true)
            .open(path)
            .with_context(|| format!("Failed to open spatial store for reading: {:?}", path))?;

        // ---- Header ----
        let mut header = [0u8; 32];
        file.read_exact(&mut header)?;
        let magic = u32::from_le_bytes(header[0..4].try_into().unwrap());
        let version = u32::from_le_bytes(header[4..8].try_into().unwrap());
        if magic != OCTREE_STORE_MAGIC {
            bail!(
                "Invalid spatial store magic: expected {:#x}, got {:#x}",
                OCTREE_STORE_MAGIC,
                magic
            );
        }
        if version != OCTREE_STORE_VERSION {
            bail!(
                "Unsupported spatial store version: expected {}, got {}",
                OCTREE_STORE_VERSION,
                version
            );
        }
        let page_count = u64::from_le_bytes(header[8..16].try_into().unwrap());
        let octree_offset = u64::from_le_bytes(header[16..24].try_into().unwrap());

        // ---- Pages ----
        let mut pages = Vec::with_capacity(page_count as usize);
        let mut morton_index = BTreeMap::new();

        for i in 0..page_count {
            let offset = file.stream_position()?;
            if offset >= octree_offset {
                // pages section should end at octree_offset
                break;
            }
            let mut len_bytes = [0u8; 4];
            file.read_exact(&mut len_bytes)?;
            let len = u32::from_le_bytes(len_bytes);
            let mut packed = vec![0u8; len as usize];
            file.read_exact(&mut packed)?;
            let page = SpatialPage::unpack(&packed)
                .with_context(|| format!("Failed to unpack spatial page {}", i))?;
            morton_index.insert(page.header.morton_prefix, pages.len());
            pages.push(page);
        }

        // ---- Octree ----
        let remaining = file.metadata()?.len() - octree_offset;
        let mut octree_bytes = vec![0u8; remaining as usize];
        file.seek(std::io::SeekFrom::Start(octree_offset))?;
        file.read_exact(&mut octree_bytes)?;
        let mut slice = octree_bytes.as_slice();
        let octree = read_octree_slice(&mut slice)?;

        let dual_graph = DualGraph::from_octree(&octree);

        Ok(Self {
            pages,
            octree,
            dual_graph,
            morton_index,
        })
    }
}

const OCTREE_STORE_MAGIC: u32 = 0x5350_4744; // "SPGD"
const OCTREE_STORE_VERSION: u32 = 1;

// Read from a byte slice, advancing the cursor. No syscalls.
fn write_octree(buf: &mut Vec<u8>, node: &OctreeNode) {
    match node {
        OctreeNode::Internal {
            bbox,
            children,
            depth,
        } => {
            buf.push(0u8); // tag: Internal
            write_bbox_to_buf(buf, bbox);
            buf.push(*depth);
            for child in children.iter() {
                write_octree(buf, child);
            }
        }
        OctreeNode::Leaf {
            bbox,
            page_indices,
            morton_prefix,
            morton_bits,
        } => {
            buf.push(1u8); // tag: Leaf
            write_bbox_to_buf(buf, bbox);
            buf.extend_from_slice(&morton_prefix.to_le_bytes());
            buf.push(*morton_bits);
            let count = page_indices.len() as u32;
            buf.extend_from_slice(&count.to_le_bytes());
            for &idx in page_indices {
                buf.extend_from_slice(&(idx as u64).to_le_bytes());
            }
        }
    }
}

fn write_bbox_to_buf(buf: &mut Vec<u8>, bbox: &BoundingBox) {
    let BoundingBox {
        min_x,
        max_x,
        min_y,
        max_y,
        min_z,
        max_z,
    } = bbox;
    buf.extend_from_slice(&min_x.to_le_bytes());
    buf.extend_from_slice(&max_x.to_le_bytes());
    buf.extend_from_slice(&min_y.to_le_bytes());
    buf.extend_from_slice(&max_y.to_le_bytes());
    buf.extend_from_slice(&min_z.to_le_bytes());
    buf.extend_from_slice(&max_z.to_le_bytes());
}

// Read from a byte slice, advancing the cursor. No syscalls.
fn read_octree_slice(bytes: &mut &[u8]) -> Result<OctreeNode> {
    if bytes.is_empty() {
        bail!("Unexpected EOF reading octree node");
    }
    let tag = bytes[0];
    *bytes = &bytes[1..];
    let bbox = read_bbox_from_slice(bytes)?;
    if tag == 0 {
        // Internal
        if bytes.is_empty() {
            bail!("Unexpected EOF reading depth");
        }
        let depth = bytes[0];
        *bytes = &bytes[1..];
        let children = Box::new([
            read_octree_slice(bytes)?,
            read_octree_slice(bytes)?,
            read_octree_slice(bytes)?,
            read_octree_slice(bytes)?,
            read_octree_slice(bytes)?,
            read_octree_slice(bytes)?,
            read_octree_slice(bytes)?,
            read_octree_slice(bytes)?,
        ]);
        Ok(OctreeNode::Internal {
            bbox,
            children,
            depth,
        })
    } else {
        // Leaf
        if bytes.len() < 8 {
            bail!("Unexpected EOF reading morton_prefix");
        }
        let morton_prefix = u64::from_le_bytes(bytes[0..8].try_into().unwrap());
        *bytes = &bytes[8..];
        if bytes.is_empty() {
            bail!("Unexpected EOF reading morton_bits");
        }
        let morton_bits = bytes[0];
        *bytes = &bytes[1..];
        if bytes.len() < 4 {
            bail!("Unexpected EOF reading page count");
        }
        let count = u32::from_le_bytes(bytes[0..4].try_into().unwrap()) as usize;
        *bytes = &bytes[4..];
        if bytes.len() < count * 8 {
            bail!("Unexpected EOF reading page_indices");
        }
        let mut page_indices = Vec::with_capacity(count);
        for i in 0..count {
            let b = &bytes[i * 8..i * 8 + 8];
            page_indices.push(u64::from_le_bytes(b.try_into().unwrap()) as usize);
        }
        *bytes = &bytes[count * 8..];
        Ok(OctreeNode::Leaf {
            bbox,
            page_indices,
            morton_prefix,
            morton_bits,
        })
    }
}

fn read_bbox_from_slice(bytes: &mut &[u8]) -> Result<BoundingBox> {
    if bytes.len() < 24 {
        bail!("Unexpected EOF reading bbox");
    }
    let min_x = f32::from_le_bytes(bytes[0..4].try_into().unwrap());
    let max_x = f32::from_le_bytes(bytes[4..8].try_into().unwrap());
    let min_y = f32::from_le_bytes(bytes[8..12].try_into().unwrap());
    let max_y = f32::from_le_bytes(bytes[12..16].try_into().unwrap());
    let min_z = f32::from_le_bytes(bytes[16..20].try_into().unwrap());
    let max_z = f32::from_le_bytes(bytes[20..24].try_into().unwrap());
    *bytes = &bytes[24..];
    Ok(BoundingBox::new(min_x, max_x, min_y, max_y, min_z, max_z))
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use crate::storage::data_structures::NodeRec;
    use crate::storage::spatial_page::SpatialPageHeader;
    use std::collections::HashMap;

    fn make_page(nodes: Vec<NodeRec>, morton_prefix: u64) -> SpatialPage {
        let mut page = SpatialPage {
            header: SpatialPageHeader {
                magic: crate::storage::spatial_page::SPATIAL_PAGE_MAGIC,
                version: crate::storage::spatial_page::SPATIAL_PAGE_VERSION,
                morton_prefix,
                morton_shift: 0,
                node_count: nodes.len() as u16,
                _pad1: [0; 5],
                min_x: f32::MAX,
                max_x: f32::MIN,
                min_y: f32::MAX,
                max_y: f32::MIN,
                min_z: f32::MAX,
                max_z: f32::MIN,
                _pad2: [0; 8],
                property_block_offset: 0,
                property_block_len: 0,
                edge_cluster_offset: 0,
                edge_cluster_len: 0,
                _reserved: [0; 16],
            },
            nodes,
            properties: HashMap::new(),
            edges: vec![],
        };
        let mut bbox = BoundingBox::from_node(&page.nodes[0]);
        for n in &page.nodes[1..] {
            bbox.expand(&BoundingBox::from_node(n));
        }
        page.header.min_x = bbox.min_x;
        page.header.max_x = bbox.max_x;
        page.header.min_y = bbox.min_y;
        page.header.max_y = bbox.max_y;
        page.header.min_z = bbox.min_z;
        page.header.max_z = bbox.max_z;
        page
    }

    fn make_node(id: u64, morton: u64, x: f32, y: f32, z: f32) -> NodeRec {
        NodeRec {
            id,
            morton_code: morton,
            x,
            y,
            z,
            edge_off: 0,
            edge_len: 0,
            flags: 0,
            begin_ts: 1,
            end_ts: 0,
            tx_id: 1,
            visibility: 1,
            _padding: [0; 7],
        }
    }

    #[test]
    fn test_octree_build_empty() {
        let store = OctreePageStore::new(vec![], 3, 1);
        assert_eq!(store.pages.len(), 0);
        assert_eq!(store.leaf_count(), 1);
        assert_eq!(store.dual_vertex_count(), 1);
    }

    #[test]
    fn test_octree_build_single_page() {
        let nodes = vec![
            make_node(1, 0, 0.1, 0.1, 0.1),
            make_node(2, 0, 0.2, 0.2, 0.2),
        ];
        let page = make_page(nodes, 0);
        let store = OctreePageStore::new(vec![page], 3, 1);
        assert_eq!(store.pages.len(), 1);
        assert_eq!(store.total_nodes(), 2);
    }

    #[test]
    fn test_octree_build_multiple_pages() {
        let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0);
        let page2 = make_page(vec![make_node(2, 0, 0.9, 0.9, 0.9)], 0);
        let store = OctreePageStore::new(vec![page1, page2], 4, 1);
        assert_eq!(store.pages.len(), 2);
        assert_eq!(store.dual_vertex_count(), store.leaf_count());
    }

    #[test]
    fn test_range_query() {
        let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0);
        let page2 = make_page(vec![make_node(2, 0, 0.9, 0.9, 0.9)], 0);
        let store = OctreePageStore::new(vec![page1, page2], 4, 1);

        let q1 = BoundingBox::new(0.0, 0.49, 0.0, 0.49, 0.0, 0.49);
        let r1 = store.range_query(&q1);
        assert_eq!(r1.len(), 1);
        assert_eq!(store.get_page(r1[0]).unwrap().nodes[0].id, 1);

        let q2 = BoundingBox::new(0.0, 1.0, 0.0, 1.0, 0.0, 1.0);
        let r2 = store.range_query(&q2);
        assert_eq!(r2.len(), 2);
    }

    #[test]
    fn test_point_query() {
        let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0);
        let page2 = make_page(vec![make_node(2, 0, 0.8, 0.8, 0.8)], 0);
        let store = OctreePageStore::new(vec![page1, page2], 4, 1);
        let r = store.point_query(0.1, 0.1, 0.1);
        assert_eq!(r.len(), 1);
        assert_eq!(store.get_page(r[0]).unwrap().nodes[0].id, 1);
    }

    #[test]
    fn test_dual_graph_connected_components() {
        // Two pages far apart — but dual graph of full octree is always connected.
        let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0);
        let page2 = make_page(vec![make_node(2, 0, 0.9, 0.9, 0.9)], 0);
        let store = OctreePageStore::new(vec![page1, page2], 1, 1); // depth 1 = 8 leaves
        let comps = store.dual_graph.connected_components();
        assert_eq!(comps.len(), 1, "Full octree dual graph is connected");
    }

    #[test]
    fn test_dual_graph_bfs() {
        let nodes1 = vec![make_node(1, 0, 0.1, 0.1, 0.1)];
        let nodes2 = vec![make_node(2, 0, 0.6, 0.1, 0.1)];
        let nodes3 = vec![make_node(3, 0, 0.9, 0.9, 0.9)];

        let page1 = make_page(nodes1, 0);
        let page2 = make_page(nodes2, 0);
        let page3 = make_page(nodes3, 0);

        let store = OctreePageStore::new(vec![page1, page2, page3], 1, 1);

        // BFS from any leaf reaches all leaves because dual graph of full octree is connected.
        let leaf = store
            .dual_graph
            .vertices
            .iter()
            .position(|v| v.page_indices.contains(&0))
            .unwrap();

        let visited = store.dual_graph.bfs(leaf);
        let leaf_count = store.leaf_count();
        assert_eq!(
            visited.len(),
            leaf_count,
            "BFS should reach all leaves in connected dual graph"
        );
    }

    #[test]
    fn test_morton_index_lookup() {
        let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0x1234);
        let store = OctreePageStore::new(vec![page1], 2, 1);
        assert!(store.find_by_morton_prefix(0x1234).is_some());
        assert!(store.find_by_morton_prefix(0x9999).is_none());
    }

    #[test]
    fn test_save_open_roundtrip_multiple_pages() {
        let mut pages = Vec::new();
        for i in 0..100 {
            let mut page = SpatialPage::new((i as u64) << 8, 8);
            page.header.node_count = 2;
            page.header.min_x = i as f32 * 0.1;
            page.header.max_x = i as f32 * 0.1 + 0.1;
            page.header.min_y = 0.0;
            page.header.max_y = 0.1;
            page.header.min_z = 0.0;
            page.header.max_z = 0.1;
            page.nodes = vec![
                make_node(i as u64 * 2, 0, i as f32 * 0.1, 0.0, 0.0),
                make_node(i as u64 * 2 + 1, 0, i as f32 * 0.1 + 0.05, 0.0, 0.0),
            ];
            pages.push(page);
        }
        let store = OctreePageStore::new(pages, 4, 1);

        let tempdir = tempfile::tempdir().unwrap();
        let path = tempdir.path().join("spatial_store_multi.bin");

        store.save(&path).expect("save should succeed");
        let loaded = OctreePageStore::open(&path, 4, 1).expect("open should succeed");

        assert_eq!(loaded.pages.len(), store.pages.len());
        assert_eq!(
            loaded.pages[100 - 1].nodes.len(),
            store.pages[100 - 1].nodes.len()
        );
        assert_eq!(loaded.octree.is_leaf(), store.octree.is_leaf());
    }

    // ── save/open benchmark (run with `cargo test --lib -- --nocapture`) ──
    #[test]
    fn bench_save_open_roundtrip() {
        let counts = [100_usize, 1000, 5000];
        for &count in &counts {
            let mut pages = Vec::with_capacity(count);
            for i in 0..count {
                let x = (i % 100) as f32 * 0.01;
                let y = ((i / 100) % 100) as f32 * 0.01;
                let z = 0.0f32;
                let mut page = SpatialPage::new(i as u64, 8);
                page.header.node_count = 2;
                page.header.min_x = x;
                page.header.max_x = x + 0.01;
                page.header.min_y = y;
                page.header.max_y = y + 0.01;
                page.header.min_z = z;
                page.header.max_z = z + 0.01;
                page.nodes = vec![
                    make_node(i as u64 * 2, 0, x, y, z),
                    make_node(i as u64 * 2 + 1, 0, x + 0.005, y + 0.005, z),
                ];
                pages.push(page);
            }
            let store = OctreePageStore::new(pages, 4, 1);

            let tempdir = tempfile::tempdir().unwrap();
            let path = tempdir.path().join("spatial_bench.bin");

            let t0 = std::time::Instant::now();
            store.save(&path).unwrap();
            let save_us = t0.elapsed().as_micros() as f64;

            let t1 = std::time::Instant::now();
            let loaded = OctreePageStore::open(&path, 4, 1).unwrap();
            let open_us = t1.elapsed().as_micros() as f64;

            assert_eq!(loaded.pages.len(), store.pages.len());

            let total_nodes = count * 2;
            println!(
                "[BENCH] {} pages ({} nodes)  save: {:>8.1} us ({:.1} M nodes/s)  open: {:>8.1} us ({:.1} M nodes/s)",
                count, total_nodes,
                save_us, total_nodes as f64 / (save_us / 1_000_000.0) / 1_000_000.0,
                open_us, total_nodes as f64 / (open_us / 1_000_000.0) / 1_000_000.0,
            );
        }
    }
}
