7#include "mdds/global.hpp"
11#include <boost/intrusive_ptr.hpp>
15#ifdef MDDS_DEBUG_NODE_BASE
16size_t node_instance_count = 0;
17inline size_t get_node_instance_count()
19 return node_instance_count;
44enum search_region_space_t
74inline node_quadrant_t opposite(node_quadrant_t quad)
79 return quad_southwest;
81 return quad_southeast;
83 return quad_northwest;
85 return quad_northeast;
86 case quad_unspecified:
89 return quad_unspecified;
92template<
typename NodePtr,
typename NodeType,
typename Key>
96 typedef NodePtr node_ptr;
97 typedef NodeType node_type;
110 quad_node_base(key_type _x, key_type _y)
111 : refcount(0), parent(
nullptr), northeast(
nullptr), northwest(
nullptr), southeast(
nullptr), southwest(
nullptr),
114#ifdef MDDS_DEBUG_NODE_BASE
115 ++node_instance_count;
124 : refcount(0), parent(nullptr), northeast(nullptr), northwest(nullptr), southeast(nullptr), southwest(nullptr),
127#ifdef MDDS_DEBUG_NODE_BASE
128 ++node_instance_count;
134 return !northeast && !northwest && !southeast && !southwest;
137 bool operator==(
const quad_node_base& r)
const
139 return x == r.x && y == r.y;
158#ifdef MDDS_DEBUG_NODE_BASE
159 --node_instance_count;
161 static_cast<node_type*
>(
this)->dispose();
174 return other_y < y ? quad_northwest : quad_southwest;
177 return other_y < y ? quad_northeast : quad_southeast;
180 bool has_quadrant_node(node_quadrant_t quad)
const
185 return northeast.get() !=
nullptr;
187 return northwest.get() !=
nullptr;
189 return southeast.get() !=
nullptr;
191 return southwest.get() !=
nullptr;
198 node_ptr get_quadrant_node(node_quadrant_t quad)
const
216 throw general_error(
"unknown quadrant type");
222template<
typename NodePtr,
typename NodeType,
typename Key>
223inline void intrusive_ptr_add_ref(::mdds::quad_node_base<NodePtr, NodeType, Key>* p)
228template<
typename NodePtr,
typename NodeType,
typename Key>
229inline void intrusive_ptr_release(::mdds::quad_node_base<NodePtr, NodeType, Key>* p)
235 delete static_cast<NodeType*
>(p);
238template<
typename NodePtr>
239void disconnect_node_from_parent(NodePtr p)
241 if (!p || !p->parent)
245 NodePtr& parent = p->parent;
246 if (parent->northeast && parent->northeast == p)
248 parent->northeast.reset();
250 else if (parent->northwest && parent->northwest == p)
252 parent->northwest.reset();
254 else if (parent->southwest && parent->southwest == p)
256 parent->southwest.reset();
258 else if (parent->southeast && parent->southeast == p)
260 parent->southeast.reset();
263 throw general_error(
"parent node doesn't lead to the deleted node.");
266template<
typename NodePtr>
267void disconnect_all_nodes(NodePtr p)
274 disconnect_all_nodes(p->northeast);
275 p->northeast.reset();
280 disconnect_all_nodes(p->northwest);
281 p->northwest.reset();
286 disconnect_all_nodes(p->southeast);
287 p->southeast.reset();
292 disconnect_all_nodes(p->southwest);
293 p->southwest.reset();
299template<
typename NodeType,
typename Key>
300search_region_space_t get_search_region_space(NodeType* p, Key x1, Key y1, Key x2, Key y2)
302 typedef Key key_type;
304 key_type x = p->x, y = p->y;
310 return region_northwest;
312 else if (y1 <= y && y <= y2)
318 return region_southwest;
320 else if (x1 <= x && x <= x2)
327 else if (y1 <= y && y <= y2)
329 return region_center;
340 return region_northeast;
342 else if (y1 <= y && y <= y2)
348 return region_southeast;
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