nodedb_spatial/rtree/
node.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! R-tree node types and constants.
4
5use nodedb_types::BoundingBox;
6use serde::{Deserialize, Serialize};
7use zerompk::{FromMessagePack, ToMessagePack};
8
9pub const LEAF_CAPACITY: usize = 32;
10pub const INTERNAL_CAPACITY: usize = 16;
11pub const MIN_FILL_LEAF: usize = LEAF_CAPACITY * 2 / 5;
12pub const MIN_FILL_INTERNAL: usize = INTERNAL_CAPACITY * 2 / 5;
13pub const REINSERT_COUNT_LEAF: usize = LEAF_CAPACITY * 3 / 10;
14
15/// Unique identifier for a spatial entry (document RID or opaque u64).
16pub type EntryId = u64;
17
18/// A spatial entry stored in an R-tree leaf.
19#[derive(
20    Debug,
21    Clone,
22    Serialize,
23    Deserialize,
24    ToMessagePack,
25    FromMessagePack,
26    rkyv::Archive,
27    rkyv::Serialize,
28    rkyv::Deserialize,
29)]
30pub struct RTreeEntry {
31    pub id: EntryId,
32    pub bbox: BoundingBox,
33}
34
35/// Internal node child reference.
36#[derive(Debug, Clone)]
37pub(crate) struct ChildRef {
38    pub bbox: BoundingBox,
39    pub node_idx: usize,
40}
41
42/// A node in the R-tree (either internal or leaf).
43#[derive(Debug, Clone)]
44pub(crate) enum NodeKind {
45    Internal { children: Vec<ChildRef> },
46    Leaf { entries: Vec<RTreeEntry> },
47}
48
49#[derive(Debug, Clone)]
50pub(crate) struct Node {
51    pub kind: NodeKind,
52    pub bbox: BoundingBox,
53    pub level: u32,
54}
55
56impl Node {
57    pub fn new_leaf() -> Self {
58        Self {
59            kind: NodeKind::Leaf {
60                // no-governor: structural per-node R-tree leaf; LEAF_CAPACITY is a small fixed constant
61                entries: Vec::with_capacity(LEAF_CAPACITY),
62            },
63            bbox: BoundingBox::new(
64                f64::INFINITY,
65                f64::INFINITY,
66                f64::NEG_INFINITY,
67                f64::NEG_INFINITY,
68            ),
69            level: 0,
70        }
71    }
72
73    pub fn new_internal(level: u32) -> Self {
74        Self {
75            kind: NodeKind::Internal {
76                // no-governor: structural per-node R-tree internal; INTERNAL_CAPACITY is a small fixed constant
77                children: Vec::with_capacity(INTERNAL_CAPACITY),
78            },
79            bbox: BoundingBox::new(
80                f64::INFINITY,
81                f64::INFINITY,
82                f64::NEG_INFINITY,
83                f64::NEG_INFINITY,
84            ),
85            level,
86        }
87    }
88
89    pub fn is_leaf(&self) -> bool {
90        matches!(self.kind, NodeKind::Leaf { .. })
91    }
92
93    pub fn capacity(&self) -> usize {
94        if self.is_leaf() {
95            LEAF_CAPACITY
96        } else {
97            INTERNAL_CAPACITY
98        }
99    }
100
101    pub fn len(&self) -> usize {
102        match &self.kind {
103            NodeKind::Internal { children } => children.len(),
104            NodeKind::Leaf { entries } => entries.len(),
105        }
106    }
107
108    pub fn is_overflow(&self) -> bool {
109        self.len() > self.capacity()
110    }
111
112    pub fn min_fill(&self) -> usize {
113        if self.is_leaf() {
114            MIN_FILL_LEAF
115        } else {
116            MIN_FILL_INTERNAL
117        }
118    }
119
120    pub fn is_underflow(&self) -> bool {
121        self.len() < self.min_fill()
122    }
123
124    pub fn recompute_bbox(&mut self) {
125        match &self.kind {
126            NodeKind::Internal { children } => {
127                if children.is_empty() {
128                    self.bbox = BoundingBox::new(0.0, 0.0, 0.0, 0.0);
129                    return;
130                }
131                let mut bb = children[0].bbox;
132                for c in &children[1..] {
133                    bb = bb.union(&c.bbox);
134                }
135                self.bbox = bb;
136            }
137            NodeKind::Leaf { entries } => {
138                if entries.is_empty() {
139                    self.bbox = BoundingBox::new(0.0, 0.0, 0.0, 0.0);
140                    return;
141                }
142                let mut bb = entries[0].bbox;
143                for e in &entries[1..] {
144                    bb = bb.union(&e.bbox);
145                }
146                self.bbox = bb;
147            }
148        }
149    }
150}
nodedb_spatial/rtree/node.rs

nodedb_spatial/rtree/
node.rs
