tilezz 0.1.1

Utilities to work with perfect-precision polygonal tiles built on top of cyclotomic integer rings.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

//! Closure-key prune.
//!
//! Pre-pass: DFS-enumerate every simple open snake up to length `L`
//! and store the set of `(endpoint, facing)` pairs they reach -- the
//! "closure keys" `K_{<=L}`. During the main DFS, when
//! `remaining_after <= L`, the candidate prefix can close iff its
//! required suffix's `(endpoint, facing)` is in `K_{<=L}`. Otherwise
//! no length-`<=remaining_after` continuation can complete it.
//!
//! Strictly stronger than any modular projection (it sees exact
//! lattice + facing info, not just a quotient). The cost is memory +
//! pre-pass time + a ring multiplication per hot-path check (to
//! compute the target suffix endpoint via
//! `target = -unit(-facing) * disp`).

use crate::cyclotomic::{IsRing, Units};
use crate::geom::snake::Snake;

/// Set of closure keys indexed by ring-coefficient vector + facing.
pub struct ClosureKeyPrune {
    /// Maximum tabulated suffix length. The prune fires only when
    /// `remaining_after <= max_l`.
    pub max_l: usize,
    /// `K_{<=L} = {(endpoint coords, facing) : reachable by some
    /// simple open snake of length 0..=L}`. Length 0 (the empty
    /// snake, key `(0, 0)`) is included so already-closed candidates
    /// aren't incorrectly rejected.
    pub keys: rustc_hash::FxHashSet<(Vec<i64>, i8)>,
}

fn collect_closure_keys_dfs<ZZ: IsRing>(
    snake: &mut Snake<ZZ>,
    max_l: usize,
    keys: &mut rustc_hash::FxHashSet<(Vec<i64>, i8)>,
) {
    if snake.angles().len() >= max_l {
        return;
    }
    let turn = ZZ::turn();
    for direction in ((-ZZ::hturn() + 1)..ZZ::hturn()).rev() {
        if !snake.add(direction) {
            continue;
        }
        // Normalize facing to 0..n-1: `Snake::direction` returns
        // truncating-mod (can be negative for net-CW walks); the
        // hot-path lookup uses `rem_euclid` (always 0..n-1), so we
        // canonicalize here to make the hash keys compatible.
        let facing = snake.direction().rem_euclid(turn);
        keys.insert((snake.offset().int_coeffs_slice().to_vec(), facing));
        collect_closure_keys_dfs::<ZZ>(snake, max_l, keys);
        snake.pop();
    }
}

pub fn collect_closure_keys<ZZ: IsRing>(max_l: usize) -> rustc_hash::FxHashSet<(Vec<i64>, i8)> {
    let mut keys = rustc_hash::FxHashSet::default();
    // Empty snake's key: closure is already achieved.
    let phi = <ZZ as Units>::unit(0).int_coeffs_slice().len();
    keys.insert((vec![0i64; phi], 0));
    let mut snake: Snake<ZZ> = Snake::new();
    collect_closure_keys_dfs::<ZZ>(&mut snake, max_l, &mut keys);
    keys
}

/// Ring-dispatch wrapper for [`collect_closure_keys`].
pub fn collect_closure_keys_for_ring(
    ring: u8,
    max_l: usize,
) -> rustc_hash::FxHashSet<(Vec<i64>, i8)> {
    crate::dispatch_ring!(ring, collect_closure_keys::<ZZ>(max_l))
}