28 #ifndef INCLUDED_MDDS_POINT_QUAD_TREE_HPP 29 #define INCLUDED_MDDS_POINT_QUAD_TREE_HPP 31 #include "mdds/quad_node.hpp" 41 #define DEBUG_POINT_QUAD_TREE 0 45 template<
typename _PairType>
46 void ensure_order(_PairType& v)
48 if (v.first > v.second)
49 ::std::swap(v.first, v.second);
52 template<
typename _Key,
typename _NodeType,
typename _Inserter>
53 void search_region_node(
54 const _NodeType* p, _Key x1, _Key y1, _Key x2, _Key y2, _Inserter& result)
61 search_region_space_t region = ::mdds::get_search_region_space(p, x1, y1, x2, y2);
67 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
68 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
69 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
70 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
73 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
74 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
77 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
78 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
80 case region_northeast:
81 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
83 case region_northwest:
84 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
87 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
88 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
90 case region_southeast:
91 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
93 case region_southwest:
94 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
97 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
98 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
101 throw general_error(
"unknown search region");
106 template<
typename _Key,
typename _Value>
110 class search_result_inserter;
113 typedef _Key key_type;
114 typedef _Value value_type;
115 typedef size_t size_type;
116 typedef ::std::vector<value_type> data_array_type;
122 typedef ::boost::intrusive_ptr<node> node_ptr;
127 node(key_type _x, key_type _y, value_type _data) :
131 node(
const node& r) :
137 bool operator== (
const node& r)
const 142 node& operator= (
const node& r)
150 typedef ::std::vector<node_ptr> reinsert_tree_array_type;
151 typedef ::std::pair<key_type, key_type> key_range_type;
168 value_type data()
const {
return mp->data; }
169 key_type x()
const {
return mp->x; }
170 key_type y()
const {
return mp->y; }
172 operator bool()
const {
return mp !=
nullptr; }
173 bool operator== (
const node_access& r)
const {
return mp == r.mp; }
196 point(key_type _x, key_type _y) : x(_x), y(_y) {}
197 point() : x(0), y(0) {}
202 friend class search_result_inserter;
204 typedef std::vector<const node*> res_nodes_type;
205 typedef std::shared_ptr<res_nodes_type> res_nodes_ptr;
212 typedef typename
point_quad_tree<_Key,_Value>::value_type parent_value_type;
216 typedef std::pair<point, parent_value_type> value_type;
217 typedef value_type* pointer;
218 typedef value_type& reference;
219 typedef ptrdiff_t difference_type;
220 typedef ::std::bidirectional_iterator_tag iterator_category;
222 const_iterator(res_nodes_ptr& ptr) : mp_res_nodes(ptr), m_end_pos(false) {}
225 mp_res_nodes(r.mp_res_nodes),
226 m_cur_pos(r.m_cur_pos),
227 m_cur_value(r.m_cur_value),
228 m_end_pos(r.m_end_pos) {}
230 const_iterator& operator= (
const const_iterator& r)
232 mp_res_nodes = r.mp_res_nodes;
233 m_cur_pos = r.m_cur_pos;
234 m_cur_value = r.m_cur_value;
235 m_end_pos = r.m_end_pos;
239 bool operator== (
const const_iterator& r)
const 244 return mp_res_nodes.get() == r.mp_res_nodes.get() &&
245 m_cur_pos == r.m_cur_pos && m_end_pos == r.m_end_pos;
252 return m_end_pos == r.m_end_pos;
255 bool operator!= (
const const_iterator& r)
const 257 return !operator==(r);
260 const value_type& operator*()
const 265 const value_type* operator->()
const 267 return get_current_value();
270 const value_type* operator++()
277 typename res_nodes_type::const_iterator cur_pos = m_cur_pos;
278 if (++cur_pos == mp_res_nodes->end())
284 update_current_value();
288 const value_type* operator--()
293 return get_current_value();
296 update_current_value();
297 return get_current_value();
310 m_cur_pos = mp_res_nodes->begin();
312 update_current_value();
322 m_cur_pos = mp_res_nodes->end();
326 void update_current_value()
328 const node* p = *m_cur_pos;
329 m_cur_value.first =
point(p->x, p->y);
330 m_cur_value.second = p->data;
333 const value_type* get_current_value()
const 339 res_nodes_ptr mp_res_nodes;
340 typename res_nodes_type::const_iterator m_cur_pos;
341 value_type m_cur_value;
345 search_results() : mp_res_nodes(static_cast<res_nodes_type*>(
nullptr)) {}
363 void push_back(
const node* p)
366 mp_res_nodes.reset(
new res_nodes_type);
367 mp_res_nodes->push_back(p);
371 res_nodes_ptr mp_res_nodes;
386 void insert(key_type x, key_type y, value_type data);
400 void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result)
const;
415 search_results search_region(key_type x1, key_type y1, key_type x2, key_type y2)
const;
427 value_type find(key_type x, key_type y)
const;
436 void remove(key_type x, key_type y);
475 bool operator!= (
const point_quad_tree& r)
const {
return !operator== (r); }
477 #ifdef MDDS_UNIT_TEST 491 node_data(key_type _x, key_type _y, value_type _data) :
492 x(_x), y(_y), data(_data) {}
493 node_data(
const node_data& r) :
494 x(r.x), y(r.y), data(r.data) {}
496 bool operator== (
const node_data& r)
const 498 return (x == r.x) && (y == r.y) && (data == r.data);
501 bool operator!= (
const node_data& r)
const 503 return !operator==(r);
506 struct sorter :
public ::std::binary_function<node_data, node_data, bool>
508 bool operator() (
const node_data& left,
const node_data& right)
const 510 if (left.x != right.x)
511 return left.x < right.x;
512 if (left.y != right.y)
513 return left.y < right.y;
514 return left.data < right.data;
519 static bool equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2);
521 bool verify_data(::std::vector<node_data>& expected)
const;
523 bool verify_node_iterator(
const node_access& nac)
const;
524 static bool verify_node_iterator(
const node_access& nac,
const node* p);
526 void get_all_stored_data(::std::vector<node_data>& stored_data)
const;
528 void dump_tree_svg(const ::std::string& fpath)
const;
531 class array_inserter :
public ::std::unary_function<const node*, void>
534 array_inserter(data_array_type& result) : m_result(result) {}
536 void operator() (
const node* p)
538 m_result.push_back(p->data);
541 data_array_type& m_result;
544 class search_result_inserter :
public ::std::unary_function<const node*, void>
547 search_result_inserter(
search_results& result) : m_result(result) {}
549 void operator() (
const node* p)
551 m_result.push_back(p);
557 class data_inserter :
public ::std::unary_function<node_data, void>
562 void operator() (
const node_data& v)
564 m_db.insert(v.x, v.y, v.data);
572 node_quadrant_t quad;
576 node_distance() : quad(quad_unspecified), dist(0), node(
nullptr) {}
577 node_distance(node_quadrant_t _quad, key_type _dist,
const node_ptr& _node) :
578 quad(_quad), dist(_dist), node(_node) {}
581 node_ptr find_node(key_type x, key_type y)
const;
582 const node* find_node_ptr(key_type x, key_type y)
const;
583 node_ptr find_replacement_node(key_type x, key_type y,
const node_ptr& delete_node)
const;
585 void find_candidate_in_quad(key_type x, key_type y,
586 node_distance& dx_node, node_distance& dy_node, node_distance& min_city_block_node,
587 const node_ptr& delete_node, node_quadrant_t quad)
const;
589 void adjust_quad(
const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange,
590 node_ptr quad_root, direction_t dir, reinsert_tree_array_type& insert_list);
592 void set_new_root(
const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange,
593 node_ptr& quad_root, node_quadrant_t dir, reinsert_tree_array_type& insert_list);
595 void insert_node(node_ptr& dest, node_ptr& node);
596 void reinsert_tree(node_ptr& dest, node_ptr& root);
597 void reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root);
598 void clear_all_nodes();
599 void dump_node_svg(
const node* p, ::std::ofstream& file)
const;
600 void count_all_nodes(
const node* p,
size_t& node_count)
const;
602 void get_all_stored_data(
const node* p, ::std::vector<node_data>& stored_data)
const;
607 key_range_type m_xrange;
608 key_range_type m_yrange;
611 template<
typename _Key,
typename _Value>
619 template<
typename _Key,
typename _Value>
628 template<
typename _Key,
typename _Value>
634 template<
typename _Key,
typename _Value>
637 m_xrange.first = ::std::min(m_xrange.first, x);
638 m_xrange.second = ::std::max(m_xrange.second, x);
639 m_yrange.first = ::std::min(m_yrange.first, y);
640 m_yrange.second = ::std::max(m_yrange.second, y);
645 m_root.reset(
new node(x, y, data));
649 node_ptr cur_node = m_root;
652 if (cur_node->x == x && cur_node->y == y)
655 cur_node->data = data;
659 node_quadrant_t quad = cur_node->get_quadrant(x, y);
663 if (cur_node->northeast)
664 cur_node = cur_node->northeast;
667 cur_node->northeast.reset(
new node(x, y, data));
668 cur_node->northeast->parent = cur_node;
673 if (cur_node->northwest)
674 cur_node = cur_node->northwest;
677 cur_node->northwest.reset(
new node(x, y, data));
678 cur_node->northwest->parent = cur_node;
683 if (cur_node->southeast)
684 cur_node = cur_node->southeast;
687 cur_node->southeast.reset(
new node(x, y, data));
688 cur_node->southeast->parent = cur_node;
693 if (cur_node->southwest)
694 cur_node = cur_node->southwest;
697 cur_node->southwest.reset(
new node(x, y, data));
698 cur_node->southwest->parent = cur_node;
706 assert(!
"This should never be reached.");
709 template<
typename _Key,
typename _Value>
713 const node* p = m_root.get();
714 array_inserter _inserter(result);
715 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
718 template<
typename _Key,
typename _Value>
724 const node* p = m_root.get();
725 search_result_inserter _inserter(result);
726 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
730 template<
typename _Key,
typename _Value>
731 typename point_quad_tree<_Key,_Value>::value_type
734 const node* p = find_node_ptr(x, y);
740 template<
typename _Key,
typename _Value>
744 node_ptr delete_node = find_node(x, y);
749 #if DEBUG_POINT_QUAD_TREE 750 cout <<
"found the node to be removed at " << delete_node->x <<
"," << delete_node->y <<
" (" << *delete_node->data <<
")" << endl;
755 if (delete_node->leaf())
757 #if DEBUG_POINT_QUAD_TREE 758 cout <<
"deleting a leaf node." << endl;
760 if (delete_node.get() == m_root.get())
763 disconnect_node_from_parent(delete_node);
768 node_ptr repl_node = find_replacement_node(x, y, delete_node);
771 throw general_error(
"failed to find a replacement candidate node.");
773 node_quadrant_t repl_quad = delete_node->get_quadrant(repl_node->x, repl_node->y);
775 key_range_type xrange(delete_node->x, repl_node->x);
776 key_range_type yrange(delete_node->y, repl_node->y);
777 ensure_order(xrange);
778 ensure_order(yrange);
779 reinsert_tree_array_type insert_list;
787 adjust_quad(xrange, yrange, delete_node->northwest, dir_south, insert_list);
788 adjust_quad(xrange, yrange, delete_node->southeast, dir_west, insert_list);
789 set_new_root(xrange, yrange, delete_node->northeast, quad_southwest, insert_list);
792 adjust_quad(xrange, yrange, delete_node->northeast, dir_south, insert_list);
793 adjust_quad(xrange, yrange, delete_node->southwest, dir_east, insert_list);
794 set_new_root(xrange, yrange, delete_node->northwest, quad_southeast, insert_list);
797 adjust_quad(xrange, yrange, delete_node->northeast, dir_west, insert_list);
798 adjust_quad(xrange, yrange, delete_node->southwest, dir_north, insert_list);
799 set_new_root(xrange, yrange, delete_node->southeast, quad_northwest, insert_list);
802 adjust_quad(xrange, yrange, delete_node->northwest, dir_east, insert_list);
803 adjust_quad(xrange, yrange, delete_node->southeast, dir_north, insert_list);
804 set_new_root(xrange, yrange, delete_node->southwest, quad_northeast, insert_list);
807 throw general_error(
"quadrant for the replacement node is unspecified.");
817 node_ptr root = repl_node->northwest;
818 repl_node->northwest.reset();
819 reinsert_tree(delete_node, quad_northwest, root);
821 root = repl_node->southeast;
822 repl_node->southeast.reset();
823 reinsert_tree(delete_node, quad_southeast, root);
829 node_ptr root = repl_node->northeast;
830 repl_node->northeast.reset();
831 reinsert_tree(delete_node, quad_northeast, root);
833 root = repl_node->southwest;
834 repl_node->southwest.reset();
835 reinsert_tree(delete_node, quad_southwest, root);
839 throw general_error(
"quadrant for the replacement node is unspecified.");
843 delete_node->x = repl_node->x;
844 delete_node->y = repl_node->y;
845 delete_node->data = repl_node->data;
848 delete_node->parent = repl_node->parent;
849 repl_node->parent.reset();
854 delete_node->northeast = repl_node->northeast;
855 repl_node->northeast.reset();
858 delete_node->northwest = repl_node->northwest;
859 repl_node->northwest.reset();
862 delete_node->southeast = repl_node->southeast;
863 repl_node->southeast.reset();
866 delete_node->southwest = repl_node->southwest;
867 repl_node->southwest.reset();
870 throw general_error(
"quadrant for the replacement node is unspecified.");
875 typename reinsert_tree_array_type::iterator
876 itr = insert_list.begin(), itr_end = insert_list.end();
877 for (; itr != itr_end; ++itr)
878 reinsert_tree(delete_node, *itr);
881 template<
typename _Key,
typename _Value>
884 m_root.swap(r.m_root);
885 ::std::swap(m_xrange, r.m_xrange);
886 ::std::swap(m_yrange, r.m_yrange);
889 template<
typename _Key,
typename _Value>
895 template<
typename _Key,
typename _Value>
898 return (m_root.get() ==
nullptr);
901 template<
typename _Key,
typename _Value>
904 size_t node_count = 0;
905 count_all_nodes(m_root.get(), node_count);
909 template<
typename _Key,
typename _Value>
916 template<
typename _Key,
typename _Value>
919 m_xrange = key_range_type(0, 0);
920 m_yrange = key_range_type(0, 0);
926 template<
typename _Key,
typename _Value>
929 ::std::vector<node_data> v1, v2;
930 get_all_stored_data(v1);
931 r.get_all_stored_data(v2);
932 return equals(v1, v2);
935 template<
typename _Key,
typename _Value>
939 ofstream file(fpath.c_str());
940 file <<
"<svg width=\"60cm\" height=\"60cm\" viewBox=\"-2 -2 202 202\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">" << endl;
942 <<
" <marker id=\"Triangle\"" 943 <<
" viewBox=\"0 0 10 10\" refX=\"10\" refY=\"5\" " 944 <<
" markerUnits=\"strokeWidth\"" 945 <<
" markerWidth=\"9\" markerHeight=\"6\"" 946 <<
" orient=\"auto\">" 947 <<
" <path d=\"M 0 0 L 10 5 L 0 10 z\" />" 949 <<
"</defs>" << endl;
951 file <<
"<path d=\"M 0 0 L 0 " << m_yrange.second + 1 <<
"\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
952 file <<
"<path d=\"M 0 0 L " << m_xrange.second + 1 <<
" 0\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
953 dump_node_svg(m_root.get(), file);
954 file <<
"</svg>" << endl;
957 template<
typename _NodePtr>
958 void draw_svg_arrow(::std::ofstream& file,
const _NodePtr start,
const _NodePtr end)
961 file <<
"<g stroke=\"red\" marker-end=\"url(#Triangle)\">" << endl;
962 file <<
"<line x1=\"" << start->x <<
"\" y1=\"" << start->y <<
"\" x2=\"" 963 << end->x <<
"\" y2=\"" << end->y <<
"\" stroke-width=\"0.2\"/>" << endl;
964 file <<
"</g>" << endl;
967 template<
typename _Key,
typename _Value>
975 file <<
"<circle cx=\"" << p->x <<
"\" cy=\"" << p->y <<
"\" r=\"0.1\"" 976 <<
" fill=\"black\" stroke=\"black\"/>" << endl;
977 file <<
"<text x=\"" << p->x + 1 <<
"\" y=\"" << p->y + 2 <<
"\" font-size=\"1.2\" fill=\"black\">" 978 << *p->data <<
" (" << p->x <<
"," << p->y <<
")</text>" << endl;
981 draw_svg_arrow<const node*>(file, p, p->northwest.get());
984 draw_svg_arrow<const node*>(file, p, p->northeast.get());
987 draw_svg_arrow<const node*>(file, p, p->southwest.get());
990 draw_svg_arrow<const node*>(file, p, p->southeast.get());
992 dump_node_svg(p->northeast.get(), file);
993 dump_node_svg(p->northwest.get(), file);
994 dump_node_svg(p->southeast.get(), file);
995 dump_node_svg(p->southwest.get(), file);
998 template<
typename _Key,
typename _Value>
1001 using namespace std;
1003 if (v1.size() != v2.size())
1009 typename vector<node_data>::const_iterator
1010 itr1 = v1.begin(), itr1_end = v1.end(), itr2 = v2.begin(), itr2_end = v2.end();
1012 for (; itr1 != itr1_end; ++itr1, ++itr2)
1014 if (itr2 == itr2_end)
1020 if (itr2 != itr2_end)
1026 template<
typename _Key,
typename _Value>
1029 stored_data.
clear();
1033 get_all_stored_data(m_root.get(), stored_data);
1036 template<
typename _Key,
typename _Value>
1044 count_all_nodes(p->northeast.get(), node_count);
1045 count_all_nodes(p->northwest.get(), node_count);
1046 count_all_nodes(p->southeast.get(), node_count);
1047 count_all_nodes(p->southwest.get(), node_count);
1050 template<
typename _Key,
typename _Value>
1053 using namespace std;
1054 vector<node_data> all_data;
1055 r.get_all_stored_data(all_data);
1056 for_each(all_data.begin(), all_data.end(), data_inserter(*
this));
1059 template<
typename _Key,
typename _Value>
1062 ::std::vector<node_data> stored;
1063 get_all_stored_data(stored);
1064 return equals(stored, expected);
1067 template<
typename _Key,
typename _Value>
1070 return verify_node_iterator(nac, m_root.get());
1073 template<
typename _Key,
typename _Value>
1077 return (p ==
nullptr);
1082 if (!verify_node_iterator(nac.northeast(), p->northeast.get()))
1084 if (!verify_node_iterator(nac.northwest(), p->northwest.get()))
1086 if (!verify_node_iterator(nac.southeast(), p->southeast.get()))
1088 if (!verify_node_iterator(nac.southwest(), p->southwest.get()))
1094 template<
typename _Key,
typename _Value>
1100 stored_data.push_back(node_data(p->x, p->y, p->data));
1102 get_all_stored_data(p->northeast.get(), stored_data);
1103 get_all_stored_data(p->northwest.get(), stored_data);
1104 get_all_stored_data(p->southeast.get(), stored_data);
1105 get_all_stored_data(p->southwest.get(), stored_data);
1108 template<
typename _Key,
typename _Value>
1109 typename point_quad_tree<_Key,_Value>::node_ptr
1112 node_ptr cur_node = m_root;
1115 if (cur_node->x == x && cur_node->y == y)
1121 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1124 case quad_northeast:
1125 if (!cur_node->northeast)
1127 cur_node = cur_node->northeast;
1129 case quad_northwest:
1130 if (!cur_node->northwest)
1132 cur_node = cur_node->northwest;
1134 case quad_southeast:
1135 if (!cur_node->southeast)
1137 cur_node = cur_node->southeast;
1139 case quad_southwest:
1140 if (!cur_node->southwest)
1142 cur_node = cur_node->southwest;
1151 template<
typename _Key,
typename _Value>
1155 const node* cur_node = m_root.get();
1158 if (cur_node->x == x && cur_node->y == y)
1164 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1167 case quad_northeast:
1168 if (!cur_node->northeast)
1170 cur_node = cur_node->northeast.get();
1172 case quad_northwest:
1173 if (!cur_node->northwest)
1175 cur_node = cur_node->northwest.get();
1177 case quad_southeast:
1178 if (!cur_node->southeast)
1180 cur_node = cur_node->southeast.get();
1182 case quad_southwest:
1183 if (!cur_node->southwest)
1185 cur_node = cur_node->southwest.get();
1194 template<
typename _Key,
typename _Value>
1195 typename point_quad_tree<_Key,_Value>::node_ptr
1198 using namespace std;
1201 node_distance dx_node, dy_node, min_city_block_node;
1203 #if DEBUG_POINT_QUAD_TREE 1204 cout <<
"northeast" << endl;
1206 find_candidate_in_quad(
1207 x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northeast);
1209 #if DEBUG_POINT_QUAD_TREE 1210 cout <<
"northwest" << endl;
1212 find_candidate_in_quad(
1213 x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northwest);
1215 #if DEBUG_POINT_QUAD_TREE 1216 cout <<
"southwest" << endl;
1218 find_candidate_in_quad(
1219 x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southwest);
1221 #if DEBUG_POINT_QUAD_TREE 1222 cout <<
"southeast" << endl;
1224 find_candidate_in_quad(
1225 x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southeast);
1229 #if DEBUG_POINT_QUAD_TREE 1231 cout <<
"node closest to x axis: " << *dx_node.node->data <<
" (dx=" << dx_node.dist <<
")" << endl;
1234 cout <<
"node closest to y axis: " << *dy_node.node->data <<
" (dy=" << dy_node.dist <<
")" << endl;
1237 if (dx_node.node == dy_node.node && ((dx_node.quad == quad_northwest) || (dx_node.quad == quad_southeast)))
1239 #if DEBUG_POINT_QUAD_TREE 1240 cout <<
"node that satisfies Criterion 1: " << *dx_node.node->data << endl;
1242 return dx_node.node;
1246 #if DEBUG_POINT_QUAD_TREE 1247 cout <<
"unable to find node that satisfies Criterion 1." << endl;
1253 if (min_city_block_node.node)
1255 #if DEBUG_POINT_QUAD_TREE 1256 cout <<
"node that satisfies Criterion 2: " << *min_city_block_node.node->data <<
" (dist=" << min_city_block_node.dist <<
")" << endl;
1258 return min_city_block_node.node;
1264 template<
typename _Key,
typename _Value>
1266 key_type x, key_type y,
1267 node_distance& dx_node, node_distance& dy_node, node_distance& min_city_block_node,
1268 const node_ptr& delete_node, node_quadrant_t quad)
const 1270 using namespace std;
1272 node_ptr repl_node = delete_node->get_quadrant_node(quad);
1276 #if DEBUG_POINT_QUAD_TREE 1277 cout <<
" no candidate in this quadrant" << endl;
1282 node_quadrant_t oppo_quad = opposite(quad);
1283 while (repl_node->has_quadrant_node(oppo_quad))
1284 repl_node = repl_node->get_quadrant_node(oppo_quad);
1286 #if DEBUG_POINT_QUAD_TREE 1287 cout <<
" candidate: " << repl_node->x <<
"," << repl_node->y <<
" (" << *repl_node->data <<
")" << endl;
1291 key_type dx = repl_node->x > x ? repl_node->x - x : x - repl_node->x;
1292 key_type dy = repl_node->y > y ? repl_node->y - y : y - repl_node->y;
1293 #if DEBUG_POINT_QUAD_TREE 1294 cout <<
" dx = " << dx <<
", dy = " << dy << endl;
1297 if (!dx_node.node || dx_node.dist > dx)
1298 dx_node = node_distance(quad, dx, repl_node);
1299 if (!dy_node.node || dy_node.dist > dy)
1300 dy_node = node_distance(quad, dy, repl_node);
1302 if (!min_city_block_node.node || min_city_block_node.dist > (dx + dy))
1303 min_city_block_node = node_distance(quad_unspecified, dx+dy, repl_node);
1306 template<
typename _Key,
typename _Value>
1308 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange,
1309 node_ptr quad_root, direction_t dir, reinsert_tree_array_type& insert_list)
1311 using namespace std;
1316 #if DEBUG_POINT_QUAD_TREE 1317 cout <<
"adjust_quad: checking " << *quad_root->data <<
" (" << quad_root->x <<
"," << quad_root->y <<
")" << endl;
1320 if ((hatched_xrange.first <= quad_root->x && quad_root->x <= hatched_xrange.second) ||
1321 (hatched_yrange.first <= quad_root->y && quad_root->y <= hatched_yrange.second))
1323 #if DEBUG_POINT_QUAD_TREE 1324 cout <<
" " << *quad_root->data <<
" is in the hatched region" << endl;
1327 disconnect_node_from_parent(quad_root);
1328 quad_root->parent.reset();
1329 insert_list.push_back(quad_root);
1336 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northeast, dir_east, insert_list);
1337 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southeast, dir_east, insert_list);
1340 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northeast, dir_north, insert_list);
1341 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northwest, dir_north, insert_list);
1344 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southeast, dir_south, insert_list);
1345 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southwest, dir_south, insert_list);
1348 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northwest, dir_west, insert_list);
1349 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southwest, dir_west, insert_list);
1356 template<
typename _Key,
typename _Value>
1358 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange,
1359 node_ptr& quad_root, node_quadrant_t dir, reinsert_tree_array_type& insert_list)
1361 node_ptr cur_node = quad_root;
1366 case quad_northeast:
1367 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_east, insert_list);
1368 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_north, insert_list);
1370 case quad_northwest:
1371 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_north, insert_list);
1372 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_west, insert_list);
1374 case quad_southeast:
1375 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_east, insert_list);
1376 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_south, insert_list);
1378 case quad_southwest:
1379 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_west, insert_list);
1380 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_south, insert_list);
1385 cur_node = cur_node->get_quadrant_node(dir);
1389 template<
typename _Key,
typename _Value>
1392 node_ptr cur_node = dest;
1395 if (cur_node->x == this_node->x && cur_node->y == this_node->y)
1400 throw general_error(
"node with identical position encountered.");
1403 node_quadrant_t quad = cur_node->get_quadrant(this_node->x, this_node->y);
1406 case quad_northeast:
1407 if (cur_node->northeast)
1408 cur_node = cur_node->northeast;
1411 cur_node->northeast = this_node;
1412 this_node->parent = cur_node;
1416 case quad_northwest:
1417 if (cur_node->northwest)
1418 cur_node = cur_node->northwest;
1421 cur_node->northwest = this_node;
1422 this_node->parent = cur_node;
1426 case quad_southeast:
1427 if (cur_node->southeast)
1428 cur_node = cur_node->southeast;
1431 cur_node->southeast = this_node;
1432 this_node->parent = cur_node;
1436 case quad_southwest:
1437 if (cur_node->southwest)
1438 cur_node = cur_node->southwest;
1441 cur_node->southwest = this_node;
1442 this_node->parent = cur_node;
1450 assert(!
"This should never be reached.");
1453 template<
typename _Key,
typename _Value>
1462 if (root->northeast)
1464 reinsert_tree(dest, root->northeast);
1465 root->northeast.reset();
1467 if (root->northwest)
1469 reinsert_tree(dest, root->northwest);
1470 root->northwest.reset();
1472 if (root->southeast)
1474 reinsert_tree(dest, root->southeast);
1475 root->southeast.reset();
1477 if (root->southwest)
1479 reinsert_tree(dest, root->southwest);
1480 root->southwest.reset();
1483 root->parent.reset();
1484 insert_node(dest, root);
1487 template<
typename _Key,
typename _Value>
1496 case quad_northeast:
1497 if (dest->northeast)
1498 reinsert_tree(dest->northeast, root);
1501 dest->northeast = root;
1502 root->parent = dest;
1505 case quad_northwest:
1506 if (dest->northwest)
1507 reinsert_tree(dest->northwest, root);
1510 dest->northwest = root;
1511 root->parent = dest;
1514 case quad_southeast:
1515 if (dest->southeast)
1516 reinsert_tree(dest->southeast, root);
1519 dest->southeast = root;
1520 root->parent = dest;
1523 case quad_southwest:
1524 if (dest->southwest)
1525 reinsert_tree(dest->southwest, root);
1528 dest->southwest = root;
1529 root->parent = dest;
1537 template<
typename _Key,
typename _Value>
1540 ::mdds::disconnect_all_nodes(m_root);
value_type find(key_type x, key_type y) const
Definition: point_quad_tree.hpp:732
Definition: point_quad_tree.hpp:208
void remove(key_type x, key_type y)
Definition: point_quad_tree.hpp:741
Definition: point_quad_tree.hpp:159
void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type &result) const
Definition: point_quad_tree.hpp:710
void swap(point_quad_tree &r)
Definition: point_quad_tree.hpp:882
Definition: point_quad_tree.hpp:192
Definition: point_quad_tree.hpp:200
Definition: point_quad_tree.hpp:107
void insert(key_type x, key_type y, value_type data)
Definition: point_quad_tree.hpp:635
void clear()
Definition: point_quad_tree.hpp:890
node_access get_node_access() const
Definition: point_quad_tree.hpp:911
Definition: global.hpp:58
Definition: point_quad_tree.hpp:118
size_t size() const
Definition: point_quad_tree.hpp:902
Definition: flat_segment_tree.hpp:46
quad_node_base & operator=(const quad_node_base &r)
Definition: quad_node.hpp:182
Definition: point_quad_tree.hpp:506
bool empty() const
Definition: point_quad_tree.hpp:896
Definition: quad_node.hpp:118