voronoi-go 1.0.1

//! The behaviours the cut computation is judged by.
//!
//! Every case here is a position with a known answer: a pair tight enough that
//! nothing fits between it, one loose enough that something does, a stone that
//! reaches the wall, a stone the wall has been taken away from. The fixture gate
//! lives in `tests/cuts.rs`.

#![allow(clippy::unwrap_used, clippy::expect_used, clippy::indexing_slicing)]

use super::{
    BoardEdge, Connectivity, CutError, CutKind, MAX_BOUNDARY_CUT_DISTANCE, MAX_PAIR_CUT_DISTANCE,
    SAFE_BOUNDARY_DISTANCE, SAFE_PAIR_DISTANCE,
};
use crate::{AliveZone, Color, Point, STONE_DIAMETER, STONE_RADIUS, Stone, StoneId};

const BOARD: f64 = 40.0;

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

fn black(id: u32, x: f64, y: f64) -> Stone {
    Stone::new(StoneId::new(id), Color::Black, p(x, y))
}

fn white(id: u32, x: f64, y: f64) -> Stone {
    Stone::new(StoneId::new(id), Color::White, p(x, y))
}

/// The alive zone a board of these stones has, carved exactly as a game carves
/// it.
fn zone_of(board: f64, stones: &[Stone]) -> AliveZone {
    let mut zone = AliveZone::new(board);
    for stone in stones {
        zone.remove_circle(stone.id, stone.position).unwrap();
    }
    assert_eq!(zone.validate(), Ok(()));
    zone
}

/// The kind of the line between `a` and `b` on a board of exactly these stones,
/// asked of a manager with nothing cached.
fn kind_on(board: f64, stones: &[Stone], a: &Stone, b: &Stone) -> CutKind {
    let mut zone = zone_of(board, stones);
    let answer = Connectivity::new(board)
        .pair_cuttable(&mut zone, stones, *a, *b)
        .expect("two different stones of one colour");
    assert_eq!(zone.validate(), Ok(()), "the zone survived the measurement");
    answer
}

fn kind(stones: &[Stone], a: &Stone, b: &Stone) -> CutKind {
    kind_on(BOARD, stones, a, b)
}

/// Whether `a` and `b` are a proven connection.
fn connected(stones: &[Stone], a: &Stone, b: &Stone) -> bool {
    kind(stones, a, b) == CutKind::Connected
}

/// Whether any board edge holds `stone` — that is, answers `Connected`.
fn any_edge_holds(board: f64, stones: &[Stone], stone: &Stone) -> bool {
    let mut zone = zone_of(board, stones);
    let mut connectivity = Connectivity::new(board);
    let held = BoardEdge::ALL.into_iter().any(|edge| {
        connectivity.boundary_cuttable(&mut zone, stones, *stone, edge) == CutKind::Connected
    });
    assert_eq!(zone.validate(), Ok(()), "the zone survived the measurement");
    held
}

// ── What holds a pair together ───────────────────────────────────────────────

#[test]
fn only_an_uncuttable_same_color_pair_is_connected() {
    // Two blacks 2.5 apart (tight, uncuttable); a third black far away; a white
    // close to the first but the wrong colour.
    let stones = [
        black(0, 20.0, 20.0),
        black(1, 20.0, 22.5),
        black(2, 32.0, 32.0),
        white(3, 23.5, 20.0),
    ];
    let mut zone = zone_of(BOARD, &stones);
    let mut connectivity = Connectivity::new(BOARD);
    let mut ask = |other: Stone| connectivity.pair_cuttable(&mut zone, &stones, stones[0], other);

    assert_eq!(ask(stones[1]), Ok(CutKind::Connected), "the tight pair");
    assert_eq!(ask(stones[2]), Ok(CutKind::TooFar), "twelve units away");
    assert_eq!(
        ask(stones[3]),
        Err(CutError::DifferentColors {
            a: stones[0].id,
            b: stones[3].id
        })
    );
    assert_eq!(
        ask(stones[0]),
        Err(CutError::SameStone {
            stone: stones[0].id
        })
    );
}

#[test]
fn a_tight_pair_holds_and_a_looser_one_does_not() {
    // For an isolated axis-aligned pair the two ideal enemy placements land on
    // the dead zone's waist, `2·√(4 − (d/2)²)` apart, and the pair is cuttable
    // exactly when that is at most `d` — from `d = 2√2 ≈ 2.83` up.
    let tight = [black(0, 20.0, 20.0), black(1, 20.0, 22.5)];
    let loose = [black(0, 20.0, 20.0), black(1, 20.0, 23.0)];

    assert_eq!(kind(&tight, &tight[0], &tight[1]), CutKind::Connected);
    assert_eq!(kind(&loose, &loose[0], &loose[1]), CutKind::Cuttable);
}

#[test]
fn a_pair_further_apart_than_the_limit_is_not_judged_at_all() {
    // A hair either side of the limit, on a board holding nothing else. Below
    // it the geometry runs and says cuttable; above it nothing runs.
    let under = MAX_PAIR_CUT_DISTANCE - 0.01;
    let over = MAX_PAIR_CUT_DISTANCE + 0.01;
    let pair = |separation: f64| {
        [
            black(0, 20.0 - separation / 2.0, 20.0),
            black(1, 20.0 + separation / 2.0, 20.0),
        ]
    };

    let close = pair(under);
    assert_eq!(kind(&close, &close[0], &close[1]), CutKind::Cuttable);

    let far = pair(over);
    assert_eq!(kind(&far, &far[0], &far[1]), CutKind::TooFar);
}

#[test]
fn a_stone_over_the_line_is_judged_like_any_other_position() {
    // Occlusion is a drawing concern and is not one of the answers: a stone
    // sitting on the line does not stop the two cells meeting, and the pair is
    // still measured. Here the occluder is a white between two tight blacks, and
    // it is too close to either to leave a cutting partner room.
    let a = black(0, 20.0, 20.0);
    let b = black(1, 20.0, 22.5);
    assert_eq!(kind(&[a, b], &a, &b), CutKind::Connected);

    let occluder = white(2, 20.0, 21.25);
    assert_eq!(kind(&[a, b, occluder], &a, &b), CutKind::Connected);
}

#[test]
fn a_pair_that_reaches_the_wall_stays_connected() {
    // Two whites against the right wall with a black inside them: their cells
    // meet on the board between the black and the wall, so the wall clips their
    // region without cutting it.
    let one = white(1, 17.0, 10.318_3);
    let other = white(2, 17.0, 7.754_4);
    let stones = [black(0, 15.464_9, 9.036_3), one, other];

    assert_eq!(kind_on(18.0, &stones, &one, &other), CutKind::Connected);
}

#[test]
fn two_pairs_that_cross_each_other_are_both_connected() {
    // Both pairs are inside the safe pair distance, and crossing is not a fact
    // about the position: whether one line would be drawn over another is a
    // caller's problem and has no business reaching an answer here.
    let b0 = black(0, 18.8, 20.0);
    let b1 = black(1, 21.2, 20.0);
    let w0 = white(2, 20.0, 18.8);
    let w1 = white(3, 20.0, 21.2);
    let stones = [b0, b1, w0, w1];

    assert!(connected(&stones, &b0, &b1));
    assert!(connected(&stones, &w0, &w1));
}

#[test]
fn a_dense_friendly_shape_is_connected_all_the_way_through() {
    // The interior of a solid friendly shape is exactly what a renderer hides,
    // and it is exactly what is most certainly connected. Every pair of a
    // two-by-two square, diagonals included, answers connected.
    let square = [
        black(0, 19.0, 19.0),
        black(1, 21.0, 19.0),
        black(2, 19.0, 21.0),
        black(3, 21.0, 21.0),
    ];
    let mut zone = zone_of(BOARD, &square);
    let mut connectivity = Connectivity::new(BOARD);

    for (index, a) in square.iter().enumerate() {
        for b in square.iter().skip(index + 1) {
            assert_eq!(
                connectivity.pair_cuttable(&mut zone, &square, *a, *b),
                Ok(CutKind::Connected),
                "{a:?} to {b:?}"
            );
        }
    }
    assert_eq!(zone.validate(), Ok(()));
}

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

#[test]
fn measuring_leaves_the_alive_zone_exactly_as_it_was() {
    // A pair loose enough that the geometry really runs, so temporary circles
    // really are carved.
    let stones = [black(0, 20.0, 20.0), black(1, 20.0, 23.0)];
    let mut zone = zone_of(BOARD, &stones);
    let before = zone.fingerprint();

    let _ = Connectivity::new(BOARD).pair_cuttable(&mut zone, &stones, stones[0], stones[1]);

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

// ── The cache ────────────────────────────────────────────────────────────────

#[test]
fn a_cached_status_is_reused_until_it_is_invalidated() {
    let mut connectivity = Connectivity::new(BOARD);
    // The same two ids at two spacings with known-different answers: 3.0 apart
    // is cuttable, 2.5 apart is not.
    let loose = [black(0, 20.0, 20.0), black(1, 20.0, 23.0)];
    let tight = [black(0, 20.0, 20.0), black(1, 20.0, 22.5)];
    let mut loose_zone = zone_of(BOARD, &loose);
    let mut tight_zone = zone_of(BOARD, &tight);

    assert_eq!(
        connectivity.pair_cuttable(&mut loose_zone, &loose, loose[0], loose[1]),
        Ok(CutKind::Cuttable)
    );

    // Same ids, so the cached answer is reused even though this spacing would
    // decide the other way.
    assert_eq!(
        connectivity.pair_cuttable(&mut tight_zone, &tight, tight[0], tight[1]),
        Ok(CutKind::Cuttable)
    );

    connectivity.invalidate_near(p(20.0, 21.0));
    assert_eq!(connectivity.cached_count(), 0);
    assert_eq!(
        connectivity.pair_cuttable(&mut tight_zone, &tight, tight[0], tight[1]),
        Ok(CutKind::Connected)
    );
}

#[test]
fn either_order_finds_the_same_cached_status() {
    let stones = [black(0, 20.0, 20.0), black(1, 20.0, 22.5)];
    let mut zone = zone_of(BOARD, &stones);
    let mut connectivity = Connectivity::new(BOARD);

    let first = connectivity.pair_cuttable(&mut zone, &stones, stones[0], stones[1]);
    assert_eq!(first, Ok(CutKind::Connected));
    assert_eq!(connectivity.cached_count(), 1);
    assert_eq!(
        connectivity.pair_cuttable(&mut zone, &stones, stones[1], stones[0]),
        first
    );
    assert_eq!(connectivity.cached_count(), 1, "one status, not two");
}

#[test]
fn invalidation_spares_a_status_out_of_range() {
    let mut connectivity = Connectivity::new(BOARD);
    let stones = [black(0, 20.0, 20.0), black(1, 20.0, 22.5)];
    let mut zone = zone_of(BOARD, &stones);

    assert_eq!(
        connectivity.pair_cuttable(&mut zone, &stones, stones[0], stones[1]),
        Ok(CutKind::Connected)
    );
    let cached = connectivity.cached_count();
    assert!(cached > 0);

    connectivity.invalidate_near(p(35.0, 35.0));
    assert_eq!(connectivity.cached_count(), cached);
}

#[test]
fn a_question_that_is_never_measured_is_never_cached() {
    // Nothing is computed for it, so there is nothing to file — and nothing to
    // go stale when the board moves under it.
    let a = black(0, 20.0, 20.0);
    let enemy = white(1, 20.0, 22.5);
    let distant = black(2, 20.0, 20.0 + MAX_PAIR_CUT_DISTANCE + 0.1);
    let far_from_every_wall = black(3, 20.0, 20.0);
    let stones = [a, enemy, distant, far_from_every_wall];
    let mut zone = zone_of(BOARD, &stones);
    let mut connectivity = Connectivity::new(BOARD);

    assert!(
        connectivity
            .pair_cuttable(&mut zone, &stones, a, enemy)
            .is_err()
    );
    assert_eq!(
        connectivity.pair_cuttable(&mut zone, &stones, a, distant),
        Ok(CutKind::TooFar)
    );
    assert!(
        connectivity
            .pair_cuttable(&mut zone, &stones, a, a)
            .is_err()
    );
    assert_eq!(
        connectivity.boundary_cuttable(&mut zone, &stones, far_from_every_wall, BoardEdge::Left),
        CutKind::TooFar
    );

    assert_eq!(connectivity.cached_count(), 0);
    assert_eq!(zone.validate(), Ok(()), "the zone survived the questions");
}

// ── Stone and edge ───────────────────────────────────────────────────────────

#[test]
fn a_corner_stone_holds_on_to_both_its_walls() {
    // One unit from each edge, so it stays connected to both — and the two far
    // ones are past the limit and never judged.
    let stone = black(0, 1.0, 1.0);
    let stones = [stone];
    let mut zone = zone_of(20.0, &stones);
    let mut connectivity = Connectivity::new(20.0);
    let mut ask = |edge| connectivity.boundary_cuttable(&mut zone, &stones, stone, edge);

    assert_eq!(ask(BoardEdge::Left), CutKind::Connected);
    assert_eq!(ask(BoardEdge::Top), CutKind::Connected);
    assert_eq!(ask(BoardEdge::Right), CutKind::TooFar);
    assert_eq!(ask(BoardEdge::Bottom), CutKind::TooFar);
}

#[test]
fn an_edge_is_cut_off_when_an_enemy_contests_the_foot() {
    // The white sits nearer the foot than the black does, taking one of the two
    // straddling cutting spots. The enemy only needs the other one, so the black
    // is cuttable either way.
    let stone = black(0, 15.842_6, 7.263_9);
    let foot_kind = |stones: &[Stone]| {
        let mut zone = zone_of(18.0, stones);
        let answer =
            Connectivity::new(18.0).boundary_cuttable(&mut zone, stones, stone, BoardEdge::Right);
        assert_eq!(zone.validate(), Ok(()));
        answer
    };

    assert_eq!(foot_kind(&[stone]), CutKind::Cuttable);
    assert_eq!(
        foot_kind(&[stone, white(1, 17.0, 5.632_8)]),
        CutKind::Cuttable
    );
}

#[test]
fn an_edge_is_cut_off_while_an_enemy_pair_straddles_the_foot() {
    // Two whites straddle the black's foot in the gap toward the wall, so the
    // black's cell no longer reaches it.
    let stone = black(0, 15.762_7, 8.992_7);
    let stones = [stone, white(1, 17.2, 7.0), white(2, 17.2, 11.1)];

    assert!(!any_edge_holds(18.0, &stones, &stone));
}

// ── The distances ────────────────────────────────────────────────────────────

#[test]
fn the_thresholds_are_the_numbers_they_are() {
    // Pinned because they are decisions, and because the two safe distances are
    // unrelated to each other: deriving one from the other is the mistake this
    // guards against.
    assert_eq!(
        SAFE_PAIR_DISTANCE.to_bits(),
        (core::f64::consts::SQRT_2 * STONE_DIAMETER).to_bits()
    );
    assert_eq!(
        SAFE_BOUNDARY_DISTANCE.to_bits(),
        (2.0 * STONE_RADIUS).to_bits()
    );

    // The two cut limits are derived rather than experimental, and the spelled
    // out `√3` has to be the one the standard library would compute.
    let root_three = 3.0_f64.sqrt();
    assert_eq!(
        MAX_PAIR_CUT_DISTANCE.to_bits(),
        (2.0 * root_three).to_bits()
    );
    assert_eq!(
        MAX_BOUNDARY_CUT_DISTANCE.to_bits(),
        (1.0 + root_three).to_bits()
    );

    // And a cutting stone really does just touch the line at the pair limit: it
    // stands a diameter from both ends, a radius off the line.
    let half = MAX_PAIR_CUT_DISTANCE / 2.0;
    let clearance = (STONE_DIAMETER * STONE_DIAMETER - half * half).sqrt();
    assert!((clearance - STONE_RADIUS).abs() < 1e-12, "{clearance}");
}

#[test]
fn every_pair_inside_the_safe_pair_distance_is_connected() {
    let mut cut: Vec<String> = Vec::new();

    let mut separation = 2.05;
    while separation < SAFE_PAIR_DISTANCE {
        let a = black(0, 20.0 - separation / 2.0, 20.0);
        let b = black(1, 20.0 + separation / 2.0, 20.0);
        if !connected(&[a, b], &a, &b) {
            cut.push(format!("{separation:.3}"));
        }
        separation += 0.02;
    }

    assert!(cut.is_empty(), "not connected at {cut:?}");
}

#[test]
fn a_pair_well_past_the_safe_distance_is_cuttable() {
    let separation = 3.4;
    let a = black(0, 20.0 - separation / 2.0, 20.0);
    let b = black(1, 20.0 + separation / 2.0, 20.0);

    assert_eq!(kind(&[a, b], &a, &b), CutKind::Cuttable);
}

#[test]
fn every_stone_inside_the_safe_boundary_distance_reaches_its_edge() {
    // The stone-edge bound is its own number solving its own problem, so it gets
    // its own sweep.
    let mut cut: Vec<String> = Vec::new();

    let mut distance = 0.2;
    while distance < SAFE_BOUNDARY_DISTANCE {
        let stone = black(0, 20.0, distance);
        if !any_edge_holds(BOARD, &[stone], &stone) {
            cut.push(format!("{distance:.3}"));
        }
        distance += 0.02;
    }

    assert!(cut.is_empty(), "cut off at {cut:?}");
}

#[test]
fn a_stone_between_the_boundary_bound_and_the_limit_is_still_evaluated() {
    // Between the safe boundary distance and the point the rules give up, the
    // geometry decides; what is asserted here is that it decides, without
    // panicking or leaving the zone behind it damaged.
    let mut distance = SAFE_BOUNDARY_DISTANCE;
    while distance <= MAX_BOUNDARY_CUT_DISTANCE {
        let stone = black(0, 20.0, distance);
        let stones = [stone];
        let mut zone = zone_of(BOARD, &stones);
        let judged =
            Connectivity::new(BOARD).boundary_cuttable(&mut zone, &stones, stone, BoardEdge::Top);
        assert_ne!(judged, CutKind::TooFar, "at {distance}");
        assert_eq!(zone.validate(), Ok(()));
        distance += 0.1;
    }
}

#[test]
fn the_fast_path_stays_optimistic_about_a_forced_eye_between_a_pair() {
    // A forced eye makes a captured stone's exact position placeable again,
    // inside its neighbours' dead zones — the one case where an enemy really
    // could stand closer than the short circuit assumes. It is taken anyway, on
    // purpose: paying full geometry on every close pair to cover it costs more
    // than it is worth.
    let separation = SAFE_PAIR_DISTANCE - 0.1;
    let a = black(0, 20.0 - separation / 2.0, 20.0);
    let b = black(1, 20.0 + separation / 2.0, 20.0);
    let stones = [a, b];

    let mut zone = zone_of(BOARD, &stones);
    zone.add_forced_eye(p(20.0, 20.0));

    assert_eq!(
        Connectivity::new(BOARD).pair_cuttable(&mut zone, &stones, a, b),
        Ok(CutKind::Connected)
    );
}