rstar/
node.rs

1use crate::envelope::Envelope;
2use crate::object::RTreeObject;
3use crate::params::RTreeParams;
4
5#[cfg(not(test))]
6use alloc::vec::Vec;
7
8#[cfg(feature = "serde")]
9use serde::{Deserialize, Serialize};
10
11#[derive(Debug, Clone)]
12#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
13#[cfg_attr(
14    feature = "serde",
15    serde(bound(
16        serialize = "T: Serialize, T::Envelope: Serialize",
17        deserialize = "T: Deserialize<'de>, T::Envelope: Deserialize<'de>"
18    ))
19)]
20
21/// An internal tree node.
22///
23/// For most applications, using this type should not be required.
24pub enum RTreeNode<T>
25where
26    T: RTreeObject,
27{
28    /// A leaf node, only containing the r-tree object
29    Leaf(T),
30    /// A parent node containing several child nodes
31    Parent(ParentNode<T>),
32}
33
34/// Represents an internal parent node.
35///
36/// For most applications, using this type should not be required. Allows read access to this
37/// node's envelope and its children.
38#[derive(Debug, Clone)]
39#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
40pub struct ParentNode<T>
41where
42    T: RTreeObject,
43{
44    pub(crate) children: Vec<RTreeNode<T>>,
45    pub(crate) envelope: T::Envelope,
46}
47
48impl<T> RTreeObject for RTreeNode<T>
49where
50    T: RTreeObject,
51{
52    type Envelope = T::Envelope;
53
54    fn envelope(&self) -> Self::Envelope {
55        match self {
56            RTreeNode::Leaf(ref t) => t.envelope(),
57            RTreeNode::Parent(ref data) => data.envelope.clone(),
58        }
59    }
60}
61
62#[doc(hidden)]
63impl<T> RTreeNode<T>
64where
65    T: RTreeObject,
66{
67    pub fn is_leaf(&self) -> bool {
68        match self {
69            RTreeNode::Leaf(..) => true,
70            RTreeNode::Parent(..) => false,
71        }
72    }
73}
74
75impl<T> ParentNode<T>
76where
77    T: RTreeObject,
78{
79    /// Returns this node's children
80    pub fn children(&self) -> &[RTreeNode<T>] {
81        &self.children
82    }
83
84    /// Returns the smallest envelope that encompasses all children.
85    pub fn envelope(&self) -> T::Envelope {
86        self.envelope.clone()
87    }
88
89    pub(crate) fn new_root<Params>() -> Self
90    where
91        Params: RTreeParams,
92    {
93        ParentNode {
94            envelope: Envelope::new_empty(),
95            children: Vec::with_capacity(Params::MAX_SIZE + 1),
96        }
97    }
98
99    pub(crate) fn new_parent(children: Vec<RTreeNode<T>>) -> Self {
100        let envelope = envelope_for_children(&children);
101
102        ParentNode { envelope, children }
103    }
104
105    #[cfg(test)]
106    #[allow(missing_docs)]
107    pub fn sanity_check<Params>(&self, check_max_size: bool) -> Option<usize>
108    where
109        Params: RTreeParams,
110    {
111        if self.children.is_empty() {
112            Some(0)
113        } else {
114            let mut result = None;
115            self.sanity_check_inner::<Params>(check_max_size, 1, &mut result);
116            result
117        }
118    }
119
120    #[cfg(test)]
121    fn sanity_check_inner<Params>(
122        &self,
123        check_max_size: bool,
124        height: usize,
125        leaf_height: &mut Option<usize>,
126    ) where
127        Params: RTreeParams,
128    {
129        if height > 1 {
130            let min_size = Params::MIN_SIZE;
131            assert!(self.children.len() >= min_size);
132        }
133        let mut envelope = T::Envelope::new_empty();
134        if check_max_size {
135            let max_size = Params::MAX_SIZE;
136            assert!(self.children.len() <= max_size);
137        }
138
139        for child in &self.children {
140            match child {
141                RTreeNode::Leaf(ref t) => {
142                    envelope.merge(&t.envelope());
143                    if let Some(ref leaf_height) = leaf_height {
144                        assert_eq!(height, *leaf_height);
145                    } else {
146                        *leaf_height = Some(height);
147                    }
148                }
149                RTreeNode::Parent(ref data) => {
150                    envelope.merge(&data.envelope);
151                    data.sanity_check_inner::<Params>(check_max_size, height + 1, leaf_height);
152                }
153            }
154        }
155        assert_eq!(self.envelope, envelope);
156    }
157}
158
159pub fn envelope_for_children<T>(children: &[RTreeNode<T>]) -> T::Envelope
160where
161    T: RTreeObject,
162{
163    let mut result = T::Envelope::new_empty();
164    for child in children {
165        result.merge(&child.envelope());
166    }
167    result
168}
rstar/node.rs

rstar/
node.rs
