mdds
quad_node.hpp
1/*************************************************************************
2 *
3 * Copyright (c) 2010 Kohei Yoshida
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 *
26 ************************************************************************/
27
28#ifndef __MDDS_QUAD_NODE_HPP__
29#define __MDDS_QUAD_NODE_HPP__
30
31#include "mdds/global.hpp"
32
33#include <cassert>
34
35#include <boost/intrusive_ptr.hpp>
36
37namespace mdds {
38
39#ifdef MDDS_DEBUG_NODE_BASE
40size_t node_instance_count = 0;
41inline size_t get_node_instance_count()
42{
43 return node_instance_count;
44}
45#endif
46
52enum node_quadrant_t
53{
54 quad_northeast,
55 quad_northwest,
56 quad_southeast,
57 quad_southwest,
58 quad_unspecified
59};
60
68enum search_region_space_t
69{
70 region_northwest,
71 region_north,
72 region_northeast,
73 region_east,
74 region_southeast,
75 region_south,
76 region_southwest,
77 region_west,
78 region_center
79};
80
90enum direction_t
91{
92 dir_north,
93 dir_west,
94 dir_south,
95 dir_east
96};
97
98inline node_quadrant_t opposite(node_quadrant_t quad)
99{
100 switch (quad)
101 {
102 case quad_northeast:
103 return quad_southwest;
104 case quad_northwest:
105 return quad_southeast;
106 case quad_southeast:
107 return quad_northwest;
108 case quad_southwest:
109 return quad_northeast;
110 case quad_unspecified:
111 default:;
112 }
113 return quad_unspecified;
114}
115
116template<typename _NodePtr, typename _NodeType, typename _Key>
118{
119 typedef _Key key_type;
120 typedef _NodePtr node_ptr;
121 typedef _NodeType node_type;
122
123 size_t refcount;
124
125 node_ptr parent;
126 node_ptr northeast;
127 node_ptr northwest;
128 node_ptr southeast;
129 node_ptr southwest;
130
131 key_type x;
132 key_type y;
133
134 quad_node_base(key_type _x, key_type _y)
135 : refcount(0), parent(nullptr), northeast(nullptr), northwest(nullptr), southeast(nullptr), southwest(nullptr),
136 x(_x), y(_y)
137 {
138#ifdef MDDS_DEBUG_NODE_BASE
139 ++node_instance_count;
140#endif
141 }
142
148 : refcount(0), parent(nullptr), northeast(nullptr), northwest(nullptr), southeast(nullptr), southwest(nullptr),
149 x(r.x), y(r.y)
150 {
151#ifdef MDDS_DEBUG_NODE_BASE
152 ++node_instance_count;
153#endif
154 }
155
156 bool leaf() const
157 {
158 return !northeast && !northwest && !southeast && !southwest;
159 }
160
161 bool operator==(const quad_node_base& r) const
162 {
163 return x == r.x && y == r.y;
164 }
165
170 {
171 if (this == &r)
172 // assignment to self.
173 return *this;
174
175 x = r.x;
176 y = r.y;
177 return *this;
178 }
179
181 {
182#ifdef MDDS_DEBUG_NODE_BASE
183 --node_instance_count;
184#endif
185 static_cast<node_type*>(this)->dispose();
186 }
187
194 node_quadrant_t get_quadrant(key_type other_x, key_type other_y) const
195 {
196 if (other_x < x)
197 // west
198 return other_y < y ? quad_northwest : quad_southwest;
199
200 // east
201 return other_y < y ? quad_northeast : quad_southeast;
202 }
203
204 bool has_quadrant_node(node_quadrant_t quad) const
205 {
206 switch (quad)
207 {
208 case quad_northeast:
209 return northeast.get() != nullptr;
210 case quad_northwest:
211 return northwest.get() != nullptr;
212 case quad_southeast:
213 return southeast.get() != nullptr;
214 case quad_southwest:
215 return southwest.get() != nullptr;
216 default:
217 throw general_error("unknown quadrant type");
218 }
219 return false;
220 }
221
222 node_ptr get_quadrant_node(node_quadrant_t quad) const
223 {
224 node_ptr ret;
225 switch (quad)
226 {
227 case quad_northeast:
228 ret = northeast;
229 break;
230 case quad_northwest:
231 ret = northwest;
232 break;
233 case quad_southeast:
234 ret = southeast;
235 break;
236 case quad_southwest:
237 ret = southwest;
238 break;
239 default:
240 throw general_error("unknown quadrant type");
241 }
242 return ret;
243 }
244};
245
246template<typename _NodePtr, typename _NodeType, typename _Key>
247inline void intrusive_ptr_add_ref(::mdds::quad_node_base<_NodePtr, _NodeType, _Key>* p)
248{
249 ++p->refcount;
250}
251
252template<typename _NodePtr, typename _NodeType, typename _Key>
253inline void intrusive_ptr_release(::mdds::quad_node_base<_NodePtr, _NodeType, _Key>* p)
254{
255 --p->refcount;
256 if (!p->refcount)
257 delete p;
258}
259
260template<typename _NodePtr>
261void disconnect_node_from_parent(_NodePtr p)
262{
263 if (!p || !p->parent)
264 // Nothing to do.
265 return;
266
267 _NodePtr& parent = p->parent;
268 if (parent->northeast && parent->northeast == p)
269 {
270 parent->northeast.reset();
271 }
272 else if (parent->northwest && parent->northwest == p)
273 {
274 parent->northwest.reset();
275 }
276 else if (parent->southwest && parent->southwest == p)
277 {
278 parent->southwest.reset();
279 }
280 else if (parent->southeast && parent->southeast == p)
281 {
282 parent->southeast.reset();
283 }
284 else
285 throw general_error("parent node doesn't lead to the deleted node.");
286}
287
288template<typename _NodePtr>
289void disconnect_all_nodes(_NodePtr p)
290{
291 if (!p)
292 return;
293
294 if (p->northeast)
295 {
296 disconnect_all_nodes(p->northeast);
297 p->northeast.reset();
298 }
299
300 if (p->northwest)
301 {
302 disconnect_all_nodes(p->northwest);
303 p->northwest.reset();
304 }
305
306 if (p->southeast)
307 {
308 disconnect_all_nodes(p->southeast);
309 p->southeast.reset();
310 }
311
312 if (p->southwest)
313 {
314 disconnect_all_nodes(p->southwest);
315 p->southwest.reset();
316 }
317
318 p->parent.reset();
319}
320
321template<typename _NodeType, typename _Key>
322search_region_space_t get_search_region_space(_NodeType* p, _Key x1, _Key y1, _Key x2, _Key y2)
323{
324 typedef _Key key_type;
325
326 key_type x = p->x, y = p->y;
327 if (x < x1)
328 {
329 // western region
330 if (y < y1)
331 {
332 return region_northwest;
333 }
334 else if (y1 <= y && y <= y2)
335 {
336 return region_west;
337 }
338
339 assert(y2 < y);
340 return region_southwest;
341 }
342 else if (x1 <= x && x <= x2)
343 {
344 // central region
345 if (y < y1)
346 {
347 return region_north;
348 }
349 else if (y1 <= y && y <= y2)
350 {
351 return region_center;
352 }
353
354 assert(y2 < y);
355 return region_south;
356 }
357
358 // eastern region
359 assert(x2 < x);
360 if (y < y1)
361 {
362 return region_northeast;
363 }
364 else if (y1 <= y && y <= y2)
365 {
366 return region_east;
367 }
368
369 assert(y2 < y);
370 return region_southeast;
371}
372
373} // namespace mdds
374
375#endif
Definition: global.hpp:84
Definition: quad_node.hpp:118
quad_node_base(const quad_node_base &r)
Definition: quad_node.hpp:147
quad_node_base & operator=(const quad_node_base &r)
Definition: quad_node.hpp:169
node_quadrant_t get_quadrant(key_type other_x, key_type other_y) const
Definition: quad_node.hpp:194