1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
use crate::geometry::Region;
use crate::rtree::Index;
#[derive(Debug)]
pub struct Node<S> {
/// The minimum bounding region enclosing all data contained in this node.
minimum_bounding_region: Region,
/// A vector containing all of the children of this node.
children: Vec<Index>,
/// Some data owned by this node
data: Option<S>,
/// The index of the parent node in our tree.
parent: Option<Index>,
}
impl<S> Node<S> {
/// Create a new node.
#[inline(always)]
fn new(
minimum_bounding_region: Region,
children: Vec<Index>,
data: Option<S>,
parent: Option<Index>,
) -> Self {
Self {
minimum_bounding_region,
children,
data,
parent,
}
}
/// Returns `true` if this node is a leaf node, `false` otherwise.
#[inline(always)]
pub fn is_leaf(&self) -> bool {
self.data.is_some()
}
/// Returns `true` if this node has any children, `false` otherwise.
#[inline(always)]
pub fn has_children(&self) -> bool {
!self.children.is_empty()
}
/// Returns the number of direct children this node has.
#[inline(always)]
pub fn child_count(&self) -> usize {
self.children.len()
}
/// Returns a reference to the minimum bounding region of this node.
#[inline(always)]
pub fn get_region(&self) -> &Region {
&self.minimum_bounding_region
}
/// Returns an iterator over the `Index`es of children of this node.
#[inline(always)]
pub fn child_index_iter(&self) -> impl Iterator<Item = Index> + '_ {
self.children.iter().cloned()
}
/// Creates a new internal [`Node`] with the given minimum bounding region and parent.
#[inline(always)]
pub(crate) fn new_internal_node(
minimum_bounding_region: Region,
parent: Option<Index>,
) -> Self {
Self::new(minimum_bounding_region, Vec::new(), None, parent)
}
/// Creates a new leaf [`Node`] with the given minimum bounding region and parent.
#[inline(always)]
pub(crate) fn new_leaf(
minimum_bounding_region: Region,
data: S,
parent: Option<Index>,
) -> Self {
Self::new(minimum_bounding_region, Vec::new(), Some(data), parent)
}
/// Combines the current minimum bounding of this region with `region`. This method is unsafe,
/// as using it incorrectly will lead to corrupt data.
///
/// To use this function safely, it is required that the minimum bounding region of the parent
/// of this node contains `region` (and is thus guaranteed to contain the combination of
/// this nodes current [`Region`] and `region`).
#[inline(always)]
pub(crate) fn combine_region_unsafe(&mut self, region: &Region) {
self.minimum_bounding_region.combine_region_in_place(region);
}
/// Sets the children vector of `self` to be equal to `children`. This method is unsafe,
/// as using it incorrectly will lead to corrupt data.
///
/// To use this function safely, it is required that:
/// - The node currently has no children (to prevent dangling nodes in our tree), and
/// - All of the nodes referred to by `children` must already have their `parent` attribute
/// set to the index of the current node.
#[inline(always)]
pub(crate) fn set_children_unsafe(&mut self, children: Vec<Index>) {
// Again, we should only ever do this on a node that has no children.
debug_assert!(self.children.is_empty());
self.children = children;
}
/// Adds a new child to the current node. This method is unsafe, as using it incorrectly
/// will lead to corrupt data.
///
/// To use this function safely, it is required that the node with index `child_index`
/// in our tree has their `parent` attribute set to the index of the current node, and
/// that the child is contained in the minimum bounding region of this node.
#[inline(always)]
pub(crate) fn add_child_unsafe(&mut self, child_index: Index) {
self.children.push(child_index);
}
/// Returns the `parent` of the current node
#[inline(always)]
pub(crate) fn get_parent(&self) -> Option<Index> {
self.parent
}
/// Updates the `parent` of the current node
#[inline(always)]
pub(crate) fn set_parent(&mut self, index: Index) {
self.parent = Some(index);
}
/// Overwrites the current minimum bounding region of this node. This method is unsafe,
/// as using it incorrectly can lead to corrupt data.
///
/// To use this function safely, you must ensure that:
/// - The minimum bounding region of any children of this node is containing
/// in the input `minimum_bounding_region`, and
/// - `minimum_bounding_region` is contained in the minimum bounding region of
/// the parent of this node.
#[inline(always)]
pub(crate) fn set_minimum_bounding_region_unsafe(&mut self, minimum_bounding_region: Region) {
self.minimum_bounding_region = minimum_bounding_region;
}
/// Clears all children of the current node, returning a vector of all of the direct
/// children of the current node.
#[inline(always)]
pub(crate) fn clear_children(&mut self) -> Vec<Index> {
let mut buffer = Vec::new();
std::mem::swap(&mut buffer, &mut self.children);
buffer
}
/// Returns a reference to the data owned by this node.
#[inline(always)]
pub fn get_data(&self) -> Option<&S> {
self.data.as_ref()
}
}