voronoi-go 1.0.1

//! Cutting: which same-colour pairs an enemy cannot wedge itself between.
//!
//! Two same-colour stones are **connected** when no enemy pair can be placed so
//! as to separate their cells. [`Connectivity::pair_cuttable`] answers that
//! about two stones, and [`Connectivity::boundary_cuttable`] about a stone and a
//! board edge — a stone near a wall is measured against its perpendicular foot
//! on it.
//!
//! # Three answers and an error
//!
//! The verdict is a [`CutKind`]: [`Connected`](CutKind::Connected),
//! [`Cuttable`](CutKind::Cuttable), or [`TooFar`](CutKind::TooFar) for a pair
//! the geometry declines to judge. **`TooFar` is not a verdict**, and neither
//! direction may be read into it: past [`MAX_PAIR_CUT_DISTANCE`] an enemy fits
//! between the two ends and the two-placement search could report a connection
//! that is not there, so the answer is withheld rather than guessed. Both limits
//! are public so a caller can see which questions are answerable before asking.
//!
//! A question that is not about a connection at all is a [`CutError`] rather
//! than a kind: a stone with itself, and two stones of opposite colours. Those
//! are malformed rather than unanswerable, and rolling them into the verdict is
//! what would let a caller act on one by mistake.
//!
//! # The cache
//!
//! A pair's cut status can only change when a stone appears or disappears near
//! it, so [`Connectivity::invalidate_near`] drops the statuses whose midpoint is
//! close to a changed stone. [`Game`](crate::Game) calls it from both
//! `apply_delta` and `pop_delta`, and **not** gated on whether the turn
//! advanced: a transient change must not leave a status behind that outlives it.
//!
//! The invalidation radius is deliberately generous — wider than the region a
//! status theoretically depends on — because in a dense cluster the ideal
//! cutting positions can sit on a third stone's dead zone and shift when it
//! moves. Over-invalidating costs a recompute; a stale answer is wrong.
//!
//! A `TooFar` answer is never cached: it is a distance test, cheaper than the
//! lookup would be, and it cannot go stale.

mod cut;

use std::collections::BTreeMap;

use thiserror::Error;

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

use cut::{Pair, evaluate_pair_cut};

pub use cut::{
    CutKind, MAX_BOUNDARY_CUT_DISTANCE, MAX_PAIR_CUT_DISTANCE, SAFE_BOUNDARY_DISTANCE,
    SAFE_DISTANCE_EPSILON, SAFE_PAIR_DISTANCE,
};

/// A cut question that is not a question about a connection.
///
/// None of these is a verdict, and none of them is [`CutKind::TooFar`] either:
/// the rules relate two *different* stones of *one* colour, and anything else is
/// a caller asking about something the rules have no opinion on.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Error)]
pub enum CutError {
    /// The stone named is not on the board.
    #[error("no stone {stone} is on the board")]
    NoSuchStone {
        /// The id that names nothing.
        stone: StoneId,
    },

    /// A stone was asked about against itself.
    #[error("stone {stone} cannot be cut from itself")]
    SameStone {
        /// The stone named twice.
        stone: StoneId,
    },

    /// The two stones are not the same colour, so there is no connection between
    /// them to cut in the first place.
    #[error("stones {a} and {b} are not the same colour")]
    DifferentColors {
        /// One stone.
        a: StoneId,
        /// The other.
        b: StoneId,
    },
}

/// How near a changed stone a cached status has to be to be dropped.
///
/// Three times the dead zone against the "within twice of both endpoints" the
/// status really depends on. See the module documentation for why the slack is
/// there.
const CUT_CACHE_INVALIDATE_RADIUS: f64 = 2.01 * crate::STONE_DIAMETER;

/// Which board edge a stone-to-edge line runs to.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(rename_all = "lowercase"))]
pub enum BoardEdge {
    /// `x = 0`.
    Left,
    /// `x = board_size`.
    Right,
    /// `y = 0`.
    Top,
    /// `y = board_size`.
    Bottom,
}

impl BoardEdge {
    /// Every edge, in a fixed order.
    pub const ALL: [Self; 4] = [Self::Left, Self::Right, Self::Top, Self::Bottom];

    /// The perpendicular foot of `position` on this edge.
    #[must_use]
    pub fn foot(self, position: Point, board_size: f64) -> Point {
        match self {
            Self::Left => Point::new(0.0, position.y),
            Self::Right => Point::new(board_size, position.y),
            Self::Top => Point::new(position.x, 0.0),
            Self::Bottom => Point::new(position.x, board_size),
        }
    }
}

/// What a cached cut status is filed under.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum CutKey {
    /// An unordered pair of stones, normalized so either order finds it.
    Pair {
        /// The lower id.
        low: StoneId,
        /// The higher id.
        high: StoneId,
    },

    /// A stone and one of the board's edges.
    Edge {
        /// The stone.
        stone: StoneId,
        /// The edge.
        edge: BoardEdge,
    },
}

impl CutKey {
    /// The key for the line between two stones, whichever way round they came.
    fn pair(one: StoneId, other: StoneId) -> Self {
        Self::Pair {
            low: one.min(other),
            high: one.max(other),
        }
    }
}

/// A cut status, and the ends its midpoint is derived from.
#[derive(Clone, Copy, Debug)]
struct CutStatus {
    /// One end of the line.
    start: Point,
    /// The other end.
    end: Point,
    /// What the geometry said.
    kind: CutKind,
}

impl CutStatus {
    /// The midpoint the invalidation radius is measured from.
    // The same arithmetic the cut geometry uses — see `Pair::midpoint`.
    #[allow(clippy::manual_midpoint)]
    fn midpoint(self) -> Point {
        Point::new(
            (self.start.x + self.end.x) / 2.0,
            (self.start.y + self.end.y) / 2.0,
        )
    }
}

/// One candidate line, with everything needed to work out its kind.
#[derive(Clone, Copy, Debug)]
struct Candidate {
    /// Where the line starts.
    start: Point,
    /// Where it ends — the other stone's centre, or the foot on an edge. Not the
    /// mirror point: that is `pair.b`, and it is twice as far away.
    end: Point,
    /// Where this line's status lives in the cache.
    key: CutKey,
    /// The pair the geometry actually measures.
    pair: Pair,
}

/// Connectivity for one board: the per-pair cut-status cache, and the two
/// queries that read it.
///
/// [`Game`](crate::Game) owns one and drives it. A caller measuring a board it
/// holds itself — a hypothetical position, say — can own one directly.
#[derive(Clone, Debug)]
pub struct Connectivity {
    /// Width and height of the board.
    board_size: f64,
    /// Lazily populated, and keyed on ids rather than positions so that nothing
    /// observable depends on iteration order.
    cache: BTreeMap<CutKey, CutStatus>,
}

impl Connectivity {
    /// Connectivity over a `board_size` board, with nothing cached yet.
    #[must_use]
    pub const fn new(board_size: f64) -> Self {
        Self {
            board_size,
            cache: BTreeMap::new(),
        }
    }

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

    /// How many cut statuses are cached.
    ///
    /// Nothing about the result depends on this — it is here so that a caller
    /// driving the invalidation itself can see that a change landed.
    #[must_use]
    pub fn cached_count(&self) -> usize {
        self.cache.len()
    }

    /// Drops every cached status whose midpoint is near `position`.
    ///
    /// Called for each stone whose presence on the board changed. See the module
    /// documentation for why the radius is wider than it strictly needs to be.
    pub fn invalidate_near(&mut self, position: Point) {
        self.cache
            .retain(|_, status| position.distance(status.midpoint()) > CUT_CACHE_INVALIDATE_RADIUS);
    }

    /// Whether an enemy pair can be wedged between two stones.
    ///
    /// [`CutKind::TooFar`] for a pair further apart than
    /// [`MAX_PAIR_CUT_DISTANCE`], which is not a verdict — see the module
    /// documentation. A stone with itself, or two stones of opposite colours, is
    /// a [`CutError`] rather than a kind.
    ///
    /// `zone` is left exactly as it was found, to the bit.
    ///
    /// # Errors
    ///
    /// [`CutError::SameStone`] when `a` and `b` are the same stone, and
    /// [`CutError::DifferentColors`] when they are not the same colour.
    pub fn pair_cuttable(
        &mut self,
        zone: &mut AliveZone,
        stones: &[Stone],
        a: Stone,
        b: Stone,
    ) -> Result<CutKind, CutError> {
        if a.id == b.id {
            return Err(CutError::SameStone { stone: a.id });
        }
        if a.color != b.color {
            return Err(CutError::DifferentColors { a: a.id, b: b.id });
        }
        if a.position.distance(b.position) > MAX_PAIR_CUT_DISTANCE {
            return Ok(CutKind::TooFar);
        }

        Ok(self.cut_kind(zone, stones, &pair_candidate(a, b)))
    }

    /// The same question about a stone and a board edge.
    ///
    /// [`CutKind::TooFar`] for a stone further from the edge than
    /// [`MAX_BOUNDARY_CUT_DISTANCE`]. There is nothing here that can be
    /// malformed, so unlike [`Connectivity::pair_cuttable`] this always answers.
    pub fn boundary_cuttable(
        &mut self,
        zone: &mut AliveZone,
        stones: &[Stone],
        stone: Stone,
        edge: BoardEdge,
    ) -> CutKind {
        let candidate = self.edge_candidate(stone, edge);
        if stone.position.distance(candidate.end) > MAX_BOUNDARY_CUT_DISTANCE {
            return CutKind::TooFar;
        }

        self.cut_kind(zone, stones, &candidate)
    }

    /// The candidate line from a stone to one of the board's edges.
    ///
    /// Built here rather than at each caller because the mirror point and the
    /// cache key have to agree exactly between the two questions — one that
    /// built either differently would file its answer where nothing would ever
    /// find it again.
    fn edge_candidate(&self, stone: Stone, edge: BoardEdge) -> Candidate {
        let foot = edge.foot(stone.position, self.board_size);
        // Mirroring the stone across the edge makes the foot the midpoint of a
        // virtual pair, so the pair machinery answers this too — there is no
        // separate boundary path.
        let mirror = Point::new(
            2.0 * foot.x - stone.position.x,
            2.0 * foot.y - stone.position.y,
        );

        Candidate {
            start: stone.position,
            end: foot,
            key: CutKey::Edge {
                stone: stone.id,
                edge,
            },
            pair: Pair {
                a: stone,
                b: mirror,
                b_id: None,
            },
        }
    }

    /// One candidate's kind, through the cache.
    fn cut_kind(
        &mut self,
        zone: &mut AliveZone,
        stones: &[Stone],
        candidate: &Candidate,
    ) -> CutKind {
        if let Some(status) = self.cache.get(&candidate.key) {
            return status.kind;
        }

        let kind = evaluate_pair_cut(zone, self.board_size, stones, candidate.pair);
        self.cache.insert(
            candidate.key,
            CutStatus {
                start: candidate.start,
                end: candidate.end,
                kind,
            },
        );

        kind
    }
}

/// The candidate line between two stones the rules relate.
fn pair_candidate(a: Stone, b: Stone) -> Candidate {
    Candidate {
        start: a.position,
        end: b.position,
        key: CutKey::pair(a.id, b.id),
        pair: Pair {
            a,
            b: b.position,
            b_id: Some(b.id),
        },
    }
}

#[cfg(test)]
mod tests;