voronoi-go 1.0.1

//! The index of segments by the point they start at.
//!
//! Two shapes that cross create one segment each, and both start at the very
//! same point. This index maps that point to those segments, and it answers
//! three questions that nothing else can:
//!
//! 1. **Does this shape already own a segment starting here?** Asked on every
//!    insertion, so that carving the same dead zone twice finds the segments
//!    that survived the first reclaim instead of duplicating them.
//! 2. **When a segment dies, is exactly one left sharing its start?** If so
//!    that survivor has nothing left to mark, and goes too.
//! 3. **Where does the outline continue?** Walking off the end of one shape's
//!    segment, the next piece belongs to whichever shape shares that point.
//!
//! `docs/design.md` § "The shared-start index" spells out why this cannot be
//! replaced by an identifier stamped on both segments when they are created.
//!
//! The key is [`PointKey`] — the exact bit patterns of the coordinates. Not a
//! quantized hash: two crossings that land on the same point are the same point
//! only when they are bit-for-bit identical, which is what makes carving,
//! reclaiming and re-carving a dead zone reproduce the identical structure.

use std::collections::BTreeMap;

use crate::{Point, PointKey};

use super::SegId;

/// Segments grouped by the point they start at.
#[derive(Clone, Debug, Default)]
pub(super) struct SharedStarts {
    /// 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.
    by_point: BTreeMap<PointKey, Vec<SegId>>,
}

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

    /// The segments starting at `point`, in the order they were added.
    pub(super) fn segments(&self, point: Point) -> &[SegId] {
        self.by_point
            .get(&point.key())
            .map_or(&[], |segments| segments.as_slice())
    }

    /// The one segment starting at `point`, if exactly one does.
    pub(super) fn sole_segment(&self, point: Point) -> Option<SegId> {
        match self.segments(point) {
            [only] => Some(*only),
            _ => None,
        }
    }

    /// Records that `segment` starts at `point`. Adding the same segment twice
    /// does nothing.
    pub(super) fn add(&mut self, point: Point, segment: SegId) {
        let segments = self.by_point.entry(point.key()).or_default();
        if !segments.contains(&segment) {
            segments.push(segment);
        }
    }

    /// Forgets that `segment` starts at `point`.
    pub(super) fn remove(&mut self, point: Point, segment: SegId) {
        let key = point.key();
        let Some(segments) = self.by_point.get_mut(&key) else {
            return;
        };
        segments.retain(|id| *id != segment);
        if segments.is_empty() {
            self.by_point.remove(&key);
        }
    }

    /// Every point in the index, with the segments starting there.
    pub(super) fn iter(&self) -> impl Iterator<Item = (PointKey, &[SegId])> {
        self.by_point
            .iter()
            .map(|(key, segments)| (*key, segments.as_slice()))
    }

    /// How many segments are indexed.
    pub(super) fn len(&self) -> usize {
        self.by_point.values().map(Vec::len).sum()
    }
}

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

    use super::SharedStarts;
    use crate::Point;
    use crate::clipping::SegId;

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

    #[test]
    fn segments_group_by_exact_point() {
        let mut index = SharedStarts::new();
        index.add(p(1.0, 2.0), SegId::new(0));
        index.add(p(1.0, 2.0), SegId::new(1));
        index.add(p(1.0, 2.000_000_1), SegId::new(2));

        assert_eq!(index.segments(p(1.0, 2.0)), [SegId::new(0), SegId::new(1)]);
        assert_eq!(index.segments(p(1.0, 2.000_000_1)), [SegId::new(2)]);
        assert_eq!(index.len(), 3);
    }

    #[test]
    fn there_is_no_tolerance_in_the_key() {
        // A point a single bit away is a different point, deliberately.
        let mut index = SharedStarts::new();
        index.add(p(1.0, 2.0), SegId::new(0));
        let one_bit_up = f64::from_bits(2.0_f64.to_bits() + 1);
        assert!(index.segments(p(1.0, one_bit_up)).is_empty());
    }

    #[test]
    fn the_two_zeroes_are_one_point() {
        let mut index = SharedStarts::new();
        index.add(p(-0.0, 0.0), SegId::new(0));
        assert_eq!(index.segments(p(0.0, -0.0)), [SegId::new(0)]);
    }

    #[test]
    fn adding_the_same_segment_twice_is_idempotent() {
        let mut index = SharedStarts::new();
        index.add(p(1.0, 2.0), SegId::new(0));
        index.add(p(1.0, 2.0), SegId::new(0));
        assert_eq!(index.segments(p(1.0, 2.0)), [SegId::new(0)]);
    }

    #[test]
    fn the_sole_segment_is_reported_only_when_it_is_alone() {
        let mut index = SharedStarts::new();
        assert_eq!(index.sole_segment(p(1.0, 2.0)), None);

        index.add(p(1.0, 2.0), SegId::new(0));
        assert_eq!(index.sole_segment(p(1.0, 2.0)), Some(SegId::new(0)));

        index.add(p(1.0, 2.0), SegId::new(1));
        assert_eq!(index.sole_segment(p(1.0, 2.0)), None);

        index.remove(p(1.0, 2.0), SegId::new(1));
        assert_eq!(index.sole_segment(p(1.0, 2.0)), Some(SegId::new(0)));
    }

    #[test]
    fn an_emptied_point_leaves_no_entry_behind() {
        let mut index = SharedStarts::new();
        index.add(p(1.0, 2.0), SegId::new(0));
        index.remove(p(1.0, 2.0), SegId::new(0));
        assert_eq!(index.iter().count(), 0);
        assert_eq!(index.len(), 0);
    }
}