tilezz 0.2.0

//! The finite state alphabet and the unit-step transition table.
//!
//! A **state** is a lattice vertex folded into the origin-centered base
//! cell `[-1/2, 1/2)^2` (via [`crate::cyclotomic::geometry::point_mod_rect`]). Two absolute vertices
//! that share a state differ by an integer-lattice translation. Because
//! both the fold and a unit step are translation invariant, the map
//!
//! ```text
//!   (state, direction) -> (next state, cell delta)
//! ```
//!
//! does not depend on which absolute cell you are in -- it is a fixed
//! finite table, the transfer-matrix state graph of the tiling. `cell
//! delta` is the integer-lattice hop (in unit cells) that the step
//! takes, so an absolute walk is reconstructed by accumulating deltas.
//!
//! States are those reachable from the origin within `radius` unit
//! steps. A closed rat of perimeter `k` has every vertex within
//! `floor(k/2)` graph-steps of the origin, so `radius = floor(k/2)`
//! covers all closed walks of perimeter `<= k`; an open walk of length
//! `L` needs `radius = L`.

use std::collections::HashMap;

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

/// Index of a state within a [`StateAlphabet`].
pub type StateId = u32;

/// A unit-step transition: the next state and the integer-lattice cell
/// hop `(dx, dy)`, or `None` when the step leaves the radius ball.
pub type Transition = Option<(StateId, (i64, i64))>;

/// Two ring elements spanning the plane: the basis of the fundamental
/// cell. `1` and the unit direction closest to 90 degrees, so on
/// `HasZZ4` rings this is the axis-aligned unit square `{1, i}` and on the
/// others (ZZ5, ZZ6, ZZ10, ...) a rhombus. Any spanning pair is correct;
/// this one keeps the cell short so a unit edge crosses O(1) cells.
pub(crate) fn cell_basis<ZZ: IsRing>() -> (ZZ, ZZ) {
    let k = (ZZ::turn() + 2) / 4; // nearest unit direction to a quarter turn
    (ZZ::one(), <ZZ as Units>::unit(k))
}

/// Fold `p` into the origin-centered fundamental cell of the
/// [`cell_basis`] lattice: return its integer cell `(k, m)` (in units of
/// the basis vectors) and the normalized residual `p - k*u - m*v`, a ring
/// element inside the cell. Exact -- each coordinate is rounded to
/// `[-1/2, 1/2)` by a sequence of `wedge_sign` tests, no floats. Offline
/// only (drives the alphabet build); the walk reads the transition table.
pub(crate) fn fold<ZZ: IsRing>(p: &ZZ) -> ((i64, i64), ZZ) {
    let (u, v) = cell_basis::<ZZ>();
    let two = ZZ::one() + ZZ::one();
    let duv = wedge_sign(&u, &v); // signed cell area; nonzero
    let mut q = *p;
    // Reduce the u-coordinate into [-1/2, 1/2) (half-open low).
    let mut k = 0i64;
    loop {
        if wedge_sign(&(two * q - u), &v) * duv >= 0 {
            q = q - u;
            k += 1;
        } else if wedge_sign(&(two * q + u), &v) * duv < 0 {
            q = q + u;
            k -= 1;
        } else {
            break;
        }
    }
    // Reduce the v-coordinate likewise (independent: shifting by u leaves
    // the v-coordinate fixed and vice versa).
    let mut m = 0i64;
    loop {
        if wedge_sign(&u, &(two * q - v)) * duv >= 0 {
            q = q - v;
            m += 1;
        } else if wedge_sign(&u, &(two * q + v)) * duv < 0 {
            q = q + v;
            m -= 1;
        } else {
            break;
        }
    }
    ((k, m), q)
}

/// The normalized residual of `p` in the base cell.
pub(crate) fn normalize<ZZ: IsRing>(p: &ZZ) -> ZZ {
    fold(p).1
}

/// The integer cell owner of `p` in the [`cell_basis`] grid.
pub(crate) fn cell_of<ZZ: IsRing>(p: &ZZ) -> (i64, i64) {
    fold(p).0
}

/// The lattice point anchoring cell `(x, y)`: `x*u + y*v` in the
/// [`cell_basis`]. Fragments are stored relative to their cell's anchor,
/// so translation-equivalent edges dedupe to one fragment and a
/// conflict lookup reproduces the true absolute crossing.
pub(crate) fn cell_anchor<ZZ: IsRing>((x, y): (i64, i64)) -> ZZ {
    let (u, v) = cell_basis::<ZZ>();
    ZZ::from(x) * u + ZZ::from(y) * v
}

/// The finite alphabet of normalized vertex positions plus the
/// position-independent unit-step transitions between them.
///
/// See the module docs for the meaning of a state and a transition.
#[derive(Clone, Debug)]
pub struct StateAlphabet<ZZ> {
    /// Normalized representative of each state, indexed by [`StateId`].
    reps: Vec<ZZ>,
    /// Inverse of `reps`: normalized representative -> its id.
    index: HashMap<ZZ, StateId>,
    /// `trans[s][d] = Some((next, (dx, dy)))` for the unit step in
    /// direction `d` out of state `s`, or `None` when that step leaves
    /// the radius ball (the neighbour is farther than `radius` from the
    /// origin and so is not part of the alphabet).
    trans: Vec<Vec<Transition>>,
    /// BFS distance (in unit steps) of each state from the origin.
    dist: Vec<u32>,
    /// The radius the alphabet was built to.
    radius: u32,
}

impl<ZZ: IsRing> StateAlphabet<ZZ> {
    /// Build the alphabet by a shell-by-shell BFS from the origin,
    /// folding every reached lattice point into the base cell and
    /// stopping at `radius` unit steps.
    ///
    /// The four cardinal steps from the origin land exactly one period
    /// away and fold back onto the origin, so they add no state -- only
    /// the off-axis directions grow the alphabet (for `ZZ12` the shells
    /// grow by `4*i` states each).
    pub fn build(radius: u32) -> Self {
        let turn = ZZ::turn() as usize;
        let origin = normalize(&ZZ::zero()); // = zero, but fold for uniformity

        let mut reps: Vec<ZZ> = vec![origin];
        let mut index: HashMap<ZZ, StateId> = HashMap::new();
        index.insert(origin, 0);
        let mut dist: Vec<u32> = vec![0];

        // Shell-by-shell so `dist` is the true graph distance: every
        // state at distance d is discovered while expanding distance
        // d-1, and all of shell d-1 is expanded before shell d.
        let mut frontier: Vec<StateId> = vec![0];
        for d in 1..=radius {
            let mut next_frontier: Vec<StateId> = Vec::new();
            for &s in &frontier {
                let rep = reps[s as usize];
                for k in 0..turn {
                    let nrep = normalize(&(rep + <ZZ as Units>::unit(k as i8)));
                    if let std::collections::hash_map::Entry::Vacant(e) = index.entry(nrep) {
                        let id = reps.len() as StateId;
                        e.insert(id);
                        reps.push(nrep);
                        dist.push(d);
                        next_frontier.push(id);
                    }
                }
            }
            frontier = next_frontier;
        }

        // Fill the transition table for every discovered state. A step
        // whose folded target was never discovered lies outside the
        // radius ball -> None.
        let mut trans: Vec<Vec<Transition>> = vec![vec![None; turn]; reps.len()];
        for (s, row) in trans.iter_mut().enumerate() {
            let rep = reps[s];
            for (k, cell) in row.iter_mut().enumerate() {
                let stepped = rep + <ZZ as Units>::unit(k as i8);
                let (delta, nrep) = fold(&stepped);
                if let Some(&nid) = index.get(&nrep) {
                    *cell = Some((nid, delta));
                }
            }
        }

        Self {
            reps,
            index,
            trans,
            dist,
            radius,
        }
    }

    /// Number of states in the alphabet.
    pub fn len(&self) -> usize {
        self.reps.len()
    }

    /// Whether the alphabet is empty (never, in practice -- the origin
    /// is always present).
    pub fn is_empty(&self) -> bool {
        self.reps.is_empty()
    }

    /// The radius (in unit steps) this alphabet was built to.
    pub fn radius(&self) -> u32 {
        self.radius
    }

    /// Number of unit-step directions (`ZZ::turn()`).
    pub fn turn(&self) -> usize {
        self.trans.first().map_or(0, Vec::len)
    }

    /// The origin state (normalized `(0, 0)`).
    pub fn origin(&self) -> StateId {
        0
    }

    /// Normalized representative of state `s`.
    pub fn rep(&self, s: StateId) -> ZZ {
        self.reps[s as usize]
    }

    /// BFS distance of state `s` from the origin, in unit steps.
    pub fn dist(&self, s: StateId) -> u32 {
        self.dist[s as usize]
    }

    /// State whose representative is `normalized`, if in the alphabet.
    /// `normalized` must already lie in the base cell.
    pub fn state_of(&self, normalized: &ZZ) -> Option<StateId> {
        self.index.get(normalized).copied()
    }

    /// The unit step in direction `d` out of state `s`: the next state
    /// and the integer-lattice cell hop `(dx, dy)`, or `None` if the
    /// step leaves the radius ball.
    pub fn step(&self, s: StateId, d: usize) -> Transition {
        self.trans[s as usize][d]
    }

    /// Iterator over all states as ids.
    pub fn states(&self) -> impl Iterator<Item = StateId> {
        0..self.reps.len() as StateId
    }
}

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

    /// Every representative lies in the half-open base cell
    /// `[-1/2, 1/2)^2`, checked exactly via the doubled sign tests
    /// (`2*q +- 1`), never f64.
    fn assert_in_base_cell(q: &ZZ12) {
        let two = ZZ12::one() + ZZ12::one();
        let i = <ZZ12 as OneImag>::one_i();
        assert!((two * *q - ZZ12::one()).re_sign() < 0, "re < 1/2");
        assert!((two * *q + ZZ12::one()).re_sign() >= 0, "re >= -1/2");
        assert!((two * *q - i).im_sign() < 0, "im < 1/2");
        assert!((two * *q + i).im_sign() >= 0, "im >= -1/2");
    }

    #[test]
    fn zz12_shell_counts() {
        // Centered ZZ12 BFS grows by exactly 4*i states per shell, so
        // radius 8 holds 1 + 4*(1+..+8) = 145 states.
        let alph = StateAlphabet::<ZZ12>::build(8);
        let mut per_shell = [0usize; 9];
        for s in alph.states() {
            per_shell[alph.dist(s) as usize] += 1;
        }
        assert_eq!(per_shell[0], 1, "origin");
        for (i, &count) in per_shell.iter().enumerate().skip(1) {
            assert_eq!(count, 4 * i, "shell {i}");
        }
        assert_eq!(alph.len(), 145);
    }

    #[test]
    fn cardinals_fold_to_origin() {
        let alph = StateAlphabet::<ZZ12>::build(4);
        let o = alph.origin();
        // ZZ12 cardinals: E=0, N=3, W=6, S=9. Each folds back to the
        // origin state, carrying the corresponding unit cell hop.
        let expect = [(0usize, (1, 0)), (3, (0, 1)), (6, (-1, 0)), (9, (0, -1))];
        for (d, delta) in expect {
            assert_eq!(alph.step(o, d), Some((o, delta)), "cardinal dir {d}");
        }
    }

    #[test]
    fn states_lie_in_base_cell() {
        let alph = StateAlphabet::<ZZ12>::build(6);
        for s in alph.states() {
            assert_in_base_cell(&alph.rep(s));
        }
    }

    #[test]
    fn transitions_round_trip() {
        // Stepping out of `s` by `d` and back by the opposite direction
        // (`d + turn/2`) must return to `s` with the negated cell hop.
        let alph = StateAlphabet::<ZZ12>::build(6);
        let turn = alph.turn();
        let hturn = turn / 2;
        for s in alph.states() {
            for d in 0..turn {
                if let Some((s2, (dx, dy))) = alph.step(s, d) {
                    let back = alph.step(s2, (d + hturn) % turn);
                    assert_eq!(
                        back,
                        Some((s, (-dx, -dy))),
                        "round trip s={s} d={d} -> s2={s2}"
                    );
                }
            }
        }
    }

    #[test]
    fn state_of_round_trips_reps() {
        let alph = StateAlphabet::<ZZ12>::build(5);
        for s in alph.states() {
            assert_eq!(alph.state_of(&alph.rep(s)), Some(s));
        }
    }
}