tilezz 0.2.0

//! Edge-gluing isohedral search (p3/p4/p6 and beyond).
//!
//! Conway certifies translation + half-turn (p1/p2). The remaining periodic
//! tilings in our single-chirality scope use 3/4/6-fold rotation centres.
//! Rather than hand-code those isohedral criteria, we search the *combinatorial*
//! gluing directly: in an edge-to-edge isohedral tiling every tile glues the
//! same way, so the gluing is an involution `sigma` on the tile's edges (a
//! fixed point = a 2-fold centre at that edge's midpoint; a 2-cycle (e,f) = the
//! neighbour across e presents edge f). The gluing isometries `g_e` are then
//! forced, and they generate the tiling group. We build the orbit and screen it
//! with the center-only `verify_tiling` (a fast pre-filter). Acceptance is sound
//! only via the minted certificate: `mint` gates every cert on
//! `PeriodicCert::verify`, which re-checks exact surroundedness at one tile PER
//! TRANSLATION CLASS (`all_exactly_surrounded`) plus exact multiplicity gates --
//! the k>1-sound check these 3/4/6-orientation cells need, since `verify_tiling`
//! alone (one center) is k=1-sound only.

use crate::classify::lattice::lattice_from_orbit;
use crate::classify::tiling::{Tiling, verify_tiling};
use crate::cyclotomic::IsRing;
use crate::geom::iso::{Iso, build_orbit, cryst_order, gluing_iso};
use crate::geom::patch::boundary_vertices;

/// Visit every involution of `0..n` (perfect matchings allowing fixed
/// points) as a `partner` array (`sigma[e]`), WITHOUT materializing the set:
/// there are ~2.4M involutions at n = 14 and ~46M at n = 16, so collecting
/// them first (the previous shape) was a multi-GB per-tile allocation before
/// any cap could bite. `f` returns `false` to stop the enumeration early
/// (the caller's build cap / first hit).
fn for_each_involution(n: usize, f: &mut impl FnMut(&[usize]) -> bool) {
    fn go(i: usize, n: usize, cur: &mut Vec<usize>, f: &mut impl FnMut(&[usize]) -> bool) -> bool {
        if i == n {
            return f(cur);
        }
        if cur[i] != usize::MAX {
            return go(i + 1, n, cur, f);
        }
        cur[i] = i; // fixed point: 2-fold centre at edge i's midpoint
        let cont = go(i + 1, n, cur, f);
        cur[i] = usize::MAX;
        if !cont {
            return false;
        }
        for j in (i + 1)..n {
            if cur[j] == usize::MAX {
                cur[i] = j;
                cur[j] = i;
                let cont = go(i + 1, n, cur, f);
                cur[i] = usize::MAX;
                cur[j] = usize::MAX;
                if !cont {
                    return false;
                }
            }
        }
        true
    }
    let mut cur = vec![usize::MAX; n];
    go(0, n, &mut cur, f);
}

/// Search for an isohedral (single-chirality) tiling of `seq` by trying every
/// edge-gluing involution whose forced isometries are all crystallographic,
/// building the orbit, and accepting the first the exact `verify_tiling`
/// confirms. `max_builds` caps how many candidate orbits are constructed
/// (exhausting it returns `None` = undecided, never a false accept).
pub fn isohedral_tiling<T: IsRing>(
    seq: &[i8],
    radius: f64,
    cap: usize,
    max_builds: usize,
) -> Option<Tiling<T>> {
    let verts = boundary_vertices::<T>(seq);
    let n = verts.len();
    // Precompute the forced gluing isometry and its crystallographic order
    // for every ordered edge pair.
    let mut g = vec![vec![None::<Iso<T>>; n]; n];
    let mut ok = vec![vec![false; n]; n];
    for e in 0..n {
        for f in 0..n {
            if let Some(iso) = gluing_iso(&verts, e, f)
                && cryst_order::<T>(iso.rot).is_some()
            {
                g[e][f] = Some(iso);
                ok[e][f] = true;
            }
        }
    }

    let mut builds = 0usize;
    let mut found: Option<Tiling<T>> = None;
    for_each_involution(n, &mut |sigma| {
        if !(0..n).all(|e| ok[e][sigma[e]]) {
            return true; // some edge gluing is non-crystallographic: next
        }
        if builds >= max_builds {
            return false; // build cap exhausted: stop enumerating
        }
        builds += 1;
        let mut gens: Vec<Iso<T>> = (0..n).map(|e| g[e][sigma[e]].unwrap()).collect();
        let invs: Vec<Iso<T>> = gens.iter().map(|x| x.inv()).collect();
        gens.extend(invs); // ensure the BFS reaches the whole group
        let placements = build_orbit(&verts, &gens, radius, cap);
        if placements.len() >= cap {
            return true; // hit the cap -> likely non-discrete group; reject
        }
        let lattice = lattice_from_orbit(&placements).unwrap_or((T::zero(), T::zero()));
        let tiling = Tiling {
            verts: verts.clone(),
            seq: seq.to_vec(),
            lattice,
            placements,
        };
        if verify_tiling(&tiling).ok() {
            found = Some(tiling);
            return false; // first verified tiling wins
        }
        true
    });
    found
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::cyclotomic::ZZ12;
    use crate::geom::rat::Rat;
    use crate::geom::tiles;

    /// The isohedral edge-gluing search must re-find tilings for known
    /// tilers (it should subsume Conway), each gated by the exact verifier.
    #[test]
    fn isohedral_search_finds_known_tilers() {
        let square = Rat::from_snake_trusted(&tiles::square::<ZZ12>());
        let triangle = Rat::from_snake_trusted(&tiles::triangle::<ZZ12>());
        let hexagon = Rat::from_snake_trusted(&tiles::hexagon::<ZZ12>());
        for (name, rat) in [
            ("square", &square),
            ("triangle", &triangle),
            ("hexagon", &hexagon),
        ] {
            let p = rat.seq().len() as f64;
            let t = isohedral_tiling::<ZZ12>(rat.seq(), 2.6 * p, 1200, 500);
            assert!(t.is_some(), "{name} must yield a verified isohedral tiling");
            eprintln!("{name}: {} tiles", t.unwrap().placements.len());
        }
    }
}