use crate::geom::matches::Match;
use crate::geom::matches::MatchSeed;
use rustc_hash::FxHashSet;
use std::sync::Arc;
use crate::cyclotomic::IsRing;
use crate::cyclotomic::geometry::intersect_unit_segments;
use crate::geom::cyclic::{cyclic_arcs_overlap, cyclic_range_contains};
use crate::geom::glue;
use crate::geom::glue::junctions_glueable;
use crate::geom::grid::UnitSquareGrid;
#[cfg(test)]
use crate::geom::matches::PatchSegment;
use crate::geom::matches::{EdgeRange, Segment};
use crate::geom::matchtypes::MatchTypeIndex;
use crate::geom::rat::Rat;
#[cfg(debug_assertions)]
use crate::geom::snake::Snake;
use crate::geom::tileset::TileSet;
use crate::geom::vertices::{
EdgeInfo, OpenJunctionType, compute_junctions, compute_segments, is_junction_at,
};
use crate::stringmatch::forward_match_length;
pub use crate::geom::matches::PatchMatch;
pub(crate) mod graph;
pub use graph::{IPatch, WithAdjacency};
#[derive(Clone, Default)]
struct BoundaryGrid<T: IsRing> {
positions: Vec<T>,
grid: UnitSquareGrid,
edge_data: Vec<(T, T)>,
boundary_edge_ids: Vec<usize>,
next_edge_id: usize,
}
#[derive(Clone)]
struct Boundary {
angles: Vec<i8>,
edges: Vec<EdgeInfo>,
}
impl Boundary {
fn new(angles: Vec<i8>, edges: Vec<EdgeInfo>) -> Self {
debug_assert_eq!(
angles.len(),
edges.len(),
"boundary angles/edges length mismatch"
);
Self { angles, edges }
}
fn len(&self) -> usize {
self.angles.len()
}
fn angles(&self) -> &[i8] {
&self.angles
}
fn edges(&self) -> &[EdgeInfo] {
&self.edges
}
fn replace(&mut self, angles: Vec<i8>, edges: Vec<EdgeInfo>) {
debug_assert_eq!(
angles.len(),
edges.len(),
"boundary angles/edges length mismatch"
);
self.angles = angles;
self.edges = edges;
}
fn rotate_left(&mut self, n: usize) {
self.angles.rotate_left(n);
self.edges.rotate_left(n);
}
}
#[derive(Clone)]
pub struct BasicPatch<T: IsRing> {
match_index: Arc<MatchTypeIndex<T>>,
boundary_seq: Boundary,
boundary: BoundaryGrid<T>,
patch_tile_ids: Vec<usize>,
next_tile_id: usize,
}
#[derive(Clone)]
pub struct WithJunctions<P> {
inner: P,
inner_petals: Vec<Vec<EdgeInfo>>,
}
pub type EPatch<T> = WithJunctions<BasicPatch<T>>;
pub trait Patch<T: IsRing>: Clone {
fn angles(&self) -> &[i8];
fn edges(&self) -> &[EdgeInfo];
fn patch_tile_ids(&self) -> &[usize];
fn boundary_positions(&self) -> &[T];
fn next_tile_id(&self) -> usize;
fn tileset(&self) -> &Arc<TileSet<T>>;
fn get_matches_in_edge_range(&self, start_edge: usize, end_edge: usize) -> Vec<PatchMatch>;
fn get_matches_touching_vertex(&self, vertex_index: usize) -> Vec<PatchMatch>;
fn add_tile(&mut self, pm: &PatchMatch) -> Option<GlueDelta>;
}
impl<T: IsRing> Patch<T> for BasicPatch<T> {
#[inline]
fn angles(&self) -> &[i8] {
self.angles()
}
#[inline]
fn edges(&self) -> &[EdgeInfo] {
self.edges()
}
#[inline]
fn patch_tile_ids(&self) -> &[usize] {
self.patch_tile_ids()
}
#[inline]
fn boundary_positions(&self) -> &[T] {
self.boundary_positions()
}
#[inline]
fn next_tile_id(&self) -> usize {
self.next_tile_id()
}
#[inline]
fn tileset(&self) -> &Arc<TileSet<T>> {
self.tileset()
}
fn get_matches_in_edge_range(&self, start_edge: usize, end_edge: usize) -> Vec<PatchMatch> {
self.get_matches_in_edge_range(start_edge, end_edge)
}
fn get_matches_touching_vertex(&self, vertex_index: usize) -> Vec<PatchMatch> {
self.get_matches_touching_vertex(vertex_index)
}
fn add_tile(&mut self, pm: &PatchMatch) -> Option<GlueDelta> {
self.add_tile(pm)
}
}
impl<T: IsRing> Patch<T> for WithJunctions<BasicPatch<T>> {
#[inline]
fn angles(&self) -> &[i8] {
self.angles()
}
#[inline]
fn edges(&self) -> &[EdgeInfo] {
self.edges()
}
#[inline]
fn patch_tile_ids(&self) -> &[usize] {
self.patch_tile_ids()
}
#[inline]
fn boundary_positions(&self) -> &[T] {
self.boundary_positions()
}
#[inline]
fn next_tile_id(&self) -> usize {
self.next_tile_id()
}
#[inline]
fn tileset(&self) -> &Arc<TileSet<T>> {
self.tileset()
}
fn get_matches_in_edge_range(&self, start_edge: usize, end_edge: usize) -> Vec<PatchMatch> {
self.get_matches_in_edge_range(start_edge, end_edge)
}
fn get_matches_touching_vertex(&self, vertex_index: usize) -> Vec<PatchMatch> {
self.get_matches_touching_vertex(vertex_index)
}
fn add_tile(&mut self, pm: &PatchMatch) -> Option<GlueDelta> {
self.add_tile(pm)
}
}
fn update_inner_petals<T: IsRing>(
old_inner: &[Vec<EdgeInfo>],
old_edges: &[EdgeInfo],
pm: &PatchMatch,
new_n: usize,
old_ptids: &[usize],
tileset: &TileSet<T>,
) -> Vec<Vec<EdgeInfo>> {
let n = old_edges.len();
let seg_len_old = n - pm.len();
let ccw_pos = (pm.a_range.start_offset + pm.len()) % n;
let cw_end_matched = (pm.a_range.start_offset + pm.len() - 1) % n;
let mut new_inner = vec![Vec::new(); new_n];
for i in 1..seg_len_old {
new_inner[i] = old_inner[(ccw_pos + i) % n].clone();
}
let petal_after = |e: EdgeInfo| -> EdgeInfo {
let tlen = tileset.rat(e.tile_type_id).len();
EdgeInfo {
tile_type_id: e.tile_type_id,
canon_offset: (e.canon_offset + 1) % tlen,
}
};
let consumed_cw_ptid = old_ptids[cw_end_matched];
let ccw_survivor_ptid = old_ptids[ccw_pos];
let mut chain_ccw: Vec<EdgeInfo> = old_inner[ccw_pos].clone();
if consumed_cw_ptid != ccw_survivor_ptid {
chain_ccw.insert(0, petal_after(old_edges[cw_end_matched]));
}
let consumed_ccw_ptid = old_ptids[pm.a_range.start_offset];
let cw_survivor_ptid = old_ptids[(pm.a_range.start_offset + n - 1) % n];
let mut chain_cw: Vec<EdgeInfo> = old_inner[pm.a_range.start_offset].clone();
if consumed_ccw_ptid != cw_survivor_ptid {
chain_cw.push(old_edges[pm.a_range.start_offset]);
}
if new_n == seg_len_old {
let mut merged = chain_cw;
merged.extend(chain_ccw);
new_inner[0] = merged;
} else {
new_inner[0] = chain_ccw;
new_inner[seg_len_old] = chain_cw;
}
new_inner
}
pub(crate) fn junction_angle_sequence<T: IsRing>(
jtype: &OpenJunctionType,
tileset: &TileSet<T>,
) -> Vec<i8> {
let seed_seq = tileset.rat(jtype.cw.tile_type_id).seq();
let n_seed = seed_seq.len();
let junc_vertex = (jtype.cw.canon_offset + 1) % n_seed;
let mut result = vec![seed_seq[junc_vertex]];
let mut petals = jtype.inner.clone();
petals.push(jtype.ccw);
for petal in &petals {
let petal_seq = tileset.rat(petal.tile_type_id).seq();
let petal_angle = petal_seq[petal.canon_offset];
let prev = *result.last().unwrap();
let next = glue::junction_angle::<T>(petal_angle, prev);
result.push(next);
}
result
}
fn flower_petal_glue_trusted<T: IsRing>(
patch: &mut WithJunctions<BasicPatch<T>>,
mut junc_pos: usize,
targets: &[EdgeInfo],
prior_juncs: &mut [usize],
) -> Option<usize> {
let tileset = Arc::clone(patch.tileset());
for target in targets {
let n_old = patch.len();
let tile_seq = tileset.rat(target.tile_type_id).seq();
let mlen = forward_match_length(patch.angles(), junc_pos, tile_seq, target.canon_offset);
let pm = PatchMatch::new(
EdgeRange::new(junc_pos, mlen),
Segment::new(
target.tile_type_id,
EdgeRange::new(target.canon_offset, mlen),
),
);
let delta = patch.add_tile_trusted(&pm)?;
let ccw_pos = (delta.removed.start_offset + delta.removed.len) % n_old;
for j in prior_juncs.iter_mut() {
*j = (*j + n_old - ccw_pos) % n_old;
}
junc_pos = delta.new_edges.start;
}
Some(junc_pos)
}
impl<T: IsRing> BasicPatch<T> {
pub fn compute_candidates_covering_position(
match_index: &Arc<MatchTypeIndex<T>>,
angles: &[i8],
edges: &[EdgeInfo],
target: usize,
) -> Vec<PatchMatch> {
let n = angles.len();
let tileset = match_index.tileset();
let max_tile_len = tileset.rats().iter().map(|r| r.len()).max().unwrap_or(0);
let mut result: Vec<PatchMatch> = Vec::new();
let segments = compute_segments(angles, edges, tileset);
let junctions_set: FxHashSet<usize> = compute_junctions(angles, edges, tileset)
.into_iter()
.collect();
let enumr = CandidateEnumerator::new(angles, match_index);
let mut seen: CandidateSeen = FxHashSet::default();
{
let mut push = |pm: PatchMatch| {
if cyclic_range_contains(pm.a_range.start_offset, pm.len(), target, n) {
result.push(pm);
}
};
for offset in 0..max_tile_len.min(n) {
let pos = (target + n - offset) % n;
if let Some(segment) = segments.iter().find(|s| {
pos >= s.range.start_offset && pos < s.range.start_offset + s.range.len
}) {
let tile_id = segment.tile_seg.tile_id;
let tile_offset = (segment.tile_seg.range.start_offset
+ (pos - segment.range.start_offset))
% tileset.rat(tile_id).len();
enumr.enumerate_at_position(pos, tile_id, tile_offset, &mut seen, &mut push);
}
if junctions_set.contains(&pos) {
enumr.enumerate_at_junction(
pos,
&mut seen,
|start_a, len| cyclic_range_contains(start_a, len, target, n),
&mut push,
);
}
}
}
result
}
pub fn compute_all_candidates(
match_index: &Arc<MatchTypeIndex<T>>,
angles: &[i8],
edges: &[EdgeInfo],
) -> Vec<Vec<PatchMatch>> {
let n = angles.len();
let tileset = match_index.tileset();
let mut result = vec![Vec::new(); n];
let segments = compute_segments(angles, edges, tileset);
let junctions = compute_junctions(angles, edges, tileset);
let enumr = CandidateEnumerator::new(angles, match_index);
let mut seen: CandidateSeen = FxHashSet::default();
{
let mut push = |pm: PatchMatch| result[pm.a_range.start_offset].push(pm);
for segment in &segments {
let tile_id = segment.tile_seg.tile_id;
let seg_len = segment.range.len;
for local_k in 0..seg_len {
let tile_offset = (segment.tile_seg.range.start_offset + local_k)
% tileset.rat(tile_id).len();
let patch_pos = segment.range.start_offset + local_k;
enumr.enumerate_at_position(
patch_pos,
tile_id,
tile_offset,
&mut seen,
&mut push,
);
}
}
for &junc_idx in &junctions {
enumr.enumerate_at_junction(junc_idx, &mut seen, |_, _| true, &mut push);
}
}
result
}
pub fn get_all_matches(&self) -> Vec<PatchMatch> {
Self::compute_all_candidates(
&self.match_index,
self.boundary_seq.angles(),
self.boundary_seq.edges(),
)
.into_iter()
.flatten()
.collect()
}
pub fn get_matches_touching_vertex(&self, vertex_index: usize) -> Vec<PatchMatch> {
let n = self.boundary_seq.len();
if n == 0 {
return Vec::new();
}
let k = self
.match_index
.tileset()
.rats()
.iter()
.map(|r| r.len())
.max()
.unwrap_or(0)
.min(n);
let anchors: Vec<usize> = (0..2 * k).map(|o| (vertex_index + n - k + o) % n).collect();
let juncs: Vec<usize> = (0..=k).map(|o| (vertex_index + n - o) % n).collect();
let source = self.candidates_windowed(&anchors, &juncs);
let mut result = Vec::new();
for offset in 0..=k {
let start = (vertex_index + n - offset) % n;
for pm in &source[start] {
if cyclic_range_contains(pm.a_range.start_offset, pm.len(), vertex_index, n) {
result.push(*pm);
}
}
}
result
}
fn candidates_windowed(&self, anchors: &[usize], junctions: &[usize]) -> Vec<Vec<PatchMatch>> {
let n = self.boundary_seq.len();
let angles = self.boundary_seq.angles();
let edges = self.boundary_seq.edges();
let tileset = self.match_index.tileset();
let enumr = CandidateEnumerator::new(angles, &self.match_index);
let mut seen: CandidateSeen = FxHashSet::default();
let mut result: Vec<Vec<PatchMatch>> = vec![Vec::new(); n];
{
let mut push = |pm: PatchMatch| result[pm.a_range.start_offset].push(pm);
for &p in anchors {
enumr.enumerate_at_position(
p,
edges[p].tile_type_id,
edges[p].canon_offset,
&mut seen,
&mut push,
);
}
for &j in junctions {
if is_junction_at(angles, edges, tileset, j) {
enumr.enumerate_at_junction(j, &mut seen, |_, _| true, &mut push);
}
}
}
result
}
pub fn get_matches_in_edge_range(&self, start_edge: usize, end_edge: usize) -> Vec<PatchMatch> {
let n = self.boundary_seq.len();
if n == 0 {
return Vec::new();
}
let range_len = (end_edge + n - start_edge) % n + 1;
let absorbs = |pm: &PatchMatch| {
cyclic_arcs_overlap(start_edge, range_len, pm.a_range.start_offset, pm.len(), n)
};
let max_len = self
.match_index
.tileset()
.rats()
.iter()
.map(|r| r.len())
.max()
.unwrap_or(0)
.min(n);
let pad = max_len.saturating_sub(1);
let win = (range_len + 2 * pad).min(n);
let base = (start_edge + n - pad) % n;
let anchors: Vec<usize> = (0..win).map(|o| (base + o) % n).collect();
let juncs: Vec<usize> = (0..range_len).map(|d| (start_edge + d) % n).collect();
self.candidates_windowed(&anchors, &juncs)
.into_iter()
.flatten()
.filter(|pm| absorbs(pm))
.collect()
}
#[allow(clippy::len_without_is_empty)]
pub fn len(&self) -> usize {
self.boundary_seq.len()
}
pub fn angles(&self) -> &[i8] {
self.boundary_seq.angles()
}
pub fn to_rat(&self) -> Rat<T> {
Rat::from_slice_trusted(self.boundary_seq.angles())
}
pub fn tileset(&self) -> &Arc<TileSet<T>> {
self.match_index.tileset()
}
pub fn match_index(&self) -> &Arc<MatchTypeIndex<T>> {
&self.match_index
}
pub fn edges(&self) -> &[EdgeInfo] {
self.boundary_seq.edges()
}
pub fn patch_tile_ids(&self) -> &[usize] {
&self.patch_tile_ids
}
pub fn boundary_positions(&self) -> &[T] {
&self.boundary.positions
}
pub fn next_tile_id(&self) -> usize {
self.next_tile_id
}
pub fn normalize(&mut self) -> Relabel {
let n = self.boundary_seq.len();
if n == 0 {
return Relabel { rot: 0 };
}
let rot = crate::stringmatch::lex_min_rot(self.boundary_seq.angles());
if rot != 0 {
self.boundary_seq.rotate_left(rot);
self.patch_tile_ids.rotate_left(rot);
self.boundary.rotate_left(rot);
}
let mut remap: rustc_hash::FxHashMap<usize, usize> = rustc_hash::FxHashMap::default();
let mut next = 0usize;
for id in &mut self.patch_tile_ids {
let new_id = *remap.entry(*id).or_insert_with(|| {
let v = next;
next += 1;
v
});
*id = new_id;
}
self.next_tile_id = next;
Relabel { rot }
}
pub fn is_junction(&self, i: usize) -> bool {
if self.boundary_seq.edges().is_empty() {
return false;
}
is_junction_at(
self.boundary_seq.angles(),
self.boundary_seq.edges(),
self.match_index.tileset(),
i,
)
}
pub fn single_tile(tileset: Arc<TileSet<T>>, tile_id: usize) -> Self {
Self::single_tile_with_index(Arc::new(MatchTypeIndex::new(tileset)), tile_id)
}
pub fn single_tile_with_index(match_index: Arc<MatchTypeIndex<T>>, tile_id: usize) -> Self {
let angles: Vec<i8> = match_index.tileset().rat(tile_id).seq().to_vec();
let n = angles.len();
let edges: Vec<EdgeInfo> = (0..n)
.map(|i| EdgeInfo {
tile_type_id: tile_id,
canon_offset: i,
})
.collect();
let boundary = BoundaryGrid::<T>::from_angles(&angles);
BasicPatch {
match_index,
boundary_seq: Boundary::new(angles, edges),
boundary,
patch_tile_ids: vec![0; n],
next_tile_id: 1,
}
}
pub fn add_tile(&mut self, pm: &PatchMatch) -> Option<GlueDelta> {
self.add_tile_growing(pm, false)
}
pub fn add_tile_trusted(&mut self, pm: &PatchMatch) -> Option<GlueDelta> {
debug_assert!(
forward_match_length(
self.boundary_seq.angles(),
pm.a_range.start_offset,
self.match_index.tileset().rat(pm.b.tile_id).seq(),
pm.b.range.start_offset,
) >= pm.len(),
"add_tile_trusted: pm does not describe a real match \
(a_range.start_offset={}, b.range.start_offset={}, mlen={})",
pm.a_range.start_offset,
pm.b.range.start_offset,
pm.len(),
);
self.add_tile_growing(pm, true)
}
pub fn with_tile(&self, pm: &PatchMatch) -> Option<Self> {
let mut next = self.clone();
next.add_tile(pm).is_some().then_some(next)
}
fn glue_geometry(&self, pm: &PatchMatch) -> Option<GlueGeometry<T>> {
let n = self.len();
let mlen = pm.len();
let m = self.match_index.tileset().rat(pm.b.tile_id).seq().len();
debug_assert!(
mlen > 0 && mlen <= n && mlen <= m,
"glue_geometry: invalid mlen={mlen} (n={n}, m={m}); \
get_all_matches() should never produce this"
);
if mlen == 0 || mlen > n || mlen > m {
return None;
}
let new_angles = match compute_glue_angles::<T>(
self.boundary_seq.angles(),
pm,
self.match_index.tileset(),
) {
Ok(a) => a,
Err(why) => {
debug_assert!(
false,
"compute_glue_angles rejected ({why:?}); get_all_matches() \
should already filter +/-hturn glues via try_glue_match"
);
return None;
}
};
let seg_len_old = n - mlen;
let seg_len_new = m - mlen;
debug_assert!(
seg_len_old + seg_len_new > 0,
"glue_geometry: new_len == 0 is geometrically impossible -- \
would require placing the new tile entirely inside the existing patch"
);
if seg_len_old + seg_len_new == 0 {
return None;
}
let ccw_pos = (pm.a_range.start_offset + mlen) % n;
let removed_ids = self.boundary.edge_ids_of_run(pm.a_range.start_offset, mlen);
let positions = self.boundary_positions();
let cw_junction = positions[pm.a_range.start_offset];
let ccw_junction = positions[ccw_pos];
let initial_dir = {
let prev = (pm.a_range.start_offset + n - 1) % n;
dir_of_edge::<T>(positions[prev], positions[pm.a_range.start_offset])
};
let new_tile_positions =
trace_polyline_from::<T>(cw_junction, initial_dir, &new_angles[seg_len_old..]);
debug_assert_eq!(
*new_tile_positions.last().unwrap(),
ccw_junction,
"new tile trace should end at CCW junction"
);
Some(GlueGeometry {
new_angles,
seg_len_old,
seg_len_new,
ccw_pos,
removed_ids,
ccw_junction,
new_tile_positions,
})
}
fn add_tile_growing(&mut self, pm: &PatchMatch, trusted: bool) -> Option<GlueDelta> {
let g = self.glue_geometry(pm)?;
let GlueGeometry {
new_angles,
seg_len_old,
seg_len_new,
ccw_pos,
removed_ids,
ccw_junction,
new_tile_positions,
} = g;
let new_len = seg_len_old + seg_len_new;
let m = seg_len_new + pm.len();
let spliced = if trusted {
self.boundary.splice_run_trusted(
&removed_ids,
ccw_pos,
seg_len_old,
seg_len_new,
&new_tile_positions,
ccw_junction,
)
} else {
self.boundary.try_splice_run(
&removed_ids,
ccw_pos,
seg_len_old,
seg_len_new,
&new_tile_positions,
ccw_junction,
)
};
if !spliced {
return None;
}
let (new_edges, new_patch_tile_ids) = build_glued_edges(
self.boundary_seq.edges(),
&self.patch_tile_ids,
pm,
m,
self.next_tile_id,
);
debug_assert_eq!(new_edges.len(), new_len);
self.boundary_seq.replace(new_angles, new_edges);
self.patch_tile_ids = new_patch_tile_ids;
let new_id = self.next_tile_id;
self.next_tile_id += 1;
#[cfg(debug_assertions)]
if trusted {
debug_assert!(
Snake::<T>::try_from(self.boundary_seq.angles())
.map(|s| s.is_closed())
.unwrap_or(false),
"add_tile_trusted produced a non-simple-closed boundary -- the caller's \
valid-match / non-colliding guarantee was violated"
);
}
Some(GlueDelta {
removed: pm.a_range,
new_edges: seg_len_old..new_len,
new_id,
})
}
}
impl<T: IsRing> WithJunctions<BasicPatch<T>> {
pub fn from_parts(
match_index: Arc<MatchTypeIndex<T>>,
angles: Vec<i8>,
edges: Vec<EdgeInfo>,
inner_petals: Vec<Vec<EdgeInfo>>,
patch_tile_ids: Vec<usize>,
next_tile_id: usize,
) -> Option<Self> {
if angles.is_empty()
|| angles.len() != edges.len()
|| inner_petals.len() != angles.len()
|| patch_tile_ids.len() != angles.len()
{
return None;
}
let boundary = BoundaryGrid::<T>::from_angles(&angles);
let inner = BasicPatch {
match_index,
boundary_seq: Boundary::new(angles, edges),
boundary,
patch_tile_ids,
next_tile_id,
};
Some(WithJunctions {
inner,
inner_petals,
})
}
#[cfg(test)]
pub fn construct_minimal_witness(
jtype: &OpenJunctionType,
match_index: Arc<MatchTypeIndex<T>>,
) -> Option<(Self, usize)> {
let (patch, juncs) =
Self::construct_witness_from_jt_sequence(std::slice::from_ref(jtype), match_index)?;
Some((patch, juncs[0]))
}
pub fn construct_witness_from_jt_sequence(
jtypes: &[OpenJunctionType],
match_index: Arc<MatchTypeIndex<T>>,
) -> Option<(Self, Vec<usize>)> {
if jtypes.is_empty() {
return None;
}
let result = Self::construct_witness_from_jt_sequence_inner(jtypes, 0, &match_index);
#[cfg(debug_assertions)]
if let Some((patch, _)) = &result {
let simple_closed = Snake::<T>::try_from(patch.angles())
.map(|s| s.is_closed())
.unwrap_or(false);
debug_assert!(
simple_closed,
"construct_witness_from_jt_sequence: result is not a simple closed polygon \
-- a jtypes precondition was violated (a cyclic sequence, or a fully-interior \
tile not captured by any junction)"
);
}
result
}
fn construct_witness_from_jt_sequence_inner(
jtypes: &[OpenJunctionType],
start: usize,
match_index: &Arc<MatchTypeIndex<T>>,
) -> Option<(Self, Vec<usize>)> {
let tileset = match_index.tileset();
let n_jts = jtypes.len();
let seed_id = jtypes[start].cw.tile_type_id;
let seed_seq = tileset.rat(seed_id).seq();
let n_seed = seed_seq.len();
let mut patch = Self::single_tile_with_index(Arc::clone(match_index), seed_id);
let mut junc_positions = Vec::new();
let jt0 = &jtypes[start];
let junc_pos = (jt0.cw.canon_offset + 1) % n_seed;
let mut all_targets = jt0.inner.clone();
all_targets.push(jt0.ccw);
let new_junc = flower_petal_glue_trusted::<T>(
&mut patch,
junc_pos,
&all_targets,
&mut junc_positions,
)?;
if patch.angles()[new_junc].abs() == T::hturn() {
return None;
}
junc_positions.push(new_junc);
for step in 1..n_jts {
let k_prev = (start + step - 1) % n_jts;
let k = (start + step) % n_jts;
let jt = &jtypes[k];
let jt_prev = &jtypes[k_prev];
let tile_size = tileset.rat(jt_prev.ccw.tile_type_id).seq().len();
let offset = ((jt.cw.canon_offset as isize - jt_prev.ccw.canon_offset as isize
+ tile_size as isize) as usize)
% tile_size
+ 1;
let prev_junc = junc_positions[step - 1];
let n = patch.len();
let junc_k = (prev_junc + offset) % n;
let angle_seq = junction_angle_sequence(jt, tileset.as_ref());
let mut all_targets = jt.inner.clone();
all_targets.push(jt.ccw);
let boundary_angle = patch.angles()[junc_k];
let skip = angle_seq
.iter()
.position(|&a| a == boundary_angle)
.unwrap_or(0);
let targets = &all_targets[skip..];
if targets.is_empty() {
junc_positions.push(junc_k);
continue;
}
let new_junc =
flower_petal_glue_trusted::<T>(&mut patch, junc_k, targets, &mut junc_positions)?;
if patch.angles()[new_junc].abs() == T::hturn() {
return None;
}
junc_positions.push(new_junc);
}
Some((patch, junc_positions))
}
pub fn single_tile(tileset: Arc<TileSet<T>>, tile_id: usize) -> Self {
Self::single_tile_with_index(Arc::new(MatchTypeIndex::new(tileset)), tile_id)
}
pub fn single_tile_with_index(match_index: Arc<MatchTypeIndex<T>>, tile_id: usize) -> Self {
let inner = BasicPatch::single_tile_with_index(match_index, tile_id);
let n = inner.len();
WithJunctions {
inner,
inner_petals: vec![vec![]; n],
}
}
pub fn inner_petals(&self) -> &[Vec<EdgeInfo>] {
&self.inner_petals
}
pub fn junction_type_at(&self, i: usize) -> Option<OpenJunctionType> {
let n = self.inner.len();
if n == 0 || i >= n || !self.is_junction(i) {
return None;
}
Some(OpenJunctionType {
cw: self.inner.edges()[(i + n - 1) % n],
inner: self.inner_petals[i].clone(),
ccw: self.inner.edges()[i],
})
}
pub fn neighbor_junction_offsets(&self, pos: usize) -> Option<(usize, usize)> {
let n = self.inner.edges().len();
if n == 0 || pos >= n {
return None;
}
let mut j_cw = (pos + n - 1) % n;
while j_cw != pos && !self.is_junction(j_cw) {
j_cw = (j_cw + n - 1) % n;
}
let mut j_ccw = (pos + 1) % n;
while j_ccw != pos && !self.is_junction(j_ccw) {
j_ccw = (j_ccw + 1) % n;
}
let cw_offset = self.inner.edges()[j_cw].canon_offset;
let ccw_prev = (j_ccw + n - 1) % n;
let ccw_edge = self.inner.edges()[ccw_prev];
let tile_len = self.inner.tileset().rat(ccw_edge.tile_type_id).len();
let ccw_offset = (ccw_edge.canon_offset + 1) % tile_len;
Some((cw_offset, ccw_offset))
}
#[cfg(test)]
pub(crate) fn tile_segments(&self) -> Vec<PatchSegment> {
if self.inner.edges().is_empty() {
return vec![];
}
compute_segments(
self.inner.angles(),
self.inner.edges(),
self.inner.tileset(),
)
}
fn add_tile_growing(&mut self, pm: &PatchMatch, trusted: bool) -> Option<GlueDelta> {
let first_glue = self.inner.next_tile_id() == 1;
let old_edges = self.inner.edges().to_vec();
let old_ptids = self.inner.patch_tile_ids().to_vec();
let delta = if trusted {
self.inner.add_tile_trusted(pm)? } else {
self.inner.add_tile(pm)? };
let new_n = delta.new_edges.end;
let new_petals = if first_glue {
vec![vec![]; new_n]
} else {
update_inner_petals(
&self.inner_petals,
&old_edges,
pm,
new_n,
&old_ptids,
self.inner.tileset(),
)
};
self.inner_petals = new_petals;
Some(delta)
}
pub fn add_tile(&mut self, pm: &PatchMatch) -> Option<GlueDelta> {
self.add_tile_growing(pm, false)
}
pub fn add_tile_trusted(&mut self, pm: &PatchMatch) -> Option<GlueDelta> {
self.add_tile_growing(pm, true)
}
pub fn with_tile(&self, pm: &PatchMatch) -> Option<Self> {
let mut next = self.clone();
next.add_tile(pm).is_some().then_some(next)
}
pub fn normalize(&mut self) -> Relabel {
let r = self.inner.normalize();
if r.rot != 0 {
self.inner_petals.rotate_left(r.rot);
}
r
}
pub fn compute_candidates_covering_position(
match_index: &Arc<MatchTypeIndex<T>>,
angles: &[i8],
edges: &[EdgeInfo],
target: usize,
) -> Vec<PatchMatch> {
BasicPatch::compute_candidates_covering_position(match_index, angles, edges, target)
}
pub fn compute_all_candidates(
match_index: &Arc<MatchTypeIndex<T>>,
angles: &[i8],
edges: &[EdgeInfo],
) -> Vec<Vec<PatchMatch>> {
BasicPatch::compute_all_candidates(match_index, angles, edges)
}
pub fn get_all_matches(&self) -> Vec<PatchMatch> {
self.inner.get_all_matches()
}
pub fn get_matches_touching_vertex(&self, vertex_index: usize) -> Vec<PatchMatch> {
self.inner.get_matches_touching_vertex(vertex_index)
}
pub 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)
}
#[allow(clippy::len_without_is_empty)]
pub fn len(&self) -> usize {
self.inner.len()
}
pub fn angles(&self) -> &[i8] {
self.inner.angles()
}
pub fn to_rat(&self) -> Rat<T> {
self.inner.to_rat()
}
pub fn tileset(&self) -> &Arc<TileSet<T>> {
self.inner.tileset()
}
pub fn match_index(&self) -> &Arc<MatchTypeIndex<T>> {
self.inner.match_index()
}
pub fn edges(&self) -> &[EdgeInfo] {
self.inner.edges()
}
pub fn patch_tile_ids(&self) -> &[usize] {
self.inner.patch_tile_ids()
}
pub fn boundary_positions(&self) -> &[T] {
self.inner.boundary_positions()
}
pub fn next_tile_id(&self) -> usize {
self.inner.next_tile_id()
}
pub fn is_junction(&self, i: usize) -> bool {
self.inner.is_junction(i)
}
}
#[derive(Debug, Clone)]
pub struct GlueDelta {
pub removed: EdgeRange,
pub new_edges: std::ops::Range<usize>,
pub new_id: usize,
}
#[derive(Debug, Clone, Copy)]
pub struct Relabel {
pub rot: usize,
}
struct GlueGeometry<T: IsRing> {
new_angles: Vec<i8>,
seg_len_old: usize,
seg_len_new: usize,
ccw_pos: usize,
removed_ids: Vec<usize>,
ccw_junction: T,
new_tile_positions: Vec<T>,
}
fn build_glued_edges(
old_edges: &[EdgeInfo],
old_patch_tile_ids: &[usize],
pm: &PatchMatch,
m_tile: usize,
new_tile_id: usize,
) -> (Vec<EdgeInfo>, Vec<usize>) {
let n = old_edges.len();
let mlen = pm.len();
let seg_len_old = n - mlen;
let seg_len_new = m_tile - mlen;
let ccw_pos = (pm.a_range.start_offset + mlen) % n;
let new_len = seg_len_old + seg_len_new;
let mut new_edges = Vec::with_capacity(new_len);
let mut new_ptids = Vec::with_capacity(new_len);
for i in 0..seg_len_old {
new_edges.push(old_edges[(ccw_pos + i) % n]);
new_ptids.push(old_patch_tile_ids[(ccw_pos + i) % n]);
}
if seg_len_new > 0 {
new_edges.push(EdgeInfo {
tile_type_id: pm.b.tile_id,
canon_offset: pm.b.range.start_offset,
});
new_ptids.push(new_tile_id);
for k in 1..seg_len_new {
new_edges.push(EdgeInfo {
tile_type_id: pm.b.tile_id,
canon_offset: (pm.b.range.start_offset + k) % m_tile,
});
new_ptids.push(new_tile_id);
}
}
(new_edges, new_ptids)
}
type CandidateSeen = FxHashSet<(usize, usize, usize, usize)>;
struct CandidateEnumerator<'a, T: IsRing> {
angles: &'a [i8],
rat: Rat<T>,
match_index: &'a MatchTypeIndex<T>,
}
impl<'a, T: IsRing> CandidateEnumerator<'a, T> {
fn new(angles: &'a [i8], match_index: &'a MatchTypeIndex<T>) -> Self {
let rat = Rat::from_slice_trusted_keep_rotation(angles);
Self {
angles,
rat,
match_index,
}
}
fn tileset(&self) -> &TileSet<T> {
self.match_index.tileset()
}
fn enumerate_at_position(
&self,
pos: usize,
tile_id: usize,
tile_offset: usize,
seen: &mut CandidateSeen,
push: &mut impl FnMut(PatchMatch),
) {
for cand in self
.match_index
.candidates_starting_at(tile_id, tile_offset)
{
self.try_candidate(pos, cand, seen, push);
}
}
fn try_candidate(
&self,
pos: usize,
cand: &Segment,
seen: &mut CandidateSeen,
push: &mut impl FnMut(PatchMatch),
) {
let tile_b = self.tileset().rat(cand.tile_id);
let (ns, len, ne) = self
.rat
.get_match(
MatchSeed::new(pos as i64, cand.range.start_offset as i64),
tile_b,
)
.parts();
if len == 0 {
return;
}
let ns_u = ns;
let ne_u = ne;
if !junctions_glueable(self.angles, ns_u, len, tile_b.seq(), ne_u) {
return;
}
if !seen.insert((ns_u, len, ne_u, cand.tile_id)) {
return;
}
if self.rat.is_locally_glueable(
Match::new(EdgeRange::new(ns, len), EdgeRange::new(ne, len)),
tile_b,
) {
push(PatchMatch::new(
EdgeRange::new(ns_u, len),
Segment::new(cand.tile_id, EdgeRange::new(ne_u, len)),
));
}
}
fn enumerate_at_junction(
&self,
pos: usize,
seen: &mut CandidateSeen,
keep: impl Fn(usize, usize) -> bool,
push: &mut impl FnMut(PatchMatch),
) {
let tileset = self.tileset();
for tile_id_b in 0..tileset.num_tiles() {
let tile_b = tileset.rat(tile_id_b);
let b_seq = tile_b.seq();
let m = b_seq.len();
for ib in 0..m {
if !junctions_glueable(self.angles, pos, 1, b_seq, ib) {
continue;
}
let (ns, len, ne) = self
.rat
.get_match(MatchSeed::new(pos as i64, ib as i64), tile_b)
.parts();
if len != 1 {
continue;
}
let ns_u = ns;
let ne_u = ne;
if !seen.insert((ns_u, len, ne_u, tile_id_b)) {
continue;
}
if !keep(ns_u, len) {
continue;
}
if self.rat.is_locally_glueable(
Match::new(EdgeRange::new(ns, len), EdgeRange::new(ne, len)),
tile_b,
) {
push(PatchMatch::new(
EdgeRange::new(ns_u, len),
Segment::new(tile_id_b, EdgeRange::new(ne_u, len)),
));
}
}
}
}
}
fn compute_glue_angles<T: IsRing>(
angles: &[i8],
pm: &PatchMatch,
tileset: &Arc<TileSet<T>>,
) -> Result<Vec<i8>, DegenerateGlue> {
let other_seq = tileset.rat(pm.b.tile_id).seq();
glue::glue_angles_local::<T>(
angles,
other_seq,
pm.a_range.start_offset,
pm.len(),
pm.b.range.start_offset,
)
.map_err(|e| match e {
glue::GlueReject::Keystone => DegenerateGlue::KeystoneHturn,
glue::GlueReject::Junction => DegenerateGlue::JunctionHturn,
})
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum DegenerateGlue {
KeystoneHturn,
JunctionHturn,
}
fn trace_polyline_from<T: IsRing>(start: T, initial_dir: i8, angles: &[i8]) -> Vec<T> {
let mut positions = Vec::with_capacity(angles.len() + 1);
positions.push(start);
let mut dir = initial_dir;
for &a in angles {
dir = (dir as i64 + a as i64).rem_euclid(T::turn() as i64) as i8;
let last = *positions.last().unwrap();
positions.push(last + T::unit(dir));
}
positions
}
pub(crate) fn trace_boundary_positions<T: IsRing>(angles: &[i8]) -> Vec<T> {
trace_polyline_from(T::zero(), 0, angles)
}
pub fn boundary_vertices<T: IsRing>(seq: &[i8]) -> Vec<T> {
trace_boundary_positions::<T>(seq)[..seq.len()].to_vec()
}
impl<T: IsRing> BoundaryGrid<T> {
fn from_angles(angles: &[i8]) -> Self {
let positions = trace_boundary_positions::<T>(angles);
let n = angles.len();
let mut grid = UnitSquareGrid::new();
let mut edge_data = Vec::with_capacity(n);
let boundary_edge_ids: Vec<usize> = (0..n).collect();
for i in 0..n {
let p1 = positions[i];
let p2 = positions[i + 1];
edge_data.push((p1, p2));
for cell in UnitSquareGrid::edge_neighborhood_of(p1, p2) {
grid.add(cell, i);
}
}
Self {
positions,
grid,
edge_data,
boundary_edge_ids,
next_edge_id: n,
}
}
fn register_edge(&mut self, p1: T, p2: T, id: usize) {
for cell in UnitSquareGrid::edge_neighborhood_of(p1, p2) {
self.grid.add(cell, id);
}
}
fn unregister_edge(&mut self, id: usize) {
let (p1, p2) = self.edge_data[id];
for cell in UnitSquareGrid::edge_neighborhood_of(p1, p2) {
self.grid.remove(cell, id);
}
}
fn check_edge_clear(&self, p1: T, p2: T, allowed_endpoint: Option<T>) -> bool {
let is_allowed = allowed_endpoint == Some(p2);
for cell in UnitSquareGrid::edge_neighborhood_of(p1, p2) {
for &id in self.grid.get(cell) {
let (x, y) = self.edge_data[id];
if !is_allowed && (p2 == x || p2 == y) {
return false;
}
if intersect_unit_segments(&(p1, p2), &(x, y)) {
return false;
}
}
}
true
}
fn polyline_all_clear(&self, positions: &[T], allowed_last_endpoint: T) -> bool {
let n_edges = positions.len().saturating_sub(1);
for i in 0..n_edges {
let allowed = (i == n_edges - 1).then_some(allowed_last_endpoint);
if !self.check_edge_clear(positions[i], positions[i + 1], allowed) {
return false;
}
}
true
}
fn edge_ids_of_run(&self, start: usize, len: usize) -> Vec<usize> {
let n = self.positions.len() - 1;
(0..len)
.map(|i| self.boundary_edge_ids[(start + i) % n])
.collect()
}
fn rotate_left(&mut self, rot: usize) {
self.boundary_edge_ids.rotate_left(rot);
let last_idx = self.positions.len() - 1;
self.positions.truncate(last_idx);
self.positions.rotate_left(rot);
let first = self.positions[0];
self.positions.push(first);
}
fn try_splice_run(
&mut self,
removed_ids: &[usize],
ccw_pos: usize,
seg_len_old: usize,
seg_len_new: usize,
new_tile_positions: &[T],
ccw_junction: T,
) -> bool {
self.splice_run(
removed_ids,
ccw_pos,
seg_len_old,
seg_len_new,
new_tile_positions,
ccw_junction,
true,
)
}
fn splice_run_trusted(
&mut self,
removed_ids: &[usize],
ccw_pos: usize,
seg_len_old: usize,
seg_len_new: usize,
new_tile_positions: &[T],
ccw_junction: T,
) -> bool {
self.splice_run(
removed_ids,
ccw_pos,
seg_len_old,
seg_len_new,
new_tile_positions,
ccw_junction,
false,
)
}
#[allow(clippy::too_many_arguments)]
fn splice_run(
&mut self,
removed_ids: &[usize],
ccw_pos: usize,
seg_len_old: usize,
seg_len_new: usize,
new_tile_positions: &[T],
ccw_junction: T,
check: bool,
) -> bool {
let n = self.positions.len() - 1;
for &id in removed_ids {
self.unregister_edge(id);
}
if check {
if !self.polyline_all_clear(new_tile_positions, ccw_junction) {
for &id in removed_ids {
let (p1, p2) = self.edge_data[id];
self.register_edge(p1, p2, id);
}
return false;
}
} else {
debug_assert!(
self.polyline_all_clear(new_tile_positions, ccw_junction),
"splice_run_trusted: the trusted glue actually collides with the \
existing boundary -- the caller's non-colliding guarantee is violated"
);
}
let new_len = seg_len_old + seg_len_new;
let mut new_positions = Vec::with_capacity(new_len + 1);
for i in 0..=seg_len_old {
new_positions.push(self.positions[(ccw_pos + i) % n]);
}
for p in new_tile_positions.iter().take(seg_len_new + 1).skip(1) {
new_positions.push(*p);
}
let mut new_boundary_edge_ids = Vec::with_capacity(new_len);
for i in 0..seg_len_old {
new_boundary_edge_ids.push(self.boundary_edge_ids[(ccw_pos + i) % n]);
}
for i in 0..seg_len_new {
let id = self.next_edge_id;
self.next_edge_id += 1;
new_boundary_edge_ids.push(id);
let p1 = new_tile_positions[i];
let p2 = new_tile_positions[i + 1];
self.edge_data.push((p1, p2));
self.register_edge(p1, p2, id);
}
self.positions = new_positions;
self.boundary_edge_ids = new_boundary_edge_ids;
true
}
}
fn dir_of_edge<T: IsRing>(from: T, to: T) -> i8 {
let d = to - from;
for dir in 0..T::turn() {
if T::unit(dir) == d {
return dir;
}
}
unreachable!("dir_of_edge: ({from:?} -> {to:?}) is not a unit vector");
}
#[cfg(test)]
mod tests;