use std::collections::{BTreeMap, BTreeSet};

use bone_kernel::{
    Arc2, BrepError, Circle2, Curve2Kind, ExtrudeProfile, Line2, ProfileDefect, ProfileEdge,
    ProfileLoop,
};
use bone_types::{Plane3, Point2, SketchEntityId, Tolerance};

use crate::sketch::{ArcData, CircleData, LineData, Sketch, SketchEntity};

const PROFILE_TOLERANCE: Tolerance = Tolerance::new(1.0e-9);

pub(crate) fn build_profile(sketch: &Sketch) -> Result<ExtrudeProfile, BrepError> {
    let plane = Plane3::from(sketch.plane());
    let circles = circle_loops(sketch)?;
    let chains = chain_loops(sketch)?;
    let loops = circles.into_iter().chain(chains).collect();
    Ok(ExtrudeProfile::new(plane, loops))
}

fn defect(reason: ProfileDefect) -> BrepError {
    BrepError::InvalidProfile { reason }
}

fn point_at(sketch: &Sketch, id: SketchEntityId) -> Point2 {
    let Some(SketchEntity::Point(point)) = sketch.entities().get(id) else {
        unreachable!("Sketch validation guarantees entity references resolve to points");
    };
    point.at()
}

fn circle_loops(sketch: &Sketch) -> Result<Vec<ProfileLoop>, BrepError> {
    sketch
        .entity_order()
        .iter()
        .filter_map(|id| match sketch.entities().get(*id) {
            Some(SketchEntity::Circle(circle)) if !circle.for_construction() => {
                Some((*id, *circle))
            }
            _ => None,
        })
        .map(|(id, circle)| circle_loop(sketch, id, circle))
        .collect()
}

fn circle_loop(
    sketch: &Sketch,
    id: SketchEntityId,
    circle: CircleData,
) -> Result<ProfileLoop, BrepError> {
    let center = point_at(sketch, circle.center());
    let disk = Circle2::new(center, circle.radius(), PROFILE_TOLERANCE)
        .map_err(|_| defect(ProfileDefect::ZeroArea))?;
    Ok(ProfileLoop::Closed {
        curve: Curve2Kind::Circle(disk),
        curve_entity: id,
    })
}

#[derive(Copy, Clone)]
enum EdgeCurve {
    Line(Line2),
    Arc(Arc2),
}

impl EdgeCurve {
    fn into_kind(self) -> Curve2Kind {
        match self {
            Self::Line(line) => Curve2Kind::Line(line),
            Self::Arc(arc) => Curve2Kind::Arc(arc),
        }
    }

    fn reversed(self) -> Result<Self, BrepError> {
        match self {
            Self::Line(line) => Line2::new(line.end(), line.start(), PROFILE_TOLERANCE)
                .map(Self::Line)
                .map_err(|_| defect(ProfileDefect::ZeroArea)),
            Self::Arc(arc) => Arc2::new(
                arc.center(),
                arc.radius(),
                arc.start_angle() + arc.sweep_angle(),
                -arc.sweep_angle(),
                PROFILE_TOLERANCE,
            )
            .map(Self::Arc)
            .map_err(|_| defect(ProfileDefect::ZeroArea)),
        }
    }
}

#[derive(Copy, Clone)]
struct RawEdge {
    entity: SketchEntityId,
    from: SketchEntityId,
    to: SketchEntityId,
    curve: EdgeCurve,
}

impl RawEdge {
    fn other(self, point: SketchEntityId) -> SketchEntityId {
        debug_assert!(
            point == self.from || point == self.to,
            "other() requires a vertex of this edge"
        );
        if point == self.from {
            self.to
        } else {
            self.from
        }
    }

    fn oriented(self, start: SketchEntityId) -> Result<Curve2Kind, BrepError> {
        if start == self.from {
            Ok(self.curve.into_kind())
        } else {
            self.curve.reversed().map(EdgeCurve::into_kind)
        }
    }
}

fn raw_edges(sketch: &Sketch) -> Result<Vec<RawEdge>, BrepError> {
    sketch
        .entity_order()
        .iter()
        .filter_map(|id| match sketch.entities().get(*id) {
            Some(SketchEntity::Line(line)) if !line.for_construction() => {
                Some(line_edge(sketch, *id, *line))
            }
            Some(SketchEntity::Arc(arc)) if !arc.for_construction() => {
                Some(arc_edge(sketch, *id, *arc))
            }
            _ => None,
        })
        .collect()
}

fn line_edge(sketch: &Sketch, id: SketchEntityId, line: LineData) -> Result<RawEdge, BrepError> {
    let start = point_at(sketch, line.a());
    let end = point_at(sketch, line.b());
    let segment =
        Line2::new(start, end, PROFILE_TOLERANCE).map_err(|_| defect(ProfileDefect::ZeroArea))?;
    Ok(RawEdge {
        entity: id,
        from: line.a(),
        to: line.b(),
        curve: EdgeCurve::Line(segment),
    })
}

fn arc_edge(sketch: &Sketch, id: SketchEntityId, arc: ArcData) -> Result<RawEdge, BrepError> {
    let center = point_at(sketch, arc.center());
    let start = point_at(sketch, arc.start());
    let end = point_at(sketch, arc.end());
    let curve = Arc2::from_center_start_end(center, start, end, PROFILE_TOLERANCE)
        .map_err(|_| defect(ProfileDefect::ZeroArea))?;
    Ok(RawEdge {
        entity: id,
        from: arc.start(),
        to: arc.end(),
        curve: EdgeCurve::Arc(curve),
    })
}

type Incidence = BTreeMap<SketchEntityId, [usize; 2]>;

fn chain_loops(sketch: &Sketch) -> Result<Vec<ProfileLoop>, BrepError> {
    let edges = raw_edges(sketch)?;
    if edges.is_empty() {
        return Ok(Vec::new());
    }
    let incidence = incidence(&edges)?;
    walk_all(&edges, &incidence)
}

fn incidence(edges: &[RawEdge]) -> Result<Incidence, BrepError> {
    let grouped: BTreeMap<SketchEntityId, Vec<usize>> =
        edges
            .iter()
            .enumerate()
            .fold(BTreeMap::new(), |mut acc, (index, edge)| {
                acc.entry(edge.from).or_default().push(index);
                acc.entry(edge.to).or_default().push(index);
                acc
            });
    grouped
        .into_iter()
        .map(|(point, indices)| match indices.as_slice() {
            [a, b] => Ok((point, [*a, *b])),
            [_] => Err(defect(ProfileDefect::OpenLoop)),
            _ => Err(defect(ProfileDefect::BranchingVertex)),
        })
        .collect()
}

fn other_edge(
    incidence: &Incidence,
    point: SketchEntityId,
    current: usize,
) -> Result<usize, BrepError> {
    match incidence.get(&point) {
        Some(&[a, b]) if a == current => Ok(b),
        Some(&[a, b]) if b == current => Ok(a),
        _ => Err(defect(ProfileDefect::OpenLoop)),
    }
}

#[derive(Copy, Clone)]
struct Step {
    edge: usize,
    from: SketchEntityId,
}

fn walk_all(edges: &[RawEdge], incidence: &Incidence) -> Result<Vec<ProfileLoop>, BrepError> {
    let (_, loops) = (0..edges.len()).try_fold(
        (BTreeSet::<usize>::new(), Vec::<ProfileLoop>::new()),
        |(visited, mut loops), start| {
            if visited.contains(&start) {
                return Ok((visited, loops));
            }
            let steps = walk_cycle(edges, incidence, start)?;
            let next_visited = steps.iter().fold(visited, |mut acc, step| {
                acc.insert(step.edge);
                acc
            });
            let profile_edges = steps
                .iter()
                .map(|step| {
                    let edge = edges[step.edge];
                    Ok(ProfileEdge::new(
                        edge.oriented(step.from)?,
                        edge.entity,
                        step.from,
                    ))
                })
                .collect::<Result<Vec<_>, BrepError>>()?;
            loops.push(ProfileLoop::Open(profile_edges));
            Ok((next_visited, loops))
        },
    )?;
    Ok(loops)
}

enum Walk {
    Going {
        edge: usize,
        from: SketchEntityId,
        steps: Vec<Step>,
    },
    Closed(Vec<Step>),
}

fn walk_cycle(
    edges: &[RawEdge],
    incidence: &Incidence,
    start: usize,
) -> Result<Vec<Step>, BrepError> {
    let origin = edges[start].from;
    let walk = (0..edges.len()).try_fold(
        Walk::Going {
            edge: start,
            from: origin,
            steps: Vec::new(),
        },
        |state, _| match state {
            Walk::Closed(steps) => Ok(Walk::Closed(steps)),
            Walk::Going {
                edge,
                from,
                mut steps,
            } => {
                let next_point = edges[edge].other(from);
                steps.push(Step { edge, from });
                if next_point == origin {
                    Ok(Walk::Closed(steps))
                } else {
                    let next_edge = other_edge(incidence, next_point, edge)?;
                    Ok(Walk::Going {
                        edge: next_edge,
                        from: next_point,
                        steps,
                    })
                }
            }
        },
    )?;
    match walk {
        Walk::Closed(steps) => Ok(steps),
        Walk::Going { .. } => Err(defect(ProfileDefect::OpenLoop)),
    }
}

#[cfg(test)]
mod tests {
    use super::build_profile;
    use crate::sketch::{EditOutcome, Sketch, SketchEdit, SketchEntity};
    use bone_kernel::{
        BrepError, BrepSolid, Curve2Kind, ExtrudeDirection, ExtrudeEndCondition, ExtrudeFeature,
        ExtrudeSense, MergeResult, ProfileDefect, ProfileLoop, evaluate_extrude,
    };
    use bone_types::{
        FeatureId, Length, Point2, Point3, PositiveLength, SketchEntityId, SketchId,
        SketchPlaneBasis, Tolerance, UnitVec3, millimeter,
    };
    use slotmap::{Key, KeyData};

    const TOL: Tolerance = Tolerance::new(1e-9);

    fn plane() -> SketchPlaneBasis {
        let Ok(basis) = SketchPlaneBasis::new(
            Point3::origin(),
            UnitVec3::x_axis(),
            UnitVec3::y_axis(),
            TOL,
        ) else {
            panic!("xy plane is orthonormal");
        };
        basis
    }

    fn feature_id(idx: u32) -> FeatureId {
        FeatureId::from(KeyData::from_ffi((1u64 << 32) | u64::from(idx)))
    }

    fn point(sketch: Sketch, x: f64, y: f64) -> (Sketch, SketchEntityId) {
        let Ok((next, EditOutcome::Entity(id))) = sketch.apply(SketchEdit::AddEntity(
            SketchEntity::point(Point2::from_mm(x, y)),
        )) else {
            panic!("add point");
        };
        (next, id)
    }

    fn line(
        sketch: Sketch,
        a: SketchEntityId,
        b: SketchEntityId,
        construction: bool,
    ) -> (Sketch, SketchEntityId) {
        let Ok((next, EditOutcome::Entity(id))) = sketch.apply(SketchEdit::AddEntity(
            SketchEntity::line(a, b, construction),
        )) else {
            panic!("add line");
        };
        (next, id)
    }

    fn arc(
        sketch: Sketch,
        center: SketchEntityId,
        start: SketchEntityId,
        end: SketchEntityId,
    ) -> (Sketch, SketchEntityId) {
        let Ok((next, EditOutcome::Entity(id))) = sketch.apply(SketchEdit::AddEntity(
            SketchEntity::arc(center, start, end, false),
        )) else {
            panic!("add arc");
        };
        (next, id)
    }

    fn circle(sketch: Sketch, center: SketchEntityId, radius_mm: f64) -> (Sketch, SketchEntityId) {
        let Ok((next, EditOutcome::Entity(id))) = sketch.apply(SketchEdit::AddEntity(
            SketchEntity::circle(center, Length::new::<millimeter>(radius_mm), false),
        )) else {
            panic!("add circle");
        };
        (next, id)
    }

    fn blind(depth_mm: f64) -> ExtrudeFeature {
        let Ok(depth) = PositiveLength::new(Length::new::<millimeter>(depth_mm)) else {
            panic!("{depth_mm} mm is positive");
        };
        ExtrudeFeature {
            sketch: SketchId::null(),
            direction: ExtrudeDirection::Normal {
                sense: ExtrudeSense::Forward,
            },
            end_condition: ExtrudeEndCondition::Blind { depth },
            draft: None,
            thin_wall: None,
            merge_result: MergeResult::Merge,
        }
    }

    fn extrude(sketch: &Sketch) -> Result<BrepSolid, BrepError> {
        let profile = build_profile(sketch)?;
        evaluate_extrude(feature_id(1), &profile, &blind(4.0))
    }

    fn corners(sketch: Sketch) -> (Sketch, [SketchEntityId; 4]) {
        let (sketch, p0) = point(sketch, 0.0, 0.0);
        let (sketch, p1) = point(sketch, 10.0, 0.0);
        let (sketch, p2) = point(sketch, 10.0, 5.0);
        let (sketch, p3) = point(sketch, 0.0, 5.0);
        (sketch, [p0, p1, p2, p3])
    }

    #[test]
    fn rectangle_builds_one_quad_loop() {
        let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
        let (sketch, l0) = line(sketch, p0, p1, false);
        let (sketch, l1) = line(sketch, p1, p2, false);
        let (sketch, l2) = line(sketch, p2, p3, false);
        let (sketch, l3) = line(sketch, p3, p0, false);

        let Ok(profile) = build_profile(&sketch) else {
            panic!("rectangle is a buildable profile");
        };
        let [single] = profile.loops() else {
            panic!("rectangle is one loop");
        };
        let ProfileLoop::Open(edges) = single else {
            panic!("a line loop is open");
        };
        assert_eq!(edges.len(), 4);
        let entities: Vec<SketchEntityId> = edges.iter().map(|edge| edge.curve_entity()).collect();
        assert_eq!(entities, vec![l0, l1, l2, l3]);
        let walk_corners: Vec<SketchEntityId> = edges.iter().map(|edge| edge.corner()).collect();
        assert_eq!(walk_corners, vec![p0, p1, p2, p3]);
        assert!(
            edges
                .iter()
                .all(|edge| matches!(edge.curve(), Curve2Kind::Line(_)))
        );
    }

    #[test]
    fn rectangle_extrudes_to_closed_solid() {
        let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
        let (sketch, _) = line(sketch, p0, p1, false);
        let (sketch, _) = line(sketch, p1, p2, false);
        let (sketch, _) = line(sketch, p2, p3, false);
        let (sketch, _) = line(sketch, p3, p0, false);
        let Ok(solid) = extrude(&sketch) else {
            panic!("rectangle extrudes");
        };
        assert_eq!(solid.iter_faces().count(), 6);
        assert!(solid.validate(TOL).is_ok());
    }

    #[test]
    fn mixed_edge_orientation_still_assembles() {
        let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
        let (sketch, _) = line(sketch, p0, p1, false);
        let (sketch, _) = line(sketch, p2, p1, false);
        let (sketch, _) = line(sketch, p2, p3, false);
        let (sketch, _) = line(sketch, p0, p3, false);
        let Ok(solid) = extrude(&sketch) else {
            panic!("the walk reverses backwards edges");
        };
        assert_eq!(solid.iter_faces().count(), 6);
        assert!(solid.validate(TOL).is_ok());
    }

    #[test]
    fn circle_builds_one_closed_loop() {
        let (sketch, center) = point(Sketch::new(plane()), 0.0, 0.0);
        let (sketch, disk) = circle(sketch, center, 5.0);
        let Ok(profile) = build_profile(&sketch) else {
            panic!("circle is a buildable profile");
        };
        let [
            ProfileLoop::Closed {
                curve_entity,
                curve,
            },
        ] = profile.loops()
        else {
            panic!("a circle is one closed loop");
        };
        assert_eq!(*curve_entity, disk);
        assert!(matches!(curve, Curve2Kind::Circle(_)));
        let Ok(solid) = extrude(&sketch) else {
            panic!("circle extrudes");
        };
        assert!(solid.validate(TOL).is_ok());
    }

    #[test]
    fn arc_and_chord_assemble_into_a_half_disk() {
        let (sketch, center) = point(Sketch::new(plane()), 0.0, 0.0);
        let (sketch, start) = point(sketch, -5.0, 0.0);
        let (sketch, end) = point(sketch, 5.0, 0.0);
        let (sketch, arc_id) = arc(sketch, center, start, end);
        let (sketch, _) = line(sketch, end, start, false);

        let Ok(profile) = build_profile(&sketch) else {
            panic!("arc plus chord is buildable");
        };
        let [ProfileLoop::Open(edges)] = profile.loops() else {
            panic!("half disk is one open loop");
        };
        assert_eq!(edges.len(), 2);
        let Some(Curve2Kind::Arc(forward)) = edges
            .iter()
            .find(|edge| edge.curve_entity() == arc_id)
            .map(|edge| edge.curve())
        else {
            panic!("arc edge present in the loop");
        };
        assert!(
            forward.sweep_rad() > 0.0 && (forward.sweep_rad() - core::f64::consts::PI).abs() < 1e-9,
            "forward ordering sweeps ccw through the bottom semicircle"
        );
        let Ok(solid) = extrude(&sketch) else {
            panic!("half disk extrudes");
        };
        assert!(solid.validate(TOL).is_ok());
    }

    #[test]
    fn reversed_arc_assembles_like_the_forward_arc() {
        let (sketch, center) = point(Sketch::new(plane()), 0.0, 0.0);
        let (sketch, start) = point(sketch, -5.0, 0.0);
        let (sketch, end) = point(sketch, 5.0, 0.0);
        let (sketch, _) = line(sketch, start, end, false);
        let (sketch, arc_id) = arc(sketch, center, start, end);

        let Ok(profile) = build_profile(&sketch) else {
            panic!("arc plus chord is buildable in either order");
        };
        let [ProfileLoop::Open(edges)] = profile.loops() else {
            panic!("half disk is one open loop");
        };
        let Some(Curve2Kind::Arc(reversed)) = edges
            .iter()
            .find(|edge| edge.curve_entity() == arc_id)
            .map(|edge| edge.curve())
        else {
            panic!("arc edge present in the loop");
        };
        assert!(
            reversed.sweep_rad() < 0.0,
            "chord-first ordering makes the walk traverse the arc backward"
        );
        let Ok(solid) = extrude(&sketch) else {
            panic!("reversed-arc half disk extrudes");
        };
        assert!(solid.validate(TOL).is_ok());
    }

    #[test]
    fn branching_vertex_is_distinct_from_open_loop() {
        let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
        let (sketch, _) = line(sketch, p0, p1, false);
        let (sketch, _) = line(sketch, p1, p2, false);
        let (sketch, _) = line(sketch, p2, p3, false);
        let (sketch, _) = line(sketch, p3, p0, false);
        let (sketch, _) = line(sketch, p0, p2, false);
        assert!(matches!(
            build_profile(&sketch),
            Err(BrepError::InvalidProfile {
                reason: ProfileDefect::BranchingVertex
            })
        ));
    }

    #[test]
    fn open_chain_is_rejected() {
        let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
        let (sketch, _) = line(sketch, p0, p1, false);
        let (sketch, _) = line(sketch, p1, p2, false);
        let (sketch, _) = line(sketch, p2, p3, false);
        assert!(matches!(
            build_profile(&sketch),
            Err(BrepError::InvalidProfile {
                reason: ProfileDefect::OpenLoop
            })
        ));
    }

    #[test]
    fn construction_geometry_is_excluded() {
        let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
        let (sketch, _) = line(sketch, p0, p1, false);
        let (sketch, _) = line(sketch, p1, p2, false);
        let (sketch, _) = line(sketch, p2, p3, false);
        let (sketch, _) = line(sketch, p3, p0, false);
        let (sketch, diag_a) = point(sketch, 0.0, 0.0);
        let (sketch, diag_b) = point(sketch, 10.0, 5.0);
        let (sketch, _) = line(sketch, diag_a, diag_b, true);

        let Ok(profile) = build_profile(&sketch) else {
            panic!("construction line does not break the profile");
        };
        assert_eq!(profile.loops().len(), 1);
    }

    #[test]
    fn nested_line_loops_extrude_to_a_tube() {
        let (sketch, [o0, o1, o2, o3]) = corners(Sketch::new(plane()));
        let (sketch, _) = line(sketch, o0, o1, false);
        let (sketch, _) = line(sketch, o1, o2, false);
        let (sketch, _) = line(sketch, o2, o3, false);
        let (sketch, _) = line(sketch, o3, o0, false);
        let (sketch, i0) = point(sketch, 3.0, 1.0);
        let (sketch, i1) = point(sketch, 7.0, 1.0);
        let (sketch, i2) = point(sketch, 7.0, 4.0);
        let (sketch, i3) = point(sketch, 3.0, 4.0);
        let (sketch, _) = line(sketch, i0, i1, false);
        let (sketch, _) = line(sketch, i1, i2, false);
        let (sketch, _) = line(sketch, i2, i3, false);
        let (sketch, _) = line(sketch, i3, i0, false);

        let Ok(profile) = build_profile(&sketch) else {
            panic!("rectangle with a rectangular hole is buildable");
        };
        assert_eq!(profile.loops().len(), 2);
        assert!(
            profile
                .loops()
                .iter()
                .all(|loop_| matches!(loop_, ProfileLoop::Open(edges) if edges.len() == 4))
        );
        let Ok(solid) = extrude(&sketch) else {
            panic!("nested loops extrude to a tube");
        };
        assert!(solid.validate(TOL).is_ok());
        assert_eq!(solid.iter_faces().count(), 10);
    }
}
