voronoi-go 1.0.1

//! Segments, and the arena they live in.

use std::collections::BTreeSet;

use crate::Point;

use super::ShapeId;

/// Identifies one segment of a shape's clipped outline.
///
/// It appears in the public API only as the subject of a
/// [`ZoneError`](crate::ZoneError): the structure it indexes into is internal.
///
/// Ids are slot indices and are **reused** once a segment is deleted, so an id
/// is only meaningful while the segment it names is alive. Nothing observable
/// may be ordered by it — see `docs/design.md` on reproducibility.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct SegId(u32);

impl SegId {
    /// The id addressing arena slot `index`.
    pub(super) const fn new(index: usize) -> Self {
        Self(index as u32)
    }

    /// The arena slot this id addresses.
    pub(super) const fn index(self) -> usize {
        self.0 as usize
    }

    /// The raw slot number, for diagnostics.
    #[must_use]
    pub const fn get(self) -> u32 {
        self.0
    }
}

/// One piece of a shape's outline: the stretch from this segment's own start
/// point round to its successor's.
///
/// A segment exists only to mark a crossing. It is created when two shapes
/// intersect, it survives while inactive so that the crossing can be un-clipped
/// later, and it is deleted once nothing else starts at its point.
#[derive(Clone, Debug)]
pub struct Segment {
    /// The shape whose outline this segment lies on.
    pub(super) parent: ShapeId,
    /// Where the segment starts, in the parent's offset parameter.
    pub(super) start: f64,
    /// Where the segment starts, in board coordinates. This is the value the
    /// shared-start index is keyed on, and it is never recomputed from
    /// [`Segment::start`].
    pub(super) point: Point,
    /// The next segment round the parent's list.
    pub(super) next: SegId,
    /// The previous segment round the parent's list.
    pub(super) prev: SegId,
    /// The shapes covering this segment. Empty means nothing covers it.
    pub(super) overlapping: BTreeSet<ShapeId>,
    /// Set on the pieces of a board edge that run off the board, which clip but
    /// are never part of the visible outline.
    pub(super) force_inactive: bool,
}

impl Segment {
    /// The shape this segment lies on.
    ///
    /// Only the tests ask: every caller that has a segment id got it from a
    /// walk that already knows the shape.
    #[cfg(test)]
    #[must_use]
    pub const fn parent(&self) -> ShapeId {
        self.parent
    }

    /// Where this segment starts, in its shape's offset parameter.
    #[must_use]
    pub const fn start(&self) -> f64 {
        self.start
    }

    /// Where this segment starts, in board coordinates.
    #[must_use]
    pub const fn point(&self) -> Point {
        self.point
    }

    /// The next segment round the parent's list.
    #[must_use]
    pub const fn next(&self) -> SegId {
        self.next
    }

    /// The previous segment round the parent's list.
    #[must_use]
    pub const fn prev(&self) -> SegId {
        self.prev
    }

    /// The shapes currently covering this segment.
    ///
    /// Only the tests ask; everything else wants [`Segment::is_active`], which
    /// is the question this set exists to answer.
    #[cfg(test)]
    pub fn overlapping(&self) -> impl Iterator<Item = ShapeId> + '_ {
        self.overlapping.iter().copied()
    }

    /// Whether this segment is part of the visible outline: nothing covers it,
    /// and it is not one of a board edge's off-board extensions.
    #[must_use]
    pub fn is_active(&self) -> bool {
        self.overlapping.is_empty() && !self.force_inactive
    }
}

/// The segments of every shape in one graph, addressed by [`SegId`].
///
/// Deleted slots go on a free list and are handed out again, so the arena stays
/// the size of the live structure rather than the size of everything that has
/// ever been in it.
#[derive(Clone, Debug, Default)]
pub(super) struct SegmentArena {
    /// Slots, live or vacant.
    slots: Vec<Option<Segment>>,
    /// Vacant slot ids, most recently freed first.
    free: Vec<SegId>,
    /// How many slots are live.
    live: usize,
}

impl SegmentArena {
    /// An arena with nothing in it.
    pub(super) const fn new() -> Self {
        Self {
            slots: Vec::new(),
            free: Vec::new(),
            live: 0,
        }
    }

    /// How many segments are alive.
    pub(super) const fn len(&self) -> usize {
        self.live
    }

    /// The segment `id` names, if it is alive.
    pub(super) fn get(&self, id: SegId) -> Option<&Segment> {
        self.slots.get(id.index())?.as_ref()
    }

    /// The segment `id` names, for modification, if it is alive.
    pub(super) fn get_mut(&mut self, id: SegId) -> Option<&mut Segment> {
        self.slots.get_mut(id.index())?.as_mut()
    }

    /// Puts `segment` in a free slot, or in a fresh one, and returns its id.
    pub(super) fn insert(&mut self, segment: Segment) -> SegId {
        let id = self.free.pop().unwrap_or_else(|| {
            let fresh = SegId::new(self.slots.len());
            self.slots.push(None);
            fresh
        });

        if let Some(slot) = self.slots.get_mut(id.index()) {
            debug_assert!(slot.is_none(), "arena handed out a slot that was live");
            *slot = Some(segment);
            self.live += 1;
        }

        id
    }

    /// Frees the slot `id` names and returns what was in it.
    pub(super) fn remove(&mut self, id: SegId) -> Option<Segment> {
        let taken = self.slots.get_mut(id.index())?.take();
        if taken.is_some() {
            self.live -= 1;
            self.free.push(id);
        }
        taken
    }

    /// Every live segment, with its id. The order is slot order, which is not
    /// reproducible across deletions — use it only where the order cannot
    /// escape.
    pub(super) fn iter(&self) -> impl Iterator<Item = (SegId, &Segment)> {
        self.slots
            .iter()
            .enumerate()
            .filter_map(|(index, slot)| slot.as_ref().map(|seg| (SegId::new(index), seg)))
    }
}

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

    use std::collections::BTreeSet;

    use super::{SegId, Segment, SegmentArena};
    use crate::Point;
    use crate::clipping::ShapeId;

    fn segment() -> Segment {
        Segment {
            parent: ShapeId::new(0),
            start: 0.0,
            point: Point::new(1.0, 2.0),
            next: SegId::new(0),
            prev: SegId::new(0),
            overlapping: BTreeSet::new(),
            force_inactive: false,
        }
    }

    #[test]
    fn a_freed_slot_is_handed_out_again() {
        let mut arena = SegmentArena::new();
        let first = arena.insert(segment());
        let second = arena.insert(segment());
        assert_eq!(arena.len(), 2);

        arena.remove(first);
        assert_eq!(arena.len(), 1);
        assert!(arena.get(first).is_none());

        let third = arena.insert(segment());
        assert_eq!(third, first, "the freed slot should be reused");
        assert_eq!(arena.len(), 2);
        assert!(arena.get(second).is_some());
    }

    #[test]
    fn removing_twice_is_harmless() {
        let mut arena = SegmentArena::new();
        let id = arena.insert(segment());
        assert!(arena.remove(id).is_some());
        assert!(arena.remove(id).is_none());
        assert_eq!(arena.len(), 0);
    }

    #[test]
    fn iteration_yields_only_live_segments() {
        let mut arena = SegmentArena::new();
        let a = arena.insert(segment());
        let b = arena.insert(segment());
        let c = arena.insert(segment());
        arena.remove(b);

        let live: Vec<SegId> = arena.iter().map(|(id, _)| id).collect();
        assert_eq!(live, vec![a, c]);
    }

    #[test]
    fn a_segment_is_active_only_when_nothing_covers_it() {
        let mut seg = segment();
        assert!(seg.is_active());

        seg.overlapping.insert(ShapeId::new(7));
        assert!(!seg.is_active());

        seg.overlapping.clear();
        seg.force_inactive = true;
        assert!(!seg.is_active());
    }
}