tilezz 0.2.0

//! Torus cover -- a sound (but *not* complete) periodic-acceptance stage.
//!
//! This certifies periodicity by folding a grown patch onto the flat torus and
//! exact-checking. It is **sound** (a "yes" is a verified tiling) but **not
//! exhaustive**: the candidate lattices are read off a corona patch, so if the
//! patch jams before reaching lattice scale, a real k-tile tiling is missed and
//! the answer is an inconclusive `None` -- never a proof of non-periodicity.
//! (A genuinely complete-for-fixed-k test enumerates every connected k-cluster
//! by edge-gluing and Beauquier-Nivat-tests each -- but that is exponential in k;
//! this is the cheap heuristic that reaches large k, e.g. tile0's 8-tile domain,
//! when exhaustive cluster enumeration is infeasible.)
//!
//! # The geometric picture
//!
//! A tile tiles the plane periodically exactly when some rank-2 lattice
//! `L = <v1, v2>` is a symmetry of a tiling: the plane folds onto the flat
//! torus `R^2 / L` (a parallelogram with opposite sides identified), and a
//! finite **fundamental domain** of `k` tile-copies covers that torus once,
//! with no gap and no overlap. Unfold by the lattice and the whole plane is
//! tiled. So "tiles periodically with a domain of at most `K` tiles" is
//! *characterized* by: for each `k <= K`, is there a lattice `L` of covolume
//! `k * area(tile)` and a set of `k` placements (rotations only, our
//! single-chirality scope) that exact-cover `R^2 / L`? (We only *search* this
//! space via patch-derived lattices below -- we do not enumerate it
//! exhaustively, so a negative answer is not a proof.)
//!
//! This is the acceptance counterpart to the finite-Heesch reject: a Heesch
//! number proves a tile *cannot* tile; a torus cover proves it *does* (and
//! periodically, which disqualifies it as an aperiodic monotile -- the
//! spectre family tiles only aperiodically).
//!
//! # Why the lattice candidates come from a grown patch (and why that is a
//! *speed* choice, not a necessity)
//!
//! Exhaustive fixed-k enumeration is in fact **finite**: tiles have area, so by
//! area-packing (and the cyclotomic spacing bound -- two non-overlapping copies
//! that are geometrically close must be combinatorially far apart) only finitely
//! many non-overlapping placements fit in the bounded region a k-tile domain
//! occupies. So the candidate fundamental domains -- the connected k-clusters --
//! are a finite (though *exponential in k*) set, and BN-testing each is the
//! complete-for-fixed-k acceptance. The density of
//! `Z[zeta12]` as an abstract point set is irrelevant here: we never enumerate
//! abstract ring points, only non-overlapping placements, which packing bounds.
//!
//! This module takes the cheaper, **incomplete** route: grow ONE patch and read
//! candidate lattices off it (two equally-oriented tiles differ by a lattice
//! vector, so once corona growth reaches lattice scale the true `v1, v2` appear
//! among the same-orientation displacements). That is O(patch) instead of the
//! exponential cluster enumeration, and it reached e.g. tile0's 8-tile domain --
//! but if the patch jams first, a real tiling is missed (a `None` is not a
//! proof). For each candidate lattice we fold the patch onto the torus and read
//! off the `k` domain classes.
//!
//! # Soundness
//!
//! The accept is gated by two complementary EXACT checks -- the whole
//! acceptance chain is integer/ring arithmetic, floats never decide:
//!
//! - [`gold_check`] (per-class angle sums to a full turn + every edge shared
//!   by exactly two, at shared ring coordinates) proves the configuration
//!   `domain x L` is a complete flat covering of the plane of CONSTANT
//!   integer multiplicity `m >= 1`. It cannot by itself distinguish `m = 1`
//!   from a clean `m`-sheet cover whose sheets share no vertex or edge
//!   coordinates (a transversally overlapping tile contributes nothing to
//!   another sheet's angle/edge maps).
//! - MULTIPLICITY 1 is forced by the exact ring identity
//!   `covol == domain.len() * area`
//!   ([`covol_eq_m_areas`]): cross products
//!   and shoelace areas are `Im`-parts of ring products (`z - conj(z) =
//!   2i Im(z)` stays in the ring), so the identity is an integer-coefficient
//!   equality that an `m`-sheet cover misses by an exact factor of `m`.
//!
//! Everything float-guided (candidate ranking around `COVOL_INT_EPS`,
//! lattice reduction, coverage-block sizing) only proposes or sizes; a wrong
//! value yields a miss, never an accept. A miss proves nothing (the grower
//! may not have reached lattice scale) -- a tile that fails here is left a
//! candidate, never wrongly rejected.

// Fx hashers (fixed seed) rather than std's random-seeded HashMap: the cover
// detection iterates these maps, so a random per-process seed made the chosen
// cover -- and thus the whole cert -- vary run to run. Fx makes iteration order
// deterministic (the same discipline `patch.rs` relies on).
use rustc_hash::FxHashMap as HashMap;

use crate::cyclotomic::IsRing;
use crate::cyclotomic::geometry::{cmp_xy, covol_eq_m_areas};
use crate::geom::patch::boundary_vertices;

use super::grow::grow_coronas;
use super::lattice::{
    basis_inverse, gauss_reduce, lattice_classes, lay_lattice_block, signature_groups,
};
use super::tiling::{AREA_EPS, all_exactly_surrounded};
use crate::cyclotomic::geometry::float::{area_f, cross_f, norm_f};
use crate::geom::iso::Iso;

/// A confirmed periodic-tiling certificate: the tile tiles `R^2` invariant
/// under the lattice `L = lattice`, with the `k`-tile `domain` as a
/// fundamental domain. Verified by the exact gold check.
#[derive(Debug, Clone)]
pub struct TorusCover<T> {
    /// Number of tiles in the fundamental domain (covolume / tile area).
    pub k: usize,
    /// The two lattice vectors `(v1, v2)`.
    pub lattice: (T, T),
    /// The `k` domain placements (one per torus class).
    pub domain: Vec<Iso<T>>,
}

/// One representative placement per `(orientation, position mod L)` class of
/// the patch -- the candidate fundamental domain. Within each orientation
/// group, anchors that differ by a lattice vector are the same torus class.
///
/// Corona growth lays only a *near*-periodic surrounding, so a few boundary
/// tiles can land in spurious one-off classes. We keep only the **recurring**
/// classes (seen in at least half as many cells as the most-populated class),
/// which is the periodic core; the exact gold check then confirms it. This
/// recurrence filter is what lets a deep but imperfect patch still reveal the
/// true fundamental domain.
fn domain_reps<T: IsRing>(
    groups: &HashMap<Vec<T>, Vec<(T, Iso<T>)>>,
    v1: T,
    v2: T,
    inv: &[[f64; 2]; 2],
) -> Vec<Iso<T>> {
    let classes = lattice_classes(groups, v1, v2, inv);
    let maxc = classes.iter().map(|&(c, _)| c).max().unwrap_or(0);
    let mut domain: Vec<Iso<T>> = classes
        .into_iter()
        .filter(|&(c, _)| c * RECURRENCE_DIVISOR >= maxc)
        .map(|(_, iso)| iso)
        .collect();
    // Deterministic order: `groups` is a HashMap, so its value-iteration order
    // (and hence the discovered class order) is per-process random. Sort the reps
    // by (orientation, position) so the returned domain -- and every cert whose
    // coset labels are read off it -- is reproducible run to run.
    domain.sort_by(|a, b| a.rot.cmp(&b.rot).then_with(|| cmp_xy(&a.shift, &b.shift)));
    domain
}

/// The exact gold check: instantiate a provably-sufficient block of the
/// infinite configuration `S = domain x L` and verify EVERY domain
/// representative is exactly surrounded in it (`all_exactly_surrounded`:
/// every vertex's incident interior angles sum to a full turn, catching both
/// gaps and overlaps, and every edge is shared by exactly two tiles).
///
/// Two ingredients make the block-local check extend to the whole plane:
///
/// - PER-CLASS checking: the lattice maps each translation class to itself,
///   so certifying one representative per class certifies, by `L`-invariance,
///   every tile of `S` -- a single checked tile would leave defects strictly
///   between tiles of the other classes unexamined.
/// - PROVEN COVERAGE: the block must contain every tile of `S` that can touch
///   a representative, else a defect (e.g. a short lattice combination
///   landing a far cell on top of a rep) would sit outside the block and the
///   truncated view could look exact. Every rep tile lies in the origin disk
///   of radius `D`, so a touching `rep + l1*v1 + l2*v2` needs
///   `|l1*v1 + l2*v2| <= 2D`; the perpendicular-component bounds
///   `|l1*v1 + l2*v2| >= |l1| * covol/|v2|` (and symmetrically for `l2`) turn
///   that into exact per-axis reaches. The basis is Gauss-reduced first (same
///   lattice) so the reaches stay small; a block that would still exceed
///   `GOLD_ORBIT_CAP` is rejected outright (fail closed).
///
/// The comparisons here are exact (ring equality, integer angles) and the
/// floats only size the block (oversizing is harmless) -- but note the exact
/// checks alone certify a constant-multiplicity covering, not multiplicity 1;
/// the caller's EXACT multiplicity gate
/// ([`covol_eq_m_areas`]) supplies that
/// final step (see the module-level Soundness section).
pub fn gold_check<T: IsRing>(verts: &[T], seq: &[i8], domain: &[Iso<T>], v1: T, v2: T) -> bool {
    if domain.is_empty() {
        return false;
    }
    let Some((v1, v2)) = gauss_reduce(v1, v2) else {
        return false;
    };
    let d_max = domain
        .iter()
        .flat_map(|iso| verts.iter().map(move |&v| norm_f(&iso.pt(v))))
        .fold(0.0_f64, f64::max);
    let covol = cross_f(&v1, &v2).abs();
    if covol < AREA_EPS {
        return false;
    }
    // Exact touching bounds with float slack; oversizing only costs time.
    let slack = 1.01;
    let reach1 = ((2.0 * d_max * norm_f(&v2) / covol) * slack).ceil() as i64 + 1;
    let reach2 = ((2.0 * d_max * norm_f(&v1) / covol) * slack).ceil() as i64 + 1;
    // Reject absurd reaches before forming the product: a hostile/corrupt cert
    // replayed by --verify can drive covol toward AREA_EPS, making the product
    // overflow i64 (wrapping past the cap check) and the loops run ~1e20
    // iterations. Fail closed instead -- a genuine tiling's reduced basis is
    // orders of magnitude below this.
    if reach1 > 100_000 || reach2 > 100_000 {
        return false;
    }
    if (2 * reach1 + 1) * (2 * reach2 + 1) * (domain.len() as i64) > GOLD_ORBIT_CAP {
        return false;
    }
    let orbit = lay_lattice_block(domain, v1, v2, reach1, reach2);
    all_exactly_surrounded(verts, seq, &orbit, domain)
}

/// Maximum distinct same-orientation displacement vectors retained as lattice
/// candidates (most frequent first -- a true lattice vector recurs across the
/// patch, so the frequent ones are the real candidates).
const MAX_DISP: usize = 160;

/// Placement cap for the gold-check orbit block. The adaptive reaches keep
/// benign cases tiny (tens to a few thousand placements); a pathologically
/// skewed basis that would explode the block is rejected outright instead
/// (fail closed -- a genuine tiling's reduced basis never comes close).
const GOLD_ORBIT_CAP: i64 = 50_000;

/// PROPOSAL filter only: a candidate lattice pair is kept when its covolume
/// is within this of an integer multiple of the tile area (k tiles per
/// cell). Generous -- the exact multiplicity gate (`covol_eq_m_areas`) and
/// the gold check decide; this just prunes hopeless pairs cheaply.
const COVOL_INT_EPS: f64 = 0.3;

/// Candidate pairs with covolume below this fraction of one tile area are
/// degenerate (near-parallel vectors) and skipped outright.
const MIN_COVOL_FRACTION: f64 = 0.5;

/// A torus class is part of the periodic core only if it recurs in at least
/// 1/RECURRENCE_DIVISOR of the cells the most-populated class shows in --
/// corona growth lays a NEAR-periodic patch, so one-off boundary classes are
/// noise, not domain tiles.
const RECURRENCE_DIVISOR: usize = 2;

/// Does `seq` tile the plane periodically with a fundamental domain of at most
/// `kmax` tiles? Grows a `coronas`-deep patch, reads candidate lattices off its
/// same-orientation displacements, and gold-checks each. Returns the verified
/// cover, or `None` (a candidate is then left undecided, never rejected).
///
/// See the module docs for why the candidate lattices come from a grown patch
/// (the ring is dense, so abstract covolume enumeration is not finite) and why
/// the float-guided search is sound (the exact gold check gates every accept).
pub fn tiles_torus<T: IsRing>(seq: &[i8], kmax: usize, coronas: usize) -> Option<TorusCover<T>> {
    let verts = boundary_vertices::<T>(seq);
    let tile_area = area_f(&verts);
    if tile_area < AREA_EPS {
        return None;
    }

    let patch = grow_coronas::<T>(seq, coronas);
    torus_cover_from_patch(&verts, seq, &patch, tile_area, kmax)
}

/// Read a torus cover off an already-grown near-periodic `patch`: group by
/// orientation, collect recurring same-orientation displacements as candidate
/// lattice vectors, and for each covolume-consistent pair fold the patch onto
/// `k` classes and exact-`gold_check` it. Returns the first verified cover.
///
/// Decoupled from the grower so a cheaply-built periodic orbit (e.g. a Conway
/// or isohedral `build_orbit` patch) can be handed straight in -- the lattice
/// detection here is what produces a *verified* primitive cell + domain, which
/// cert minting needs, without paying for `grow_coronas`'s backtracking.
pub(crate) fn torus_cover_from_patch<T: IsRing>(
    verts: &[T],
    seq: &[i8],
    patch: &[Iso<T>],
    tile_area: f64,
    kmax: usize,
) -> Option<TorusCover<T>> {
    if patch.len() < 4 {
        return None; // not surrounded enough to expose any lattice
    }

    // Group placements by orientation (translation signature); the anchor of
    // each is its minimal vertex. Built ONCE, reused across all candidate
    // lattice pairs below.
    let groups = signature_groups(patch, verts);

    // Same-orientation displacement vectors, by frequency (a true lattice
    // vector recurs across the patch, so the frequent ones are the candidates).
    let mut freq: HashMap<T, usize> = HashMap::default();
    for members in groups.values() {
        for i in 0..members.len() {
            for j in 0..members.len() {
                if i != j {
                    let d = members[j].0 - members[i].0;
                    if d.xy() != (0.0, 0.0) {
                        *freq.entry(d).or_insert(0) += 1;
                    }
                }
            }
        }
    }
    let mut disps: Vec<(usize, T)> = freq.into_iter().map(|(v, c)| (c, v)).collect();
    // Sort by frequency DESC, breaking ties by a deterministic geometric key --
    // `freq` is a HashMap, so without the tiebreak equal-frequency vectors keep a
    // per-process-random order, which makes both `truncate` and the first cover
    // found below nondeterministic (different but equally valid k-covers on
    // different runs, some of which the carve then fails to reproduce). The
    // tiebreak makes the chosen cover -- and thus the whole cert -- reproducible.
    disps.sort_by(|a, b| b.0.cmp(&a.0).then_with(|| cmp_xy(&a.1, &b.1)));
    disps.truncate(MAX_DISP);
    let vecs: Vec<T> = disps.into_iter().map(|(_, v)| v).collect();

    // For each pair, the covolume fixes k = round(|cross| / area); keep pairs
    // whose covolume is (near) an integer multiple of the tile area, then let
    // the exact gold check decide.
    for a in 0..vecs.len() {
        for b in (a + 1)..vecs.len() {
            let (v1, v2) = (vecs[a], vecs[b]);
            let c = cross_f(&v1, &v2).abs();
            if c < tile_area * MIN_COVOL_FRACTION {
                continue;
            }
            let k = (c / tile_area).round() as usize;
            if k == 0 || k > kmax {
                continue;
            }
            if (c / tile_area - k as f64).abs() > COVOL_INT_EPS {
                continue; // covolume must be ~ k * tile area
            }
            let Some(inv) = basis_inverse(&v1, &v2) else {
                continue;
            };
            let domain = domain_reps(&groups, v1, v2, &inv);
            if domain.len() != k {
                continue; // patch must fold onto exactly k torus classes
            }
            // THE MULTIPLICITY GATE, exact: the float `k` above is only a
            // proposal filter; this ring identity (covolume == exactly
            // `domain.len()` tile areas) plus the per-class gold check pins
            // the covering multiplicity to 1 with no float in the chain.
            if !covol_eq_m_areas(v1, v2, verts, domain.len()) {
                continue;
            }
            if gold_check(verts, seq, &domain, v1, v2) {
                return Some(TorusCover {
                    k,
                    lattice: (v1, v2),
                    domain,
                });
            }
        }
    }
    None
}

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

    /// The three regular Conway tilers must accept with a small domain.
    #[test]
    fn regular_tilers_tile_torus() {
        for (name, seq) in [
            (
                "triangle",
                Rat::from_snake_trusted(&tiles::triangle::<ZZ12>())
                    .seq()
                    .to_vec(),
            ),
            (
                "square",
                Rat::from_snake_trusted(&tiles::square::<ZZ12>())
                    .seq()
                    .to_vec(),
            ),
            (
                "hexagon",
                Rat::from_snake_trusted(&tiles::hexagon::<ZZ12>())
                    .seq()
                    .to_vec(),
            ),
        ] {
            let cover = tiles_torus::<ZZ12>(&seq, 4, 3);
            eprintln!(
                "{name}: {:?}",
                cover
                    .as_ref()
                    .map(|c| (c.k, c.lattice.0.xy(), c.lattice.1.xy()))
            );
            assert!(cover.is_some(), "{name} must tile the torus");
        }
    }

    /// gold_check fails CLOSED on absurd geometry instead of hanging: a domain
    /// rep far from the origin blows the coverage reaches past the per-axis
    /// guard (or the orbit cap) and the check rejects outright.
    #[test]
    fn gold_check_fail_closed_on_absurd_reaches() {
        use crate::cyclotomic::traits::{SymNum, Units};
        let tri =
            crate::geom::rat::Rat::<ZZ12>::from_snake_trusted(&crate::geom::tiles::triangle());
        let verts = crate::geom::patch::boundary_vertices::<ZZ12>(tri.seq());
        let (v1, v2) = (ZZ12::unit(0), ZZ12::unit(3));
        // reach guard: rep ~200k from origin -> reach > 100k -> reject.
        let far = Iso {
            rot: 0,
            shift: ZZ12::unit(0).scale(200_000),
        };
        assert!(!gold_check(&verts, tri.seq(), &[far], v1, v2));
        // orbit-cap guard: rep ~30k -> reaches ~60k (pass the guard) but the
        // block would hold ~1e10 placements -> reject via GOLD_ORBIT_CAP.
        let mid = Iso {
            rot: 0,
            shift: ZZ12::unit(0).scale(30_000),
        };
        assert!(!gold_check(&verts, tri.seq(), &[mid], v1, v2));
        // Empty domain never passes.
        assert!(!gold_check(&verts, tri.seq(), &[], v1, v2));
    }

    /// The regular dodecagon cannot tile, so no torus cover may be certified.
    #[test]
    fn dodecagon_has_no_torus_cover() {
        let dodec = Rat::from_snake_trusted(&tiles::dodecagon::<ZZ12>());
        let cover = tiles_torus::<ZZ12>(dodec.seq(), 8, 3);
        assert!(cover.is_none(), "dodecagon must not certify a cover");
    }
}