//! Integer grid-coordinate geometry (spec §4.1).
//!
//! These are the foundational value types reused by the grid, regions, and
//! every generation pass. They are deliberately small, `Copy`, and total: no
//! method panics on valid input. All types derive the standard comparison and
//! serialization traits so that a [`crate::map`]-level value can round-trip
//! through serde.

use serde::{Deserialize, Serialize};

/// A single cell coordinate on the integer grid.
///
/// Coordinates are signed so that intermediate arithmetic (offsets, inflation)
/// can produce out-of-bounds values without wrapping; bounds checking is the
/// grid's responsibility, not the point's.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Point {
    /// Horizontal coordinate (column), increasing rightward.
    pub x: i32,
    /// Vertical coordinate (row), increasing downward.
    pub y: i32,
}

impl Point {
    /// The four orthogonal neighbor offsets (N, S, W, E), in a stable order.
    ///
    /// Order is fixed for determinism: anything iterating neighbors visits them
    /// the same way on every machine and every run.
    pub const OFFSETS4: [Point; 4] = [
        Point { x: 0, y: -1 },
        Point { x: 0, y: 1 },
        Point { x: -1, y: 0 },
        Point { x: 1, y: 0 },
    ];

    /// The eight neighbor offsets (orthogonal then diagonal), in a stable order.
    pub const OFFSETS8: [Point; 8] = [
        Point { x: 0, y: -1 },
        Point { x: 0, y: 1 },
        Point { x: -1, y: 0 },
        Point { x: 1, y: 0 },
        Point { x: -1, y: -1 },
        Point { x: 1, y: -1 },
        Point { x: -1, y: 1 },
        Point { x: 1, y: 1 },
    ];

    /// Creates a new point at `(x, y)`.
    pub const fn new(x: i32, y: i32) -> Self {
        Point { x, y }
    }

    /// Returns the Manhattan (L1) distance between `self` and `other`.
    ///
    /// This is symmetric: `a.manhattan(b) == b.manhattan(a)`.
    pub fn manhattan(&self, other: Point) -> i32 {
        (self.x - other.x).abs() + (self.y - other.y).abs()
    }

    /// Returns a copy of this point translated by `(dx, dy)`.
    pub const fn offset(&self, dx: i32, dy: i32) -> Point {
        Point {
            x: self.x + dx,
            y: self.y + dy,
        }
    }

    /// Returns the four orthogonally adjacent points (N, S, W, E).
    ///
    /// Bounds are not consulted here — callers that need in-bounds neighbors
    /// filter through the grid. Order matches [`Point::OFFSETS4`].
    pub fn neighbors4(&self) -> [Point; 4] {
        Point::OFFSETS4.map(|o| self.offset(o.x, o.y))
    }

    /// Returns the eight surrounding points (orthogonal then diagonal).
    ///
    /// Order matches [`Point::OFFSETS8`].
    pub fn neighbors8(&self) -> [Point; 8] {
        Point::OFFSETS8.map(|o| self.offset(o.x, o.y))
    }
}

/// An axis-aligned rectangle of grid cells with integer origin and size.
///
/// `(x, y)` is the top-left (minimum) corner; `w`/`h` are the extents in cells.
/// A rectangle with `w <= 0` or `h <= 0` is empty: it contains no cells and
/// intersects nothing.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Rect {
    /// Left edge (minimum x).
    pub x: i32,
    /// Top edge (minimum y).
    pub y: i32,
    /// Width in cells.
    pub w: i32,
    /// Height in cells.
    pub h: i32,
}

impl Rect {
    /// Creates a rectangle with top-left corner `(x, y)` and size `w` x `h`.
    pub const fn new(x: i32, y: i32, w: i32, h: i32) -> Self {
        Rect { x, y, w, h }
    }

    /// The exclusive right edge (`x + w`): one past the last contained column.
    pub const fn right(&self) -> i32 {
        self.x + self.w
    }

    /// The exclusive bottom edge (`y + h`): one past the last contained row.
    pub const fn bottom(&self) -> i32 {
        self.y + self.h
    }

    /// Returns `true` if the rectangle contains no cells (non-positive extent).
    pub const fn is_empty(&self) -> bool {
        self.w <= 0 || self.h <= 0
    }

    /// Returns the center cell of the rectangle.
    ///
    /// Uses integer division, so for even extents the center is biased toward
    /// the top-left. For any non-empty rect this is an interior (contained)
    /// cell.
    pub const fn center(&self) -> Point {
        Point::new(self.x + self.w / 2, self.y + self.h / 2)
    }

    /// Returns `true` if `p` lies within the rectangle (corners inclusive).
    pub const fn contains(&self, p: Point) -> bool {
        p.x >= self.x && p.x < self.right() && p.y >= self.y && p.y < self.bottom()
    }

    /// Returns `true` if `self` and `other` share at least one cell.
    ///
    /// This is symmetric. Rectangles that merely touch edge-to-edge (one's
    /// right edge equal to the other's left edge) do **not** intersect, since
    /// they share no cell. Empty rectangles intersect nothing.
    pub const fn intersects(&self, other: &Rect) -> bool {
        if self.is_empty() || other.is_empty() {
            return false;
        }
        self.x < other.right()
            && other.x < self.right()
            && self.y < other.bottom()
            && other.y < self.bottom()
    }

    /// Returns a copy grown by `by` cells on every side.
    ///
    /// A negative `by` shrinks (deflates) the rectangle; if it shrinks past
    /// zero, the resulting extents may be non-positive (an empty rect).
    pub const fn inflate(&self, by: i32) -> Rect {
        Rect {
            x: self.x - by,
            y: self.y - by,
            w: self.w + 2 * by,
            h: self.h + 2 * by,
        }
    }

    /// Iterates over every contained cell in row-major order (rows top to
    /// bottom, columns left to right within each row).
    ///
    /// Yields exactly `w * h` distinct points for a non-empty rect, and nothing
    /// for an empty one. Row-major order is fixed for determinism.
    pub fn iter(&self) -> impl Iterator<Item = Point> + '_ {
        let xs = self.x..self.right();
        (self.y..self.bottom()).flat_map(move |y| xs.clone().map(move |x| Point::new(x, y)))
    }
}

/// A segment between two grid cells, used for carving corridors.
///
/// `cells()` walks the grid run from `from` to `to`. v1 only needs straight
/// orthogonal runs (horizontal or vertical), which is what corridors are built
/// from; the iterator documents its behavior for the diagonal/general case
/// below.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Line {
    /// Start cell (inclusive).
    pub from: Point,
    /// End cell (inclusive).
    pub to: Point,
}

impl Line {
    /// Creates a line segment from `from` to `to`.
    pub const fn new(from: Point, to: Point) -> Self {
        Line { from, to }
    }

    /// Iterates the grid cells along the segment, inclusive of both endpoints.
    ///
    /// For a horizontal or vertical line this yields a contiguous run of cells
    /// (the case v1 corridors rely on). For a sloped line it walks one cell per
    /// step along the longer axis, stepping the shorter axis proportionally —
    /// the cells form a connected staircase but are not guaranteed to be a
    /// "thin" Bresenham line; this suffices for corridor carving where any
    /// connected run between the endpoints is acceptable. The endpoints are
    /// always the first and last cells yielded.
    pub fn cells(&self) -> impl Iterator<Item = Point> {
        let (from, to) = (self.from, self.to);
        let dx = to.x - from.x;
        let dy = to.y - from.y;
        let steps = dx.abs().max(dy.abs());

        (0..=steps).map(move |i| {
            if steps == 0 {
                // Degenerate line: from == to, a single cell.
                from
            } else {
                // Linearly interpolate, rounding to the nearest cell. Rounding
                // (rather than truncating) keeps the run symmetric end-to-end.
                let x = from.x + (dx * i + sign(dx) * steps / 2) / steps;
                let y = from.y + (dy * i + sign(dy) * steps / 2) / steps;
                Point::new(x, y)
            }
        })
    }
}

/// Returns -1, 0, or 1 matching the sign of `n`.
const fn sign(n: i32) -> i32 {
    match n {
        n if n > 0 => 1,
        n if n < 0 => -1,
        _ => 0,
    }
}

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

    #[test]
    fn point_manhattan_is_correct_and_symmetric() {
        let a = Point::new(1, 2);
        let b = Point::new(4, -2);
        // |4-1| + |-2-2| = 3 + 4 = 7
        assert_eq!(a.manhattan(b), 7);
        assert_eq!(a.manhattan(b), b.manhattan(a));
        // Distance to self is zero.
        assert_eq!(a.manhattan(a), 0);
    }

    #[test]
    fn point_neighbors_offset_correctly() {
        let p = Point::new(5, 5);
        let n4 = p.neighbors4();
        assert!(n4.contains(&Point::new(5, 4)));
        assert!(n4.contains(&Point::new(5, 6)));
        assert!(n4.contains(&Point::new(4, 5)));
        assert!(n4.contains(&Point::new(6, 5)));

        let n8 = p.neighbors8();
        assert_eq!(n8.len(), 8);
        // All eight are distinct and none is the point itself.
        assert!(!n8.contains(&p));
        assert!(n8.contains(&Point::new(4, 4)));
        assert!(n8.contains(&Point::new(6, 6)));
    }

    #[test]
    fn rect_contains_corners_interior_and_rejects_outside() {
        let r = Rect::new(2, 3, 4, 5); // x:2..6, y:3..8
        // Corners (inclusive).
        assert!(r.contains(Point::new(2, 3))); // top-left
        assert!(r.contains(Point::new(5, 3))); // top-right
        assert!(r.contains(Point::new(2, 7))); // bottom-left
        assert!(r.contains(Point::new(5, 7))); // bottom-right
        // Interior.
        assert!(r.contains(Point::new(3, 5)));
        // Just outside on each side.
        assert!(!r.contains(Point::new(1, 5))); // left of
        assert!(!r.contains(Point::new(6, 5))); // right of (exclusive edge)
        assert!(!r.contains(Point::new(3, 2))); // above
        assert!(!r.contains(Point::new(3, 8))); // below (exclusive edge)
    }

    #[test]
    fn rect_intersects_is_symmetric_for_overlap() {
        let a = Rect::new(0, 0, 4, 4);
        let b = Rect::new(2, 2, 4, 4); // overlaps a in the 2..4 square
        assert!(a.intersects(&b));
        assert!(b.intersects(&a)); // symmetric
    }

    #[test]
    fn rect_intersects_false_for_adjacent_disjoint() {
        let a = Rect::new(0, 0, 4, 4); // x:0..4
        let b = Rect::new(4, 0, 4, 4); // x:4..8 — touches a's right edge, shares no cell
        assert!(!a.intersects(&b));
        assert!(!b.intersects(&a)); // symmetric

        // Fully separated rects also do not intersect.
        let c = Rect::new(100, 100, 2, 2);
        assert!(!a.intersects(&c));
        assert!(!c.intersects(&a));
    }

    #[test]
    fn rect_intersects_handles_empty_rects() {
        let a = Rect::new(0, 0, 4, 4);
        let empty = Rect::new(1, 1, 0, 5);
        assert!(!a.intersects(&empty));
        assert!(!empty.intersects(&a));
    }

    #[test]
    fn rect_iter_yields_exactly_w_times_h_distinct_contained_points() {
        let r = Rect::new(2, 3, 4, 5);
        let points: Vec<Point> = r.iter().collect();

        // Exactly w * h points.
        assert_eq!(points.len() as i32, r.w * r.h);

        // All distinct.
        let mut unique = points.clone();
        unique.sort_by_key(|p| (p.y, p.x));
        unique.dedup();
        assert_eq!(unique.len(), points.len());

        // All contained.
        assert!(points.iter().all(|&p| r.contains(p)));
    }

    #[test]
    fn rect_iter_empty_yields_nothing() {
        let r = Rect::new(0, 0, 0, 5);
        assert_eq!(r.iter().count(), 0);
        let r = Rect::new(0, 0, 5, -1);
        assert_eq!(r.iter().count(), 0);
    }

    #[test]
    fn rect_center_is_an_interior_point() {
        let r = Rect::new(2, 3, 4, 5);
        let c = r.center();
        assert!(r.contains(c));

        // Odd extents center exactly.
        let odd = Rect::new(0, 0, 5, 5);
        assert_eq!(odd.center(), Point::new(2, 2));
        assert!(odd.contains(odd.center()));
    }

    #[test]
    fn rect_inflate_grows_and_deflate_shrinks() {
        let r = Rect::new(5, 5, 4, 4);
        let bigger = r.inflate(2);
        assert_eq!(bigger, Rect::new(3, 3, 8, 8));
        // The original rect sits inside the inflated one.
        assert!(r.iter().all(|p| bigger.contains(p)));

        let smaller = r.inflate(-1);
        assert_eq!(smaller, Rect::new(6, 6, 2, 2));
    }

    #[test]
    fn line_cells_horizontal_is_contiguous_inclusive() {
        let line = Line::new(Point::new(2, 5), Point::new(6, 5));
        let cells: Vec<Point> = line.cells().collect();
        let expected: Vec<Point> = (2..=6).map(|x| Point::new(x, 5)).collect();
        assert_eq!(cells, expected);
        // First and last are the endpoints.
        assert_eq!(*cells.first().unwrap(), line.from);
        assert_eq!(*cells.last().unwrap(), line.to);
    }

    #[test]
    fn line_cells_vertical_is_contiguous_inclusive() {
        let line = Line::new(Point::new(3, 1), Point::new(3, 4));
        let cells: Vec<Point> = line.cells().collect();
        let expected: Vec<Point> = (1..=4).map(|y| Point::new(3, y)).collect();
        assert_eq!(cells, expected);
        assert_eq!(*cells.first().unwrap(), line.from);
        assert_eq!(*cells.last().unwrap(), line.to);
    }

    #[test]
    fn line_cells_reversed_run_is_inclusive() {
        // Walking right-to-left still includes both endpoints in order.
        let line = Line::new(Point::new(6, 5), Point::new(2, 5));
        let cells: Vec<Point> = line.cells().collect();
        let expected: Vec<Point> = (2..=6).rev().map(|x| Point::new(x, 5)).collect();
        assert_eq!(cells, expected);
    }

    #[test]
    fn line_cells_single_point() {
        let line = Line::new(Point::new(7, 7), Point::new(7, 7));
        let cells: Vec<Point> = line.cells().collect();
        assert_eq!(cells, vec![Point::new(7, 7)]);
    }

    #[test]
    fn line_cells_diagonal_is_connected_and_inclusive() {
        // A 45-degree run: one cell per step, endpoints included.
        let line = Line::new(Point::new(0, 0), Point::new(3, 3));
        let cells: Vec<Point> = line.cells().collect();
        assert_eq!(*cells.first().unwrap(), line.from);
        assert_eq!(*cells.last().unwrap(), line.to);
        assert_eq!(cells.len(), 4);
        // Consecutive cells differ by at most one in each axis (connected).
        for w in cells.windows(2) {
            assert!((w[0].x - w[1].x).abs() <= 1);
            assert!((w[0].y - w[1].y).abs() <= 1);
        }
    }
}