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

rstar/
node.rs
