tilezz 0.1.4

//! Abstract representation of points and polygonal segment chains.

use std::collections::HashSet;
use std::fmt::{Debug, Display};

use num_complex::Complex;
use num_traits::ToPrimitive;

use super::angles::normalize_angle;
use super::grid::UnitSquareGrid;
use crate::cyclotomic::geometry::intersect_unit_segments;
use crate::cyclotomic::{IsRing, Units};

/// Best-effort dedup for `seg_id` against a `u128` bitmap.
///
/// Returns `true` if the caller should process this `seg_id` (and the
/// bit was just set), `false` if the segment was already marked.
///
/// When `seg_id >= 128` the bitmap can't represent it; we fall through
/// to always returning `true` (no dedup for very long snakes). That's
/// safe because the only consequence is running `intersect` a second
/// time on a duplicate -- correct, just slightly wasteful. So there's
/// no hard cap on snake length; the bitmap is purely an optimization
/// for the common short-snake case.
#[inline]
fn check_and_mark(seen: &mut u128, seg_id: usize) -> bool {
    if seg_id >= 128 {
        return true;
    }
    let bit = 1u128 << seg_id;
    if *seen & bit != 0 {
        false
    } else {
        *seen |= bit;
        true
    }
}

/// Representation of a turtle (i.e. an oriented point).
pub struct Turtle<T: IsRing> {
    /// Position in the complex integer plane.
    pub pos: T,

    /// Facing direction (interpreted modulo full turn).
    pub dir: i8,
}

impl<T: IsRing> Turtle<T> {
    /// Create a new turtle with given location and orientation.
    pub fn new(pos: T, dir: i8) -> Self {
        Self { pos, dir }
    }
}

impl<T: IsRing> Default for Turtle<T> {
    /// Return a canonical turtle, i.e. located at the origin
    /// and looking in the direction of the positive real axis.
    fn default() -> Self {
        Turtle {
            pos: T::zero(),
            dir: 0,
        }
    }
}

/// Blueprint of a polyline or polygon that consists of
/// unit-length segments in a chosen complex integer ring.
///
/// It can be seen as (a subset of) the free monoid of angle sequences,
/// that is interpreted as an action on a point in the plane
/// and can be quotiented by equal total dislocation.
/// If we allow self intersecting sequences, we actually have
/// the full free monoid.
///
/// From this perspective, a closed snake corresponds to the quotient class that
/// contains the identity action / monoid element (i.e. no movement) as a representative.
///
/// Note that this structure does not support a useful inversion,
/// because we cannot include "turning around" at the end of the chain
/// into the formalism. The snake is in so far asymmetric, until it is closed.
/// A closed snake traces out a path that can be inverted (see the `Rat` type).
#[derive(Debug, Clone)]
pub struct Snake<T: IsRing> {
    /// Abstract sequence of unit segments that point into different directions
    /// (i.e. turtle movement instructions).
    /// Each number corresponds to the corresponding rotated unit in the
    /// underlying cyclotomic ring.
    angles: Vec<i8>,

    /// Sum of outer angles (i.e. sum of the angle sequence).
    ang_sum: i64,

    /// Representative polyline vertices
    /// (always non-empty and starting at origin).
    points: Vec<T>,

    /// Structure to collect indices of points that fall
    /// into the same unit square grid cell.
    /// Used to minimize number of segments to be compared
    /// when checking for self-intersections
    /// (including touching segment endpoints).
    ///
    /// Each point with index i is part of at most two segments,
    /// with indices (i-1, i) and (i, i+1), if 0 < i < num_points
    grid: UnitSquareGrid,

    /// If set to true, the snake will NOT prevent self-intersections.
    allow_intersections: bool,

    /// Set of all visited points for fast vertex-revisit detection.
    /// Only populated when T::turn() == 4 (i.e. ZZ4), where all edges are
    /// axis-aligned unit segments and intersection reduces to vertex revisits.
    /// None for all other ring types (avoiding allocation/insertion overhead).
    visited: Option<HashSet<T>>,

    /// When the snake retro-closes (the latest [`add`] / [`add_unsafe`]
    /// produced a polygon), [`add_unsafe`] overwrites `angles[0]` to
    /// make the angle sum a full ±turn. We cache the pre-overwrite
    /// value here so [`pop`] can restore it. `None` whenever the
    /// snake is open or freshly constructed.
    saved_angle_0: Option<i8>,
}

impl<I: ToPrimitive, T: IsRing> TryFrom<&[I]> for Snake<T> {
    type Error = &'static str;

    /// Create a snake from an angle sequence.
    /// Equivalent to adding all angles sequentially.
    fn try_from(angles: &[I]) -> Result<Self, Self::Error> {
        let mut result = Self::new();
        match result.extend_from_slice(angles) {
            Ok(()) => Ok(result),
            Err(_) => Err("Self-intersecting angle sequence!"),
        }
    }
}
impl<const N: usize, I: ToPrimitive, T: IsRing> TryFrom<&[I; N]> for Snake<T> {
    type Error = &'static str;

    fn try_from(angles: &[I; N]) -> Result<Self, Self::Error> {
        Self::try_from(angles.as_slice())
    }
}

impl<T: IsRing> Default for Snake<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: IsRing> Snake<T> {
    /// Return a new empty snake that is guaranteed to be free of self-intersections.
    pub fn new() -> Self {
        let mut grid = UnitSquareGrid::new();
        grid.add((0, 0), 0);
        let visited = if T::turn() == 4 {
            let mut s = HashSet::new();
            s.insert(T::zero());
            Some(s)
        } else {
            None
        };
        Self {
            points: vec![T::zero(); 1],
            angles: Vec::new(),
            ang_sum: 0,
            grid,
            allow_intersections: false,
            visited,
            saved_angle_0: None,
        }
    }

    /// Return a new empty snake that allows self-intersecting segment chains.
    pub fn new_unchecked() -> Self {
        Self {
            allow_intersections: true,
            ..Self::new()
        }
    }

    /// Return a snake that *allows* self-intersecting segment chains
    /// from a given sequence of angles.
    pub fn from_slice_unchecked<I: ToPrimitive>(angles: &[I]) -> Self {
        let mut result = Self::new_unchecked();
        result.extend_from_slice(angles).unwrap(); // Err will not happen with unchecked
        result
    }

    /// Return a snake that is guaranteed to be free of self-intersections
    /// from a trusted sequence of angles (that will **not** be verified).
    ///
    /// To be used for performance optimizations on already checked sequences.
    pub fn from_slice_unsafe<I: ToPrimitive>(angles: &[I]) -> Self {
        let mut result = Self::from_slice_unchecked(angles);
        result.allow_intersections = false;
        result
    }

    // ----

    /// Returns whether the snake is unchecked (i.e. created with `new_unchecked`).
    pub fn is_unchecked(&self) -> bool {
        self.allow_intersections
    }

    /// Return the number of unit segments of this snake.
    pub fn len(&self) -> usize {
        self.angles.len()
    }

    /// Returns whether the snake is empty,
    /// i.e. that it has no segments.
    pub fn is_empty(&self) -> bool {
        self.angles.is_empty()
    }

    /// Return angle sequence this snake is defined by.
    pub fn angles(&self) -> &[i8] {
        self.angles.as_slice()
    }

    /// Return the sum of angles. If the snake is closed,
    /// corresponds to the sum of outer angles.
    pub fn angle_sum(&self) -> i64 {
        self.ang_sum
    }

    /// Return canonical representative polyline vertex sequence.
    pub fn representative(&self) -> &[T] {
        self.points.as_slice()
    }

    /// Returns true if the represented path is closed, i.e.
    /// not empty + first and last point is the same (and equal to 0).
    ///
    /// As we always ensure that the sequence is not self-intersecting,
    /// this also equals to being a simple polygon.
    pub fn is_closed(&self) -> bool {
        !self.is_empty() && *self.points.last().unwrap() == T::zero()
    }

    // ----

    /// Returns the offset from the origin, i.e. effective
    /// direct Euclidean distance travelled by the snake.
    pub fn offset(&self) -> T {
        *self.points.last().unwrap()
    }

    /// Return the current facing direction of the snake.
    pub fn direction(&self) -> i8 {
        (self.ang_sum % (T::turn() as i64)) as i8
    }

    /// The head of the snake is the final turtle state
    /// after tracing out all the steps in the given snake.
    /// The tail of a snake is always fixed at the origin.
    pub fn head(&self) -> Turtle<T> {
        Turtle {
            pos: self.offset(),
            dir: self.direction(),
        }
    }

    // ----

    /// Return the two end points of the next segment,
    /// obtained from adding a new directed step.
    fn next_seg(&self, angle: i8) -> (T, T) {
        let old_direction = self.direction();
        let last = *self.points.last().unwrap();
        let new_pt = last + (<T as Units>::unit(old_direction) * <T as Units>::unit(angle));
        (last, new_pt)
    }

    /// Add a segment to the snake without checking for
    /// denormalization, degeneracy or self-intersection.
    fn add_unsafe(&mut self, angle: i8) {
        // compute next representative point (uses current orientation!)
        let (_, new_pt) = self.next_seg(angle);

        // append segment to symbolic angle sequence
        self.angles.push(angle);
        self.ang_sum += angle as i64;

        // register point in the grid
        self.grid
            .add(UnitSquareGrid::cell_of(new_pt), self.points.len());
        // add point to representative polyline
        self.points.push(new_pt);
        if let Some(ref mut visited) = self.visited {
            visited.insert(new_pt);
        }

        // if the snake is closed, we need to fix up the start angle
        if self.is_closed() {
            // the missing angle must complete one full turn
            // clockwise or counter-clockwise (simple polygon property).
            // Cache the original `angles[0]` so `pop` can restore it.
            debug_assert!(self.saved_angle_0.is_none());
            let target = (T::turn() as i64) * self.ang_sum.signum();
            let original_angle_0 = self.angles[0];
            let missing = target - (self.ang_sum - original_angle_0 as i64);
            self.angles[0] = missing as i8;
            self.ang_sum = target;
            self.saved_angle_0 = Some(original_angle_0);
        }
    }

    /// Return a polyline by tracing out snake with given turtle.
    pub fn to_polyline(&self, turtle: Turtle<T>) -> Vec<T> {
        let mut result = Self::new();
        *result.points.last_mut().unwrap() = turtle.pos;
        result.ang_sum = turtle.dir as i64;

        for angle in self.angles.iter() {
            result.add_unsafe(*angle);
        }

        result.points
    }

    pub fn to_polyline_f64(&self, turtle: Turtle<T>) -> Vec<(f64, f64)> {
        self.to_polyline(turtle)
            .iter()
            .map(|p| {
                let Complex { re: x, im: y } = p.complex64();
                (x, y)
            })
            .collect()
    }

    /// Return all representative segments of the current snakes
    /// that intersect with at least one of the given cells.
    ///
    /// Kept for tests only; the hot path in `can_add` traverses the grid
    /// directly without materializing this list.
    #[cfg(test)]
    fn cell_segs(&self, cells: &[(i64, i64)]) -> Vec<(T, T)> {
        let mut seg_pt_indices: Vec<(usize, usize)> = Vec::new();
        for pt_idx in self.grid.get_cells(cells) {
            // each point is part of at least one and at most 2 segments
            if pt_idx != 0 {
                seg_pt_indices.push((pt_idx - 1, pt_idx));
            }
            // NOTE: self.len() = self.points.len()-1 = last pt idx
            if pt_idx != self.len() {
                seg_pt_indices.push((pt_idx, pt_idx + 1));
            }
        }
        seg_pt_indices.sort();
        seg_pt_indices.dedup();
        seg_pt_indices
            .iter()
            .map(|(ix1, ix2)| (self.points[*ix1], self.points[*ix2]))
            .collect()
    }

    /// Check if the new segment can be added without
    /// causing a self-intersection.
    ///
    /// Note that the correctness of the optimized check strongly relies
    /// on the assumption that all segments have unit length.
    /// Check whether appending the segment described by `angle` would cause
    /// a self-intersection.
    ///
    /// Returns `None` if the segment can be added safely, or `Some(edge_idx)`
    /// where `edge_idx` is the latest (highest-index) existing edge that
    /// conflicts. If multiple edges conflict, the latest is returned — it is
    /// the closest to the would-be new edge.
    ///
    /// The closing segment (new endpoint = origin) is exempt and returns `None`.
    /// The "already closed" and "allow_intersections" fast paths are handled
    /// here for now; they return `Some(0)` for closed and `None` for unchecked.
    fn can_add(&self, angle: i8) -> Option<usize> {
        if self.allow_intersections {
            return None;
        }

        if self.is_closed() {
            return Some(0);
        }

        let new_seg @ (prev_pt, new_pt) = self.next_seg(angle);

        if let Some(ref visited) = self.visited {
            if new_pt.is_zero() || !visited.contains(&new_pt) {
                return None;
            }
            // Vertex revisit: scan for the index.
            for i in 1..self.points.len() {
                if self.points[i] == new_pt {
                    return Some(i);
                }
            }
            unreachable!("visited contains new_pt but not found in points");
        }

        // Direct grid traversal: no intermediate Vec / sort / dedup.
        // We walk the 5+5 cells of the segment's neighborhood, look up
        // point indices in each cell directly, and from each point
        // index recover the (at most two) adjacent segments.
        //
        // A u128 bitmap deduplicates segment ids on the fly when they
        // fit (i.e. id < 128). Snake lengths beyond that -- e.g. long
        // patch boundaries -- fall through to running `intersect` on
        // the duplicate, which is correct (intersect is idempotent),
        // just slightly wasteful. No hard limit on snake length.
        let new_pt_nz = !new_pt.is_zero();
        let len = self.len();
        let mut seen_segs: u128 = 0;
        let mut conflict: Option<usize> = None;

        // Iterate the precomputed deduplicated cell set for this segment's
        // (dx, dy) cell offset (one of 9 cases). Yields at most 8 cells, all
        // unique -- no runtime dedup needed at the cell level.
        let mut record = |idx: usize| {
            conflict = Some(conflict.map_or(idx, |c| c.max(idx)));
        };

        for cell in UnitSquareGrid::edge_neighborhood_of(prev_pt, new_pt) {
            for &pt_idx in self.grid.get(cell) {
                // Vertex-revisit check (only when new_pt is not origin --
                // origin matches points[0] by polygon closure, which is fine).
                if new_pt_nz && self.points[pt_idx] == new_pt {
                    record(pt_idx);
                }
                // Segment ending at pt_idx (if any).
                if pt_idx > 0 {
                    let seg_id = pt_idx - 1;
                    if check_and_mark(&mut seen_segs, seg_id) {
                        let s = (self.points[seg_id], self.points[pt_idx]);
                        if intersect_unit_segments(&new_seg, &s) {
                            record(seg_id);
                        }
                    }
                }
                // Segment starting at pt_idx (if any).
                if pt_idx < len {
                    let seg_id = pt_idx;
                    if check_and_mark(&mut seen_segs, seg_id) {
                        let s = (self.points[pt_idx], self.points[pt_idx + 1]);
                        if intersect_unit_segments(&new_seg, &s) {
                            record(seg_id);
                        }
                    }
                }
            }
        }
        conflict
    }

    /// Add a new segment to the snake, returning the index of the conflicting
    /// edge if the segment would cause a self-intersection.
    ///
    /// Returns `None` on success (segment added), or `Some(edge_idx)` where
    /// `edge_idx` is the latest existing edge that conflicts with the new
    /// segment. Panics if the snake is already closed or the angle is a
    /// half-turn (degenerate).
    pub fn add_diagnosed(&mut self, angle: i8) -> Option<usize> {
        assert!(!self.is_closed(), "add_diagnosed: snake is already closed");
        let a = normalize_angle::<T>(angle);
        assert!(a.abs() != T::hturn());
        let conflict = self.can_add(a);
        if conflict.is_none() {
            self.add_unsafe(a);
        }
        conflict
    }

    /// Add a new segment to the snake.
    /// Returns true on success or false if the new segment
    /// would cause a self-intersection (point is rejected).
    pub fn add(&mut self, angle: i8) -> bool {
        if self.is_closed() {
            return false;
        }
        self.add_diagnosed(angle).is_none()
    }

    /// Remove the most-recently-added segment, returning its angle
    /// (after normalisation). `None` if the snake is empty.
    ///
    /// Reverses every state change that [`add`] / [`add_unsafe`]
    /// made on the last call:
    ///
    /// - pops the angle and trailing vertex,
    /// - deregisters the cell from the grid,
    /// - removes the point from the visited set (skipping the start
    ///   point, which other segments may still touch),
    /// - restores `angles[0]` if the popped segment was the one that
    ///   retro-closed the snake.
    ///
    /// Calling `pop` after every `add` returns the snake to exactly
    /// its prior state, so this enables zero-allocation backtracking
    /// loops (compare `rat_enum.rs`).
    pub fn pop(&mut self) -> Option<i8> {
        let popped_angle = self.angles.pop()?;
        let popped_point = self.points.pop().expect("points and angles in lockstep");

        // Remove the popped vertex from the grid. Its grid index was
        // the new `len()` of `points` (after the pop), since indices
        // are 0-based.
        self.grid
            .remove(UnitSquareGrid::cell_of(popped_point), self.points.len());

        // Remove from the visited set (ZZ4 path). The starting point
        // is always retained -- when the popped segment was the
        // closing one, popped_point == points[0] and the start is
        // still in the polyline.
        if let Some(visited) = self.visited.as_mut()
            && Some(&popped_point) != self.points.first()
        {
            visited.remove(&popped_point);
        }

        if let Some(original_angle_0) = self.saved_angle_0.take() {
            // The popped segment was the one that closed the snake.
            // Restore `angles[0]` and recompute `ang_sum` from the
            // (now-shorter) angle vector.
            if !self.angles.is_empty() {
                self.angles[0] = original_angle_0;
            }
            self.ang_sum = self.angles.iter().map(|&a| a as i64).sum();
        } else {
            self.ang_sum -= popped_angle as i64;
        }

        Some(popped_angle)
    }

    /// Extend a snake from a sequence of angles in-place.
    pub fn extend_from_slice<I: ToPrimitive>(&mut self, angles: &[I]) -> Result<(), &str> {
        for angle in angles {
            if !self.add(angle.to_i8().unwrap()) {
                return Err("Cannot extend, self-intersecting sequence!");
            }
        }
        Ok(())
    }

    /// Concatenate given snake to this one in-place.
    pub fn extend(&mut self, other: &Snake<T>) -> Result<(), &str> {
        self.extend_from_slice(other.angles.as_slice())
    }

    /// Return concatenation of two snakes.
    pub fn concat(&self, other: &Snake<T>) -> Result<Self, &str> {
        let errmsg = "Cannot concatenate, self-intersecting sequence!";
        let mut result = Self::new();
        // FIXME: why can't I return the error message from the inner result?! (borrow issues)
        match result.extend(self) {
            Ok(()) => {}
            Err(_) => return Err(errmsg),
        }
        match result.extend(other) {
            Ok(()) => {}
            Err(_) => return Err(errmsg),
        }
        Ok(result)
    }

    /// Point-in-polygon check using raycasting.
    pub fn is_point_inside(&self) -> bool {
        if !self.is_closed() {
            return false;
        }

        true
    }
}

// For comparisons (Eq, Ord) and presentation (Display)
// we only care about the angles, all other data is derivative.
impl<T: IsRing> PartialEq for Snake<T> {
    fn eq(&self, other: &Self) -> bool {
        self.angles == other.angles
    }
}
impl<T: IsRing> Eq for Snake<T> {}
impl<T: IsRing> PartialOrd for Snake<T> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}
impl<T: IsRing> Ord for Snake<T> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.angles.cmp(&other.angles)
    }
}
impl<T: IsRing> Display for Snake<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.angles.fmt(f)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::cyclotomic::{Ccw, SymNum, ZZ4, ZZ12};
    use num_traits::{One, Zero};

    /// **T-touch regression pin** for the ZZ12 snake
    /// `0 5 -2 5 -1 5 -5 4 1 1 1 5 -5 5` followed by angle `3`.
    ///
    /// Initially reported as a possible false-positive
    /// self-intersection rejection (visual inspection in
    /// `rat_explorer` suggested the new segment "shouldn't"
    /// intersect anything). Closer analysis: the new segment ENDS
    /// exactly on the interior of edge 9. Specifically:
    ///
    /// * `P9 = 3 - 2ζ - ζ² + ζ³`, `P10 = 3 - ζ - ζ² + ζ³`, so edge
    ///   9 has direction `ζ` (unit length).
    /// * Adding angle `3` after the 14-segment prefix produces
    ///   `P15 = 4 - 3ζ + ζ³`.
    /// * `P15 - P9 = 1 - ζ + ζ² = (√3 - 1)·ζ` exactly.
    /// * Since `√3 - 1 ≈ 0.732 ∈ (0, 1)`, `P15` lies strictly
    ///   inside edge 9 -- a T-touch. The resulting figure would
    ///   not be a simple polygon, so the rejection is correct.
    ///
    /// Pins:
    /// * All 14 prefix adds succeed.
    /// * `add(3)` reports conflict at edge index 9 specifically
    ///   (the edge whose interior is touched).
    /// * The new segment is the one ending at `P15`.
    #[test]
    fn zz12_t_touch_rejected_at_edge_9() {
        let mut s: Snake<ZZ12> = Snake::new();
        let prefix: &[i8] = &[0, 5, -2, 5, -1, 5, -5, 4, 1, 1, 1, 5, -5, 5];
        for (i, &a) in prefix.iter().enumerate() {
            assert!(s.add(a), "ZZ12 prefix add #{i} (angle {a}) was rejected",);
        }
        assert_eq!(s.len(), prefix.len());
        let conflict = s.add_diagnosed(3);
        assert_eq!(
            conflict,
            Some(9),
            "expected T-touch rejection at edge 9 (new endpoint = P9 + (√3-1)·ζ)"
        );
    }

    #[test]
    #[should_panic]
    fn test_add_invalid_angle() {
        let mut s: Snake<ZZ12> = Snake::new();
        s.add(6);
    }

    #[test]
    #[should_panic]
    fn test_add_invalid_angle_neg() {
        let mut s: Snake<ZZ12> = Snake::new();
        s.add(-6);
    }

    #[test]
    #[should_panic]
    fn test_add_invalid_angle_mod() {
        let mut s: Snake<ZZ12> = Snake::new();
        s.add(18);
    }

    #[test]
    fn test_basic() {
        let mut s: Snake<ZZ12> = Snake::new();
        assert!(s.is_empty());
        assert!(!s.is_closed());
        assert_eq!(s.len(), 0);
        assert_eq!(s.angle_sum(), 0);
        assert_eq!(s.direction(), 0);
        assert_eq!(s.offset(), ZZ12::zero());

        s.add(-9); // same as 3
        assert!(!s.is_empty());
        assert!(!s.is_closed());
        assert_eq!(*s.angles().last().unwrap(), 3);
        assert_eq!(s.direction(), 3);
        assert_eq!(s.offset(), <ZZ12 as Units>::unit(3));

        s.add(2);
        s.add(2);
        s.add(5);
        assert_eq!(s.len(), 4);

        // check behavior of extend and concat
        let mut s2: Snake<ZZ12> = Snake::new();
        s2.add(-2);
        s2.add(0);
        s2.add(5);
        assert_eq!(s2.len(), 3);

        let s3 = s.concat(&s2).unwrap();
        s.extend(&s2).unwrap();
        assert_eq!(s, s3);

        // check that state is as expected
        assert_eq!(s.len(), 7);
        assert_eq!(s.angle_sum(), 15);
        assert_eq!(s.direction(), 3);
        assert_eq!(s.head().dir, s.direction());
        assert_eq!(s.head().pos, s.offset());

        // rep. polyline = instantiated with default turtle
        let l_exp: Vec<ZZ12> = s.representative().to_vec();
        let l = s.to_polyline(Turtle::default());
        assert_eq!(l, l_exp);

        // check instantiation with a non-trivial turtle
        let t = Turtle {
            pos: ZZ12::ccw().scale(7),
            dir: -2,
        };
        let l2_exp: Vec<ZZ12> = l_exp
            .iter()
            .map(|pt| (*pt * <ZZ12 as Units>::unit(t.dir)) + t.pos)
            .collect();
        let l2 = s.to_polyline(t);
        assert_eq!(l2, l2_exp);
    }

    #[test]
    fn test_closed_snake() {
        // test that once a snake is closed, the initial angle is fixed up
        // (the first angle is relative to the initially undefined predecessor)
        let sq1: Snake<ZZ12> = Snake::try_from(&[0, 3, 3, 3]).unwrap();
        assert!(sq1.is_closed());
        assert_eq!(sq1.angle_sum(), ZZ12::turn() as i64);
        let sq2: Snake<ZZ12> = Snake::try_from(&[0, -3, -3, -3]).unwrap();
        assert!(sq2.is_closed());
        assert_eq!(sq2.angle_sum(), -ZZ12::turn() as i64);

        let mut square: Snake<ZZ12> = Snake::new();
        assert!(!square.is_closed()); // empty

        for _ in 0..3 {
            square.add(3);
        }
        assert!(!square.is_closed()); // not closed

        square.add(3);
        assert!(square.is_closed()); // valid
    }

    #[test]
    fn test_cell_segs() {
        let mut s: Snake<ZZ12> = Snake::new();
        assert!(s.cell_segs(&[(0, 0)]).is_empty());

        s.add(0);
        assert_eq!(s.cell_segs(&[(0, 0)]), &[(ZZ12::zero(), ZZ12::one())]);

        s.add(0);
        assert_eq!(s.cell_segs(&[(0, 0)]), &[(ZZ12::zero(), ZZ12::one())]);
        assert_eq!(
            s.cell_segs(&[(1, 0)]),
            &[
                (ZZ12::zero(), ZZ12::one()),
                (ZZ12::one(), ZZ12::one().scale(2))
            ]
        );
        assert_eq!(
            s.cell_segs(&[(2, 0)]),
            &[(ZZ12::one(), ZZ12::one().scale(2))]
        );
    }

    #[test]
    fn test_add_diagnosed_crossing() {
        // s3: origin → unit(0) → unit(0)+unit(4).
        // angle 5 would go back across edge 0.
        let mut s3: Snake<ZZ12> = Snake::try_from(&[0, 4]).unwrap();
        assert_eq!(s3.add_diagnosed(5), Some(0), "should cross edge 0");
        // add still returns false — no behavioral change.
        assert!(!s3.add(5));
    }

    #[test]
    fn test_add_diagnosed_vertex_revisit() {
        // ZZ4: [0,0,1,1] → (0,0)→(1,0)→(2,0)→(2,1)→(1,1). Dir=2(left).
        // From (1,1), angle 1 → dir 3(down): new_pt = (1,1)+(-i) = (1,0) = vertex 1.
        // Vertex index 1 = edge 1.
        let mut s: Snake<ZZ4> = Snake::try_from(&[0, 0, 1, 1]).unwrap();
        assert_eq!(
            s.add_diagnosed(1),
            Some(1),
            "should revisit vertex 1 (edge 1)"
        );
    }

    /// Cross-check `add_diagnosed` against a brute scan: build several
    /// snakes, try every legal next angle, and for each rejection
    /// confirm the reported edge index matches `max` over all edges
    /// that geometrically conflict with the would-be new segment.
    ///
    /// "Latest" is the load-bearing contract; this test verifies it
    /// directly rather than relying on a hand-picked multi-crossing
    /// configuration.
    #[test]
    fn test_add_diagnosed_latest_conflict_brute() {
        fn brute_conflicts<T: IsRing>(s: &Snake<T>, angle: i8) -> Vec<usize> {
            let new_seg @ (_prev, new_pt) = s.next_seg(angle);
            let new_pt_nz = !new_pt.is_zero();
            let mut conflicts: Vec<usize> = Vec::new();
            // Vertex revisits: any existing vertex (except origin / closure)
            // that matches `new_pt`.
            for i in 1..s.points.len() {
                if new_pt_nz && s.points[i] == new_pt {
                    conflicts.push(i);
                }
            }
            // Segment crossings: every existing edge.
            for seg_id in 0..s.len() {
                let seg = (s.points[seg_id], s.points[seg_id + 1]);
                if intersect_unit_segments(&new_seg, &seg) {
                    conflicts.push(seg_id);
                }
            }
            conflicts
        }

        fn check<T: IsRing>(label: &str, prefix: &[i8]) {
            let s: Snake<T> = Snake::try_from(prefix).expect("valid prefix");
            for direction in (-T::hturn() + 1)..T::hturn() {
                let expected_max = brute_conflicts(&s, direction).into_iter().max();
                let got = s.clone().add_diagnosed(direction);
                assert_eq!(
                    got, expected_max,
                    "{label}: prefix={prefix:?} angle={direction}: brute={expected_max:?}, got={got:?}"
                );
            }
        }

        // ZZ4 L-shaped walk. Last-vertex revisit by stepping back into
        // an interior vertex is one expected conflict here.
        check::<ZZ4>("zz4 L-walk", &[0, 0, 1, 1]);
        // ZZ12 short zig that creates multiple candidate crossing edges
        // on a follow-up angle.
        check::<ZZ12>("zz12 zig", &[0, 5]);
        check::<ZZ12>("zz12 longer zig", &[0, 5, -5, 5]);
        check::<ZZ12>("zz12 spiral", &[0, 1, 1, 1, 1, 1]);
    }

    #[test]
    #[should_panic(expected = "add_diagnosed: snake is already closed")]
    fn test_add_diagnosed_panics_on_closed() {
        let mut s: Snake<ZZ12> = Snake::try_from(&[3, 3, 3]).unwrap();
        assert!(s.add(3)); // closes the square
        s.add_diagnosed(0); // should panic
    }

    #[test]
    fn test_can_add() {
        let mut s: Snake<ZZ12> = Snake::try_from(&[3, 3, 3]).unwrap();
        assert!(s.add(3)); // can add, closes shape
        assert!(!s.add(0)); // cannot add, shape is already closed

        let mut s2: Snake<ZZ12> = Snake::try_from(&[0, 3, 3, 3]).unwrap();
        assert!(!s2.add(3)); // cannot add, closes shape not in origin

        let mut s3: Snake<ZZ12> = Snake::try_from(&[0, 4]).unwrap();
        assert!(!s3.add(5)); // cannot add, crosses segment

        // try a more complicated example
        let mut s4: Snake<ZZ12> = Snake::new();
        assert!(s4.add(0));
        assert!(s4.add(5));

        // take sharpest turns possible
        assert!(!s4.add(4));
        assert!(s4.add(3));

        assert!(!s4.add(5));
        assert!(s4.add(4));

        assert!(!s4.add(2));
        assert!(s4.add(1));

        assert!(!s4.add(5));
        assert!(s4.add(4));

        // create a dead-end where we cannot continue the snake
        s4.extend(&Snake::try_from(&[1, 1, 3, 5]).unwrap()).unwrap();
        assert_eq!(s4.len(), 10);
        for i in (-ZZ12::hturn() + 1)..(ZZ12::hturn() - 1) {
            assert!(!s4.add(i));
        }
    }

    #[test]
    fn test_eq_ord() {
        let s1: Snake<ZZ12> = Snake::try_from(&[1, 2, 3]).unwrap();
        let mut s2: Snake<ZZ12> = Snake::try_from(s1.angles.as_slice()).unwrap();
        assert_eq!(s1, s2);

        s2.add(4);
        assert!(s1 != s2);
        assert!(s1 < s2);

        let s3: Snake<ZZ12> = Snake::try_from(&[-1, 4, 3]).unwrap();
        assert!(s3 < s1);
        assert!(s3 < s2);

        let s4: Snake<ZZ12> = Snake::new();
        assert!(s4 < s1);
        assert!(s4 < s2);
        assert!(s4 < s3);

        // check natural lexicographic sorting order:
        // compare prefix of length of the shorter sequence
        // the lexicographically smaller is smaller
        // if they are equal on the prefix, the shorter is smaller
        assert!(vec![1, 2] < vec![1, 2, -1]);
        assert!(vec![-1, 2, 3] < vec![1, 2]);
        assert!(vec![-1, 2] < vec![1, 2, 3]);
    }

    #[test]
    fn test_display() {
        let mut s: Snake<ZZ12> = Snake::new();
        for i in -2..2 {
            s.add(i);
        }
        s.add(7);
        assert_eq!(format!("{s}"), "[-2, -1, 0, 1, -5]");
    }

    #[test]
    fn test_zz4_visited_fast_path() {
        let mut s: Snake<ZZ4> = Snake::new();
        assert!(s.visited.is_some());
        assert!(s.add(0));
        assert!(s.add(0));
        assert!(s.add(1));
        assert!(s.add(1));
        assert!(!s.add(1));
    }

    #[test]
    fn test_zz4_visited_matches_grid() {
        let mut s_grid: Snake<ZZ12> = Snake::new();
        let mut s_fast: Snake<ZZ4> = Snake::new();
        let zz4_angles: &[i8] = &[0, 1, 1, 1];
        for &a in zz4_angles {
            assert_eq!(s_grid.add(a * 3), s_fast.add(a), "angle {a}");
        }
        assert!(s_fast.is_closed());
        assert!(s_grid.is_closed());
    }

    // ---- pop tests ----
    //
    // The contract: after `add(x); pop();` the snake's externally
    // observable state is identical to before the add. Tests cover
    // the open-snake case, the closed-snake case (where add_unsafe
    // retroactively overwrites angles[0]), and the empty-snake edge.

    /// Snapshot of every externally-observable Snake field, used by
    /// the round-trip pop tests below.
    fn snapshot<T: IsRing>(s: &Snake<T>) -> (Vec<i8>, i64, bool, T, i8) {
        (
            s.angles().to_vec(),
            s.angle_sum(),
            s.is_closed(),
            s.offset(),
            s.direction(),
        )
    }

    #[test]
    fn test_pop_on_empty_snake_returns_none() {
        let mut s: Snake<ZZ12> = Snake::new();
        assert!(s.pop().is_none());
        assert!(s.is_empty());
    }

    #[test]
    fn test_add_then_pop_round_trips_open_snake() {
        // Hexagon partial walk: 5 of 6 segments, snake stays open.
        let mut s: Snake<ZZ12> = Snake::new();
        for a in [2i8, 2, 2, 2, 2] {
            assert!(s.add(a));
        }
        let before = snapshot(&s);

        assert!(s.add(2)); // 6th hex segment -- would close.
        assert!(s.is_closed());
        let popped = s.pop();
        assert_eq!(popped, Some(2));
        assert_eq!(snapshot(&s), before);
        assert!(!s.is_closed());
    }

    #[test]
    fn test_pop_undoes_retro_close_fixup() {
        // For a *simple* closing polygon, angles sum to ±turn and
        // the retro-close fixup in `add_unsafe` is a no-op. The
        // saved_angle_0 cache still flows through `pop`; we verify
        // the round-trip ends at the pre-close snapshot exactly.
        let mut s: Snake<ZZ12> = Snake::new();
        for a in [2i8, 2, 2, 2, 2] {
            assert!(s.add(a));
        }
        let pre_close = snapshot(&s);
        assert!(!s.is_closed());
        assert!(s.add(2)); // 6th hexagon edge -- closes.
        assert!(s.is_closed());
        assert_eq!(s.angle_sum().unsigned_abs(), 12);

        // Pop the closing segment: state must match pre-close
        // exactly (angles[0] included), and the snake re-opens.
        let popped = s.pop();
        assert_eq!(popped, Some(2));
        assert_eq!(snapshot(&s), pre_close);
        assert!(!s.is_closed());
        assert_eq!(s.angles().len(), 5);
    }

    #[test]
    fn test_repeated_add_pop_each_direction_is_idempotent() {
        // The rat_enum backtracking pattern: try every direction
        // from a given prefix, add then pop, verify the snake is
        // back to the prefix state every time.
        let mut s: Snake<ZZ12> = Snake::new();
        for a in [2i8, 2, 2] {
            assert!(s.add(a));
        }
        let baseline = snapshot(&s);

        for direction in -5i8..=5 {
            let pre = snapshot(&s);
            if s.add(direction) {
                let _ = s.pop();
            }
            assert_eq!(snapshot(&s), pre, "direction {direction}: state diverged");
        }
        assert_eq!(snapshot(&s), baseline);
    }

    #[test]
    fn test_add_pop_visited_set_preserves_start() {
        // ZZ4 path uses the visited HashSet for revisit detection.
        // When pop removes the *closing* segment, points[0] is the
        // popped vertex but it must remain in `visited` (the polygon
        // still has a vertex there as its starting point).
        let mut s: Snake<ZZ4> = Snake::new();
        for a in [1i8, 1, 1] {
            assert!(s.add(a));
        }
        // Closing step: angle 1 brings us back to origin (the start).
        assert!(s.add(1));
        assert!(s.is_closed());

        let _ = s.pop();
        // After popping the closing step we are at the 4th vertex
        // (one short of closing). Now re-adding the closing step
        // must still work -- which it can only do if origin remains
        // in `visited` and the geometry round-trips correctly.
        assert!(!s.is_closed());
        assert!(s.add(1), "re-adding closing step after pop must work");
        assert!(s.is_closed());
    }

    #[test]
    fn test_pop_decrements_grid_so_can_add_works_again() {
        // After pop, a previously-blocked direction (because it'd
        // revisit the popped point) should now be allowed again.
        let mut s: Snake<ZZ12> = Snake::new();
        // Walk a tiny L: [3, 3] - now at a corner two unit cells
        // from the origin in different directions.
        assert!(s.add(3));
        assert!(s.add(3));
        // The next add(0) would walk back through a visited cell;
        // verify it's rejected.
        // (Test depends on geometry; the simpler invariant is
        // that pop releases the grid entry it added.)
        let pre_grid_state = s.points.len();
        assert!(s.pop().is_some());
        assert_eq!(s.points.len(), pre_grid_state - 1);
        // And the snake should once again be able to add(3) (we
        // just popped a (3) step) -- round-trip should be allowed.
        assert!(s.add(3));
    }
}