tilezz 0.2.0

//! The geometry backend the enumeration DFS walks over.
//!
//! [`crate::enumerate::dfs::rat_enum_step`] is a single generic algorithm:
//! it owns the direction order, the canonical prune, the reachability
//! prunes, closure recording, and the seed-split policy. Everything that
//! is *geometry* -- extend the boundary by one edge (rejecting a
//! self-intersection), back it off, and read the current head / turning
//! sequence -- is behind this [`Boundary`] trait, so the same DFS drives
//! either backend:
//!
//! * [`Snake`] -- exact cyclotomic arithmetic; self-avoidance is an
//!   `intersect` orientation test against a grid of nearby edges.
//! * [`DominoBoundary`] -- the transfer-matrix automaton
//!   ([`crate::geom::celltable`]): the head is a
//!   `(cell, state)` advanced by a precomputed transition table (no
//!   `cell_floor`), and self-avoidance is a per-cell fragment-conflict
//!   bit lookup (no multiplication). Same tree, same results, ~2x faster.
//!   Works for any ring (the cell is a parallelogram of two ring
//!   elements; on `HasZZ4` rings it is the axis-aligned unit square).

use std::collections::{HashMap, HashSet};

use crate::cyclotomic::{IsRing, Units};
use crate::geom::celltable::{FragId, FragmentAlphabet, Placement, StateAlphabet, StateId};
use crate::geom::snake::Snake;

/// One growing rat boundary the DFS extends and backtracks. Angles are
/// the cyclic turning sequence; on closure `angles[0]` is the origin
/// vertex's turn (not edge-0's heading), matching [`Snake`] exactly, so
/// `Rat::from_slice_trusted(b.angles())` is valid for any backend.
pub trait Boundary<ZZ> {
    /// Try to extend by a unit edge turning `angle` from the current
    /// heading. Returns `false` (leaving the boundary unchanged) iff the
    /// new edge would self-intersect or revisit a vertex.
    fn add(&mut self, angle: i8) -> bool;
    /// Undo the last successful [`add`](Boundary::add).
    fn pop(&mut self);
    /// The turning-angle prefix walked so far.
    fn angles(&self) -> &[i8];
    /// Whether the head has returned to the origin (a closed rat).
    fn is_closed(&self) -> bool;
    /// The head vertex position.
    fn offset(&self) -> ZZ;
    /// The current heading (absolute unit-direction index).
    fn direction(&self) -> i8;
    /// Optional `--paranoid` cross-check after a successful add; default
    /// no-op. `Snake` re-derives the prefix from scratch.
    fn paranoid_recheck(&self) {}
}

impl<ZZ: IsRing> Boundary<ZZ> for Snake<ZZ> {
    fn add(&mut self, angle: i8) -> bool {
        Snake::add(self, angle)
    }
    fn pop(&mut self) {
        Snake::pop(self);
    }
    fn angles(&self) -> &[i8] {
        Snake::angles(self)
    }
    fn is_closed(&self) -> bool {
        Snake::is_closed(self)
    }
    fn offset(&self) -> ZZ {
        Snake::offset(self)
    }
    fn direction(&self) -> i8 {
        Snake::direction(self)
    }
    fn paranoid_recheck(&self) {
        // Replay the whole current prefix in a fresh Snake: any
        // disagreement means the stateful incremental check accepts a
        // prefix the from-scratch check rejects -- a Snake bug.
        let angles = Snake::angles(self).to_vec();
        let mut fresh: Snake<ZZ> = Snake::new();
        for (i, &a) in angles.iter().enumerate() {
            assert!(
                fresh.add(a),
                "stateful snake accepted full prefix {:?} but fresh snake \
                 rejected angle {a} at step {i}",
                angles,
            );
        }
        assert_eq!(
            fresh.is_closed(),
            Snake::is_closed(self),
            "fresh snake disagrees on is_closed for {:?}",
            angles
        );
    }
}

/// Per-edge undo record for [`DominoBoundary`]: the head state *before*
/// the edge, the slice of `place_buf` this edge added, the visited-vertex
/// it inserted (none on the closing edge), and the original `angles[0]`
/// if this edge triggered the closing-turn fixup.
struct Frame<ZZ> {
    cell: (i64, i64),
    state: StateId,
    pt: ZZ,
    facing: i8,
    places: (usize, usize),
    vertex: Option<(i64, i64, StateId)>,
    saved_angle0: Option<i8>,
}

/// Transfer-matrix geometry backend. Borrows a prebuilt state + fragment
/// alphabet (radius must cover `max_steps`) and tracks the head as
/// `(cell, state)` plus the exact point `pt` (carried only so the shared
/// reachability prune stays bit-identical to `Snake`).
pub struct DominoBoundary<'a, ZZ> {
    st: &'a StateAlphabet<ZZ>,
    fr: &'a FragmentAlphabet<ZZ>,
    turn: i8,
    cell: (i64, i64),
    state: StateId,
    pt: ZZ,
    facing: i8,
    angles: Vec<i8>,
    /// Fragment ids resident in each occupied cell.
    occ: HashMap<(i64, i64), Vec<FragId>>,
    /// Vertices on the path, keyed `(cell.x, cell.y, state)`.
    visited: HashSet<(i64, i64, StateId)>,
    /// Backtracking stack (one frame per live edge).
    frames: Vec<Frame<ZZ>>,
    /// Flat arena of emitted fragment placements; frame `i` owns
    /// `place_buf[frame.places.0 .. frame.places.1]` (no per-add alloc).
    place_buf: Vec<Placement>,
}

impl<'a, ZZ: IsRing> DominoBoundary<'a, ZZ> {
    /// A boundary rooted at the origin. `st`/`fr` must be built to
    /// `radius >= max_steps` so no transition ever leaves the ball.
    pub fn new(st: &'a StateAlphabet<ZZ>, fr: &'a FragmentAlphabet<ZZ>) -> Self {
        let origin = st.origin();
        let mut visited = HashSet::new();
        visited.insert((0, 0, origin));
        DominoBoundary {
            st,
            fr,
            turn: ZZ::turn(),
            cell: (0, 0),
            state: origin,
            pt: ZZ::zero(),
            facing: 0,
            angles: Vec::new(),
            occ: HashMap::new(),
            visited,
            frames: Vec::new(),
            place_buf: Vec::new(),
        }
    }
}

impl<ZZ: IsRing> Boundary<ZZ> for DominoBoundary<'_, ZZ> {
    fn add(&mut self, angle: i8) -> bool {
        let abs_dir = (self.facing as i64 + angle as i64).rem_euclid(self.turn as i64);
        let (next_state, delta) = self
            .st
            .step(self.state, abs_dir as usize)
            .expect("domino alphabet radius too small (transition left the ball)");
        let next_cell = (self.cell.0 + delta.0, self.cell.1 + delta.1);
        let new_pt = self.pt + <ZZ as Units>::unit(abs_dir as i8);

        // Buffer this edge's per-cell fragments into the arena, then check
        // each against the fragments already resident in that cell.
        let p0 = self.place_buf.len();
        for &pl in self.fr.emit(self.state, abs_dir as usize) {
            self.place_buf.push(pl);
        }
        let mut crossed = false;
        for i in p0..self.place_buf.len() {
            let (off, fid) = self.place_buf[i];
            let c = (self.cell.0 + off.0, self.cell.1 + off.1);
            if let Some(v) = self.occ.get(&c)
                && v.iter().any(|&g| self.fr.conflict(fid, g))
            {
                crossed = true;
                break;
            }
        }
        let is_origin = next_cell == (0, 0) && next_state == self.st.origin();
        let revisit = !is_origin
            && self
                .visited
                .contains(&(next_cell.0, next_cell.1, next_state));
        if crossed || revisit {
            self.place_buf.truncate(p0);
            return false;
        }

        // Commit. Frame captures the pre-add head for `pop`.
        let p1 = self.place_buf.len();
        for i in p0..p1 {
            let (off, fid) = self.place_buf[i];
            let c = (self.cell.0 + off.0, self.cell.1 + off.1);
            self.occ.entry(c).or_default().push(fid);
        }
        let vertex = if is_origin {
            None
        } else {
            let v = (next_cell.0, next_cell.1, next_state);
            self.visited.insert(v);
            Some(v)
        };
        let mut frame = Frame {
            cell: self.cell,
            state: self.state,
            pt: self.pt,
            facing: self.facing,
            places: (p0, p1),
            vertex,
            saved_angle0: None,
        };
        self.cell = next_cell;
        self.state = next_state;
        self.pt = new_pt;
        self.facing = abs_dir as i8;
        self.angles.push(angle);

        // Closing-turn fixup: `angles[0]` was edge-0's heading; make it
        // the origin vertex's turn so the sequence sums to +-turn (exactly
        // `Snake::add_unsafe`). Saved for `pop` to restore.
        if is_origin {
            let ang_sum: i64 = self.angles.iter().map(|&a| a as i64).sum();
            let target = self.turn as i64 * ang_sum.signum();
            let orig = self.angles[0];
            self.angles[0] = (target - (ang_sum - orig as i64)) as i8;
            frame.saved_angle0 = Some(orig);
        }
        self.frames.push(frame);
        true
    }

    fn pop(&mut self) {
        let frame = self.frames.pop().expect("pop with no live edge");
        self.angles.pop();
        if let Some(orig) = frame.saved_angle0
            && !self.angles.is_empty()
        {
            self.angles[0] = orig;
        }
        // Remove this edge's fragments (relative to its start cell).
        let (p0, p1) = frame.places;
        for i in p0..p1 {
            let (off, fid) = self.place_buf[i];
            let c = (frame.cell.0 + off.0, frame.cell.1 + off.1);
            let v = self.occ.get_mut(&c).expect("occ cell vanished");
            let pos = v.iter().rposition(|&g| g == fid).expect("frag vanished");
            v.swap_remove(pos);
        }
        self.place_buf.truncate(p0);
        if let Some(v) = frame.vertex {
            self.visited.remove(&v);
        }
        self.cell = frame.cell;
        self.state = frame.state;
        self.pt = frame.pt;
        self.facing = frame.facing;
    }

    fn angles(&self) -> &[i8] {
        &self.angles
    }
    fn is_closed(&self) -> bool {
        !self.angles.is_empty() && self.pt.is_zero()
    }
    fn offset(&self) -> ZZ {
        self.pt
    }
    fn direction(&self) -> i8 {
        self.facing
    }
}

// The domino backend is reached through the shared enumeration path:
// `enumerate_dispatch` (and thus `run_rat_enum_seqs` /
// `run_rat_enum_polylines` / the stream workers) builds a `DominoBoundary`
// factory when `domino` is set, so there is no separate automaton entry
// point -- only this `Boundary` impl.

#[cfg(test)]
mod tests {
    use crate::enumerate::run_rat_enum_seqs;
    use std::collections::BTreeMap;

    fn by_len(rats: &[Vec<i8>]) -> BTreeMap<usize, usize> {
        let mut m = BTreeMap::new();
        for s in rats {
            *m.entry(s.len()).or_insert(0) += 1;
        }
        m
    }

    /// The automaton backend and the Snake backend, driven by the *same*
    /// unified DFS, must explore the identical tree: same free-rat set and
    /// the same per-branch stats. This is the core equivalence guarantee.
    #[test]
    fn automaton_equals_snake() {
        for ring in [6u8, 10, 12] {
            for n in [6usize, 8] {
                let (a_rats, a) = run_rat_enum_seqs(ring, n, 1, 1, true, false, true);
                let (s_rats, s) = run_rat_enum_seqs(ring, n, 1, 1, true, false, false);
                assert_eq!(
                    a_rats.len(),
                    s_rats.len(),
                    "count mismatch ring={ring} n={n}"
                );
                assert_eq!(
                    by_len(&a_rats),
                    by_len(&s_rats),
                    "per-length mismatch ring={ring} n={n}"
                );
                assert_eq!(
                    (
                        a.closed,
                        a.intersected,
                        a.too_far,
                        a.recursed,
                        a.canonical_skip
                    ),
                    (
                        s.closed,
                        s.intersected,
                        s.too_far,
                        s.recursed,
                        s.canonical_skip
                    ),
                    "branch stats diverge ring={ring} n={n}"
                );
            }
        }
    }

    /// Full-scale correctness: OEIS A316192 (ZZ12 free) per-perimeter
    /// counts a(3..=13). Single-threaded, ~45 min.
    #[test]
    #[ignore = "heavy (~45 min, n=13); run with --ignored --nocapture"]
    fn automaton_a316192_to_n13() {
        const OEIS: &[(usize, usize)] = &[
            (3, 1),
            (4, 3),
            (5, 4),
            (6, 22),
            (7, 69),
            (8, 418),
            (9, 2210),
            (10, 14024),
            (11, 89075),
            (12, 597581),
            (13, 4076855),
        ];
        let (rats, _) = run_rat_enum_seqs(12, 13, 1, 1, true, false, true);
        let bl = by_len(&rats);
        let mut ok = true;
        for &(n, want) in OEIS {
            let got = bl.get(&n).copied().unwrap_or(0);
            eprintln!(
                "  a({n}) = {got} (OEIS {want}){}",
                if got == want { "" } else { "  MISMATCH" }
            );
            ok &= got == want;
        }
        assert!(ok, "automaton per-length counts diverge from OEIS A316192");
        assert_eq!(rats.len(), 4_780_262, "cumulative n<=13 free count");
    }
}