7#include "mdds/quad_node.hpp"
18#define DEBUG_POINT_QUAD_TREE 0
22template<
typename PairType>
23void ensure_order(PairType& v)
25 if (v.first > v.second)
26 ::std::swap(v.first, v.second);
29template<
typename Key,
typename NodeType,
typename Inserter>
30void search_region_node(
const NodeType* p, Key x1, Key y1, Key x2, Key y2, Inserter& result)
37 search_region_space_t region = ::mdds::get_search_region_space(p, x1, y1, x2, y2);
43 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
44 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
45 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
46 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
49 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
50 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
53 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
54 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
56 case region_northeast:
57 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
59 case region_northwest:
60 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
63 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
64 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
66 case region_southeast:
67 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
69 case region_southwest:
70 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
73 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
74 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
81template<
typename Key,
typename Value>
85 class search_result_inserter;
89 typedef Value value_type;
90 typedef size_t size_type;
91 typedef ::std::vector<value_type> data_array_type;
99 typedef ::boost::intrusive_ptr<node> node_ptr;
104 node(key_type _x, key_type _y, value_type _data) :
quad_node_base<node_ptr, node, key_type>(_x, _y), data(std::move(_data))
107 node(
const node& r) :
quad_node_base<node_ptr, node, key_type>(r), data(r.data)
113 bool operator==(
const node& r)
const
115 return quad_node_base<node_ptr, node, key_type>::operator==(r) && data == r.data;
118 node& operator=(
const node& r)
126 typedef ::std::vector<node_ptr> reinsert_tree_array_type;
127 typedef ::std::pair<key_type, key_type> key_range_type;
136 friend class point_quad_tree<Key, Value>;
139 node_access northeast()
const
141 return node_access(mp->northeast.get());
143 node_access northwest()
const
145 return node_access(mp->northwest.get());
147 node_access southeast()
const
149 return node_access(mp->southeast.get());
151 node_access southwest()
const
153 return node_access(mp->southwest.get());
156 value_type data()
const
169 operator bool()
const
171 return mp !=
nullptr;
173 bool operator==(
const node_access& r)
const
178 node_access() : mp(
nullptr)
184 node_access(
const node* p) : mp(p)
195 point(key_type _x, key_type _y) : x(_x), y(_y)
203 friend class search_result_inserter;
205 using res_nodes_type = std::vector<const node*>;
206 using res_nodes_ptr = std::shared_ptr<res_nodes_type>;
211 friend class point_quad_tree<Key, Value>::search_results;
212 typedef typename point_quad_tree<Key, Value>::point point;
213 typedef typename point_quad_tree<Key, Value>::value_type parent_value_type;
217 typedef std::pair<point, parent_value_type> value_type;
218 typedef value_type* pointer;
219 typedef value_type& reference;
220 typedef ptrdiff_t difference_type;
221 typedef ::std::bidirectional_iterator_tag iterator_category;
223 const_iterator(res_nodes_ptr& ptr) : mp_res_nodes(ptr), m_end_pos(false)
226 const_iterator(
const const_iterator& r)
227 : mp_res_nodes(r.mp_res_nodes), m_cur_pos(r.m_cur_pos), m_cur_value(r.m_cur_value),
228 m_end_pos(r.m_end_pos)
231 const_iterator& operator=(
const const_iterator& r)
233 mp_res_nodes = r.mp_res_nodes;
234 m_cur_pos = r.m_cur_pos;
235 m_cur_value = r.m_cur_value;
236 m_end_pos = r.m_end_pos;
240 bool operator==(
const const_iterator& r)
const
245 return mp_res_nodes.get() == r.mp_res_nodes.get() && m_cur_pos == r.m_cur_pos &&
246 m_end_pos == r.m_end_pos;
253 return m_end_pos == r.m_end_pos;
256 const value_type& operator*()
const
261 const value_type* operator->()
const
263 return get_current_value();
266 const value_type* operator++()
273 typename res_nodes_type::const_iterator cur_pos = m_cur_pos;
274 if (++cur_pos == mp_res_nodes->end())
280 update_current_value();
284 const value_type* operator--()
289 return get_current_value();
292 update_current_value();
293 return get_current_value();
306 m_cur_pos = mp_res_nodes->begin();
308 update_current_value();
318 m_cur_pos = mp_res_nodes->end();
322 void update_current_value()
324 const node* p = *m_cur_pos;
325 m_cur_value.first = point(p->x, p->y);
326 m_cur_value.second = p->data;
329 const value_type* get_current_value()
const
335 res_nodes_ptr mp_res_nodes;
336 typename res_nodes_type::const_iterator m_cur_pos;
337 value_type m_cur_value;
341 search_results() =
default;
342 search_results(
const search_results& other) =
default;
343 search_results(search_results&& other) =
default;
344 search_results& operator=(
const search_results& other) =
default;
345 search_results& operator=(search_results&& other) =
default;
362 void push_back(
const node* p)
365 mp_res_nodes.reset(
new res_nodes_type);
366 mp_res_nodes->push_back(p);
370 res_nodes_ptr mp_res_nodes;
374 point_quad_tree(
const point_quad_tree& r);
385 void insert(key_type x, key_type y, value_type data);
399 void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result)
const;
414 search_results
search_region(key_type x1, key_type y1, key_type x2, key_type y2)
const;
426 value_type
find(key_type x, key_type y)
const;
470 point_quad_tree& operator=(
const point_quad_tree& r);
472 bool operator==(
const point_quad_tree& r)
const;
488 node_data(key_type _x, key_type _y, value_type _data) : x(_x), y(_y), data(_data)
490 node_data(
const node_data& r) : x(r.x), y(r.y), data(r.data)
493 bool operator==(
const node_data& r)
const
495 return (x == r.x) && (y == r.y) && (data == r.data);
500 bool operator()(
const node_data& left,
const node_data& right)
const
502 if (left.x != right.x)
503 return left.x < right.x;
504 if (left.y != right.y)
505 return left.y < right.y;
506 return left.data < right.data;
511 static bool equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2);
513 bool verify_data(::std::vector<node_data>& expected)
const;
515 bool verify_node_iterator(
const node_access& nac)
const;
516 static bool verify_node_iterator(
const node_access& nac,
const node* p);
518 void get_all_stored_data(::std::vector<node_data>& stored_data)
const;
520 void dump_tree_svg(const ::std::string& fpath)
const;
526 array_inserter(data_array_type& result) : m_result(result)
529 void operator()(
const node* p)
531 m_result.push_back(p->data);
535 data_array_type& m_result;
538 class search_result_inserter
541 search_result_inserter(search_results& result) : m_result(result)
544 void operator()(
const node* p)
546 m_result.push_back(p);
550 search_results& m_result;
556 data_inserter(point_quad_tree& db) : m_db(db)
559 void operator()(
const node_data& v)
561 m_db.insert(v.x, v.y, v.data);
565 point_quad_tree& m_db;
570 node_quadrant_t quad;
574 node_distance() : quad(quad_unspecified), dist(0), node(nullptr)
576 node_distance(node_quadrant_t _quad, key_type _dist,
const node_ptr& _node)
577 : 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(
586 key_type x, key_type y, 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;
590 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange, node_ptr quad_root, direction_t dir,
591 reinsert_tree_array_type& insert_list);
594 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange, node_ptr& quad_root,
595 node_quadrant_t dir, reinsert_tree_array_type& insert_list);
597 void insert_node(node_ptr& dest, node_ptr& node);
598 void reinsert_tree(node_ptr& dest, node_ptr& root);
599 void reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root);
600 void clear_all_nodes();
601 void dump_node_svg(
const node* p, ::std::ofstream& file)
const;
602 void count_all_nodes(
const node* p,
size_t& node_count)
const;
603 void insert_data_from(
const point_quad_tree& r);
604 void get_all_stored_data(
const node* p, ::std::vector<node_data>& stored_data)
const;
609 key_range_type m_xrange;
610 key_range_type m_yrange;
613template<
typename Key,
typename Value>
614point_quad_tree<Key, Value>::point_quad_tree() : m_root(nullptr), m_xrange(0, 0), m_yrange(0, 0)
617template<
typename Key,
typename Value>
618point_quad_tree<Key, Value>::point_quad_tree(
const point_quad_tree& r) : m_root(nullptr), m_xrange(0, 0), m_yrange(0, 0)
623template<
typename Key,
typename Value>
624point_quad_tree<Key, Value>::~point_quad_tree()
629template<
typename Key,
typename Value>
632 m_xrange.first = ::std::min(m_xrange.first, x);
633 m_xrange.second = ::std::max(m_xrange.second, x);
634 m_yrange.first = ::std::min(m_yrange.first, y);
635 m_yrange.second = ::std::max(m_yrange.second, y);
640 m_root.reset(
new node(x, y, std::move(data)));
644 node_ptr cur_node = m_root;
647 if (cur_node->x == x && cur_node->y == y)
650 cur_node->data = std::move(data);
654 node_quadrant_t quad = cur_node->get_quadrant(x, y);
658 if (cur_node->northeast)
659 cur_node = cur_node->northeast;
662 cur_node->northeast.reset(
new node(x, y, std::move(data)));
663 cur_node->northeast->parent = cur_node;
668 if (cur_node->northwest)
669 cur_node = cur_node->northwest;
672 cur_node->northwest.reset(
new node(x, y, std::move(data)));
673 cur_node->northwest->parent = cur_node;
678 if (cur_node->southeast)
679 cur_node = cur_node->southeast;
682 cur_node->southeast.reset(
new node(x, y, std::move(data)));
683 cur_node->southeast->parent = cur_node;
688 if (cur_node->southwest)
689 cur_node = cur_node->southwest;
692 cur_node->southwest.reset(
new node(x, y, std::move(data)));
693 cur_node->southwest->parent = cur_node;
701 assert(!
"This should never be reached.");
704template<
typename Key,
typename Value>
706 key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result)
const
709 const node* p = m_root.get();
710 array_inserter _inserter(result);
711 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
714template<
typename Key,
typename Value>
716 key_type x1, key_type y1, key_type x2, key_type y2)
const
720 const node* p = m_root.get();
721 search_result_inserter _inserter(result);
722 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
726template<
typename Key,
typename Value>
729 const node* p = find_node_ptr(x, y);
735template<
typename Key,
typename Value>
739 node_ptr delete_node = find_node(x, y);
744#if DEBUG_POINT_QUAD_TREE
745 cout <<
"found the node to be removed at " << delete_node->x <<
"," << delete_node->y <<
" (" << *delete_node->data
751 if (delete_node->leaf())
753#if DEBUG_POINT_QUAD_TREE
754 cout <<
"deleting a leaf node." << endl;
756 if (delete_node.get() == m_root.get())
759 disconnect_node_from_parent(delete_node);
764 node_ptr repl_node = find_replacement_node(x, y, delete_node);
767 throw general_error(
"failed to find a replacement candidate node.");
769 node_quadrant_t repl_quad = delete_node->get_quadrant(repl_node->x, repl_node->y);
771 key_range_type xrange(delete_node->x, repl_node->x);
772 key_range_type yrange(delete_node->y, repl_node->y);
773 ensure_order(xrange);
774 ensure_order(yrange);
775 reinsert_tree_array_type insert_list;
783 adjust_quad(xrange, yrange, delete_node->northwest, dir_south, insert_list);
784 adjust_quad(xrange, yrange, delete_node->southeast, dir_west, insert_list);
785 set_new_root(xrange, yrange, delete_node->northeast, quad_southwest, insert_list);
788 adjust_quad(xrange, yrange, delete_node->northeast, dir_south, insert_list);
789 adjust_quad(xrange, yrange, delete_node->southwest, dir_east, insert_list);
790 set_new_root(xrange, yrange, delete_node->northwest, quad_southeast, insert_list);
793 adjust_quad(xrange, yrange, delete_node->northeast, dir_west, insert_list);
794 adjust_quad(xrange, yrange, delete_node->southwest, dir_north, insert_list);
795 set_new_root(xrange, yrange, delete_node->southeast, quad_northwest, insert_list);
798 adjust_quad(xrange, yrange, delete_node->northwest, dir_east, insert_list);
799 adjust_quad(xrange, yrange, delete_node->southeast, dir_north, insert_list);
800 set_new_root(xrange, yrange, delete_node->southwest, quad_northeast, insert_list);
803 throw general_error(
"quadrant for the replacement node is unspecified.");
813 node_ptr root = repl_node->northwest;
814 repl_node->northwest.reset();
815 reinsert_tree(delete_node, quad_northwest, root);
817 root = repl_node->southeast;
818 repl_node->southeast.reset();
819 reinsert_tree(delete_node, quad_southeast, root);
825 node_ptr root = repl_node->northeast;
826 repl_node->northeast.reset();
827 reinsert_tree(delete_node, quad_northeast, root);
829 root = repl_node->southwest;
830 repl_node->southwest.reset();
831 reinsert_tree(delete_node, quad_southwest, root);
835 throw general_error(
"quadrant for the replacement node is unspecified.");
839 delete_node->x = repl_node->x;
840 delete_node->y = repl_node->y;
841 delete_node->data = repl_node->data;
844 delete_node->parent = repl_node->parent;
845 repl_node->parent.reset();
850 delete_node->northeast = repl_node->northeast;
851 repl_node->northeast.reset();
854 delete_node->northwest = repl_node->northwest;
855 repl_node->northwest.reset();
858 delete_node->southeast = repl_node->southeast;
859 repl_node->southeast.reset();
862 delete_node->southwest = repl_node->southwest;
863 repl_node->southwest.reset();
866 throw general_error(
"quadrant for the replacement node is unspecified.");
871 typename reinsert_tree_array_type::iterator itr = insert_list.begin(), itr_end = insert_list.end();
872 for (; itr != itr_end; ++itr)
873 reinsert_tree(delete_node, *itr);
876template<
typename Key,
typename Value>
879 m_root.swap(r.m_root);
880 ::std::swap(m_xrange, r.m_xrange);
881 ::std::swap(m_yrange, r.m_yrange);
884template<
typename Key,
typename Value>
890template<
typename Key,
typename Value>
893 return (m_root.get() ==
nullptr);
896template<
typename Key,
typename Value>
899 size_t node_count = 0;
900 count_all_nodes(m_root.get(), node_count);
904template<
typename Key,
typename Value>
910template<
typename Key,
typename Value>
913 m_xrange = key_range_type(0, 0);
914 m_yrange = key_range_type(0, 0);
920template<
typename Key,
typename Value>
921bool point_quad_tree<Key, Value>::operator==(
const point_quad_tree& r)
const
923 ::std::vector<node_data> v1, v2;
924 get_all_stored_data(v1);
925 r.get_all_stored_data(v2);
926 return equals(v1, v2);
929template<
typename Key,
typename Value>
930void point_quad_tree<Key, Value>::dump_tree_svg(const ::std::string& fpath)
const
933 ofstream file(fpath.c_str());
934 file <<
"<svg width=\"60cm\" height=\"60cm\" viewBox=\"-2 -2 202 202\" xmlns=\"http://www.w3.org/2000/svg\" "
938 <<
" <marker id=\"Triangle\""
939 <<
" viewBox=\"0 0 10 10\" refX=\"10\" refY=\"5\" "
940 <<
" markerUnits=\"strokeWidth\""
941 <<
" markerWidth=\"9\" markerHeight=\"6\""
942 <<
" orient=\"auto\">"
943 <<
" <path d=\"M 0 0 L 10 5 L 0 10 z\" />"
945 <<
"</defs>" << endl;
947 file <<
"<path d=\"M 0 0 L 0 " << m_yrange.second + 1
948 <<
"\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
949 file <<
"<path d=\"M 0 0 L " << m_xrange.second + 1
950 <<
" 0\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
951 dump_node_svg(m_root.get(), file);
952 file <<
"</svg>" << endl;
955template<
typename NodePtr>
956void draw_svg_arrow(::std::ofstream& file,
const NodePtr start,
const NodePtr end)
959 file <<
"<g stroke=\"red\" marker-end=\"url(#Triangle)\">" << endl;
960 file <<
"<line x1=\"" << start->x <<
"\" y1=\"" << start->y <<
"\" x2=\"" << end->x <<
"\" y2=\"" << end->y
961 <<
"\" stroke-width=\"0.2\"/>" << endl;
962 file <<
"</g>" << endl;
965template<
typename Key,
typename Value>
966void point_quad_tree<Key, Value>::dump_node_svg(
const node* p, ::std::ofstream& file)
const
973 file <<
"<circle cx=\"" << p->x <<
"\" cy=\"" << p->y <<
"\" r=\"0.1\""
974 <<
" fill=\"black\" stroke=\"black\"/>" << endl;
975 file <<
"<text x=\"" << p->x + 1 <<
"\" y=\"" << p->y + 2 <<
"\" font-size=\"1.2\" fill=\"black\">" << *p->data
976 <<
" (" << p->x <<
"," << p->y <<
")</text>" << endl;
979 draw_svg_arrow<const node*>(file, p, p->northwest.get());
982 draw_svg_arrow<const node*>(file, p, p->northeast.get());
985 draw_svg_arrow<const node*>(file, p, p->southwest.get());
988 draw_svg_arrow<const node*>(file, p, p->southeast.get());
990 dump_node_svg(p->northeast.get(), file);
991 dump_node_svg(p->northwest.get(), file);
992 dump_node_svg(p->southeast.get(), file);
993 dump_node_svg(p->southwest.get(), file);
996template<
typename Key,
typename Value>
997bool point_quad_tree<Key, Value>::equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2)
1001 if (v1.size() != v2.size())
1004 sort(v1.begin(), v1.end(),
typename node_data::sorter());
1005 sort(v2.begin(), v2.end(),
typename node_data::sorter());
1007 typename vector<node_data>::const_iterator itr1 = v1.begin(), itr1_end = v1.end(), itr2 = v2.begin(),
1008 itr2_end = v2.end();
1010 for (; itr1 != itr1_end; ++itr1, ++itr2)
1012 if (itr2 == itr2_end)
1018 if (itr2 != itr2_end)
1024template<
typename Key,
typename Value>
1025void point_quad_tree<Key, Value>::get_all_stored_data(::std::vector<node_data>& stored_data)
const
1027 stored_data.clear();
1031 get_all_stored_data(m_root.get(), stored_data);
1034template<
typename Key,
typename Value>
1035void point_quad_tree<Key, Value>::count_all_nodes(
const node* p,
size_t& node_count)
const
1042 count_all_nodes(p->northeast.get(), node_count);
1043 count_all_nodes(p->northwest.get(), node_count);
1044 count_all_nodes(p->southeast.get(), node_count);
1045 count_all_nodes(p->southwest.get(), node_count);
1048template<
typename Key,
typename Value>
1049void point_quad_tree<Key, Value>::insert_data_from(
const point_quad_tree& r)
1051 using namespace std;
1052 vector<node_data> all_data;
1053 r.get_all_stored_data(all_data);
1054 for_each(all_data.begin(), all_data.end(), data_inserter(*
this));
1057template<
typename Key,
typename Value>
1058bool point_quad_tree<Key, Value>::verify_data(::std::vector<node_data>& expected)
const
1060 ::std::vector<node_data> stored;
1061 get_all_stored_data(stored);
1062 return equals(stored, expected);
1065template<
typename Key,
typename Value>
1066bool point_quad_tree<Key, Value>::verify_node_iterator(
const node_access& nac)
const
1068 return verify_node_iterator(nac, m_root.get());
1071template<
typename Key,
typename Value>
1072bool point_quad_tree<Key, Value>::verify_node_iterator(
const node_access& nac,
const node* p)
1075 return (p ==
nullptr);
1080 if (!verify_node_iterator(nac.northeast(), p->northeast.get()))
1082 if (!verify_node_iterator(nac.northwest(), p->northwest.get()))
1084 if (!verify_node_iterator(nac.southeast(), p->southeast.get()))
1086 if (!verify_node_iterator(nac.southwest(), p->southwest.get()))
1092template<
typename Key,
typename Value>
1093void point_quad_tree<Key, Value>::get_all_stored_data(
const node* p, ::std::vector<node_data>& stored_data)
const
1098 stored_data.push_back(node_data(p->x, p->y, p->data));
1100 get_all_stored_data(p->northeast.get(), stored_data);
1101 get_all_stored_data(p->northwest.get(), stored_data);
1102 get_all_stored_data(p->southeast.get(), stored_data);
1103 get_all_stored_data(p->southwest.get(), stored_data);
1106template<
typename Key,
typename Value>
1107typename point_quad_tree<Key, Value>::node_ptr point_quad_tree<Key, Value>::find_node(key_type x, key_type y)
const
1109 node_ptr cur_node = m_root;
1112 if (cur_node->x == x && cur_node->y == y)
1118 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1121 case quad_northeast:
1122 if (!cur_node->northeast)
1124 cur_node = cur_node->northeast;
1126 case quad_northwest:
1127 if (!cur_node->northwest)
1129 cur_node = cur_node->northwest;
1131 case quad_southeast:
1132 if (!cur_node->southeast)
1134 cur_node = cur_node->southeast;
1136 case quad_southwest:
1137 if (!cur_node->southwest)
1139 cur_node = cur_node->southwest;
1142 throw general_error(
"unknown quadrant");
1148template<
typename Key,
typename Value>
1149const typename point_quad_tree<Key, Value>::node* point_quad_tree<Key, Value>::find_node_ptr(
1150 key_type x, key_type y)
const
1152 const node* cur_node = m_root.get();
1155 if (cur_node->x == x && cur_node->y == y)
1161 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1164 case quad_northeast:
1165 if (!cur_node->northeast)
1167 cur_node = cur_node->northeast.get();
1169 case quad_northwest:
1170 if (!cur_node->northwest)
1172 cur_node = cur_node->northwest.get();
1174 case quad_southeast:
1175 if (!cur_node->southeast)
1177 cur_node = cur_node->southeast.get();
1179 case quad_southwest:
1180 if (!cur_node->southwest)
1182 cur_node = cur_node->southwest.get();
1185 throw general_error(
"unknown quadrant");
1191template<
typename Key,
typename Value>
1192typename point_quad_tree<Key, Value>::node_ptr point_quad_tree<Key, Value>::find_replacement_node(
1193 key_type x, key_type y,
const node_ptr& delete_node)
const
1195 using namespace std;
1198 node_distance dx_node, dy_node, min_city_block_node;
1200#if DEBUG_POINT_QUAD_TREE
1201 cout <<
"northeast" << endl;
1203 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northeast);
1205#if DEBUG_POINT_QUAD_TREE
1206 cout <<
"northwest" << endl;
1208 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northwest);
1210#if DEBUG_POINT_QUAD_TREE
1211 cout <<
"southwest" << endl;
1213 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southwest);
1215#if DEBUG_POINT_QUAD_TREE
1216 cout <<
"southeast" << endl;
1218 find_candidate_in_quad(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
1250 <<
" (dist=" << min_city_block_node.dist <<
")" << endl;
1252 return min_city_block_node.node;
1258template<
typename Key,
typename Value>
1259void point_quad_tree<Key, Value>::find_candidate_in_quad(
1260 key_type x, key_type y, 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);
1299template<
typename Key,
typename Value>
1300void point_quad_tree<Key, Value>::adjust_quad(
1301 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange, node_ptr quad_root, direction_t dir,
1302 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);
1348template<
typename Key,
typename Value>
1349void point_quad_tree<Key, Value>::set_new_root(
1350 const key_range_type& hatched_xrange,
const key_range_type& hatched_yrange, node_ptr& quad_root,
1351 node_quadrant_t dir, reinsert_tree_array_type& insert_list)
1353 node_ptr cur_node = quad_root;
1358 case quad_northeast:
1359 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_east, insert_list);
1360 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_north, insert_list);
1362 case quad_northwest:
1363 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_north, insert_list);
1364 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_west, insert_list);
1366 case quad_southeast:
1367 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_east, insert_list);
1368 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_south, insert_list);
1370 case quad_southwest:
1371 adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_west, insert_list);
1372 adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_south, insert_list);
1375 throw general_error(
"unspecified quadrant");
1377 cur_node = cur_node->get_quadrant_node(dir);
1381template<
typename Key,
typename Value>
1382void point_quad_tree<Key, Value>::insert_node(node_ptr& dest, node_ptr& this_node)
1384 node_ptr cur_node = dest;
1387 if (cur_node->x == this_node->x && cur_node->y == this_node->y)
1392 throw general_error(
"node with identical position encountered.");
1395 node_quadrant_t quad = cur_node->get_quadrant(this_node->x, this_node->y);
1398 case quad_northeast:
1399 if (cur_node->northeast)
1400 cur_node = cur_node->northeast;
1403 cur_node->northeast = this_node;
1404 this_node->parent = cur_node;
1408 case quad_northwest:
1409 if (cur_node->northwest)
1410 cur_node = cur_node->northwest;
1413 cur_node->northwest = this_node;
1414 this_node->parent = cur_node;
1418 case quad_southeast:
1419 if (cur_node->southeast)
1420 cur_node = cur_node->southeast;
1423 cur_node->southeast = this_node;
1424 this_node->parent = cur_node;
1428 case quad_southwest:
1429 if (cur_node->southwest)
1430 cur_node = cur_node->southwest;
1433 cur_node->southwest = this_node;
1434 this_node->parent = cur_node;
1439 throw general_error(
"unknown quadrant");
1442 assert(!
"This should never be reached.");
1445template<
typename Key,
typename Value>
1446void point_quad_tree<Key, Value>::reinsert_tree(node_ptr& dest, node_ptr& root)
1454 if (root->northeast)
1456 reinsert_tree(dest, root->northeast);
1457 root->northeast.reset();
1459 if (root->northwest)
1461 reinsert_tree(dest, root->northwest);
1462 root->northwest.reset();
1464 if (root->southeast)
1466 reinsert_tree(dest, root->southeast);
1467 root->southeast.reset();
1469 if (root->southwest)
1471 reinsert_tree(dest, root->southwest);
1472 root->southwest.reset();
1475 root->parent.reset();
1476 insert_node(dest, root);
1479template<
typename Key,
typename Value>
1480void point_quad_tree<Key, Value>::reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root)
1488 case quad_northeast:
1489 if (dest->northeast)
1490 reinsert_tree(dest->northeast, root);
1493 dest->northeast = root;
1494 root->parent = dest;
1497 case quad_northwest:
1498 if (dest->northwest)
1499 reinsert_tree(dest->northwest, root);
1502 dest->northwest = root;
1503 root->parent = dest;
1506 case quad_southeast:
1507 if (dest->southeast)
1508 reinsert_tree(dest->southeast, root);
1511 dest->southeast = root;
1512 root->parent = dest;
1515 case quad_southwest:
1516 if (dest->southwest)
1517 reinsert_tree(dest->southwest, root);
1520 dest->southwest = root;
1521 root->parent = dest;
1525 throw general_error(
"reinsert_tree: quadrant unspecified");
1529template<
typename Key,
typename Value>
1530void point_quad_tree<Key, Value>::clear_all_nodes()
1532 ::mdds::disconnect_all_nodes(m_root);
Definition point_quad_tree.hpp:94
Definition point_quad_tree.hpp:135
Definition point_quad_tree.hpp:210
Definition point_quad_tree.hpp:202
Definition point_quad_tree.hpp:83
value_type find(key_type x, key_type y) const
Definition point_quad_tree.hpp:727
void insert(key_type x, key_type y, value_type data)
Definition point_quad_tree.hpp:630
size_t size() const
Definition point_quad_tree.hpp:897
node_access get_node_access() const
Definition point_quad_tree.hpp:905
bool empty() const
Definition point_quad_tree.hpp:891
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:705
void swap(point_quad_tree &r)
Definition point_quad_tree.hpp:877
void clear()
Definition point_quad_tree.hpp:885
search_results search_region(key_type x1, key_type y1, key_type x2, key_type y2) const
Definition point_quad_tree.hpp:715
void remove(key_type x, key_type y)
Definition point_quad_tree.hpp:736
Definition point_quad_tree.hpp:499
Definition quad_node.hpp:94
quad_node_base & operator=(const quad_node_base &r)
Definition quad_node.hpp:145