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
45template<
typename _PairType>
46void ensure_order(_PairType& v)
48 if (v.first > v.second)
49 ::std::swap(v.first, v.second);
52template<
typename _Key,
typename _NodeType,
typename _Inserter>
53void search_region_node(
const _NodeType* p, _Key x1, _Key y1, _Key x2, _Key y2, _Inserter& result)
60 search_region_space_t region = ::mdds::get_search_region_space(p, x1, y1, x2, y2);
66 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
67 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
68 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
69 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
72 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
73 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
76 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
77 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
79 case region_northeast:
80 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
82 case region_northwest:
83 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
86 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
87 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
89 case region_southeast:
90 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
92 case region_southwest:
93 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
96 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
97 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
100 throw general_error(
"unknown search region");
104template<
typename _Key,
typename _Value>
108 class search_result_inserter;
111 typedef _Key key_type;
112 typedef _Value value_type;
113 typedef size_t size_type;
114 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) :
quad_node_base<node_ptr, node, key_type>(_x, _y), data(_data)
130 node(
const node& r) :
quad_node_base<node_ptr, node, key_type>(r), data(r.data)
136 bool operator==(
const node& r)
const
138 return quad_node_base<node_ptr, node, key_type>::operator==(r) && data == r.data;
149 typedef ::std::vector<node_ptr> reinsert_tree_array_type;
150 typedef ::std::pair<key_type, key_type> key_range_type;
179 value_type data()
const
192 operator bool()
const
194 return mp !=
nullptr;
218 point(key_type _x, key_type _y) : x(_x), y(_y)
226 friend class search_result_inserter;
228 typedef std::vector<const node*> res_nodes_type;
229 typedef std::shared_ptr<res_nodes_type> res_nodes_ptr;
236 typedef typename
point_quad_tree<_Key, _Value>::value_type parent_value_type;
240 typedef std::pair<point, parent_value_type> value_type;
241 typedef value_type* pointer;
242 typedef value_type& reference;
243 typedef ptrdiff_t difference_type;
244 typedef ::std::bidirectional_iterator_tag iterator_category;
246 const_iterator(res_nodes_ptr& ptr) : mp_res_nodes(ptr), m_end_pos(false)
250 : mp_res_nodes(r.mp_res_nodes), m_cur_pos(r.m_cur_pos), m_cur_value(r.m_cur_value),
251 m_end_pos(r.m_end_pos)
256 mp_res_nodes = r.mp_res_nodes;
257 m_cur_pos = r.m_cur_pos;
258 m_cur_value = r.m_cur_value;
259 m_end_pos = r.m_end_pos;
268 return mp_res_nodes.get() == r.mp_res_nodes.get() && m_cur_pos == r.m_cur_pos &&
269 m_end_pos == r.m_end_pos;
276 return m_end_pos == r.m_end_pos;
281 return !operator==(r);
284 const value_type& operator*()
const
289 const value_type* operator->()
const
291 return get_current_value();
294 const value_type* operator++()
301 typename res_nodes_type::const_iterator cur_pos = m_cur_pos;
302 if (++cur_pos == mp_res_nodes->end())
308 update_current_value();
312 const value_type* operator--()
317 return get_current_value();
320 update_current_value();
321 return get_current_value();
334 m_cur_pos = mp_res_nodes->begin();
336 update_current_value();
346 m_cur_pos = mp_res_nodes->end();
350 void update_current_value()
352 const node* p = *m_cur_pos;
353 m_cur_value.first =
point(p->x, p->y);
354 m_cur_value.second = p->data;
357 const value_type* get_current_value()
const
363 res_nodes_ptr mp_res_nodes;
364 typename res_nodes_type::const_iterator m_cur_pos;
365 value_type m_cur_value;
369 search_results() : mp_res_nodes(static_cast<res_nodes_type*>(nullptr))
374 typename search_results::const_iterator begin()
376 typename search_results::const_iterator itr(mp_res_nodes);
381 typename search_results::const_iterator end()
383 typename search_results::const_iterator itr(mp_res_nodes);
389 void push_back(
const node* p)
392 mp_res_nodes.reset(
new res_nodes_type);
393 mp_res_nodes->push_back(p);
397 res_nodes_ptr mp_res_nodes;
401 point_quad_tree(
const point_quad_tree& r);
412 void insert(key_type x, key_type y, value_type data);
426 void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result)
const;
441 search_results
search_region(key_type x1, key_type y1, key_type x2, key_type y2)
const;
453 value_type
find(key_type x, key_type y)
const;
462 void remove(key_type x, key_type y);
469 void swap(point_quad_tree& r);
497 point_quad_tree& operator=(
const point_quad_tree& r);
499 bool operator==(
const point_quad_tree& r)
const;
501 bool operator!=(
const point_quad_tree& r)
const
503 return !operator==(r);
520 node_data(key_type _x, key_type _y, value_type _data) : x(_x), y(_y), data(_data)
522 node_data(
const node_data& r) : x(r.x), y(r.y), data(r.data)
525 bool operator==(
const node_data& r)
const
527 return (x == r.x) && (y == r.y) && (data == r.data);
530 bool operator!=(
const node_data& r)
const
532 return !operator==(r);
537 bool operator()(
const node_data& left,
const node_data& right)
const
539 if (left.x != right.x)
540 return left.x < right.x;
541 if (left.y != right.y)
542 return left.y < right.y;
543 return left.data < right.data;
548 static bool equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2);
550 bool verify_data(::std::vector<node_data>& expected)
const;
552 bool verify_node_iterator(
const node_access& nac)
const;
553 static bool verify_node_iterator(
const node_access& nac,
const node* p);
555 void get_all_stored_data(::std::vector<node_data>& stored_data)
const;
557 void dump_tree_svg(const ::std::string& fpath)
const;
563 array_inserter(data_array_type& result) : m_result(result)
566 void operator()(
const node* p)
568 m_result.push_back(p->data);
572 data_array_type& m_result;
575 class search_result_inserter
578 search_result_inserter(search_results& result) : m_result(result)
581 void operator()(
const node* p)
583 m_result.push_back(p);
587 search_results& m_result;
593 data_inserter(point_quad_tree& db) : m_db(db)
596 void operator()(
const node_data& v)
598 m_db.insert(v.x, v.y, v.data);
602 point_quad_tree& m_db;
607 node_quadrant_t quad;
611 node_distance() : quad(quad_unspecified), dist(0), node(nullptr)
613 node_distance(node_quadrant_t _quad, key_type _dist,
const node_ptr& _node)
614 : quad(_quad), dist(_dist), node(_node)
618 node_ptr find_node(key_type x, key_type y)
const;
619 const node* find_node_ptr(key_type x, key_type y)
const;
620 node_ptr find_replacement_node(key_type x, key_type y,
const node_ptr& delete_node)
const;
622 void find_candidate_in_quad(
623 key_type x, key_type y, node_distance& dx_node, node_distance& dy_node, node_distance& min_city_block_node,
624 const node_ptr& delete_node, node_quadrant_t quad)
const;
627 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange, node_ptr quad_root, direction_t dir,
628 reinsert_tree_array_type& insert_list);
631 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange, node_ptr& quad_root,
632 node_quadrant_t dir, reinsert_tree_array_type& insert_list);
634 void insert_node(node_ptr& dest, node_ptr& node);
635 void reinsert_tree(node_ptr& dest, node_ptr& root);
636 void reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root);
637 void clear_all_nodes();
638 void dump_node_svg(
const node* p, ::std::ofstream& file)
const;
639 void count_all_nodes(
const node* p,
size_t& node_count)
const;
640 void insert_data_from(
const point_quad_tree& r);
641 void get_all_stored_data(
const node* p, ::std::vector<node_data>& stored_data)
const;
646 key_range_type m_xrange;
647 key_range_type m_yrange;
650template<
typename _Key,
typename _Value>
651point_quad_tree<_Key, _Value>::point_quad_tree() : m_root(nullptr), m_xrange(0, 0), m_yrange(0, 0)
654template<
typename _Key,
typename _Value>
655point_quad_tree<_Key, _Value>::point_quad_tree(
const point_quad_tree& r)
656 : m_root(nullptr), m_xrange(0, 0), m_yrange(0, 0)
661template<
typename _Key,
typename _Value>
662point_quad_tree<_Key, _Value>::~point_quad_tree()
667template<
typename _Key,
typename _Value>
670 m_xrange.first = ::std::min(m_xrange.first, x);
671 m_xrange.second = ::std::max(m_xrange.second, x);
672 m_yrange.first = ::std::min(m_yrange.first, y);
673 m_yrange.second = ::std::max(m_yrange.second, y);
678 m_root.reset(
new node(x, y, data));
682 node_ptr cur_node = m_root;
685 if (cur_node->x == x && cur_node->y == y)
688 cur_node->data = data;
692 node_quadrant_t quad = cur_node->get_quadrant(x, y);
696 if (cur_node->northeast)
697 cur_node = cur_node->northeast;
700 cur_node->northeast.reset(
new node(x, y, data));
701 cur_node->northeast->parent = cur_node;
706 if (cur_node->northwest)
707 cur_node = cur_node->northwest;
710 cur_node->northwest.reset(
new node(x, y, data));
711 cur_node->northwest->parent = cur_node;
716 if (cur_node->southeast)
717 cur_node = cur_node->southeast;
720 cur_node->southeast.reset(
new node(x, y, data));
721 cur_node->southeast->parent = cur_node;
726 if (cur_node->southwest)
727 cur_node = cur_node->southwest;
730 cur_node->southwest.reset(
new node(x, y, data));
731 cur_node->southwest->parent = cur_node;
739 assert(!
"This should never be reached.");
742template<
typename _Key,
typename _Value>
744 key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result)
const
747 const node* p = m_root.get();
748 array_inserter _inserter(result);
749 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
752template<
typename _Key,
typename _Value>
754 key_type x1, key_type y1, key_type x2, key_type y2)
const
758 const node* p = m_root.get();
759 search_result_inserter _inserter(result);
760 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
764template<
typename _Key,
typename _Value>
767 const node* p = find_node_ptr(x, y);
773template<
typename _Key,
typename _Value>
777 node_ptr delete_node = find_node(x, y);
782#if DEBUG_POINT_QUAD_TREE
783 cout <<
"found the node to be removed at " << delete_node->x <<
"," << delete_node->y <<
" (" << *delete_node->data
789 if (delete_node->leaf())
791#if DEBUG_POINT_QUAD_TREE
792 cout <<
"deleting a leaf node." << endl;
794 if (delete_node.get() == m_root.get())
797 disconnect_node_from_parent(delete_node);
802 node_ptr repl_node = find_replacement_node(x, y, delete_node);
805 throw general_error(
"failed to find a replacement candidate node.");
807 node_quadrant_t repl_quad = delete_node->get_quadrant(repl_node->x, repl_node->y);
809 key_range_type xrange(delete_node->x, repl_node->x);
810 key_range_type yrange(delete_node->y, repl_node->y);
811 ensure_order(xrange);
812 ensure_order(yrange);
813 reinsert_tree_array_type insert_list;
821 adjust_quad(xrange, yrange, delete_node->northwest, dir_south, insert_list);
822 adjust_quad(xrange, yrange, delete_node->southeast, dir_west, insert_list);
823 set_new_root(xrange, yrange, delete_node->northeast, quad_southwest, insert_list);
826 adjust_quad(xrange, yrange, delete_node->northeast, dir_south, insert_list);
827 adjust_quad(xrange, yrange, delete_node->southwest, dir_east, insert_list);
828 set_new_root(xrange, yrange, delete_node->northwest, quad_southeast, insert_list);
831 adjust_quad(xrange, yrange, delete_node->northeast, dir_west, insert_list);
832 adjust_quad(xrange, yrange, delete_node->southwest, dir_north, insert_list);
833 set_new_root(xrange, yrange, delete_node->southeast, quad_northwest, insert_list);
836 adjust_quad(xrange, yrange, delete_node->northwest, dir_east, insert_list);
837 adjust_quad(xrange, yrange, delete_node->southeast, dir_north, insert_list);
838 set_new_root(xrange, yrange, delete_node->southwest, quad_northeast, insert_list);
841 throw general_error(
"quadrant for the replacement node is unspecified.");
851 node_ptr root = repl_node->northwest;
852 repl_node->northwest.reset();
853 reinsert_tree(delete_node, quad_northwest, root);
855 root = repl_node->southeast;
856 repl_node->southeast.reset();
857 reinsert_tree(delete_node, quad_southeast, root);
863 node_ptr root = repl_node->northeast;
864 repl_node->northeast.reset();
865 reinsert_tree(delete_node, quad_northeast, root);
867 root = repl_node->southwest;
868 repl_node->southwest.reset();
869 reinsert_tree(delete_node, quad_southwest, root);
873 throw general_error(
"quadrant for the replacement node is unspecified.");
877 delete_node->x = repl_node->x;
878 delete_node->y = repl_node->y;
879 delete_node->data = repl_node->data;
882 delete_node->parent = repl_node->parent;
883 repl_node->parent.reset();
888 delete_node->northeast = repl_node->northeast;
889 repl_node->northeast.reset();
892 delete_node->northwest = repl_node->northwest;
893 repl_node->northwest.reset();
896 delete_node->southeast = repl_node->southeast;
897 repl_node->southeast.reset();
900 delete_node->southwest = repl_node->southwest;
901 repl_node->southwest.reset();
904 throw general_error(
"quadrant for the replacement node is unspecified.");
909 typename reinsert_tree_array_type::iterator itr = insert_list.begin(), itr_end = insert_list.end();
910 for (; itr != itr_end; ++itr)
911 reinsert_tree(delete_node, *itr);
914template<
typename _Key,
typename _Value>
917 m_root.swap(r.m_root);
918 ::std::swap(m_xrange, r.m_xrange);
919 ::std::swap(m_yrange, r.m_yrange);
922template<
typename _Key,
typename _Value>
928template<
typename _Key,
typename _Value>
931 return (m_root.get() ==
nullptr);
934template<
typename _Key,
typename _Value>
937 size_t node_count = 0;
938 count_all_nodes(m_root.get(), node_count);
942template<
typename _Key,
typename _Value>
948template<
typename _Key,
typename _Value>
951 m_xrange = key_range_type(0, 0);
952 m_yrange = key_range_type(0, 0);
958template<
typename _Key,
typename _Value>
959bool point_quad_tree<_Key, _Value>::operator==(
const point_quad_tree& r)
const
961 ::std::vector<node_data> v1, v2;
962 get_all_stored_data(v1);
963 r.get_all_stored_data(v2);
964 return equals(v1, v2);
967template<
typename _Key,
typename _Value>
968void point_quad_tree<_Key, _Value>::dump_tree_svg(const ::std::string& fpath)
const
971 ofstream file(fpath.c_str());
972 file <<
"<svg width=\"60cm\" height=\"60cm\" viewBox=\"-2 -2 202 202\" xmlns=\"http://www.w3.org/2000/svg\" "
976 <<
" <marker id=\"Triangle\""
977 <<
" viewBox=\"0 0 10 10\" refX=\"10\" refY=\"5\" "
978 <<
" markerUnits=\"strokeWidth\""
979 <<
" markerWidth=\"9\" markerHeight=\"6\""
980 <<
" orient=\"auto\">"
981 <<
" <path d=\"M 0 0 L 10 5 L 0 10 z\" />"
983 <<
"</defs>" << endl;
985 file <<
"<path d=\"M 0 0 L 0 " << m_yrange.second + 1
986 <<
"\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
987 file <<
"<path d=\"M 0 0 L " << m_xrange.second + 1
988 <<
" 0\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
989 dump_node_svg(m_root.get(), file);
990 file <<
"</svg>" << endl;
993template<
typename _NodePtr>
994void draw_svg_arrow(::std::ofstream& file,
const _NodePtr start,
const _NodePtr end)
997 file <<
"<g stroke=\"red\" marker-end=\"url(#Triangle)\">" << endl;
998 file <<
"<line x1=\"" << start->x <<
"\" y1=\"" << start->y <<
"\" x2=\"" << end->x <<
"\" y2=\"" << end->y
999 <<
"\" stroke-width=\"0.2\"/>" << endl;
1000 file <<
"</g>" << endl;
1003template<
typename _Key,
typename _Value>
1004void point_quad_tree<_Key, _Value>::dump_node_svg(
const node* p, ::std::ofstream& file)
const
1006 using namespace std;
1011 file <<
"<circle cx=\"" << p->x <<
"\" cy=\"" << p->y <<
"\" r=\"0.1\""
1012 <<
" fill=\"black\" stroke=\"black\"/>" << endl;
1013 file <<
"<text x=\"" << p->x + 1 <<
"\" y=\"" << p->y + 2 <<
"\" font-size=\"1.2\" fill=\"black\">" << *p->data
1014 <<
" (" << p->x <<
"," << p->y <<
")</text>" << endl;
1017 draw_svg_arrow<const node*>(file, p, p->northwest.get());
1020 draw_svg_arrow<const node*>(file, p, p->northeast.get());
1023 draw_svg_arrow<const node*>(file, p, p->southwest.get());
1026 draw_svg_arrow<const node*>(file, p, p->southeast.get());
1028 dump_node_svg(p->northeast.get(), file);
1029 dump_node_svg(p->northwest.get(), file);
1030 dump_node_svg(p->southeast.get(), file);
1031 dump_node_svg(p->southwest.get(), file);
1034template<
typename _Key,
typename _Value>
1035bool point_quad_tree<_Key, _Value>::equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2)
1037 using namespace std;
1039 if (v1.size() != v2.size())
1042 sort(v1.begin(), v1.end(),
typename node_data::sorter());
1043 sort(v2.begin(), v2.end(),
typename node_data::sorter());
1045 typename vector<node_data>::const_iterator itr1 = v1.begin(), itr1_end = v1.end(), itr2 = v2.begin(),
1046 itr2_end = v2.end();
1048 for (; itr1 != itr1_end; ++itr1, ++itr2)
1050 if (itr2 == itr2_end)
1056 if (itr2 != itr2_end)
1062template<
typename _Key,
typename _Value>
1063void point_quad_tree<_Key, _Value>::get_all_stored_data(::std::vector<node_data>& stored_data)
const
1065 stored_data.clear();
1069 get_all_stored_data(m_root.get(), stored_data);
1072template<
typename _Key,
typename _Value>
1073void point_quad_tree<_Key, _Value>::count_all_nodes(
const node* p,
size_t& node_count)
const
1080 count_all_nodes(p->northeast.get(), node_count);
1081 count_all_nodes(p->northwest.get(), node_count);
1082 count_all_nodes(p->southeast.get(), node_count);
1083 count_all_nodes(p->southwest.get(), node_count);
1086template<
typename _Key,
typename _Value>
1087void point_quad_tree<_Key, _Value>::insert_data_from(
const point_quad_tree& r)
1089 using namespace std;
1090 vector<node_data> all_data;
1091 r.get_all_stored_data(all_data);
1092 for_each(all_data.begin(), all_data.end(), data_inserter(*
this));
1095template<
typename _Key,
typename _Value>
1096bool point_quad_tree<_Key, _Value>::verify_data(::std::vector<node_data>& expected)
const
1098 ::std::vector<node_data> stored;
1099 get_all_stored_data(stored);
1100 return equals(stored, expected);
1103template<
typename _Key,
typename _Value>
1104bool point_quad_tree<_Key, _Value>::verify_node_iterator(
const node_access& nac)
const
1106 return verify_node_iterator(nac, m_root.get());
1109template<
typename _Key,
typename _Value>
1110bool point_quad_tree<_Key, _Value>::verify_node_iterator(
const node_access& nac,
const node* p)
1113 return (p ==
nullptr);
1118 if (!verify_node_iterator(nac.northeast(), p->northeast.get()))
1120 if (!verify_node_iterator(nac.northwest(), p->northwest.get()))
1122 if (!verify_node_iterator(nac.southeast(), p->southeast.get()))
1124 if (!verify_node_iterator(nac.southwest(), p->southwest.get()))
1130template<
typename _Key,
typename _Value>
1131void point_quad_tree<_Key, _Value>::get_all_stored_data(
const node* p, ::std::vector<node_data>& stored_data)
const
1136 stored_data.push_back(node_data(p->x, p->y, p->data));
1138 get_all_stored_data(p->northeast.get(), stored_data);
1139 get_all_stored_data(p->northwest.get(), stored_data);
1140 get_all_stored_data(p->southeast.get(), stored_data);
1141 get_all_stored_data(p->southwest.get(), stored_data);
1144template<
typename _Key,
typename _Value>
1145typename point_quad_tree<_Key, _Value>::node_ptr point_quad_tree<_Key, _Value>::find_node(key_type x, key_type y)
const
1147 node_ptr cur_node = m_root;
1150 if (cur_node->x == x && cur_node->y == y)
1156 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1159 case quad_northeast:
1160 if (!cur_node->northeast)
1162 cur_node = cur_node->northeast;
1164 case quad_northwest:
1165 if (!cur_node->northwest)
1167 cur_node = cur_node->northwest;
1169 case quad_southeast:
1170 if (!cur_node->southeast)
1172 cur_node = cur_node->southeast;
1174 case quad_southwest:
1175 if (!cur_node->southwest)
1177 cur_node = cur_node->southwest;
1180 throw general_error(
"unknown quadrant");
1186template<
typename _Key,
typename _Value>
1187const typename point_quad_tree<_Key, _Value>::node* point_quad_tree<_Key, _Value>::find_node_ptr(
1188 key_type x, key_type y)
const
1190 const node* cur_node = m_root.get();
1193 if (cur_node->x == x && cur_node->y == y)
1199 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1202 case quad_northeast:
1203 if (!cur_node->northeast)
1205 cur_node = cur_node->northeast.get();
1207 case quad_northwest:
1208 if (!cur_node->northwest)
1210 cur_node = cur_node->northwest.get();
1212 case quad_southeast:
1213 if (!cur_node->southeast)
1215 cur_node = cur_node->southeast.get();
1217 case quad_southwest:
1218 if (!cur_node->southwest)
1220 cur_node = cur_node->southwest.get();
1223 throw general_error(
"unknown quadrant");
1229template<
typename _Key,
typename _Value>
1230typename point_quad_tree<_Key, _Value>::node_ptr point_quad_tree<_Key, _Value>::find_replacement_node(
1231 key_type x, key_type y,
const node_ptr& delete_node)
const
1233 using namespace std;
1236 node_distance dx_node, dy_node, min_city_block_node;
1238#if DEBUG_POINT_QUAD_TREE
1239 cout <<
"northeast" << endl;
1241 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northeast);
1243#if DEBUG_POINT_QUAD_TREE
1244 cout <<
"northwest" << endl;
1246 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northwest);
1248#if DEBUG_POINT_QUAD_TREE
1249 cout <<
"southwest" << endl;
1251 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southwest);
1253#if DEBUG_POINT_QUAD_TREE
1254 cout <<
"southeast" << endl;
1256 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southeast);
1260#if DEBUG_POINT_QUAD_TREE
1262 cout <<
"node closest to x axis: " << *dx_node.node->data <<
" (dx=" << dx_node.dist <<
")" << endl;
1265 cout <<
"node closest to y axis: " << *dy_node.node->data <<
" (dy=" << dy_node.dist <<
")" << endl;
1268 if (dx_node.node == dy_node.node && ((dx_node.quad == quad_northwest) || (dx_node.quad == quad_southeast)))
1270#if DEBUG_POINT_QUAD_TREE
1271 cout <<
"node that satisfies Criterion 1: " << *dx_node.node->data << endl;
1273 return dx_node.node;
1277#if DEBUG_POINT_QUAD_TREE
1278 cout <<
"unable to find node that satisfies Criterion 1." << endl;
1284 if (min_city_block_node.node)
1286#if DEBUG_POINT_QUAD_TREE
1287 cout <<
"node that satisfies Criterion 2: " << *min_city_block_node.node->data
1288 <<
" (dist=" << min_city_block_node.dist <<
")" << endl;
1290 return min_city_block_node.node;
1296template<
typename _Key,
typename _Value>
1297void point_quad_tree<_Key, _Value>::find_candidate_in_quad(
1298 key_type x, key_type y, node_distance& dx_node, node_distance& dy_node, node_distance& min_city_block_node,
1299 const node_ptr& delete_node, node_quadrant_t quad)
const
1301 using namespace std;
1303 node_ptr repl_node = delete_node->get_quadrant_node(quad);
1307#if DEBUG_POINT_QUAD_TREE
1308 cout <<
" no candidate in this quadrant" << endl;
1313 node_quadrant_t oppo_quad = opposite(quad);
1314 while (repl_node->has_quadrant_node(oppo_quad))
1315 repl_node = repl_node->get_quadrant_node(oppo_quad);
1317#if DEBUG_POINT_QUAD_TREE
1318 cout <<
" candidate: " << repl_node->x <<
"," << repl_node->y <<
" (" << *repl_node->data <<
")" << endl;
1322 key_type dx = repl_node->x > x ? repl_node->x - x : x - repl_node->x;
1323 key_type dy = repl_node->y > y ? repl_node->y - y : y - repl_node->y;
1324#if DEBUG_POINT_QUAD_TREE
1325 cout <<
" dx = " << dx <<
", dy = " << dy << endl;
1328 if (!dx_node.node || dx_node.dist > dx)
1329 dx_node = node_distance(quad, dx, repl_node);
1330 if (!dy_node.node || dy_node.dist > dy)
1331 dy_node = node_distance(quad, dy, repl_node);
1333 if (!min_city_block_node.node || min_city_block_node.dist > (dx + dy))
1334 min_city_block_node = node_distance(quad_unspecified, dx + dy, repl_node);
1337template<
typename _Key,
typename _Value>
1338void point_quad_tree<_Key, _Value>::adjust_quad(
1339 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange, node_ptr quad_root, direction_t dir,
1340 reinsert_tree_array_type& insert_list)
1342 using namespace std;
1347#if DEBUG_POINT_QUAD_TREE
1348 cout <<
"adjust_quad: checking " << *quad_root->data <<
" (" << quad_root->x <<
"," << quad_root->y <<
")" << endl;
1351 if ((hatched_xrange.first <= quad_root->x && quad_root->x <= hatched_xrange.second) ||
1352 (hatched_yrange.first <= quad_root->y && quad_root->y <= hatched_yrange.second))
1354#if DEBUG_POINT_QUAD_TREE
1355 cout <<
" " << *quad_root->data <<
" is in the hatched region" << endl;
1358 disconnect_node_from_parent(quad_root);
1359 quad_root->parent.reset();
1360 insert_list.push_back(quad_root);
1367 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northeast, dir_east, insert_list);
1368 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southeast, dir_east, insert_list);
1371 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northeast, dir_north, insert_list);
1372 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northwest, dir_north, insert_list);
1375 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southeast, dir_south, insert_list);
1376 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southwest, dir_south, insert_list);
1379 adjust_quad(hatched_xrange, hatched_yrange, quad_root->northwest, dir_west, insert_list);
1380 adjust_quad(hatched_xrange, hatched_yrange, quad_root->southwest, dir_west, insert_list);
1386template<
typename _Key,
typename _Value>
1387void point_quad_tree<_Key, _Value>::set_new_root(
1388 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange, node_ptr& quad_root,
1389 node_quadrant_t dir, reinsert_tree_array_type& insert_list)
1391 node_ptr cur_node = quad_root;
1396 case quad_northeast:
1397 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_east, insert_list);
1398 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_north, insert_list);
1400 case quad_northwest:
1401 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_north, insert_list);
1402 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_west, insert_list);
1404 case quad_southeast:
1405 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_east, insert_list);
1406 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_south, insert_list);
1408 case quad_southwest:
1409 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_west, insert_list);
1410 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_south, insert_list);
1413 throw general_error(
"unspecified quadrant");
1415 cur_node = cur_node->get_quadrant_node(dir);
1419template<
typename _Key,
typename _Value>
1420void point_quad_tree<_Key, _Value>::insert_node(node_ptr& dest, node_ptr& this_node)
1422 node_ptr cur_node = dest;
1425 if (cur_node->x == this_node->x && cur_node->y == this_node->y)
1430 throw general_error(
"node with identical position encountered.");
1433 node_quadrant_t quad = cur_node->get_quadrant(this_node->x, this_node->y);
1436 case quad_northeast:
1437 if (cur_node->northeast)
1438 cur_node = cur_node->northeast;
1441 cur_node->northeast = this_node;
1442 this_node->parent = cur_node;
1446 case quad_northwest:
1447 if (cur_node->northwest)
1448 cur_node = cur_node->northwest;
1451 cur_node->northwest = this_node;
1452 this_node->parent = cur_node;
1456 case quad_southeast:
1457 if (cur_node->southeast)
1458 cur_node = cur_node->southeast;
1461 cur_node->southeast = this_node;
1462 this_node->parent = cur_node;
1466 case quad_southwest:
1467 if (cur_node->southwest)
1468 cur_node = cur_node->southwest;
1471 cur_node->southwest = this_node;
1472 this_node->parent = cur_node;
1477 throw general_error(
"unknown quadrant");
1480 assert(!
"This should never be reached.");
1483template<
typename _Key,
typename _Value>
1484void point_quad_tree<_Key, _Value>::reinsert_tree(node_ptr& dest, node_ptr& root)
1492 if (root->northeast)
1494 reinsert_tree(dest, root->northeast);
1495 root->northeast.reset();
1497 if (root->northwest)
1499 reinsert_tree(dest, root->northwest);
1500 root->northwest.reset();
1502 if (root->southeast)
1504 reinsert_tree(dest, root->southeast);
1505 root->southeast.reset();
1507 if (root->southwest)
1509 reinsert_tree(dest, root->southwest);
1510 root->southwest.reset();
1513 root->parent.reset();
1514 insert_node(dest, root);
1517template<
typename _Key,
typename _Value>
1518void point_quad_tree<_Key, _Value>::reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root)
1526 case quad_northeast:
1527 if (dest->northeast)
1528 reinsert_tree(dest->northeast, root);
1531 dest->northeast = root;
1532 root->parent = dest;
1535 case quad_northwest:
1536 if (dest->northwest)
1537 reinsert_tree(dest->northwest, root);
1540 dest->northwest = root;
1541 root->parent = dest;
1544 case quad_southeast:
1545 if (dest->southeast)
1546 reinsert_tree(dest->southeast, root);
1549 dest->southeast = root;
1550 root->parent = dest;
1553 case quad_southwest:
1554 if (dest->southwest)
1555 reinsert_tree(dest->southwest, root);
1558 dest->southwest = root;
1559 root->parent = dest;
1563 throw general_error(
"reinsert_tree: quadrant unspecified");
1567template<
typename _Key,
typename _Value>
1568void point_quad_tree<_Key, _Value>::clear_all_nodes()
1570 ::mdds::disconnect_all_nodes(m_root);
Definition: global.hpp:84
Definition: point_quad_tree.hpp:117
Definition: point_quad_tree.hpp:158
Definition: point_quad_tree.hpp:233
Definition: point_quad_tree.hpp:225
Definition: point_quad_tree.hpp:106
void insert(key_type x, key_type y, value_type data)
Definition: point_quad_tree.hpp:668
void swap(point_quad_tree &r)
Definition: point_quad_tree.hpp:915
bool empty() const
Definition: point_quad_tree.hpp:929
size_t size() const
Definition: point_quad_tree.hpp:935
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:743
void clear()
Definition: point_quad_tree.hpp:923
void remove(key_type x, key_type y)
Definition: point_quad_tree.hpp:774
node_access get_node_access() const
Definition: point_quad_tree.hpp:943
value_type find(key_type x, key_type y) const
Definition: point_quad_tree.hpp:765
Definition: point_quad_tree.hpp:536
Definition: point_quad_tree.hpp:215
Definition: quad_node.hpp:118
quad_node_base & operator=(const quad_node_base &r)
Definition: quad_node.hpp:169