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
139 return quad_node_base<node_ptr, node, key_type>::operator ==(r) && data == r.data;
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; }
189 point(key_type _x, key_type _y) : x(_x), y(_y) {}
190 point() : x(0), y(0) {}
195 friend class search_result_inserter;
197 typedef std::vector<const node*> res_nodes_type;
198 typedef std::shared_ptr<res_nodes_type> res_nodes_ptr;
205 typedef typename
point_quad_tree<_Key,_Value>::value_type parent_value_type;
209 typedef std::pair<point, parent_value_type> value_type;
210 typedef value_type* pointer;
211 typedef value_type& reference;
212 typedef ptrdiff_t difference_type;
213 typedef ::std::bidirectional_iterator_tag iterator_category;
215 const_iterator(res_nodes_ptr& ptr) : mp_res_nodes(ptr), m_end_pos(false) {}
218 mp_res_nodes(r.mp_res_nodes),
219 m_cur_pos(r.m_cur_pos),
220 m_cur_value(r.m_cur_value),
221 m_end_pos(r.m_end_pos) {}
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;
237 return mp_res_nodes.get() == r.mp_res_nodes.get() &&
238 m_cur_pos == r.m_cur_pos && m_end_pos == r.m_end_pos;
245 return m_end_pos == r.m_end_pos;
250 return !operator==(r);
253 const value_type& operator*()
const
258 const value_type* operator->()
const
260 return get_current_value();
263 const value_type* operator++()
270 typename res_nodes_type::const_iterator cur_pos = m_cur_pos;
271 if (++cur_pos == mp_res_nodes->end())
277 update_current_value();
281 const value_type* operator--()
286 return get_current_value();
289 update_current_value();
290 return get_current_value();
303 m_cur_pos = mp_res_nodes->begin();
305 update_current_value();
315 m_cur_pos = mp_res_nodes->end();
319 void update_current_value()
321 const node* p = *m_cur_pos;
322 m_cur_value.first =
point(p->x, p->y);
323 m_cur_value.second = p->data;
326 const value_type* get_current_value()
const
332 res_nodes_ptr mp_res_nodes;
333 typename res_nodes_type::const_iterator m_cur_pos;
334 value_type m_cur_value;
338 search_results() : mp_res_nodes(static_cast<res_nodes_type*>(nullptr)) {}
341 typename search_results::const_iterator begin()
343 typename search_results::const_iterator itr(mp_res_nodes);
348 typename search_results::const_iterator end()
350 typename search_results::const_iterator itr(mp_res_nodes);
356 void push_back(
const node* p)
359 mp_res_nodes.reset(
new res_nodes_type);
360 mp_res_nodes->push_back(p);
364 res_nodes_ptr mp_res_nodes;
368 point_quad_tree(
const point_quad_tree& r);
379 void insert(key_type x, key_type y, value_type data);
393 void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result)
const;
408 search_results
search_region(key_type x1, key_type y1, key_type x2, key_type y2)
const;
420 value_type
find(key_type x, key_type y)
const;
429 void remove(key_type x, key_type y);
436 void swap(point_quad_tree& r);
464 point_quad_tree& operator= (
const point_quad_tree& r);
466 bool operator== (
const point_quad_tree& r)
const;
468 bool operator!= (
const point_quad_tree& r)
const {
return !operator== (r); }
470 #ifdef MDDS_UNIT_TEST
484 node_data(key_type _x, key_type _y, value_type _data) :
485 x(_x), y(_y), data(_data) {}
486 node_data(
const node_data& r) :
487 x(r.x), y(r.y), data(r.data) {}
489 bool operator== (
const node_data& r)
const
491 return (x == r.x) && (y == r.y) && (data == r.data);
494 bool operator!= (
const node_data& r)
const
496 return !operator==(r);
501 bool operator() (
const node_data& left,
const node_data& right)
const
503 if (left.x != right.x)
504 return left.x < right.x;
505 if (left.y != right.y)
506 return left.y < right.y;
507 return left.data < right.data;
512 static bool equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2);
514 bool verify_data(::std::vector<node_data>& expected)
const;
516 bool verify_node_iterator(
const node_access& nac)
const;
517 static bool verify_node_iterator(
const node_access& nac,
const node* p);
519 void get_all_stored_data(::std::vector<node_data>& stored_data)
const;
521 void dump_tree_svg(const ::std::string& fpath)
const;
527 array_inserter(data_array_type& result) : m_result(result) {}
529 void operator() (
const node* p)
531 m_result.push_back(p->data);
534 data_array_type& m_result;
537 class search_result_inserter
540 search_result_inserter(search_results& result) : m_result(result) {}
542 void operator() (
const node* p)
544 m_result.push_back(p);
547 search_results& m_result;
553 data_inserter(point_quad_tree& db) : m_db(db) {}
555 void operator() (
const node_data& v)
557 m_db.insert(v.x, v.y, v.data);
560 point_quad_tree& m_db;
565 node_quadrant_t quad;
569 node_distance() : quad(quad_unspecified), dist(0), node(nullptr) {}
570 node_distance(node_quadrant_t _quad, key_type _dist,
const node_ptr& _node) :
571 quad(_quad), dist(_dist), node(_node) {}
574 node_ptr find_node(key_type x, key_type y)
const;
575 const node* find_node_ptr(key_type x, key_type y)
const;
576 node_ptr find_replacement_node(key_type x, key_type y,
const node_ptr& delete_node)
const;
578 void find_candidate_in_quad(key_type x, key_type y,
579 node_distance& dx_node, node_distance& dy_node, node_distance& min_city_block_node,
580 const node_ptr& delete_node, node_quadrant_t quad)
const;
582 void adjust_quad(
const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange,
583 node_ptr quad_root, direction_t dir, reinsert_tree_array_type& insert_list);
585 void set_new_root(
const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange,
586 node_ptr& quad_root, node_quadrant_t dir, reinsert_tree_array_type& insert_list);
588 void insert_node(node_ptr& dest, node_ptr& node);
589 void reinsert_tree(node_ptr& dest, node_ptr& root);
590 void reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root);
591 void clear_all_nodes();
592 void dump_node_svg(
const node* p, ::std::ofstream& file)
const;
593 void count_all_nodes(
const node* p,
size_t& node_count)
const;
594 void insert_data_from(
const point_quad_tree& r);
595 void get_all_stored_data(
const node* p, ::std::vector<node_data>& stored_data)
const;
600 key_range_type m_xrange;
601 key_range_type m_yrange;
604 template<
typename _Key,
typename _Value>
605 point_quad_tree<_Key,_Value>::point_quad_tree() :
612 template<
typename _Key,
typename _Value>
613 point_quad_tree<_Key,_Value>::point_quad_tree(
const point_quad_tree& r) :
621 template<
typename _Key,
typename _Value>
622 point_quad_tree<_Key,_Value>::~point_quad_tree()
627 template<
typename _Key,
typename _Value>
630 m_xrange.first = ::std::min(m_xrange.first, x);
631 m_xrange.second = ::std::max(m_xrange.second, x);
632 m_yrange.first = ::std::min(m_yrange.first, y);
633 m_yrange.second = ::std::max(m_yrange.second, y);
638 m_root.reset(
new node(x, y, data));
642 node_ptr cur_node = m_root;
645 if (cur_node->x == x && cur_node->y == y)
648 cur_node->data = data;
652 node_quadrant_t quad = cur_node->get_quadrant(x, y);
656 if (cur_node->northeast)
657 cur_node = cur_node->northeast;
660 cur_node->northeast.reset(
new node(x, y, data));
661 cur_node->northeast->parent = cur_node;
666 if (cur_node->northwest)
667 cur_node = cur_node->northwest;
670 cur_node->northwest.reset(
new node(x, y, data));
671 cur_node->northwest->parent = cur_node;
676 if (cur_node->southeast)
677 cur_node = cur_node->southeast;
680 cur_node->southeast.reset(
new node(x, y, data));
681 cur_node->southeast->parent = cur_node;
686 if (cur_node->southwest)
687 cur_node = cur_node->southwest;
690 cur_node->southwest.reset(
new node(x, y, data));
691 cur_node->southwest->parent = cur_node;
699 assert(!
"This should never be reached.");
702 template<
typename _Key,
typename _Value>
706 const node* p = m_root.get();
707 array_inserter _inserter(result);
708 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
711 template<
typename _Key,
typename _Value>
717 const node* p = m_root.get();
718 search_result_inserter _inserter(result);
719 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
723 template<
typename _Key,
typename _Value>
724 typename point_quad_tree<_Key,_Value>::value_type
727 const node* p = find_node_ptr(x, y);
733 template<
typename _Key,
typename _Value>
737 node_ptr delete_node = find_node(x, y);
742 #if DEBUG_POINT_QUAD_TREE
743 cout <<
"found the node to be removed at " << delete_node->x <<
"," << delete_node->y <<
" (" << *delete_node->data <<
")" << endl;
748 if (delete_node->leaf())
750 #if DEBUG_POINT_QUAD_TREE
751 cout <<
"deleting a leaf node." << endl;
753 if (delete_node.get() == m_root.get())
756 disconnect_node_from_parent(delete_node);
761 node_ptr repl_node = find_replacement_node(x, y, delete_node);
764 throw general_error(
"failed to find a replacement candidate node.");
766 node_quadrant_t repl_quad = delete_node->get_quadrant(repl_node->x, repl_node->y);
768 key_range_type xrange(delete_node->x, repl_node->x);
769 key_range_type yrange(delete_node->y, repl_node->y);
770 ensure_order(xrange);
771 ensure_order(yrange);
772 reinsert_tree_array_type insert_list;
780 adjust_quad(xrange, yrange, delete_node->northwest, dir_south, insert_list);
781 adjust_quad(xrange, yrange, delete_node->southeast, dir_west, insert_list);
782 set_new_root(xrange, yrange, delete_node->northeast, quad_southwest, insert_list);
785 adjust_quad(xrange, yrange, delete_node->northeast, dir_south, insert_list);
786 adjust_quad(xrange, yrange, delete_node->southwest, dir_east, insert_list);
787 set_new_root(xrange, yrange, delete_node->northwest, quad_southeast, insert_list);
790 adjust_quad(xrange, yrange, delete_node->northeast, dir_west, insert_list);
791 adjust_quad(xrange, yrange, delete_node->southwest, dir_north, insert_list);
792 set_new_root(xrange, yrange, delete_node->southeast, quad_northwest, insert_list);
795 adjust_quad(xrange, yrange, delete_node->northwest, dir_east, insert_list);
796 adjust_quad(xrange, yrange, delete_node->southeast, dir_north, insert_list);
797 set_new_root(xrange, yrange, delete_node->southwest, quad_northeast, insert_list);
800 throw general_error(
"quadrant for the replacement node is unspecified.");
810 node_ptr root = repl_node->northwest;
811 repl_node->northwest.reset();
812 reinsert_tree(delete_node, quad_northwest, root);
814 root = repl_node->southeast;
815 repl_node->southeast.reset();
816 reinsert_tree(delete_node, quad_southeast, root);
822 node_ptr root = repl_node->northeast;
823 repl_node->northeast.reset();
824 reinsert_tree(delete_node, quad_northeast, root);
826 root = repl_node->southwest;
827 repl_node->southwest.reset();
828 reinsert_tree(delete_node, quad_southwest, root);
832 throw general_error(
"quadrant for the replacement node is unspecified.");
836 delete_node->x = repl_node->x;
837 delete_node->y = repl_node->y;
838 delete_node->data = repl_node->data;
841 delete_node->parent = repl_node->parent;
842 repl_node->parent.reset();
847 delete_node->northeast = repl_node->northeast;
848 repl_node->northeast.reset();
851 delete_node->northwest = repl_node->northwest;
852 repl_node->northwest.reset();
855 delete_node->southeast = repl_node->southeast;
856 repl_node->southeast.reset();
859 delete_node->southwest = repl_node->southwest;
860 repl_node->southwest.reset();
863 throw general_error(
"quadrant for the replacement node is unspecified.");
868 typename reinsert_tree_array_type::iterator
869 itr = insert_list.begin(), itr_end = insert_list.end();
870 for (; itr != itr_end; ++itr)
871 reinsert_tree(delete_node, *itr);
874 template<
typename _Key,
typename _Value>
877 m_root.swap(r.m_root);
878 ::std::swap(m_xrange, r.m_xrange);
879 ::std::swap(m_yrange, r.m_yrange);
882 template<
typename _Key,
typename _Value>
888 template<
typename _Key,
typename _Value>
891 return (m_root.get() ==
nullptr);
894 template<
typename _Key,
typename _Value>
897 size_t node_count = 0;
898 count_all_nodes(m_root.get(), node_count);
902 template<
typename _Key,
typename _Value>
909 template<
typename _Key,
typename _Value>
912 m_xrange = key_range_type(0, 0);
913 m_yrange = key_range_type(0, 0);
919 template<
typename _Key,
typename _Value>
920 bool point_quad_tree<_Key,_Value>::operator== (
const point_quad_tree& r)
const
922 ::std::vector<node_data> v1, v2;
923 get_all_stored_data(v1);
924 r.get_all_stored_data(v2);
925 return equals(v1, v2);
928 template<
typename _Key,
typename _Value>
929 void point_quad_tree<_Key,_Value>::dump_tree_svg(const ::std::string& fpath)
const
932 ofstream file(fpath.c_str());
933 file <<
"<svg width=\"60cm\" height=\"60cm\" viewBox=\"-2 -2 202 202\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">" << endl;
935 <<
" <marker id=\"Triangle\""
936 <<
" viewBox=\"0 0 10 10\" refX=\"10\" refY=\"5\" "
937 <<
" markerUnits=\"strokeWidth\""
938 <<
" markerWidth=\"9\" markerHeight=\"6\""
939 <<
" orient=\"auto\">"
940 <<
" <path d=\"M 0 0 L 10 5 L 0 10 z\" />"
942 <<
"</defs>" << endl;
944 file <<
"<path d=\"M 0 0 L 0 " << m_yrange.second + 1 <<
"\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
945 file <<
"<path d=\"M 0 0 L " << m_xrange.second + 1 <<
" 0\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
946 dump_node_svg(m_root.get(), file);
947 file <<
"</svg>" << endl;
950 template<
typename _NodePtr>
951 void draw_svg_arrow(::std::ofstream& file,
const _NodePtr start,
const _NodePtr end)
954 file <<
"<g stroke=\"red\" marker-end=\"url(#Triangle)\">" << endl;
955 file <<
"<line x1=\"" << start->x <<
"\" y1=\"" << start->y <<
"\" x2=\""
956 << end->x <<
"\" y2=\"" << end->y <<
"\" stroke-width=\"0.2\"/>" << endl;
957 file <<
"</g>" << endl;
960 template<
typename _Key,
typename _Value>
961 void point_quad_tree<_Key,_Value>::dump_node_svg(
const node* p, ::std::ofstream& file)
const
968 file <<
"<circle cx=\"" << p->x <<
"\" cy=\"" << p->y <<
"\" r=\"0.1\""
969 <<
" fill=\"black\" stroke=\"black\"/>" << endl;
970 file <<
"<text x=\"" << p->x + 1 <<
"\" y=\"" << p->y + 2 <<
"\" font-size=\"1.2\" fill=\"black\">"
971 << *p->data <<
" (" << p->x <<
"," << p->y <<
")</text>" << endl;
974 draw_svg_arrow<const node*>(file, p, p->northwest.get());
977 draw_svg_arrow<const node*>(file, p, p->northeast.get());
980 draw_svg_arrow<const node*>(file, p, p->southwest.get());
983 draw_svg_arrow<const node*>(file, p, p->southeast.get());
985 dump_node_svg(p->northeast.get(), file);
986 dump_node_svg(p->northwest.get(), file);
987 dump_node_svg(p->southeast.get(), file);
988 dump_node_svg(p->southwest.get(), file);
991 template<
typename _Key,
typename _Value>
992 bool point_quad_tree<_Key,_Value>::equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2)
996 if (v1.size() != v2.size())
999 sort(v1.begin(), v1.end(),
typename node_data::sorter());
1000 sort(v2.begin(), v2.end(),
typename node_data::sorter());
1002 typename vector<node_data>::const_iterator
1003 itr1 = v1.begin(), itr1_end = v1.end(), itr2 = v2.begin(), itr2_end = v2.end();
1005 for (; itr1 != itr1_end; ++itr1, ++itr2)
1007 if (itr2 == itr2_end)
1013 if (itr2 != itr2_end)
1019 template<
typename _Key,
typename _Value>
1020 void point_quad_tree<_Key,_Value>::get_all_stored_data(::std::vector<node_data>& stored_data)
const
1022 stored_data.clear();
1026 get_all_stored_data(m_root.get(), stored_data);
1029 template<
typename _Key,
typename _Value>
1030 void point_quad_tree<_Key,_Value>::count_all_nodes(
const node* p,
size_t& node_count)
const
1037 count_all_nodes(p->northeast.get(), node_count);
1038 count_all_nodes(p->northwest.get(), node_count);
1039 count_all_nodes(p->southeast.get(), node_count);
1040 count_all_nodes(p->southwest.get(), node_count);
1043 template<
typename _Key,
typename _Value>
1044 void point_quad_tree<_Key,_Value>::insert_data_from(
const point_quad_tree& r)
1046 using namespace std;
1047 vector<node_data> all_data;
1048 r.get_all_stored_data(all_data);
1049 for_each(all_data.begin(), all_data.end(), data_inserter(*
this));
1052 template<
typename _Key,
typename _Value>
1053 bool point_quad_tree<_Key,_Value>::verify_data(::std::vector<node_data>& expected)
const
1055 ::std::vector<node_data> stored;
1056 get_all_stored_data(stored);
1057 return equals(stored, expected);
1060 template<
typename _Key,
typename _Value>
1061 bool point_quad_tree<_Key,_Value>::verify_node_iterator(
const node_access& nac)
const
1063 return verify_node_iterator(nac, m_root.get());
1066 template<
typename _Key,
typename _Value>
1067 bool point_quad_tree<_Key,_Value>::verify_node_iterator(
const node_access& nac,
const node* p)
1070 return (p ==
nullptr);
1075 if (!verify_node_iterator(nac.northeast(), p->northeast.get()))
1077 if (!verify_node_iterator(nac.northwest(), p->northwest.get()))
1079 if (!verify_node_iterator(nac.southeast(), p->southeast.get()))
1081 if (!verify_node_iterator(nac.southwest(), p->southwest.get()))
1087 template<
typename _Key,
typename _Value>
1088 void point_quad_tree<_Key,_Value>::get_all_stored_data(
const node* p, ::std::vector<node_data>& stored_data)
const
1093 stored_data.push_back(node_data(p->x, p->y, p->data));
1095 get_all_stored_data(p->northeast.get(), stored_data);
1096 get_all_stored_data(p->northwest.get(), stored_data);
1097 get_all_stored_data(p->southeast.get(), stored_data);
1098 get_all_stored_data(p->southwest.get(), stored_data);
1101 template<
typename _Key,
typename _Value>
1102 typename point_quad_tree<_Key,_Value>::node_ptr
1103 point_quad_tree<_Key,_Value>::find_node(key_type x, key_type y)
const
1105 node_ptr cur_node = m_root;
1108 if (cur_node->x == x && cur_node->y == y)
1114 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1117 case quad_northeast:
1118 if (!cur_node->northeast)
1120 cur_node = cur_node->northeast;
1122 case quad_northwest:
1123 if (!cur_node->northwest)
1125 cur_node = cur_node->northwest;
1127 case quad_southeast:
1128 if (!cur_node->southeast)
1130 cur_node = cur_node->southeast;
1132 case quad_southwest:
1133 if (!cur_node->southwest)
1135 cur_node = cur_node->southwest;
1138 throw general_error(
"unknown quadrant");
1144 template<
typename _Key,
typename _Value>
1145 const typename point_quad_tree<_Key,_Value>::node*
1146 point_quad_tree<_Key,_Value>::find_node_ptr(key_type x, key_type y)
const
1148 const node* cur_node = m_root.get();
1151 if (cur_node->x == x && cur_node->y == y)
1157 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1160 case quad_northeast:
1161 if (!cur_node->northeast)
1163 cur_node = cur_node->northeast.get();
1165 case quad_northwest:
1166 if (!cur_node->northwest)
1168 cur_node = cur_node->northwest.get();
1170 case quad_southeast:
1171 if (!cur_node->southeast)
1173 cur_node = cur_node->southeast.get();
1175 case quad_southwest:
1176 if (!cur_node->southwest)
1178 cur_node = cur_node->southwest.get();
1181 throw general_error(
"unknown quadrant");
1187 template<
typename _Key,
typename _Value>
1188 typename point_quad_tree<_Key,_Value>::node_ptr
1189 point_quad_tree<_Key,_Value>::find_replacement_node(key_type x, key_type y,
const node_ptr& delete_node)
const
1191 using namespace std;
1194 node_distance dx_node, dy_node, min_city_block_node;
1196 #if DEBUG_POINT_QUAD_TREE
1197 cout <<
"northeast" << endl;
1199 find_candidate_in_quad(
1200 x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northeast);
1202 #if DEBUG_POINT_QUAD_TREE
1203 cout <<
"northwest" << endl;
1205 find_candidate_in_quad(
1206 x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northwest);
1208 #if DEBUG_POINT_QUAD_TREE
1209 cout <<
"southwest" << endl;
1211 find_candidate_in_quad(
1212 x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southwest);
1214 #if DEBUG_POINT_QUAD_TREE
1215 cout <<
"southeast" << endl;
1217 find_candidate_in_quad(
1218 x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southeast);
1222 #if DEBUG_POINT_QUAD_TREE
1224 cout <<
"node closest to x axis: " << *dx_node.node->data <<
" (dx=" << dx_node.dist <<
")" << endl;
1227 cout <<
"node closest to y axis: " << *dy_node.node->data <<
" (dy=" << dy_node.dist <<
")" << endl;
1230 if (dx_node.node == dy_node.node && ((dx_node.quad == quad_northwest) || (dx_node.quad == quad_southeast)))
1232 #if DEBUG_POINT_QUAD_TREE
1233 cout <<
"node that satisfies Criterion 1: " << *dx_node.node->data << endl;
1235 return dx_node.node;
1239 #if DEBUG_POINT_QUAD_TREE
1240 cout <<
"unable to find node that satisfies Criterion 1." << endl;
1246 if (min_city_block_node.node)
1248 #if DEBUG_POINT_QUAD_TREE
1249 cout <<
"node that satisfies Criterion 2: " << *min_city_block_node.node->data <<
" (dist=" << min_city_block_node.dist <<
")" << endl;
1251 return min_city_block_node.node;
1257 template<
typename _Key,
typename _Value>
1258 void point_quad_tree<_Key,_Value>::find_candidate_in_quad(
1259 key_type x, key_type y,
1260 node_distance& dx_node, node_distance& dy_node, node_distance& min_city_block_node,
1261 const node_ptr& delete_node, node_quadrant_t quad)
const
1263 using namespace std;
1265 node_ptr repl_node = delete_node->get_quadrant_node(quad);
1269 #if DEBUG_POINT_QUAD_TREE
1270 cout <<
" no candidate in this quadrant" << endl;
1275 node_quadrant_t oppo_quad = opposite(quad);
1276 while (repl_node->has_quadrant_node(oppo_quad))
1277 repl_node = repl_node->get_quadrant_node(oppo_quad);
1279 #if DEBUG_POINT_QUAD_TREE
1280 cout <<
" candidate: " << repl_node->x <<
"," << repl_node->y <<
" (" << *repl_node->data <<
")" << endl;
1284 key_type dx = repl_node->x > x ? repl_node->x - x : x - repl_node->x;
1285 key_type dy = repl_node->y > y ? repl_node->y - y : y - repl_node->y;
1286 #if DEBUG_POINT_QUAD_TREE
1287 cout <<
" dx = " << dx <<
", dy = " << dy << endl;
1290 if (!dx_node.node || dx_node.dist > dx)
1291 dx_node = node_distance(quad, dx, repl_node);
1292 if (!dy_node.node || dy_node.dist > dy)
1293 dy_node = node_distance(quad, dy, repl_node);
1295 if (!min_city_block_node.node || min_city_block_node.dist > (dx + dy))
1296 min_city_block_node = node_distance(quad_unspecified, dx+dy, repl_node);
1299 template<
typename _Key,
typename _Value>
1300 void point_quad_tree<_Key,_Value>::adjust_quad(
1301 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange,
1302 node_ptr quad_root, direction_t dir, reinsert_tree_array_type& insert_list)
1304 using namespace std;
1309 #if DEBUG_POINT_QUAD_TREE
1310 cout <<
"adjust_quad: checking " << *quad_root->data <<
" (" << quad_root->x <<
"," << quad_root->y <<
")" << endl;
1313 if ((hatched_xrange.first <= quad_root->x && quad_root->x <= hatched_xrange.second) ||
1314 (hatched_yrange.first <= quad_root->y && quad_root->y <= hatched_yrange.second))
1316 #if DEBUG_POINT_QUAD_TREE
1317 cout <<
" " << *quad_root->data <<
" is in the hatched region" << endl;
1320 disconnect_node_from_parent(quad_root);
1321 quad_root->parent.reset();
1322 insert_list.push_back(quad_root);
1329 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northeast, dir_east, insert_list);
1330 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southeast, dir_east, insert_list);
1333 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northeast, dir_north, insert_list);
1334 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northwest, dir_north, insert_list);
1337 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southeast, dir_south, insert_list);
1338 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southwest, dir_south, insert_list);
1341 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northwest, dir_west, insert_list);
1342 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southwest, dir_west, insert_list);
1349 template<
typename _Key,
typename _Value>
1350 void point_quad_tree<_Key,_Value>::set_new_root(
1351 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange,
1352 node_ptr& quad_root, node_quadrant_t dir, reinsert_tree_array_type& insert_list)
1354 node_ptr cur_node = quad_root;
1359 case quad_northeast:
1360 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_east, insert_list);
1361 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_north, insert_list);
1363 case quad_northwest:
1364 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_north, insert_list);
1365 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_west, insert_list);
1367 case quad_southeast:
1368 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_east, insert_list);
1369 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_south, insert_list);
1371 case quad_southwest:
1372 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_west, insert_list);
1373 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_south, insert_list);
1376 throw general_error(
"unspecified quadrant");
1378 cur_node = cur_node->get_quadrant_node(dir);
1382 template<
typename _Key,
typename _Value>
1383 void point_quad_tree<_Key,_Value>::insert_node(node_ptr& dest, node_ptr& this_node)
1385 node_ptr cur_node = dest;
1388 if (cur_node->x == this_node->x && cur_node->y == this_node->y)
1393 throw general_error(
"node with identical position encountered.");
1396 node_quadrant_t quad = cur_node->get_quadrant(this_node->x, this_node->y);
1399 case quad_northeast:
1400 if (cur_node->northeast)
1401 cur_node = cur_node->northeast;
1404 cur_node->northeast = this_node;
1405 this_node->parent = cur_node;
1409 case quad_northwest:
1410 if (cur_node->northwest)
1411 cur_node = cur_node->northwest;
1414 cur_node->northwest = this_node;
1415 this_node->parent = cur_node;
1419 case quad_southeast:
1420 if (cur_node->southeast)
1421 cur_node = cur_node->southeast;
1424 cur_node->southeast = this_node;
1425 this_node->parent = cur_node;
1429 case quad_southwest:
1430 if (cur_node->southwest)
1431 cur_node = cur_node->southwest;
1434 cur_node->southwest = this_node;
1435 this_node->parent = cur_node;
1440 throw general_error(
"unknown quadrant");
1443 assert(!
"This should never be reached.");
1446 template<
typename _Key,
typename _Value>
1447 void point_quad_tree<_Key,_Value>::reinsert_tree(node_ptr& dest, node_ptr& root)
1455 if (root->northeast)
1457 reinsert_tree(dest, root->northeast);
1458 root->northeast.reset();
1460 if (root->northwest)
1462 reinsert_tree(dest, root->northwest);
1463 root->northwest.reset();
1465 if (root->southeast)
1467 reinsert_tree(dest, root->southeast);
1468 root->southeast.reset();
1470 if (root->southwest)
1472 reinsert_tree(dest, root->southwest);
1473 root->southwest.reset();
1476 root->parent.reset();
1477 insert_node(dest, root);
1480 template<
typename _Key,
typename _Value>
1481 void point_quad_tree<_Key,_Value>::reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root)
1489 case quad_northeast:
1490 if (dest->northeast)
1491 reinsert_tree(dest->northeast, root);
1494 dest->northeast = root;
1495 root->parent = dest;
1498 case quad_northwest:
1499 if (dest->northwest)
1500 reinsert_tree(dest->northwest, root);
1503 dest->northwest = root;
1504 root->parent = dest;
1507 case quad_southeast:
1508 if (dest->southeast)
1509 reinsert_tree(dest->southeast, root);
1512 dest->southeast = root;
1513 root->parent = dest;
1516 case quad_southwest:
1517 if (dest->southwest)
1518 reinsert_tree(dest->southwest, root);
1521 dest->southwest = root;
1522 root->parent = dest;
1526 throw general_error(
"reinsert_tree: quadrant unspecified");
1530 template<
typename _Key,
typename _Value>
1531 void point_quad_tree<_Key,_Value>::clear_all_nodes()
1533 ::mdds::disconnect_all_nodes(m_root);
Definition: global.hpp:82
Definition: point_quad_tree.hpp:118
Definition: point_quad_tree.hpp:160
Definition: point_quad_tree.hpp:202
Definition: point_quad_tree.hpp:194
Definition: point_quad_tree.hpp:108
void insert(key_type x, key_type y, value_type data)
Definition: point_quad_tree.hpp:628
void swap(point_quad_tree &r)
Definition: point_quad_tree.hpp:875
bool empty() const
Definition: point_quad_tree.hpp:889
size_t size() const
Definition: point_quad_tree.hpp:895
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:703
void clear()
Definition: point_quad_tree.hpp:883
void remove(key_type x, key_type y)
Definition: point_quad_tree.hpp:734
node_access get_node_access() const
Definition: point_quad_tree.hpp:904
value_type find(key_type x, key_type y) const
Definition: point_quad_tree.hpp:725
Definition: point_quad_tree.hpp:500
Definition: point_quad_tree.hpp:186
Definition: quad_node.hpp:119
quad_node_base & operator=(const quad_node_base &r)
Definition: quad_node.hpp:182