//! Pattern-match helpers — given a graph, recognize whether it
//! matches a known regular topology and return its parameters.
//! Used by the universal renderer to short-circuit force-directed
//! layout for common cases.

use crate::board::{BoardGraph, BoardBuilder};

/// If `g` is a regular square grid, return `(cols, rows)`.
pub fn detect_square_grid(g: &BoardGraph) -> Option<(u32, u32)> {
    // For a square_grid(c, r): node_count = (c+1)*(r+1), face_count = c*r,
    // every face has exactly 4 bounding nodes.
    if g.face_count() == 0 { return None; }
    if g.faces.values().any(|b| b.len() != 4) { return None; }
    // Candidate: solve cols/rows from counts.
    let nc = g.node_count();
    let fc = g.face_count();
    for c in 1..=64u32 {
        for r in 1..=64u32 {
            if (c as usize + 1) * (r as usize + 1) == nc && (c as usize * r as usize) == fc {
                // Round-trip — compare with a canonical builder.
                let canonical = BoardBuilder::square_grid(c, r);
                if canonical.graph.node_count() == nc
                    && canonical.graph.edge_count() == g.edge_count()
                    && canonical.graph.face_count() == fc
                {
                    return Some((c, r));
                }
            }
        }
    }
    None
}

/// If `g` is a hex grid, return the radius R.
/// A `hex_grid(R)` has `face_count = 1 + 3*R*(R+1)` and every face has 6 nodes.
pub fn detect_hex_grid(g: &BoardGraph) -> Option<u32> {
    let fc = g.face_count();
    if fc == 0 { return None; }
    if g.faces.values().any(|b| b.len() != 6) { return None; }
    // Solve R from fc = 1 + 3R(R+1).
    for r in 0u32..=64 {
        let expected = 1 + 3 * (r as usize) * (r as usize + 1);
        if expected == fc {
            // Round-trip — build canonical and compare counts.
            let canonical = BoardBuilder::hex_grid(r);
            if canonical.graph.node_count() == g.node_count()
                && canonical.graph.edge_count() == g.edge_count()
                && canonical.graph.face_count() == fc
            {
                return Some(r);
            }
            return None; // face count matched but other counts didn't
        }
        if expected > fc { return None; }
    }
    None
}

/// If `g` is a triangle grid, return `(rows, cols)`.
/// A `triangle_grid(rows, cols)` has `face_count = 2 * rows * cols`
/// and every face has 3 bounding nodes.
pub fn detect_triangle_grid(g: &BoardGraph) -> Option<(u32, u32)> {
    let fc = g.face_count();
    if fc == 0 { return None; }
    if g.faces.values().any(|b| b.len() != 3) { return None; }
    if !fc.is_multiple_of(2) { return None; }
    let half = fc / 2;
    // Try (rows, cols) factor pairs where rows*cols == half.
    for rows in 1u32..=64 {
        if (rows as usize) > half { break; }
        if !half.is_multiple_of(rows as usize) { continue; }
        let cols = (half / rows as usize) as u32;
        if cols == 0 { continue; }
        let canonical = BoardBuilder::triangle_grid(rows, cols);
        if canonical.graph.node_count() == g.node_count()
            && canonical.graph.edge_count() == g.edge_count()
            && canonical.graph.face_count() == fc
        {
            return Some((rows, cols));
        }
    }
    None
}

/// Linear path: every node has degree ≤ 2; exactly two nodes have
/// degree 1 (the endpoints); the chain is connected.
#[expect(clippy::indexing_slicing, reason = "invariant: endpoints[0] accessed only after endpoints.len() != 2 returns None")]
pub fn detect_linear_path(g: &BoardGraph) -> Option<Vec<crate::board::BoardNodeId>> {
    if g.node_count() < 2 || g.face_count() > 0 { return None; }
    let nodes: Vec<_> = g.nodes.iter().copied().collect();
    let mut endpoints = Vec::new();
    for &n in &nodes {
        let d = g.edges_at(n).len();
        if d == 1 { endpoints.push(n); }
        else if d != 2 { return None; }
    }
    if endpoints.len() != 2 { return None; }
    // Walk from one endpoint.
    let start = endpoints[0];
    let mut path = vec![start];
    let mut cur = start;
    let mut prev: Option<crate::board::BoardNodeId> = None;
    while path.len() < nodes.len() {
        let next = g.neighbors(cur).into_iter().find(|n| Some(*n) != prev)?;
        path.push(next);
        prev = Some(cur);
        cur = next;
    }
    Some(path)
}

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

    #[test]
    fn detects_built_square_grid() {
        let b = BoardBuilder::square_grid(8, 8);
        assert_eq!(detect_square_grid(&b.graph), Some((8, 8)));
    }

    #[test]
    fn rejects_perturbed_grid() {
        let mut b = BoardBuilder::square_grid(4, 4);
        // Add a stray node — should no longer match.
        b.graph.add_node();
        assert_eq!(detect_square_grid(&b.graph), None);
    }

    #[test]
    fn detects_linear_path() {
        let b = BoardBuilder::linear_path(5);
        let path = detect_linear_path(&b.graph).unwrap();
        assert_eq!(path.len(), 5);
    }

    #[test]
    fn detects_built_hex_grid_radius0() {
        let b = BoardBuilder::hex_grid(0);
        assert_eq!(detect_hex_grid(&b.graph), Some(0));
    }

    #[test]
    fn detects_built_hex_grid_radius1() {
        let b = BoardBuilder::hex_grid(1);
        assert_eq!(detect_hex_grid(&b.graph), Some(1));
    }

    #[test]
    fn detects_built_hex_grid_radius2() {
        let b = BoardBuilder::hex_grid(2);
        assert_eq!(detect_hex_grid(&b.graph), Some(2));
    }

    #[test]
    fn rejects_perturbed_hex_grid() {
        let mut b = BoardBuilder::hex_grid(2);
        b.graph.add_node(); // stray node
        assert_eq!(detect_hex_grid(&b.graph), None);
    }

    #[test]
    fn detects_built_triangle_grid_2x2() {
        let b = BoardBuilder::triangle_grid(2, 2);
        assert_eq!(detect_triangle_grid(&b.graph), Some((2, 2)));
    }

    #[test]
    fn detects_built_triangle_grid_3x4() {
        let b = BoardBuilder::triangle_grid(3, 4);
        assert_eq!(detect_triangle_grid(&b.graph), Some((3, 4)));
    }

    #[test]
    fn rejects_perturbed_triangle_grid() {
        let mut b = BoardBuilder::triangle_grid(2, 2);
        b.graph.add_node();
        assert_eq!(detect_triangle_grid(&b.graph), None);
    }

    #[test]
    fn rejects_branching_as_linear() {
        let b = BoardBuilder::branching_path(
            5,
            vec![crate::board::builders::Branch { fork_at: 2, length: 3 }],
        );
        assert!(detect_linear_path(&b.graph).is_none());
    }
}
