tilezz 0.2.0

//! The tile-adjacency graph of a patch, carried INLINE by [`WithAdjacency`].
//!
//! # Picture
//!
//! A patch is a set of glued tiles; its adjacency graph has one **node per tile
//! instance** (the same `patch_tile_id` the [`BasicPatch`] core assigns) and one
//! **edge per shared border** between two tiles. An edge is a [`TileMatch`] --
//! the pair of edge ranges, one on each tile, that name the shared unit edges --
//! and its [`TileMatch::involution`] is the very same border seen from the other
//! tile. So the graph invents nothing: nodes are ids the patch already tracks,
//! edges are the match info the patch already records at glue time.
//!
//! # The graph IS a patch layer
//!
//! [`WithAdjacency`] is a [`Patch`] layer that wraps a core patch and carries the
//! adjacency INLINE (`shape` + `adj`, one entry per tile instance) -- there is no
//! separate graph object. Every [`Patch`] method delegates straight to the inner
//! patch EXCEPT `add_tile`, which additionally projects the graph: it reads the
//! glue's adjacency off the PRE-glue boundary, forwards to the inner patch, and
//! registers the new node + edges only on success (the inner `None`
//! short-circuits before any push). So the graph is built DURING the corona
//! search, node `i` == patch tile instance `i`; drop the layer and the patch is
//! unaffected.
//!
//! # What one glue records
//!
//! A single glue can bury a run of boundary edges (`pm.a_range`) spanning
//! **several** owner tiles -- so one `add_tile` can create several graph edges,
//! one per distinct owner. Each consumed boundary edge already carries its owner
//! (`patch_tile_ids()[i]`) and the owner's local edge (`edges()[i].tile_offset`),
//! so the owner side of every edge is exact. The new tile's matched edges are
//! the complement of its surviving edges, `[b_start - mlen, b_start)` (see
//! `build_glued_edges` in `patch.rs`); we slice that per owner sub-run.
//!
//! # Serializing the graph back to a recipe
//!
//! [`WithAdjacency::to_recipe`] turns a grown graph into a replayable `build`
//! recipe (the inverse of the replay path), via the graph-pure `assemble` peel
//! in this module -- it reads only the [`adj`](WithAdjacency::adj) /
//! [`shape`](WithAdjacency::shape) slices, no geometry. The cert carve's own
//! coset transversal (`connected_transversal`) lives with it in
//! [`mint`](crate::classify::mint) and feeds a chosen node subset to `assemble`.

use std::sync::Arc;

use crate::cyclotomic::IsRing;
use crate::geom::matches::{EdgeRange, PatchMatch, Segment, TileMatch};
use crate::geom::patch::{BasicPatch, GlueDelta, Patch};
use crate::geom::rat::Rat;
use crate::geom::tileset::TileSet;
use crate::geom::vertices::EdgeInfo;

// --- Anti-parallel edge pairing (the one shared-border primitive) ---
//
// Two tiles glued along a common border traverse it in OPPOSITE senses: walking
// the border, one tile's local edge offsets ascend while the peer's descend. So
// a border of `len` edges pairs position `i` of one tile's forward `EdgeRange`
// with position `len - 1 - i` of the peer's. Every offset computation below
// funnels through these two helpers so the convention lives in exactly one place.

/// Peer tile-edge offset paired with border position `i`, for a peer segment
/// `s` (a forward `EdgeRange` of the border) on a tile with `m` edges.
#[inline]
pub(crate) fn peer_offset(s: &EdgeRange, i: usize, m: usize) -> usize {
    (s.start_offset + (s.len - 1 - i)) % m
}

/// If tile-edge offset `x` lies in segment `owner`, the anti-parallel partner
/// offset in the equal-length `peer` segment; else `None`.
#[inline]
pub(crate) fn partner_offset(
    owner: &EdgeRange,
    peer: &EdgeRange,
    x: usize,
    m: usize,
) -> Option<usize> {
    let i = (x + m - owner.start_offset % m) % m;
    (i < owner.len).then(|| peer_offset(peer, i, m))
}

/// Forward `EdgeRange` of the new tile's edges buried by a fresh glue over the
/// boundary sub-run `[p, p + q)`, given the glue's first-surviving-edge offset
/// `b_start` and tile size `m`. The new tile's edges descend from `b_start - 1`
/// (border position 0) as the boundary is walked, so the sub-run occupies new
/// offsets `b_start-1-p` down to `b_start-p-q+1`; its forward start (smallest)
/// is `b_start - p - q + 1`.
#[inline]
fn glue_new_range(b_start: usize, p: usize, q: usize, m: usize) -> EdgeRange {
    EdgeRange::new((b_start + 2 * m - 1 - p - (q - 1)) % m, q)
}

/// A patch layer that carries the tile-adjacency graph INLINE over a
/// [`BasicPatch`] core, building it DURING the corona search rather than by
/// replaying a recipe afterward.
///
/// # Picture
///
/// This is the graph analogue of, and an INDEPENDENT PARALLEL wrapper to,
/// [`WithJunctions`](crate::geom::patch): both wrap the same [`BasicPatch`] core
/// and project one extra layer on top of every glue, but neither depends on the
/// other. Where `WithJunctions` projects the interior junction fan (yielding
/// [`EPatch`](crate::geom::patch::EPatch)), `WithAdjacency` projects the
/// adjacency graph -- one node per glued tile (`shape[i]` is tile instance `i`'s
/// tileset shape id) and one edge per shared border (`adj[i]` holds one
/// [`TileMatch`] per incident border, oriented `a = i`, `b = neighbour`). Every
/// [`Patch`] method delegates straight to the inner patch EXCEPT `add_tile`,
/// which additionally registers the new node and the edges the glue forms (read
/// off the PRE-glue boundary). The graph is thus the true adjacency of whatever
/// patch the corona search settles on -- no second growth, no recipe replay.
///
/// The two layers are parallel, not stacked: the burial search reads junctions
/// through a supplied lookup, so the grower runs it on this bare
/// `WithAdjacency<BasicPatch>` with no junction metadata at all. Composing the
/// two wrappers into a single stack that carries both the junction fan and the
/// adjacency graph would only be needed by a hypothetical consumer wanting BOTH
/// at once; none exists.
///
/// PUBLIC API: name the [`IPatch`] typedef, not this raw wrapper -- the wrappers
/// are the generic composition mechanism, the typedefs are the intended interface
/// (see [`WithJunctions`](crate::geom::patch::WithJunctions)).
///
/// # Edge convention
///
/// BOTH segments of each edge name the shared (matched) edges directly, as
/// forward ranges. So the reverse view is the plain swap `{a: b, b: a}` -- NOT
/// [`TileMatch::involution`], which is for the asymmetric `PatchMatch` storage
/// (one side = first-surviving edge). The two edge sets are the same physical
/// unit edges on the two tiles, traversed anti-parallel. The `tile_id` fields
/// here are graph NODE ids (patch tile instances), not tileset shape ids --
/// meaning 2 of the three-way overload documented on
/// [`crate::geom::matches::Segment`].
///
/// # Node 0 is pre-seeded
///
/// [`Self::single_tile`] seeds node 0 already present, so the FIRST glue goes
/// through `add_tile` uniformly (the seed tile's boundary is just
/// `inner.edges()`); there is no special first-glue path.
///
/// # No `normalize`
///
/// Unlike [`BasicPatch`]/[`EPatch`](crate::geom::patch::EPatch), this layer
/// deliberately has NO `normalize`:
/// a graph patch is grown then consumed (the carve reads its adjacency), never
/// canonicalized. Canonicalizing would additionally need to remap the graph node
/// ids by `normalize`'s `id_perm`, which is not built -- and is not needed, since
/// nothing dedups or compares graphs (all search dedup is EXTENSIONAL, on the
/// canonical boundary, never on the interior adjacency). See patch-layering spec
/// decision 4. Calling `normalize` on this stack is therefore a compile error, by
/// design, rather than a silent no-op or a corrupting boundary-only rotation.
#[derive(Clone)]
pub struct WithAdjacency<P> {
    inner: P,
    /// node id -> the tileset shape id of that tile instance.
    shape: Vec<usize>,
    /// node id -> incident edges (each `a.tile_id == this node`).
    adj: Vec<Vec<TileMatch>>,
}

impl<P> WithAdjacency<P> {
    /// Number of tile nodes (one per tile INSTANCE glued into the patch).
    pub fn num_tiles(&self) -> usize {
        self.shape.len()
    }

    /// The edges incident to node `id` (each oriented `a = id`).
    pub fn neighbors(&self, id: usize) -> &[TileMatch] {
        &self.adj[id]
    }

    /// Number of edges incident to node `id`.
    pub fn degree(&self, id: usize) -> usize {
        self.adj[id].len()
    }

    /// The per-node incidence lists (node id -> its edges) -- the graph-pure view
    /// the cert carve reads its fundamental domain off (see the module docs).
    pub fn adj(&self) -> &[Vec<TileMatch>] {
        &self.adj
    }

    /// The per-node tileset shape ids (node id -> shape).
    pub fn shape(&self) -> &[usize] {
        &self.shape
    }

    /// Register a node with no edges (its edges are added by later glues). Used
    /// to seed node 0 before the first glue and to add each glued tile's node.
    /// Returns the new node id.
    fn push_node(&mut self, shape: usize) -> usize {
        self.shape.push(shape);
        self.adj.push(Vec::new());
        self.shape.len() - 1
    }

    /// Add the undirected edge `tm` to both endpoints. Each `TileMatch` here uses
    /// the graph's own convention -- BOTH segments name the shared (matched)
    /// edges directly, forward ranges -- so the same border seen from the other
    /// tile is just the segment SWAP `{a: tm.b, b: tm.a}`. (This is NOT the
    /// asymmetric `PatchMatch`/`TileMatch::involution` convention, where one side
    /// stores the first-surviving edge; do not mix them.)
    ///
    /// The `tile_id` fields here are graph NODE ids (patch tile instances),
    /// not tileset shape ids -- meaning 2 of the three-way overload documented
    /// on [`crate::geom::matches::Segment`].
    fn push_edge(&mut self, tm: TileMatch) {
        self.adj[tm.a.tile_id].push(tm);
        self.adj[tm.b.tile_id].push(TileMatch::new(tm.b, tm.a));
    }
}

impl<T: IsRing, P: Patch<T>> Patch<T> for WithAdjacency<P> {
    fn angles(&self) -> &[i8] {
        self.inner.angles()
    }
    fn edges(&self) -> &[EdgeInfo] {
        self.inner.edges()
    }
    fn patch_tile_ids(&self) -> &[usize] {
        self.inner.patch_tile_ids()
    }
    fn boundary_positions(&self) -> &[T] {
        self.inner.boundary_positions()
    }
    fn next_tile_id(&self) -> usize {
        self.inner.next_tile_id()
    }
    fn tileset(&self) -> &Arc<TileSet<T>> {
        self.inner.tileset()
    }
    fn get_matches_in_edge_range(&self, start_edge: usize, end_edge: usize) -> Vec<PatchMatch> {
        self.inner.get_matches_in_edge_range(start_edge, end_edge)
    }
    fn get_matches_touching_vertex(&self, vertex_index: usize) -> Vec<PatchMatch> {
        self.inner.get_matches_touching_vertex(vertex_index)
    }

    /// Glue `pm`, then project the graph: read the edges this glue forms off the
    /// PRE-glue boundary, forward to the inner patch, and -- only on success --
    /// register the new node and those edges INLINE. On failure the graph is
    /// untouched (the inner `None` short-circuits before any `push`), driven by
    /// the inner glue's success.
    fn add_tile(&mut self, pm: &PatchMatch) -> Option<GlueDelta> {
        let new_id = self.inner.next_tile_id();
        let m_new = self.inner.tileset().rat(pm.b.tile_id).len();
        // Snapshot the boundary owners BEFORE mutating.
        let edges = tile_match_runs(
            self.inner.edges(),
            self.inner.patch_tile_ids(),
            pm,
            m_new,
            new_id,
        );
        let delta = self.inner.add_tile(pm)?; // None -> graph untouched
        debug_assert_eq!(new_id, self.num_tiles(), "node ids track patch tile ids");
        self.push_node(pm.b.tile_id);
        for tm in edges {
            self.push_edge(tm);
        }
        Some(delta)
    }
}

impl<T: IsRing> WithAdjacency<BasicPatch<T>> {
    /// A single-tile graph-carrying patch: the inner [`BasicPatch`] seeded on
    /// `tile_id`, with the adjacency pre-seeded with node 0 (see the type docs).
    /// The bootstrap for growing a graph-carrying corona.
    pub fn single_tile(tileset: Arc<TileSet<T>>, tile_id: usize) -> Self {
        let inner = BasicPatch::single_tile(tileset, tile_id);
        let mut wa = WithAdjacency {
            inner,
            shape: Vec::new(),
            adj: Vec::new(),
        };
        wa.push_node(tile_id); // node 0 (seed); first glue handled by add_tile
        wa
    }

    /// All legal `add_tile` candidates for the current boundary (delegates to the
    /// inner [`BasicPatch`]).
    pub fn get_all_matches(&self) -> Vec<PatchMatch> {
        self.inner.get_all_matches()
    }

    /// Materialise the current boundary as a `Rat` (delegates to the inner patch).
    pub fn to_rat(&self) -> Rat<T> {
        self.inner.to_rat()
    }

    /// Serialize this grown adjacency graph into a replayable `build` recipe: a
    /// spanning glue-sequence (one [`PatchMatch`] per non-seed tile) that
    /// [`replay_placements`](crate::classify::grow::replay_placements) or
    /// `PeriodicCert::reconstruct` rebuild the identical patch from -- the
    /// inverse of the from-recipe replay. Reads only the graph (adjacency +
    /// per-node shape ids), never coordinates, so the recipe is content-
    /// addressable. `None` if the graph is not connectedly assemblable. Monotile
    /// only: every node is the base shape (id 0).
    pub fn to_recipe(&self) -> Option<Vec<PatchMatch>> {
        let nodes: Vec<usize> = (0..self.num_tiles()).collect();
        let base = self.tileset().rat(0).clone();
        assemble(self.shape(), self.adj(), &nodes, &base).map(|(build, _, _)| build)
    }
}

/// The concrete graph-carrying patch the corona grower and cert carve pass
/// around: a [`WithAdjacency`] layer over the plain [`BasicPatch`] core -- the
/// adjacency wrapper parallel to [`EPatch`](crate::geom::patch::EPatch) (the
/// junction wrapper), NOT a stack of the two. Named for the *intensional graph*
/// it is -- the tile adjacency built inline during the search. A single name for
/// it keeps the grow/mint signatures legible.
pub type IPatch<T> = WithAdjacency<BasicPatch<T>>;

/// The seed tile's own synthetic boundary before any glue: `m` edges of shape
/// `shape`, all owned by patch instance 0 -- the pre-first-glue state that
/// `assemble` (in [`mint`](crate::classify::mint)) reads the first adjacency off
/// (a one-tile patch has no real `BasicPatch` to query).
pub(crate) fn seed_boundary(shape: usize, m: usize) -> (Vec<EdgeInfo>, Vec<usize>) {
    let edges = (0..m)
        .map(|i| EdgeInfo {
            tile_type_id: shape,
            canon_offset: i,
        })
        .collect();
    (edges, vec![0usize; m])
}

/// Segment the consumed boundary run `pm.a_range` into maximal same-owner
/// sub-runs and build one [`TileMatch`] per owner (oriented `a = new_id`,
/// `b = owner`). The owner side is read exactly from `EdgeInfo`; the new-tile
/// side is the matching slice of the new tile's matched edges
/// `[b_start - mlen, b_start)` (mod `m_new`).
pub(crate) fn tile_match_runs(
    old_edges: &[crate::geom::vertices::EdgeInfo],
    old_ptids: &[usize],
    pm: &PatchMatch,
    m_new: usize,
    new_id: usize,
) -> Vec<TileMatch> {
    let n = old_edges.len();
    let mlen = pm.len();
    let a_start = pm.a_range.start_offset;
    let b_start = pm.b.range.start_offset;
    let mut out = Vec::new();
    let mut p = 0;
    while p < mlen {
        let owner = old_ptids[(a_start + p) % n];
        // Extend the sub-run while the owner is unchanged.
        let mut q = 1;
        while p + q < mlen && old_ptids[(a_start + p + q) % n] == owner {
            q += 1;
        }
        // Owner edges ascend along the boundary (CCW); the new tile's edges
        // descend (see `glue_new_range`). Both are stored as forward ranges that
        // pair anti-parallel (owner position i <-> new position len-1-i).
        let owner_off0 = old_edges[(a_start + p) % n].canon_offset;
        // Monotile: the owner's edge count equals the new tile's (`m_new`).
        debug_assert!(
            (0..q)
                .all(|t| old_edges[(a_start + p + t) % n].canon_offset == (owner_off0 + t) % m_new),
            "owner run is ascending-contiguous",
        );
        out.push(TileMatch::new(
            Segment::new(new_id, glue_new_range(b_start, p, q, m_new)),
            Segment::new(owner, EdgeRange::new(owner_off0, q)),
        ));
        p += q;
    }
    out
}

/// Greedy peel (see the body comment): each round attaches SOME not-yet-placed
/// node through a still-exposed shared edge of an already-placed neighbour,
/// picking the candidate glue that reproduces the recorded submatch
/// `(parent edge X <-> child edge Y)`. A fixed spanning-tree order would NOT
/// suffice -- a tree parent edge can already be buried by the time its child
/// attaches -- which is why all placed-neighbour edges are tried and whichever
/// is live is used. Deterministic (first-fit over a fixed scan order). `None`
/// if the subgraph is disconnected or no frontier tile is attachable.
///
/// Graph-pure: geometry enters only through `base` (the single monotile shape);
/// `shape` is the per-node shape ids (unused for a monotile, present for the
/// graph-pure contract).
pub(crate) fn assemble<T: IsRing>(
    shape: &[usize],
    adj: &[Vec<TileMatch>],
    nodes: &[usize],
    base: &Rat<T>,
) -> Option<(Vec<PatchMatch>, BasicPatch<T>, Vec<usize>)> {
    // Monotile pipeline: geometry comes entirely from `base`, so every node
    // must be the single base shape (id 0). `shape` is carried for the
    // graph-pure contract (real per-node ids once multi-proto assembly lands);
    // assert the monotile precondition rather than silently ignoring it.
    debug_assert!(
        nodes.iter().all(|&n| shape.get(n) == Some(&0)),
        "assemble: monotile pipeline expects every node to be shape 0"
    );
    let m = base.len();
    let ts = TileSet::single(base.clone());
    let seed = BasicPatch::single_tile(ts, 0);

    // GREEDY PEEL: grow the placed set outward. Each round, add SOME not-yet-
    // placed node that is graph-adjacent to a placed one via an edge whose
    // parent-side is still on the boundary (not buried) -- i.e. attach a
    // frontier tile through a still-exposed shared edge. A fixed BFS-tree
    // parent edge can be buried before its child attaches (for a compact
    // patch), so we try ALL placed-neighbour edges and use whichever is live.
    // The glue is the UNIQUE match at that boundary edge reproducing the graph
    // submatch (parent edge X <-> child edge Y).
    let (synth_edges, synth_ptids) = seed_boundary(0, m);
    // Does a candidate's induced adjacency include the target submatch
    // "owner edge X shares with new edge Y"?
    let hits = |created: &[TileMatch], parent_tile: usize, x: usize, y: usize| {
        created.iter().any(|c| {
            c.b.tile_id == parent_tile && partner_offset(&c.b.range, &c.a.range, x, m) == Some(y)
        })
    };
    let mut order = vec![nodes[0]]; // gp tile j == order[j]; tile 0 = seed
    let mut placed: std::collections::HashSet<usize> = std::collections::HashSet::from([nodes[0]]);
    let mut build: Vec<PatchMatch> = Vec::new();
    let mut gp: Option<BasicPatch<T>> = None;
    while placed.len() < nodes.len() {
        let mut next: Option<(usize, BasicPatch<T>, PatchMatch)> = None;
        'search: for &child in nodes {
            if placed.contains(&child) {
                continue;
            }
            // Every placed neighbour of `child` is a candidate attachment.
            for e in &adj[child] {
                let parent = e.b.tile_id; // e.a == child, e.b == neighbour
                if !placed.contains(&parent) {
                    continue;
                }
                let parent_tile = order.iter().position(|&n| n == parent)?;
                // Target one shared edge: owner (parent) range-start X (border
                // position 0), paired anti-parallel with child offset Y.
                let x = e.b.range.start_offset;
                let y = peer_offset(&e.a.range, 0, m);
                // candidate glues at parent-edge X (skip if that edge is buried).
                let cands: Vec<PatchMatch> = match &gp {
                    None => seed
                        .get_all_matches()
                        .iter()
                        .filter(|pm| pm.a_range.start_offset == x)
                        .cloned()
                        .collect(),
                    Some(g) => match (0..g.len()).find(|&i| {
                        g.patch_tile_ids()[i] == parent_tile && g.edges()[i].canon_offset == x
                    }) {
                        Some(pos) => g.get_matches_in_edge_range(pos, pos),
                        None => continue, // parent-edge X buried; try another edge
                    },
                };
                for pm in &cands {
                    let created = match &gp {
                        None => tile_match_runs(&synth_edges, &synth_ptids, pm, m, 1),
                        Some(g) => {
                            tile_match_runs(g.edges(), g.patch_tile_ids(), pm, m, g.next_tile_id())
                        }
                    };
                    if !hits(&created, parent_tile, x, y) {
                        continue;
                    }
                    let trial = match &gp {
                        None => seed.with_tile(pm),
                        Some(g) => {
                            let mut g2 = g.clone();
                            g2.add_tile(pm).is_some().then_some(g2)
                        }
                    };
                    if let Some(g2) = trial {
                        next = Some((child, g2, *pm));
                        break 'search;
                    }
                }
            }
        }
        let Some((child, g2, pm)) = next else {
            return None; // no frontier tile attachable this round; graph not fully assembled
        };
        gp = Some(g2);
        build.push(pm);
        order.push(child);
        placed.insert(child);
    }
    Some((build, gp?, order))
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::classify::grow::capture_placement;
    use crate::classify::mint::connected_transversal;
    use crate::cyclotomic::ZZ12;
    use crate::cyclotomic::traits::SymNum;
    use crate::geom::iso::Iso;
    use crate::geom::patch::{BasicPatch, trace_boundary_positions};
    use crate::geom::rat::Rat;
    use crate::geom::tiles;
    use crate::geom::tileset::TileSet;
    use std::collections::HashSet;
    use std::collections::VecDeque;

    /// `to_recipe` serializes a grown adjacency graph back into a replayable
    /// recipe: grow a patch as a graph (no recorded build), extract the recipe
    /// from the GRAPH alone, and confirm replaying it rebuilds the identical
    /// patch -- the graph <-> recipe round-trip.
    #[test]
    fn to_recipe_round_trips_a_grown_graph() {
        use crate::classify::grow::{grow_coronas_build, replay_recipe};

        let seq: &[i8] = &[3, 2, 0, 2, -3, 2, 3, 2, -3, 2, 3, -2, 3, -2]; // spectre
        let (_pls, ig) = grow_coronas_build::<ZZ12>(seq, 2).expect("grew a patch");
        let base = Rat::<ZZ12>::from_slice_trusted(seq);

        let recipe = ig.to_recipe().expect("graph assembles into a recipe");
        assert_eq!(
            recipe.len(),
            ig.num_tiles() - 1,
            "one glue per non-seed tile"
        );

        let recon = replay_recipe(&base, &recipe, |_, _| true).expect("recipe replays");
        assert_eq!(
            recon.to_rat(),
            ig.to_rat(),
            "round-trip rebuilds the identical patch"
        );
    }

    /// BFS order from `root` over the undirected graph (root first). Test
    /// infrastructure operating directly on the adjacency slices.
    fn bfs_from(adj: &[Vec<TileMatch>], root: usize) -> Vec<usize> {
        let mut seen = vec![false; adj.len()];
        let mut order = Vec::new();
        let mut q = VecDeque::from([root]);
        seen[root] = true;
        while let Some(u) = q.pop_front() {
            order.push(u);
            for e in &adj[u] {
                let v = e.b.tile_id;
                if !seen[v] {
                    seen[v] = true;
                    q.push_back(v);
                }
            }
        }
        order
    }

    /// Connected-component id per node (dense, 0-based in discovery order).
    fn components(adj: &[Vec<TileMatch>]) -> Vec<usize> {
        let mut comp = vec![usize::MAX; adj.len()];
        let mut c = 0;
        for s in 0..adj.len() {
            if comp[s] != usize::MAX {
                continue;
            }
            let mut q = VecDeque::from([s]);
            comp[s] = c;
            while let Some(u) = q.pop_front() {
                for e in &adj[u] {
                    let v = e.b.tile_id;
                    if comp[v] == usize::MAX {
                        comp[v] = c;
                        q.push_back(v);
                    }
                }
            }
            c += 1;
        }
        comp
    }

    /// Grow a monotile patch of `target` tiles by always gluing the most concave
    /// boundary vertex, on a [`WithAdjacency`] patch so the graph is built during
    /// growth, and capturing each tile's placement at glue time (an interior tile
    /// loses its boundary edges, so placements cannot be captured after the fact).
    /// The single growth worker behind the `grow_keep` view.
    fn grow_full(
        seq: &[i8],
        target: usize,
    ) -> (WithAdjacency<BasicPatch<ZZ12>>, Vec<Iso<ZZ12>>, Vec<ZZ12>) {
        let ts = TileSet::single(Rat::<ZZ12>::from_slice_trusted(seq));
        let verts: Vec<ZZ12> = trace_boundary_positions::<ZZ12>(seq)[..seq.len()].to_vec();
        let mut wa = WithAdjacency::single_tile(ts.clone(), 0);
        let first = wa
            .get_all_matches()
            .first()
            .cloned()
            .expect("a first match");
        wa.add_tile(&first).expect("seed grows");
        let mut placements = vec![
            capture_placement(&wa, &verts, 0).expect("seed placement"),
            capture_placement(&wa, &verts, 1).expect("tile 1 placement"),
        ];
        while wa.next_tile_id() < target {
            let angles = wa.angles().to_vec();
            let n = angles.len();
            let mut matches = wa.get_all_matches();
            if matches.is_empty() {
                break;
            }
            matches.sort_by_key(|pm| angles[pm.a_range.start_offset % n]);
            let mut glued = false;
            for pm in &matches {
                let new_id = wa.next_tile_id();
                if wa.add_tile(pm).is_some() {
                    placements.push(capture_placement(&wa, &verts, new_id).expect("placement"));
                    glued = true;
                    break;
                }
            }
            if !glued {
                break;
            }
        }
        (wa, placements, verts)
    }

    /// Every graph edge names the SAME physical unit edges on both tiles, AND
    /// the within-run PAIRING is right: position i of the `a` range and position
    /// i of the `b` range must be the same physical edge (anti-parallel). The
    /// set check alone is direction-blind (symmetric tiles pass regardless), so
    /// this per-position check is what catches an offset/direction bug.
    fn assert_edges_geometric(
        g: &WithAdjacency<BasicPatch<ZZ12>>,
        pls: &[Iso<ZZ12>],
        base: &[ZZ12],
    ) {
        let m = base.len();
        let canon = |p: ZZ12, q: ZZ12| {
            if format!("{:?}", p.xy()) < format!("{:?}", q.xy()) {
                (p, q)
            } else {
                (q, p)
            }
        };
        for a in 0..g.num_tiles() {
            for tm in g.neighbors(a) {
                assert_eq!(tm.a.tile_id, a, "edge oriented a = node");
                assert_eq!(tm.a.range.len, tm.b.range.len, "equal match length");
                let pa = pls[tm.a.tile_id].tile(base);
                let pb = pls[tm.b.tile_id].tile(base);
                let len = tm.a.range.len;
                for i in 0..len {
                    // Anti-parallel pairing: a[i] shares the border with b[len-1-i].
                    let ao = (tm.a.range.start_offset + i) % m;
                    let bo = peer_offset(&tm.b.range, i, m);
                    let ae = canon(pa[ao], pa[(ao + 1) % m]);
                    let be = canon(pb[bo], pb[(bo + 1) % m]);
                    assert_eq!(
                        ae, be,
                        "edge {}-{}: within-run position {i} mismatch (a off {ao}, b off {bo})",
                        tm.a.tile_id, tm.b.tile_id
                    );
                }
            }
        }
    }

    /// An asymmetric tile: capture_placement gives it a UNIQUE frame, so a
    /// tile's edge offset `o` maps to physical edge `o` unambiguously (unlike a
    /// symmetric hexagon, where several isos are valid). Used wherever a test
    /// checks edge OFFSETS geometrically.
    const ASYM: [i8; 7] = [-1, 2, 3, 1, 2, 1, 4];

    /// Build an adjacency list from an explicit undirected edge list (monotile
    /// shape 0, placeholder edge ranges) -- for exercising the traversal
    /// algorithms independent of any real patch geometry.
    fn from_edges(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<TileMatch>> {
        let mut adj: Vec<Vec<TileMatch>> = vec![Vec::new(); n];
        for &(a, b) in edges {
            let r = EdgeRange::new(0, 1);
            adj[a].push(TileMatch::new(Segment::new(a, r), Segment::new(b, r)));
            adj[b].push(TileMatch::new(Segment::new(b, r), Segment::new(a, r)));
        }
        adj
    }

    /// [`grow_full`] view: the graph-carrying patch (used to check `assemble`
    /// reconstructs the patch -- via its `.adj()`/`.shape()` and `.to_rat()`).
    fn grow_keep(seq: &[i8], target: usize) -> WithAdjacency<BasicPatch<ZZ12>> {
        grow_full(seq, target).0
    }

    /// The "snowflake": a hex flower (center 0 + petals 1..=6) plus one outer hex
    /// glued centrally onto each petal (7..=12, each touching only its petal).
    /// 13 tiles with a rich, predictable topology for subset-assembly tests.
    fn grow_snowflake() -> WithAdjacency<BasicPatch<ZZ12>> {
        let hex = Rat::<ZZ12>::from_snake_trusted(&tiles::hexagon());
        let m = 6;
        let ts = TileSet::single(hex);
        let mut wa = WithAdjacency::single_tile(ts.clone(), 0);
        let first = wa.get_all_matches().first().cloned().unwrap();
        wa.add_tile(&first).unwrap();
        // Flower: fill until the center (tile 0) has all 6 petals.
        while wa.degree(0) < 6 {
            let ptids = wa.patch_tile_ids().to_vec();
            let n = ptids.len();
            let matches = wa.get_all_matches();
            let pick = matches
                .iter()
                .find(|pm| {
                    (0..pm.a_range.len).any(|t| ptids[(pm.a_range.start_offset + t) % n] == 0)
                })
                .or_else(|| matches.first())
                .cloned()
                .unwrap();
            assert!(wa.add_tile(&pick).is_some(), "flower glue");
        }
        assert_eq!(wa.num_tiles(), 7, "flower is 7 tiles");
        // Outer hexes: one single-owner glue onto each petal (1..=6).
        let mut done: HashSet<usize> = HashSet::new();
        while wa.num_tiles() < 13 {
            let cands = wa.get_all_matches();
            let mut glued = false;
            for pm in &cands {
                let created =
                    tile_match_runs(wa.edges(), wa.patch_tile_ids(), pm, m, wa.next_tile_id());
                let owners: HashSet<usize> = created.iter().map(|c| c.b.tile_id).collect();
                if owners.len() == 1 {
                    let owner = *owners.iter().next().unwrap();
                    if (1..=6).contains(&owner)
                        && !done.contains(&owner)
                        && wa.add_tile(pm).is_some()
                    {
                        done.insert(owner);
                        glued = true;
                        break;
                    }
                }
            }
            if !glued {
                break;
            }
        }
        wa
    }

    /// Reconstruct the adjacency graph of a patch assembled from `build` (replay
    /// `build` through a fresh [`WithAdjacency`] patch).
    fn graph_of_build(build: &[PatchMatch], base: &Rat<ZZ12>) -> WithAdjacency<BasicPatch<ZZ12>> {
        let ts = TileSet::single(base.clone());
        let mut wa = WithAdjacency::single_tile(ts, 0);
        wa.add_tile(&build[0]).expect("seed");
        for pm in &build[1..] {
            assert!(wa.add_tile(pm).is_some(), "replay glue");
        }
        wa
    }

    /// Assemble `subset` from a graph over base tile `seq` and assert the
    /// reconstructed patch has the SAME topology as the graph induced on
    /// `subset` (same set of adjacent node-pairs, mapped through `order`).
    fn check_subset_of(g: &WithAdjacency<BasicPatch<ZZ12>>, seq: &[i8], subset: &[usize]) {
        let base = Rat::<ZZ12>::from_slice_trusted(seq);
        let (build, gp2, order) = assemble(g.shape(), g.adj(), subset, &base)
            .unwrap_or_else(|| panic!("assemble {subset:?} must succeed"));
        assert_eq!(
            gp2.next_tile_id(),
            subset.len(),
            "{subset:?}: all tiles placed"
        );
        assert_eq!(build.len(), subset.len() - 1);
        let sub: HashSet<usize> = subset.iter().copied().collect();
        let pair = |a: usize, b: usize| if a < b { (a, b) } else { (b, a) };
        // Original induced adjacency (undirected node-pairs within subset).
        let mut want: HashSet<(usize, usize)> = HashSet::new();
        for &a in subset {
            for e in g.neighbors(a) {
                let b = e.b.tile_id;
                if sub.contains(&b) {
                    want.insert(pair(a, b));
                }
            }
        }
        // Reconstructed adjacency, mapped tile-id -> original node via `order`.
        let g2 = graph_of_build(&build, &base);
        let mut got: HashSet<(usize, usize)> = HashSet::new();
        for u in 0..g2.num_tiles() {
            for e in g2.neighbors(u) {
                got.insert(pair(order[u], order[e.b.tile_id]));
            }
        }
        assert_eq!(
            got, want,
            "{subset:?}: reconstructed topology matches induced subgraph"
        );
    }

    fn check_subset(g: &WithAdjacency<BasicPatch<ZZ12>>, subset: &[usize]) {
        check_subset_of(
            g,
            Rat::<ZZ12>::from_snake_trusted(&tiles::hexagon()).seq(),
            subset,
        );
    }

    /// The real L-tetromino (from `geom::tiles`), as a ZZ12 turn word. ASYMMETRIC,
    /// tiles densely with many multi-edge shared borders -- the case that exposes
    /// within-run offset/direction bugs symmetric tiles mask.
    fn tetro() -> Vec<i8> {
        Rat::<ZZ12>::try_from(&tiles::tetromino_L::<ZZ12>())
            .unwrap()
            .seq()
            .to_vec()
    }

    #[test]
    fn tetromino_graph_edges_geometric() {
        // Grow a dense L-tetromino patch and verify EVERY graph edge's within-run
        // pairing is geometrically correct (per-position, not just per-set).
        let seq = tetro();
        let (g, pls, base) = grow_full(&seq, 16);
        assert!(
            g.num_tiles() >= 10,
            "grew a dense patch (got {})",
            g.num_tiles()
        );
        assert_edges_geometric(&g, &pls, &base);
    }

    #[test]
    fn tetromino_subsets_assemble() {
        // Reconstruct the full dense patch and several connected subpatches.
        let seq = tetro();
        let wa = grow_keep(&seq, 16);
        let n = wa.num_tiles();
        check_subset_of(&wa, &seq, &(0..n).collect::<Vec<_>>()); // full patch
        check_subset_of(&wa, &seq, &[0, 1, 2]); // small corner
        // a connected "line" of tiles: BFS-order first 5
        let line: Vec<usize> = bfs_from(wa.adj(), 0).into_iter().take(5).collect();
        check_subset_of(&wa, &seq, &line);
    }

    #[test]
    fn snowflake_structure() {
        let wa = grow_snowflake();
        assert_eq!(wa.num_tiles(), 13, "center + 6 petals + 6 outer");
        assert_eq!(wa.degree(0), 6, "center touches 6 petals");
        // Outer hexes (7..=12) each touch exactly one petal.
        for o in 7..13 {
            let nbrs: HashSet<usize> = wa.neighbors(o).iter().map(|e| e.b.tile_id).collect();
            assert_eq!(nbrs.len(), 1, "outer hex {o} touches one tile");
            assert!(
                (1..=6).contains(nbrs.iter().next().unwrap()),
                "outer hex on a petal"
            );
        }
    }

    #[test]
    fn snowflake_subsets_assemble() {
        let wa = grow_snowflake();
        // center 7 (the flower)
        check_subset(&wa, &[0, 1, 2, 3, 4, 5, 6]);
        // a corner: two adjacent petals + the center
        check_subset(&wa, &[0, 1, 2]);
        // a petal and its outer hex
        let p1_outer = (7..13)
            .find(|&o| wa.neighbors(o)[0].b.tile_id == 1)
            .unwrap();
        check_subset(&wa, &[1, p1_outer]);
        // a path through the centre: two petals + the center + both petals'
        // outer hexes (connected only via the center hub).
        let p4_outer = (7..13)
            .find(|&o| wa.neighbors(o)[0].b.tile_id == 4)
            .unwrap();
        check_subset(&wa, &[0, 1, 4, p1_outer, p4_outer]);
    }

    #[test]
    fn assemble_reconstructs_patch() {
        // Assembling ALL of a grown patch's tiles (in growth order, a valid
        // connected tree order) must rebuild the IDENTICAL patch -- same tile
        // count and same boundary shape -- purely from the graph's edges, with no
        // geometry. This isolates `assemble` from the cert glue stage.
        let hex = Rat::<ZZ12>::from_snake_trusted(&tiles::hexagon());
        let tri = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle());
        for seq in [&ASYM[..], hex.seq(), tri.seq()] {
            let wa = grow_keep(seq, 12);
            let n = wa.num_tiles();
            assert!(n >= 6, "grew a real patch (got {n})");
            let base = Rat::<ZZ12>::from_slice_trusted(seq);
            let nodes: Vec<usize> = (0..n).collect();
            let (build, gp2, _order) = assemble(wa.shape(), wa.adj(), &nodes, &base)
                .unwrap_or_else(|| panic!("{seq:?}: assemble must succeed"));
            eprintln!(
                "{seq:?}: n={n} build={} wa.next_tile_id={} gp2.next_tile_id={}",
                build.len(),
                wa.next_tile_id(),
                gp2.next_tile_id()
            );
            assert_eq!(build.len(), n - 1, "{seq:?}: one glue per non-seed tile");
            assert_eq!(gp2.next_tile_id(), n, "{seq:?}: assembled all tiles");
            assert_eq!(
                gp2.to_rat(),
                wa.to_rat(),
                "{seq:?}: assembled patch identical to original"
            );
        }
    }

    #[test]
    fn geometric_edges_asymmetric() {
        // THE offset-correctness test: an asymmetric tile has a UNIQUE placement,
        // so each graph edge's stored ranges can be checked against the real
        // shared unit edges. (Symmetric tiles are frame-ambiguous under
        // capture_placement, so their offset geometry is not a reliable oracle.)
        let (g, pls, base) = grow_full(&ASYM, 14);
        assert!(
            g.num_tiles() >= 8,
            "grew a real patch (got {})",
            g.num_tiles()
        );
        assert_edges_geometric(&g, &pls, &base);
        assert!(components(g.adj()).iter().all(|&c| c == 0), "connected");
    }

    #[test]
    fn geometric_edges_real_tiles() {
        // Verify the graph edges are geometrically correct for the actual tiles
        // whose carve fails -- if an edge's stored (X,Y) is not the real shared
        // physical edge, the bug is in the graph builder, not the assembly.
        for seq in [
            &[-2i8, -1, 2, 5, -2, 1, 2, 1, 2, 4][..],
            &[-3i8, 1, 3, -2, 4, 3, -2, 1, 2, 5][..],
        ] {
            let (g, pls, base) = grow_full(seq, 16);
            assert!(
                g.num_tiles() >= 10,
                "{seq:?}: grew a real patch (got {})",
                g.num_tiles()
            );
            assert_edges_geometric(&g, &pls, &base);
        }
    }

    /// Build the hexagonal flower: a center hexagon surrounded by 6 petals.
    /// Growth prefers glues that touch the center (tile 0), so the seed gets
    /// fully surrounded (plain greedy fills notches first and never closes the
    /// ring).
    fn grow_flower() -> WithAdjacency<BasicPatch<ZZ12>> {
        let ts = TileSet::single(Rat::<ZZ12>::from_snake_trusted(&tiles::hexagon()));
        let mut wa = WithAdjacency::single_tile(ts.clone(), 0);
        let first = wa.get_all_matches().first().cloned().unwrap();
        wa.add_tile(&first).unwrap();
        while wa.next_tile_id() < 7 {
            let ptids = wa.patch_tile_ids().to_vec();
            let n = ptids.len();
            let touches_center = |pm: &PatchMatch| {
                (0..pm.a_range.len).any(|t| ptids[(pm.a_range.start_offset + t) % n] == 0)
            };
            let matches = wa.get_all_matches();
            let pick = matches
                .iter()
                .find(|pm| touches_center(pm))
                .or_else(|| matches.first())
                .cloned()
                .expect("a match to extend the flower");
            assert!(wa.add_tile(&pick).is_some(), "flower glue succeeds");
        }
        wa
    }

    #[test]
    fn hexagon_flower_graph() {
        // Center (node 0) touches all 6 petals; ignoring the center, the 6 petals
        // form a clean 6-cycle (each petal edge-adjacent to its two neighbours).
        let g = grow_flower();
        assert_eq!(g.num_tiles(), 7, "center + 6 petals");
        assert!(components(g.adj()).iter().all(|&c| c == 0), "connected");

        // Distinct petal neighbours of the center.
        let petals: HashSet<usize> = g.neighbors(0).iter().map(|e| e.b.tile_id).collect();
        assert_eq!(
            petals,
            HashSet::from([1, 2, 3, 4, 5, 6]),
            "center touches all 6 petals"
        );

        // Petal-petal adjacency (edges among 1..=6, ignoring the center): each
        // petal has exactly two petal-neighbours and they form ONE 6-cycle.
        let petal_nbrs = |p: usize| -> HashSet<usize> {
            g.neighbors(p)
                .iter()
                .map(|e| e.b.tile_id)
                .filter(|&v| v != 0)
                .collect::<HashSet<_>>()
        };
        for p in 1..=6 {
            assert_eq!(petal_nbrs(p).len(), 2, "petal {p} has two petal-neighbours");
        }
        // Walk the cycle from petal 1; it must return to 1 after visiting all 6.
        let mut order = vec![1usize];
        let mut prev = 0usize; // came from the center-side; any non-petal
        while order.len() < 6 {
            let cur = *order.last().unwrap();
            let next = petal_nbrs(cur)
                .into_iter()
                .find(|&v| v != prev)
                .expect("cycle continues");
            prev = cur;
            order.push(next);
        }
        // The last petal must close back to the first.
        assert!(
            petal_nbrs(order[5]).contains(&order[0]),
            "petals close into a cycle"
        );
        let uniq: HashSet<usize> = order.iter().copied().collect();
        assert_eq!(uniq.len(), 6, "the six petals form one clean cycle");
    }

    #[test]
    fn edges_recorded_both_ways() {
        // Every directed edge a->b has a reverse b->a of equal length, and each
        // edge on a node is oriented with that node as `a` (the undirected
        // invariant; the reverse is the plain segment swap).
        let (g, _pls, _base) = grow_full(&ASYM, 12);
        assert!(
            g.num_tiles() >= 8,
            "grew a real patch (got {})",
            g.num_tiles()
        );
        for a in 0..g.num_tiles() {
            for tm in g.neighbors(a) {
                assert_eq!(tm.a.tile_id, a, "edge oriented a = node");
                assert_eq!(tm.a.range.len, tm.b.range.len, "equal match length");
                // Multiplicity of a->b edges equals b->a (reverse is the swap).
                let fwd = g
                    .neighbors(a)
                    .iter()
                    .filter(|u| u.b.tile_id == tm.b.tile_id)
                    .count();
                let rev = g
                    .neighbors(tm.b.tile_id)
                    .iter()
                    .filter(|u| u.b.tile_id == a)
                    .count();
                assert_eq!(
                    fwd, rev,
                    "edges {}-{} recorded equally both ways",
                    a, tm.b.tile_id
                );
            }
        }
    }

    #[test]
    fn add_tile_forwards_and_leaves_graph_clean_on_failure() {
        let ts = TileSet::single(Rat::<ZZ12>::from_snake_trusted(&tiles::hexagon()));
        let mut wa = WithAdjacency::single_tile(ts.clone(), 0);
        let first = wa.get_all_matches().first().cloned().unwrap();
        wa.add_tile(&first).expect("seed grows");
        let (nodes_before, before_tiles) = (wa.num_tiles(), wa.next_tile_id());
        // A bogus match (out-of-range offsets) must be rejected; both the patch
        // and its projected graph stay put and the failure is forwarded.
        let bogus = PatchMatch::new(
            EdgeRange::new(0, 99),
            Segment::new(0, EdgeRange::new(0, 99)),
        );
        let ok = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
            wa.add_tile(&bogus).is_some()
        }))
        .unwrap_or(false);
        assert!(!ok, "bogus glue rejected");
        assert_eq!(
            wa.num_tiles(),
            nodes_before,
            "graph unchanged on failed glue"
        );
        assert_eq!(
            wa.next_tile_id(),
            before_tiles,
            "patch unchanged on failed glue"
        );
    }

    #[test]
    fn multi_owner_glue_creates_multiple_edges() {
        // Closing a hexagon flower: a petal glued into the notch between two
        // placed petals matches several owners in one add_tile, so some petals
        // end with degree >= 3 (center + two neighbours) -- edges only one glue's
        // a_range could have produced by spanning multiple owners.
        let (g, _pls, _base) =
            grow_full(Rat::<ZZ12>::from_snake_trusted(&tiles::hexagon()).seq(), 7);
        let high = (1..g.num_tiles()).filter(|&i| g.degree(i) >= 3).count();
        assert!(
            high >= 1,
            "closing the flower must produce multi-owner glues"
        );
    }

    #[test]
    fn connected_transversal_synthetic() {
        // 2x3 grid of tiles, columns = 3 classes:
        //   0 - 1 - 2
        //   |   |   |
        //   3 - 4 - 5
        // classes: col of each node. A connected transversal must pick one node
        // per column forming a connected set (e.g. 0-1-2 or 3-4-5, or an L).
        let adj = from_edges(6, &[(0, 1), (1, 2), (3, 4), (4, 5), (0, 3), (1, 4), (2, 5)]);
        let class = [0usize, 1, 2, 0, 1, 2];
        let dom = connected_transversal(&adj, &class, 3, 0).expect("transversal exists");
        assert_eq!(dom.len(), 3);
        assert_eq!(dom[0], 0, "root first");
        let classes: HashSet<usize> = dom.iter().map(|&i| class[i]).collect();
        assert_eq!(classes, HashSet::from([0, 1, 2]), "one node per class");
        // induced-connected
        let dset: HashSet<usize> = dom.iter().copied().collect();
        let mut seen = HashSet::from([dom[0]]);
        let mut stack = vec![dom[0]];
        while let Some(u) = stack.pop() {
            for e in &adj[u] {
                if dset.contains(&e.b.tile_id) && seen.insert(e.b.tile_id) {
                    stack.push(e.b.tile_id);
                }
            }
        }
        assert_eq!(seen.len(), 3, "transversal induces a connected subgraph");
    }

    #[test]
    fn connected_transversal_needs_bridge_class() {
        // The greedy-from-root trap: root's only same-class-free path to class 2
        // runs THROUGH class 1. A path graph 0(c0)-1(c1)-2(c2): from 0 you cannot
        // reach c2 without stepping through c1. The lift must still return all 3.
        let adj = from_edges(3, &[(0, 1), (1, 2)]);
        let class = [0usize, 1, 2];
        let dom = connected_transversal(&adj, &class, 3, 0).expect("path transversal");
        assert_eq!(dom.len(), 3);
        assert_eq!(
            HashSet::<usize>::from_iter(dom.iter().map(|&i| class[i])),
            HashSet::from([0, 1, 2])
        );
    }

    #[test]
    fn connected_transversal_missing_class_is_none() {
        // Only 2 of 3 classes present in the graph -> no k=3 transversal.
        let adj = from_edges(3, &[(0, 1), (1, 2)]);
        let class = [0usize, 1, 0];
        assert!(connected_transversal(&adj, &class, 3, 0).is_none());
    }

    #[test]
    fn components_splits_disjoint_graphs() {
        let adj = from_edges(5, &[(0, 1), (1, 2), (3, 4)]);
        let comp = components(&adj);
        assert_eq!(comp[0], comp[1]);
        assert_eq!(comp[1], comp[2]);
        assert_eq!(comp[3], comp[4]);
        assert_ne!(comp[0], comp[3], "two components");
    }

    #[test]
    fn bfs_covers_component() {
        let (g, _pls, _base) =
            grow_full(Rat::<ZZ12>::from_snake_trusted(&tiles::hexagon()).seq(), 7);
        let order = bfs_from(g.adj(), 0);
        assert_eq!(
            order.len(),
            g.num_tiles(),
            "BFS reaches every node (connected)"
        );
        assert_eq!(order[0], 0);
    }
}