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
21pub enum RTreeNode<T>
25where
26 T: RTreeObject,
27{
28 Leaf(T),
30 Parent(ParentNode<T>),
32}
33
34#[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 pub fn children(&self) -> &[RTreeNode<T>] {
81 &self.children
82 }
83
84 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}