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
use crate::geometry::FPCoordinate;
/// Provides a total order on fixed-point coordinates that corresponds to the
/// well-known Z-order space-filling curve.
///
/// This implementation ensures a proper total ordering by:
/// 1. First comparing the most significant differing bits
/// 2. Using consistent tie-breaking when bits are equal
/// 3. Properly handling all edge cases
///
/// # Arguments
/// * `lhs` - First coordinate to compare
/// * `rhs` - Second coordinate to compare
///
/// # Returns
/// A total ordering between the coordinates based on their Z-order:
/// * `Ordering::Less` - if `lhs` comes before `rhs`
/// * `Ordering::Equal` - if coordinates are identical
/// * `Ordering::Greater` - if `lhs` comes after `rhs`
///
/// # Examples
/// ```rust
/// use std::cmp::Ordering;
/// use toolbox_rs::geometry::FPCoordinate;
/// use toolbox_rs::space_filling_curve::zorder_cmp;
///
/// // Create some test coordinates
/// let berlin = FPCoordinate::new_from_lat_lon(52.520008, 13.404954);
/// let paris = FPCoordinate::new_from_lat_lon(48.856613, 2.352222);
/// let london = FPCoordinate::new_from_lat_lon(51.507351, -0.127758);
///
/// // Test total ordering properties
///
/// // 1. Antisymmetry: if a ≤ b and b ≤ a then a = b
/// assert_eq!(zorder_cmp(&berlin, &berlin), Ordering::Equal);
///
/// // 2. Transitivity: if a ≤ b and b ≤ c then a ≤ c
/// if zorder_cmp(&paris, &london) == Ordering::Less
/// && zorder_cmp(&london, &berlin) == Ordering::Less {
/// assert_eq!(zorder_cmp(&paris, &berlin), Ordering::Less);
/// }
///
/// // 3. Totality: either a ≤ b or b ≤ a must be true
/// let order = zorder_cmp(&paris, &london);
/// assert!(order == Ordering::Less || order == Ordering::Equal || order == Ordering::Greater);
/// ```
pub fn zorder_cmp(lhs: &FPCoordinate, rhs: &FPCoordinate) -> std::cmp::Ordering {
let lat_xor = lhs.lat ^ rhs.lat;
let lon_xor = lhs.lon ^ rhs.lon;
// If both coordinates are identical
if lat_xor == 0 && lon_xor == 0 {
return std::cmp::Ordering::Equal;
}
// If one dimension has no differences
if lat_xor == 0 {
return lhs.lon.cmp(&rhs.lon);
}
if lon_xor == 0 {
return lhs.lat.cmp(&rhs.lat);
}
// Compare most significant bits
let lat_msb = 31 - lat_xor.leading_zeros();
let lon_msb = 31 - lon_xor.leading_zeros();
match lat_msb.cmp(&lon_msb) {
std::cmp::Ordering::Greater => lhs.lat.cmp(&rhs.lat),
std::cmp::Ordering::Less => lhs.lon.cmp(&rhs.lon),
std::cmp::Ordering::Equal => {
// If MSBs are at same position, use consistent ordering
if (lhs.lat >> lat_msb) & 1 != (rhs.lat >> lat_msb) & 1 {
lhs.lat.cmp(&rhs.lat)
} else {
lhs.lon.cmp(&rhs.lon)
}
}
}
}
#[cfg(test)]
mod tests {
use crate::{geometry::FPCoordinate, space_filling_curve::zorder_cmp};
#[test]
fn compare_greater() {
let ny = FPCoordinate::new_from_lat_lon(40.730610, -73.935242);
let sf = FPCoordinate::new_from_lat_lon(37.773972, -122.431297);
assert_eq!(std::cmp::Ordering::Greater, zorder_cmp(&ny, &sf));
}
#[test]
fn compare_less() {
let ny = FPCoordinate::new_from_lat_lon(40.730610, -73.935242);
let sf = FPCoordinate::new_from_lat_lon(37.773972, -122.431297);
assert_eq!(std::cmp::Ordering::Less, zorder_cmp(&sf, &ny));
}
#[test]
fn compare_equal() {
let ny = FPCoordinate::new_from_lat_lon(40.730610, -73.935242);
assert_eq!(std::cmp::Ordering::Equal, zorder_cmp(&ny, &ny));
}
}