tilezz 0.2.0

//! Tests for the patch-growth machinery (BasicPatch / EPatch /
//! BoundaryGrid / gluing / candidate enumeration). Split out of
//! patch/mod.rs, which held ~2650 lines of tests inline.

use super::*;
use crate::cyclotomic::{ZZ4, ZZ12};
use crate::geom::glue::Validation;
use crate::geom::matches::EdgeRange;
use crate::geom::matches::Match;
use crate::geom::matches::MatchSeed;
use crate::geom::matchtypes::MatchTypeIndex;
use crate::geom::snake::Snake;
use crate::geom::tiles;
use crate::geom::vertices::{ClosedJunctionType, junction_type_raw_from};
use std::collections::BTreeMap;

fn ei(tile_id: usize, tile_offset: usize) -> EdgeInfo {
    EdgeInfo {
        tile_type_id: tile_id,
        canon_offset: tile_offset,
    }
}

/// Tileset for the white-box `update_inner_petals` tests: two 12-edge
/// shapes, so the only thing the helper reads from it -- a consumed edge's
/// tile length, for the `(offset + 1) % len` petal -- is well-defined for
/// the abstract `ei(0, ..)` / `ei(1, ..)` edges those tests use.
fn inner_chain_ts() -> TileSet<ZZ12> {
    let dod = Rat::<ZZ12>::from_snake_trusted(&tiles::dodecagon());
    TileSet::new(vec![dod.clone(), dod])
}

#[test]
fn closed_junction_type_canonicalises_to_lex_min_rotation() {
    // Four distinct rotations of the same ring should canonicalise
    // identically.
    let petals = [ei(2, 0), ei(0, 1), ei(1, 2), ei(0, 3)];
    let canonical = ClosedJunctionType::from_cyclic(&petals);
    for shift in 0..petals.len() {
        let rotated: Vec<EdgeInfo> = (0..petals.len())
            .map(|i| petals[(shift + i) % petals.len()])
            .collect();
        assert_eq!(
            ClosedJunctionType::from_cyclic(&rotated),
            canonical,
            "rotation by {shift} should canonicalise to the same JT"
        );
    }

    // The canonical form must start at the lex-min entry.
    let edges = canonical.edges();
    for k in 1..edges.len() {
        assert!(edges[0] <= edges[k]);
    }
}

#[test]
fn closed_junction_type_distinguishes_non_rotation_orderings() {
    let a = ClosedJunctionType::from_cyclic(&[ei(0, 0), ei(0, 1), ei(0, 2)]);
    let b = ClosedJunctionType::from_cyclic(&[ei(0, 0), ei(0, 2), ei(0, 1)]);
    assert_ne!(a, b, "different cyclic orderings must be distinct");
}

#[test]
fn closed_junction_type_from_open_via_closure() {
    let open = OpenJunctionType {
        cw: ei(1, 5),
        inner: vec![ei(0, 0), ei(2, 3)],
        ccw: ei(1, 4),
    };
    let closed = ClosedJunctionType::from_open_via_closure(&open);
    // Underlying raw ring is [cw, inner..., ccw] = [(1,5),(0,0),(2,3),(1,4)],
    // canonicalised to start at the lex-min entry (0,0).
    let expected = ClosedJunctionType::from_cyclic(&[ei(0, 0), ei(2, 3), ei(1, 4), ei(1, 5)]);
    assert_eq!(closed, expected);
    assert_eq!(closed.len(), 4);
}

/// The next junction position strictly CCW of `from_pos` on `patch`'s boundary,
/// wrapping around. `None` if the patch has no junctions.
fn next_junction_on_boundary<T: IsRing>(patch: &EPatch<T>, from_pos: usize) -> Option<usize> {
    let n = patch.len();
    for step in 1..=n {
        let pos = (from_pos + step) % n;
        if patch.is_junction(pos) {
            return Some(pos);
        }
    }
    None
}

fn square_seed() -> EPatch<ZZ4> {
    let sq: Snake<ZZ4> = tiles::square();
    let rat = Rat::try_from(&sq).unwrap();
    let ts = TileSet::single(rat);
    EPatch::single_tile(ts, 0)
}

fn hex_seed() -> EPatch<ZZ12> {
    let hex: Snake<ZZ12> = tiles::hexagon();
    let rat = Rat::try_from(&hex).unwrap();
    let ts = TileSet::single(rat);
    EPatch::single_tile(ts, 0)
}

/// Build a `EPatch` by gluing the first candidate match to a
/// fresh seed for tile shape 0. Convenience for tests that just
/// need *some* growing patch on a given tileset.
fn grow_first<T: IsRing>(ts: Arc<TileSet<T>>) -> EPatch<T> {
    let seed = EPatch::single_tile(ts, 0);
    let pm = *seed.get_all_matches().first().expect("seed has matches");
    seed.with_tile(&pm).expect("first glue succeeds")
}

/// The localized (cold-cache) `get_matches_in_edge_range` must return
/// exactly the same set as the whole-boundary computation filtered to the
/// range -- for every edge, across a range of grown patches and depths.
/// This pins the windowed-enumeration completeness argument.
#[test]
fn matches_in_edge_range_localized_equals_full() {
    let tri = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle());
    let dodec = Rat::<ZZ12>::from_snake_trusted(&tiles::dodecagon());
    let seqs: [&[i8]; 3] = [
        tri.seq(),
        &[-2, -1, 2, 5, -2, 1, 2, 1, 2, 4], // the asymmetric "unknown"
        dodec.seq(),
    ];
    for seq in seqs {
        let ts = TileSet::single(Rat::<ZZ12>::from_slice_trusted(seq));
        let mut gp = grow_first(ts);
        for step in 0..6 {
            let n = gp.len();
            // every single-edge query, plus a couple of multi-edge ranges
            let full = gp.get_all_matches();
            let mut ranges: Vec<(usize, usize)> = (0..n).map(|e| (e, e)).collect();
            if n >= 3 {
                ranges.push((0, 2));
                ranges.push((n - 2, (n - 2 + 1) % n));
            }
            for (s, e) in ranges {
                let range_len = (e + n - s) % n + 1;
                let mut want: Vec<PatchMatch> = full
                    .iter()
                    .filter(|pm| {
                        cyclic_arcs_overlap(s, range_len, pm.a_range.start_offset, pm.len(), n)
                    })
                    .cloned()
                    .collect();
                let mut got = gp.get_matches_in_edge_range(s, e);
                want.sort();
                got.sort();
                assert_eq!(got, want, "seq={seq:?} step={step} range=({s},{e}) n={n}");
            }
            // advance one tile (keeps the cache cold for the next round)
            let Some(m) = gp.get_all_matches().first().copied() else {
                break;
            };
            if gp.add_tile(&m).is_none() {
                break;
            }
        }
    }
}

/// The localized (cold-cache) `get_matches_touching_vertex` must equal the
/// whole-boundary computation filtered by vertex-containment, for every
/// vertex across grown patches and depths. Pins the windowed cold path.
#[test]
fn touching_vertex_localized_equals_full() {
    let tri = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle());
    let dodec = Rat::<ZZ12>::from_snake_trusted(&tiles::dodecagon());
    let seqs: [&[i8]; 3] = [tri.seq(), &[-2, -1, 2, 5, -2, 1, 2, 1, 2, 4], dodec.seq()];
    for seq in seqs {
        let ts = TileSet::single(Rat::<ZZ12>::from_slice_trusted(seq));
        let mut gp = grow_first(ts);
        for step in 0..6 {
            let n = gp.len();
            let full = gp.get_all_matches();
            for vi in 0..n {
                let mut want: Vec<PatchMatch> = full
                    .iter()
                    .filter(|pm| cyclic_range_contains(pm.a_range.start_offset, pm.len(), vi, n))
                    .cloned()
                    .collect();
                let mut got = gp.get_matches_touching_vertex(vi);
                want.sort();
                got.sort();
                assert_eq!(got, want, "seq={seq:?} step={step} vertex={vi} n={n}");
            }
            let Some(m) = gp.get_all_matches().first().copied() else {
                break;
            };
            if gp.add_tile(&m).is_none() {
                break;
            }
        }
    }
}

/// Apply a pinned sequence of glues starting from a seed. Panics
/// with a descriptive message at the failing glue index. Used by
/// the hand-built test fixtures (3x3-minus-corner, T-tetromino,
/// five-hex cross).
fn build_from_glues<T: IsRing>(seed: EPatch<T>, glues: &[PatchMatch], label: &str) -> EPatch<T> {
    let mut gp = seed
        .with_tile(&glues[0])
        .unwrap_or_else(|| panic!("{label} glue 0 failed: pm={:?}", glues[0]));
    for (i, pm) in glues.iter().enumerate().skip(1) {
        assert!(
            gp.add_tile(pm).is_some(),
            "{label} glue {} failed: pm={:?}",
            i,
            pm
        );
    }
    gp
}

/// User-suggested hollow-ring construction: build a curving chain
/// of hexagons by always gluing the latest hex's edge 1 to the
/// new hex's edge 5 (= a 60 deg wedge angle, so the chain curves
/// inward). The first 4 glues succeed and produce a 5-hex C
/// around an empty hex-shaped center. The 5th glue (= closing
/// into a 6-hex hollow ring around the empty center) would
/// produce a non-simply-connected patch with a hole -- which
/// `EPatch::add_tile` correctly rejects.
///
/// At each step the latest hex's edge 1 sits at boundary position
/// `len - 4` (= second of the latest hex's surviving
/// edges in CCW order after the boundary rotation the glue applies --
/// surviving old edges first, then the new tile's edges).
#[test]
fn hollow_hex_ring_closure_rejected() {
    // First glue: hex_0's edge 1 -> hex_1's edge 5 (start_a=1 on
    // the seed's notional boundary, len=1, start_b=0 so the
    // matched petal edge is start_b-1 = 5 mod 6).
    let first = PatchMatch::new(EdgeRange::new(1, 1), Segment::new(0, EdgeRange::new(0, 1)));
    let mut gp = hex_seed()
        .with_tile(&first)
        .expect("first glue should succeed");
    // Glues 2-4: continue the chain. start_a is tracked from
    // the post-glue boundary's "second surviving edge of latest
    // hex" = len - 4.
    for step in 2..=4 {
        let start_a = gp.len() - 4;
        let pm = PatchMatch::new(
            EdgeRange::new(start_a, 1),
            Segment::new(0, EdgeRange::new(0, 1)),
        );
        assert!(
            gp.add_tile(&pm).is_some(),
            "step {} glue (pm={:?}) should succeed",
            step,
            pm
        );
    }
    assert_eq!(
        gp.len(),
        22,
        "after 4 glues = 5 hexes in a C, boundary should be 22 edges"
    );

    // Step 5: would add hex_5 closing the chain into a 6-hex
    // ring AROUND AN EMPTY CENTER. The chain has curved enough
    // that hex_5's surviving edges would spatially coincide
    // with hex_0's exposed edges on the other side of the gap
    // (= the chain endpoints face each other across the empty
    // center). `check_edge_clear` rejects: the new tile's
    // segments would touch the existing boundary at non-
    // endpoint positions.
    let start_a = gp.len() - 4;
    let closing_pm = PatchMatch::new(
        EdgeRange::new(start_a, 1),
        Segment::new(0, EdgeRange::new(0, 1)),
    );
    let ok = gp.add_tile(&closing_pm).is_some();
    assert!(
        !ok,
        "EPatch::add_tile must refuse the closing glue \
             (= would build a 6-hex ring with a hex-shaped hole at \
             the center, which is non-simply-connected). \
             pm={:?}, current len={}",
        closing_pm,
        gp.len()
    );
    // After rejection the patch is unchanged.
    assert_eq!(gp.len(), 22, "rejected glue must leave state unchanged");
}

/// Build a 7-hex full corona (1 central + 6 ring tiles) via the
/// user-suggested approach: glue the central as the FIRST chain
/// step, then continue the same curving "edge 1 -> edge 5"
/// pattern. Returns the patch.
///
/// Step 1 glues central to hex_0's edge 0 (`start_a = 0`,
/// `len = 1`). After this glue the rotation puts hex_0's edge 1
/// at boundary position 0, so step 2 also uses `start_a = 0`.
/// From step 3 onward, the latest hex's edge 1 sits at
/// `len - 4` per the rotation convention.
#[cfg(debug_assertions)]
fn seven_hex_full_corona() -> EPatch<ZZ12> {
    // Build via three phases:
    //   1. Chain (4 glues): 5 hexes curving around an empty center.
    //   2. Fill (1 glue): central tile fills the inner concavity
    //      via mlen=5 (matching all 5 center-facing edges).
    //   3. Close (1 glue): 6th corona at the remaining wedge via
    //      mlen=3 (matching the 3 wedge-facing edges).
    let first = PatchMatch::new(EdgeRange::new(1, 1), Segment::new(0, EdgeRange::new(0, 1)));
    let mut gp = hex_seed().with_tile(&first).expect("chain glue 1");
    for _ in 2..=4 {
        let start_a = gp.len() - 4;
        let pm = PatchMatch::new(
            EdgeRange::new(start_a, 1),
            Segment::new(0, EdgeRange::new(0, 1)),
        );
        assert!(gp.add_tile(&pm).is_some(), "chain glue {:?}", pm);
    }
    // Brute-force pick: a match with mlen=5 fills central.
    let central = gp
        .get_all_matches()
        .into_iter()
        .find(|pm| {
            pm.len() == 5 && {
                let mut trial = gp.clone();
                trial.add_tile(pm).is_some()
            }
        })
        .unwrap_or_else(|| panic!("no mlen=5 candidate to fill central"));
    assert!(gp.add_tile(&central).is_some(), "central fill");
    // Close via mlen=3.
    let closer = gp
        .get_all_matches()
        .into_iter()
        .find(|pm| {
            pm.len() == 3 && {
                let mut trial = gp.clone();
                trial.add_tile(pm).is_some() && trial.len() == 18
            }
        })
        .unwrap_or_else(|| panic!("no mlen=3 candidate closing the corona"));
    assert!(gp.add_tile(&closer).is_some(), "ring closure");
    gp
}

/// Precondition GUARD test for [`EPatch::construct_witness_from_jt_sequence`]:
/// when the input jt_seq omits a FULLY INTERIOR tile (not captured by any
/// junction's cw/ccw/inner), reconstruction would place the tiles in a
/// self-intersecting spiral. The debug precondition guard now CATCHES that
/// (panics) instead of silently returning the bogus patch.
///
/// Concrete case: the 7-hex full corona has 6 outer junctions (cw/ccw of the
/// two outer hexes at each corner; `inner` empty), so the central hex appears
/// in no junction. Reconstructing from those 6 jtypes trips the guard.
///
/// Debug-only: the guard is a `debug_assert`, so in release it compiles out and
/// the call would silently return the spiral (the documented, unguarded
/// footgun) -- hence this test only exists under `debug_assertions`. This bad
/// witness self-intersects mid-construction, so the trusted-glue collision
/// debug-assert catches it first; the end-of-construction simple-closed check is
/// the backstop. Either guard rejects it, so we match any panic rather than a
/// specific message.
#[test]
#[cfg(debug_assertions)]
#[should_panic]
fn construct_witness_guard_rejects_fully_interior_tile() {
    let gp = seven_hex_full_corona();
    assert_eq!(gp.len(), 18);
    let jt_seq: Vec<OpenJunctionType> = (0..gp.len())
        .filter_map(|i| gp.junction_type_at(i))
        .collect();
    assert_eq!(jt_seq.len(), 6, "7-hex corona has 6 outer junctions");
    let mi = Arc::clone(gp.match_index());
    // Trips the debug precondition guard (central tile not captured).
    let _ = EPatch::construct_witness_from_jt_sequence(&jt_seq, mi);
}

/// Pure unit tests for [`cyclic_range_contains`]. Computed via the
/// brute reference "which vertices does a `len`-edge match anchored
/// at `start` touch on a cyclic boundary of length `n`?":
/// vertices `{start, start+1, ..., start+len}` modulo `n` (i.e.
/// `len + 1` vertices).
///
/// Regression: the previous implementation had a wrap-around bug
/// exactly when `start + len == n`. In that case the match's
/// CCW-endpoint vertex is `n mod n = 0`, but the function's
/// `end <= n` branch checked `index >= start && index <= end`
/// which is false for `index = 0` whenever `start > 0`.
/// This test pins all four interesting regimes (interior,
/// CCW-endpoint-no-wrap, CW-endpoint, wrap-around) plus the
/// `start + len == n` exact-fit boundary case.
#[test]
fn cyclic_range_contains_unit() {
    // (start, len, n) -> set of vertex indices the match touches.
    fn brute(start: usize, len: usize, n: usize) -> std::collections::BTreeSet<usize> {
        if len == 0 || n == 0 {
            return std::collections::BTreeSet::new();
        }
        (0..=len).map(|i| (start + i) % n).collect()
    }

    // Pin the regression case directly:
    // start=25, len=1, n=26 should touch vertices {25, 0}.
    // Signature: cyclic_range_contains(start, len, index, n).
    assert!(
        cyclic_range_contains(25, 1, 0, 26),
        "regression: end-at-n-mod-n=0 wrap"
    );
    assert!(cyclic_range_contains(25, 1, 25, 26), "CW endpoint");

    // Exhaustive cross-check against brute over a moderate range.
    for n in [1, 2, 5, 13, 26] {
        for start in 0..n {
            for len in 0..=(n + 1) {
                let want = brute(start, len, n);
                for index in 0..n {
                    let got = cyclic_range_contains(start, len, index, n);
                    let expected = want.contains(&index);
                    assert_eq!(got, expected, "n={n} start={start} len={len} index={index}");
                }
            }
        }
    }

    // Edge cases.
    assert!(!cyclic_range_contains(0, 0, 0, 10), "len=0 -> false");
    assert!(!cyclic_range_contains(0, 5, 0, 0), "n=0 -> false");
}

/// Pure unit test for [`cyclic_arcs_overlap`]. Exhaustively
/// cross-checks against brute-force edge enumeration over small
/// boundary sizes plus a handful of regression cases (empty arcs,
/// zero-length boundary, full-cycle arcs, wraparound on both
/// arcs).
#[test]
fn cyclic_arcs_overlap_unit() {
    fn brute_edges(start: usize, len: usize, n: usize) -> std::collections::BTreeSet<usize> {
        if len == 0 || n == 0 {
            return std::collections::BTreeSet::new();
        }
        (0..len).map(|i| (start + i) % n).collect()
    }
    fn brute_overlap(a: usize, l_a: usize, b: usize, l_b: usize, n: usize) -> bool {
        let arc_a = brute_edges(a, l_a, n);
        let arc_b = brute_edges(b, l_b, n);
        !arc_a.is_disjoint(&arc_b)
    }

    // Exhaustive cross-check over moderate sizes.
    for n in [1, 2, 5, 8, 13] {
        for a in 0..n {
            for l_a in 0..=(n + 1) {
                for b in 0..n {
                    for l_b in 0..=(n + 1) {
                        let got = cyclic_arcs_overlap(a, l_a, b, l_b, n);
                        let want = brute_overlap(a, l_a, b, l_b, n);
                        assert_eq!(got, want, "mismatch: a={a} l_a={l_a} b={b} l_b={l_b} n={n}");
                    }
                }
            }
        }
    }

    // Targeted edge cases.
    assert!(
        !cyclic_arcs_overlap(0, 0, 0, 5, 10),
        "empty arc never overlaps"
    );
    assert!(
        !cyclic_arcs_overlap(0, 5, 0, 0, 10),
        "empty arc never overlaps (other side)"
    );
    assert!(!cyclic_arcs_overlap(0, 5, 0, 5, 0), "n=0 -> false");
    assert!(
        cyclic_arcs_overlap(0, 10, 5, 1, 10),
        "full-cycle A vs any non-empty B"
    );
    assert!(
        cyclic_arcs_overlap(7, 5, 1, 2, 10),
        "wraparound A vs interior B"
    );
    assert!(!cyclic_arcs_overlap(0, 3, 5, 3, 10), "disjoint interiors");
    assert!(cyclic_arcs_overlap(0, 3, 2, 3, 10), "edge 2 shared");
}

/// `get_matches_in_edge_range` agreement with the brute-force
/// derivation (= filter `get_all_matches()` by edge-set
/// intersection). Exhaustive across all start/end positions on
/// real BFS-grown patches in hex and spectre tilesets.
#[test]
fn get_matches_in_edge_range_matches_brute_force() {
    for ts in [
        Arc::new(TileSet::new(vec![
            Rat::try_from(&tiles::hexagon::<ZZ12>()).unwrap(),
        ])),
        Arc::new(TileSet::new(vec![
            Rat::try_from(&tiles::spectre::<ZZ12>()).unwrap(),
        ])),
    ] {
        let seed = EPatch::single_tile(Arc::clone(&ts), 0);
        let first = *seed.get_all_matches().first().expect("seed match");
        let gp = seed.with_tile(&first).expect("seed add");
        let n = gp.len();
        assert!(n > 0);
        let all = gp.get_all_matches();
        for start in 0..n {
            for end in 0..n {
                let range_len = (end + n - start) % n + 1;
                let want: std::collections::BTreeSet<(usize, usize, usize, usize)> = all
                    .iter()
                    .filter(|pm| {
                        cyclic_arcs_overlap(start, range_len, pm.a_range.start_offset, pm.len(), n)
                    })
                    .map(|pm| {
                        (
                            pm.a_range.start_offset,
                            pm.len(),
                            pm.b.range.start_offset,
                            pm.b.tile_id,
                        )
                    })
                    .collect();
                let got: std::collections::BTreeSet<(usize, usize, usize, usize)> = gp
                    .get_matches_in_edge_range(start, end)
                    .into_iter()
                    .map(|pm| {
                        (
                            pm.a_range.start_offset,
                            pm.len(),
                            pm.b.range.start_offset,
                            pm.b.tile_id,
                        )
                    })
                    .collect();
                assert_eq!(
                    got, want,
                    "mismatch on n={n} start={start} end={end} range_len={range_len}"
                );
            }
        }
    }
}

/// Identity test: a range covering the full boundary returns
/// every match (= equivalent to `get_all_matches()`).
#[test]
fn get_matches_in_edge_range_full_boundary_equals_all() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre::<ZZ12>()).unwrap(),
    ]));
    let seed = EPatch::single_tile(Arc::clone(&ts), 0);
    let first = *seed.get_all_matches().first().unwrap();
    let gp = seed.with_tile(&first).unwrap();
    let n = gp.len();
    let mut all: Vec<_> = gp.get_all_matches();
    all.sort_by_key(|pm| {
        (
            pm.a_range.start_offset,
            pm.len(),
            pm.b.range.start_offset,
            pm.b.tile_id,
        )
    });
    for start in 0..n {
        let end = (start + n - 1) % n;
        let mut got = gp.get_matches_in_edge_range(start, end);
        got.sort_by_key(|pm| {
            (
                pm.a_range.start_offset,
                pm.len(),
                pm.b.range.start_offset,
                pm.b.tile_id,
            )
        });
        assert_eq!(got, all, "full-boundary range from start={start}");
    }
}

/// Verify that the *set* of `(OpenJunctionType, OpenJunctionType)`
/// junction pairs on a patch boundary is invariant under
/// `normalize()`.
///
/// Rationale: `OpenJunctionType` is built from `cw`, `inner`, and
/// `ccw` fields, all `EdgeInfo` (= `tile_id` + `tile_offset`) --
/// never `patch_tile_id`. And the set of consecutive pairs on a
/// cyclic boundary is rotation-invariant. So normalize, which
/// only rotates the boundary and renumbers `patch_tile_id`s,
/// can't change the pair set.
#[test]
fn junction_pair_set_is_normalize_invariant() {
    for ts in [
        Arc::new(TileSet::new(vec![
            Rat::try_from(&tiles::hexagon::<ZZ12>()).unwrap(),
        ])),
        Arc::new(TileSet::new(vec![
            Rat::try_from(&tiles::spectre::<ZZ12>()).unwrap(),
        ])),
    ] {
        // Grow a patch a few tiles deep and check at each step.
        let seed = EPatch::single_tile(Arc::clone(&ts), 0);
        let first = *seed.get_all_matches().first().unwrap();
        let mut gp = seed.with_tile(&first).unwrap();
        for _step in 0..4 {
            let pre_pairs = collect_pair_set(&gp);
            let mut normed = gp.clone();
            normed.normalize();
            let post_pairs = collect_pair_set(&normed);
            assert_eq!(
                pre_pairs, post_pairs,
                "junction pair set differs across normalize"
            );
            // Grow one more tile for the next iteration.
            if let Some(pm) = gp.get_all_matches().into_iter().next() {
                if gp.add_tile(&pm).is_none() {
                    break;
                }
            } else {
                break;
            }
        }
    }
}

fn collect_pair_set(
    patch: &EPatch<ZZ12>,
) -> std::collections::BTreeSet<(OpenJunctionType, OpenJunctionType)> {
    let n = patch.len();
    let juncs: Vec<OpenJunctionType> = (0..n).filter_map(|i| patch.junction_type_at(i)).collect();
    let k = juncs.len();
    let mut out = std::collections::BTreeSet::new();
    if k < 2 {
        return out;
    }
    for j in 0..k {
        out.insert((juncs[j].clone(), juncs[(j + 1) % k].clone()));
    }
    out
}

/// Build 8 unit squares as 3x3-minus-top-left-corner, via pinned literal
/// glues (see the body) chosen so every intermediate patch stays simply
/// connected.
fn square_grid_3x3_minus_top_left_corner() -> EPatch<ZZ4> {
    // 8 unit squares forming a 3x3 minus the top-left corner
    // (X = present, . = missing):
    //   row 2: . X X
    //   row 1: X X X
    //   row 0: X X X
    //
    // The 7 glues below were extracted by greedy search (pick the
    // first match producing the right boundary length) and then
    // pinned. Each step keeps the cumulative patch simply
    // connected. Pinning the literals avoids the brute search.
    let glues = [
        // boundary 4 -> 6: attach a strip-mate to the seed square.
        PatchMatch::new(EdgeRange::new(0, 1), Segment::new(0, EdgeRange::new(0, 1))),
        // boundary 6 -> 8: extend the row.
        PatchMatch::new(EdgeRange::new(0, 1), Segment::new(0, EdgeRange::new(1, 1))),
        // boundary 8 -> 10: extend again to make a 1x3 row.
        PatchMatch::new(EdgeRange::new(0, 1), Segment::new(0, EdgeRange::new(1, 1))),
        // boundary 10 -> 12: turn upward, starting the right column.
        PatchMatch::new(EdgeRange::new(0, 1), Segment::new(0, EdgeRange::new(1, 1))),
        // boundary 12 -> 12: continue upward.
        PatchMatch::new(EdgeRange::new(2, 2), Segment::new(0, EdgeRange::new(1, 2))),
        // boundary 12 -> 12: wrap left along the top.
        PatchMatch::new(EdgeRange::new(1, 2), Segment::new(0, EdgeRange::new(1, 2))),
        // boundary 12 -> 12: drop into the inner tile (1, 1).
        PatchMatch::new(EdgeRange::new(1, 2), Segment::new(0, EdgeRange::new(1, 2))),
    ];
    build_from_glues(square_seed(), &glues, "3x3-minus-corner fixture")
}

/// User-suggested scenario: 8 unit squares forming a 3x3 grid
/// minus the top-left corner -- a simply-connected patch with a
/// concave notch where the missing tile would be. Extract the
/// boundary's jt_seq (7 junctions: 6 "straight" tile-tile
/// boundaries + 1 concave-notch corner) and feed it into
/// `construct_witness_from_jt_sequence`.
///
/// `construct_witness_from_jt_sequence` glues tiles one at a
/// time around the seq, which on this input does NOT need the
/// inner tile (1, 1) -- the minimal witness for these 7 junctions
/// is the 7-tile ring of corner+edge tiles around the notch. The
/// reconstruction therefore succeeds without ever hitting a
/// seg_len_new == 0 keystone glue. Pin: rebuilt.len ==
/// original.len.
#[test]
fn reconstruct_3x3_minus_corner_from_vt_seq() {
    let gp = square_grid_3x3_minus_top_left_corner();
    assert_eq!(
        gp.len(),
        12,
        "fixture: 3x3-minus-corner has 12 boundary edges"
    );
    let n = gp.len();
    let mut corona_vt_seq: Vec<OpenJunctionType> = Vec::new();
    for i in 0..n {
        if let Some(jt) = gp.junction_type_at(i) {
            corona_vt_seq.push(jt);
        }
    }
    assert_eq!(
        corona_vt_seq.len(),
        7,
        "fixture: 6 tile-tile straight junctions + 1 concave notch"
    );
    let mi = Arc::clone(gp.match_index());
    let (rebuilt, _junc_positions) = EPatch::construct_witness_from_jt_sequence(&corona_vt_seq, mi)
        .expect("3x3-minus-corner jt_seq should reconstruct");
    assert_eq!(
        rebuilt.len(),
        gp.len(),
        "reconstructed boundary length should match original",
    );
}

/// Regression test for the keystone-glue path in [`build_glued_edges`] and
/// [`update_inner_petals`] (the two keystone tests below): when
/// `pm.len() == m_tile` (the petal's full perimeter is absorbed by the match),
/// `seg_len_new == 0` and the petal contributes zero surviving boundary edges.
/// The pre-fix code:
///
/// - `build_glued_edges` unconditionally pushed one petal edge, yielding
///   `seg_len_old + 1` edges instead of `seg_len_old`.
/// - `update_inner_petals` wrote `chain_cw` into `new_inner[seg_len_old]`, one
///   past the end of the length-`seg_len_old` vector.
///
/// Both call the private helpers directly with crafted inputs that exercise the
/// `seg_len_new == 0` path.
#[test]
fn build_glued_edges_keystone_len() {
    // Old boundary: 8 edges, all tile_id 0 (placeholders).
    let old_edges: Vec<EdgeInfo> = (0..8)
        .map(|i| EdgeInfo {
            tile_type_id: 0,
            canon_offset: i,
        })
        .collect();
    let old_ptids = vec![0usize; 8];
    // Keystone: petal of m_tile = 4 fully absorbed (pm.len() = 4 = m_tile).
    let pm = PatchMatch::new(EdgeRange::new(2, 4), Segment::new(1, EdgeRange::new(0, 4)));
    let m_tile = 4;
    let (new_edges, new_ptids) = build_glued_edges(&old_edges, &old_ptids, &pm, m_tile, 99);
    // new_len = seg_len_old + seg_len_new = (8-4) + (4-4) = 4 + 0 = 4.
    assert_eq!(new_edges.len(), 4, "keystone glue: new_len == seg_len_old");
    assert_eq!(new_ptids.len(), 4);
    // None of the new edges should belong to the petal (= no petal
    // edge survives the keystone glue).
    for e in &new_edges {
        assert_ne!(e.tile_type_id, pm.b.tile_id, "no surviving petal edges");
    }
}

#[test]
fn update_inner_petals_keystone_no_oob() {
    // Same setup as build_glued_edges_keystone_len.
    let old_edges: Vec<EdgeInfo> = (0..8)
        .map(|i| EdgeInfo {
            tile_type_id: 0,
            canon_offset: i,
        })
        .collect();
    let old_inner: Vec<Vec<EdgeInfo>> = vec![Vec::new(); 8];
    let old_ptids = vec![0usize; 8];
    let pm = PatchMatch::new(EdgeRange::new(2, 4), Segment::new(1, EdgeRange::new(0, 4)));
    let new_n = 4; // seg_len_old + seg_len_new = 4 + 0.
    let new_inner = update_inner_petals(
        &old_inner,
        &old_edges,
        &pm,
        new_n,
        &old_ptids,
        &inner_chain_ts(),
    );
    // The pre-fix code would have panicked here. Just verify
    // length and that the call succeeded.
    assert_eq!(new_inner.len(), new_n);
}

/// Helper: contiguous edges from a single tile, used as old_edges.
fn shape_edges(tile_id: usize, n: usize) -> Vec<EdgeInfo> {
    (0..n).map(|i| ei(tile_id, i)).collect()
}

/// Normal glue, all old edges from the same tile instance (= all
/// ptids equal). No matched edge ever crosses a tile-instance
/// boundary, so neither junction's inner-chain absorbs any old edge.
/// Surviving inner-chains shift into place untouched.
#[test]
fn update_inner_petals_normal_no_crossings_passes_old_through() {
    let n = 6;
    let old_edges = shape_edges(0, n);
    // Plant a marker in each old inner chain so we can check who
    // moved where.
    let old_inner: Vec<Vec<EdgeInfo>> = (0..n).map(|i| vec![ei(99, i)]).collect();
    let old_ptids = vec![7usize; n]; // all same instance.

    // Match [start_a=2, len=2). seg_len_old = 4, ccw_pos = 4,
    // cw_end_matched = 3. Petal m_tile = 4 -> new_n = 4 + 2 = 6.
    let pm = PatchMatch::new(EdgeRange::new(2, 2), Segment::new(1, EdgeRange::new(0, 2)));
    let m_tile = 4;
    let seg_len_old = n - pm.len();
    let new_n = seg_len_old + (m_tile - pm.len());

    let got = update_inner_petals(
        &old_inner,
        &old_edges,
        &pm,
        new_n,
        &old_ptids,
        &inner_chain_ts(),
    );

    assert_eq!(got.len(), new_n);
    // CCW junction at new[0] inherits old_inner[ccw_pos=4]; no edge pushed.
    assert_eq!(got[0], vec![ei(99, 4)]);
    // Interior survivors at new[1..seg_len_old] come from old_inner[(ccw_pos + i) % n].
    assert_eq!(got[1], vec![ei(99, 5)]);
    assert_eq!(got[2], vec![ei(99, 0)]);
    assert_eq!(got[3], vec![ei(99, 1)]);
    // CW junction at new[seg_len_old=4] inherits old_inner[start_a=2]; no edge pushed.
    assert_eq!(got[4], vec![ei(99, 2)]);
    // Petal-side new positions (>= seg_len_old + 1) stay empty;
    // `update_inner_petals` only sets the boundary side.
    assert_eq!(got[5], Vec::<EdgeInfo>::new());
}

/// Normal glue where matched edges sit in a different tile
/// instance than their immediate survivors. Both junctions should
/// absorb their incident matched edge into their inner chain.
#[test]
fn update_inner_petals_normal_with_crossings_pushes_matched_edges() {
    let n = 6;
    let old_edges = shape_edges(0, n);
    let old_inner: Vec<Vec<EdgeInfo>> = vec![Vec::new(); n];
    // ptids: matched edges at positions 2..4 are instance #1, the
    // rest are instance #0. Both junctions therefore cross an
    // instance boundary.
    let old_ptids = vec![0, 0, 1, 1, 0, 0];

    let pm = PatchMatch::new(EdgeRange::new(2, 2), Segment::new(1, EdgeRange::new(0, 2)));
    let m_tile = 4;
    let seg_len_old = n - pm.len();
    let new_n = seg_len_old + (m_tile - pm.len());

    let got = update_inner_petals(
        &old_inner,
        &old_edges,
        &pm,
        new_n,
        &old_ptids,
        &inner_chain_ts(),
    );

    // CCW junction at new[0] gets the buried tile's petal: the edge
    // STARTING at the vertex = successor of the CW-end matched edge
    // old_edges[3] = ei(0,3) -> ei(0,4) (the edge ending at the vertex's
    // next edge of that tile).
    assert_eq!(got[0], vec![ei(0, 4)]);
    // Interior survivors are empty (old_inner was all empty).
    for (i, chain) in got.iter().enumerate().take(seg_len_old).skip(1) {
        assert!(chain.is_empty(), "interior position {i}");
    }
    // CW junction at new[seg_len_old]: the CCW-end matched edge
    // old_edges[start_a] = old_edges[2] STARTS at the vertex, so it is
    // recorded as-is.
    assert_eq!(got[seg_len_old], vec![ei(0, 2)]);
}

/// Keystone glue (`seg_len_new == 0`, so `new_n == seg_len_old`):
/// both junctions collapse to new[0] and the merged inner chain is
/// `chain_cw` followed by `chain_ccw`.
#[test]
fn update_inner_petals_keystone_merges_cw_then_ccw() {
    let n = 6;
    let old_edges = shape_edges(0, n);
    let old_inner: Vec<Vec<EdgeInfo>> = vec![Vec::new(); n];
    let old_ptids = vec![0, 0, 1, 1, 0, 0];

    // Keystone: petal of size 2 fully absorbed by the L=2 match.
    let pm = PatchMatch::new(EdgeRange::new(2, 2), Segment::new(1, EdgeRange::new(0, 2)));
    let m_tile = 2;
    let seg_len_old = n - pm.len();
    let new_n = seg_len_old + (m_tile - pm.len());
    assert_eq!(new_n, seg_len_old, "keystone precondition");

    let got = update_inner_petals(
        &old_inner,
        &old_edges,
        &pm,
        new_n,
        &old_ptids,
        &inner_chain_ts(),
    );

    // new[0] = chain_cw ++ chain_ccw. With all old_inner empty and
    // both junctions crossing the instance boundary, that's
    // [old_edges[start_a]=ei(0,2), petal_after(old_edges[cw_end_matched=3])
    // = ei(0,4)].
    assert_eq!(got[0], vec![ei(0, 2), ei(0, 4)]);
    // Interior positions retain shifted old_inner (empty here).
    for (i, chain) in got.iter().enumerate().skip(1) {
        assert!(chain.is_empty(), "interior position {i}");
    }
}

/// Matched range wraps the array seam (`start_a + len > n`).
/// Indexing must be cyclic; otherwise the CW-end-matched lookup
/// goes out of bounds.
#[test]
fn update_inner_petals_wraps_array_seam() {
    let n = 6;
    let old_edges = shape_edges(0, n);
    let old_inner: Vec<Vec<EdgeInfo>> = vec![Vec::new(); n];
    // Match runs from position 5 across the seam to position 0
    // (= edges {5, 0}). Both matched positions are in instance #1.
    let old_ptids = vec![1, 0, 0, 0, 0, 1];

    let pm = PatchMatch::new(EdgeRange::new(5, 2), Segment::new(1, EdgeRange::new(0, 2)));
    let m_tile = 3;
    let seg_len_old = n - pm.len();
    let new_n = seg_len_old + (m_tile - pm.len());

    let got = update_inner_petals(
        &old_inner,
        &old_edges,
        &pm,
        new_n,
        &old_ptids,
        &inner_chain_ts(),
    );

    // ccw_pos = (5 + 2) % 6 = 1; cw_end_matched = (5 + 2 - 1) % 6 = 0.
    // CCW junction at new[0] gets the petal STARTING at the vertex =
    // successor of old_edges[cw_end_matched=0] = ei(0,0) -> ei(0,1).
    assert_eq!(got[0], vec![ei(0, 1)]);
    // CW junction at new[seg_len_old=4] absorbs old_edges[start_a=5].
    assert_eq!(got[seg_len_old], vec![ei(0, 5)]);
    // Interior positions are empty here.
    for (i, chain) in got.iter().enumerate().take(seg_len_old).skip(1) {
        assert!(chain.is_empty(), "interior position {i}");
    }
}

/// Verify [`glue::glue_raw_angles`] handles `mlen == m` (= the
/// keystone case, `y_raw_len == 1`) by:
/// - Returning a result of the correct length (`seg_len_old`).
/// - Setting a non-`None` `a_yx` / `a_xy` (= the merged junction
///   angle written into `result[0]`).
/// - Producing an angle that is a valid normalized turn (`|merged|
///   < hturn`).
///
/// This is purely algebraic; the function makes no claim that the
/// resulting boundary actually corresponds to a realizable simply
/// connected patch.
#[test]
fn glue_raw_angles_keystone_returns_adjusted_result() {
    use crate::geom::glue::glue_raw_angles;
    // Self: 8 angles, with 4 consecutive angles forming a revcomp
    // pattern with a hypothetical 4-edge petal whose angles are all 1.
    // Petal angles = [1, 1, 1, 1]; revcomp(petal) reversed and
    // negated = [-1, -1, -1, -1]. So self_angles[3..=6] = [-1, -1, -1, -1].
    // Outside the match, fill arbitrarily; sum will not equal turn but
    // glue_raw_angles is a pure algebraic transform that doesn't care.
    let self_angles = vec![3, 3, 3, -1, -1, -1, -1, 3];
    let other_angles = vec![1, 1, 1, 1];
    // start_a = 3 (= start of match on self), mlen = 4 (= m, keystone),
    // start_b = 0 (= first surviving petal index; for mlen = m, none survive).
    let gr = glue_raw_angles::<ZZ12>(&self_angles, &other_angles, 3, 4, 0)
        .expect("glue should succeed on keystone");
    assert_eq!(
        gr.angles.len(),
        4,
        "keystone result length = seg_len_old = 8 - 4 = 4"
    );
    assert!(
        gr.a_yx.is_some() && gr.a_xy.is_some(),
        "keystone junction angle should be recorded"
    );
    // Pre-fix, `result[0]` was left as the raw old angle
    // (`self_angles[7] = 3`). Post-fix, it's set to the merged
    // junction angle = normalize(x_first + x_last + y - turn)
    // = normalize(self[7] + self[3] + other[0] - 12)
    // = normalize(3 + (-1) + 1 - 12) = normalize(-9) = 3
    // (since -9 mod 12 = 3 in [-6, 6]).
    assert_eq!(
        gr.angles[0], 3,
        "merged junction angle at result[0]: normalize(3 + (-1) + 1 - 12) = 3"
    );
}

#[test]
fn first_add_produces_growing() {
    let seed = hex_seed();
    let pm = seed.get_all_matches()[0];
    let gp = seed.with_tile(&pm).expect("first add");

    assert_eq!(gp.len(), 12 - 2 * pm.len());
    assert_eq!(gp.edges().len(), gp.len());
    assert_eq!(gp.angles().len(), gp.len());
}

#[test]
fn has_junctions_after_each_add() {
    let seed = hex_seed();
    let first = seed.get_all_matches()[0];
    let mut gp = seed.with_tile(&first).expect("first glue");
    let mut step = 0;
    assert!(
        !gp.edges().is_empty(),
        "step {step}: edges should not be empty"
    );
    assert!(
        (0..gp.len()).any(|i| gp.is_junction(i)),
        "step {step}: should have junction vertices"
    );
    step += 1;
    // Recompute candidates after each add -- pms from a stale patch
    // state are not valid input to `add_tile` once the boundary changes.
    while step < 3 {
        let candidates = gp.get_all_matches();
        let pm = match candidates.first() {
            Some(pm) => *pm,
            None => break,
        };
        if gp.add_tile(&pm).is_none() {
            break;
        }
        assert!(
            !gp.edges().is_empty(),
            "step {step}: edges should not be empty"
        );
        assert!(
            (0..gp.len()).any(|i| gp.is_junction(i)),
            "step {step}: should have junction vertices"
        );
        step += 1;
    }
    assert!(step > 0, "expected at least one successful add");
}

#[test]
fn hexagon_all_36_matches_produce_valid_bi_hexes() {
    let seed = hex_seed();
    let matches = seed.get_all_matches();
    assert_eq!(matches.len(), 36, "hex self-matches = 36");

    for pm in &matches {
        let gp2 = seed
            .with_tile(pm)
            .unwrap_or_else(|| panic!("first add should succeed for pm {:?}", pm));
        assert_eq!(gp2.len(), 12 - 2 * pm.len());
        assert_eq!(gp2.edges().len(), gp2.len());

        let rat = gp2.to_rat();
        assert!(
            Snake::<ZZ12>::try_from(rat.seq()).is_ok(),
            "valid snake for pm {:?}",
            pm
        );
    }
}

#[test]
fn square_all_16_matches_produce_valid_bi_squares() {
    let seed = square_seed();
    let matches = seed.get_all_matches();
    assert_eq!(matches.len(), 16, "square self-matches = 16");

    for pm in &matches {
        let gp2 = seed
            .with_tile(pm)
            .unwrap_or_else(|| panic!("first add should succeed for pm {:?}", pm));
        assert_eq!(gp2.len(), 8 - 2 * pm.len());

        let rat = gp2.to_rat();
        assert!(
            Snake::<ZZ4>::try_from(rat.seq()).is_ok(),
            "valid snake for pm {:?}",
            pm
        );
    }
}

#[test]
fn to_rat_matches_direct_glue_for_all_matches() {
    let seed = hex_seed();
    let matches = seed.get_all_matches();
    let ts = seed.tileset().clone();

    for pm in &matches {
        let gp2 = EPatch::<ZZ12>::single_tile(Arc::clone(&ts), 0)
            .with_tile(pm)
            .expect("first add");
        let rat = gp2.to_rat();

        let seed_rat = ts.rat(0);
        let new_rat = ts.rat(pm.b.tile_id);
        let glued = seed_rat.try_glue(
            MatchSeed::new(
                pm.a_range.start_offset as i64,
                pm.b.range.start_offset as i64,
            ),
            new_rat,
        );
        match glued {
            Ok(g) => assert_eq!(rat.seq(), g.seq(), "mismatch for pm {:?}", pm),
            Err(e) => panic!("glue failed for pm {:?}: {}", pm, e),
        }
    }
}

#[test]
fn edges_self_consistent() {
    let seed_sq: EPatch<ZZ4> = square_seed();
    for pm in seed_sq.get_all_matches() {
        let gp2 = match seed_sq.with_tile(&pm) {
            Some(g) => g,
            None => continue,
        };
        verify_edges_consistency(&gp2, gp2.tileset(), &format!("bi-sq pm {:?}", pm));
    }
    let seed_hex: EPatch<ZZ12> = hex_seed();
    for pm in seed_hex.get_all_matches() {
        let gp2 = match seed_hex.with_tile(&pm) {
            Some(g) => g,
            None => continue,
        };
        verify_edges_consistency(&gp2, gp2.tileset(), &format!("bi-hex pm {:?}", pm));
        for pm2 in gp2.get_all_matches() {
            let mut gp3 = gp2.clone();
            if gp3.add_tile(&pm2).is_some() {
                verify_edges_consistency(&gp3, gp3.tileset(), "3-hex");
            }
        }
    }
}

/// Assert two angle sequences are equal up to cyclic rotation (i.e.
/// describe the same closed shape). Stronger than the
/// sort-the-multisets comparison: two unrelated sequences with the
/// same angle counts would pass a sorted equality but fail this.
fn assert_same_cyclic_shape(a: &[i8], b: &[i8], label: &str) {
    assert_eq!(
        a.len(),
        b.len(),
        "{label}: angle sequences have different lengths ({} vs {})",
        a.len(),
        b.len(),
    );
    if a.is_empty() {
        return;
    }
    let mut a_canon = a.to_vec();
    let a_rot = crate::stringmatch::lex_min_rot(&a_canon);
    a_canon.rotate_left(a_rot);
    let mut b_canon = b.to_vec();
    let b_rot = crate::stringmatch::lex_min_rot(&b_canon);
    b_canon.rotate_left(b_rot);
    assert_eq!(
        a_canon, b_canon,
        "{label}: angle sequences are not cyclic rotations of each other"
    );
}

fn verify_edges_consistency<T: IsRing>(gp: &EPatch<T>, ts: &Arc<TileSet<T>>, label: &str) {
    let n = gp.len();
    assert!(n > 0, "[{}] patch should be growing", label);
    let edges = gp.edges();
    assert_eq!(edges.len(), n, "[{}] edges length", label);

    for (i, edge) in edges.iter().enumerate().take(n) {
        assert!(
            edge.tile_type_id < ts.num_tiles(),
            "[{}] pos {}: invalid tile_id {}",
            label,
            i,
            edge.tile_type_id
        );
        let tile_len = ts.rat(edge.tile_type_id).len();
        assert!(
            edge.canon_offset < tile_len,
            "[{}] pos {}: invalid offset {} for tile {} (len {})",
            label,
            i,
            edge.canon_offset,
            edge.tile_type_id,
            tile_len
        );
    }

    for i in 0..n {
        let j = (i + 1) % n;
        if edges[i].tile_type_id == edges[j].tile_type_id
            && !gp.is_junction(i)
            && !gp.is_junction(j)
        {
            let tile_len = ts.rat(edges[i].tile_type_id).len();
            let expected_next = (edges[i].canon_offset + 1) % tile_len;
            assert_eq!(
                edges[j].canon_offset, expected_next,
                "[{}] pos {}->{}: same-tile continuation expected offset {} got {}",
                label, i, j, expected_next, edges[j].canon_offset
            );
        }
    }

    let angles = gp.angles();
    assert_eq!(angles.len(), n, "[{}] angles length", label);
}

/// For each junction position on `glued`, build the minimal JT witness
/// and assert that extracting the JT from the witness yields the original.
/// Returns the number of junctions checked (asserts at least one).
fn assert_minimal_witness_roundtrips_for<T: IsRing>(
    glued: &EPatch<T>,
    mi: &Arc<MatchTypeIndex<T>>,
    label: &str,
) {
    let mut checked = 0;
    for pos in 0..glued.len() {
        let jt = match glued.junction_type_at(pos) {
            Some(jt) => jt,
            None => continue,
        };
        let (witness, wpos) = EPatch::construct_minimal_witness(&jt, Arc::clone(mi))
            .unwrap_or_else(|| {
                panic!("{label}: construct_minimal_witness failed at pos={pos} jt={jt:?}")
            });
        let reconstructed = junction_type_raw_from(witness.edges(), witness.inner_petals(), wpos);
        assert_eq!(
            reconstructed, jt,
            "{label}: roundtrip failed at pos={pos} for jt={jt:?}",
        );
        checked += 1;
    }
    assert!(checked > 0, "{label}: expected at least one junction");
}

/// For each junction position on `brute`, construct the minimal witness,
/// locate the matching position in the witness boundary, and assert the
/// witness/brute JTs agree. Also asserts that the witness angle multiset
/// equals the brute-force angle multiset.
fn assert_witness_matches_brute_force<T: IsRing>(
    brute: &EPatch<T>,
    mi: &Arc<MatchTypeIndex<T>>,
    label: &str,
) {
    let brute_angles = brute.angles().to_vec();
    let brute_edges = brute.edges().to_vec();
    let brute_inner = brute.inner_petals().to_vec();

    for pos in 0..brute.len() {
        let jt = match brute.junction_type_at(pos) {
            Some(jt) => jt,
            None => continue,
        };
        let (witness, _wpos) = EPatch::construct_minimal_witness(&jt, Arc::clone(mi))
            .unwrap_or_else(|| panic!("{label}: witness construction failed at pos={pos}"));
        let w_edges = witness.edges();
        let w_inner = witness.inner_petals();

        let mut found = false;
        for wpos in 0..witness.len() {
            let wvt = junction_type_raw_from(w_edges, w_inner, wpos);
            if wvt == jt {
                let brute_vt = junction_type_raw_from(&brute_edges, &brute_inner, pos);
                assert_eq!(
                    wvt, brute_vt,
                    "{label}: witness JT != brute-force JT at pos={pos}"
                );
                found = true;
                break;
            }
        }
        assert!(
            found,
            "{label}: no matching position in witness for jt={jt:?} at pos={pos}"
        );

        // For these fixtures (bi-hex and bi-square), the brute patch
        // *is* the minimum-witness shape, so witness and brute should
        // describe the same closed shape -- same boundary up to
        // cyclic rotation.
        assert_same_cyclic_shape(
            witness.angles(),
            &brute_angles,
            &format!("{label}: witness vs brute"),
        );
    }
}

/// For each junction on `glued`, assert that `junction_angle_sequence`
/// (a) ends at the witness junction angle, and (b) is monotonically
/// non-increasing. Returns the number of junctions checked (asserts at
/// least one).
fn assert_junction_angle_sequence_valid<T: IsRing>(
    glued: &EPatch<T>,
    mi: &Arc<MatchTypeIndex<T>>,
    label: &str,
) {
    let tileset = mi.tileset();
    let mut checked = 0;
    for pos in 0..glued.len() {
        let jt = match glued.junction_type_at(pos) {
            Some(jt) => jt,
            None => continue,
        };
        let angles = junction_angle_sequence::<T>(&jt, tileset.as_ref());
        let (witness, wpos) =
            EPatch::construct_minimal_witness(&jt, Arc::clone(mi)).expect("witness");
        assert_eq!(
            *angles.last().unwrap(),
            witness.angles()[wpos],
            "{label}: last angle should match witness junction angle for jt={jt:?}",
        );
        assert!(
            angles[0] > 0,
            "{label}: seed angle should be positive for jt={jt:?} (convex-tile invariant)",
        );
        for i in 1..angles.len() {
            assert!(
                angles[i] <= angles[i - 1],
                "{label}: angles should be monotone decreasing at i={i} for jt={jt:?}: {angles:?}",
            );
        }
        checked += 1;
    }
    assert!(checked > 0, "{label}: expected at least one junction");
}

#[test]
fn edges_mixed_consistency() {
    let hex_snake: Snake<ZZ12> = tiles::hexagon();
    let sq_snake: Snake<ZZ12> = tiles::square();
    let hex_rat = Rat::try_from(&hex_snake).unwrap();
    let sq_rat = Rat::try_from(&sq_snake).unwrap();
    let ts = Arc::new(TileSet::new(vec![hex_rat, sq_rat]));

    for seed_id in 0..ts.num_tiles() {
        let seed = EPatch::<ZZ12>::single_tile(Arc::clone(&ts), seed_id);
        for pm in seed.get_all_matches() {
            if let Some(gp2) = seed.with_tile(&pm) {
                verify_edges_consistency(&gp2, &ts, &format!("mixed seed={} pm {:?}", seed_id, pm));
            }
        }
    }
}

#[test]
fn brute_force_squares_up_to_4_tiles() {
    let sq: Snake<ZZ4> = tiles::square();
    let rat = Rat::try_from(&sq).unwrap();
    let ts = TileSet::single(rat);
    let patches = brute_force_patches(&ts, 4);

    let mut by_tiles: BTreeMap<usize, (usize, usize)> = BTreeMap::new();
    for ways in patches.values() {
        let n = ways[0].len() + 1;
        let e = by_tiles.entry(n).or_insert((0, 0));
        e.0 += 1;
        e.1 += ways.len();
    }

    assert_eq!(
        by_tiles.get(&1).map(|(s, _)| *s).unwrap_or(0),
        1,
        "1 mono-square"
    );
    assert_eq!(by_tiles.get(&2), Some(&(1, 16)), "1 bi-square, 16 ways");
    assert!(
        by_tiles.get(&3).map(|(s, _)| *s).unwrap_or(0) >= 2,
        "at least 2 tri-squares"
    );
}

#[test]
fn brute_force_hexagons_up_to_3_tiles() {
    let hex: Snake<ZZ12> = tiles::hexagon();
    let rat = Rat::try_from(&hex).unwrap();
    let ts = TileSet::single(rat);
    let patches = brute_force_patches(&ts, 3);

    let mut by_tiles: BTreeMap<usize, usize> = BTreeMap::new();
    for ways in patches.values() {
        let n = ways[0].len() + 1;
        by_tiles.entry(n).and_modify(|c| *c += 1).or_insert(1);
    }

    assert_eq!(by_tiles.get(&1).copied().unwrap_or(0), 1, "1 mono-hex");
    assert_eq!(by_tiles.get(&2).copied().unwrap_or(0), 1, "1 bi-hex");
    assert!(
        by_tiles.get(&3).copied().unwrap_or(0) >= 1,
        "at least 1 tri-hex"
    );
}

fn brute_force_recurse<T: IsRing>(
    gp: &mut EPatch<T>,
    history: &mut Vec<PatchMatch>,
    max_tiles: usize,
    results: &mut BTreeMap<Rat<T>, Vec<Vec<PatchMatch>>>,
) {
    let num_tiles = history.len() + 1;
    let rat = gp.to_rat();
    results.entry(rat).or_default().push(history.clone());

    if num_tiles >= max_tiles {
        return;
    }

    for pm in &gp.get_all_matches() {
        let mut gp2 = gp.clone();
        if gp2.add_tile(pm).is_some() {
            history.push(*pm);
            brute_force_recurse(&mut gp2, history, max_tiles, results);
            history.pop();
        }
    }
}

fn brute_force_patches<T: IsRing>(
    ts: &Arc<TileSet<T>>,
    max_tiles: usize,
) -> BTreeMap<Rat<T>, Vec<Vec<PatchMatch>>> {
    let mut results: BTreeMap<Rat<T>, Vec<Vec<PatchMatch>>> = BTreeMap::new();
    results
        .entry(ts.rat(0).clone())
        .or_default()
        .push(Vec::new());

    let seed = EPatch::single_tile(Arc::clone(ts), 0);
    let seed_matches = seed.get_all_matches();
    for pm in &seed_matches {
        let mut gp = seed.with_tile(pm).expect("first add");
        let mut history = vec![*pm];
        brute_force_recurse(&mut gp, &mut history, max_tiles, &mut results);
    }

    results
}

#[test]
fn inner_petals_empty_after_first_glue() {
    let seed = hex_seed();
    let pm = seed.get_all_matches()[0];
    let gp2 = seed.with_tile(&pm).expect("first add");
    for (i, chain) in gp2.inner_petals().iter().enumerate() {
        assert!(
            chain.is_empty(),
            "inner chain at position {i} should be empty after first glue, got {chain:?}"
        );
    }
}

#[test]
fn inner_petals_grow_on_second_glue() {
    let seed = hex_seed();
    let first_match = seed.get_all_matches()[0];
    let gp2 = seed.with_tile(&first_match).expect("first add");

    let candidates = gp2.get_all_matches();
    let second = candidates
        .iter()
        .find(|pm| pm.len() == 1)
        .expect("need len-1 match");
    let mut gp3 = gp2.clone();
    assert!(gp3.add_tile(second).is_some(), "second add");

    let n = gp3.len();
    let edges = gp3.edges();
    let ptids = gp3.patch_tile_ids();
    let inners = gp3.inner_petals();

    for pos in 0..n {
        let prev = (pos + n - 1) % n;
        let cw_ptid = ptids[prev];
        let ccw_ptid = ptids[pos];
        for entry in &inners[pos] {
            assert_ne!(
                entry.tile_type_id, edges[prev].tile_type_id,
                "inner at {pos} should not be from CW tile"
            );
            assert_ne!(
                entry.tile_type_id, edges[pos].tile_type_id,
                "inner at {pos} should not be from CCW tile"
            );
            assert!(
                cw_ptid != ccw_ptid || inners[pos].is_empty(),
                "when CW and CCW have same ptid, inner should be empty at {pos}"
            );
        }
    }
}

#[test]
fn junction_type_roundtrip_after_first_glue() {
    let seed = hex_seed();
    let pm = seed.get_all_matches()[0];
    let gp2 = seed.with_tile(&pm).expect("first add");
    let n = gp2.len();
    let mut junction_count = 0;
    for i in 0..n {
        if let Some(jt) = gp2.junction_type_at(i) {
            assert!(jt.inner.is_empty(), "inner should be empty at pos {i}");
            junction_count += 1;
        }
    }
    assert!(junction_count > 0, "should have at least one junction");
}

#[test]
fn construct_minimal_witness_hex_roundtrip() {
    let seed = hex_seed();
    let mi = seed.match_index().clone();
    for pm in seed.get_all_matches() {
        let glued = seed.with_tile(&pm).expect("glue should succeed");
        assert_minimal_witness_roundtrips_for(&glued, &mi, &format!("hex pm {:?}", pm));
    }
}

#[test]
fn construct_minimal_witness_square_roundtrip() {
    let seed = square_seed();
    let mi = seed.match_index().clone();
    for pm in seed.get_all_matches() {
        let glued = seed.with_tile(&pm).expect("glue should succeed");
        assert_minimal_witness_roundtrips_for(&glued, &mi, &format!("square pm {:?}", pm));
    }
}

#[test]
fn construct_minimal_witness_hex_with_inner() {
    let seed = hex_seed();
    let mi = seed.match_index().clone();
    let first = seed.get_all_matches()[0];
    let gp2 = seed.with_tile(&first).expect("first add");

    let len1_match = gp2
        .get_all_matches()
        .into_iter()
        .find(|pm| pm.len() == 1)
        .expect("need len-1 match");
    let mut gp3 = gp2.clone();
    assert!(gp3.add_tile(&len1_match).is_some(), "second add");

    assert_minimal_witness_roundtrips_for(&gp3, &mi, "hex two-glue with inner");
}
#[test]
fn compute_candidates_covering_position_matches_full_enumeration() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre()).unwrap(),
    ]));
    let mi: Arc<MatchTypeIndex<ZZ12>> = Arc::new(MatchTypeIndex::new(Arc::clone(&ts)));
    let gp = grow_first(Arc::clone(&ts));

    let all_cands = EPatch::compute_all_candidates(&mi, gp.angles(), gp.edges());
    let n = gp.angles().len();
    let sort_key = |pm: &PatchMatch| {
        (
            pm.a_range.start_offset,
            pm.len(),
            pm.b.range.start_offset,
            pm.b.tile_id,
        )
    };

    for target in 0..n {
        let mut covering =
            EPatch::compute_candidates_covering_position(&mi, gp.angles(), gp.edges(), target);

        // Ground truth: every match in the full enumeration that touches
        // `target`. Compared as multisets via sorting.
        let mut touching_truth: Vec<PatchMatch> = all_cands
            .iter()
            .flatten()
            .filter(|pm| cyclic_range_contains(pm.a_range.start_offset, pm.len(), target, n))
            .cloned()
            .collect();

        covering.sort_by_key(sort_key);
        touching_truth.sort_by_key(sort_key);
        assert_eq!(
            covering, touching_truth,
            "covering vs touching-from-all mismatch at target={target}",
        );
    }
}

/// Snapshot of externally observable patch state plus a probe of the
/// internal spatial grid via candidate accept/reject classification.
/// Two patches with equal snapshots behave identically against further
/// `add_tile` attempts -- grid corruption would show up as a different
/// reject set even when angles/edges/etc. are still equal.
fn classify_candidates<T: IsRing>(gp: &EPatch<T>) -> Vec<(PatchMatch, bool)> {
    let mut results: Vec<(PatchMatch, bool)> = gp
        .get_all_matches()
        .into_iter()
        .map(|pm| {
            let mut trial = gp.clone();
            let ok = trial.add_tile(&pm).is_some();
            (pm, ok)
        })
        .collect();
    results.sort_by_key(|(pm, _)| {
        (
            pm.a_range.start_offset,
            pm.len(),
            pm.b.range.start_offset,
            pm.b.tile_id,
        )
    });
    results
}

/// Snapshot every publicly observable component of a growing patch,
/// plus the candidate classification (which doubles as a grid probe).
#[allow(clippy::type_complexity)]
fn snapshot_growing<T: IsRing>(
    gp: &EPatch<T>,
) -> (
    Vec<i8>,
    Vec<EdgeInfo>,
    Vec<Vec<EdgeInfo>>,
    Vec<usize>,
    usize,
    usize,
    Vec<(PatchMatch, bool)>,
) {
    (
        gp.angles().to_vec(),
        gp.edges().to_vec(),
        gp.inner_petals().to_vec(),
        gp.patch_tile_ids().to_vec(),
        gp.next_tile_id(),
        gp.len(),
        classify_candidates(gp),
    )
}

/// The only legitimate rejection path in `add_tile_growing` is the
/// geometric collision check (`check_edge_clear`) -- paths 1, 2, 4
/// are invariants that legitimate callers (`get_all_matches`) never
/// violate. This test exercises path 3 against a 2-spectre patch and
/// asserts that the full patch state (plus a grid probe via candidate
/// classification) is byte-identical after the failed `add_tile`.
#[test]
fn add_tile_failure_leaves_state_unchanged() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre()).unwrap(),
    ]));
    let mut gp = grow_first(Arc::clone(&ts));
    let before = snapshot_growing(&gp);
    let failing_pm = before
        .6
        .iter()
        .find(|(_, ok)| !*ok)
        .map(|(pm, _)| *pm)
        .expect("expected at least one colliding candidate");
    assert!(
        gp.add_tile(&failing_pm).is_none(),
        "must reject a colliding candidate",
    );
    assert_eq!(
        snapshot_growing(&gp),
        before,
        "state changed after a geometrically-rejected pm",
    );
}

/// `get_all_matches()` returns edge-compatible candidates without
/// checking spatial overlap (it only filters via single-edge
/// compatibility and angle math). For non-convex tiles like spectre,
/// some of those candidates would self-intersect with existing tiles,
/// and `add_tile`'s `check_edge_clear` path is the safety net that
/// catches them. This test pins that behavior: at least one returned
/// candidate must be rejected, and at least one must be accepted (so
/// we know the candidate list is non-trivial).
#[test]
fn add_tile_rejects_geometrically_invalid_candidate() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre()).unwrap(),
    ]));
    let gp = grow_first(Arc::clone(&ts));

    let candidates = gp.get_all_matches();
    let (mut accepted, mut rejected) = (0usize, 0usize);
    for pm in &candidates {
        let mut trial = gp.clone();
        if trial.add_tile(pm).is_some() {
            accepted += 1;
        } else {
            rejected += 1;
        }
    }
    assert!(
        rejected > 0,
        "expected at least one geometrically-invalid candidate to be rejected; \
             all {} candidates were accepted",
        candidates.len()
    );
    assert!(
        accepted > 0,
        "expected at least one valid candidate to be accepted; all {} rejected",
        candidates.len()
    );
}

/// Cross-check between the two independent geometric implementations:
/// EPatch's incremental check (which maintains a UnitSquareGrid
/// across glues that remove multiple segments and add new ones with an
/// allowed-endpoint exception) versus Snake's batch validator (which
/// walks the resulting boundary segment-by-segment from origin and
/// checks each new segment against the previously visited ones).
///
/// Both ultimately use the same `intersect` + `UnitSquareGrid` primitive
/// but compose it differently. They must agree on accept/reject for
/// every candidate.
///
/// Skips candidates that would produce +/-hturn (Snake panics on hturn,
/// and `compute_glue_angles` would have already rejected them at the
/// add_tile level -- the two paths trivially agree there).
#[test]
fn add_tile_decision_agrees_with_snake_on_spectre() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre()).unwrap(),
    ]));
    let gp = grow_first(Arc::clone(&ts));

    let candidates = gp.get_all_matches();
    let tileset = gp.tileset().clone();
    let mut compared = 0usize;
    let mut discrepancies: Vec<(PatchMatch, bool, bool)> = Vec::new();

    for pm in &candidates {
        let new_angles = match compute_glue_angles::<ZZ12>(gp.angles(), pm, &tileset) {
            Ok(a) => a,
            Err(_) => continue,
        };
        let snake_ok = Snake::<ZZ12>::try_from(new_angles.as_slice()).is_ok();
        let mut trial = gp.clone();
        let gp_ok = trial.add_tile(pm).is_some();
        if snake_ok != gp_ok {
            discrepancies.push((*pm, snake_ok, gp_ok));
        }
        compared += 1;
    }

    assert!(compared > 0, "expected non-zero candidates to compare");
    assert!(
        discrepancies.is_empty(),
        "Snake and add_tile disagreed on {} of {} candidates: {:?}",
        discrepancies.len(),
        compared,
        discrepancies
    );
}

/// After every successful `add_tile`, the resulting boundary should
/// be a valid (non-self-intersecting) closed Snake polygon. Spectre
/// is the right fixture because it has a non-convex shape -- most of
/// the candidate boundaries are non-trivial.
#[test]
fn growing_patch_boundary_validates_as_snake_through_growth() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre()).unwrap(),
    ]));
    let mut gp = grow_first(Arc::clone(&ts));
    // First snake check before any further growth.
    {
        let angles = gp.angles().to_vec();
        let snake = Snake::<ZZ12>::try_from(angles.as_slice());
        assert!(
            snake.is_ok(),
            "step 0: snake validation failed: angles={angles:?}"
        );
        assert!(
            snake.unwrap().is_closed(),
            "step 0: boundary should close as a polygon"
        );
    }
    let mut step = 1usize;
    while step < 4 {
        let pm = match gp.get_all_matches().first() {
            Some(pm) => *pm,
            None => break,
        };
        if gp.add_tile(&pm).is_none() {
            break;
        }
        let angles = gp.angles().to_vec();
        let snake = Snake::<ZZ12>::try_from(angles.as_slice());
        assert!(
            snake.is_ok(),
            "step {step}: EPatch's boundary failed Snake validation: angles={angles:?}"
        );
        assert!(
            snake.unwrap().is_closed(),
            "step {step}: EPatch's boundary should close as a polygon"
        );
        step += 1;
    }
    assert!(step > 0, "expected at least one successful add");
}

/// Brute-force candidate enumeration independent of `MatchTypeIndex`.
///
/// `compute_all_candidates` (and therefore `get_all_matches`) relies on
/// the pre-computed `MatchTypeIndex::candidates_starting_at` index for
/// the segment path, and direct iteration for the junction path. This
/// test brute-forces every `(tile_id_b, ib, start_a)` triple and
/// applies the same downstream filters
/// (`junctions_glueable`, `try_glue_match`), so a mismatch
/// against `get_all_matches()` would indicate a bug in either the
/// index or the segment/junction routing.
#[test]
fn get_all_matches_matches_brute_force_on_spectre() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre()).unwrap(),
    ]));
    let gp = grow_first(Arc::clone(&ts));

    let n = gp.len();
    let rat = Rat::from_slice_trusted(gp.angles());

    let mut brute: std::collections::BTreeSet<(usize, usize, usize, usize)> =
        std::collections::BTreeSet::new();
    for tile_id_b in 0..ts.num_tiles() {
        let tile_b = ts.rat(tile_id_b);
        let b_seq = tile_b.seq();
        let m_tile = b_seq.len();
        for ib in 0..m_tile {
            for start_a in 0..n {
                let (ns, len, ne) = rat
                    .get_match(MatchSeed::new(start_a as i64, ib as i64), tile_b)
                    .parts();
                if len == 0 {
                    continue;
                }
                let ns_u = ns;
                let ne_u = ne;
                if !crate::geom::glue::junctions_glueable(gp.angles(), ns_u, len, b_seq, ne_u) {
                    continue;
                }
                if rat
                    .try_glue_match(
                        Match::new(EdgeRange::new(ns, len), EdgeRange::new(ne, len)),
                        tile_b,
                        Validation::Local,
                    )
                    .is_ok()
                {
                    brute.insert((ns_u, len, ne_u, tile_id_b));
                }
            }
        }
    }

    let from_api: std::collections::BTreeSet<(usize, usize, usize, usize)> = gp
        .get_all_matches()
        .into_iter()
        .map(|pm| {
            (
                pm.a_range.start_offset,
                pm.len(),
                pm.b.range.start_offset,
                pm.b.tile_id,
            )
        })
        .collect();

    assert_eq!(
        brute, from_api,
        "brute-force candidate set differs from get_all_matches()"
    );
}

/// Like `get_all_matches_matches_brute_force_on_spectre` but for
/// `get_matches_touching_vertex`: brute-force enumerate all matches,
/// filter by `cyclic_range_contains(start_a, len, v, n)` for each
/// vertex `v`, and compare against the per-vertex fast path.
#[test]
fn get_matches_touching_vertex_matches_brute_force_on_spectre() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre()).unwrap(),
    ]));
    let gp = grow_first(Arc::clone(&ts));

    let n = gp.len();
    let rat = Rat::from_slice_trusted(gp.angles());

    let mut brute_matches: Vec<PatchMatch> = Vec::new();
    for tile_id_b in 0..ts.num_tiles() {
        let tile_b = ts.rat(tile_id_b);
        let b_seq = tile_b.seq();
        let m_tile = b_seq.len();
        for ib in 0..m_tile {
            for start_a in 0..n {
                let (ns, len, ne) = rat
                    .get_match(MatchSeed::new(start_a as i64, ib as i64), tile_b)
                    .parts();
                if len == 0 {
                    continue;
                }
                let ns_u = ns;
                let ne_u = ne;
                if !crate::geom::glue::junctions_glueable(gp.angles(), ns_u, len, b_seq, ne_u) {
                    continue;
                }
                if rat
                    .try_glue_match(
                        Match::new(EdgeRange::new(ns, len), EdgeRange::new(ne, len)),
                        tile_b,
                        Validation::Local,
                    )
                    .is_ok()
                {
                    brute_matches.push(PatchMatch::new(
                        EdgeRange::new(ns_u, len),
                        Segment::new(tile_id_b, EdgeRange::new(ne_u, len)),
                    ));
                }
            }
        }
    }
    // Dedup the brute set (the (start_a, ib) double-counts hit the same
    // canonical match).
    let brute_set: std::collections::BTreeSet<(usize, usize, usize, usize)> = brute_matches
        .iter()
        .map(|pm| {
            (
                pm.a_range.start_offset,
                pm.len(),
                pm.b.range.start_offset,
                pm.b.tile_id,
            )
        })
        .collect();

    for target in 0..n {
        // Brute-side filter must NOT use `cyclic_range_contains`,
        // otherwise this cross-check is circular (a bug in
        // `cyclic_range_contains` would affect both sides
        // identically and pass). We instead use an explicit
        // "vertex `target` is in `{start, start+1, ..., start+len}`
        // mod n" check via modular arithmetic -- independent of the
        // function under test.
        let touching_brute: std::collections::BTreeSet<(usize, usize, usize, usize)> = brute_set
            .iter()
            .copied()
            .filter(|(start_a, len, _, _)| {
                let cyclic_diff = (target + n - *start_a % n) % n;
                cyclic_diff <= *len
            })
            .collect();
        let touching_api: std::collections::BTreeSet<(usize, usize, usize, usize)> = gp
            .get_matches_touching_vertex(target)
            .into_iter()
            .map(|pm| {
                (
                    pm.a_range.start_offset,
                    pm.len(),
                    pm.b.range.start_offset,
                    pm.b.tile_id,
                )
            })
            .collect();
        assert_eq!(
            touching_brute, touching_api,
            "mismatch at target={target}: brute={touching_brute:?} api={touching_api:?}"
        );
    }
}

/// `neighbor_junction_offsets(pos)` returns offsets into the CW and CCW
/// neighbouring junctions' tile sequences. The returned values must
/// (a) be within the relevant tile's length and (b) correctly identify
/// the CW junction's edge and the (ccw_prev + 1) offset of the CCW
/// junction's preceding edge.
#[test]
fn neighbor_junction_offsets_returns_valid_offsets() {
    let seed = hex_seed();
    let pm = *seed
        .get_all_matches()
        .iter()
        .find(|p| p.len() == 1)
        .expect("len-1 hex match");
    let gp = seed.with_tile(&pm).expect("fixture");
    let n = gp.len();
    let edges = gp.edges().to_vec();
    let ts = gp.tileset().clone();

    for pos in 0..n {
        let (cw_off, ccw_off) = gp
            .neighbor_junction_offsets(pos)
            .expect("Some for valid pos");

        // Walk CW to the nearest junction (possibly == pos itself).
        let mut j_cw = (pos + n - 1) % n;
        while j_cw != pos && !gp.is_junction(j_cw) {
            j_cw = (j_cw + n - 1) % n;
        }
        let cw_tile_len = ts.rat(edges[j_cw].tile_type_id).len();
        assert!(cw_off < cw_tile_len, "cw_off out of range at pos {pos}");
        assert_eq!(
            cw_off, edges[j_cw].canon_offset,
            "cw_off should be the CW junction's tile_offset at pos {pos}",
        );

        // Walk CCW to the nearest junction.
        let mut j_ccw = (pos + 1) % n;
        while j_ccw != pos && !gp.is_junction(j_ccw) {
            j_ccw = (j_ccw + 1) % n;
        }
        let ccw_prev_edge = edges[(j_ccw + n - 1) % n];
        let ccw_tile_len = ts.rat(ccw_prev_edge.tile_type_id).len();
        assert!(ccw_off < ccw_tile_len, "ccw_off out of range at pos {pos}");
        assert_eq!(
            ccw_off,
            (ccw_prev_edge.canon_offset + 1) % ccw_tile_len,
            "ccw_off should be (ccw_prev edge's offset + 1) at pos {pos}",
        );
    }

    // Out-of-range returns None.
    assert!(gp.neighbor_junction_offsets(n).is_none());
}

/// `tile_segments()` should:
/// (a) cover the boundary contiguously (segments concatenated from
/// 0 to `n` with no gaps),
/// (b) have segment boundaries at exactly the junction positions,
/// (c) within each segment, `tile_id` is constant and `tile_offset`
/// advances by 1 modulo the tile's edge count.
#[test]
fn tile_segments_partitions_boundary() {
    let seed = hex_seed();
    let pm = *seed
        .get_all_matches()
        .iter()
        .find(|p| p.len() == 1)
        .expect("len-1 hex match");
    let gp = seed.with_tile(&pm).expect("fixture");
    let n = gp.len();
    let edges = gp.edges().to_vec();
    let segs = gp.tile_segments();

    // Contiguous partition.
    assert_eq!(
        segs.first().map(|s| s.range.start_offset),
        Some(0),
        "first segment starts at 0"
    );
    assert_eq!(
        segs.last().map(|s| s.range.start_offset + s.range.len),
        Some(n),
        "last segment ends at n"
    );
    for w in segs.windows(2) {
        assert_eq!(
            w[0].range.start_offset + w[0].range.len,
            w[1].range.start_offset,
            "segments must be contiguous"
        );
    }

    // Consistent tile_id and contiguous offsets within each segment.
    for seg in &segs {
        let tile_id = seg.tile_seg.tile_id;
        let tile_len = gp.tileset().rat(tile_id).len();
        for k in 0..seg.range.len {
            let pos = seg.range.start_offset + k;
            assert_eq!(edges[pos].tile_type_id, tile_id, "tile_id at pos {pos}");
            assert_eq!(
                edges[pos].canon_offset,
                (seg.tile_seg.range.start_offset + k) % tile_len,
                "tile_offset at pos {pos}",
            );
        }
    }

    // A position is a segment start iff it is position 0 (the
    // linear-partition seam, always present) or a junction.
    let expected_starts: std::collections::BTreeSet<usize> = std::iter::once(0)
        .chain((0..n).filter(|&i| gp.is_junction(i)))
        .collect();
    let actual_starts: std::collections::BTreeSet<usize> =
        segs.iter().map(|s| s.range.start_offset).collect();
    assert_eq!(
        actual_starts, expected_starts,
        "segment starts must equal {{0}} union junctions"
    );
}

#[test]
fn construct_minimal_witness_hex_boundary_matches_brute_force() {
    let seed = hex_seed();
    let mi = seed.match_index().clone();
    for pm in seed.get_all_matches() {
        let brute = seed.with_tile(&pm).expect("brute glue");
        assert_witness_matches_brute_force(&brute, &mi, &format!("hex pm {:?}", pm));
    }
}

#[test]
fn construct_minimal_witness_square_boundary_matches_brute_force() {
    let seed = square_seed();
    let mi = seed.match_index().clone();
    for pm in seed.get_all_matches() {
        let brute = seed.with_tile(&pm).expect("brute glue");
        assert_witness_matches_brute_force(&brute, &mi, &format!("square pm {:?}", pm));
    }
}

#[test]
fn construct_minimal_witness_spectre_roundtrip() {
    let ts: Arc<TileSet<ZZ12>> = Arc::new(TileSet::new(vec![
        Rat::try_from(&tiles::spectre()).unwrap(),
    ]));
    let gp = grow_first(Arc::clone(&ts));
    let mi = gp.match_index().clone();
    assert_minimal_witness_roundtrips_for(&gp, &mi, "spectre first-glue");
}

#[test]
fn forward_match_length_hex_basic() {
    let hex: Snake<ZZ12> = tiles::hexagon();
    let rat = Rat::try_from(&hex).unwrap();
    let seq = rat.seq();

    assert_eq!(forward_match_length(seq, 0, seq, 0), 1);
    assert_eq!(forward_match_length(seq, 3, seq, 3), 1);
    assert_eq!(forward_match_length(seq, 0, seq, 1), 1);

    let boundary: Vec<i8> = vec![-2, 2, 2, 2, 2, -2, 2, 2, 2, 2];
    assert_eq!(forward_match_length(&boundary, 5, seq, 0), 1);
    assert_eq!(forward_match_length(&boundary, 0, seq, 0), 1);
}

#[test]
fn forward_match_length_square_basic() {
    let sq: Snake<ZZ4> = tiles::square();
    let rat = Rat::try_from(&sq).unwrap();
    let seq = rat.seq();

    assert_eq!(forward_match_length(seq, 0, seq, 0), 1);
    assert_eq!(forward_match_length(seq, 2, seq, 2), 1);
}

#[test]
fn glue_raw_angles_hex_self_glue() {
    let hex: Snake<ZZ12> = tiles::hexagon();
    let rat = Rat::try_from(&hex).unwrap();
    let seq = rat.seq().to_vec();

    let result = glue::glue_raw_angles::<ZZ12>(&seq, &seq, 0, 1, 0);
    assert!(result.is_some());
    let gr = result.unwrap();
    assert_eq!(gr.angles.len(), 10);
    assert_eq!(gr.a_yx, Some(-2));
    assert_eq!(gr.a_xy, Some(-2));
}

#[test]
fn glue_raw_angles_matches_rat_glue() {
    let hex: Snake<ZZ12> = tiles::hexagon();
    let rat = Rat::try_from(&hex).unwrap();
    let seq = rat.seq();

    let rat_result = rat.try_glue(MatchSeed::new(0, 0), &rat).expect("rat glue");
    let raw_result = glue::glue_raw_angles::<ZZ12>(seq, seq, 0, 1, 0).expect("raw glue");

    // Both glue paths must produce the same boundary up to cyclic
    // rotation (they may pick different starting positions).
    assert_same_cyclic_shape(rat_result.seq(), &raw_result.angles, "rat vs raw glue");
}

#[test]
fn test_junction_angle_sequence_hex() {
    let seed = hex_seed();
    let mi = seed.match_index().clone();
    for pm in seed.get_all_matches() {
        let glued = seed.with_tile(&pm).expect("glue");
        assert_junction_angle_sequence_valid(&glued, &mi, &format!("hex pm {:?}", pm));
    }
}

#[test]
fn construct_witness_from_jt_sequence_single_vt_roundtrip() {
    let seed = hex_seed();
    let mi = seed.match_index().clone();
    let pm = *seed
        .get_all_matches()
        .iter()
        .find(|pm| pm.len() == 1)
        .expect("len-1 match");
    let gp = seed.with_tile(&pm).expect("first glue");

    let jt = gp.junction_type_at(0).expect("junction at 0");

    let (minimal, _wpos) =
        EPatch::construct_minimal_witness(&jt, mi.clone()).expect("minimal witness");

    let (reconstructed, _junc_positions) =
        EPatch::construct_witness_from_jt_sequence(std::slice::from_ref(&jt), mi)
            .expect("reconstruction");

    // construct_minimal_witness delegates to
    // construct_witness_from_jt_sequence for single-element input,
    // so the two outputs must be byte-identical, not just congruent.
    assert_eq!(minimal.angles(), reconstructed.angles());
    assert_eq!(minimal.edges(), reconstructed.edges());
    assert_eq!(minimal.inner_petals(), reconstructed.inner_petals());
}

/// Build a 5-hexagon plus-shaped cross: a central hex with four
/// hexagons attached on alternating sides. The resulting patch has
/// 18 boundary edges and 6 junctions arranged symmetrically.
///
/// The four glues are pinned as literal `PatchMatch` values (targeted boundary
/// lengths after each step: 10 -> 14 -> 16 -> 18), so the fixture is
/// reproducible and independent of `get_all_matches` iteration order.
/// `five_hex_cross_structure` verifies the boundary symmetry, junction count,
/// and tile-id pattern.
fn five_hex_cross() -> EPatch<ZZ12> {
    // Five hexagons arranged as a cross: one central hex with four
    // petals on opposite-pair edges (= a 2-axis-symmetric shape,
    // 18-edge boundary). Glue sequence pinned to literal
    // PatchMatch values for reproducibility; targeted boundary
    // lengths after each step are 10, 14, 16, 18.
    let glues = [
        PatchMatch::new(EdgeRange::new(0, 1), Segment::new(0, EdgeRange::new(0, 1))),
        PatchMatch::new(EdgeRange::new(1, 1), Segment::new(0, EdgeRange::new(1, 1))),
        PatchMatch::new(EdgeRange::new(2, 2), Segment::new(0, EdgeRange::new(1, 2))),
        PatchMatch::new(EdgeRange::new(9, 2), Segment::new(0, EdgeRange::new(1, 2))),
    ];
    build_from_glues(hex_seed(), &glues, "five_hex_cross")
}

#[test]
fn five_hex_cross_structure() {
    let gp = five_hex_cross();
    let n = gp.len();
    assert_eq!(n, 18);

    let angles = gp.angles();
    assert_eq!(&angles[..9], &angles[9..], "boundary should be symmetric");

    let junctions: Vec<usize> = (0..n).filter(|&i| gp.is_junction(i)).collect();
    assert_eq!(junctions.len(), 6);

    let mut segs: Vec<usize> = Vec::new();
    for w in junctions.windows(2) {
        segs.push(w[1] - w[0]);
    }
    segs.push(n - junctions[5] + junctions[0]);
    assert_eq!(
        segs,
        vec![1, 4, 4, 1, 4, 4],
        "junction offsets should be 1,4,4,1,4,4"
    );

    for i in 0..n {
        let prev = (i + n - 1) % n;
        let id = gp.patch_tile_ids()[i];
        let prev_id = gp.patch_tile_ids()[prev];
        if gp.is_junction(i) {
            assert_ne!(
                id, prev_id,
                "junction at {i} should have distinct patch_tile_ids"
            );
        }
    }

    let mut run_start = 0;
    let mut runs: Vec<(usize, usize)> = Vec::new();
    for i in 1..=n {
        if i == n || gp.patch_tile_ids()[i] != gp.patch_tile_ids()[run_start] {
            runs.push((gp.patch_tile_ids()[run_start], i - run_start));
            run_start = i;
        }
    }
    assert_eq!(runs.len(), 6, "should have 6 runs of patch_tile_ids");
    let center_runs: Vec<&(usize, usize)> = runs.iter().filter(|(id, _)| *id == 0).collect();
    assert_eq!(
        center_runs.len(),
        2,
        "center tile should appear in exactly 2 runs"
    );
    assert_eq!(center_runs[0].1, 1, "each center run should be 1 edge");
    assert_eq!(center_runs[1].1, 1, "each center run should be 1 edge");
}

#[test]
fn reconstruct_five_hex_cross() {
    let gp = five_hex_cross();
    let mi = gp.match_index().clone();

    let n = gp.len();
    let mut jt_seq: Vec<OpenJunctionType> = Vec::new();
    for i in 0..n {
        if gp.is_junction(i) {
            let jt = gp.junction_type_at(i).unwrap();
            assert!(
                jt.inner.is_empty(),
                "hex boundary junctions should have empty inner"
            );
            jt_seq.push(jt);
        }
    }
    assert_eq!(jt_seq.len(), 6);

    let result = EPatch::construct_witness_from_jt_sequence(&jt_seq, mi);
    let (reconstructed, _junc_positions) = result.expect("reconstruction should succeed");

    assert_same_cyclic_shape(
        gp.angles(),
        reconstructed.angles(),
        "5-hex-cross: reconstructed vs original",
    );
    assert_eq!(
        reconstructed.len(),
        gp.len(),
        "boundary length should match"
    );

    let recon_juncs: Vec<usize> = (0..reconstructed.len())
        .filter(|&i| reconstructed.is_junction(i))
        .collect();
    assert_eq!(recon_juncs.len(), 6, "should have 6 junctions");
}

#[test]
fn next_junction_on_boundary_finds_all_junctions() {
    let seed = hex_seed();

    let pm = *seed
        .get_all_matches()
        .iter()
        .find(|pm| pm.len() == 1)
        .expect("len-1 match");
    let gp = seed.with_tile(&pm).expect("first glue");

    let n = gp.len();
    let junctions: Vec<usize> = (0..n).filter(|&i| gp.is_junction(i)).collect();
    assert_eq!(junctions.len(), 2, "two-hex should have 2 junctions");

    let j1 = next_junction_on_boundary(&gp, junctions[0]).expect("should find next junction");
    assert_eq!(j1, junctions[1], "should find the other junction");

    let j0 = next_junction_on_boundary(&gp, junctions[1]).expect("should wrap around");
    assert_eq!(j0, junctions[0], "should wrap to first junction");
}

#[test]
fn test_junction_angle_sequence_square() {
    let seed = square_seed();
    let mi = seed.match_index().clone();
    for pm in seed.get_all_matches() {
        let glued = seed.with_tile(&pm).expect("glue");
        assert_junction_angle_sequence_valid(&glued, &mi, &format!("square pm {:?}", pm));
    }
}

#[test]
fn normalize_five_hex_cross() {
    let gp = five_hex_cross();
    let mut gp2 = gp.clone();
    gp2.normalize();

    assert_eq!(gp2.len(), 18);

    let ptids = gp2.patch_tile_ids();
    let mut seen = std::collections::HashSet::new();
    for &id in ptids {
        seen.insert(id);
    }
    let max_id = *seen.iter().max().unwrap();
    assert_eq!(
        seen.len(),
        max_id + 1,
        "ptids should be 0..=max with no gaps"
    );
    assert_eq!(gp2.next_tile_id(), seen.len());

    let angles = gp2.angles();
    let min_angle = *angles.iter().min().unwrap();
    assert_eq!(
        angles[0], min_angle,
        "normalized boundary should start at lex-min angle"
    );
}

#[test]
fn normalize_idempotent() {
    let gp = five_hex_cross();
    let mut gp1 = gp.clone();
    gp1.normalize();
    let snap1 = (
        gp1.angles().to_vec(),
        gp1.edges().to_vec(),
        gp1.patch_tile_ids().to_vec(),
    );
    gp1.normalize();
    let snap2 = (
        gp1.angles().to_vec(),
        gp1.edges().to_vec(),
        gp1.patch_tile_ids().to_vec(),
    );
    assert_eq!(snap1, snap2, "normalize should be idempotent");
}

fn t_tetromino_angles() -> Vec<i8> {
    let snake: Snake<ZZ4> = tiles::tetromino_T();
    let rat = Rat::try_from(&snake).unwrap();
    rat.seq().to_vec()
}

/// Build the T-tetromino -- 4 unit squares in a T shape:
///
/// ```text
///     +---+
///     |   |
/// +---+   +---+
/// |             |
/// +---+---+---+
/// ```
///
/// Glues three squares onto the seed via pinned literal `PatchMatch` values
/// (each a `(start_a, len, start_b)` triple). Per-step boundary length
/// assertions (square seed: 4 edges; bi-square: 6; tri-square: 8; T: 10) catch
/// the case where the match-finder semantics drift such that the pinned triple
/// produces a different shape.
fn t_tetromino() -> EPatch<ZZ4> {
    // T-tetromino built incrementally as a chain of 4 unit
    // squares: pin each glue's PatchMatch directly. Boundary
    // length grows 4 -> 6 -> 8 -> 10.
    let glues = [
        // seed 4 -> 6: attach the second square to the seed's edge 0.
        PatchMatch::new(EdgeRange::new(0, 1), Segment::new(0, EdgeRange::new(0, 1))),
        // 6 -> 8: extend the chain off the new boundary edge 0.
        PatchMatch::new(EdgeRange::new(0, 1), Segment::new(0, EdgeRange::new(1, 1))),
        // 8 -> 10: attach the fourth square, forming the T stem.
        PatchMatch::new(EdgeRange::new(0, 1), Segment::new(0, EdgeRange::new(1, 1))),
    ];
    let gp = build_from_glues(square_seed(), &glues, "t_tetromino");
    assert_eq!(gp.len(), 10, "T-tetromino should have 10 edges");
    gp
}

#[test]
fn reconstruct_t_tetromino() {
    let gp = t_tetromino();
    let mi = gp.match_index().clone();
    let n = gp.len();
    assert_eq!(n, 10);

    let ref_angles = t_tetromino_angles();
    assert_same_cyclic_shape(
        gp.angles(),
        &ref_angles,
        "built patch should be the T tetromino shape",
    );

    let mut jt_seq: Vec<OpenJunctionType> = Vec::new();
    for i in 0..n {
        if gp.is_junction(i) {
            let jt = gp.junction_type_at(i).unwrap();
            jt_seq.push(jt);
        }
    }
    assert!(!jt_seq.is_empty(), "T should have junctions");

    let has_inner = jt_seq.iter().any(|jt| !jt.inner.is_empty());
    assert!(
        has_inner,
        "T tetromino should have junctions with non-empty inner"
    );

    let result = EPatch::construct_witness_from_jt_sequence(&jt_seq, mi);
    let (reconstructed, _junc_positions) = result.expect("reconstruction should succeed");

    assert_eq!(reconstructed.len(), n, "boundary length should match");

    assert_same_cyclic_shape(
        reconstructed.angles(),
        &ref_angles,
        "reconstructed angles should match T",
    );

    let recon_juncs: Vec<usize> = (0..reconstructed.len())
        .filter(|&i| reconstructed.is_junction(i))
        .collect();
    assert_eq!(
        recon_juncs.len(),
        jt_seq.len(),
        "junction count should match"
    );
}