tilezz 0.2.0

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

//! Breadth-first exploration of the additive point set a cyclotomic
//! ring's unit steps generate.
//!
//! From the origin, each round takes one unit step (a root of unity,
//! [`Units::unit`]) in every direction from every point reached so far,
//! deduplicating through a caller-supplied `fold`. With the identity fold
//! this enumerates the reachable point cloud layer by layer; with a
//! unit-cell reduction it explores the quotient torus instead. The walk
//! needs only `Units`, so it is ring-generic -- any ring-specific
//! constraint (e.g. a square-cell fold requiring the imaginary unit)
//! lives entirely in the `fold` the caller supplies.

use std::collections::HashSet;
use std::sync::Mutex;

use crate::cyclotomic::{IsRing, Units};

/// Points reachable in up to `n` unit steps from the origin, one `Vec`
/// per round: `round_pts[0]` is the origin seed and `round_pts[k]` holds
/// the points first reached at distance `k`.
///
/// `fold` maps each stepped-to point to the representative used for
/// visited-set deduplication -- the identity for free exploration, or a
/// unit-cell reduction for a torus view. `on_round(k, new_count)` is
/// invoked on the calling thread after each round `k` for progress
/// reporting (pass `|_, _| {}` if unwanted). Work within a round is
/// split across up to `num_threads` scoped threads sharing the visited
/// set behind a mutex.
pub fn reachable_points<ZZ, F, R>(
    n: usize,
    num_threads: usize,
    fold: F,
    mut on_round: R,
) -> Vec<Vec<ZZ>>
where
    ZZ: IsRing + Units + Send + Sync,
    F: Fn(&ZZ) -> ZZ + Sync,
    R: FnMut(usize, usize),
{
    let start: ZZ = ZZ::zero();
    let visited: Mutex<HashSet<ZZ>> = Mutex::new(HashSet::from([start]));
    let mut round_pts: Vec<Vec<ZZ>> = vec![vec![start]];

    let fold = &fold;
    let num_threads = num_threads.max(1);

    for k in 1..=n {
        let last = round_pts.last().unwrap();
        // Chunk size (kept from the original): at least `num_threads`, so
        // small frontiers still run on one chunk.
        let per_thread = num_threads.max(last.len() / num_threads).max(1);

        let curr: Mutex<Vec<ZZ>> = Mutex::new(Vec::new());
        let visited_ref = &visited;
        let curr_ref = &curr;

        std::thread::scope(|s| {
            for chunk in last.chunks(per_thread) {
                s.spawn(move || {
                    for p in chunk {
                        for d in 0..ZZ::turn() {
                            let raw: ZZ = *p + <ZZ as Units>::unit(d);
                            let dest = fold(&raw);
                            // Release the visited lock before touching
                            // `curr` so we never hold both at once.
                            let is_new = visited_ref.lock().unwrap().insert(dest);
                            if is_new {
                                curr_ref.lock().unwrap().push(dest);
                            }
                        }
                    }
                });
            }
        });

        let curr = curr.into_inner().unwrap();
        on_round(k, curr.len());
        round_pts.push(curr);
    }

    round_pts
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::cyclotomic::ZZ4;
    use crate::cyclotomic::Zero;
    use crate::cyclotomic::geometry::point_mod_rect;

    #[test]
    fn zz4_free_reaches_the_l1_ball() {
        // ZZ4 unit steps are +-1, +-i. Free exploration reaches the L1
        // ball: round 1 = the 4 neighbours, round 2 = the 8 points at L1
        // distance 2 ((+-2,0),(0,+-2),(+-1,+-1)).
        let rounds = reachable_points::<ZZ4, _, _>(2, 1, |p| *p, |_, _| {});
        assert_eq!(rounds[0].len(), 1);
        assert_eq!(rounds[1].len(), 4);
        assert_eq!(rounds[2].len(), 8);
    }

    #[test]
    fn zz4_unit_cell_fold_collapses_cardinal_steps() {
        // Folding into the origin-centered unit square: the 4 cardinal
        // unit steps land one period away and fold back onto the origin,
        // so the first round produces no new representative.
        let anchor = ZZ4::zero();
        let rounds =
            reachable_points::<ZZ4, _, _>(1, 1, |p| point_mod_rect(p, &anchor, (1, 1)), |_, _| {});
        assert_eq!(rounds[1].len(), 0);
    }

    #[test]
    fn on_round_reports_each_round_count() {
        let mut counts = Vec::new();
        let rounds = reachable_points::<ZZ4, _, _>(2, 1, |p| *p, |_, c| counts.push(c));
        assert_eq!(counts, vec![rounds[1].len(), rounds[2].len()]);
    }
}