space_time/zorder/
z_n.rs

1//
2// Copyright 2020, Gobsmacked Labs, LLC.
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//     http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16//! An N-Dimensional Z-Order Curve base class.
17
18use crate::{
19    index_range::{CoveredRange, IndexRange, OverlappingRange},
20    zorder::z_range::ZRange,
21};
22use alloc::{boxed::Box, collections::VecDeque, vec, vec::Vec};
23
24const DEFAULT_RECURSE: usize = 7;
25
26const LEVEL_TERMINATOR: (Option<u64>, Option<u64>) = (None, None);
27
28/// An N-Dimensional Z-Order Curve base class.
29pub trait ZN {
30    /// Number of Bits per Dimension.
31    const BITS_PER_DIMENSION: u32;
32
33    /// Number of Dimensions.
34    const DIMENSIONS: u64;
35
36    /// MAX Value of this Z-order.
37    const MAX_MASK: u64;
38
39    /// Total bits used. Usually bits_per_dim * dim.
40    const TOTAL_BITS: u64;
41
42    /// Number of quadrants in the quad/oct tree.
43    const QUADRANTS: u32 = 2_u32.pow(Self::DIMENSIONS as u32);
44
45    /// Insert (DIMENSIONS - 1) zeros between each bit to create a zvalue
46    ///  from a single dimension.
47    ///
48    /// #Note:
49    ///   - Only the first `BITS_PER_DIMENSION` can be considered.
50    fn split(value: u32) -> u64;
51
52    /// Combine every (Dimensions - 1) bits to re-create a single dimension. Opposite
53    /// of split.
54    fn combine(z: u64) -> u32;
55
56    /// Tests whether range contains the value. Considers User space.
57    fn contains(range: ZRange, value: u64) -> bool;
58
59    /// Test whether range contains the value. Considers User space.
60    #[must_use]
61    fn contains_value(range: ZRange, value: ZRange) -> bool {
62        Self::contains(range, value.min) && Self::contains(range, value.max)
63    }
64
65    /// Test whether range and value overlap. Considers User space.
66    ///
67    /// # Precondition
68    ///
69    /// Both `range` and `value` must be proper bounding boxes whose `min` and
70    /// `max` decode to user-space corners that are ordered in every dimension
71    /// (i.e. `min`'s coordinate is `<=` `max`'s coordinate per axis). The
72    /// Z-curve is not monotonic per dimension, so a `ZRange` with `min <= max`
73    /// as raw indices does not guarantee this; passing an unordered box can make
74    /// `overlaps` report no overlap when the boxes actually intersect. The range
75    /// constructors on the curve types (e.g. `Z2Curve::ranges`) always build
76    /// ordered boxes, so callers using those are safe.
77    #[must_use]
78    fn overlaps(range: ZRange, value: ZRange) -> bool;
79
80    /// Compute the Z-index ranges that cover zbounds (Default values: precision = 64,
81    /// `max_recurse` = 7, `max_ranges` = `usize::MAX`).
82    #[must_use]
83    fn zranges_default<Z: ZN>(zbounds: &[ZRange]) -> Vec<Box<dyn IndexRange>> {
84        Self::zranges::<Z>(zbounds, 64, Some(usize::MAX), Some(DEFAULT_RECURSE))
85    }
86
87    /// Compute the Z-index ranges that cover zbounds.
88    #[must_use]
89    fn zranges<Z: ZN>(
90        zbounds: &[ZRange],
91        precision: u64,
92        max_ranges: Option<usize>,
93        max_recurse: Option<usize>,
94    ) -> Vec<Box<dyn IndexRange>> {
95        let mut ranges: Vec<Box<dyn IndexRange>> = Vec::with_capacity(100);
96
97        let mut remaining: VecDeque<(Option<u64>, Option<u64>)> = VecDeque::with_capacity(100);
98
99        let lcp = Self::longest_common_prefix(
100            zbounds
101                .iter()
102                .flat_map(|b| vec![b.min, b.max])
103                .collect::<Vec<u64>>()
104                .as_slice(),
105        );
106
107        let mut offset = 64 - lcp.precision;
108
109        check_value::<Z>(
110            lcp.prefix,
111            0,
112            offset,
113            zbounds,
114            precision,
115            &mut ranges,
116            &mut remaining,
117        );
118        remaining.push_back(LEVEL_TERMINATOR);
119        offset -= Self::DIMENSIONS;
120
121        let mut level = 0;
122
123        let max_recurse = max_recurse.unwrap_or(DEFAULT_RECURSE);
124        let max_ranges = max_ranges.unwrap_or(usize::MAX);
125
126        loop {
127            let next = remaining.pop_front();
128
129            match next {
130                Some(LEVEL_TERMINATOR) if !remaining.is_empty() => {
131                    level += 1;
132
133                    if offset == 0 || level >= max_recurse {
134                        bottom_out(&mut ranges, &mut remaining);
135                    } else {
136                        remaining.push_back(LEVEL_TERMINATOR);
137                    }
138                    offset -= Self::DIMENSIONS;
139                }
140                Some((Some(min), _)) => {
141                    let prefix = min;
142                    let mut quadrant = 0_u64;
143                    while quadrant < Self::QUADRANTS.into() {
144                        check_value::<Z>(
145                            prefix,
146                            quadrant,
147                            offset,
148                            zbounds,
149                            precision,
150                            &mut ranges,
151                            &mut remaining,
152                        );
153                        quadrant += 1;
154                    }
155                    if ranges.len() + remaining.len() > max_ranges {
156                        bottom_out(&mut ranges, &mut remaining);
157                    }
158                }
159                _ => (),
160            }
161
162            if remaining.is_empty() {
163                break;
164            }
165        }
166
167        // All ranges found. Now reduce them by merging overlapping values.
168        ranges.sort();
169
170        let mut current: Option<Box<dyn IndexRange>> = None;
171        let mut results = Vec::new();
172
173        for range in ranges {
174            match current.take() {
175                Some(cur) => {
176                    if range.lower() <= cur.upper().saturating_add(1) {
177                        let max = cur.upper().max(range.upper());
178                        let min = cur.lower();
179                        if cur.contained() && range.contained() {
180                            current = Some(Box::new(CoveredRange::new(min, max)));
181                        } else {
182                            current = Some(Box::new(OverlappingRange::new(min, max)));
183                        }
184                    } else {
185                        results.push(cur);
186                        current = Some(range);
187                    }
188                }
189                _ => {
190                    current = Some(range);
191                }
192            }
193        }
194        if let Some(cur) = current {
195            results.push(cur);
196        }
197        results
198    }
199
200    /// Compute the longest common binary prefix for a slice of i64s.
201    ///
202    /// # NOTE:
203    ///   panics if `values.len() == 0`
204    #[must_use]
205    fn longest_common_prefix(values: &[u64]) -> ZPrefix {
206        assert!(!values.is_empty());
207
208        let mut bit_shift = Self::TOTAL_BITS - Self::DIMENSIONS;
209        let mut head = values[0].wrapping_shr(bit_shift as u32);
210
211        while values[1..]
212            .iter()
213            .all(|v| v.wrapping_shr(bit_shift as u32) == head)
214        {
215            bit_shift -= Self::DIMENSIONS;
216            head = values[0].wrapping_shr(bit_shift as u32);
217            if bit_shift == 0 {
218                break;
219            }
220        }
221
222        bit_shift += Self::DIMENSIONS;
223        ZPrefix {
224            prefix: values[0] & (u64::MAX.wrapping_shl(bit_shift as u32)),
225            precision: 64 - bit_shift,
226        }
227    }
228}
229
230/// The longest common prefix for a group of z-indexes.
231#[derive(Debug, PartialEq)]
232pub struct ZPrefix {
233    /// The common prefix.
234    pub prefix: u64,
235    /// The number of bits in common.
236    pub precision: u64,
237}
238
239fn check_value<Z: ZN>(
240    prefix: u64,
241    quadrant: u64,
242    offset: u64,
243    zbounds: &[ZRange],
244    precision: u64,
245    ranges: &mut Vec<Box<dyn IndexRange>>,
246    remaining: &mut VecDeque<(Option<u64>, Option<u64>)>,
247) {
248    let min = prefix | quadrant.wrapping_shl(offset as u32);
249    let max = min | (1_u64.wrapping_shl(offset as u32) - 1);
250    let quadrant_range = ZRange { min, max };
251
252    if is_contained::<Z>(quadrant_range, zbounds) || offset < 64 - precision {
253        ranges.push(Box::new(CoveredRange::new(min, max)));
254    } else if is_overlapped::<Z>(quadrant_range, zbounds) {
255        remaining.push_back((Some(min), Some(max)));
256    }
257}
258
259fn bottom_out(
260    ranges: &mut Vec<Box<dyn IndexRange>>,
261    remaining: &mut VecDeque<(Option<u64>, Option<u64>)>,
262) {
263    while let Some((min, max)) = remaining.pop_front() {
264        if let (Some(min), Some(max)) = (min, max) {
265            ranges.push(Box::new(OverlappingRange::new(min, max)));
266        }
267    }
268}
269
270fn is_contained<Z: ZN>(range: ZRange, zbounds: &[ZRange]) -> bool {
271    for bound in zbounds {
272        if Z::contains_value(*bound, range) {
273            return true;
274        }
275    }
276    false
277}
278
279fn is_overlapped<Z: ZN>(range: ZRange, zbounds: &[ZRange]) -> bool {
280    for bound in zbounds {
281        if Z::overlaps(*bound, range) {
282            return true;
283        }
284    }
285    false
286}
space_time/zorder/z_n.rs

space_time/zorder/
z_n.rs
