voronoi-go 1.0.1

//! The alive zone: where a stone centre may still be placed.
//!
//! The playable area is the board inset by one stone radius, minus a disc of
//! [`STONE_DIAMETER`] radius around every stone. It is held as a set of shapes
//! clipped against one another, and
//! this module is the policy over that structure: which shapes exist, when they
//! are carved and taken away again, and what counts as playable.
//!
//! # Carving and reclaiming
//!
//! [`AliveZone::remove_circle`] carves the dead zone around a new stone out of
//! the playable area. [`AliveZone::reclaim_circle`] gives it back when that
//! stone is captured or the move is undone, and the two are exact inverses:
//! carving the same centre again recomputes bit-identical crossing points and
//! finds the very segments that survived the reclaim. `docs/design.md` § "Undo
//! is bit-exact" explains why that matters more here than it would in a program
//! a person watches.
//!
//! Reclaiming garbage-collects as it goes. A segment exists only to mark a
//! crossing, so when the reclaimed shape's segment at some point goes and
//! exactly one segment is left there, that survivor has nothing left to mark and
//! goes too. Where three shapes meet at one point it does not: two survivors are
//! still marking each other's crossing.
//!
//! # Forced eyes
//!
//! A captured stone's exact position stays playable even though it sits inside
//! its neighbours' dead zones. The forced-eye set is what says so, and a point
//! at a forced eye is inside the alive zone regardless of what covers it —
//! [`AliveZone::remove_forced_eyes_near_point`] is where the two behaviours
//! that removal has, and the reason for them, are written down.
//!
//! # Asking
//!
//! [`AliveZone::contains`] is here; the queries that read the clipped outline
//! rather than the shapes — [`AliveZone::closest_point`],
//! [`AliveZone::closest_distance`] and [`AliveZone::cell_is_alive`] — sit
//! alongside it, and carry the rule that an empty zone is infinitely far away
//! rather than zero away.
//!
//! # Asking "and what if a stone were there?"
//!
//! Cut evaluation needs the *second*-best position for an enemy stone, which
//! means carving the best one's dead zone and asking again.
//! [`AliveZone::with_temp_circle`] is the only way to do that, and it is a
//! closure precisely so the carve cannot outlive the question: the restore hangs
//! off a guard's `Drop`, so an early return or a panic inside the closure
//! restores just as a normal return does. A leaked temporary circle would carve
//! a hole in the board that nothing could ever name to reclaim, which is what
//! [`ZoneError::UnnamedDeadZone`] exists to catch.

mod forced_eyes;
mod queries;
#[cfg(feature = "svg")]
#[cfg_attr(docsrs, doc(cfg(feature = "svg")))]
mod svg;
mod validate;

use std::collections::BTreeMap;

use thiserror::Error;

use crate::clipping::{ClippingGraph, Segment, ShapeId};
use crate::geometry::{Circle, point_is_on_board};
use crate::{EPSILON, Point, STONE_DIAMETER, StoneId};

use forced_eyes::ForcedEyes;

pub use validate::ZoneError;

/// Carving or reclaiming a dead zone that the alive zone cannot account for.
///
/// Neither variant is reachable from user input: a move is checked for
/// placeability before any of this runs, and a stone id is issued once and
/// never reused. They exist so that a bug in the caller surfaces as an error
/// rather than as a silently corrupted board.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Error)]
pub enum DeadZoneError {
    /// A dead zone has already been carved for this stone. Carving a second one
    /// would strand the first, which nothing could then reclaim.
    #[error("stone {stone}'s dead zone has already been carved out of the alive zone")]
    AlreadyCarved {
        /// The stone.
        stone: StoneId,
    },

    /// There is no dead zone carved for this stone to reclaim.
    #[error("stone {stone} has no dead zone carved out of the alive zone")]
    NotCarved {
        /// The stone.
        stone: StoneId,
    },
}

/// Everywhere a stone centre may still be placed.
///
/// # Invariants
///
/// Every mutating method restores all of these before it returns, and checks
/// them with [`AliveZone::validate`] under `cfg(debug_assertions)`:
///
/// - The clipping structure underneath holds all of its own invariants.
/// - Stones and dead zones name each other one-for-one: every stone's dead zone
///   is in the graph, no two stones share one, and no dead zone is left in the
///   graph that neither a stone nor a live [`AliveZone::with_temp_circle`] call
///   can name.
/// - Every forced eye is filed under its own point's key.
#[derive(Clone, Debug)]
pub struct AliveZone {
    /// The shapes the playable area is clipped out of.
    graph: ClippingGraph,
    /// The dead zone carved for each stone. A `BTreeMap` keeps iteration
    /// reproducible.
    dead_zones: BTreeMap<StoneId, ShapeId>,
    /// Positions kept playable by fiat.
    forced_eyes: ForcedEyes,
    /// Dead zones carved by a [`AliveZone::with_temp_circle`] call that has not
    /// returned yet, innermost last.
    ///
    /// Empty at every point a caller can observe: the only thing that pushes
    /// onto it is `with_temp_circle`, and the only thing that pops is the guard
    /// it drops on the way out. It is a stack rather than a single slot so that
    /// nesting one measurement inside another is a well-defined thing to do
    /// rather than a silent leak of the outer one.
    temp_circles: Vec<ShapeId>,
}

impl AliveZone {
    /// The whole of a `board_size` board, inset by one stone radius, with no
    /// stones on it.
    #[must_use]
    pub fn new(board_size: f64) -> Self {
        let zone = Self {
            graph: ClippingGraph::new(board_size),
            dead_zones: BTreeMap::new(),
            forced_eyes: ForcedEyes::new(),
            temp_circles: Vec::new(),
        };
        zone.debug_validate();
        zone
    }

    /// Width and height of the board.
    #[must_use]
    pub const fn board_size(&self) -> f64 {
        self.graph.board_size()
    }

    // ── Dead zones ───────────────────────────────────────────────────────────

    /// Carves the dead zone around a stone at `center` out of the playable
    /// area, clipping it against every shape already there.
    ///
    /// # Errors
    ///
    /// [`DeadZoneError::AlreadyCarved`] if this stone's dead zone is already
    /// carved. A stone id is issued once and never reused, so this means the
    /// caller has lost track of the board.
    pub fn remove_circle(&mut self, stone: StoneId, center: Point) -> Result<(), DeadZoneError> {
        if self.dead_zones.contains_key(&stone) {
            return Err(DeadZoneError::AlreadyCarved { stone });
        }

        let zone = self.carve(center);
        self.dead_zones.insert(stone, zone);
        self.debug_validate();
        Ok(())
    }

    /// Cuts a disc of [`STONE_DIAMETER`] radius about `center` out of the
    /// playable area, and answers the shape it added.
    ///
    /// Deliberately does **not** validate: until the caller has recorded who the
    /// new shape belongs to, it is a dead zone nothing names, which is exactly
    /// what [`AliveZone::validate`] is there to reject.
    fn carve(&mut self, center: Point) -> ShapeId {
        self.compound(|zone| {
            // Collected before the new shape exists, so that it is not clipped
            // against itself.
            let targets: Vec<ShapeId> = zone.graph.shape_ids().collect();
            let dead_zone = zone.graph.add_dead_zone(center);
            let circle = Circle::new(center, STONE_DIAMETER);

            for target in targets {
                // `None` only where the two do not properly cross, or where a
                // shape has vanished mid-clip, which cannot happen.
                let _ = zone.clip(target, dead_zone, circle);
            }

            dead_zone
        })
    }

    /// Runs `f` as a single mutating operation, with the clipping structure's
    /// own per-mutation check deferred until it returns.
    ///
    /// A carve or a reclaim is one operation to a caller and dozens of segment
    /// insertions, deletions and covered-run markings underneath, each of which
    /// checks the whole structure — which makes the pair quadratic in the size
    /// of the board and dominates a debug build completely. The check is not
    /// skipped, only moved: `f`'s caller validates the zone in full, which
    /// delegates to the very same structural check, and mid-carve is a state
    /// the zone's own invariants do not hold in anyway — a dead zone exists
    /// there that no stone has been told about yet.
    ///
    /// **The resume is structural, not a convention**, on the same terms as
    /// [`AliveZone::with_temp_circle`]: it hangs off a guard's `Drop`, so a
    /// panic unwinding out of `f` cannot leave the structure with its check
    /// suspended for the rest of the run.
    fn compound<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T {
        /// Puts the structure's own check back when it goes out of scope.
        struct Resume<'zone> {
            /// The zone whose structure the check was deferred on.
            zone: &'zone mut AliveZone,
        }

        impl Drop for Resume<'_> {
            fn drop(&mut self) {
                self.zone.graph.resume_validation();
            }
        }

        self.graph.defer_validation();

        // A reborrow, not a move: the guard keeps hold of the zone, so its
        // `Drop` still runs however `f` leaves.
        let guard = Resume { zone: self };
        f(&mut *guard.zone)
    }

    /// Splits `target` and `zone` where they cross, and marks the stretch of
    /// each that the other covers.
    ///
    /// Answers `None` when the two do not properly cross — tangency included,
    /// which is rejected rather than smoothed.
    fn clip(&mut self, target: ShapeId, zone: ShapeId, circle: Circle) -> Option<()> {
        let crossing = self.graph.intersect(target, circle)?;

        // The target enters the dead zone at the entry point, so the stretch of
        // the target starting there is the covered one — and the stretch of the
        // dead zone starting there is the one outside the target. The exit point
        // is the mirror of that.
        let target_covered = self.graph.insert_or_get_existing(target, crossing.entry)?;
        let zone_uncovered = self.graph.insert_or_get_existing(zone, crossing.entry)?;
        let target_uncovered = self.graph.insert_or_get_existing(target, crossing.exit)?;
        let zone_covered = self.graph.insert_or_get_existing(zone, crossing.exit)?;

        self.graph
            .add_overlapping(target_covered, target_uncovered, zone);
        self.graph
            .add_overlapping(zone_covered, zone_uncovered, target);
        Some(())
    }

    /// Gives a stone's dead zone back to the playable area.
    ///
    /// Every other shape forgets the dead zone first, so that the stretches it
    /// was covering become visible again. Then the dead zone's own segments go,
    /// and with each of them any segment left alone at the same point: segments
    /// exist only to mark crossings, and a crossing needs two shapes. What
    /// survives is exactly the structure there was before the dead zone was
    /// carved.
    ///
    /// # Errors
    ///
    /// [`DeadZoneError::NotCarved`] if no dead zone is carved for this stone.
    pub fn reclaim_circle(&mut self, stone: StoneId) -> Result<(), DeadZoneError> {
        let zone = self
            .dead_zones
            .remove(&stone)
            .ok_or(DeadZoneError::NotCarved { stone })?;

        self.uncarve(zone);
        self.debug_validate();
        Ok(())
    }

    /// Gives the area a carved shape was covering back, and takes the shape out
    /// of the graph.
    ///
    /// The mirror of [`AliveZone::carve`], and it does not validate either: the
    /// caller still has to forget the shape it was naming.
    fn uncarve(&mut self, dead_zone: ShapeId) {
        self.compound(|zone| {
            let others: Vec<ShapeId> = zone
                .graph
                .shape_ids()
                .filter(|id| *id != dead_zone)
                .collect();
            for other in others {
                zone.graph.remove_overlapping(other, dead_zone);
            }

            for node in zone.graph.node_ids(dead_zone) {
                let Some(point) = zone.graph.segment(node).map(Segment::point) else {
                    continue;
                };
                zone.graph.delete_segment(node);
                if let Some(orphan) = zone.graph.sole_segment_at(point) {
                    zone.graph.delete_segment(orphan);
                }
            }

            let _ = zone.graph.remove_shape(dead_zone);
        });
    }

    /// Whether a dead zone is carved for `stone`.
    #[must_use]
    pub fn has_circle(&self, stone: StoneId) -> bool {
        self.dead_zones.contains_key(&stone)
    }

    /// Answers `f` with a stone's dead zone temporarily carved at `center`, and
    /// puts the zone back exactly as it was before returning.
    ///
    /// This is the "and what if a stone were there?" question, and the only way
    /// to ask it. Cut evaluation needs the second-best position for an enemy
    /// stone, which is [`AliveZone::closest_point`] asked again with the best
    /// one's dead zone in the way.
    ///
    /// **The restore is structural, not a convention.** It hangs off a guard's
    /// `Drop`, so every way out of `f` — a value, an early return, a `?`, a
    /// panic unwinding through it — goes through the same restore. A call placed
    /// after `f` would be skipped by exactly the case that matters, and a leaked
    /// temporary circle is not a transient error: it is a hole in the board that
    /// no stone names and nothing can ever reclaim.
    ///
    /// The round trip is bit-exact, on the same terms as
    /// [`AliveZone::reclaim_circle`], so nothing downstream can tell that the
    /// question was asked.
    pub fn with_temp_circle<T>(&mut self, center: Point, f: impl FnOnce(&mut Self) -> T) -> T {
        /// Puts the innermost temporary circle back when it goes out of scope.
        struct Restore<'zone> {
            /// The zone to restore.
            zone: &'zone mut AliveZone,
        }

        impl Drop for Restore<'_> {
            fn drop(&mut self) {
                if let Some(temp) = self.zone.temp_circles.pop() {
                    self.zone.uncarve(temp);
                    self.zone.debug_validate();
                }
            }
        }

        let temp = self.carve(center);
        self.temp_circles.push(temp);
        self.debug_validate();

        // A reborrow, not a move: the guard keeps hold of the zone, so its
        // `Drop` still runs however `f` leaves.
        let guard = Restore { zone: self };
        f(&mut *guard.zone)
    }

    // ── Forced eyes ──────────────────────────────────────────────────────────

    /// Marks `point` playable regardless of what covers it.
    pub fn add_forced_eye(&mut self, point: Point) {
        self.forced_eyes.insert(point);
        self.debug_validate();
    }

    /// Takes the mark off exactly `point`, and answers whether there was one.
    pub fn remove_forced_eye(&mut self, point: Point) -> bool {
        let removed = self.forced_eyes.take(point).is_some();
        self.debug_validate();
        removed
    }

    /// Whether there is a forced eye at exactly `point`.
    #[must_use]
    pub fn has_forced_eye(&self, point: Point) -> bool {
        self.forced_eyes.contains(point)
    }

    /// Every forced eye, in a reproducible order.
    pub fn forced_eyes(&self) -> impl Iterator<Item = Point> + '_ {
        self.forced_eyes.iter()
    }

    /// How many forced eyes there are.
    #[must_use]
    pub fn forced_eye_count(&self) -> usize {
        self.forced_eyes.len()
    }

    /// Removes the forced eyes a new stone at `center` consumes, and answers
    /// them.
    ///
    /// Two behaviours, both intended:
    ///
    /// - An **exact** hit removes only the eye at that point and leaves its
    ///   neighbours alone. Replaying a move into an eye must not disturb the
    ///   other eyes of the same capture, which in a tight position can sit
    ///   within a hair of it.
    /// - Otherwise every eye within [`STONE_DIAMETER`] goes, because the new
    ///   stone's dead zone consumes them. That is a geometric rule about the
    ///   stone, not a tolerance on identity.
    pub fn remove_forced_eyes_near_point(&mut self, center: Point) -> Vec<Point> {
        if let Some(exact) = self.forced_eyes.take(center) {
            self.debug_validate();
            return vec![exact];
        }

        let removed: Vec<Point> = self
            .forced_eyes
            .iter()
            .filter(|eye| eye.distance(center) <= STONE_DIAMETER)
            .collect();
        for eye in &removed {
            self.forced_eyes.take(*eye);
        }

        self.debug_validate();
        removed
    }

    // ── Queries ──────────────────────────────────────────────────────────────

    /// Whether `point` is in the playable area.
    ///
    /// A forced eye is playable whatever covers it. Otherwise the point is
    /// playable exactly when no shape contains it: it is on the board, and
    /// outside every stone's dead zone.
    ///
    /// A point that is not a position on this board at all — off the rectangle,
    /// or with a coordinate that is not a number — is not in the playable area,
    /// and is rejected before any shape is asked. See
    /// [`point_is_on_board`].
    ///
    /// This is the **exact** predicate the alive zone is defined by, with no
    /// slack anywhere in it. A move is judged by [`AliveZone::is_placeable`]
    /// instead, for the reason stated there.
    #[must_use]
    pub fn contains(&self, point: Point) -> bool {
        self.deepest(point) <= 0.0
    }

    /// Whether a stone centre may be placed at `point`.
    ///
    /// [`AliveZone::contains`] with [`EPSILON`] of slack, and the difference
    /// matters for exactly one input: a position that came out of
    /// [`AliveZone::closest_point`]. Such a position lies *on* the outline —
    /// often on a point where a dead zone crosses another shape — and the
    /// crossing was computed by intersecting the two, while this test
    /// recomputes its distance from a centre. The two arithmetics agree to a
    /// few parts in `10^15` and then land the position on either side of the
    /// rim at random.
    ///
    /// So the exact predicate would reject about half of the positions the zone
    /// itself names as the nearest playable one, which is not a rule anybody
    /// could play by. The slack is a magnitude test against a real distance —
    /// see `docs/design.md` § "A snapped position is placeable" — and is seven
    /// orders of magnitude below [`STONE_DIAMETER`], the smallest distance the
    /// game distinguishes.
    #[must_use]
    pub fn is_placeable(&self, point: Point) -> bool {
        self.deepest(point) <= EPSILON
    }

    /// How far inside the covered area `point` lies, across every shape:
    /// positive where something covers it, zero on an outline, negative in the
    /// clear. A forced eye is [`f64::NEG_INFINITY`] — nothing covers it, by
    /// fiat — and anything that is not a position on this board is
    /// [`f64::INFINITY`].
    ///
    /// The off-board case is checked **first**, and it is not redundant with the
    /// board's own edge shapes. Every shape's depth is a subtraction, and a
    /// coordinate that is not a number makes every one of them `NaN`;
    /// [`f64::max`] discards a `NaN` operand, so the fold below would answer
    /// [`f64::NEG_INFINITY`] — the deepest possible *clearance* — for a position
    /// that does not exist. See `docs/design.md` § "A position is a point on the
    /// board".
    fn deepest(&self, point: Point) -> f64 {
        if !point_is_on_board(point, self.board_size()) {
            return f64::INFINITY;
        }

        if self.forced_eyes.contains(point) {
            return f64::NEG_INFINITY;
        }

        self.graph
            .shapes()
            .map(|(_, shape)| shape.kind().depth(point))
            .fold(f64::NEG_INFINITY, f64::max)
    }
}

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

    use std::collections::BTreeSet;

    use super::{AliveZone, DeadZoneError};
    use crate::clipping::{Segment, Shape, ShapeId};
    use crate::{Point, STONE_DIAMETER, StoneId};

    const BOARD: f64 = 20.0;

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

    fn s(id: u32) -> StoneId {
        StoneId::new(id)
    }

    /// 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(s(index as u32), *center).unwrap();
            assert_eq!(zone.validate(), Ok(()));
        }
        zone
    }

    /// Whether `point` is inside the alive zone, at every probe of an evenly
    /// spaced grid — the observable the fixture's `contains` probes take.
    fn probe_grid(zone: &AliveZone, steps: usize) -> Vec<bool> {
        let size = zone.board_size();
        let coordinate = |n: usize| size * (n as f64 + 1.0) / (steps as f64 + 1.0);
        let mut probes = Vec::with_capacity(steps * steps);
        for row in 0..steps {
            for column in 0..steps {
                probes.push(zone.contains(p(coordinate(row), coordinate(column))));
            }
        }
        probes
    }

    // ── Carving ──────────────────────────────────────────────────────────────

    #[test]
    fn a_new_zone_is_the_board_and_nothing_else() {
        let zone = AliveZone::new(BOARD);
        assert_eq!(zone.validate(), Ok(()));
        assert_eq!(zone.board_size().to_bits(), BOARD.to_bits());
        assert_eq!(zone.graph.shape_ids().count(), 4);
        assert_eq!(zone.forced_eye_count(), 0);
    }

    #[test]
    fn a_single_dead_zone_is_carved_and_named() {
        let zone = carve_all(BOARD, &[p(10.0, 10.0)]);
        assert!(zone.has_circle(s(0)));
        assert!(!zone.has_circle(s(1)));
        assert_eq!(zone.graph.shape_ids().count(), 5);
    }

    #[test]
    fn dead_zones_that_do_not_touch_leave_each_other_whole() {
        let zone = carve_all(
            BOARD,
            &[p(5.0, 5.0), p(15.0, 5.0), p(5.0, 15.0), p(15.0, 15.0)],
        );
        for stone in 0..4 {
            let shape = *zone.dead_zones.get(&s(stone)).unwrap();
            assert_eq!(zone.graph.shape(shape).unwrap().count(), 0);
        }
    }

    #[test]
    fn overlapping_dead_zones_split_each_other() {
        let zone = carve_all(BOARD, &[p(10.0, 10.0), p(12.0, 10.0)]);
        for stone in 0..2 {
            let shape = *zone.dead_zones.get(&s(stone)).unwrap();
            assert_eq!(zone.graph.shape(shape).unwrap().count(), 2);
            // One arc inside the other disc, one outside.
            assert_eq!(
                zone.graph
                    .segments(shape)
                    .filter(|id| zone.graph.is_active(*id))
                    .count(),
                1
            );
        }
    }

    #[test]
    fn a_dead_zone_surrounded_on_every_side_has_nothing_visible_left() {
        // A ring of six, close enough that consecutive neighbours overlap each
        // other as well as the middle one.
        let spacing = STONE_DIAMETER * 1.5;
        let mut centers: Vec<Point> = (0..6)
            .map(|step| {
                let angle = f64::from(step) * core::f64::consts::TAU / 6.0;
                p(10.0 + spacing * angle.cos(), 10.0 + spacing * angle.sin())
            })
            .collect();
        centers.push(p(10.0, 10.0));

        let zone = carve_all(BOARD, &centers);
        let middle = *zone.dead_zones.get(&s(6)).unwrap();
        assert!(
            zone.graph
                .segments(middle)
                .all(|id| !zone.graph.is_active(id))
        );
        assert!(!zone.contains(p(10.0, 10.0)));
    }

    #[test]
    fn a_dead_zone_against_an_edge_splits_the_edge() {
        let zone = carve_all(BOARD, &[p(2.0, 10.0)]);
        let left = zone.graph.shape_ids().next().unwrap();
        // The edge gained a segment at each crossing, on top of the four nodes
        // it starts with.
        assert_eq!(zone.graph.shape(left).unwrap().count(), 6);
        assert!(
            zone.graph
                .segments(left)
                .any(|id| !zone.graph.is_active(id))
        );
    }

    #[test]
    fn a_dead_zone_at_a_corner_splits_both_edges() {
        let zone = carve_all(BOARD, &[p(2.0, 2.0)]);
        let shape = *zone.dead_zones.get(&s(0)).unwrap();
        assert_eq!(zone.graph.shape(shape).unwrap().count(), 4);
    }

    #[test]
    fn carving_the_same_stone_twice_is_refused() {
        let mut zone = carve_all(BOARD, &[p(10.0, 10.0)]);
        assert_eq!(
            zone.remove_circle(s(0), p(4.0, 4.0)),
            Err(DeadZoneError::AlreadyCarved { stone: s(0) })
        );
        // And it changed nothing.
        assert_eq!(zone.graph.shape_ids().count(), 5);
        assert_eq!(zone.validate(), Ok(()));
    }

    #[test]
    fn a_progressive_run_of_overlaps_stays_consistent() {
        let centers: Vec<Point> = (0..5).map(|i| p(5.0 + f64::from(i) * 1.5, 10.0)).collect();
        let zone = carve_all(BOARD, &centers);
        assert_eq!(zone.validate(), Ok(()));
    }

    // ── Reclaiming ───────────────────────────────────────────────────────────

    #[test]
    fn reclaiming_a_stone_that_has_no_dead_zone_is_refused() {
        let mut zone = AliveZone::new(BOARD);
        assert_eq!(
            zone.reclaim_circle(s(3)),
            Err(DeadZoneError::NotCarved { stone: s(3) })
        );
    }

    #[test]
    fn reclaiming_takes_the_shape_and_its_crossings_away() {
        let mut zone = carve_all(BOARD, &[p(10.0, 10.0), p(12.0, 10.0)]);
        let reclaimed = *zone.dead_zones.get(&s(1)).unwrap();
        let survivor = *zone.dead_zones.get(&s(0)).unwrap();

        zone.reclaim_circle(s(1)).unwrap();

        assert!(zone.graph.shape(reclaimed).is_none());
        assert!(!zone.has_circle(s(1)));
        // The survivor's crossings had nothing left to mark, so they went too.
        assert_eq!(zone.graph.shape(survivor).unwrap().count(), 0);
        assert_eq!(zone.validate(), Ok(()));
    }

    #[test]
    fn reclaiming_gives_the_area_back() {
        let mut zone = carve_all(BOARD, &[p(10.0, 10.0)]);
        assert!(!zone.contains(p(10.5, 10.0)));

        zone.reclaim_circle(s(0)).unwrap();
        assert!(zone.contains(p(10.5, 10.0)));
    }

    #[test]
    fn reclaiming_a_surrounded_dead_zone_restores_its_neighbours() {
        let spacing = STONE_DIAMETER * 1.5;
        let mut zone = carve_all(
            BOARD,
            &[
                p(10.0 + spacing, 10.0),
                p(10.0 - spacing, 10.0),
                p(10.0, 10.0 + spacing),
                p(10.0, 10.0 - spacing),
                p(10.0, 10.0),
            ],
        );

        zone.reclaim_circle(s(4)).unwrap();

        assert_eq!(zone.validate(), Ok(()));
        assert!(zone.contains(p(10.0, 10.0)));
    }

    // ── The round trip that has to be exact ──────────────────────────────────

    #[test]
    fn carving_reclaiming_and_carving_again_reproduces_the_structure() {
        // This is the property the shared-start index exists for: the second
        // carve recomputes bit-identical crossing points and must find the
        // segments that survived the reclaim rather than duplicating them.
        let mut zone = carve_all(BOARD, &[p(6.0, 6.0), p(8.5, 7.0), p(7.0, 9.0)]);
        let carved = zone.fingerprint();
        let probes = probe_grid(&zone, 7);

        zone.reclaim_circle(s(1)).unwrap();
        assert_eq!(zone.validate(), Ok(()));
        assert_ne!(zone.fingerprint(), carved);

        zone.remove_circle(s(1), p(8.5, 7.0)).unwrap();

        assert_eq!(zone.fingerprint(), carved);
        assert_eq!(probe_grid(&zone, 7), probes);
        assert_eq!(zone.validate(), Ok(()));
    }

    #[test]
    fn a_dead_zone_against_an_edge_round_trips_too() {
        // The other crossing a dead zone can have. This one overlaps its
        // neighbour and runs off the left edge of the board.
        let mut zone = carve_all(BOARD, &[p(2.0, 10.0), p(2.0, 13.0)]);
        let carved = zone.fingerprint();

        zone.reclaim_circle(s(1)).unwrap();
        zone.remove_circle(s(1), p(2.0, 13.0)).unwrap();

        assert_eq!(zone.fingerprint(), carved);
    }

    #[test]
    fn unwinding_every_dead_zone_restores_the_empty_board() {
        let centers = [p(5.0, 5.0), p(7.0, 6.0), p(6.0, 8.0), p(9.0, 9.0)];
        let empty = AliveZone::new(BOARD).fingerprint();
        let empty_probes = probe_grid(&AliveZone::new(BOARD), 7);

        let mut zone = carve_all(BOARD, &centers);
        for stone in (0..centers.len() as u32).rev() {
            zone.reclaim_circle(s(stone)).unwrap();
            assert_eq!(zone.validate(), Ok(()));
        }

        assert_eq!(zone.fingerprint(), empty);
        assert_eq!(probe_grid(&zone, 7), empty_probes);
        assert_eq!(zone.graph.segment_count(), 16);
    }

    #[test]
    fn reclaiming_out_of_order_restores_the_empty_board_too() {
        let centers = [p(5.0, 5.0), p(7.0, 6.0), p(6.0, 8.0), p(9.0, 9.0)];
        let empty = AliveZone::new(BOARD).fingerprint();

        let mut zone = carve_all(BOARD, &centers);
        for stone in [1_u32, 3, 0, 2] {
            zone.reclaim_circle(s(stone)).unwrap();
        }

        assert_eq!(zone.fingerprint(), empty);
    }

    // ── The temporary circle ─────────────────────────────────────────────────

    #[test]
    fn a_temporary_circle_is_there_inside_the_closure() {
        let mut zone = carve_all(BOARD, &[p(5.0, 5.0)]);
        assert!(zone.contains(p(12.0, 12.0)));

        let seen = zone.with_temp_circle(p(12.0, 12.0), |zone| {
            assert_eq!(zone.validate(), Ok(()));
            (zone.contains(p(12.0, 12.0)), zone.contains(p(12.5, 12.0)))
        });

        assert_eq!(
            seen,
            (false, false),
            "the temporary dead zone was in the way"
        );
        assert!(zone.contains(p(12.0, 12.0)), "and is not any more");
    }

    #[test]
    fn a_temporary_circle_leaves_the_zone_bit_identical() {
        let mut zone = carve_all(BOARD, &[p(6.0, 6.0), p(8.5, 7.0), p(7.0, 9.0)]);
        let before = zone.fingerprint();
        let probes = probe_grid(&zone, 9);

        // Overlapping two of the three, so the carve really does split things.
        zone.with_temp_circle(p(7.5, 7.5), |zone| {
            assert_eq!(zone.validate(), Ok(()));
        });

        assert_eq!(zone.fingerprint(), before);
        assert_eq!(probe_grid(&zone, 9), probes);
        assert_eq!(zone.validate(), Ok(()));
    }

    #[test]
    fn a_temporary_circle_is_restored_even_when_the_closure_panics() {
        // The whole reason the restore hangs off a guard rather than sitting
        // after the call: a panic skips the call and cannot skip the guard.
        let mut zone = carve_all(BOARD, &[p(6.0, 6.0), p(8.5, 7.0)]);
        let before = zone.fingerprint();

        let unwound = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
            zone.with_temp_circle(p(7.5, 7.5), |_| panic!("the closure gave up"));
        }));

        assert!(unwound.is_err());
        assert_eq!(zone.fingerprint(), before);
        assert_eq!(zone.validate(), Ok(()));
        assert!(zone.temp_circles.is_empty());
    }

    #[test]
    fn a_temporary_circle_is_restored_on_an_early_return() {
        let mut zone = carve_all(BOARD, &[p(6.0, 6.0)]);
        let before = zone.fingerprint();

        let answer = zone.with_temp_circle(p(9.0, 9.0), |zone| {
            if zone.contains(p(9.0, 9.0)) {
                return "still playable";
            }
            "covered"
        });

        assert_eq!(answer, "covered");
        assert_eq!(zone.fingerprint(), before);
    }

    #[test]
    fn temporary_circles_nest() {
        // Not something the cut geometry does, but the stack makes it a defined
        // thing to do rather than a silent leak of the outer circle.
        let mut zone = carve_all(BOARD, &[p(5.0, 5.0)]);
        let before = zone.fingerprint();

        let inner_saw = zone.with_temp_circle(p(11.0, 11.0), |zone| {
            assert_eq!(zone.temp_circles.len(), 1);
            zone.with_temp_circle(p(14.0, 11.0), |zone| {
                assert_eq!(zone.temp_circles.len(), 2);
                assert_eq!(zone.validate(), Ok(()));
                (zone.contains(p(11.0, 11.0)), zone.contains(p(14.0, 11.0)))
            })
        });

        assert_eq!(inner_saw, (false, false));
        assert!(zone.temp_circles.is_empty());
        assert_eq!(zone.fingerprint(), before);
    }

    #[test]
    fn a_temporary_circle_is_not_a_stone_and_cannot_be_reclaimed_by_one() {
        let mut zone = carve_all(BOARD, &[p(5.0, 5.0)]);
        zone.with_temp_circle(p(11.0, 11.0), |zone| {
            assert!(!zone.has_circle(s(1)));
            assert_eq!(
                zone.reclaim_circle(s(1)),
                Err(DeadZoneError::NotCarved { stone: s(1) })
            );
        });
    }

    #[test]
    fn a_stone_can_still_be_carved_while_a_temporary_circle_is_out() {
        let mut zone = carve_all(BOARD, &[p(5.0, 5.0)]);
        zone.with_temp_circle(p(11.0, 11.0), |zone| {
            zone.remove_circle(s(1), p(12.5, 11.0)).unwrap();
            assert_eq!(zone.validate(), Ok(()));
        });
        assert!(zone.has_circle(s(1)));
        assert_eq!(zone.validate(), Ok(()));
    }

    // ── Three shapes through one point ───────────────────────────────────────

    /// Where the three dead zones below all pass.
    const MEETING: Point = Point::new(9.0, 9.0);

    /// Three centres exactly [`STONE_DIAMETER`] from [`MEETING`], evenly spaced
    /// around it, so that all three outlines pass through that one point.
    ///
    /// This is the configuration `docs/design.md` § "Three shapes through one
    /// point" is about, and the arithmetic is what makes it interesting: two of
    /// the three pairs cross at *exactly* the same coordinates, and the third
    /// pair crosses one ulp away from them.
    fn concurrent_triple() -> Vec<Point> {
        let third = core::f64::consts::TAU / 3.0;
        (0..3)
            .map(|step| {
                let angle = f64::from(step) * third;
                p(
                    MEETING.x + STONE_DIAMETER * angle.cos(),
                    MEETING.y + STONE_DIAMETER * angle.sin(),
                )
            })
            .collect()
    }

    #[test]
    fn three_dead_zones_through_one_point_meet_there_exactly() {
        let zone = carve_all(BOARD, &concurrent_triple());

        // Three segments start at the meeting point, one on each dead zone.
        let meeting = zone.graph.segments_at(MEETING);
        assert_eq!(meeting.len(), 3);
        let owners: BTreeSet<ShapeId> = meeting
            .iter()
            .filter_map(|id| zone.graph.segment(*id).map(Segment::parent))
            .collect();
        assert_eq!(owners.len(), 3);

        // Two of the three pairs put their crossing on those very bits, so the
        // last dead zone carved is split into three arcs rather than four: two
        // of its four crossings are one and the same segment.
        let counts: Vec<usize> = (0..3)
            .filter_map(|stone| zone.dead_zones.get(&s(stone)))
            .filter_map(|shape| zone.graph.shape(*shape))
            .map(Shape::count)
            .collect();
        assert_eq!(counts, vec![4, 4, 3]);
        assert_eq!(zone.validate(), Ok(()));
    }

    #[test]
    fn the_third_pair_crosses_a_hair_away_and_is_therefore_a_second_point() {
        // The remaining pair's crossing misses the meeting point by about two
        // parts in 10^15 — the arithmetic that finds it starts from a different
        // pair of centres. Identity is exact, so that is a different point, and
        // it gets its own pair of segments and a sub-ulp arc between them.
        let zone = carve_all(BOARD, &concurrent_triple());
        let first = *zone.dead_zones.get(&s(0)).unwrap();

        let near_misses: Vec<Point> = zone
            .graph
            .node_ids(first)
            .into_iter()
            .filter_map(|id| zone.graph.segment(id).map(Segment::point))
            .filter(|point| *point != MEETING && point.distance(MEETING) < 1e-12)
            .collect();

        let [near_miss] = near_misses.as_slice() else {
            panic!("expected exactly one near miss, got {near_misses:?}");
        };
        assert_eq!(zone.graph.segments_at(*near_miss).len(), 2);
        // Both slivers are covered, so nothing visible depends on them.
        for id in zone.graph.node_ids(first) {
            let Some(point) = zone.graph.segment(id).map(Segment::point) else {
                continue;
            };
            if point.distance(MEETING) < 1e-12 {
                assert!(!zone.graph.is_active(id));
            }
        }
    }

    #[test]
    fn a_crossing_three_shapes_share_survives_the_collector() {
        // The collector deletes a survivor only when it is *the* survivor. Two
        // segments left at the meeting point are still marking each other's
        // crossing, so neither goes.
        let mut zone = carve_all(BOARD, &concurrent_triple());
        zone.reclaim_circle(s(2)).unwrap();

        assert_eq!(zone.graph.segments_at(MEETING).len(), 2);
        assert_eq!(zone.validate(), Ok(()));
    }

    #[test]
    fn the_meeting_point_drains_however_the_dead_zones_are_reclaimed() {
        // Whichever order they go in, nothing is left stranded at the point all
        // three passed through.
        for order in [
            [0_u32, 1, 2],
            [0, 2, 1],
            [1, 0, 2],
            [1, 2, 0],
            [2, 0, 1],
            [2, 1, 0],
        ] {
            let mut zone = carve_all(BOARD, &concurrent_triple());
            for stone in order {
                zone.reclaim_circle(s(stone)).unwrap();
                assert_eq!(zone.validate(), Ok(()));
            }
            assert!(zone.graph.segments_at(MEETING).is_empty(), "{order:?}");
            assert_eq!(zone.graph.segment_count(), 16, "{order:?}");
        }
    }

    #[test]
    fn the_concurrent_triple_round_trips_exactly() {
        let mut zone = carve_all(BOARD, &concurrent_triple());
        let carved = zone.fingerprint();
        let last = *concurrent_triple().last().unwrap();

        zone.reclaim_circle(s(2)).unwrap();
        zone.remove_circle(s(2), last).unwrap();

        assert_eq!(zone.fingerprint(), carved);
    }

    // ── Near-tangency ────────────────────────────────────────────────────────

    #[test]
    fn exactly_tangent_dead_zones_do_not_split_each_other() {
        // Two discs that touch at one point split neither: the crossing they
        // would share is a single point, and the square root that finds it goes
        // negative on the wrong side of the branch. The guard stays.
        let zone = carve_all(BOARD, &[p(6.0, 9.0), p(6.0 + 2.0 * STONE_DIAMETER, 9.0)]);
        for stone in 0..2 {
            let shape = *zone.dead_zones.get(&s(stone)).unwrap();
            assert_eq!(zone.graph.shape(shape).unwrap().count(), 0);
        }
    }

    // ── Forced eyes ──────────────────────────────────────────────────────────

    #[test]
    fn forced_eyes_are_added_and_found_exactly() {
        let mut zone = AliveZone::new(BOARD);
        zone.add_forced_eye(p(10.0, 10.0));
        zone.add_forced_eye(p(12.0, 12.0));

        assert_eq!(zone.forced_eye_count(), 2);
        assert!(zone.has_forced_eye(p(10.0, 10.0)));
        assert!(zone.has_forced_eye(p(12.0, 12.0)));
        assert!(!zone.has_forced_eye(p(10.0, 10.000_000_1)));
    }

    #[test]
    fn a_forced_eye_is_removed_by_its_own_point() {
        let mut zone = AliveZone::new(BOARD);
        zone.add_forced_eye(p(10.0, 10.0));

        assert!(zone.remove_forced_eye(p(10.0, 10.0)));
        assert_eq!(zone.forced_eye_count(), 0);
        // Removing one that is not there changes nothing.
        assert!(!zone.remove_forced_eye(p(15.0, 15.0)));
        assert_eq!(zone.forced_eye_count(), 0);
    }

    #[test]
    fn a_new_stone_consumes_the_forced_eyes_around_it() {
        let mut zone = AliveZone::new(BOARD);
        for eye in [p(10.0, 10.0), p(10.0, 12.0), p(12.0, 12.0)] {
            zone.add_forced_eye(eye);
        }

        let removed = zone.remove_forced_eyes_near_point(p(10.0, 11.0));

        assert_eq!(removed, vec![p(10.0, 10.0), p(10.0, 12.0)]);
        assert_eq!(zone.forced_eye_count(), 1);
        assert!(zone.has_forced_eye(p(12.0, 12.0)));
    }

    #[test]
    fn an_exact_hit_leaves_the_eyes_around_it_alone() {
        let mut zone = AliveZone::new(BOARD);
        for eye in [p(10.0, 10.0), p(10.0, 12.0), p(12.0, 12.0)] {
            zone.add_forced_eye(eye);
        }

        let removed = zone.remove_forced_eyes_near_point(p(10.0, 10.0));

        assert_eq!(removed, vec![p(10.0, 10.0)]);
        assert_eq!(zone.forced_eye_count(), 2);
        assert!(zone.has_forced_eye(p(10.0, 12.0)));
    }

    #[test]
    fn an_eye_exactly_a_stone_diameter_away_is_consumed() {
        // The radius sweep is inclusive: the eye sits on the rim of the new
        // stone's dead zone, which the stone still consumes.
        let mut zone = AliveZone::new(BOARD);
        zone.add_forced_eye(p(10.0, 10.0 + STONE_DIAMETER));

        let removed = zone.remove_forced_eyes_near_point(p(10.0, 10.0));
        assert_eq!(removed.len(), 1);
    }

    #[test]
    fn removing_near_a_point_with_nothing_around_it_removes_nothing() {
        let mut zone = AliveZone::new(BOARD);
        zone.add_forced_eye(p(2.0, 2.0));

        assert!(zone.remove_forced_eyes_near_point(p(16.0, 16.0)).is_empty());
        assert_eq!(zone.forced_eye_count(), 1);
    }

    #[test]
    fn forced_eyes_are_walked_in_a_reproducible_order() {
        let build = |order: [Point; 3]| {
            let mut zone = AliveZone::new(BOARD);
            for eye in order {
                zone.add_forced_eye(eye);
            }
            zone.forced_eyes().collect::<Vec<Point>>()
        };

        assert_eq!(
            build([p(9.0, 1.0), p(1.0, 9.0), p(5.0, 5.0)]),
            build([p(5.0, 5.0), p(9.0, 1.0), p(1.0, 9.0)])
        );
    }

    // ── contains ─────────────────────────────────────────────────────────────

    #[test]
    fn every_point_on_an_empty_board_is_playable() {
        let zone = AliveZone::new(100.0);
        assert!(zone.contains(p(50.0, 50.0)));
        assert!(zone.contains(p(10.0, 10.0)));
        assert!(zone.contains(p(90.0, 90.0)));
    }

    #[test]
    fn a_point_off_the_inset_board_is_not_playable() {
        let zone = AliveZone::new(100.0);
        assert!(!zone.contains(p(0.1, 50.0)));
        assert!(!zone.contains(p(99.9, 50.0)));
        assert!(!zone.contains(p(50.0, 0.1)));
        assert!(!zone.contains(p(50.0, 99.9)));
        assert!(!zone.contains(p(-10.0, 50.0)));
        assert!(!zone.contains(p(110.0, 50.0)));
    }

    #[test]
    fn a_point_inside_a_dead_zone_is_not_playable() {
        let zone = carve_all(100.0, &[p(50.0, 50.0)]);
        assert!(!zone.contains(p(50.5, 50.5)));
        assert!(!zone.contains(p(51.0, 50.0)));
        assert!(zone.contains(p(60.0, 50.0)));
        assert!(zone.contains(p(10.0, 10.0)));
    }

    #[test]
    fn a_point_on_the_rim_of_a_dead_zone_is_playable() {
        // Containment is strict, so the rim itself is still placeable — two
        // stones exactly a diameter apart are legal.
        let zone = carve_all(100.0, &[p(50.0, 50.0)]);
        assert!(zone.contains(p(50.0 + STONE_DIAMETER, 50.0)));
    }

    #[test]
    fn several_dead_zones_are_all_consulted() {
        let zone = carve_all(100.0, &[p(30.0, 50.0), p(70.0, 50.0)]);
        assert!(!zone.contains(p(30.0, 50.0)));
        assert!(!zone.contains(p(70.0, 50.0)));
        assert!(zone.contains(p(50.0, 50.0)));
    }

    #[test]
    fn a_point_where_two_dead_zones_overlap_is_not_playable() {
        let zone = carve_all(100.0, &[p(50.0, 50.0), p(51.5, 50.0)]);
        assert!(!zone.contains(p(50.5, 50.0)));
    }

    #[test]
    fn a_forced_eye_is_playable_however_it_is_covered() {
        let mut zone = carve_all(100.0, &[p(50.0, 50.0)]);
        assert!(!zone.contains(p(50.0, 50.0)));

        zone.add_forced_eye(p(50.0, 50.0));
        assert!(zone.contains(p(50.0, 50.0)));
        // Only the eye itself, not its surroundings: the exception is a single
        // position, not a disc.
        assert!(!zone.contains(p(50.5, 50.0)));

        zone.remove_forced_eye(p(50.0, 50.0));
        assert!(!zone.contains(p(50.0, 50.0)));
    }

    #[test]
    fn a_forced_eye_overrides_every_shape_including_a_board_edge() {
        // A forced eye is checked before any shape, boundaries included: an eye
        // just inside the edge is playable even though the inset boundary covers
        // everything within a stone radius of the wall.
        let mut zone = AliveZone::new(100.0);
        zone.add_forced_eye(p(0.5, 50.0));

        assert!(
            !zone.contains(p(0.5, 51.0)),
            "the inset margin still covers"
        );
        assert!(zone.contains(p(0.5, 50.0)));
    }

    #[test]
    fn a_forced_eye_cannot_put_a_position_back_on_the_board() {
        // The domain is the outer statement and the eye is checked inside it, so
        // fiat reaches as far as the shapes and no further. Nothing can reach
        // this in practice — an eye is the position of a stone that was on the
        // board, and `DeltaError::OffBoard` is what keeps that true — but the
        // ordering is the reason it stays unreachable rather than merely
        // unusual. See `docs/design.md` § "A position is a point on the board".
        let mut zone = AliveZone::new(100.0);
        zone.add_forced_eye(p(-5.0, 50.0));
        zone.add_forced_eye(p(f64::NAN, 50.0));

        assert!(!zone.contains(p(-5.0, 50.0)));
        assert!(!zone.contains(p(f64::NAN, 50.0)));
        assert!(!zone.is_placeable(p(-5.0, 50.0)));
    }

    #[test]
    fn segments_are_never_consulted_by_contains() {
        // `contains` asks the shapes, not the outline they have been clipped
        // into, so it answers the same before and after a reclaim rebuilds that
        // outline. `closest_point`, `closest_distance` and `cell_is_alive` are
        // the ones that read the segments.
        let mut zone = carve_all(BOARD, &[p(6.0, 6.0), p(8.5, 7.0), p(7.0, 9.0)]);
        let before = probe_grid(&zone, 9);

        zone.reclaim_circle(s(1)).unwrap();
        zone.remove_circle(s(1), p(8.5, 7.0)).unwrap();

        assert_eq!(probe_grid(&zone, 9), before);
    }

    // ── Bookkeeping ──────────────────────────────────────────────────────────

    #[test]
    fn a_reclaimed_dead_zone_leaves_no_shape_behind() {
        let mut zone = carve_all(BOARD, &[p(5.0, 5.0), p(6.5, 5.0)]);
        assert_eq!(zone.graph.shape_ids().count(), 6);

        zone.reclaim_circle(s(0)).unwrap();
        assert_eq!(zone.graph.shape_ids().count(), 5);

        zone.reclaim_circle(s(1)).unwrap();
        assert_eq!(zone.graph.shape_ids().count(), 4);
        assert_eq!(zone.graph.segment_count(), 16);
    }

    #[test]
    fn a_recarved_dead_zone_gets_a_fresh_shape_id() {
        let mut zone = carve_all(BOARD, &[p(5.0, 5.0)]);
        let first = *zone.dead_zones.get(&s(0)).unwrap();

        zone.reclaim_circle(s(0)).unwrap();
        zone.remove_circle(s(0), p(5.0, 5.0)).unwrap();

        let second = *zone.dead_zones.get(&s(0)).unwrap();
        assert_ne!(first, second);
    }

    #[test]
    fn every_crossing_of_a_carve_is_shared_by_exactly_two_shapes() {
        let zone = carve_all(BOARD, &[p(2.0, 10.0), p(3.5, 11.0), p(10.0, 10.0)]);
        for id in zone.graph.shape_ids().collect::<Vec<ShapeId>>() {
            for node in zone.graph.node_ids(id) {
                let Some(segment) = zone.graph.segment(node) else {
                    continue;
                };
                let shared = zone.graph.segments_at(Segment::point(segment)).len();
                assert!(shared <= 2, "{shared} segments share one point");
            }
        }
    }
}