rstar/
node.rs

1use crate::envelope::Envelope;
2use crate::object::RTreeObject;
3use crate::params::RTreeParams;
4
5use alloc::vec::Vec;
6
7#[cfg(feature = "serde")]
8use serde::{Deserialize, Serialize};
9
10#[derive(Debug, Clone)]
11#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
12#[cfg_attr(
13    feature = "serde",
14    serde(bound(
15        serialize = "T: Serialize, T::Envelope: Serialize",
16        deserialize = "T: Deserialize<'de>, T::Envelope: Deserialize<'de>"
17    ))
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    pub fn sanity_check<Params>(&self, check_max_size: bool) -> Option<usize>
106    where
107        Params: RTreeParams,
108    {
109        if self.children.is_empty() {
110            Some(0)
111        } else {
112            let mut result = None;
113            self.sanity_check_inner::<Params>(check_max_size, 1, &mut result);
114            result
115        }
116    }
117
118    #[cfg(test)]
119    fn sanity_check_inner<Params>(
120        &self,
121        check_max_size: bool,
122        height: usize,
123        leaf_height: &mut Option<usize>,
124    ) where
125        Params: RTreeParams,
126    {
127        if height > 1 {
128            let min_size = Params::MIN_SIZE;
129            assert!(self.children.len() >= min_size);
130        }
131        let mut envelope = T::Envelope::new_empty();
132        if check_max_size {
133            let max_size = Params::MAX_SIZE;
134            assert!(self.children.len() <= max_size);
135        }
136
137        for child in &self.children {
138            match child {
139                RTreeNode::Leaf(ref t) => {
140                    envelope.merge(&t.envelope());
141                    if let Some(ref leaf_height) = leaf_height {
142                        assert_eq!(height, *leaf_height);
143                    } else {
144                        *leaf_height = Some(height);
145                    }
146                }
147                RTreeNode::Parent(ref data) => {
148                    envelope.merge(&data.envelope);
149                    data.sanity_check_inner::<Params>(check_max_size, height + 1, leaf_height);
150                }
151            }
152        }
153        assert_eq!(self.envelope, envelope);
154    }
155}
156
157pub fn envelope_for_children<T>(children: &[RTreeNode<T>]) -> T::Envelope
158where
159    T: RTreeObject,
160{
161    let mut result = T::Envelope::new_empty();
162    for child in children {
163        result.merge(&child.envelope());
164    }
165    result
166}
rstar/node.rs

rstar/
node.rs
