//! Half-edge / DCEL graph (spec §2.3, D2).
//!
//! Construction is two-phase:
//!
//! 1. Caller adds nodes (`add_node`) and roads (`add_road`).
//! 2. The graph runs `rebuild_topology` (called automatically by
//!    `subdivide_all`) which builds half-edges, sorts them at each
//!    vertex by angle, links `next`/`prev`, and extracts faces.

use glam::DVec2;
use slotmap::{new_key_type, Key, SlotMap};

use crate::error::SubdivisionError;
use crate::geometry::{segments_properly_intersect, signed_area, EPS_GEOM};

new_key_type! {
    /// Stable identifier for a graph node (intersection).
    pub struct NodeId;
    /// Stable identifier for a road segment.
    pub struct RoadId;
}

new_key_type! {
    pub(crate) struct HalfEdgeId;
    pub(crate) struct FaceId;
}

#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(crate) struct Node {
    pub pos: DVec2,
    /// Outgoing half-edges sorted CCW by direction angle. Maintained
    /// by `rebuild_topology`.
    pub outgoing: Vec<HalfEdgeId>,
}

#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(crate) struct Road {
    pub a: NodeId,
    pub b: NodeId,
    pub half_a_to_b: HalfEdgeId,
    pub half_b_to_a: HalfEdgeId,
}

#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(crate) struct HalfEdge {
    pub origin: NodeId,
    pub twin: HalfEdgeId,
    pub next: HalfEdgeId,
    pub prev: HalfEdgeId,
    pub face: Option<FaceId>,
    pub road: RoadId,
}

#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(crate) struct Face {
    pub boundary: HalfEdgeId,
    pub is_exterior: bool,
}

/// Planar road graph. Maintains a half-edge data structure with stable
/// IDs across edits.
#[derive(Debug, Clone, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct RoadGraph {
    pub(crate) nodes: SlotMap<NodeId, Node>,
    pub(crate) roads: SlotMap<RoadId, Road>,
    pub(crate) half_edges: SlotMap<HalfEdgeId, HalfEdge>,
    pub(crate) faces: SlotMap<FaceId, Face>,
    /// True after `rebuild_topology`; cleared by any mutation.
    pub(crate) topology_valid: bool,
}

impl RoadGraph {
    /// Empty graph.
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Insert a new node at `pos`. The graph allows two nodes within
    /// `EPS_GEOM` of each other but downstream subdivision will reject
    /// them via the `near_duplicate_nodes` test in §5.
    pub fn add_node(&mut self, pos: DVec2) -> NodeId {
        self.topology_valid = false;
        self.nodes.insert(Node {
            pos,
            outgoing: Vec::new(),
        })
    }

    /// Position of a node, or `None` if the ID has been deleted.
    #[must_use]
    pub fn node_position(&self, id: NodeId) -> Option<DVec2> {
        self.nodes.get(id).map(|n| n.pos)
    }

    /// Iterate over every live node (id, position). Includes isolated
    /// nodes that are not yet connected to any road.
    pub fn nodes(&self) -> impl Iterator<Item = (NodeId, DVec2)> + '_ {
        self.nodes.iter().map(|(id, n)| (id, n.pos))
    }

    /// Insert a road between two existing nodes.
    ///
    /// # Errors
    ///
    /// Returns `InvalidParams` if either node is unknown, the two
    /// nodes are the same, or a duplicate road already exists.
    pub fn add_road(&mut self, a: NodeId, b: NodeId) -> Result<RoadId, SubdivisionError> {
        if a == b {
            return Err(SubdivisionError::InvalidParams(
                "road endpoints must differ".into(),
            ));
        }
        if !self.nodes.contains_key(a) || !self.nodes.contains_key(b) {
            return Err(SubdivisionError::InvalidParams("unknown node id".into()));
        }
        if self.find_road_between(a, b).is_some() {
            return Err(SubdivisionError::InvalidParams(
                "duplicate road between nodes".into(),
            ));
        }
        self.topology_valid = false;
        Ok(self.roads.insert(Road {
            a,
            b,
            half_a_to_b: HalfEdgeId::null(),
            half_b_to_a: HalfEdgeId::null(),
        }))
    }

    /// Iterate over `(RoadId, NodeId, NodeId)` triples — useful for
    /// rendering and for tests.
    pub fn road_endpoints(&self) -> impl Iterator<Item = (RoadId, NodeId, NodeId)> + '_ {
        self.roads.iter().map(|(rid, r)| (rid, r.a, r.b))
    }

    /// Number of roads currently in the graph.
    #[must_use]
    pub fn road_count(&self) -> usize {
        self.roads.len()
    }

    /// Number of nodes currently in the graph.
    #[must_use]
    pub fn node_count(&self) -> usize {
        self.nodes.len()
    }

    /// Find the road between `a` and `b`, in either direction.
    pub(crate) fn find_road_between(&self, a: NodeId, b: NodeId) -> Option<RoadId> {
        self.roads
            .iter()
            .find(|(_, r)| (r.a == a && r.b == b) || (r.a == b && r.b == a))
            .map(|(rid, _)| rid)
    }

    /// Endpoints of a road, in storage order.
    pub(crate) fn road_nodes(&self, rid: RoadId) -> Option<(NodeId, NodeId)> {
        self.roads.get(rid).map(|r| (r.a, r.b))
    }

    /// Build twin/next/prev pointers and extract faces. Idempotent.
    ///
    /// # Errors
    ///
    /// `NonPlanarGraph` if two non-incident roads cross. `OpenBlock`
    /// if face traversal fails.
    pub fn rebuild_topology(&mut self) -> Result<(), SubdivisionError> {
        if self.topology_valid {
            return Ok(());
        }
        self.check_planarity()?;
        self.build_half_edges();
        self.sort_outgoing_by_angle();
        self.link_next_and_prev();
        self.extract_faces()?;
        self.topology_valid = true;
        Ok(())
    }

    fn check_planarity(&self) -> Result<(), SubdivisionError> {
        let segs: Vec<(RoadId, DVec2, DVec2)> = self
            .roads
            .iter()
            .map(|(rid, r)| (rid, self.nodes[r.a].pos, self.nodes[r.b].pos))
            .collect();
        let road_endpts: Vec<(NodeId, NodeId)> = self.roads.values().map(|r| (r.a, r.b)).collect();
        for (i, &(_, p1, p2)) in segs.iter().enumerate() {
            for j in (i + 1)..segs.len() {
                let (_, p3, p4) = segs[j];
                let (a1, b1) = road_endpts[i];
                let (a2, b2) = road_endpts[j];
                // skip pairs that share a node — they meet legally
                if a1 == a2 || a1 == b2 || b1 == a2 || b1 == b2 {
                    continue;
                }
                if segments_properly_intersect(p1, p2, p3, p4) {
                    // Pick the closer of (a2, b2) for the error
                    // message; either is informative.
                    return Err(SubdivisionError::NonPlanarGraph(a2));
                }
            }
        }
        Ok(())
    }

    fn build_half_edges(&mut self) {
        // Clear prior topology.
        self.half_edges.clear();
        self.faces.clear();
        for (_, n) in &mut self.nodes {
            n.outgoing.clear();
        }
        let road_keys: Vec<RoadId> = self.roads.keys().collect();
        for rid in road_keys {
            let (a, b) = {
                let r = &self.roads[rid];
                (r.a, r.b)
            };
            let h_ab = self.half_edges.insert(HalfEdge {
                origin: a,
                twin: HalfEdgeId::null(),
                next: HalfEdgeId::null(),
                prev: HalfEdgeId::null(),
                face: None,
                road: rid,
            });
            let h_ba = self.half_edges.insert(HalfEdge {
                origin: b,
                twin: h_ab,
                next: HalfEdgeId::null(),
                prev: HalfEdgeId::null(),
                face: None,
                road: rid,
            });
            self.half_edges[h_ab].twin = h_ba;
            self.nodes[a].outgoing.push(h_ab);
            self.nodes[b].outgoing.push(h_ba);
            let r = &mut self.roads[rid];
            r.half_a_to_b = h_ab;
            r.half_b_to_a = h_ba;
        }
    }

    fn sort_outgoing_by_angle(&mut self) {
        let node_keys: Vec<NodeId> = self.nodes.keys().collect();
        for nid in node_keys {
            let pos = self.nodes[nid].pos;
            let outgoing: Vec<HalfEdgeId> = self.nodes[nid].outgoing.clone();
            let mut with_angles: Vec<(f64, HalfEdgeId)> = Vec::with_capacity(outgoing.len());
            for h in outgoing {
                let twin = self.half_edges[h].twin;
                let target = self.half_edges[twin].origin;
                let dir = self.nodes[target].pos - pos;
                let angle = dir.y.atan2(dir.x);
                with_angles.push((angle, h));
            }
            with_angles.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
            self.nodes[nid].outgoing = with_angles.into_iter().map(|(_, h)| h).collect();
        }
    }

    fn link_next_and_prev(&mut self) {
        let edge_keys: Vec<HalfEdgeId> = self.half_edges.keys().collect();
        for h in edge_keys {
            // For a CCW interior face, h's `next` is the half-edge
            // making the smallest left turn at h.target. Concretely:
            // at v = h.target, scan v's CCW-sorted outgoing list and
            // take the immediate predecessor (CW neighbor) of
            // h.twin. This is the standard DCEL rule.
            let twin = self.half_edges[h].twin;
            let v = self.half_edges[twin].origin;
            let v_outgoing = &self.nodes[v].outgoing;
            let pos_in_v = v_outgoing
                .iter()
                .position(|&x| x == twin)
                .expect("twin must appear in target's outgoing list");
            let next = v_outgoing[(pos_in_v + v_outgoing.len() - 1) % v_outgoing.len()];
            self.half_edges[h].next = next;

            // h.prev = the half-edge whose `.next` is h. That is the
            // CCW *successor* of h in h.origin's outgoing list,
            // taken twin-of.
            let u = self.half_edges[h].origin;
            let u_outgoing = &self.nodes[u].outgoing;
            let pos_in_u = u_outgoing
                .iter()
                .position(|&x| x == h)
                .expect("h must appear in origin's outgoing list");
            let succ = u_outgoing[(pos_in_u + 1) % u_outgoing.len()];
            let prev = self.half_edges[succ].twin;
            self.half_edges[h].prev = prev;
        }
    }

    fn extract_faces(&mut self) -> Result<(), SubdivisionError> {
        let edge_keys: Vec<HalfEdgeId> = self.half_edges.keys().collect();
        for h_start in edge_keys {
            if self.half_edges[h_start].face.is_some() {
                continue;
            }
            // Walk the cycle, capturing vertex positions for area sign.
            let mut cycle = Vec::new();
            let mut h = h_start;
            let max_iter = self.half_edges.len() + 4;
            let mut iters = 0;
            loop {
                cycle.push(h);
                let next = self.half_edges[h].next;
                if next.is_null() {
                    return Err(SubdivisionError::OpenBlock);
                }
                h = next;
                iters += 1;
                if iters > max_iter {
                    return Err(SubdivisionError::OpenBlock);
                }
                if h == h_start {
                    break;
                }
            }
            let pts: Vec<DVec2> = cycle
                .iter()
                .map(|&hid| self.nodes[self.half_edges[hid].origin].pos)
                .collect();
            let signed = signed_area(&pts);
            let is_exterior = signed < 0.0 || signed.abs() < EPS_GEOM;
            let face_id = self.faces.insert(Face {
                boundary: h_start,
                is_exterior,
            });
            for h in cycle {
                self.half_edges[h].face = Some(face_id);
            }
        }
        Ok(())
    }
}

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

    fn square_graph() -> RoadGraph {
        let mut g = RoadGraph::new();
        let a = g.add_node(DVec2::new(0.0, 0.0));
        let b = g.add_node(DVec2::new(1.0, 0.0));
        let c = g.add_node(DVec2::new(1.0, 1.0));
        let d = g.add_node(DVec2::new(0.0, 1.0));
        g.add_road(a, b).unwrap();
        g.add_road(b, c).unwrap();
        g.add_road(c, d).unwrap();
        g.add_road(d, a).unwrap();
        g
    }

    #[test]
    fn square_yields_two_faces() {
        let mut g = square_graph();
        g.rebuild_topology().unwrap();
        assert_eq!(g.faces.len(), 2);
        let exterior = g.faces.values().filter(|f| f.is_exterior).count();
        assert_eq!(exterior, 1);
    }

    #[test]
    fn duplicate_road_rejected() {
        let mut g = RoadGraph::new();
        let a = g.add_node(DVec2::new(0.0, 0.0));
        let b = g.add_node(DVec2::new(1.0, 0.0));
        g.add_road(a, b).unwrap();
        assert!(g.add_road(a, b).is_err());
        assert!(g.add_road(b, a).is_err());
    }

    #[test]
    fn self_loop_rejected() {
        let mut g = RoadGraph::new();
        let a = g.add_node(DVec2::new(0.0, 0.0));
        assert!(g.add_road(a, a).is_err());
    }

    #[test]
    fn non_planar_graph_detected() {
        // Two crossing roads with no node at the crossing.
        let mut g = RoadGraph::new();
        let a = g.add_node(DVec2::new(0.0, 0.0));
        let b = g.add_node(DVec2::new(2.0, 2.0));
        let c = g.add_node(DVec2::new(0.0, 2.0));
        let d = g.add_node(DVec2::new(2.0, 0.0));
        g.add_road(a, b).unwrap();
        g.add_road(c, d).unwrap();
        let err = g.rebuild_topology().unwrap_err();
        assert!(matches!(err, SubdivisionError::NonPlanarGraph(_)));
    }
}
