28#ifndef __MDDS_QUAD_NODE_HPP__
29#define __MDDS_QUAD_NODE_HPP__
31#include "mdds/global.hpp"
35#include <boost/intrusive_ptr.hpp>
39#ifdef MDDS_DEBUG_NODE_BASE
40size_t node_instance_count = 0;
41inline size_t get_node_instance_count()
43 return node_instance_count;
68enum search_region_space_t
98inline node_quadrant_t opposite(node_quadrant_t quad)
103 return quad_southwest;
105 return quad_southeast;
107 return quad_northwest;
109 return quad_northeast;
110 case quad_unspecified:
113 return quad_unspecified;
116template<
typename _NodePtr,
typename _NodeType,
typename _Key>
119 typedef _Key key_type;
120 typedef _NodePtr node_ptr;
121 typedef _NodeType node_type;
135 : refcount(0), parent(
nullptr), northeast(
nullptr), northwest(
nullptr), southeast(
nullptr), southwest(
nullptr),
138#ifdef MDDS_DEBUG_NODE_BASE
139 ++node_instance_count;
148 : refcount(0), parent(nullptr), northeast(nullptr), northwest(nullptr), southeast(nullptr), southwest(nullptr),
151#ifdef MDDS_DEBUG_NODE_BASE
152 ++node_instance_count;
158 return !northeast && !northwest && !southeast && !southwest;
161 bool operator==(
const quad_node_base& r)
const
163 return x == r.x && y == r.y;
182#ifdef MDDS_DEBUG_NODE_BASE
183 --node_instance_count;
185 static_cast<node_type*
>(
this)->dispose();
198 return other_y < y ? quad_northwest : quad_southwest;
201 return other_y < y ? quad_northeast : quad_southeast;
204 bool has_quadrant_node(node_quadrant_t quad)
const
209 return northeast.get() !=
nullptr;
211 return northwest.get() !=
nullptr;
213 return southeast.get() !=
nullptr;
215 return southwest.get() !=
nullptr;
222 node_ptr get_quadrant_node(node_quadrant_t quad)
const
240 throw general_error(
"unknown quadrant type");
246template<
typename _NodePtr,
typename _NodeType,
typename _Key>
252template<
typename _NodePtr,
typename _NodeType,
typename _Key>
260template<
typename _NodePtr>
261void disconnect_node_from_parent(_NodePtr p)
263 if (!p || !p->parent)
267 _NodePtr& parent = p->parent;
268 if (parent->northeast && parent->northeast == p)
270 parent->northeast.reset();
272 else if (parent->northwest && parent->northwest == p)
274 parent->northwest.reset();
276 else if (parent->southwest && parent->southwest == p)
278 parent->southwest.reset();
280 else if (parent->southeast && parent->southeast == p)
282 parent->southeast.reset();
285 throw general_error(
"parent node doesn't lead to the deleted node.");
288template<
typename _NodePtr>
289void disconnect_all_nodes(_NodePtr p)
296 disconnect_all_nodes(p->northeast);
297 p->northeast.reset();
302 disconnect_all_nodes(p->northwest);
303 p->northwest.reset();
308 disconnect_all_nodes(p->southeast);
309 p->southeast.reset();
314 disconnect_all_nodes(p->southwest);
315 p->southwest.reset();
321template<
typename _NodeType,
typename _Key>
322search_region_space_t get_search_region_space(_NodeType* p, _Key x1, _Key y1, _Key x2, _Key y2)
324 typedef _Key key_type;
326 key_type x = p->x, y = p->y;
332 return region_northwest;
334 else if (y1 <= y && y <= y2)
340 return region_southwest;
342 else if (x1 <= x && x <= x2)
349 else if (y1 <= y && y <= y2)
351 return region_center;
362 return region_northeast;
364 else if (y1 <= y && y <= y2)
370 return region_southeast;
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