voronoi-go 1.0.1

//! The set of forced eyes: positions kept playable by fiat.
//!
//! When a stone is captured, its exact position becomes placeable again even
//! though it sits inside the dead zones of the stones that surrounded it. In a
//! tight position the gap that the capture opens is frequently too small to
//! survive the clipping arithmetic, and the point that a player would obviously
//! be allowed to play back into reads as covered. A forced eye is the standing
//! exception that keeps it playable, until a new stone's dead zone consumes it.
//!
//! Identity here is the same as everywhere else: [`PointKey`], the exact bit
//! patterns of the coordinates. Two eyes a single bit apart are two eyes.
//! Iteration is by key, so it is total, stable and reproducible — the set never
//! leaks insertion order into anything observable.

use std::collections::BTreeMap;

use crate::{Point, PointKey};

/// Positions that count as playable regardless of what covers them.
#[derive(Clone, Debug, Default)]
pub(super) struct ForcedEyes {
    /// A `BTreeMap` rather than a hash map: nothing observable may depend on
    /// iteration order, and `PointKey` orders by bit pattern, which is total and
    /// stable.
    pub(super) by_point: BTreeMap<PointKey, Point>,
}

impl ForcedEyes {
    /// An empty set.
    pub(super) const fn new() -> Self {
        Self {
            by_point: BTreeMap::new(),
        }
    }

    /// Adds `point`. Adding a point already in the set does nothing.
    pub(super) fn insert(&mut self, point: Point) {
        self.by_point.insert(point.key(), point);
    }

    /// Removes the eye at exactly `point`, and answers the eye that was there.
    ///
    /// The stored point is returned rather than the one asked for: they are the
    /// same point by [`PointKey`], and the stored one is the answer to *which
    /// eye went*.
    pub(super) fn take(&mut self, point: Point) -> Option<Point> {
        self.by_point.remove(&point.key())
    }

    /// Whether there is an eye at exactly `point`.
    pub(super) fn contains(&self, point: Point) -> bool {
        self.by_point.contains_key(&point.key())
    }

    /// Every eye, in key order.
    pub(super) fn iter(&self) -> impl Iterator<Item = Point> + '_ {
        self.by_point.values().copied()
    }

    /// Every eye with the key it is filed under, for validation.
    pub(super) fn entries(&self) -> impl Iterator<Item = (PointKey, Point)> + '_ {
        self.by_point.iter().map(|(key, point)| (*key, *point))
    }

    /// How many eyes there are.
    pub(super) fn len(&self) -> usize {
        self.by_point.len()
    }
}

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

    use super::ForcedEyes;
    use crate::Point;

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

    #[test]
    fn an_eye_is_found_only_at_its_exact_point() {
        let mut eyes = ForcedEyes::new();
        eyes.insert(p(10.0, 10.0));

        assert!(eyes.contains(p(10.0, 10.0)));
        let one_bit_up = f64::from_bits(10.0_f64.to_bits() + 1);
        assert!(!eyes.contains(p(10.0, one_bit_up)));
    }

    #[test]
    fn the_two_zeroes_are_one_eye() {
        let mut eyes = ForcedEyes::new();
        eyes.insert(p(-0.0, 0.0));
        assert!(eyes.contains(p(0.0, -0.0)));
        assert_eq!(eyes.len(), 1);
    }

    #[test]
    fn inserting_the_same_eye_twice_keeps_one() {
        let mut eyes = ForcedEyes::new();
        eyes.insert(p(4.0, 4.0));
        eyes.insert(p(4.0, 4.0));
        assert_eq!(eyes.len(), 1);
    }

    #[test]
    fn taking_answers_the_stored_point_and_empties_the_slot() {
        let mut eyes = ForcedEyes::new();
        eyes.insert(p(4.0, 4.0));

        assert_eq!(eyes.take(p(4.0, 4.0)), Some(p(4.0, 4.0)));
        assert_eq!(eyes.take(p(4.0, 4.0)), None);
        assert_eq!(eyes.len(), 0);
    }

    #[test]
    fn iteration_is_by_key_not_by_insertion() {
        let mut eyes = ForcedEyes::new();
        for point in [p(9.0, 1.0), p(1.0, 9.0), p(5.0, 5.0)] {
            eyes.insert(point);
        }

        let walked: Vec<Point> = eyes.iter().collect();
        let mut sorted = walked.clone();
        sorted.sort_by_key(|point| point.key());
        assert_eq!(walked, sorted);
    }
}