voronoi-go 1.0.1

//! What the alive zone can be asked once it has been carved: where the nearest
//! playable position is, how far a line is from playable space, and whether a
//! group still touches any.
//!
//! [`AliveZone::contains`] answers about one position and reads only the shapes.
//! Everything here reads the *outline* those shapes have been clipped into — the
//! active segments — because "how near is this to playable space" is a question
//! about the boundary of that space, not about its interior.
//!
//! # An empty zone is infinitely far away
//!
//! [`AliveZone::closest_distance`] answers [`f64::INFINITY`], never `0.0`, when
//! nothing is left: no active segment anywhere and no forced eye. An empty zone
//! means there is nothing to be near, so a group touching only the
//! now-nonexistent boundary must read as having no liberties rather than as
//! sitting on it. That is what lets a fully packed board capture — fill the
//! board bar one position, play it, and every group correctly dies.
//! `docs/design.md` § "An empty zone is infinitely far away" is the same rule
//! stated as an invariant, and the fixture pins it.

use crate::clipping::Segment;
use crate::geometry::{LineSegment, point_in_rings};
use crate::{Point, STONE_RADIUS};

use super::AliveZone;

impl AliveZone {
    /// The playable position nearest to `point`.
    ///
    /// A point that is already playable is its own answer. Otherwise this is the
    /// nearest point of the visible outline — the rim of a dead zone, a stretch
    /// of board edge — or a forced eye, whichever is closest.
    ///
    /// Answers `None` when the zone is empty: there is no playable position to
    /// name. That is the same emptiness [`AliveZone::closest_distance`] reports
    /// as [`f64::INFINITY`].
    ///
    /// Also `None` when `point` is not finite. A probe is a direction to look
    /// from rather than a position, so it is deliberately allowed to sit **off
    /// the board** — snapping a click from outside the edge inwards is the whole
    /// point of the method — but it still has to be somewhere. Every distance
    /// measured from a `NaN` is `NaN`, every comparison against it is false, and
    /// the search below would answer whichever candidate it happened to look at
    /// first. See `docs/design.md` § "A position is a point on the board".
    #[must_use]
    pub fn closest_point(&self, point: Point) -> Option<Point> {
        if !point.is_finite() {
            return None;
        }

        if self.contains(point) {
            return Some(point);
        }

        let mut closest = None;
        let mut minimum = f64::INFINITY;

        for shape in self.graph.shape_ids() {
            let Some(candidate) = self.graph.shape_closest_point(shape, point) else {
                continue;
            };
            let distance = point.distance(candidate);
            if distance < minimum {
                minimum = distance;
                closest = Some(candidate);
            }
        }

        for eye in self.forced_eyes.iter() {
            let distance = point.distance(eye);
            if distance < minimum {
                minimum = distance;
                closest = Some(eye);
            }
        }

        closest
    }

    /// How far `line` is from the boundary of the playable area, and `0.0` when
    /// it crosses it.
    ///
    /// Every shape's visible outline and every forced eye is a candidate, and
    /// the answer is the smallest distance among them. A zone with none of
    /// either is [`f64::INFINITY`] away — see the module documentation, and
    /// `docs/design.md`, for why that is not `0.0`.
    #[must_use]
    pub fn closest_distance(&self, line: LineSegment) -> f64 {
        let mut minimum = f64::INFINITY;

        for shape in self.graph.shape_ids() {
            minimum = minimum.min(self.graph.shape_closest_distance(shape, line));
            // Distances are never negative, so this is the crossing case, and
            // nothing further can beat it.
            if minimum <= 0.0 {
                return 0.0;
            }
        }

        for eye in self.forced_eyes.iter() {
            minimum = minimum.min(eye.distance(line.closest_point(eye)));
            if minimum <= 0.0 {
                return 0.0;
            }
        }

        minimum
    }

    /// Whether a group whose territory is `rings` still touches playable space.
    ///
    /// `rings` is the group's hull as [`point_in_rings`] reads it: ring 0 is the
    /// outer loop and the rest are holes. Three tests, any one of which is
    /// enough — they catch the three ways a group and the playable area can
    /// meet, and a group that fails all three has no liberties and is captured.
    ///
    /// 1. **A hull vertex is playable.** The cheapest case, and the common one.
    /// 2. **A hull edge runs within [`STONE_RADIUS`] of the visible outline.**
    ///    Real geometry, not slack on the first test: a stone placed on the
    ///    playable side of that outline has its centre at most a radius away, so
    ///    a hull this close is a hull the group can still be extended across.
    /// 3. **A playable position lies inside the hull.** The mirror of the first,
    ///    for a hull large enough to swallow what is left of the zone: every
    ///    forced eye, and the start of every visible piece of outline, which is
    ///    what catches a sliver too small to contain a vertex.
    #[must_use]
    pub fn cell_is_alive(&self, rings: &[Vec<Point>]) -> bool {
        // 1. A hull vertex inside the zone.
        if rings.iter().flatten().any(|vertex| self.contains(*vertex)) {
            return true;
        }

        // 2. A hull edge within a stone's radius of the outline.
        let close_enough = rings.iter().flat_map(|ring| edges(ring)).any(|edge| {
            // A magnitude test against a real distance, not a tolerance.
            self.closest_distance(edge) <= STONE_RADIUS
        });
        if close_enough {
            return true;
        }

        // 3. A point of the zone inside the hull.
        if self
            .forced_eyes
            .iter()
            .any(|eye| point_in_rings(eye, rings))
        {
            return true;
        }

        self.graph.shape_ids().any(|shape| {
            self.graph
                .segments(shape)
                .filter(|id| self.graph.is_active(*id))
                .filter_map(|id| self.graph.segment(id).map(Segment::point))
                .any(|start| point_in_rings(start, rings))
        })
    }
}

/// The edges of a closed ring, wrapping the last vertex back onto the first.
///
/// A ring of fewer than two vertices has no edges; a ring given closed — its
/// last vertex repeating its first — yields one degenerate edge, which changes
/// no answer.
fn edges(ring: &[Point]) -> impl Iterator<Item = LineSegment> + '_ {
    ring.iter()
        .zip(ring.iter().cycle().skip(1))
        .take(if ring.len() < 2 { 0 } else { ring.len() })
        .map(|(start, end)| LineSegment::new(*start, *end))
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used, clippy::expect_used)]

    use super::edges;
    use crate::alive_zone::AliveZone;
    use crate::clipping::Shape;
    use crate::geometry::LineSegment;
    use crate::{Point, STONE_DIAMETER, STONE_RADIUS, StoneId};

    const BOARD: f64 = 100.0;

    fn p(x: f64, y: f64) -> Point {
        Point::new(x, y)
    }

    fn seg(ax: f64, ay: f64, bx: f64, by: f64) -> LineSegment {
        LineSegment::new(p(ax, ay), p(bx, by))
    }

    fn near(actual: f64, expected: f64) {
        assert!(
            (actual - expected).abs() < 1e-5,
            "expected {expected}, got {actual}"
        );
    }

    /// Carves a dead zone per centre, numbering the stones from zero.
    fn carve_all(board: f64, centers: &[Point]) -> AliveZone {
        let mut zone = AliveZone::new(board);
        for (index, center) in centers.iter().enumerate() {
            zone.remove_circle(StoneId::new(index as u32), *center)
                .unwrap();
            assert_eq!(zone.validate(), Ok(()));
        }
        zone
    }

    /// One closed ring, as a cell's rings.
    fn ring(vertices: &[(f64, f64)]) -> Vec<Vec<Point>> {
        vec![vertices.iter().map(|(x, y)| p(*x, *y)).collect()]
    }

    /// An axis-aligned rectangle, closed by repeating its first vertex the way
    /// a cell's ring is.
    fn rect(x0: f64, y0: f64, x1: f64, y1: f64) -> Vec<Vec<Point>> {
        ring(&[(x0, y0), (x0, y1), (x1, y1), (x1, y0), (x0, y0)])
    }

    // ── closest_point ────────────────────────────────────────────────────────

    #[test]
    fn a_playable_point_is_its_own_nearest_playable_point() {
        let zone = AliveZone::new(BOARD);
        assert_eq!(zone.closest_point(p(50.0, 50.0)), Some(p(50.0, 50.0)));
    }

    #[test]
    fn a_point_off_the_board_lands_on_the_nearest_edge() {
        let zone = AliveZone::new(BOARD);
        let closest = zone.closest_point(p(-10.0, 50.0)).unwrap();
        near(closest.x, STONE_RADIUS);
        near(closest.y, 50.0);
    }

    #[test]
    fn a_point_off_a_corner_lands_on_the_corner() {
        let zone = AliveZone::new(BOARD);
        let closest = zone.closest_point(p(0.0, 0.0)).unwrap();
        near(closest.x, STONE_RADIUS);
        near(closest.y, STONE_RADIUS);
    }

    #[test]
    fn a_point_inside_a_dead_zone_lands_on_its_rim() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        let closest = zone.closest_point(p(50.0, 50.0)).unwrap();
        near(closest.distance(p(50.0, 50.0)), STONE_DIAMETER);
    }

    #[test]
    fn the_nearest_of_several_dead_zones_wins() {
        let zone = carve_all(BOARD, &[p(30.0, 50.0), p(70.0, 50.0)]);

        // Inside the first: its own rim is nearest.
        let closest = zone.closest_point(p(30.0, 50.0)).unwrap();
        near(closest.distance(p(30.0, 50.0)), STONE_DIAMETER);

        // Just inside the first, off centre: still the first, not the second.
        let closest = zone.closest_point(p(31.0, 50.0)).unwrap();
        assert!(closest.distance(p(30.0, 50.0)) < closest.distance(p(70.0, 50.0)));
    }

    #[test]
    fn a_forced_eye_can_be_the_nearest_playable_point() {
        let mut zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        zone.add_forced_eye(p(50.2, 50.0));

        // The eye is nearer than the rim, so it is the answer …
        assert_eq!(zone.closest_point(p(50.0, 50.0)), Some(p(50.2, 50.0)));
        // … and the eye itself is playable, so it answers with itself.
        assert_eq!(zone.closest_point(p(50.2, 50.0)), Some(p(50.2, 50.0)));
    }

    #[test]
    fn an_empty_zone_has_no_nearest_playable_point() {
        let zone = packed();
        assert_eq!(zone.closest_point(ONLY_POSITION), None);
    }

    // ── closest_distance ─────────────────────────────────────────────────────

    #[test]
    fn a_line_in_open_space_measures_to_the_nearest_edge() {
        let zone = AliveZone::new(BOARD);
        let distance = zone.closest_distance(seg(40.0, 50.0, 60.0, 50.0));
        assert!(distance > 0.0);
        assert!(distance < 50.0);
        near(distance, 40.0 - STONE_RADIUS);
    }

    #[test]
    fn a_line_crossing_a_dead_zone_rim_is_zero_away() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        near(zone.closest_distance(seg(40.0, 50.0, 60.0, 50.0)), 0.0);
    }

    #[test]
    fn a_line_lying_along_a_board_edge_is_zero_away() {
        let zone = AliveZone::new(BOARD);
        near(
            zone.closest_distance(seg(STONE_RADIUS, 10.0, STONE_RADIUS, 20.0)),
            0.0,
        );
    }

    #[test]
    fn a_line_wholly_inside_a_dead_zone_measures_out_to_its_rim() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        let distance = zone.closest_distance(seg(50.0, 49.0, 50.0, 49.5));
        assert!(distance > 0.0);
        near(distance, 1.0);
    }

    #[test]
    fn a_line_between_two_dead_zones_measures_to_the_nearer() {
        let zone = carve_all(BOARD, &[p(30.0, 50.0), p(70.0, 50.0)]);
        let distance = zone.closest_distance(seg(50.0, 40.0, 50.0, 60.0));
        assert!(distance >= 0.0);
        near(distance, 20.0 - STONE_DIAMETER);
    }

    #[test]
    fn a_forced_eye_is_a_candidate_of_its_own() {
        let mut zone = AliveZone::new(BOARD);
        let far = zone.closest_distance(seg(50.0, 50.0, 51.0, 50.0));

        zone.add_forced_eye(p(50.5, 53.0));
        near(zone.closest_distance(seg(50.0, 50.0, 51.0, 50.0)), 3.0);
        assert!(far > 3.0, "the eye has to be nearer than the board edge");
    }

    #[test]
    fn a_line_through_a_forced_eye_is_zero_away() {
        let mut zone = AliveZone::new(BOARD);
        zone.add_forced_eye(p(50.0, 50.0));
        near(zone.closest_distance(seg(49.0, 50.0, 51.0, 50.0)), 0.0);
    }

    /// Width of the smallest board a single stone can fill: two stones across.
    const TINY_BOARD: f64 = 2.0 * STONE_DIAMETER;

    /// The centre of that board, and the only position on it.
    const ONLY_POSITION: Point = Point::new(STONE_DIAMETER, STONE_DIAMETER);

    /// A fully packed board: nothing playable is left anywhere.
    ///
    /// A board two stones across has exactly one position on it, and one stone
    /// there consumes all of it — the dead zone swallows the whole inset square,
    /// and every point of the dead zone's own rim is off the board, so no
    /// outline survives on either. This is the fully packed board in miniature,
    /// and the whole point of it is that the queries below answer *nothing*
    /// rather than *zero*.
    fn packed() -> AliveZone {
        let zone = carve_all(TINY_BOARD, &[ONLY_POSITION]);

        // Not an assumption: the emptiness is what is under test, so it is
        // checked here against the structure rather than against the queries the
        // tests then ask.
        assert_eq!(zone.forced_eye_count(), 0);
        for shape in zone.graph.shape_ids() {
            assert!(
                zone.graph.shape(shape).is_some_and(Shape::is_subdivided),
                "{shape:?} was never clipped, so its whole outline is visible"
            );
            assert!(
                zone.graph
                    .segments(shape)
                    .all(|id| !zone.graph.is_active(id)),
                "{shape:?} still has a visible piece of outline"
            );
        }
        zone
    }

    #[test]
    fn a_full_board_leaves_nothing_playable() {
        let zone = packed();
        assert!(!zone.contains(ONLY_POSITION));
        assert!(!zone.contains(p(STONE_RADIUS, STONE_RADIUS)));
        assert!(!zone.contains(p(TINY_BOARD - STONE_RADIUS, STONE_RADIUS)));
    }

    #[test]
    fn an_empty_zone_is_infinitely_far_away_not_zero() {
        // The load-bearing one. A group touching only the now-nonexistent
        // boundary must read as having no liberties, which `0.0` would not say.
        let zone = packed();
        for line in [
            seg(
                STONE_RADIUS,
                STONE_RADIUS,
                TINY_BOARD - STONE_RADIUS,
                STONE_RADIUS,
            ),
            seg(0.0, 0.0, TINY_BOARD, TINY_BOARD),
            seg(
                ONLY_POSITION.x,
                ONLY_POSITION.y,
                ONLY_POSITION.x,
                ONLY_POSITION.y,
            ),
        ] {
            let distance = zone.closest_distance(line);
            assert!(
                distance.is_infinite(),
                "an empty zone must be infinitely far away, got {distance}"
            );
        }
    }

    #[test]
    fn every_cell_on_a_full_board_is_dead() {
        // The consequence: fill the board and every group correctly dies.
        let zone = packed();
        assert!(!zone.cell_is_alive(&rect(0.0, 0.0, TINY_BOARD, TINY_BOARD)));
        assert!(!zone.cell_is_alive(&rect(
            STONE_RADIUS,
            STONE_RADIUS,
            TINY_BOARD - STONE_RADIUS,
            TINY_BOARD - STONE_RADIUS
        )));
    }

    #[test]
    fn a_forced_eye_is_content_enough_to_stop_a_zone_being_empty() {
        let mut zone = packed();
        zone.add_forced_eye(ONLY_POSITION);

        let line = seg(
            ONLY_POSITION.x,
            ONLY_POSITION.y - 2.0,
            ONLY_POSITION.x,
            ONLY_POSITION.y - 1.0,
        );
        let distance = zone.closest_distance(line);
        assert!(distance.is_finite(), "the eye is content, got {distance}");
        near(distance, 1.0);
    }

    // ── cell_is_alive ────────────────────────────────────────────────────────

    #[test]
    fn a_cell_covering_playable_space_is_alive() {
        let mut zone = AliveZone::new(BOARD);
        let cell = rect(40.0, 40.0, 60.0, 60.0);
        assert!(zone.cell_is_alive(&cell));

        // Carving somewhere else changes nothing.
        zone.remove_circle(StoneId::new(0), p(80.0, 80.0)).unwrap();
        assert!(zone.cell_is_alive(&cell));
    }

    #[test]
    fn a_tiny_cell_deep_inside_a_dead_zone_is_dead() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        assert!(!zone.cell_is_alive(&rect(50.0, 50.0, 50.1, 50.1)));
        // Straddling the centre, still a stone's radius clear of the rim.
        assert!(!zone.cell_is_alive(&rect(49.5, 49.5, 50.5, 50.5)));
    }

    #[test]
    fn a_cell_within_a_stone_radius_of_the_outline_is_alive() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        let offset = STONE_DIAMETER + STONE_RADIUS / 2.0;
        assert!(zone.cell_is_alive(&rect(50.0 + offset, 50.0, 51.0 + offset, 51.0)));
    }

    #[test]
    fn the_stone_radius_threshold_is_inclusive() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        let offset = STONE_DIAMETER + STONE_RADIUS;
        assert!(zone.cell_is_alive(&rect(50.0 + offset, 50.0, 51.0 + offset, 51.0)));
    }

    #[test]
    fn a_cell_edge_crossing_the_outline_is_alive() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        assert!(zone.cell_is_alive(&rect(48.0, 50.0, 52.0, 55.0)));
    }

    #[test]
    fn a_cell_swallowing_a_forced_eye_is_alive() {
        let mut zone = AliveZone::new(BOARD);
        zone.add_forced_eye(p(50.0, 50.0));
        assert!(zone.cell_is_alive(&rect(30.0, 30.0, 70.0, 70.0)));
    }

    #[test]
    fn a_cell_swallowing_a_sliver_between_dead_zones_is_alive() {
        // Three dead zones almost touching leave a curved triangle of playable
        // space too small to hold a cell vertex. The reverse-containment test
        // finds it through the starts of the arcs bounding it.
        let spacing = STONE_DIAMETER * 2.1;
        let zone = carve_all(
            BOARD,
            &[
                p(50.0, 50.0),
                p(50.0 + spacing, 50.0),
                p(50.0 + spacing / 2.0, 50.0 + spacing * 0.866),
            ],
        );
        assert!(zone.cell_is_alive(&rect(40.0, 40.0, 80.0, 80.0)));
    }

    #[test]
    fn a_cell_far_off_the_board_is_dead() {
        let zone = AliveZone::new(BOARD);
        assert!(!zone.cell_is_alive(&rect(-20.0, -20.0, -10.0, -10.0)));
    }

    #[test]
    fn a_cell_just_off_the_board_but_within_a_stone_radius_is_alive() {
        let zone = AliveZone::new(BOARD);
        let offset = STONE_RADIUS / 2.0;
        assert!(zone.cell_is_alive(&rect(offset / 2.0, 40.0, offset, 60.0)));
    }

    #[test]
    fn a_cell_just_beyond_a_stone_radius_of_the_board_is_dead() {
        let zone = AliveZone::new(BOARD);
        let outside = -STONE_RADIUS - 0.5;
        assert!(!zone.cell_is_alive(&rect(outside, 50.0, outside + 0.02, 50.02)));
    }

    #[test]
    fn one_live_ring_is_enough() {
        let zone = AliveZone::new(BOARD);
        let mut rings = rect(40.0, 40.0, 45.0, 45.0);
        rings.extend(rect(-10.0, -10.0, -5.0, -5.0));
        assert!(zone.cell_is_alive(&rings));
    }

    #[test]
    fn every_ring_dead_is_dead() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0)]);
        let mut rings = rect(50.0, 50.0, 50.05, 50.05);
        rings.extend(rect(49.9, 49.9, 49.95, 49.95));
        assert!(!zone.cell_is_alive(&rings));
    }

    #[test]
    fn a_cell_with_no_rings_is_dead() {
        let zone = AliveZone::new(BOARD);
        assert!(!zone.cell_is_alive(&[]));
        assert!(!zone.cell_is_alive(&[Vec::new()]));
    }

    #[test]
    fn a_cell_deep_in_overlapping_dead_zones_is_dead() {
        let zone = carve_all(BOARD, &[p(50.0, 50.0), p(52.0, 50.0)]);
        assert!(!zone.cell_is_alive(&rect(51.0, 50.0, 51.05, 50.05)));
    }

    #[test]
    fn a_grid_of_dead_zones_kills_only_what_it_covers() {
        let zone = carve_all(
            BOARD,
            &[p(30.0, 30.0), p(70.0, 30.0), p(30.0, 70.0), p(70.0, 70.0)],
        );
        assert!(zone.cell_is_alive(&rect(48.0, 48.0, 52.0, 52.0)));
        assert!(!zone.cell_is_alive(&rect(30.0, 30.0, 30.1, 30.1)));
    }

    #[test]
    fn a_hole_is_not_part_of_the_cell_for_reverse_containment() {
        // The zone's only content is a forced eye, and it sits in the hull's
        // hole — which is not part of the cell, so it does not revive it. On a
        // packed board there is no outline for the other two tests to find.
        let mut zone = packed();
        zone.add_forced_eye(ONLY_POSITION);

        // Both rings are well clear of the eye — the edge-proximity test scans
        // every ring, holes included, so a hole hugging the eye would keep the
        // cell alive through that test rather than this one.
        let square = |half: f64| {
            vec![
                p(ONLY_POSITION.x - half, ONLY_POSITION.y - half),
                p(ONLY_POSITION.x - half, ONLY_POSITION.y + half),
                p(ONLY_POSITION.x + half, ONLY_POSITION.y + half),
                p(ONLY_POSITION.x + half, ONLY_POSITION.y - half),
            ]
        };
        let hull = square(2.0 * TINY_BOARD);
        let hole = square(TINY_BOARD);

        assert!(zone.cell_is_alive(core::slice::from_ref(&hull)));
        assert!(!zone.cell_is_alive(&[hull, hole]));
    }

    // ── The ring walk ────────────────────────────────────────────────────────

    #[test]
    fn a_ring_is_walked_as_a_closed_loop() {
        let square: Vec<Point> = [(0.0, 0.0), (0.0, 1.0), (1.0, 1.0), (1.0, 0.0)]
            .iter()
            .map(|(x, y)| p(*x, *y))
            .collect();
        let walked: Vec<LineSegment> = edges(&square).collect();

        assert_eq!(walked.len(), 4);
        assert_eq!(walked.last().unwrap().b, p(0.0, 0.0));
    }

    #[test]
    fn a_ring_too_short_to_enclose_anything_has_no_edges() {
        assert_eq!(edges(&[]).count(), 0);
        assert_eq!(edges(&[p(0.0, 0.0)]).count(), 0);
    }
}