geometry_rtree/
node.rs

1//! Tree nodes: leaves hold values, branches hold child subtrees.
2//!
3//! Mirrors `index/detail/rtree/node/variant.hpp`. Boost dispatches over
4//! its node variant with a runtime visitor; the port uses a plain enum
5//! and lets `match` be the visitor — the same shape, no vtable.
6
7use alloc::boxed::Box;
8use alloc::vec::Vec;
9
10use crate::bounds::{Bounds, union_all};
11use crate::indexable::Indexable;
12
13/// One node of the tree.
14///
15/// A [`Node::Leaf`] stores the indexed values directly; a
16/// [`Node::Branch`] stores `(child_bounds, child_node)` pairs. Mirrors
17/// the leaf / internal split of Boost's rtree node variant.
18#[derive(Debug)]
19pub enum Node<T> {
20    /// Values at the bottom of the tree.
21    Leaf(Vec<T>),
22    /// Child subtrees, each paired with its bounding box.
23    Branch(Vec<(Bounds, Box<Node<T>>)>),
24}
25
26impl<T: Indexable> Node<T> {
27    /// The bounding box covering everything in this node, or `None` for
28    /// an empty node.
29    #[must_use]
30    pub fn bounds(&self) -> Option<Bounds> {
31        match self {
32            Node::Leaf(values) => {
33                if values.is_empty() {
34                    None
35                } else {
36                    let boxes: Vec<Bounds> = values.iter().map(Indexable::bounds).collect();
37                    Some(union_all(&boxes))
38                }
39            }
40            Node::Branch(children) => {
41                if children.is_empty() {
42                    None
43                } else {
44                    let boxes: Vec<Bounds> = children.iter().map(|(b, _)| *b).collect();
45                    Some(union_all(&boxes))
46                }
47            }
48        }
49    }
50
51    /// Number of immediate entries (values in a leaf, children in a
52    /// branch).
53    #[must_use]
54    pub fn entry_count(&self) -> usize {
55        match self {
56            Node::Leaf(values) => values.len(),
57            Node::Branch(children) => children.len(),
58        }
59    }
60
61    /// Total number of leaf values in this subtree.
62    #[must_use]
63    pub fn value_count(&self) -> usize {
64        match self {
65            Node::Leaf(values) => values.len(),
66            Node::Branch(children) => children.iter().map(|(_, c)| c.value_count()).sum(),
67        }
68    }
69
70    /// Height of this subtree: a leaf is height 1.
71    #[must_use]
72    pub fn height(&self) -> usize {
73        match self {
74            Node::Leaf(_) => 1,
75            Node::Branch(children) => {
76                1 + children.iter().map(|(_, c)| c.height()).max().unwrap_or(0)
77            }
78        }
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::Node;
85    use crate::bounds::Bounds;
86    use alloc::boxed::Box;
87
88    #[test]
89    fn leaf_bounds_union_of_values() {
90        let leaf: Node<Bounds> = Node::Leaf(alloc::vec![
91            Bounds::point([0.0, 0.0]),
92            Bounds::point([2.0, 3.0]),
93        ]);
94        assert_eq!(leaf.bounds(), Some(Bounds::new([0.0, 0.0], [2.0, 3.0])));
95        assert_eq!(leaf.entry_count(), 2);
96        assert_eq!(leaf.height(), 1);
97    }
98
99    #[test]
100    fn branch_bounds_and_height() {
101        let leaf_a: Node<Bounds> = Node::Leaf(alloc::vec![Bounds::point([0.0, 0.0])]);
102        let leaf_b: Node<Bounds> = Node::Leaf(alloc::vec![Bounds::point([5.0, 5.0])]);
103        let branch: Node<Bounds> = Node::Branch(alloc::vec![
104            (leaf_a.bounds().unwrap(), Box::new(leaf_a)),
105            (leaf_b.bounds().unwrap(), Box::new(leaf_b)),
106        ]);
107        assert_eq!(branch.bounds(), Some(Bounds::new([0.0, 0.0], [5.0, 5.0])));
108        assert_eq!(branch.height(), 2);
109        assert_eq!(branch.value_count(), 2);
110    }
111
112    #[test]
113    fn empty_leaf_has_no_bounds() {
114        let leaf: Node<Bounds> = Node::Leaf(alloc::vec![]);
115        assert_eq!(leaf.bounds(), None);
116    }
117}
geometry_rtree/node.rs

geometry_rtree/
node.rs
