frp_plexus/
spc.rs

1use serde::{Deserialize, Serialize};
2
3// ---------------------------------------------------------------------------
4// Morton encoding helpers
5// ---------------------------------------------------------------------------
6
7/// Spread the bits of a `u32` into alternating positions of a `u64`.
8/// Bit i of `x` goes to bit 2i of the result.
9#[inline]
10fn spread_bits(x: u32) -> u64 {
11    let mut x = x as u64;
12    x = (x | (x << 16)) & 0x0000_FFFF_0000_FFFF;
13    x = (x | (x << 8)) & 0x00FF_00FF_00FF_00FF;
14    x = (x | (x << 4)) & 0x0F0F_0F0F_0F0F_0F0F;
15    x = (x | (x << 2)) & 0x3333_3333_3333_3333;
16    x = (x | (x << 1)) & 0x5555_5555_5555_5555;
17    x
18}
19
20/// Compact alternating bits of a `u64` back into a `u32`.
21/// Inverse of `spread_bits`.
22#[inline]
23fn compact_bits(mut x: u64) -> u32 {
24    x &= 0x5555_5555_5555_5555;
25    x = (x | (x >> 1)) & 0x3333_3333_3333_3333;
26    x = (x | (x >> 2)) & 0x0F0F_0F0F_0F0F_0F0F;
27    x = (x | (x >> 4)) & 0x00FF_00FF_00FF_00FF;
28    x = (x | (x >> 8)) & 0x0000_FFFF_0000_FFFF;
29    x = (x | (x >> 16)) & 0x0000_0000_FFFF_FFFF;
30    x as u32
31}
32
33/// Interleave bits of `x` and `y` to produce a Morton (Z-order) code.
34/// Bits of `x` occupy even positions; bits of `y` occupy odd positions.
35#[inline]
36pub fn morton_encode(x: u32, y: u32) -> u64 {
37    spread_bits(x) | (spread_bits(y) << 1)
38}
39
40/// Decode a Morton code back into its `(x, y)` components.
41#[inline]
42pub fn morton_decode(key: u64) -> (u32, u32) {
43    (compact_bits(key), compact_bits(key >> 1))
44}
45
46// ---------------------------------------------------------------------------
47// SpcKey
48// ---------------------------------------------------------------------------
49
50/// A Morton-encoded 2D spatial key.
51#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
52pub struct SpcKey(u64);
53
54impl SpcKey {
55    /// Construct from a raw Morton-encoded value.
56    #[inline]
57    pub fn from_raw(raw: u64) -> Self {
58        Self(raw)
59    }
60
61    /// Encode `(x, y)` as a Morton key.
62    #[inline]
63    pub fn from_xy(x: u32, y: u32) -> Self {
64        Self(morton_encode(x, y))
65    }
66
67    /// Decode this key back to `(x, y)`.
68    #[inline]
69    pub fn to_xy(self) -> (u32, u32) {
70        morton_decode(self.0)
71    }
72
73    /// The raw `u64` Morton value.
74    #[inline]
75    pub fn raw(self) -> u64 {
76        self.0
77    }
78}
79
80impl std::fmt::Display for SpcKey {
81    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
82        let (x, y) = self.to_xy();
83        write!(f, "SpcKey({}, {})", x, y)
84    }
85}
86
87// ---------------------------------------------------------------------------
88// SpcRegion
89// ---------------------------------------------------------------------------
90
91/// An axis-aligned bounding box in 2D SPC space.
92#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
93pub struct SpcRegion {
94    pub min_x: u32,
95    pub min_y: u32,
96    pub max_x: u32,
97    pub max_y: u32,
98}
99
100impl SpcRegion {
101    /// Create a new region. Panics in debug mode if `min > max` on either axis.
102    pub fn new(min_x: u32, min_y: u32, max_x: u32, max_y: u32) -> Self {
103        debug_assert!(min_x <= max_x, "min_x must be <= max_x");
104        debug_assert!(min_y <= max_y, "min_y must be <= max_y");
105        Self { min_x, min_y, max_x, max_y }
106    }
107
108    /// Test whether a [`SpcKey`] falls within this region (inclusive on all sides).
109    pub fn contains_key(&self, key: SpcKey) -> bool {
110        let (x, y) = key.to_xy();
111        x >= self.min_x && x <= self.max_x && y >= self.min_y && y <= self.max_y
112    }
113
114    /// Return the `(min_key, max_key)` Morton-encoded corners of this region.
115    ///
116    /// **Note:** Morton ranges are not contiguous — a range scan must also
117    /// apply `contains_key` to filter keys outside the true rectangular region.
118    pub fn key_range(&self) -> (SpcKey, SpcKey) {
119        (
120            SpcKey::from_xy(self.min_x, self.min_y),
121            SpcKey::from_xy(self.max_x, self.max_y),
122        )
123    }
124}
125
126// ---------------------------------------------------------------------------
127// Tests
128// ---------------------------------------------------------------------------
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133
134    #[test]
135    fn morton_round_trip() {
136        for (x, y) in [(0, 0), (1, 0), (0, 1), (255, 255), (u32::MAX, u32::MAX)] {
137            assert_eq!(morton_decode(morton_encode(x, y)), (x, y));
138        }
139    }
140
141    #[test]
142    fn spc_key_round_trip() {
143        let key = SpcKey::from_xy(42, 99);
144        assert_eq!(key.to_xy(), (42, 99));
145    }
146
147    #[test]
148    fn spc_region_contains() {
149        let region = SpcRegion::new(0, 0, 10, 10);
150        assert!(region.contains_key(SpcKey::from_xy(5, 5)));
151        assert!(region.contains_key(SpcKey::from_xy(0, 0)));
152        assert!(region.contains_key(SpcKey::from_xy(10, 10)));
153        assert!(!region.contains_key(SpcKey::from_xy(11, 5)));
154        assert!(!region.contains_key(SpcKey::from_xy(5, 11)));
155    }
156
157    #[test]
158    fn spc_region_key_range_corners() {
159        let region = SpcRegion::new(1, 2, 3, 4);
160        let (lo, hi) = region.key_range();
161        assert_eq!(lo.to_xy(), (1, 2));
162        assert_eq!(hi.to_xy(), (3, 4));
163    }
164}
frp_plexus/spc.rs

frp_plexus/
spc.rs
