//! Node ordering strategies for graph contraction.
//!
//! To achieve optimal query performance, the graph must be contracted in an order that
//! minimizes the introduction of new shortcut edges and keeps the elimination tree shallow.
//!
//! This module leverages the METIS graph partitioning library via `metis_sys` to compute
//! a Nested Dissection ordering. This produces significantly better contraction hierarchies
//! than simple degree-based heuristics, especially for large, real-world road networks.

use crate::cch::{Cch, CchGraph};

impl Cch {
    pub fn get_metis_order<G: CchGraph>(graph: &G) -> Vec<u32> {
        let n = graph.num_nodes();
        let mut xadj: Vec<metis_sys::idx_t> = Vec::with_capacity(n + 1);
        let mut adjncy: Vec<metis_sys::idx_t> = Vec::new();

        let mut temp_adj = vec![vec![]; n];
        for u in 0..n {
            for v in graph.neighbors(u as u32) {
                let v = v as usize;
                if u != v {
                    temp_adj[u].push(v as metis_sys::idx_t);
                    temp_adj[v].push(u as metis_sys::idx_t);
                }
            }
        }

        xadj.push(0);
        for neighbors in temp_adj.iter_mut().take(n) {
            neighbors.sort_unstable();
            neighbors.dedup();
            for &mut v in neighbors {
                adjncy.push(v);
            }
            xadj.push(adjncy.len() as metis_sys::idx_t);
        }

        let mut perm = vec![0 as metis_sys::idx_t; n];
        let mut iperm = vec![0 as metis_sys::idx_t; n];
        let mut nvtxs = n as metis_sys::idx_t;

        if !adjncy.is_empty() {
            unsafe {
                metis_sys::METIS_NodeND(
                    &mut nvtxs,
                    xadj.as_mut_ptr(),
                    adjncy.as_mut_ptr(),
                    std::ptr::null_mut(),
                    std::ptr::null_mut(),
                    perm.as_mut_ptr(),
                    iperm.as_mut_ptr(),
                );
            }
        } else {
            return (0..n as u32).collect();
        }

        iperm.into_iter().map(|x| x as u32).collect()
    }
}
