mdds
Loading...
Searching...
No Matches
quad_node.hpp
1// SPDX-FileCopyrightText: 2010 - 2025 Kohei Yoshida
2//
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
7#include "mdds/global.hpp"
8
9#include <cassert>
10
11#include <boost/intrusive_ptr.hpp>
12
13namespace mdds {
14
15#ifdef MDDS_DEBUG_NODE_BASE
16size_t node_instance_count = 0;
17inline size_t get_node_instance_count()
18{
19 return node_instance_count;
20}
21#endif
22
28enum node_quadrant_t
29{
30 quad_northeast,
31 quad_northwest,
32 quad_southeast,
33 quad_southwest,
34 quad_unspecified
35};
36
44enum search_region_space_t
45{
46 region_northwest,
47 region_north,
48 region_northeast,
49 region_east,
50 region_southeast,
51 region_south,
52 region_southwest,
53 region_west,
54 region_center
55};
56
66enum direction_t
67{
68 dir_north,
69 dir_west,
70 dir_south,
71 dir_east
72};
73
74inline node_quadrant_t opposite(node_quadrant_t quad)
75{
76 switch (quad)
77 {
78 case quad_northeast:
79 return quad_southwest;
80 case quad_northwest:
81 return quad_southeast;
82 case quad_southeast:
83 return quad_northwest;
84 case quad_southwest:
85 return quad_northeast;
86 case quad_unspecified:
87 default:;
88 }
89 return quad_unspecified;
90}
91
92template<typename NodePtr, typename NodeType, typename Key>
93struct quad_node_base
94{
95 typedef Key key_type;
96 typedef NodePtr node_ptr;
97 typedef NodeType node_type;
98
99 size_t refcount;
100
101 node_ptr parent;
102 node_ptr northeast;
103 node_ptr northwest;
104 node_ptr southeast;
105 node_ptr southwest;
106
107 key_type x;
108 key_type y;
109
110 quad_node_base(key_type _x, key_type _y)
111 : refcount(0), parent(nullptr), northeast(nullptr), northwest(nullptr), southeast(nullptr), southwest(nullptr),
112 x(_x), y(_y)
113 {
114#ifdef MDDS_DEBUG_NODE_BASE
115 ++node_instance_count;
116#endif
117 }
118
123 quad_node_base(const quad_node_base& r)
124 : refcount(0), parent(nullptr), northeast(nullptr), northwest(nullptr), southeast(nullptr), southwest(nullptr),
125 x(r.x), y(r.y)
126 {
127#ifdef MDDS_DEBUG_NODE_BASE
128 ++node_instance_count;
129#endif
130 }
131
132 bool leaf() const
133 {
134 return !northeast && !northwest && !southeast && !southwest;
135 }
136
137 bool operator==(const quad_node_base& r) const
138 {
139 return x == r.x && y == r.y;
140 }
141
145 quad_node_base& operator=(const quad_node_base& r)
146 {
147 if (this == &r)
148 // assignment to self.
149 return *this;
150
151 x = r.x;
152 y = r.y;
153 return *this;
154 }
155
157 {
158#ifdef MDDS_DEBUG_NODE_BASE
159 --node_instance_count;
160#endif
161 static_cast<node_type*>(this)->dispose();
162 }
163
170 node_quadrant_t get_quadrant(key_type other_x, key_type other_y) const
171 {
172 if (other_x < x)
173 // west
174 return other_y < y ? quad_northwest : quad_southwest;
175
176 // east
177 return other_y < y ? quad_northeast : quad_southeast;
178 }
179
180 bool has_quadrant_node(node_quadrant_t quad) const
181 {
182 switch (quad)
183 {
184 case quad_northeast:
185 return northeast.get() != nullptr;
186 case quad_northwest:
187 return northwest.get() != nullptr;
188 case quad_southeast:
189 return southeast.get() != nullptr;
190 case quad_southwest:
191 return southwest.get() != nullptr;
192 default:
193 throw general_error("unknown quadrant type");
194 }
195 return false;
196 }
197
198 node_ptr get_quadrant_node(node_quadrant_t quad) const
199 {
200 node_ptr ret;
201 switch (quad)
202 {
203 case quad_northeast:
204 ret = northeast;
205 break;
206 case quad_northwest:
207 ret = northwest;
208 break;
209 case quad_southeast:
210 ret = southeast;
211 break;
212 case quad_southwest:
213 ret = southwest;
214 break;
215 default:
216 throw general_error("unknown quadrant type");
217 }
218 return ret;
219 }
220};
221
222template<typename NodePtr, typename NodeType, typename Key>
223inline void intrusive_ptr_add_ref(::mdds::quad_node_base<NodePtr, NodeType, Key>* p)
224{
225 ++p->refcount;
226}
227
228template<typename NodePtr, typename NodeType, typename Key>
229inline void intrusive_ptr_release(::mdds::quad_node_base<NodePtr, NodeType, Key>* p)
230{
231 --p->refcount;
232 if (!p->refcount)
233 // NB: Delete as the derived node type to ensure the size of the deleted
234 // object is correct.
235 delete static_cast<NodeType*>(p);
236}
237
238template<typename NodePtr>
239void disconnect_node_from_parent(NodePtr p)
240{
241 if (!p || !p->parent)
242 // Nothing to do.
243 return;
244
245 NodePtr& parent = p->parent;
246 if (parent->northeast && parent->northeast == p)
247 {
248 parent->northeast.reset();
249 }
250 else if (parent->northwest && parent->northwest == p)
251 {
252 parent->northwest.reset();
253 }
254 else if (parent->southwest && parent->southwest == p)
255 {
256 parent->southwest.reset();
257 }
258 else if (parent->southeast && parent->southeast == p)
259 {
260 parent->southeast.reset();
261 }
262 else
263 throw general_error("parent node doesn't lead to the deleted node.");
264}
265
266template<typename NodePtr>
267void disconnect_all_nodes(NodePtr p)
268{
269 if (!p)
270 return;
271
272 if (p->northeast)
273 {
274 disconnect_all_nodes(p->northeast);
275 p->northeast.reset();
276 }
277
278 if (p->northwest)
279 {
280 disconnect_all_nodes(p->northwest);
281 p->northwest.reset();
282 }
283
284 if (p->southeast)
285 {
286 disconnect_all_nodes(p->southeast);
287 p->southeast.reset();
288 }
289
290 if (p->southwest)
291 {
292 disconnect_all_nodes(p->southwest);
293 p->southwest.reset();
294 }
295
296 p->parent.reset();
297}
298
299template<typename NodeType, typename Key>
300search_region_space_t get_search_region_space(NodeType* p, Key x1, Key y1, Key x2, Key y2)
301{
302 typedef Key key_type;
303
304 key_type x = p->x, y = p->y;
305 if (x < x1)
306 {
307 // western region
308 if (y < y1)
309 {
310 return region_northwest;
311 }
312 else if (y1 <= y && y <= y2)
313 {
314 return region_west;
315 }
316
317 assert(y2 < y);
318 return region_southwest;
319 }
320 else if (x1 <= x && x <= x2)
321 {
322 // central region
323 if (y < y1)
324 {
325 return region_north;
326 }
327 else if (y1 <= y && y <= y2)
328 {
329 return region_center;
330 }
331
332 assert(y2 < y);
333 return region_south;
334 }
335
336 // eastern region
337 assert(x2 < x);
338 if (y < y1)
339 {
340 return region_northeast;
341 }
342 else if (y1 <= y && y <= y2)
343 {
344 return region_east;
345 }
346
347 assert(y2 < y);
348 return region_southeast;
349}
350
351} // namespace mdds
Definition global.hpp:54
Definition quad_node.hpp:94
node_quadrant_t get_quadrant(key_type other_x, key_type other_y) const
Definition quad_node.hpp:170
quad_node_base(const quad_node_base &r)
Definition quad_node.hpp:123
quad_node_base & operator=(const quad_node_base &r)
Definition quad_node.hpp:145