voronoi-go 1.0.1

//! The outline of the playable area, as SVG path data.
//!
//! This is the **third** consumer of the shared-start index, and the one the
//! other two do not explain. The visible boundary of the playable area is not a
//! property of any single shape: it runs along a dead zone's rim until that rim
//! disappears under a neighbour, and there it continues along the neighbour's
//! rim instead. The two shapes' segments meet at exactly one point, and the
//! index is what says so — `docs/design.md` § "The shared-start index" is the
//! long form.
//!
//! So the walk is not a walk over one shape's circular list. It starts at some
//! active segment, follows that shape's list to the end of the segment's span,
//! then asks the index which segments start at the point it has arrived at and
//! steps onto whichever of them continues the boundary. A loop closes when the
//! point it arrives at is one the starting segment also starts at.
//!
//! # Termination
//!
//! Every step either closes the loop or moves onto a segment that has not been
//! visited, so the walk cannot revisit anything and must stop. That is an
//! argument about a well-formed structure, and a malformed one is exactly what
//! the rails exist for: the per-shape scan is bounded by the shape's segment
//! count by [`ClippingGraph::segments`](crate::clipping::ClippingGraph::segments),
//! and the cross-shape walk carries its own bound of the total live segment
//! count. A boundary that never closes fails an assertion rather than hanging.

use std::collections::BTreeSet;

use crate::clipping::{SegId, Segment};
use crate::svg::path_command;

use super::AliveZone;

// On the impl rather than the module: `doc(cfg)` propagates down a module tree
// but not sideways onto a type declared elsewhere, so the gate on `mod svg`
// alone leaves this method looking unconditional on docs.rs.
#[cfg_attr(docsrs, doc(cfg(feature = "svg")))]
impl AliveZone {
    /// The visible boundary of the playable area, as a single SVG `<path>`
    /// element, or an empty string when nothing is left of it.
    ///
    /// Every loop of the boundary becomes one closed subpath: a `M` to where it
    /// starts, an `A` per stretch of a dead zone's rim, an `L` per stretch of a
    /// board edge, and a `Z`. Coordinates are rounded on the way into the
    /// string and nowhere else.
    ///
    /// This is a read. It carves nothing, restores nothing, and leaves the zone
    /// bit for bit as it found it.
    #[must_use]
    pub fn to_svg(&self) -> String {
        // Every segment the walk has drawn or dismissed. Membership only —
        // nothing is ever ordered by a `SegId`, which is an arena slot and is
        // handed out again after a deletion.
        let mut visited: BTreeSet<SegId> = BTreeSet::new();
        let mut commands: Vec<String> = Vec::new();

        // The cross-shape walk steps onto a segment it has not visited every
        // time, so it cannot take more steps than there are segments. Anything
        // more means the structure is malformed.
        let bound = self.graph.segment_count();

        for shape in self.graph.shape_ids() {
            for seed in self.graph.segments(shape) {
                if visited.contains(&seed) {
                    continue;
                }
                if !self.graph.is_active(seed) {
                    visited.insert(seed);
                    continue;
                }

                // The segment following the seed on the seed's *own* shape.
                // Stepping onto it would retrace the loop the wrong way round,
                // so it is never a candidate for continuing.
                let seed_successor = self.graph.segment(seed).map(Segment::next);

                let mut current = Some(seed);
                let mut needs_move = true;
                let mut steps = 0_usize;

                while let Some(id) = current {
                    debug_assert!(
                        steps < bound,
                        "the outline walk from {seed:?} never closed within {bound} segments — the structure is malformed"
                    );
                    if steps >= bound {
                        break;
                    }
                    steps += 1;

                    if let Some(span) = self.graph.segment_span(id) {
                        commands.push(path_command(span, needs_move));
                    }
                    needs_move = false;
                    visited.insert(id);

                    // Where this segment's span ends is where its successor on
                    // the same shape begins, and that point is what the index
                    // is keyed on.
                    let Some(arrival) = self
                        .graph
                        .segment(id)
                        .map(Segment::next)
                        .and_then(|next| self.graph.segment(next))
                        .map(Segment::point)
                    else {
                        break;
                    };

                    let sharing = self.graph.segments_at(arrival);
                    if sharing.contains(&seed) {
                        commands.push("Z".to_owned());
                        break;
                    }

                    current = sharing.iter().copied().find(|candidate| {
                        self.graph.is_active(*candidate)
                            && !visited.contains(candidate)
                            && Some(*candidate) != seed_successor
                    });
                }
            }
        }

        if commands.is_empty() {
            return String::new();
        }
        format!("<path d=\"{}\" />", commands.join(" "))
    }
}

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

    use crate::{AliveZone, Point, STONE_DIAMETER, StoneId};

    const BOARD: f64 = 20.0;

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

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

    /// The `d` attribute of the path the zone draws.
    fn path_data(zone: &AliveZone) -> String {
        let svg = zone.to_svg();
        let start = svg.find("d=\"").expect("a path with data") + 3;
        let rest = svg.get(start..).expect("the data starts inside the string");
        let end = rest.find('"').expect("the data is quoted");
        rest.get(..end)
            .expect("the data ends inside the string")
            .to_owned()
    }

    /// Every drawing command in the path, `M` and `Z` included.
    fn commands(zone: &AliveZone) -> Vec<String> {
        let data = path_data(zone);
        let mut commands: Vec<String> = Vec::new();
        for token in data.split_whitespace() {
            if token
                .chars()
                .next()
                .is_some_and(|first| first.is_ascii_alphabetic())
            {
                commands.push(token.to_owned());
            } else if let Some(last) = commands.last_mut() {
                last.push(' ');
                last.push_str(token);
            }
        }
        commands
    }

    /// The commands that draw geometry, sorted — the part of the path that does
    /// not depend on where a loop was entered.
    fn drawn(zone: &AliveZone) -> Vec<String> {
        let mut drawn: Vec<String> = commands(zone)
            .into_iter()
            .filter(|command| command.starts_with('A') || command.starts_with('L'))
            .collect();
        drawn.sort();
        drawn
    }

    /// Every point the path moves or draws to, read back out of the string.
    fn drawn_points(zone: &AliveZone) -> Vec<Point> {
        commands(zone)
            .iter()
            .filter_map(|command| {
                let pair = command.rsplit(' ').next()?;
                let (x, y) = pair.split_once(',')?;
                Some(Point::new(x.parse().ok()?, y.parse().ok()?))
            })
            .collect()
    }

    #[test]
    fn every_point_drawn_is_on_the_boundary_of_the_playable_area() {
        // The independent check on the whole walk: a point the outline passes
        // through lies *on* the playable area's boundary, so it is placeable.
        // Anything drawn through covered ground — a segment the walk should
        // have skipped, an arc taken the long way round — puts a point well
        // inside a dead zone and fails this.
        //
        // Eight decimals of truncation is five parts in `10^9`, two orders
        // below the slack `is_placeable` allows.
        let zone = carve_all(&[
            p(2.0, 10.0),
            p(3.5, 11.0),
            p(6.0, 6.0),
            p(8.5, 7.0),
            p(7.0, 9.0),
            p(10.0, 10.0),
            p(11.0, 11.5),
        ]);

        let points = drawn_points(&zone);
        assert!(points.len() > 10, "not much of a test: {}", points.len());
        for point in points {
            assert!(
                zone.is_placeable(point),
                "({}, {}) is drawn but is not on the boundary",
                point.x,
                point.y
            );
        }
    }

    #[test]
    fn an_empty_board_draws_its_inset_square() {
        let zone = AliveZone::new(BOARD);
        assert_eq!(
            path_data(&zone),
            "M 1.00000000,1.00000000 L 1.00000000,19.00000000 \
             L 19.00000000,19.00000000 L 19.00000000,1.00000000 L 1.00000000,1.00000000 Z"
        );
    }

    #[test]
    fn a_dead_zone_in_open_space_draws_its_whole_rim() {
        let zone = carve_all(&[p(10.0, 10.0)]);
        let commands = commands(&zone);

        // The board's square, then the untouched circle as a lone full turn.
        // A whole circle cannot be one arc — SVG has no way to say "all the way
        // round" — so the rim is not drawn at all until something splits it.
        assert_eq!(commands.iter().filter(|c| c.starts_with('L')).count(), 4);
        assert_eq!(commands.iter().filter(|c| *c == "Z").count(), 1);
    }

    #[test]
    fn a_dead_zone_against_an_edge_hands_the_outline_over_and_back() {
        // The stone's rim reaches the left edge, so the boundary leaves the
        // edge, runs round the rim and comes back — which it can only do by
        // stepping between two different shapes at their shared points.
        let zone = carve_all(&[p(2.0, 10.0)]);
        let commands = commands(&zone);

        assert!(
            commands.iter().any(|c| c.starts_with('A')),
            "the rim is part of the boundary: {commands:?}"
        );
        assert!(commands.iter().any(|c| c.starts_with('L')));
        assert_eq!(
            commands.iter().filter(|c| *c == "Z").count(),
            1,
            "one loop, still: {commands:?}"
        );
        assert!(commands.first().is_some_and(|c| c.starts_with('M')));
    }

    #[test]
    fn a_string_of_dead_zones_still_closes_every_loop() {
        let centers: Vec<Point> = (0..6).map(|i| p(4.0 + f64::from(i) * 1.5, 10.0)).collect();
        let zone = carve_all(&centers);
        let commands = commands(&zone);

        let moves = commands.iter().filter(|c| c.starts_with('M')).count();
        let closes = commands.iter().filter(|c| *c == "Z").count();
        assert!(moves > 0);
        assert_eq!(moves, closes, "every subpath closes: {commands:?}");
    }

    #[test]
    fn an_enclosed_dead_zone_leaves_no_arc_behind() {
        // A ring of six around a seventh: the middle rim is covered on every
        // side, so nothing of it is drawn.
        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(&centers);
        // The middle stone's hole in the board is gone, so the eye it would
        // have left is not part of the boundary either.
        assert!(!zone.contains(p(10.0, 10.0)));
        assert!(!path_data(&zone).is_empty());
    }

    #[test]
    fn a_zone_with_nothing_visible_draws_nothing() {
        // Every shape's outline covered by another leaves no boundary at all.
        // A 4-unit board is entirely inside one stone's dead zone.
        let mut zone = AliveZone::new(4.0);
        zone.remove_circle(StoneId::new(0), p(2.0, 2.0)).unwrap();
        assert_eq!(zone.to_svg(), "");
    }

    #[test]
    fn the_path_is_the_same_however_the_zone_was_reached() {
        // Two zones carved in the same order from the same centres draw the
        // same path, byte for byte. This is what a snapshot rests on.
        let centers = [p(6.0, 6.0), p(8.5, 7.0), p(7.0, 9.0), p(2.0, 10.0)];
        assert_eq!(
            path_data(&carve_all(&centers)),
            path_data(&carve_all(&centers))
        );
    }

    #[test]
    fn a_round_trip_redraws_the_same_geometry_possibly_rotated() {
        // `docs/design.md` § "Undo is bit-exact": a reclaim can leave a shape's
        // segment list rotated, because the head is whichever segment was
        // inserted first and deleting it moves the head on. The offsets and
        // what is visible come back identical, so the *geometry* drawn is
        // identical — but which segment of a loop carries the `M`, and the
        // order the loops come out in, are not part of that guarantee.
        let centers = [p(6.0, 6.0), p(8.5, 7.0), p(7.0, 9.0), p(2.0, 10.0)];
        let mut zone = carve_all(&centers);
        let before = drawn(&zone);

        zone.reclaim_circle(StoneId::new(1)).unwrap();
        zone.remove_circle(StoneId::new(1), centers[1]).unwrap();

        assert_eq!(zone.validate(), Ok(()));
        assert_eq!(drawn(&zone), before);
    }

    #[test]
    fn drawing_the_outline_changes_nothing() {
        let zone = carve_all(&[p(6.0, 6.0), p(8.5, 7.0), p(2.0, 10.0)]);
        let before = zone.fingerprint();
        let _ = zone.to_svg();
        assert_eq!(zone.fingerprint(), before);
        assert_eq!(zone.validate(), Ok(()));
    }
}