stac_hash/
lib.rs

1//! Configurable, sortable spatio-temporal hashes, good for
2//! [STAC](https://stacspec.org/)
3//! [items](https://github.com/radiantearth/stac-spec/blob/master/item-spec/item-spec.md).
4//!
5//! # Examples
6//!
7//! ```
8//! use stac_hash::Hasher;
9//! use chrono::{Utc, TimeZone};
10//!
11//! let start_datetime = Utc.with_ymd_and_hms(2026, 1, 1, 0, 0, 0).unwrap();
12//! let end_datetime = Utc.with_ymd_and_hms(2027, 1, 1, 0, 0, 0).unwrap();
13//! let hasher = Hasher::global(start_datetime, end_datetime).unwrap();
14//! let hash = hasher.hash(start_datetime, (-105., 40.)).unwrap();
15//!
16//! // Later datetimes sort after earlier ones
17//! let hash_later = hasher.hash(end_datetime, (-105., 40.)).unwrap();
18//! assert!(hash < hash_later);
19//!
20//! // Latitudes and longitudes sort as well
21//! let hash_right = hasher.hash(start_datetime, (-104., 40.)).unwrap();
22//! assert!(hash < hash_right);
23//! let hash_above = hasher.hash(start_datetime, (-105., 41.)).unwrap();
24//! assert!(hash < hash_above);
25//! ```
26
27use chrono::{DateTime, Utc};
28use thiserror::Error;
29
30const BITS_PER_DIMENSION: u8 = 21; // 63 / 3
31const MAX_VALUE: f64 = ((1u64 << BITS_PER_DIMENSION) - 1) as f64;
32
33/// Crate-specific result type.
34pub type Result<T> = std::result::Result<T, Error>;
35
36/// A structure for creating sortable spatio-temporal hashes with millisecond temporal precision.
37// TODO Configurable datetime precision
38// TODO Configurable output type (currently hardcoded to u64)
39// TODO Configurable primary sort order (currently hardcoded to datetime)
40#[derive(Debug)]
41pub struct Hasher {
42    start_datetime: DateTime<Utc>,
43    end_datetime: DateTime<Utc>,
44    datetime_range_millis: f64,
45    min_longitude: f64,
46    max_longitude: f64,
47    longitude_range: f64,
48    min_latitude: f64,
49    max_latitude: f64,
50    latitude_range: f64,
51}
52
53/// A simple WGS84 point structure.
54#[derive(Debug, Clone, Copy)]
55pub struct Point {
56    pub longitude: f64,
57    pub latitude: f64,
58}
59
60/// Errors returned when a value falls outside of a [Hasher]'s extent.
61#[derive(Debug, Error)]
62pub enum Error {
63    /// The datetime is outside of the hasher's temporal extent.
64    #[error("datetime outside of the hasher's temporal extent: {0}")]
65    InvalidDatetime(DateTime<Utc>),
66
67    /// The latitude is outside of the hasher's spatial extent.
68    #[error("latitude outside of the hasher's spatial extent: {0}")]
69    InvalidLatitude(f64),
70
71    /// The longitude is outside of the hasher's spatial extent.
72    #[error("longitude outside of the hasher's spatial extent: {0}")]
73    InvalidLongitude(f64),
74}
75
76impl Hasher {
77    /// Creates a new hasher for the given datetime and the global extents.
78    ///
79    /// # Examples
80    ///
81    /// ```
82    /// use stac_hash::Hasher;
83    /// use chrono::{Utc, TimeZone};
84    ///
85    /// let start_datetime = Utc.with_ymd_and_hms(2026, 1, 1, 0, 0, 0).unwrap();
86    /// let end_datetime = Utc.with_ymd_and_hms(2027, 1, 1, 0, 0, 0).unwrap();
87    /// let hasher = Hasher::global(start_datetime, end_datetime).unwrap();
88    /// ```
89    pub fn global(start_datetime: DateTime<Utc>, end_datetime: DateTime<Utc>) -> Result<Self> {
90        Self::new(start_datetime, end_datetime, (-180., -90.), (180., 90.))
91    }
92
93    /// Creates a new hasher for the given datetime and spatial intervals.
94    ///
95    /// # Examples
96    ///
97    /// ```
98    /// use stac_hash::Hasher;
99    /// use chrono::{Utc, TimeZone};
100    ///
101    /// // CONUS (roughly)
102    /// let start_datetime = Utc.with_ymd_and_hms(2026, 1, 1, 0, 0, 0).unwrap();
103    /// let end_datetime = Utc.with_ymd_and_hms(2027, 1, 1, 0, 0, 0).unwrap();
104    /// let hasher = Hasher::new(start_datetime, end_datetime, (-125., 25.), (-66., 50.)).unwrap();
105    /// ```
106    pub fn new(
107        start_datetime: DateTime<Utc>,
108        end_datetime: DateTime<Utc>,
109        min: impl Into<Point>,
110        max: impl Into<Point>,
111    ) -> Result<Self> {
112        let min = min.into();
113        let max = max.into();
114        let datetime_range_millis = (end_datetime - start_datetime).num_milliseconds();
115        let longitude_range = max.longitude - min.longitude;
116        let latitude_range = max.latitude - min.latitude;
117        Ok(Self {
118            start_datetime,
119            end_datetime,
120            datetime_range_millis: datetime_range_millis as f64,
121            min_longitude: min.longitude,
122            max_longitude: max.longitude,
123            longitude_range,
124            min_latitude: min.latitude,
125            max_latitude: max.latitude,
126            latitude_range,
127        })
128    }
129
130    /// Converts a datetime and a Point into a hash.
131    ///
132    /// Returns an error if the datetime or the point falls outside of this
133    /// hasher's extent. Use [Hasher::hash_clamped] to clamp onto the boundary
134    /// instead of erroring.
135    ///
136    /// # Examples
137    ///
138    /// ```
139    /// use stac_hash::Hasher;
140    /// use chrono::{Utc, TimeZone};
141    ///
142    /// let start = Utc.with_ymd_and_hms(2023, 1, 1, 0, 0, 0).unwrap();
143    /// let end = Utc.with_ymd_and_hms(2024, 1, 1, 0, 0, 0).unwrap();
144    /// let hasher = Hasher::global(start, end).unwrap();
145    /// let hash = hasher.hash(start, (0., 0.)).unwrap();
146    /// ```
147    pub fn hash(&self, datetime: DateTime<Utc>, point: impl Into<Point>) -> Result<u64> {
148        let point = point.into();
149        if datetime < self.start_datetime || datetime > self.end_datetime {
150            return Err(Error::InvalidDatetime(datetime));
151        }
152        if point.latitude < self.min_latitude || point.latitude > self.max_latitude {
153            return Err(Error::InvalidLatitude(point.latitude));
154        }
155        if point.longitude < self.min_longitude || point.longitude > self.max_longitude {
156            return Err(Error::InvalidLongitude(point.longitude));
157        }
158        Ok(self.interleave(datetime, point))
159    }
160
161    /// Converts a datetime and a Point into a hash, clamping anything outside
162    /// of this hasher's extent onto its boundary.
163    ///
164    /// This cannot fail. A datetime before `start_datetime` hashes as
165    /// `start_datetime`, a longitude west of the minimum hashes as that
166    /// minimum, and so on. Each clamped value is logged at warn level. Use
167    /// [Hasher::hash] to get an error instead.
168    ///
169    /// # Examples
170    ///
171    /// ```
172    /// use stac_hash::Hasher;
173    /// use chrono::{Utc, TimeZone};
174    ///
175    /// let start = Utc.with_ymd_and_hms(2026, 1, 1, 0, 0, 0).unwrap();
176    /// let end = Utc.with_ymd_and_hms(2027, 1, 1, 0, 0, 0).unwrap();
177    /// let hasher = Hasher::new(start, end, (-109., 37.), (-102., 41.)).unwrap();
178    ///
179    /// // Well west of the bounding box, so it hashes as if it were on the edge.
180    /// let hash = hasher.hash_clamped(start, (-120., 40.));
181    /// assert_eq!(hash, hasher.hash(start, (-109., 40.)).unwrap());
182    /// ```
183    pub fn hash_clamped(&self, datetime: DateTime<Utc>, point: impl Into<Point>) -> u64 {
184        let point = point.into();
185        if datetime < self.start_datetime || datetime > self.end_datetime {
186            log::warn!("datetime outside of the hasher's temporal extent: {datetime}");
187        }
188        if point.latitude < self.min_latitude || point.latitude > self.max_latitude {
189            log::warn!(
190                "latitude outside of the hasher's spatial extent: {}",
191                point.latitude
192            );
193        }
194        if point.longitude < self.min_longitude || point.longitude > self.max_longitude {
195            log::warn!(
196                "longitude outside of the hasher's spatial extent: {}",
197                point.longitude
198            );
199        }
200        self.interleave(datetime, point)
201    }
202
203    fn interleave(&self, datetime: DateTime<Utc>, point: Point) -> u64 {
204        let datetime_normalized = (((datetime.timestamp_millis()
205            - self.start_datetime.timestamp_millis()) as f64)
206            / self.datetime_range_millis)
207            .clamp(0., 1.);
208        let latitude_normalized =
209            ((point.latitude - self.min_latitude) / self.latitude_range).clamp(0., 1.);
210        let longitude_normalized =
211            ((point.longitude - self.min_longitude) / self.longitude_range).clamp(0., 1.);
212
213        let datetime_quantized = (datetime_normalized * MAX_VALUE) as u64;
214        let latitude_quantized = (latitude_normalized * MAX_VALUE) as u64;
215        let longitude_quantized = (longitude_normalized * MAX_VALUE) as u64;
216
217        let mut hash = 0u64;
218        for i in 0..BITS_PER_DIMENSION {
219            let src = i as u64;
220            let dst = (i as u64) * 3;
221            hash |= ((longitude_quantized >> src) & 1) << dst;
222            hash |= ((latitude_quantized >> src) & 1) << (dst + 1);
223            hash |= ((datetime_quantized >> src) & 1) << (dst + 2);
224        }
225        hash
226    }
227}
228
229impl From<(f64, f64)> for Point {
230    fn from((longitude, latitude): (f64, f64)) -> Self {
231        Self {
232            longitude,
233            latitude,
234        }
235    }
236}
237
238#[cfg(test)]
239mod tests {
240    use crate::Point;
241
242    use super::Hasher;
243    use chrono::{DateTime, TimeZone, Utc};
244    use rstest::{fixture, rstest};
245
246    #[fixture]
247    fn start_datetime() -> DateTime<Utc> {
248        Utc.with_ymd_and_hms(2026, 1, 1, 0, 0, 0).unwrap()
249    }
250
251    #[fixture]
252    fn end_datetime() -> DateTime<Utc> {
253        Utc.with_ymd_and_hms(2027, 1, 1, 0, 0, 0).unwrap()
254    }
255
256    #[fixture]
257    fn longmont() -> Point {
258        Point {
259            longitude: -105.,
260            latitude: 40.,
261        }
262    }
263
264    #[fixture]
265    fn hasher(start_datetime: DateTime<Utc>, end_datetime: DateTime<Utc>) -> Hasher {
266        Hasher::global(start_datetime, end_datetime).unwrap()
267    }
268
269    #[rstest]
270    fn one_year_global(hasher: Hasher, longmont: Point) {
271        let hash = hasher
272            .hash(
273                Utc.with_ymd_and_hms(2026, 6, 14, 12, 0, 0).unwrap(),
274                longmont,
275            )
276            .unwrap();
277        assert_eq!(hash, 3024785829217804842);
278    }
279
280    #[fixture]
281    fn colorado(start_datetime: DateTime<Utc>, end_datetime: DateTime<Utc>) -> Hasher {
282        Hasher::new(start_datetime, end_datetime, (-109., 37.), (-102., 41.)).unwrap()
283    }
284
285    #[rstest]
286    fn hash_clamped_matches_hash_inside_the_extent(
287        colorado: Hasher,
288        start_datetime: DateTime<Utc>,
289        longmont: Point,
290    ) {
291        assert_eq!(
292            colorado.hash_clamped(start_datetime, longmont),
293            colorado.hash(start_datetime, longmont).unwrap()
294        );
295    }
296
297    #[rstest]
298    fn hash_clamped_clamps_longitude(colorado: Hasher, start_datetime: DateTime<Utc>) {
299        assert_eq!(
300            colorado.hash_clamped(start_datetime, (-120., 40.)),
301            colorado.hash(start_datetime, (-109., 40.)).unwrap()
302        );
303    }
304
305    #[rstest]
306    fn hash_clamped_clamps_latitude(colorado: Hasher, start_datetime: DateTime<Utc>) {
307        assert_eq!(
308            colorado.hash_clamped(start_datetime, (-105., 90.)),
309            colorado.hash(start_datetime, (-105., 41.)).unwrap()
310        );
311    }
312
313    #[rstest]
314    fn hash_clamped_clamps_datetime(
315        colorado: Hasher,
316        end_datetime: DateTime<Utc>,
317        longmont: Point,
318    ) {
319        let beyond = end_datetime + chrono::Duration::days(365);
320        assert_eq!(
321            colorado.hash_clamped(beyond, longmont),
322            colorado.hash(end_datetime, longmont).unwrap()
323        );
324    }
325
326    #[rstest]
327    fn hash_still_errors_outside_the_extent(colorado: Hasher, start_datetime: DateTime<Utc>) {
328        assert!(colorado.hash(start_datetime, (-120., 40.)).is_err());
329        assert!(colorado.hash(start_datetime, (-105., 90.)).is_err());
330        assert!(
331            colorado
332                .hash(start_datetime - chrono::Duration::days(1), (-105., 40.))
333                .is_err()
334        );
335    }
336
337    #[rstest]
338    fn nearby_points_have_close_hashes(hasher: Hasher, start_datetime: DateTime<Utc>) {
339        let hash = hasher.hash(start_datetime, (-105., 40.)).unwrap();
340        let hash_near = hasher.hash(start_datetime, (-105.1, 40.1)).unwrap();
341        let hash_far = hasher.hash(start_datetime, (-106., 41.)).unwrap();
342        assert!(hash.abs_diff(hash_near) < hash.abs_diff(hash_far));
343    }
344
345    #[rstest]
346    fn sort_datetime(hasher: Hasher, start_datetime: DateTime<Utc>, longmont: Point) {
347        let hash_a = hasher.hash(start_datetime, longmont).unwrap();
348        let hash_b = hasher
349            .hash(start_datetime + chrono::Duration::days(1), longmont)
350            .unwrap();
351        assert!(hash_a < hash_b);
352    }
353
354    #[rstest]
355    fn sort_latitude(hasher: Hasher, start_datetime: DateTime<Utc>, longmont: Point) {
356        let hash_a = hasher.hash(start_datetime, longmont).unwrap();
357        let hash_b = hasher
358            .hash(
359                start_datetime,
360                Point {
361                    latitude: 41.,
362                    longitude: -105.,
363                },
364            )
365            .unwrap();
366        assert!(hash_a < hash_b);
367    }
368
369    #[rstest]
370    fn sort_longitude(hasher: Hasher, start_datetime: DateTime<Utc>, longmont: Point) {
371        let hash_a = hasher.hash(start_datetime, longmont).unwrap();
372        let hash_b = hasher
373            .hash(
374                start_datetime,
375                Point {
376                    latitude: 40.,
377                    longitude: -104.,
378                },
379            )
380            .unwrap();
381        assert!(hash_a < hash_b);
382    }
383}
stac_hash/lib.rs

stac_hash/
lib.rs
