voronoi-go 1.0.1

//! Points, and the exact key that gives them identity.

use core::hash::{Hash, Hasher};

/// The bit pattern of positive zero.
const POS_ZERO_BITS: u64 = 0.0_f64.to_bits();
/// The bit pattern of negative zero.
const NEG_ZERO_BITS: u64 = (-0.0_f64).to_bits();

/// A position on the board, in units where a stone has radius
/// [`STONE_RADIUS`](crate::STONE_RADIUS).
///
/// Equality is **exact**: it compares [`PointKey`]s, so two points are the same
/// point only when their coordinates are bit-identical (with `-0.0` and `0.0`
/// treated alike). There is no tolerance in it, deliberately — see
/// `docs/design.md`.
#[derive(Clone, Copy, Debug, Default)]
pub struct Point {
    /// Horizontal coordinate, increasing rightwards.
    pub x: f64,
    /// Vertical coordinate, increasing downwards.
    pub y: f64,
}

impl Point {
    /// A point at `(x, y)`.
    #[must_use]
    pub const fn new(x: f64, y: f64) -> Self {
        Self { x, y }
    }

    /// This point's identity key.
    #[must_use]
    pub const fn key(self) -> PointKey {
        PointKey::new(self.x, self.y)
    }

    /// Whether both coordinates are finite numbers.
    ///
    /// A point that is not finite is not a position, and the rules say so
    /// explicitly rather than letting a comparison decide: every ordering
    /// against a `NaN` is false, so "not outside the board" and "inside the
    /// board" are different statements about it, and a predicate phrased as the
    /// first quietly admits it. See `docs/design.md` § "A position is a point on
    /// the board".
    #[must_use]
    pub fn is_finite(self) -> bool {
        self.x.is_finite() && self.y.is_finite()
    }

    /// Squared distance to `other`.
    #[must_use]
    pub fn distance_squared(self, other: Self) -> f64 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        dx * dx + dy * dy
    }

    /// Euclidean distance to `other`.
    #[must_use]
    pub fn distance(self, other: Self) -> f64 {
        self.distance_squared(other).sqrt()
    }
}

impl PartialEq for Point {
    fn eq(&self, other: &Self) -> bool {
        self.key() == other.key()
    }
}

impl Eq for Point {}

impl Hash for Point {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.key().hash(state);
    }
}

/// The identity of a [`Point`]: the exact bit patterns of its coordinates.
///
/// This is the only way points are compared for identity anywhere in the crate.
/// `-0.0` is normalized to `0.0` first, so the two zeroes are one point; every
/// other value keys on itself and nothing else. Ordering is by bit pattern —
/// meaningless geometrically, but total and stable, which is what a `BTreeMap`
/// needs to keep iteration reproducible.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct PointKey {
    /// Bits of the x coordinate.
    x: u64,
    /// Bits of the y coordinate.
    y: u64,
}

impl PointKey {
    /// The key for the coordinate pair `(x, y)`.
    #[must_use]
    pub const fn new(x: f64, y: f64) -> Self {
        Self {
            x: normalize_bits(x),
            y: normalize_bits(y),
        }
    }

    /// The raw `(x, y)` bit patterns.
    #[must_use]
    pub const fn bits(self) -> (u64, u64) {
        (self.x, self.y)
    }
}

impl From<Point> for PointKey {
    fn from(point: Point) -> Self {
        point.key()
    }
}

/// `f64::to_bits`, with negative zero folded onto positive zero so that the two
/// zeroes are the same point.
const fn normalize_bits(value: f64) -> u64 {
    let bits = value.to_bits();
    if bits == NEG_ZERO_BITS {
        POS_ZERO_BITS
    } else {
        bits
    }
}

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

    use super::{Point, PointKey};
    use std::collections::HashMap;

    #[test]
    fn zeroes_are_one_point() {
        assert_eq!(Point::new(-0.0, -0.0), Point::new(0.0, 0.0));
        assert_eq!(PointKey::new(-0.0, 1.0), PointKey::new(0.0, 1.0));
        assert_eq!(PointKey::new(0.0, -0.0).bits(), (0, 0));
    }

    #[test]
    fn identity_has_no_tolerance() {
        let a = Point::new(1.0, 1.0);
        let b = Point::new(1.0 + f64::EPSILON, 1.0);
        assert_ne!(a, b);
        assert_ne!(a.key(), b.key());
    }

    #[test]
    fn key_survives_a_hash_map_round_trip() {
        let mut map = HashMap::new();
        map.insert(Point::new(3.5, -0.0).key(), "here");
        assert_eq!(map.get(&Point::new(3.5, 0.0).key()), Some(&"here"));
        assert_eq!(map.get(&Point::new(3.5, 1e-300).key()), None);
    }

    #[test]
    fn nan_is_not_equal_to_itself_bitwise_but_keys_alike() {
        // NaN is never produced by the engine's geometry; this only pins that
        // the key is a pure bit comparison and does not special-case it.
        let nan = Point::new(f64::NAN, 0.0);
        assert_eq!(nan.key(), nan.key());
    }

    #[test]
    fn distance_is_euclidean() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(3.0, 4.0);
        assert!((a.distance(b) - 5.0).abs() < 1e-15);
        assert!((a.distance_squared(b) - 25.0).abs() < 1e-15);
    }
}