bonsai/backends/
mod.rs

1//! Spatial backend trait and implementations.
2//!
3//! All four spatial index backends implement the [`SpatialBackend`] trait,
4//! which provides a uniform interface for insert, remove, range query, kNN
5//! query, spatial join, and bulk loading.
6
7use crate::types::{BBox, BackendKind, CoordType, EntryId, Point};
8
9pub mod grid;
10pub mod kdtree;
11pub mod quadtree;
12pub mod rtree;
13
14pub use grid::GridIndex;
15pub use kdtree::KDTree;
16pub use quadtree::Quadtree;
17pub use rtree::RTree;
18
19/// Uniform interface implemented by all spatial index backends.
20///
21/// # Type Parameters
22/// - `T`: payload type stored alongside each point
23/// - `C`: coordinate scalar type (must implement [`CoordType`])
24/// - `D`: number of spatial dimensions (const generic)
25pub trait SpatialBackend<T, C, const D: usize>: Send + Sync
26where
27    C: CoordType,
28{
29    /// Insert a point with an associated payload. Returns the unique [`EntryId`]
30    /// assigned to this entry.
31    fn insert(&mut self, point: Point<C, D>, payload: T) -> EntryId;
32
33    /// Remove the entry with the given [`EntryId`]. Returns the payload if the
34    /// entry existed, or `None` otherwise.
35    fn remove(&mut self, id: EntryId) -> Option<T>;
36
37    /// Return all entries whose positions are contained within `bbox`.
38    fn range_query(&self, bbox: &BBox<C, D>) -> Vec<(EntryId, &T)>;
39
40    /// Return the `k` nearest entries to `point`, ordered by ascending
41    /// Euclidean distance. Each result is `(distance, id, payload_ref)`.
42    fn knn_query(&self, point: &Point<C, D>, k: usize) -> Vec<(f64, EntryId, &T)>;
43
44    /// Return all pairs `(id_a, id_b)` where the bounding box of entry `id_a`
45    /// in `self` intersects the bounding box of entry `id_b` in `other`.
46    ///
47    /// For point-only backends the "bounding box" of a point is the degenerate
48    /// box `[p, p]`.
49    fn spatial_join(&self, other: &dyn SpatialBackend<T, C, D>) -> Vec<(EntryId, EntryId)>;
50
51    /// Bulk-load a set of `(point, payload)` pairs into a new backend instance.
52    ///
53    /// Implementations may sort entries (e.g. by Hilbert index) for better
54    /// spatial locality.
55    fn bulk_load(entries: Vec<(Point<C, D>, T)>) -> Self
56    where
57        Self: Sized;
58
59    /// Return the number of entries currently stored.
60    fn len(&self) -> usize;
61
62    /// Return `true` if the backend contains no entries.
63    fn is_empty(&self) -> bool {
64        self.len() == 0
65    }
66
67    /// Return the [`BackendKind`] discriminant for this backend.
68    fn kind(&self) -> BackendKind;
69
70    /// Return all `(point, id, payload)` triples — used by `spatial_join`
71    /// implementations that need to iterate over the other backend's entries.
72    fn all_entries(&self) -> Vec<(Point<C, D>, EntryId, &T)>;
73}
bonsai/backends/mod.rs

bonsai/backends/
mod.rs
