nodedb_array/segment/mbr_index/
node.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! R-tree node + bounding box.
4//!
5//! BBox stores per-dim min/max as [`DomainBound`] so it can carry the
6//! mixed-type coordinates produced by [`crate::tile::mbr`]. The tree
7//! is built once from segment-footer entries and is read-only;
8//! split/merge operations would land here if/when we need a writeable
9//! variant.
10
11use crate::types::domain::DomainBound;
12
13/// Per-dim bounding box. `min`/`max` are parallel to schema dims.
14#[derive(Debug, Clone, PartialEq)]
15pub struct BBox {
16    pub min: Vec<DomainBound>,
17    pub max: Vec<DomainBound>,
18}
19
20impl BBox {
21    pub fn from_mbr(mbr: &crate::tile::mbr::TileMBR) -> Self {
22        Self {
23            min: mbr.dim_mins.clone(),
24            max: mbr.dim_maxs.clone(),
25        }
26    }
27
28    pub fn arity(&self) -> usize {
29        self.min.len()
30    }
31
32    /// Union `self` with `other` in-place. Empty boxes (arity 0) are
33    /// ignored — callers seed leaves with concrete MBRs.
34    pub fn extend(&mut self, other: &BBox) {
35        if self.arity() == 0 {
36            *self = other.clone();
37            return;
38        }
39        for i in 0..self.arity().min(other.arity()) {
40            if super::predicate::lt_bound(&other.min[i], &self.min[i]) {
41                self.min[i] = other.min[i].clone();
42            }
43            if super::predicate::lt_bound(&self.max[i], &other.max[i]) {
44                self.max[i] = other.max[i].clone();
45            }
46        }
47    }
48}
49
50/// One node in the Hilbert-packed R-tree.
51///
52/// Leaves carry an index into the segment's `TileEntry` table; internal
53/// nodes carry indices into the tree's own `nodes` arena.
54#[derive(Debug, Clone)]
55pub struct RNode {
56    pub bbox: BBox,
57    pub kind: RNodeKind,
58}
59
60#[derive(Debug, Clone)]
61pub enum RNodeKind {
62    /// Each entry is `(tile_index_into_segment_footer, per_tile_bbox)`.
63    /// The per-tile bbox is required so the leaf can filter individual
64    /// tiles whose group bbox spans the predicate but whose own MBR
65    /// doesn't overlap.
66    Leaf {
67        tiles: Vec<(usize, BBox)>,
68    },
69    Internal {
70        children: Vec<usize>,
71    },
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn bbox_extend_grows_bounds() {
80        let mut a = BBox {
81            min: vec![DomainBound::Int64(0)],
82            max: vec![DomainBound::Int64(10)],
83        };
84        let b = BBox {
85            min: vec![DomainBound::Int64(-5)],
86            max: vec![DomainBound::Int64(20)],
87        };
88        a.extend(&b);
89        assert_eq!(a.min[0], DomainBound::Int64(-5));
90        assert_eq!(a.max[0], DomainBound::Int64(20));
91    }
92
93    #[test]
94    fn bbox_extend_from_empty_takes_other() {
95        let mut a = BBox {
96            min: vec![],
97            max: vec![],
98        };
99        let b = BBox {
100            min: vec![DomainBound::Int64(0)],
101            max: vec![DomainBound::Int64(1)],
102        };
103        a.extend(&b);
104        assert_eq!(a, b);
105    }
106}
nodedb_array/segment/mbr_index/node.rs

nodedb_array/segment/mbr_index/
node.rs
