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 
37 namespace mdds {
38 
39 #ifdef MDDS_DEBUG_NODE_BASE
40 size_t node_instance_count = 0;
41 inline size_t get_node_instance_count()
42 {
43  return node_instance_count;
44 }
45 #endif
46 
52 enum node_quadrant_t
53 {
54  quad_northeast,
55  quad_northwest,
56  quad_southeast,
57  quad_southwest,
58  quad_unspecified
59 };
60 
68 enum 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 
90 enum direction_t
91 {
92  dir_north,
93  dir_west,
94  dir_south,
95  dir_east
96 };
97 
98 inline 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 
116 template<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 
180  ~quad_node_base()
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 
246 template<typename _NodePtr, typename _NodeType, typename _Key>
247 inline void intrusive_ptr_add_ref(::mdds::quad_node_base<_NodePtr, _NodeType, _Key>* p)
248 {
249  ++p->refcount;
250 }
251 
252 template<typename _NodePtr, typename _NodeType, typename _Key>
253 inline 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 
260 template<typename _NodePtr>
261 void 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 
288 template<typename _NodePtr>
289 void 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 
321 template<typename _NodeType, typename _Key>
322 search_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
quad_node_base(const quad_node_base &r)
Definition: quad_node.hpp:147
Definition: global.hpp:83
Definition: flat_segment_tree.hpp:46
quad_node_base & operator=(const quad_node_base &r)
Definition: quad_node.hpp:169
Definition: quad_node.hpp:117
node_quadrant_t get_quadrant(key_type other_x, key_type other_y) const
Definition: quad_node.hpp:194