//! Path extraction and shortcut unpacking.
//!
//! The query phase returns a path composed of shortcut arcs in the contracted hierarchy.
//! This module recursively unpacks those shortcuts using the `Shortcuts` data generated
//! during the customization phase, yielding the final sequence of original graph nodes.

use crate::cch::Cch;
use crate::cch::customize::Shortcuts;
use crate::cch::query::{Query, QueryResult, QuerySlot};

impl Cch {
    pub fn unpack(&self, rank_path: Vec<u32>, shortcuts: &Shortcuts) -> Vec<u32> {
        if rank_path.len() < 2 {
            return rank_path.into_iter().map(|r| self.order[r as usize]).collect();
        }
        let mut path = Vec::with_capacity(rank_path.len() * 2);
        path.push(self.order[rank_path[0] as usize]);
        rank_path.windows(2).for_each(|w| self.unpack_edge(w[0], w[1], shortcuts, &mut path));
        path
    }

    fn unpack_edge(&self, u: u32, v: u32, sc: &Shortcuts, out: &mut Vec<u32>) {
        let (low, high) = if u < v { (u, v) } else { (v, u) };
        let arc_id = unsafe { self.topology.find_edge_id(low, high).expect("CCH arc must exist") as usize };
        let mid = if u < v { sc.middles[arc_id].up } else { sc.middles[arc_id].down };
        if mid != u32::MAX {
            self.unpack_edge(u, mid, sc, out);
            self.unpack_edge(mid, v, sc, out);
        } else {
            out.push(self.order[v as usize]);
        }
    }

    pub fn query_path(&self, q: &Query, sc: &Shortcuts, res: &QueryResult) -> Vec<u32> {
        let get_path = |start: u32, side: &[QuerySlot]| -> Vec<u32> {
            std::iter::successors(Some(start).filter(|&n| n != u32::MAX), |&curr| {
                let p = unsafe { side.get_unchecked(curr as usize).parent_node };
                Some(p).filter(|&n| n != u32::MAX)
            })
            .collect()
        };
        let mut path = get_path(res.meeting, &q.fw);
        path.reverse();
        let bw_path = get_path(res.meeting, &q.bw);
        path.extend(bw_path.into_iter().skip(1));
        self.unpack(path, sc)
    }
}
