tilezz 0.2.0

//! The fragment alphabet and the conflict table.
//!
//! A **fragment** is one unit edge restricted to one cell it passes
//! through, taken relative to that cell (translated so the cell sits at
//! the origin). A unit edge crosses at most one wall of each of the two
//! cell-line families -- provably, for the near-quarter-turn cell basis;
//! see `occupied_offsets` -- so it occupies 1, 2, or 3 cells:
//!
//! * `(0,0)` -> the whole edge lives in one cell (both endpoints are
//!   vertices): a `VertexVertex` fragment.
//! * two axis-adjacent cells -> the edge crosses one wall: two
//!   `VertexWall` half-edges.
//! * three cells (a diagonal step across a grid corner) -> a start
//!   half-edge, a `WallWall` corner-cut through the middle cell, and an
//!   end half-edge.
//!
//! The full (unclipped) relative edge is kept per fragment, because the
//! conflict predicate needs whole segments. Two fragments **conflict**
//! iff their edges cross/touch improperly. Crossing is translation
//! invariant and every crossing lies in one cell that both edges pass
//! through, so testing every fragment pair with
//! [`intersect`] -- relative to
//! their shared cell -- is complete. `intersect` returns false for a
//! shared endpoint, so consecutive edges never conflict here; a
//! non-consecutive shared vertex is a walk-level concern (all vertices
//! distinct), not a fragment conflict.
//!
//! All of this is offline: the only multiplication in the whole pipeline
//! (the orientation tests inside `intersect`, and the corner-cell
//! comparison) happens here, once, building the tables consumers then
//! read with plain lookups.

use std::collections::HashMap;

use crate::cyclotomic::geometry::intersect;
use crate::cyclotomic::linalg::wedge_sign;
use crate::cyclotomic::{IsRing, Units};

use super::states::{StateAlphabet, StateId, cell_anchor, cell_basis, cell_of};

/// Index of a fragment within a [`FragmentAlphabet`].
pub type FragId = u32;

/// A fragment placed in a cell: `(cell offset, fragment id)`.
pub type Placement = ((i64, i64), FragId);

/// Which endpoints of a fragment's edge are vertices lying in the
/// fragment's own cell (versus wall crossings on the way through).
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum FragShape {
    /// The whole unit edge sits inside the cell (both endpoints are
    /// vertices of the chain).
    VertexVertex,
    /// One endpoint is a vertex in this cell; the other is a wall
    /// crossing (a half-edge).
    VertexWall,
    /// Neither endpoint is in this cell; the edge cuts across a corner
    /// (both ends are wall crossings).
    WallWall,
}

/// Classify a relative edge `(a, b)` by how many of its endpoints lie in
/// the base cell `(0,0)`.
fn frag_shape<ZZ: IsRing>(a: &ZZ, b: &ZZ) -> FragShape {
    let a_in = cell_of(a) == (0, 0);
    let b_in = cell_of(b) == (0, 0);
    match (a_in, b_in) {
        (true, true) => FragShape::VertexVertex,
        (true, false) | (false, true) => FragShape::VertexWall,
        (false, false) => FragShape::WallWall,
    }
}

/// For a diagonal unit edge from `p` (in cell `(0,0)`, direction
/// `edge_vec`) to the diagonal neighbour cell `(dx, dy)` (`dx, dy` both
/// `+-1`), the single middle cell it cuts through -- `(dx, 0)` or
/// `(0, dy)` -- or `None` if it passes exactly through the shared grid
/// vertex (touching only the two end cells).
///
/// Which corner is decided by whether the edge crosses the `u`-family
/// wall or the `v`-family wall first, in exact ring arithmetic: with
/// `g2 = dx*u + dy*v` (twice the shared corner) and `w = g2 - 2p`,
/// `t_u < t_v` iff `wedge(w, edge_vec) * sign(dx*dy) * sign(u wedge v) <
/// 0`. On a `HasZZ4` square (`u,v = 1,i`, `det = 1`) this is the classic
/// two-cell decision; the `sign(det)` factor makes it correct on any
/// (possibly obtuse) cell.
fn diagonal_corner<ZZ: IsRing>(p: &ZZ, edge_vec: &ZZ, dx: i64, dy: i64) -> Option<(i64, i64)> {
    let two = ZZ::one() + ZZ::one();
    let (u, v) = cell_basis::<ZZ>();
    let g2 = ZZ::from(dx) * u + ZZ::from(dy) * v; // 2 * the corner between the cells
    let w = g2 - two * *p;
    let dsign = wedge_sign(&u, &v); // sign of the cell's signed area
    let s = wedge_sign(&w, edge_vec) * if dx * dy > 0 { 1 } else { -1 } * dsign;
    match s.cmp(&0) {
        std::cmp::Ordering::Less => Some((dx, 0)),
        std::cmp::Ordering::Greater => Some((0, dy)),
        std::cmp::Ordering::Equal => None,
    }
}

/// The cell offsets (relative to the start vertex's cell) that the unit
/// edge from `p` in direction `edge_vec`, landing in cell `(dx, dy)`,
/// passes through: 1 cell (internal), 2 (one wall), or 3 (a corner cut,
/// with [`diagonal_corner`] choosing the single middle cell).
///
/// A unit edge spans **at most one cell per family** for every ring. With
/// the cell basis `{1, v}` where `v` is the unit direction closest to a
/// quarter turn, the unit edge's coordinate in each basis direction is
/// `sin(angle to the other basis vector) / sin(angle between the basis
/// vectors)`, and the denominator is the maximum the numerator can reach
/// (that is exactly why `v` is chosen closest to 90 degrees) -- so every
/// coordinate is `<= 1` in magnitude and `|dx|, |dy| <= 1`. The `assert`
/// pins that invariant; it is offline (build only) so it costs nothing in
/// the walk, and it turns any future basis regression into a loud failure
/// rather than a silently missed cell. (See the `occupied_offsets_covers_
/// every_swept_cell` test for the empirical confirmation.)
pub(crate) fn occupied_offsets<ZZ: IsRing>(
    p: &ZZ,
    edge_vec: &ZZ,
    (dx, dy): (i64, i64),
) -> Vec<(i64, i64)> {
    assert!(
        dx.abs() <= 1 && dy.abs() <= 1,
        "unit edge spans >1 cell (dx={dx}, dy={dy}): cell basis is not near-orthogonal, \
         so the 3-cell decomposition is unsound -- restore a superset fallback"
    );
    if dx == 0 && dy == 0 {
        vec![(0, 0)] // fully internal
    } else if dx == 0 || dy == 0 {
        vec![(0, 0), (dx, dy)] // one wall crossing
    } else {
        match diagonal_corner(p, edge_vec, dx, dy) {
            Some(corner) => vec![(0, 0), corner, (dx, dy)],
            None => vec![(0, 0), (dx, dy)],
        }
    }
}

/// The finite fragment alphabet plus the conflict relation, derived from
/// a [`StateAlphabet`]. See the module docs.
#[derive(Clone, Debug)]
pub struct FragmentAlphabet<ZZ> {
    /// Distinct relative edges, indexed by [`FragId`].
    edges: Vec<(ZZ, ZZ)>,
    /// Shape of each fragment.
    shape: Vec<FragShape>,
    /// `emit[s][d]` = the fragments of the edge (state `s`, direction
    /// `d`). Empty when the step leaves the radius ball.
    emit: Vec<Vec<Vec<Placement>>>,
    /// Symmetric conflict matrix, `n * n` row-major.
    conflict: Vec<bool>,
    /// `|F|`.
    n: usize,
    turn: usize,
}

impl<ZZ: IsRing> FragmentAlphabet<ZZ> {
    /// Build the fragment alphabet and conflict table over a state
    /// alphabet: decompose every in-ball edge into per-cell fragments,
    /// intern the distinct relative edges, then fill the pairwise
    /// conflict matrix with [`intersect`].
    pub fn build(states: &StateAlphabet<ZZ>) -> Self {
        let turn = states.turn();
        let mut edges: Vec<(ZZ, ZZ)> = Vec::new();
        let mut shape: Vec<FragShape> = Vec::new();
        let mut index: HashMap<(ZZ, ZZ), FragId> = HashMap::new();
        let mut emit: Vec<Vec<Vec<Placement>>> = vec![vec![Vec::new(); turn]; states.len()];

        for s in states.states() {
            let p = states.rep(s);
            for (d, cell) in emit[s as usize].iter_mut().enumerate() {
                let Some((_, delta)) = states.step(s, d) else {
                    continue; // step leaves the ball -> unusable edge
                };
                let u = <ZZ as Units>::unit(d as i8);
                let q = p + u;
                for off in occupied_offsets(&p, &u, delta) {
                    let ov: ZZ = cell_anchor(off);
                    let rel = (p - ov, q - ov);
                    let fid = *index.entry(rel).or_insert_with(|| {
                        let id = edges.len() as FragId;
                        edges.push(rel);
                        shape.push(frag_shape(&rel.0, &rel.1));
                        id
                    });
                    cell.push((off, fid));
                }
            }
        }

        let n = edges.len();
        let mut conflict = vec![false; n * n];
        for i in 0..n {
            for j in (i + 1)..n {
                if intersect(&edges[i], &edges[j]) {
                    conflict[i * n + j] = true;
                    conflict[j * n + i] = true;
                }
            }
        }

        Self {
            edges,
            shape,
            emit,
            conflict,
            n,
            turn,
        }
    }

    /// Number of distinct fragments `|F|`.
    pub fn len(&self) -> usize {
        self.n
    }

    /// Whether the alphabet is empty.
    pub fn is_empty(&self) -> bool {
        self.n == 0
    }

    /// Number of unit-step directions.
    pub fn turn(&self) -> usize {
        self.turn
    }

    /// The relative edge of fragment `f`.
    pub fn edge(&self, f: FragId) -> (ZZ, ZZ) {
        self.edges[f as usize]
    }

    /// The shape of fragment `f`.
    pub fn shape(&self, f: FragId) -> FragShape {
        self.shape[f as usize]
    }

    /// Whether fragments `a` and `b` conflict (their edges cross/touch
    /// improperly when placed in the same cell).
    pub fn conflict(&self, a: FragId, b: FragId) -> bool {
        self.conflict[a as usize * self.n + b as usize]
    }

    /// The fragments emitted by the edge (state `s`, direction `d`),
    /// each a `(cell offset relative to the start vertex's cell,
    /// fragment id)`.
    pub fn emit(&self, s: StateId, d: usize) -> &[Placement] {
        &self.emit[s as usize][d]
    }

    /// Count of conflicting unordered fragment pairs `|X|`.
    pub fn num_conflicts(&self) -> usize {
        self.conflict.iter().filter(|&&c| c).count() / 2
    }

    /// Count of fragments of each shape: `(vertex-vertex, vertex-wall,
    /// wall-wall)`.
    pub fn shape_counts(&self) -> (usize, usize, usize) {
        let mut c = (0, 0, 0);
        for &sh in &self.shape {
            match sh {
                FragShape::VertexVertex => c.0 += 1,
                FragShape::VertexWall => c.1 += 1,
                FragShape::WallWall => c.2 += 1,
            }
        }
        c
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::cyclotomic::{ZZ6, ZZ10, ZZ12};

    fn build(radius: u32) -> (StateAlphabet<ZZ12>, FragmentAlphabet<ZZ12>) {
        let states = StateAlphabet::<ZZ12>::build(radius);
        let frags = FragmentAlphabet::build(&states);
        (states, frags)
    }

    /// Directly validate the soundness invariant for a ring: every cell a
    /// unit alphabet edge sweeps through is listed by `occupied_offsets`.
    /// Each edge is densely float-sampled; for every sample clearly inside
    /// a cell (not near a wall, where either neighbour is covered anyway),
    /// the sample's cell -- computed independently, by inverting the
    /// `{u,v}` basis in floats -- must appear in `occupied_offsets`. If a
    /// swept cell were ever missed, a crossing there could go undetected.
    /// Returns the max `|dx|, |dy|` any unit edge reaches; this must stay
    /// `<= 1` (the exact corner decomposition `occupied_offsets` relies on
    /// -- and hard-asserts -- that a unit edge spans at most one cell per
    /// basis family; a span of 2 would now panic, not fall back).
    fn coverage_and_span<ZZ: IsRing>(radius: u32) -> (i64, i64) {
        let st = StateAlphabet::<ZZ>::build(radius);
        let (u, v) = cell_basis::<ZZ>();
        let (ux, uy) = u.xy();
        let (vx, vy) = v.xy();
        let det = ux * vy - uy * vx; // u x v, nonzero for a real basis
        let eps = 1e-6;
        let (mut mdx, mut mdy) = (0i64, 0i64);
        for s in st.states() {
            let (px, py) = st.rep(s).xy();
            for d in 0..st.turn() {
                let Some((_, (dx, dy))) = st.step(s, d) else {
                    continue;
                };
                mdx = mdx.max(dx.abs());
                mdy = mdy.max(dy.abs());
                let e = <ZZ as Units>::unit(d as i8);
                let (ex, ey) = e.xy();
                let listed: std::collections::HashSet<(i64, i64)> =
                    occupied_offsets(&st.rep(s), &e, (dx, dy))
                        .into_iter()
                        .collect();
                let samples = 2048;
                for i in 1..samples {
                    let t = i as f64 / samples as f64;
                    let (zx, zy) = (px + t * ex, py + t * ey);
                    let a = (zx * vy - zy * vx) / det; // z's u-coordinate
                    let b = (ux * zy - uy * zx) / det; // z's v-coordinate
                    if (a - a.round()).abs() > 0.5 - eps || (b - b.round()).abs() > 0.5 - eps {
                        continue; // near a wall -> ambiguous, both sides covered
                    }
                    let cell = (a.round() as i64, b.round() as i64);
                    assert!(
                        listed.contains(&cell),
                        "turn={} s={s} d={d} delta=({dx},{dy}): swept cell {cell:?} \
                         at t={t:.4} not covered by {listed:?}",
                        ZZ::turn()
                    );
                }
            }
        }
        (mdx, mdy)
    }

    #[test]
    fn occupied_offsets_covers_every_swept_cell() {
        for (name, (mdx, mdy)) in [
            ("ZZ6", coverage_and_span::<ZZ6>(8)),
            ("ZZ10", coverage_and_span::<ZZ10>(8)),
            ("ZZ12", coverage_and_span::<ZZ12>(8)),
        ] {
            eprintln!("{name}: coverage OK; max unit-edge span |dx|<={mdx} |dy|<={mdy}");
        }
    }

    #[test]
    #[ignore = "scaling probe; run with --ignored --nocapture"]
    fn scaling_probe() {
        eprintln!("-- state alphabet (cheap) --");
        for r in [8u32, 16, 24, 32, 40, 50, 60] {
            let st = StateAlphabet::<ZZ12>::build(r);
            eprintln!("  R={r:>2} (perimeter n={:>3}): states={}", 2 * r, st.len());
        }
        eprintln!("-- fragment alphabet + conflicts (heavy: O(|F|^2)) --");
        for r in [8u32, 12, 16, 20] {
            let (st, fr) = build(r);
            eprintln!(
                "  R={r:>2} (n={:>3}): states={} |F|={} |X|={}",
                2 * r,
                st.len(),
                fr.len(),
                fr.num_conflicts()
            );
        }
    }

    #[test]
    fn all_three_shapes_present() {
        // Corner cuts (WallWall) and diagonal-fit whole edges
        // (VertexVertex) both occur in ZZ12, alongside the common
        // half-edges (VertexWall).
        let (_, frags) = build(8);
        let (vv, vw, ww) = frags.shape_counts();
        assert!(vv > 0, "expected VertexVertex fragments");
        assert!(vw > 0, "expected VertexWall fragments");
        assert!(ww > 0, "expected WallWall fragments");
    }

    #[test]
    fn emit_reconstructs_the_edge() {
        // Translating each emitted fragment back by its cell offset must
        // recover the original absolute edge (p, p+unit(d)).
        let (states, frags) = build(6);
        let turn = states.turn();
        for s in states.states() {
            let p = states.rep(s);
            for d in 0..turn {
                if states.step(s, d).is_none() {
                    assert!(frags.emit(s, d).is_empty());
                    continue;
                }
                let q = p + <ZZ12 as Units>::unit(d as i8);
                for &(off, fid) in frags.emit(s, d) {
                    let ov = ZZ12::from(off);
                    let (a, b) = frags.edge(fid);
                    assert_eq!((a + ov, b + ov), (p, q), "s={s} d={d} off={off:?}");
                }
            }
        }
    }

    #[test]
    fn conflict_symmetric_and_irreflexive() {
        let (_, frags) = build(6);
        for i in 0..frags.len() as FragId {
            assert!(!frags.conflict(i, i), "self-conflict at {i}");
            for j in 0..frags.len() as FragId {
                assert_eq!(frags.conflict(i, j), frags.conflict(j, i), "asym {i},{j}");
            }
        }
    }

    #[test]
    fn report_sizes() {
        // Informational: alphabet + conflict-table sizes at this radius.
        let (states, frags) = build(8);
        let (vv, vw, ww) = frags.shape_counts();
        eprintln!(
            "ZZ12 r=8: states={} frags={} conflicts={} shapes(vv/vw/ww)={}/{}/{}",
            states.len(),
            frags.len(),
            frags.num_conflicts(),
            vv,
            vw,
            ww
        );
        assert_eq!(states.len(), 145);
        assert!(!frags.is_empty());
    }
}