voronoi-go 1.0.1

//! The graph of clipped shapes: shapes, their segment lists, and the index that
//! ties segments starting at the same point together.

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

use crate::geometry::{Circle, LineSegment};
use crate::{Point, STONE_RADIUS};

use super::segment::{SegId, Segment, SegmentArena};
use super::shape::{Closure, Edge, Intersection, Shape, ShapeId, ShapeKind, Span};
use super::shared_starts::SharedStarts;

/// Every shape the playable area is clipped out of, the segments their outlines
/// have been split into, and the shared-start index over those segments.
///
/// This is the structure, not the policy: it knows how to split an outline at a
/// point, mark a run of segments as covered, and take a shape away again, but it
/// has no opinion about when any of that should happen. The alive zone supplies
/// that.
///
/// # Invariants
///
/// Every mutating method restores all of these before it returns, and checks
/// them with [`ClippingGraph::validate`] under `cfg(debug_assertions)`:
///
/// - A shape's segments are exactly those reachable from its head, they are
///   `count` of them, and the list is circular and symmetric.
/// - Offsets do not decrease as the list is walked from the head, except once
///   at the wrap — and for an open shape that one decrease is the wrap itself,
///   so the head always holds the lowest offset.
/// - The segment arena and the shared-start index agree in both directions.
#[derive(Clone, Debug)]
pub struct ClippingGraph {
    /// Width and height of the board.
    pub(super) board_size: f64,
    /// Shapes by id. A `BTreeMap` keeps iteration reproducible, and ids are
    /// handed out in increasing order, so iteration is also creation order.
    pub(super) shapes: BTreeMap<ShapeId, Shape>,
    /// Every shape's segments.
    pub(super) arena: SegmentArena,
    /// Segments by the point they start at.
    pub(super) shared_starts: SharedStarts,
    /// The next shape id. Shape ids are never reused.
    pub(super) next_shape: usize,
    /// How many compound mutations are in progress — see
    /// [`ClippingGraph::defer_validation`]. Always zero in a release build, and
    /// zero at every point a caller can observe in a debug one.
    pub(super) deferred: usize,
}

impl ClippingGraph {
    /// A graph holding nothing but the four inset edges of a `board_size`
    /// board.
    #[must_use]
    pub fn new(board_size: f64) -> Self {
        let mut graph = Self {
            board_size,
            shapes: BTreeMap::new(),
            arena: SegmentArena::new(),
            shared_starts: SharedStarts::new(),
            next_shape: 0,
            deferred: 0,
        };
        for edge in Edge::ALL {
            graph.add_boundary(edge);
        }
        graph.debug_validate();
        graph
    }

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

    // ── Reading ──────────────────────────────────────────────────────────────

    /// Every shape, in creation order.
    pub fn shapes(&self) -> impl Iterator<Item = (ShapeId, &Shape)> {
        self.shapes.iter().map(|(id, shape)| (*id, shape))
    }

    /// Every shape's id, in creation order.
    pub fn shape_ids(&self) -> impl Iterator<Item = ShapeId> + '_ {
        self.shapes.keys().copied()
    }

    /// The shape `id` names.
    #[must_use]
    pub fn shape(&self, id: ShapeId) -> Option<&Shape> {
        self.shapes.get(&id)
    }

    /// The segment `id` names.
    #[must_use]
    pub fn segment(&self, id: SegId) -> Option<&Segment> {
        self.arena.get(id)
    }

    /// Whether the segment `id` names is part of the visible outline.
    #[must_use]
    pub fn is_active(&self, id: SegId) -> bool {
        self.arena.get(id).is_some_and(Segment::is_active)
    }

    /// How many segments exist across every shape.
    ///
    /// The bound on the outline walk, which leaves its shape and so cannot use
    /// a shape's own count.
    #[cfg(any(feature = "svg", test))]
    #[must_use]
    pub const fn segment_count(&self) -> usize {
        self.arena.len()
    }

    /// The segments of `shape`, walked from its head.
    ///
    /// An open shape's last segment is not yielded: it closes the list without
    /// standing for any piece of outline. The walk is bounded by the shape's
    /// segment count, so a malformed list fails an assertion rather than
    /// spinning.
    #[must_use]
    pub fn segments(&self, shape: ShapeId) -> Segments<'_> {
        let shape = self.shapes.get(&shape);
        let head = shape.and_then(Shape::head);
        Segments {
            arena: &self.arena,
            head,
            current: head,
            closure: shape.map_or(Closure::Closed, Shape::closure),
            budget: shape.map_or(0, Shape::count),
        }
    }

    /// The segments starting at `point`, whichever shape they belong to.
    ///
    /// This is how the outline walk crosses from one shape onto another: at a
    /// crossing, both shapes own a segment starting on the very same point.
    #[cfg(any(feature = "svg", test))]
    #[must_use]
    pub fn segments_at(&self, point: Point) -> &[SegId] {
        self.shared_starts.segments(point)
    }

    /// The one segment starting at `point`, if exactly one does.
    ///
    /// This is the question reclaim garbage collection asks: a segment whose
    /// start nothing else shares is marking a crossing that no longer exists.
    #[must_use]
    pub fn sole_segment_at(&self, point: Point) -> Option<SegId> {
        self.shared_starts.sole_segment(point)
    }

    /// The piece of outline the segment `id` names covers.
    #[must_use]
    pub fn segment_span(&self, id: SegId) -> Option<Span> {
        let segment = self.arena.get(id)?;
        let next = self.arena.get(segment.next)?;
        let kind = self.shapes.get(&segment.parent)?.kind;
        Some(kind.span(segment.start, next.start))
    }

    /// Where `shape`'s outline crosses `circle`, or `None` if it does not
    /// properly cross it.
    #[must_use]
    pub fn intersect(&self, shape: ShapeId, circle: Circle) -> Option<Intersection> {
        self.shapes.get(&shape)?.kind.intersect_circle(circle)
    }

    /// The point on `shape`'s visible outline closest to `point`.
    ///
    /// An outline nothing has split is taken whole — a dead zone that no other
    /// shape touches is still a complete circle. A board edge in that state has
    /// no visible outline at all and answers `None`, which cannot happen: an
    /// edge is split into four pieces the moment it is created.
    #[must_use]
    pub fn shape_closest_point(&self, shape: ShapeId, point: Point) -> Option<Point> {
        let entry = self.shapes.get(&shape)?;
        if !entry.is_subdivided() {
            return entry
                .kind
                .circle()
                .map(|circle| circle.closest_point(point));
        }

        let mut closest = None;
        let mut minimum = f64::INFINITY;
        for id in self.segments(shape) {
            if !self.is_active(id) {
                continue;
            }
            let Some(span) = self.segment_span(id) else {
                continue;
            };
            let candidate = span.closest_point(point);
            let distance = point.distance(candidate);
            if distance < minimum {
                minimum = distance;
                closest = Some(candidate);
            }
        }
        closest
    }

    /// The minimum distance from `line` to `shape`'s visible outline, and
    /// `f64::INFINITY` when the shape has none left.
    #[must_use]
    pub fn shape_closest_distance(&self, shape: ShapeId, line: LineSegment) -> f64 {
        let Some(entry) = self.shapes.get(&shape) else {
            return f64::INFINITY;
        };
        if !entry.is_subdivided() {
            return entry
                .kind
                .circle()
                .map_or(f64::INFINITY, |circle| circle.distance_to_segment(line));
        }

        let mut minimum = f64::INFINITY;
        for id in self.segments(shape) {
            if !self.is_active(id) {
                continue;
            }
            let Some(span) = self.segment_span(id) else {
                continue;
            };
            minimum = minimum.min(span.distance_to_segment(line));
            // Distances are never negative, so this is the crossing case.
            if minimum <= 0.0 {
                return 0.0;
            }
        }
        minimum
    }

    // ── Shapes ───────────────────────────────────────────────────────────────

    /// Adds the dead zone around a stone at `center`, with no segments yet.
    pub fn add_dead_zone(&mut self, center: Point) -> ShapeId {
        let id = self.alloc_shape(ShapeKind::dead_zone(center));
        self.debug_validate();
        id
    }

    /// Removes `shape` and every segment it owns.
    ///
    /// **Every other shape must already have forgotten it** — call
    /// [`ClippingGraph::remove_overlapping`] for each of them first. A segment
    /// left marked as covered by a shape that no longer exists would never
    /// become visible again, so the validator treats it as corruption rather
    /// than tidying it away.
    pub fn remove_shape(&mut self, shape: ShapeId) -> Option<ShapeKind> {
        let kind = self.shapes.get(&shape)?.kind;
        for id in self.node_ids(shape) {
            self.delete_segment(id);
        }
        self.shapes.remove(&shape);
        self.debug_validate();
        Some(kind)
    }

    /// Adds one inset board edge, split into the four pieces an edge always
    /// has.
    fn add_boundary(&mut self, edge: Edge) {
        let kind = ShapeKind::boundary(self.board_size, edge);
        let id = self.alloc_shape(kind);

        // The edge is an infinite line, split into: the stretch running off the
        // board before the board starts, the stretch the board occupies, the
        // stretch running off the board after it ends, and a tail that closes
        // the list without standing for any outline. Only the middle stretch is
        // ever visible; the others still clip, which is what stops a dead zone
        // hanging off the end of the board from leaking playable area back in.
        //
        // The off-board stretches stop at a far-away finite offset rather than
        // at infinity, so that every segment has real coordinates to be drawn
        // and measured with.
        let far = 2.0 * self.board_size;
        for (offset, visible) in [
            (-far, false),
            (STONE_RADIUS, true),
            (self.board_size - STONE_RADIUS, false),
            (far, false),
        ] {
            let inserted = self.insert_or_get_existing(id, kind.offset_to_point(offset));
            // Set explicitly rather than relying on what the new segment
            // inherited from its predecessor: the first of these is created
            // before there is anything to inherit from, and the visible stretch
            // is inserted after an off-board one.
            if let Some(segment) = inserted.and_then(|seg| self.arena.get_mut(seg)) {
                segment.force_inactive = !visible;
            }
        }
        self.debug_validate();
    }

    /// Hands out the next shape id.
    fn alloc_shape(&mut self, kind: ShapeKind) -> ShapeId {
        let id = ShapeId::new(self.next_shape);
        self.next_shape += 1;
        self.shapes.insert(id, Shape::new(kind));
        id
    }

    // ── Segments ─────────────────────────────────────────────────────────────

    /// The segment of `shape` starting at `point`, splitting the outline there
    /// if it is not split already.
    ///
    /// The lookup goes through the shared-start index rather than comparing
    /// offsets. That is deliberate and load-bearing: offsets are derived
    /// values, and two segments that agree on an offset are not necessarily the
    /// same crossing, whereas the index is keyed on the exact coordinates the
    /// crossing was computed to. It is what makes carving a dead zone,
    /// reclaiming it, and carving it again find the very segments that survived
    /// the reclaim instead of duplicating them.
    ///
    /// Answers `None` only if `shape` does not exist.
    pub fn insert_or_get_existing(&mut self, shape: ShapeId, point: Point) -> Option<SegId> {
        let (kind, closure, head) = {
            let entry = self.shapes.get(&shape)?;
            (entry.kind, entry.closure, entry.head)
        };
        let offset = kind.point_to_offset(point);

        let Some(head) = head else {
            let id = self.push_segment(shape, point, offset, None);
            if let Some(entry) = self.shapes.get_mut(&shape) {
                entry.head = Some(id);
                entry.count = 1;
            }
            self.debug_validate();
            return Some(id);
        };

        // Does this shape already own a segment starting exactly here?
        let existing = self
            .shared_starts
            .segments(point)
            .iter()
            .copied()
            .find(|id| {
                self.arena
                    .get(*id)
                    .is_some_and(|segment| segment.parent == shape)
            });
        if let Some(existing) = existing {
            return Some(existing);
        }

        let anchor = self.span_containing(shape, offset);
        let id = match (anchor, closure) {
            // Split the piece of outline the point falls on.
            (Some(after), _) => {
                let id = self.push_segment(shape, point, offset, Some(after));
                self.link_after(id, after);
                id
            }
            // A closed outline split into a single piece has only one place to
            // put anything.
            (None, Closure::Closed) => {
                let id = self.push_segment(shape, point, offset, Some(head));
                self.link_after(id, head);
                id
            }
            // An open outline can be extended past either end. Nothing on a
            // board reaches that far — the ends sit two board widths away — but
            // it is how the ends themselves are laid down in the first place.
            (None, Closure::Open) => {
                let head_start = self.arena.get(head).map_or(offset, Segment::start);
                if offset < head_start {
                    let tail = self.arena.get(head).map_or(head, Segment::prev);
                    let id = self.push_segment(shape, point, offset, None);
                    self.link_after(id, tail);
                    if let Some(entry) = self.shapes.get_mut(&shape) {
                        entry.head = Some(id);
                    }
                    id
                } else {
                    let tail = self.arena.get(head).map_or(head, Segment::prev);
                    let id = self.push_segment(shape, point, offset, Some(tail));
                    self.link_after(id, tail);
                    id
                }
            }
        };

        if let Some(entry) = self.shapes.get_mut(&shape) {
            entry.count += 1;
        }
        self.debug_validate();
        Some(id)
    }

    /// Removes `segment` from its shape's list, from the shared-start index,
    /// and from the arena.
    pub fn delete_segment(&mut self, segment: SegId) {
        let Some(entry) = self.arena.get(segment) else {
            return;
        };
        let (parent, point, next, prev) = (entry.parent, entry.point, entry.next, entry.prev);

        if next == segment {
            // The last one: the outline is whole again.
            if let Some(shape) = self.shapes.get_mut(&parent) {
                shape.head = None;
                shape.count = 0;
            }
        } else {
            if let Some(following) = self.arena.get_mut(next) {
                following.prev = prev;
            }
            if let Some(preceding) = self.arena.get_mut(prev) {
                preceding.next = next;
            }
            if let Some(shape) = self.shapes.get_mut(&parent) {
                // The successor holds the next-lowest offset, so an open
                // shape's head stays the lowest.
                if shape.head == Some(segment) {
                    shape.head = Some(next);
                }
                shape.count = shape.count.saturating_sub(1);
            }
        }

        self.shared_starts.remove(point, segment);
        self.arena.remove(segment);
        self.debug_validate();
    }

    /// Marks every segment from `from_inclusive` up to but not including
    /// `to_exclusive` as covered by `overlapping`.
    ///
    /// The run is walked forwards along the list, so passing the same segment
    /// as both ends marks the shape's whole outline.
    pub fn add_overlapping(
        &mut self,
        from_inclusive: SegId,
        to_exclusive: SegId,
        overlapping: ShapeId,
    ) {
        let bound = self
            .arena
            .get(from_inclusive)
            .and_then(|segment| self.shapes.get(&segment.parent))
            .map_or(0, Shape::count);

        let mut current = from_inclusive;
        let mut steps = 0;
        loop {
            debug_assert!(
                steps < bound,
                "walk from {from_inclusive:?} never reached {to_exclusive:?} — the list is malformed"
            );
            if steps >= bound {
                break;
            }
            steps += 1;

            if let Some(segment) = self.arena.get_mut(current) {
                segment.overlapping.insert(overlapping);
            }
            let Some(next) = self.arena.get(current).map(Segment::next) else {
                break;
            };
            current = next;
            if current == to_exclusive {
                break;
            }
        }
        self.debug_validate();
    }

    /// Drops every record of `overlapping` covering any part of `shape`.
    pub fn remove_overlapping(&mut self, shape: ShapeId, overlapping: ShapeId) {
        for id in self.node_ids(shape) {
            if let Some(segment) = self.arena.get_mut(id) {
                segment.overlapping.remove(&overlapping);
            }
        }
        self.debug_validate();
    }

    // ── List mechanics ───────────────────────────────────────────────────────

    /// Creates a segment linked only to itself, filed in the shared-start
    /// index, inheriting its covered-by state from `inherit`.
    ///
    /// Inheriting is what keeps a split honest: cutting a piece of outline in
    /// two produces two pieces in exactly the state the original was in.
    fn push_segment(
        &mut self,
        shape: ShapeId,
        point: Point,
        offset: f64,
        inherit: Option<SegId>,
    ) -> SegId {
        let (overlapping, force_inactive) = inherit.and_then(|id| self.arena.get(id)).map_or_else(
            || (BTreeSet::new(), false),
            |segment| (segment.overlapping.clone(), segment.force_inactive),
        );

        let id = self.arena.insert(Segment {
            parent: shape,
            start: offset,
            point,
            // Patched to point at itself as soon as the id is known.
            next: SegId::new(0),
            prev: SegId::new(0),
            overlapping,
            force_inactive,
        });
        if let Some(segment) = self.arena.get_mut(id) {
            segment.next = id;
            segment.prev = id;
        }
        self.shared_starts.add(point, id);
        id
    }

    /// Splices `new` into the list immediately after `after`.
    fn link_after(&mut self, new: SegId, after: SegId) {
        let Some(following) = self.arena.get(after).map(Segment::next) else {
            return;
        };
        if let Some(segment) = self.arena.get_mut(new) {
            segment.prev = after;
            segment.next = following;
        }
        if let Some(segment) = self.arena.get_mut(following) {
            segment.prev = new;
        }
        if let Some(segment) = self.arena.get_mut(after) {
            segment.next = new;
        }
    }

    /// The segment whose piece of outline `offset` falls on.
    fn span_containing(&self, shape: ShapeId, offset: f64) -> Option<SegId> {
        self.segments(shape).find(|id| {
            let Some(segment) = self.arena.get(*id) else {
                return false;
            };
            let Some(next) = self.arena.get(segment.next) else {
                return false;
            };
            if segment.start > next.start {
                // This piece runs past the end of the parameter and back round.
                offset >= segment.start || offset < next.start
            } else {
                offset >= segment.start && offset < next.start
            }
        })
    }

    /// Every node of `shape`'s list, including an open shape's tail.
    ///
    /// Where [`ClippingGraph::segments`] yields the pieces of outline a shape is
    /// split into, this yields the nodes of the list itself — which for an open
    /// shape is one more, the tail that closes the list without standing for
    /// any outline. Bounded by the shape's segment count, and collected rather
    /// than borrowed so that the caller can mutate as it goes.
    #[must_use]
    pub fn node_ids(&self, shape: ShapeId) -> Vec<SegId> {
        let Some(entry) = self.shapes.get(&shape) else {
            return Vec::new();
        };
        let Some(head) = entry.head else {
            return Vec::new();
        };

        let mut nodes = Vec::with_capacity(entry.count);
        let mut current = head;
        for _ in 0..entry.count {
            nodes.push(current);
            let Some(next) = self.arena.get(current).map(Segment::next) else {
                break;
            };
            current = next;
            if current == head {
                break;
            }
        }
        debug_assert!(
            current == head,
            "walk over shape {shape:?} did not return to its head within {} steps — the list is malformed",
            entry.count
        );
        nodes
    }
}

/// The segments of one shape, walked from its head.
///
/// Yields nothing for a shape whose outline has not been split, and stops
/// before an open shape's tail — that last node closes the list without
/// standing for any piece of outline.
#[derive(Clone, Debug)]
pub struct Segments<'a> {
    /// Where the segments live.
    arena: &'a SegmentArena,
    /// Where the walk started, and what it stops at.
    head: Option<SegId>,
    /// What to yield next.
    current: Option<SegId>,
    /// Whether the list wraps.
    closure: Closure,
    /// How many more segments may be yielded before the list must be declared
    /// malformed.
    budget: usize,
}

impl Iterator for Segments<'_> {
    type Item = SegId;

    fn next(&mut self) -> Option<SegId> {
        let current = self.current?;
        let segment = self.arena.get(current)?;

        // An open shape's tail spans nothing.
        if matches!(self.closure, Closure::Open) && Some(segment.next) == self.head {
            self.current = None;
            return None;
        }

        debug_assert!(
            self.budget > 0,
            "walk over a shape's segments ran past its segment count — the list is malformed"
        );
        if self.budget == 0 {
            self.current = None;
            return None;
        }
        self.budget -= 1;

        self.current = if Some(segment.next) == self.head {
            None
        } else {
            Some(segment.next)
        };
        Some(current)
    }
}

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

    use core::f64::consts::{FRAC_PI_2, PI};

    use super::{ClippingGraph, SegId, Segment, ShapeId};
    use crate::clipping::{Closure, Edge, ShapeKind};
    use crate::geometry::{Circle, LineSegment};
    use crate::{Point, STONE_DIAMETER, STONE_RADIUS};

    const BOARD: f64 = 20.0;

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

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

    /// The four boundaries, in the order they are created.
    fn boundaries(graph: &ClippingGraph) -> Vec<ShapeId> {
        graph
            .shapes()
            .filter(|(_, shape)| matches!(shape.kind(), ShapeKind::Boundary { .. }))
            .map(|(id, _)| id)
            .collect()
    }

    /// The left edge, which is the first shape a graph ever holds.
    fn left_edge(graph: &ClippingGraph) -> ShapeId {
        graph.shape_ids().next().unwrap()
    }

    fn offsets(graph: &ClippingGraph, shape: ShapeId) -> Vec<f64> {
        graph
            .node_ids(shape)
            .into_iter()
            .filter_map(|id| graph.segment(id).map(Segment::start))
            .collect()
    }

    /// Carves a dead zone the way the alive zone will: split both outlines at
    /// each crossing, then mark the covered runs.
    fn carve(graph: &mut ClippingGraph, center: Point) -> ShapeId {
        let circle = Circle::new(center, STONE_DIAMETER);
        let targets: Vec<ShapeId> = graph.shape_ids().collect();
        let dead_zone = graph.add_dead_zone(center);

        for target in targets {
            let Some(crossing) = graph.intersect(target, circle) else {
                continue;
            };
            let target_covered = graph
                .insert_or_get_existing(target, crossing.entry)
                .unwrap();
            let zone_uncovered = graph
                .insert_or_get_existing(dead_zone, crossing.entry)
                .unwrap();
            let target_uncovered = graph.insert_or_get_existing(target, crossing.exit).unwrap();
            let zone_covered = graph
                .insert_or_get_existing(dead_zone, crossing.exit)
                .unwrap();

            graph.add_overlapping(target_covered, target_uncovered, dead_zone);
            graph.add_overlapping(zone_covered, zone_uncovered, target);
        }
        dead_zone
    }

    // ── Construction ─────────────────────────────────────────────────────────

    #[test]
    fn a_new_graph_holds_the_four_board_edges() {
        let graph = ClippingGraph::new(BOARD);
        assert_eq!(graph.shape_ids().count(), 4);
        assert_eq!(graph.segment_count(), 16);
        assert!(graph.validate().is_ok());

        for id in boundaries(&graph) {
            let shape = graph.shape(id).unwrap();
            assert_eq!(shape.count(), 4);
            assert_eq!(shape.closure(), Closure::Open);
        }
    }

    #[test]
    fn an_edge_is_split_into_three_stretches_and_a_tail() {
        let graph = ClippingGraph::new(BOARD);
        for id in boundaries(&graph) {
            // Four nodes, in ascending offset order from the head.
            assert_eq!(
                offsets(&graph, id),
                vec![
                    -2.0 * BOARD,
                    STONE_RADIUS,
                    BOARD - STONE_RADIUS,
                    2.0 * BOARD
                ]
            );
            // Three of them span outline; the tail only closes the list.
            assert_eq!(graph.segments(id).count(), 3);
            // Exactly one of those is visible: the stretch the board occupies.
            let visible: Vec<f64> = graph
                .segments(id)
                .filter(|seg| graph.is_active(*seg))
                .filter_map(|seg| graph.segment(seg).map(Segment::start))
                .collect();
            assert_eq!(visible, vec![STONE_RADIUS]);
        }
    }

    #[test]
    fn the_board_corners_are_shared_starts() {
        let graph = ClippingGraph::new(BOARD);
        for corner in [p(1.0, 1.0), p(1.0, 19.0), p(19.0, 19.0), p(19.0, 1.0)] {
            assert_eq!(
                graph.segments_at(corner).len(),
                2,
                "two edges should meet at {corner:?}"
            );
            assert_eq!(graph.sole_segment_at(corner), None);
        }
    }

    #[test]
    fn the_far_ends_of_an_edge_are_shared_with_nothing() {
        let graph = ClippingGraph::new(BOARD);
        let left = ShapeKind::boundary(BOARD, Edge::Left);
        for offset in [-2.0 * BOARD, 2.0 * BOARD] {
            let point = left.offset_to_point(offset);
            assert!(graph.sole_segment_at(point).is_some());
        }
    }

    // ── Insertion ────────────────────────────────────────────────────────────

    #[test]
    fn inserting_the_same_point_twice_returns_the_same_segment() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);

        let first = graph.insert_or_get_existing(left, p(1.0, 7.5)).unwrap();
        let before = graph.segment_count();
        let second = graph.insert_or_get_existing(left, p(1.0, 7.5)).unwrap();

        assert_eq!(first, second);
        assert_eq!(graph.segment_count(), before);
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn a_point_a_single_bit_away_is_a_different_segment() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);

        let first = graph.insert_or_get_existing(left, p(1.0, 7.5)).unwrap();
        let nudged = 7.5_f64 + f64::EPSILON * 4.0;
        let second = graph.insert_or_get_existing(left, p(1.0, nudged)).unwrap();

        assert_ne!(first, second);
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn insertion_keeps_an_edge_in_offset_order() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);

        for y in [12.0, 3.0, 18.5, 7.5, 0.25] {
            graph.insert_or_get_existing(left, p(1.0, y)).unwrap();
        }

        let mut expected = vec![
            -2.0 * BOARD,
            0.25,
            1.0,
            3.0,
            7.5,
            12.0,
            18.5,
            19.0,
            2.0 * BOARD,
        ];
        expected.sort_by(f64::total_cmp);
        assert_eq!(offsets(&graph, left), expected);
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn insertion_keeps_a_dead_zone_in_offset_order_around_the_wrap() {
        let mut graph = ClippingGraph::new(BOARD);
        let zone = graph.add_dead_zone(p(10.0, 10.0));
        let kind = ShapeKind::dead_zone(p(10.0, 10.0));

        // Deliberately out of order. A closed outline has no lowest offset, so
        // the list is a rotation of the sorted order: it ascends all the way
        // round with exactly one drop, wherever the first-inserted segment
        // happens to sit.
        for angle in [3.0, 0.1, 5.9, 1.5, 4.4] {
            graph
                .insert_or_get_existing(zone, kind.offset_to_point(angle))
                .unwrap();
        }

        let walked = offsets(&graph, zone);
        assert_eq!(walked.len(), 5);
        let drops = walked
            .windows(2)
            .filter(|pair| matches!(pair, [before, after] if before > after))
            .count();
        assert_eq!(drops, 1, "walked {walked:?}");
        // The head is the first one inserted, at 3.0, and the drop is the wrap
        // past a full turn between 5.9 and 0.1.
        near(*walked.first().unwrap(), 3.0);
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn an_open_shape_can_be_extended_past_either_end() {
        // Nothing on a board reaches this far — the ends of an edge sit two
        // board widths away — but it is how those ends are laid down in the
        // first place, so the head and the tail both have to move correctly.
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);

        let below = graph
            .insert_or_get_existing(left, p(1.0, -3.0 * BOARD))
            .unwrap();
        let above = graph
            .insert_or_get_existing(left, p(1.0, 3.0 * BOARD))
            .unwrap();

        assert_eq!(graph.shape(left).unwrap().head(), Some(below));
        assert_eq!(
            offsets(&graph, left),
            vec![
                -3.0 * BOARD,
                -2.0 * BOARD,
                STONE_RADIUS,
                BOARD - STONE_RADIUS,
                2.0 * BOARD,
                3.0 * BOARD,
            ]
        );
        // The new tail closes the list and spans nothing.
        assert!(!graph.segments(left).any(|id| id == above));
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn a_new_segment_inherits_what_covered_the_piece_it_split() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);
        let other = graph.add_dead_zone(p(50.0, 50.0));

        let first = graph.insert_or_get_existing(left, p(1.0, 5.0)).unwrap();
        let second = graph.insert_or_get_existing(left, p(1.0, 9.0)).unwrap();
        graph.add_overlapping(first, second, other);
        assert!(!graph.is_active(first));

        // Splitting the covered stretch gives two covered stretches.
        let split = graph.insert_or_get_existing(left, p(1.0, 7.0)).unwrap();
        assert!(!graph.is_active(split));

        // And splitting an off-board stretch gives two off-board stretches.
        let far = graph.insert_or_get_existing(left, p(1.0, -5.0)).unwrap();
        assert!(!graph.is_active(far));
        assert!(graph.segment(far).unwrap().overlapping().next().is_none());
    }

    // ── Deletion ─────────────────────────────────────────────────────────────

    #[test]
    fn deleting_a_segment_relinks_the_list_and_clears_the_index() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);
        let id = graph.insert_or_get_existing(left, p(1.0, 7.5)).unwrap();

        graph.delete_segment(id);

        assert!(graph.segment(id).is_none());
        assert!(graph.segments_at(p(1.0, 7.5)).is_empty());
        assert_eq!(graph.shape(left).unwrap().count(), 4);
        assert_eq!(
            offsets(&graph, left),
            vec![
                -2.0 * BOARD,
                STONE_RADIUS,
                BOARD - STONE_RADIUS,
                2.0 * BOARD
            ]
        );
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn deleting_the_head_moves_it_to_the_successor() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);
        let head = graph.shape(left).unwrap().head().unwrap();

        graph.delete_segment(head);

        let new_head = graph.shape(left).unwrap().head().unwrap();
        assert_ne!(new_head, head);
        near(graph.segment(new_head).unwrap().start(), STONE_RADIUS);
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn deleting_the_last_segment_leaves_the_outline_whole() {
        let mut graph = ClippingGraph::new(BOARD);
        let zone = graph.add_dead_zone(p(10.0, 10.0));
        let only = graph.insert_or_get_existing(zone, p(12.0, 10.0)).unwrap();

        graph.delete_segment(only);

        let shape = graph.shape(zone).unwrap();
        assert_eq!(shape.head(), None);
        assert_eq!(shape.count(), 0);
        assert!(!shape.is_subdivided());
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn removing_a_shape_takes_its_segments_with_it() {
        let mut graph = ClippingGraph::new(BOARD);
        let before = graph.segment_count();
        let zone = carve(&mut graph, p(2.0, 10.0));
        assert!(graph.segment_count() > before);

        for other in graph.shape_ids().collect::<Vec<_>>() {
            graph.remove_overlapping(other, zone);
        }
        graph.remove_shape(zone);

        assert!(graph.shape(zone).is_none());
        assert!(graph.validate().is_ok());
    }

    // ── Covering ─────────────────────────────────────────────────────────────

    #[test]
    fn add_overlapping_covers_the_run_between_its_ends() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);
        let other = graph.add_dead_zone(p(50.0, 50.0));

        let from = graph.insert_or_get_existing(left, p(1.0, 5.0)).unwrap();
        let middle = graph.insert_or_get_existing(left, p(1.0, 7.0)).unwrap();
        let to = graph.insert_or_get_existing(left, p(1.0, 9.0)).unwrap();

        graph.add_overlapping(from, to, other);

        assert!(!graph.is_active(from));
        assert!(!graph.is_active(middle));
        assert!(graph.is_active(to), "the far end is not included");
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn add_overlapping_from_a_segment_to_itself_covers_everything() {
        let mut graph = ClippingGraph::new(BOARD);
        let zone = graph.add_dead_zone(p(10.0, 10.0));
        let kind = ShapeKind::dead_zone(p(10.0, 10.0));
        let other = graph.add_dead_zone(p(50.0, 50.0));

        let first = graph
            .insert_or_get_existing(zone, kind.offset_to_point(0.0))
            .unwrap();
        graph
            .insert_or_get_existing(zone, kind.offset_to_point(PI))
            .unwrap();

        graph.add_overlapping(first, first, other);

        assert!(graph.segments(zone).all(|id| !graph.is_active(id)));
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn remove_overlapping_brings_the_outline_back() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);
        let other = graph.add_dead_zone(p(50.0, 50.0));

        let from = graph.insert_or_get_existing(left, p(1.0, 5.0)).unwrap();
        let to = graph.insert_or_get_existing(left, p(1.0, 9.0)).unwrap();
        graph.add_overlapping(from, to, other);
        assert!(!graph.is_active(from));

        graph.remove_overlapping(left, other);

        assert!(graph.is_active(from));
        assert!(graph.validate().is_ok());
    }

    // ── Clipping as the alive zone will drive it ─────────────────────────────

    #[test]
    fn a_dead_zone_against_an_edge_splits_both() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);
        let zone = carve(&mut graph, p(2.0, 10.0));

        // Both outlines gained a segment at each crossing, and each crossing is
        // shared by exactly those two.
        assert_eq!(graph.shape(left).unwrap().count(), 6);
        assert_eq!(graph.shape(zone).unwrap().count(), 2);

        for id in graph.segments(zone).collect::<Vec<_>>() {
            let point = graph.segment(id).unwrap().point();
            assert_eq!(graph.segments_at(point).len(), 2);
        }

        // The stretch of edge behind the stone is covered; the dead zone's arc
        // off the board is covered too.
        assert!(graph.segments(left).any(|id| !graph.is_active(id)));
        assert!(graph.segments(zone).any(|id| !graph.is_active(id)));
        assert!(graph.segments(zone).any(|id| graph.is_active(id)));
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn two_dead_zones_clip_each_other() {
        let mut graph = ClippingGraph::new(BOARD);
        let first = carve(&mut graph, p(10.0, 10.0));
        let second = carve(&mut graph, p(12.0, 10.0));

        assert_eq!(graph.shape(first).unwrap().count(), 2);
        assert_eq!(graph.shape(second).unwrap().count(), 2);
        // Each has one arc inside the other and one outside.
        for zone in [first, second] {
            assert_eq!(
                graph
                    .segments(zone)
                    .filter(|id| graph.is_active(*id))
                    .count(),
                1
            );
        }
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn a_dead_zone_in_open_space_stays_whole() {
        let mut graph = ClippingGraph::new(BOARD);
        let zone = carve(&mut graph, p(10.0, 10.0));

        let shape = graph.shape(zone).unwrap();
        assert_eq!(shape.count(), 0);
        assert!(!shape.is_subdivided());
        // An unsplit outline is still an outline: the whole circle counts.
        let closest = graph.shape_closest_point(zone, p(10.0, 0.0)).unwrap();
        near(closest.x, 10.0);
        near(closest.y, 10.0 - STONE_DIAMETER);
        near(
            graph.shape_closest_distance(zone, LineSegment::new(p(0.0, 0.0), p(0.0, 20.0))),
            10.0 - STONE_DIAMETER,
        );
    }

    #[test]
    fn a_covered_stretch_is_not_measured() {
        let mut graph = ClippingGraph::new(BOARD);
        let zone = graph.add_dead_zone(p(10.0, 10.0));
        let kind = ShapeKind::dead_zone(p(10.0, 10.0));
        let other = graph.add_dead_zone(p(50.0, 50.0));

        // Split the circle in half at 0 and π, then cover the lower half.
        let east = graph
            .insert_or_get_existing(zone, kind.offset_to_point(0.0))
            .unwrap();
        let west = graph
            .insert_or_get_existing(zone, kind.offset_to_point(PI))
            .unwrap();
        graph.add_overlapping(east, west, other);

        // The nearest point below the centre is now on the surviving half.
        let closest = graph
            .shape_closest_point(zone, p(10.0, 10.0 + STONE_DIAMETER * 2.0))
            .unwrap();
        assert!(closest.y <= 10.0 + 1e-9, "got {closest:?}");
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn a_shape_with_nothing_visible_is_infinitely_far_away() {
        let mut graph = ClippingGraph::new(BOARD);
        let zone = graph.add_dead_zone(p(10.0, 10.0));
        let kind = ShapeKind::dead_zone(p(10.0, 10.0));
        let other = graph.add_dead_zone(p(50.0, 50.0));

        let east = graph
            .insert_or_get_existing(zone, kind.offset_to_point(0.0))
            .unwrap();
        graph
            .insert_or_get_existing(zone, kind.offset_to_point(PI))
            .unwrap();
        graph.add_overlapping(east, east, other);

        assert_eq!(graph.shape_closest_point(zone, p(0.0, 0.0)), None);
        assert!(
            graph
                .shape_closest_distance(zone, LineSegment::new(p(0.0, 0.0), p(1.0, 1.0)))
                .is_infinite()
        );
    }

    #[test]
    fn a_span_runs_from_a_segment_to_its_successor() {
        let mut graph = ClippingGraph::new(BOARD);
        let zone = graph.add_dead_zone(p(0.0, 0.0));
        let kind = ShapeKind::dead_zone(p(0.0, 0.0));

        let east = graph
            .insert_or_get_existing(zone, kind.offset_to_point(0.0))
            .unwrap();
        graph
            .insert_or_get_existing(zone, kind.offset_to_point(FRAC_PI_2))
            .unwrap();

        let span = graph.segment_span(east).unwrap();
        near(span.start_point().x, STONE_DIAMETER);
        near(span.start_point().y, 0.0);
        near(span.end_point().x, 0.0);
        near(span.end_point().y, STONE_DIAMETER);
    }

    // ── Reclaim, and 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 first reclaim rather than duplicating
        // them.
        //
        // Both crossings a dead zone can have are in play here: the reclaimed
        // one overlaps its neighbour and runs off the left edge of the board.
        let mut graph = ClippingGraph::new(BOARD);
        let neighbour = carve(&mut graph, p(2.0, 10.0));
        let baseline = structure(&graph);

        let zone = carve(&mut graph, p(2.0, 13.0));
        let carved = structure(&graph);
        assert_eq!(graph.shape(zone).unwrap().count(), 4);

        // Reclaim it, the way the alive zone will.
        for other in graph.shape_ids().collect::<Vec<_>>() {
            graph.remove_overlapping(other, zone);
        }
        for id in graph.node_ids(zone) {
            let point = graph.segment(id).unwrap().point();
            graph.delete_segment(id);
            if let Some(orphan) = graph.sole_segment_at(point) {
                graph.delete_segment(orphan);
            }
        }
        graph.remove_shape(zone);
        assert_eq!(structure(&graph), baseline);
        assert!(graph.validate().is_ok());

        // And carve it again.
        let again = carve(&mut graph, p(2.0, 13.0));
        assert_eq!(structure(&graph), carved);
        assert!(graph.validate().is_ok());
        assert!(graph.shape(neighbour).is_some());
        assert!(graph.shape(again).is_some());
    }

    /// Every shape's outline, as the exact bits of its segment offsets together
    /// with what is visible. Shape ids are deliberately excluded: a reclaimed
    /// dead zone that is carved again gets a fresh id.
    fn structure(graph: &ClippingGraph) -> Vec<(Vec<u64>, Vec<bool>)> {
        graph
            .shape_ids()
            .map(|shape| {
                let ids = graph.node_ids(shape);
                (
                    ids.iter()
                        .filter_map(|id| graph.segment(*id).map(|s| s.start().to_bits()))
                        .collect(),
                    ids.iter().map(|id| graph.is_active(*id)).collect(),
                )
            })
            .collect()
    }

    // ── The walk bound ───────────────────────────────────────────────────────

    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "ran past its segment count")]
    fn a_list_that_never_comes_back_trips_the_walk_bound() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);
        let head = graph.shape(left).unwrap().head().unwrap();
        let second = graph.segment(head).unwrap().next();

        // Point the second segment at itself. A walk from the head now spins
        // there for ever instead of coming back round — which is exactly the
        // failure the bound exists to turn into a test failure.
        if let Some(segment) = graph.arena.get_mut(second) {
            segment.next = second;
        }

        let _ = graph.segments(left).count();
    }

    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "the list is malformed")]
    fn covering_a_run_that_never_reaches_its_end_trips_the_bound() {
        let mut graph = ClippingGraph::new(BOARD);
        let left = left_edge(&graph);
        let other = graph.add_dead_zone(p(50.0, 50.0));
        let head = graph.shape(left).unwrap().head().unwrap();

        // A terminator that is not in this shape's list at all.
        let stranger = graph.insert_or_get_existing(other, p(52.0, 50.0)).unwrap();
        graph.add_overlapping(head, stranger, other);
    }

    #[test]
    fn a_walk_over_a_missing_shape_yields_nothing() {
        let mut graph = ClippingGraph::new(BOARD);
        assert_eq!(graph.segments(ShapeId::new(99)).count(), 0);
        assert!(graph.node_ids(ShapeId::new(99)).is_empty());
        assert!(graph.segment(SegId::new(999)).is_none());
        assert!(graph.shape(ShapeId::new(99)).is_none());
        assert!(
            graph
                .insert_or_get_existing(ShapeId::new(99), p(1.0, 1.0))
                .is_none()
        );
        assert!(graph.remove_shape(ShapeId::new(99)).is_none());
        // Deleting something that is not there changes nothing.
        graph.delete_segment(SegId::new(999));
        assert!(graph.validate().is_ok());
    }
}