//! Read-only graph queries. All run against the canonical `BoardGraph`
//! data; derived indices may cache for performance later but the
//! public API is iterator-shaped and order is sorted-by-id (stable).
#![allow(clippy::indexing_slicing)]

use crate::board::{BoardGraph, EdgeKind};
use crate::board::ids::{EdgeId, BoardNodeId};

impl BoardGraph {
    /// Nodes connected to `node` by any incident edge — bidirectional
    /// edges contribute both endpoints; directed edges contribute the
    /// `to` endpoint when `node == from`.
    pub fn neighbors(&self, node: BoardNodeId) -> Vec<BoardNodeId> {
        let mut out: Vec<BoardNodeId> = self.edges.values().filter_map(|kind| match *kind {
            EdgeKind::Bidirectional { a, b } if a == node => Some(b),
            EdgeKind::Bidirectional { a, b } if b == node => Some(a),
            EdgeKind::Directed { from, to } if from == node => Some(to),
            _ => None,
        }).collect();
        out.sort();
        out.dedup();
        out
    }

    /// All edges incident to `node`. Order: ascending EdgeId.
    pub fn edges_at(&self, node: BoardNodeId) -> Vec<EdgeId> {
        let mut out: Vec<EdgeId> = self.edges.iter().filter_map(|(id, kind)| match *kind {
            EdgeKind::Bidirectional { a, b }     if a == node || b == node    => Some(*id),
            EdgeKind::Directed      { from, to } if from == node || to == node => Some(*id),
            _ => None,
        }).collect();
        out.sort();
        out
    }

    /// Endpoints of an edge. For directed edges returns `(from, to)`;
    /// for bidirectional, `(a, b)`.
    pub fn endpoints(&self, edge: EdgeId) -> Option<(BoardNodeId, BoardNodeId)> {
        match self.edges.get(&edge)? {
            EdgeKind::Bidirectional { a, b } => Some((*a, *b)),
            EdgeKind::Directed { from, to } => Some((*from, *to)),
        }
    }

    /// Faces whose boundary contains `node`. Order: ascending FaceId.
    pub fn faces_at_node(&self, node: BoardNodeId) -> Vec<crate::board::ids::FaceId> {
        let mut out: Vec<_> = self.faces.iter()
            .filter(|(_, bnodes)| bnodes.contains(&node))
            .map(|(id, _)| *id)
            .collect();
        out.sort();
        out
    }

    /// Faces whose boundary uses `edge` (i.e., contains both endpoints
    /// as consecutive nodes in the boundary cycle).
    pub fn faces_at_edge(&self, edge: EdgeId) -> Vec<crate::board::ids::FaceId> {
        let Some((from, to)) = self.endpoints(edge) else { return vec![] };
        let mut out: Vec<_> = self.faces.iter().filter_map(|(id, bnodes)| {
            for i in 0..bnodes.len() {
                let cur = bnodes[i];
                let next = bnodes[(i + 1) % bnodes.len()];
                if (cur == from && next == to) || (cur == to && next == from) {
                    return Some(*id);
                }
            }
            None
        }).collect();
        out.sort();
        out
    }

    /// Shortest path (fewest edges) from `from` to `to`, honoring
    /// directionality. Returns the node sequence including both
    /// endpoints; `None` if unreachable.
    pub fn shortest_path(&self, from: BoardNodeId, to: BoardNodeId) -> Option<Vec<BoardNodeId>> {
        if from == to { return Some(vec![from]); }
        use std::collections::{VecDeque, HashMap};
        let mut prev: HashMap<BoardNodeId, BoardNodeId> = HashMap::new();
        let mut q: VecDeque<BoardNodeId> = VecDeque::from([from]);
        let mut seen: std::collections::HashSet<BoardNodeId> = std::collections::HashSet::from([from]);
        while let Some(n) = q.pop_front() {
            if n == to {
                // Reconstruct path.
                let mut path = vec![to];
                let mut cur = to;
                while let Some(&p) = prev.get(&cur) {
                    path.push(p);
                    cur = p;
                }
                path.reverse();
                return Some(path);
            }
            for nb in self.neighbors(n) {
                if seen.insert(nb) {
                    prev.insert(nb, n);
                    q.push_back(nb);
                }
            }
        }
        None
    }

    /// Breadth-first traversal yielding `(node, depth)` pairs starting
    /// at `start` (depth 0), up to and including `max_depth`.
    pub fn bfs_from(&self, start: BoardNodeId, max_depth: u32) -> impl Iterator<Item = (BoardNodeId, u32)> + '_ {
        // Materialize so we don't have to track lifetimes through a closure.
        use std::collections::{VecDeque, HashSet};
        let mut out = Vec::new();
        let mut q: VecDeque<(BoardNodeId, u32)> = VecDeque::from([(start, 0)]);
        let mut seen: HashSet<BoardNodeId> = HashSet::from([start]);
        while let Some((n, depth)) = q.pop_front() {
            out.push((n, depth));
            if depth >= max_depth { continue; }
            for nb in self.neighbors(n) {
                if seen.insert(nb) {
                    q.push_back((nb, depth + 1));
                }
            }
        }
        out.into_iter()
    }

    /// Faces sharing at least one edge with `face`. Order: ascending FaceId.
    pub fn adjacent_faces(&self, face: crate::board::ids::FaceId) -> Vec<crate::board::ids::FaceId> {
        let Some(bnodes) = self.faces.get(&face) else { return vec![] };
        let bnodes = bnodes.clone();
        let mut out: Vec<_> = self.faces.iter()
            .filter(|(other_id, _)| **other_id != face)
            .filter(|(_, other_bnodes)| {
                for i in 0..bnodes.len() {
                    let cur = bnodes[i];
                    let next = bnodes[(i + 1) % bnodes.len()];
                    for j in 0..other_bnodes.len() {
                        let oc = other_bnodes[j];
                        let on = other_bnodes[(j + 1) % other_bnodes.len()];
                        if (cur == oc && next == on) || (cur == on && next == oc) {
                            return true;
                        }
                    }
                }
                false
            })
            .map(|(id, _)| *id)
            .collect();
        out.sort();
        out
    }
}

// PTM-1 phase A: implement the read-only `BoardGraphView` trait so SDK
// behavioural code (movement patterns, distance, predicate eval) and
// extension crates can consume the graph without depending on the
// concrete `BoardGraph` type.
impl crate::board::BoardGraphView for crate::board::BoardGraph {
    fn node_count(&self) -> usize { self.node_count() }
    fn edge_count(&self) -> usize { self.edge_count() }
    fn face_count(&self) -> usize { self.face_count() }
    fn contains_node(&self, id: BoardNodeId) -> bool { self.contains_node(id) }
    fn contains_edge(&self, id: EdgeId) -> bool { self.contains_edge(id) }
    fn contains_face(&self, id: crate::board::ids::FaceId) -> bool { self.contains_face(id) }
    fn neighbors(&self, node: BoardNodeId) -> Vec<BoardNodeId> { self.neighbors(node) }
    fn edges_at(&self, node: BoardNodeId) -> Vec<EdgeId> { self.edges_at(node) }
    fn endpoints(&self, edge: EdgeId) -> Option<(BoardNodeId, BoardNodeId)> { self.endpoints(edge) }
    fn face_bounding(&self, id: crate::board::ids::FaceId) -> Option<Vec<BoardNodeId>> {
        self.face_bounding(id).cloned()
    }
    fn faces_at_node(&self, node: BoardNodeId) -> Vec<crate::board::ids::FaceId> { self.faces_at_node(node) }
    fn faces_at_edge(&self, edge: EdgeId) -> Vec<crate::board::ids::FaceId> { self.faces_at_edge(edge) }
    fn adjacent_faces(&self, face: crate::board::ids::FaceId) -> Vec<crate::board::ids::FaceId> {
        self.adjacent_faces(face)
    }
    fn version(&self) -> u64 { self.version() }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn neighbors_reflect_bidirectional_edges() {
        let mut g = BoardGraph::new();
        let a = g.add_node();
        let b = g.add_node();
        let c = g.add_node();
        g.add_bidirectional_edge(a, b);
        g.add_bidirectional_edge(b, c);
        assert_eq!(g.neighbors(a), vec![b]);
        assert_eq!(g.neighbors(b), vec![a, c]);
        assert_eq!(g.neighbors(c), vec![b]);
    }

    #[test]
    fn neighbors_honor_directionality() {
        let mut g = BoardGraph::new();
        let a = g.add_node();
        let b = g.add_node();
        g.add_directed_edge(a, b);
        // a → b: a's neighbor is b; b has no outgoing neighbor.
        assert_eq!(g.neighbors(a), vec![b]);
        assert_eq!(g.neighbors(b), Vec::<BoardNodeId>::new());
    }

    #[test]
    fn endpoints_round_trip() {
        let mut g = BoardGraph::new();
        let a = g.add_node();
        let b = g.add_node();
        let bi = g.add_bidirectional_edge(a, b);
        let dir = g.add_directed_edge(a, b);
        assert_eq!(g.endpoints(bi), Some((a, b)));
        assert_eq!(g.endpoints(dir), Some((a, b)));
    }

    use crate::board::ids::FaceId;

    fn build_two_triangles_sharing_edge() -> (BoardGraph, BoardNodeId, BoardNodeId, BoardNodeId, BoardNodeId, FaceId, FaceId) {
        // Diamond: a-b-c plus a-d-c, where a-c is the shared edge.
        let mut g = BoardGraph::new();
        let a = g.add_node();
        let b = g.add_node();
        let c = g.add_node();
        let d = g.add_node();
        g.add_bidirectional_edge(a, b);
        g.add_bidirectional_edge(b, c);
        g.add_bidirectional_edge(a, c);
        g.add_bidirectional_edge(a, d);
        g.add_bidirectional_edge(d, c);
        let f1 = g.add_face(vec![a, b, c]).unwrap();
        let f2 = g.add_face(vec![a, c, d]).unwrap();
        (g, a, b, c, d, f1, f2)
    }

    #[test]
    fn faces_at_node_lists_all_incident_faces() {
        let (g, a, _b, _c, _d, f1, f2) = build_two_triangles_sharing_edge();
        let mut faces = g.faces_at_node(a);
        faces.sort();
        assert_eq!(faces, vec![f1, f2]);
    }

    #[test]
    fn adjacent_faces_lists_face_sharing_an_edge() {
        let (g, _a, _b, _c, _d, f1, f2) = build_two_triangles_sharing_edge();
        assert_eq!(g.adjacent_faces(f1), vec![f2]);
        assert_eq!(g.adjacent_faces(f2), vec![f1]);
    }

    #[test]
    fn shortest_path_finds_2hop() {
        let mut g = BoardGraph::new();
        let a = g.add_node();
        let b = g.add_node();
        let c = g.add_node();
        g.add_bidirectional_edge(a, b);
        g.add_bidirectional_edge(b, c);
        let path = g.shortest_path(a, c).unwrap();
        assert_eq!(path, vec![a, b, c]);
    }

    #[test]
    fn shortest_path_returns_none_when_disconnected() {
        let mut g = BoardGraph::new();
        let a = g.add_node();
        let b = g.add_node();
        // No edge between them.
        assert!(g.shortest_path(a, b).is_none());
    }

    #[test]
    fn shortest_path_honors_directionality() {
        let mut g = BoardGraph::new();
        let a = g.add_node();
        let b = g.add_node();
        let c = g.add_node();
        g.add_directed_edge(a, b);
        g.add_directed_edge(b, c);
        // a → b → c: forward path exists.
        assert_eq!(g.shortest_path(a, c), Some(vec![a, b, c]));
        // c → a: no reverse direction.
        assert!(g.shortest_path(c, a).is_none());
    }

    #[test]
    fn bfs_from_yields_depth() {
        let mut g = BoardGraph::new();
        let a = g.add_node();
        let b = g.add_node();
        let c = g.add_node();
        g.add_bidirectional_edge(a, b);
        g.add_bidirectional_edge(b, c);
        let mut visited: Vec<_> = g.bfs_from(a, 5).collect();
        visited.sort_by_key(|(n, _)| *n);
        assert_eq!(visited, vec![(a, 0), (b, 1), (c, 2)]);
    }
}
