mdds
Loading...
Searching...
No Matches
point_quad_tree.hpp
1// SPDX-FileCopyrightText: 2010 - 2025 Kohei Yoshida
2//
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
7#include "mdds/quad_node.hpp"
8
9#include <cstdlib>
10#include <cassert>
11#include <iostream>
12#include <fstream>
13#include <string>
14#include <vector>
15#include <memory>
16#include <utility>
17
18#define DEBUG_POINT_QUAD_TREE 0
19
20namespace mdds {
21
22template<typename PairType>
23void ensure_order(PairType& v)
24{
25 if (v.first > v.second)
26 ::std::swap(v.first, v.second);
27}
28
29template<typename Key, typename NodeType, typename Inserter>
30void search_region_node(const NodeType* p, Key x1, Key y1, Key x2, Key y2, Inserter& result)
31{
32 using namespace std;
33
34 if (!p)
35 return;
36
37 search_region_space_t region = ::mdds::get_search_region_space(p, x1, y1, x2, y2);
38
39 switch (region)
40 {
41 case region_center:
42 result(p);
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);
47 break;
48 case region_east:
49 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
50 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
51 break;
52 case region_north:
53 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
54 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
55 break;
56 case region_northeast:
57 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
58 break;
59 case region_northwest:
60 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
61 break;
62 case region_south:
63 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
64 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
65 break;
66 case region_southeast:
67 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
68 break;
69 case region_southwest:
70 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
71 break;
72 case region_west:
73 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
74 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
75 break;
76 default:
77 throw general_error("unknown search region");
78 }
79}
80
81template<typename Key, typename Value>
82class point_quad_tree
83{
84private:
85 class search_result_inserter;
86
87public:
88 typedef Key key_type;
89 typedef Value value_type;
90 typedef size_t size_type;
91 typedef ::std::vector<value_type> data_array_type;
92
93 class data_not_found : public ::std::exception
94 {
95 };
96
97private:
98 struct node;
99 typedef ::boost::intrusive_ptr<node> node_ptr;
100
101 struct node : quad_node_base<node_ptr, node, key_type>
102 {
103 value_type data;
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))
105 {}
106
107 node(const node& r) : quad_node_base<node_ptr, node, key_type>(r), data(r.data)
108 {}
109
110 void dispose()
111 {}
112
113 bool operator==(const node& r) const
114 {
115 return quad_node_base<node_ptr, node, key_type>::operator==(r) && data == r.data;
116 }
117
118 node& operator=(const node& r)
119 {
121 data = r.data;
122 return *this;
123 }
124 };
125
126 typedef ::std::vector<node_ptr> reinsert_tree_array_type;
127 typedef ::std::pair<key_type, key_type> key_range_type;
128
129public:
134 class node_access
135 {
136 friend class point_quad_tree<Key, Value>;
137
138 public:
139 node_access northeast() const
140 {
141 return node_access(mp->northeast.get());
142 }
143 node_access northwest() const
144 {
145 return node_access(mp->northwest.get());
146 }
147 node_access southeast() const
148 {
149 return node_access(mp->southeast.get());
150 }
151 node_access southwest() const
152 {
153 return node_access(mp->southwest.get());
154 }
155
156 value_type data() const
157 {
158 return mp->data;
159 }
160 key_type x() const
161 {
162 return mp->x;
163 }
164 key_type y() const
165 {
166 return mp->y;
167 }
168
169 operator bool() const
170 {
171 return mp != nullptr;
172 }
173 bool operator==(const node_access& r) const
174 {
175 return mp == r.mp;
176 }
177
178 node_access() : mp(nullptr)
179 {}
180 ~node_access()
181 {}
182
183 private:
184 node_access(const node* p) : mp(p)
185 {}
186
187 private:
188 const node* mp;
189 };
190
191 struct point
192 {
193 key_type x;
194 key_type y;
195 point(key_type _x, key_type _y) : x(_x), y(_y)
196 {}
197 point() : x(0), y(0)
198 {}
199 };
200
201 class search_results
202 {
203 friend class search_result_inserter;
204
205 using res_nodes_type = std::vector<const node*>;
206 using res_nodes_ptr = std::shared_ptr<res_nodes_type>;
207
208 public:
209 class const_iterator
210 {
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;
214
215 public:
216 // Iterator traits
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;
222
223 const_iterator(res_nodes_ptr& ptr) : mp_res_nodes(ptr), m_end_pos(false)
224 {}
225
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)
229 {}
230
231 const_iterator& operator=(const const_iterator& r)
232 {
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;
237 return *this;
238 }
239
240 bool operator==(const const_iterator& r) const
241 {
242 if (mp_res_nodes)
243 {
244 // Non-empty result set.
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;
247 }
248
249 // Empty result set.
250 if (r.mp_res_nodes)
251 return false;
252
253 return m_end_pos == r.m_end_pos;
254 }
255
256 const value_type& operator*() const
257 {
258 return m_cur_value;
259 }
260
261 const value_type* operator->() const
262 {
263 return get_current_value();
264 }
265
266 const value_type* operator++()
267 {
268 // The only difference between the last data position and the
269 // end iterator position must be the value of m_end_pos;
270 // m_cur_pos needs to point to the last data position even
271 // when the iterator is at the end-of-iterator position.
272
273 typename res_nodes_type::const_iterator cur_pos = m_cur_pos;
274 if (++cur_pos == mp_res_nodes->end())
275 {
276 m_end_pos = true;
277 return nullptr;
278 }
279 m_cur_pos = cur_pos;
280 update_current_value();
281 return operator->();
282 }
283
284 const value_type* operator--()
285 {
286 if (m_end_pos)
287 {
288 m_end_pos = false;
289 return get_current_value();
290 }
291 --m_cur_pos;
292 update_current_value();
293 return get_current_value();
294 }
295
296 private:
297 void move_to_front()
298 {
299 if (!mp_res_nodes)
300 {
301 // Empty data set.
302 m_end_pos = true;
303 return;
304 }
305
306 m_cur_pos = mp_res_nodes->begin();
307 m_end_pos = false;
308 update_current_value();
309 }
310
311 void move_to_end()
312 {
313 m_end_pos = true;
314 if (!mp_res_nodes)
315 // Empty data set.
316 return;
317
318 m_cur_pos = mp_res_nodes->end();
319 --m_cur_pos; // Keep the position at the last data position.
320 }
321
322 void update_current_value()
323 {
324 const node* p = *m_cur_pos;
325 m_cur_value.first = point(p->x, p->y);
326 m_cur_value.second = p->data;
327 }
328
329 const value_type* get_current_value() const
330 {
331 return &m_cur_value;
332 }
333
334 private:
335 res_nodes_ptr mp_res_nodes;
336 typename res_nodes_type::const_iterator m_cur_pos;
337 value_type m_cur_value;
338 bool m_end_pos : 1;
339 };
340
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;
346
347 typename search_results::const_iterator begin()
348 {
349 typename search_results::const_iterator itr(mp_res_nodes);
350 itr.move_to_front();
351 return itr;
352 }
353
354 typename search_results::const_iterator end()
355 {
356 typename search_results::const_iterator itr(mp_res_nodes);
357 itr.move_to_end();
358 return itr;
359 }
360
361 private:
362 void push_back(const node* p)
363 {
364 if (!mp_res_nodes)
365 mp_res_nodes.reset(new res_nodes_type);
366 mp_res_nodes->push_back(p);
367 }
368
369 private:
370 res_nodes_ptr mp_res_nodes;
371 };
372
373 point_quad_tree();
374 point_quad_tree(const point_quad_tree& r);
375 ~point_quad_tree();
376
385 void insert(key_type x, key_type y, value_type data);
386
399 void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result) const;
400
414 search_results search_region(key_type x1, key_type y1, key_type x2, key_type y2) const;
415
426 value_type find(key_type x, key_type y) const;
427
435 void remove(key_type x, key_type y);
436
442 void swap(point_quad_tree& r);
443
447 void clear();
448
454 bool empty() const;
455
461 size_t size() const;
462
468 node_access get_node_access() const;
469
470 point_quad_tree& operator=(const point_quad_tree& r);
471
472 bool operator==(const point_quad_tree& r) const;
473
474#ifdef MDDS_UNIT_TEST
475public:
476#else
477private:
478#endif
483 struct node_data
484 {
485 key_type x;
486 key_type y;
487 value_type data;
488 node_data(key_type _x, key_type _y, value_type _data) : x(_x), y(_y), data(_data)
489 {}
490 node_data(const node_data& r) : x(r.x), y(r.y), data(r.data)
491 {}
492
493 bool operator==(const node_data& r) const
494 {
495 return (x == r.x) && (y == r.y) && (data == r.data);
496 }
497
498 struct sorter
499 {
500 bool operator()(const node_data& left, const node_data& right) const
501 {
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;
507 }
508 };
509 };
510
511 static bool equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2);
512
513 bool verify_data(::std::vector<node_data>& expected) const;
514
515 bool verify_node_iterator(const node_access& nac) const;
516 static bool verify_node_iterator(const node_access& nac, const node* p);
517
518 void get_all_stored_data(::std::vector<node_data>& stored_data) const;
519
520 void dump_tree_svg(const ::std::string& fpath) const;
521
522private:
523 class array_inserter
524 {
525 public:
526 array_inserter(data_array_type& result) : m_result(result)
527 {}
528
529 void operator()(const node* p)
530 {
531 m_result.push_back(p->data);
532 }
533
534 private:
535 data_array_type& m_result;
536 };
537
538 class search_result_inserter
539 {
540 public:
541 search_result_inserter(search_results& result) : m_result(result)
542 {}
543
544 void operator()(const node* p)
545 {
546 m_result.push_back(p);
547 }
548
549 private:
550 search_results& m_result;
551 };
552
553 class data_inserter
554 {
555 public:
556 data_inserter(point_quad_tree& db) : m_db(db)
557 {}
558
559 void operator()(const node_data& v)
560 {
561 m_db.insert(v.x, v.y, v.data);
562 }
563
564 private:
565 point_quad_tree& m_db;
566 };
567
568 struct node_distance
569 {
570 node_quadrant_t quad;
571 key_type dist;
572 node_ptr node;
573
574 node_distance() : quad(quad_unspecified), dist(0), node(nullptr)
575 {}
576 node_distance(node_quadrant_t _quad, key_type _dist, const node_ptr& _node)
577 : quad(_quad), dist(_dist), node(_node)
578 {}
579 };
580
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;
584
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;
588
589 void adjust_quad(
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);
592
593 void set_new_root(
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);
596
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;
605
606private:
607 node_ptr m_root;
608
609 key_range_type m_xrange;
610 key_range_type m_yrange;
611};
612
613template<typename Key, typename Value>
614point_quad_tree<Key, Value>::point_quad_tree() : m_root(nullptr), m_xrange(0, 0), m_yrange(0, 0)
615{}
616
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)
619{
620 insert_data_from(r);
621}
622
623template<typename Key, typename Value>
624point_quad_tree<Key, Value>::~point_quad_tree()
625{
626 clear_all_nodes();
627}
628
629template<typename Key, typename Value>
630void point_quad_tree<Key, Value>::insert(key_type x, key_type y, value_type data)
631{
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);
636
637 if (!m_root)
638 {
639 // The very first node.
640 m_root.reset(new node(x, y, std::move(data)));
641 return;
642 }
643
644 node_ptr cur_node = m_root;
645 while (true)
646 {
647 if (cur_node->x == x && cur_node->y == y)
648 {
649 // Replace the current data with this, and we are done!
650 cur_node->data = std::move(data);
651 return;
652 }
653
654 node_quadrant_t quad = cur_node->get_quadrant(x, y);
655 switch (quad)
656 {
657 case quad_northeast:
658 if (cur_node->northeast)
659 cur_node = cur_node->northeast;
660 else
661 {
662 cur_node->northeast.reset(new node(x, y, std::move(data)));
663 cur_node->northeast->parent = cur_node;
664 return;
665 }
666 break;
667 case quad_northwest:
668 if (cur_node->northwest)
669 cur_node = cur_node->northwest;
670 else
671 {
672 cur_node->northwest.reset(new node(x, y, std::move(data)));
673 cur_node->northwest->parent = cur_node;
674 return;
675 }
676 break;
677 case quad_southeast:
678 if (cur_node->southeast)
679 cur_node = cur_node->southeast;
680 else
681 {
682 cur_node->southeast.reset(new node(x, y, std::move(data)));
683 cur_node->southeast->parent = cur_node;
684 return;
685 }
686 break;
687 case quad_southwest:
688 if (cur_node->southwest)
689 cur_node = cur_node->southwest;
690 else
691 {
692 cur_node->southwest.reset(new node(x, y, std::move(data)));
693 cur_node->southwest->parent = cur_node;
694 return;
695 }
696 break;
697 default:
698 throw general_error("unknown quadrant");
699 }
700 }
701 assert(!"This should never be reached.");
702}
703
704template<typename Key, typename Value>
706 key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result) const
707{
708 using namespace std;
709 const node* p = m_root.get();
710 array_inserter _inserter(result);
711 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
712}
713
714template<typename Key, typename Value>
716 key_type x1, key_type y1, key_type x2, key_type y2) const
717{
718 using namespace std;
719 search_results result;
720 const node* p = m_root.get();
721 search_result_inserter _inserter(result);
722 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
723 return result;
724}
725
726template<typename Key, typename Value>
727typename point_quad_tree<Key, Value>::value_type point_quad_tree<Key, Value>::find(key_type x, key_type y) const
728{
729 const node* p = find_node_ptr(x, y);
730 if (!p)
731 throw data_not_found();
732 return p->data;
733}
734
735template<typename Key, typename Value>
736void point_quad_tree<Key, Value>::remove(key_type x, key_type y)
737{
738 using namespace std;
739 node_ptr delete_node = find_node(x, y);
740 if (!delete_node)
741 // No node exists at this coordinate.
742 return;
743
744#if DEBUG_POINT_QUAD_TREE
745 cout << "found the node to be removed at " << delete_node->x << "," << delete_node->y << " (" << *delete_node->data
746 << ")" << endl;
747#endif
748
749 // Check if this is a leaf node, in which case we can just delete it
750 // without further processing.
751 if (delete_node->leaf())
752 {
753#if DEBUG_POINT_QUAD_TREE
754 cout << "deleting a leaf node." << endl;
755#endif
756 if (delete_node.get() == m_root.get())
757 m_root.reset();
758 else
759 disconnect_node_from_parent(delete_node);
760 delete_node.reset();
761 return;
762 }
763
764 node_ptr repl_node = find_replacement_node(x, y, delete_node);
765 if (!repl_node)
766 // Non-leaf node should have at least one replacement candidate.
767 throw general_error("failed to find a replacement candidate node.");
768
769 node_quadrant_t repl_quad = delete_node->get_quadrant(repl_node->x, repl_node->y);
770
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;
776
777 // Call the quadrant where the replacement node is quadrant I. Adjust the
778 // quadrants adjacent to quadrant I first, then adjust quadrant I
779 // afterwards.
780 switch (repl_quad)
781 {
782 case quad_northeast:
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);
786 break;
787 case quad_northwest:
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);
791 break;
792 case quad_southeast:
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);
796 break;
797 case quad_southwest:
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);
801 break;
802 default:
803 throw general_error("quadrant for the replacement node is unspecified.");
804 }
805
806 // Reinsert all child nodes from the replacement node into the node to be
807 // "deleted".
808 switch (repl_quad)
809 {
810 case quad_northeast:
811 case quad_southwest:
812 {
813 node_ptr root = repl_node->northwest;
814 repl_node->northwest.reset();
815 reinsert_tree(delete_node, quad_northwest, root);
816
817 root = repl_node->southeast;
818 repl_node->southeast.reset();
819 reinsert_tree(delete_node, quad_southeast, root);
820 }
821 break;
822 case quad_northwest:
823 case quad_southeast:
824 {
825 node_ptr root = repl_node->northeast;
826 repl_node->northeast.reset();
827 reinsert_tree(delete_node, quad_northeast, root);
828
829 root = repl_node->southwest;
830 repl_node->southwest.reset();
831 reinsert_tree(delete_node, quad_southwest, root);
832 }
833 break;
834 default:
835 throw general_error("quadrant for the replacement node is unspecified.");
836 }
837
838 // Finally, replace the node to be removed with the replacement node.
839 delete_node->x = repl_node->x;
840 delete_node->y = repl_node->y;
841 delete_node->data = repl_node->data;
842
843 // Reset the parent node.
844 delete_node->parent = repl_node->parent;
845 repl_node->parent.reset();
846
847 switch (repl_quad)
848 {
849 case quad_northeast:
850 delete_node->northeast = repl_node->northeast;
851 repl_node->northeast.reset();
852 break;
853 case quad_northwest:
854 delete_node->northwest = repl_node->northwest;
855 repl_node->northwest.reset();
856 break;
857 case quad_southeast:
858 delete_node->southeast = repl_node->southeast;
859 repl_node->southeast.reset();
860 break;
861 case quad_southwest:
862 delete_node->southwest = repl_node->southwest;
863 repl_node->southwest.reset();
864 break;
865 default:
866 throw general_error("quadrant for the replacement node is unspecified.");
867 }
868
869 // Lastly, re-insert all those trees that have been cut during the quad
870 // adjustment into the new root.
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);
874}
875
876template<typename Key, typename Value>
877void point_quad_tree<Key, Value>::swap(point_quad_tree& r)
878{
879 m_root.swap(r.m_root);
880 ::std::swap(m_xrange, r.m_xrange);
881 ::std::swap(m_yrange, r.m_yrange);
882}
883
884template<typename Key, typename Value>
886{
887 clear_all_nodes();
888}
889
890template<typename Key, typename Value>
892{
893 return (m_root.get() == nullptr);
894}
895
896template<typename Key, typename Value>
898{
899 size_t node_count = 0;
900 count_all_nodes(m_root.get(), node_count);
901 return node_count;
902}
903
904template<typename Key, typename Value>
909
910template<typename Key, typename Value>
911point_quad_tree<Key, Value>& point_quad_tree<Key, Value>::operator=(const point_quad_tree& r)
912{
913 m_xrange = key_range_type(0, 0);
914 m_yrange = key_range_type(0, 0);
915 clear_all_nodes();
916 insert_data_from(r);
917 return *this;
918}
919
920template<typename Key, typename Value>
921bool point_quad_tree<Key, Value>::operator==(const point_quad_tree& r) const
922{
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);
927}
928
929template<typename Key, typename Value>
930void point_quad_tree<Key, Value>::dump_tree_svg(const ::std::string& fpath) const
931{
932 using namespace std;
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\" "
935 "version=\"1.1\">"
936 << endl;
937 file << "<defs>"
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\" />"
944 << " </marker>"
945 << "</defs>" << endl;
946
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;
953}
954
955template<typename NodePtr>
956void draw_svg_arrow(::std::ofstream& file, const NodePtr start, const NodePtr end)
957{
958 using namespace std;
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;
963}
964
965template<typename Key, typename Value>
966void point_quad_tree<Key, Value>::dump_node_svg(const node* p, ::std::ofstream& file) const
967{
968 using namespace std;
969
970 if (!p)
971 return;
972
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;
977
978 if (p->northwest)
979 draw_svg_arrow<const node*>(file, p, p->northwest.get());
980
981 if (p->northeast)
982 draw_svg_arrow<const node*>(file, p, p->northeast.get());
983
984 if (p->southwest)
985 draw_svg_arrow<const node*>(file, p, p->southwest.get());
986
987 if (p->southeast)
988 draw_svg_arrow<const node*>(file, p, p->southeast.get());
989
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);
994}
995
996template<typename Key, typename Value>
997bool point_quad_tree<Key, Value>::equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2)
998{
999 using namespace std;
1000
1001 if (v1.size() != v2.size())
1002 return false;
1003
1004 sort(v1.begin(), v1.end(), typename node_data::sorter());
1005 sort(v2.begin(), v2.end(), typename node_data::sorter());
1006
1007 typename vector<node_data>::const_iterator itr1 = v1.begin(), itr1_end = v1.end(), itr2 = v2.begin(),
1008 itr2_end = v2.end();
1009
1010 for (; itr1 != itr1_end; ++itr1, ++itr2)
1011 {
1012 if (itr2 == itr2_end)
1013 return false;
1014
1015 if (*itr1 != *itr2)
1016 return false;
1017 }
1018 if (itr2 != itr2_end)
1019 return false;
1020
1021 return true;
1022}
1023
1024template<typename Key, typename Value>
1025void point_quad_tree<Key, Value>::get_all_stored_data(::std::vector<node_data>& stored_data) const
1026{
1027 stored_data.clear();
1028 if (!m_root)
1029 return;
1030
1031 get_all_stored_data(m_root.get(), stored_data);
1032}
1033
1034template<typename Key, typename Value>
1035void point_quad_tree<Key, Value>::count_all_nodes(const node* p, size_t& node_count) const
1036{
1037 if (!p)
1038 return;
1039
1040 ++node_count;
1041
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);
1046}
1047
1048template<typename Key, typename Value>
1049void point_quad_tree<Key, Value>::insert_data_from(const point_quad_tree& r)
1050{
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));
1055}
1056
1057template<typename Key, typename Value>
1058bool point_quad_tree<Key, Value>::verify_data(::std::vector<node_data>& expected) const
1059{
1060 ::std::vector<node_data> stored;
1061 get_all_stored_data(stored);
1062 return equals(stored, expected);
1063}
1064
1065template<typename Key, typename Value>
1066bool point_quad_tree<Key, Value>::verify_node_iterator(const node_access& nac) const
1067{
1068 return verify_node_iterator(nac, m_root.get());
1069}
1070
1071template<typename Key, typename Value>
1072bool point_quad_tree<Key, Value>::verify_node_iterator(const node_access& nac, const node* p)
1073{
1074 if (!nac)
1075 return (p == nullptr);
1076
1077 if (!p)
1078 return false;
1079
1080 if (!verify_node_iterator(nac.northeast(), p->northeast.get()))
1081 return false;
1082 if (!verify_node_iterator(nac.northwest(), p->northwest.get()))
1083 return false;
1084 if (!verify_node_iterator(nac.southeast(), p->southeast.get()))
1085 return false;
1086 if (!verify_node_iterator(nac.southwest(), p->southwest.get()))
1087 return false;
1088
1089 return true;
1090}
1091
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
1094{
1095 if (!p)
1096 return;
1097
1098 stored_data.push_back(node_data(p->x, p->y, p->data));
1099
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);
1104}
1105
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
1108{
1109 node_ptr cur_node = m_root;
1110 while (cur_node)
1111 {
1112 if (cur_node->x == x && cur_node->y == y)
1113 {
1114 // Found the node.
1115 return cur_node;
1116 }
1117
1118 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1119 switch (quad)
1120 {
1121 case quad_northeast:
1122 if (!cur_node->northeast)
1123 return node_ptr();
1124 cur_node = cur_node->northeast;
1125 break;
1126 case quad_northwest:
1127 if (!cur_node->northwest)
1128 return node_ptr();
1129 cur_node = cur_node->northwest;
1130 break;
1131 case quad_southeast:
1132 if (!cur_node->southeast)
1133 return node_ptr();
1134 cur_node = cur_node->southeast;
1135 break;
1136 case quad_southwest:
1137 if (!cur_node->southwest)
1138 return node_ptr();
1139 cur_node = cur_node->southwest;
1140 break;
1141 default:
1142 throw general_error("unknown quadrant");
1143 }
1144 }
1145 return node_ptr();
1146}
1147
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
1151{
1152 const node* cur_node = m_root.get();
1153 while (cur_node)
1154 {
1155 if (cur_node->x == x && cur_node->y == y)
1156 {
1157 // Found the node.
1158 return cur_node;
1159 }
1160
1161 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1162 switch (quad)
1163 {
1164 case quad_northeast:
1165 if (!cur_node->northeast)
1166 return nullptr;
1167 cur_node = cur_node->northeast.get();
1168 break;
1169 case quad_northwest:
1170 if (!cur_node->northwest)
1171 return nullptr;
1172 cur_node = cur_node->northwest.get();
1173 break;
1174 case quad_southeast:
1175 if (!cur_node->southeast)
1176 return nullptr;
1177 cur_node = cur_node->southeast.get();
1178 break;
1179 case quad_southwest:
1180 if (!cur_node->southwest)
1181 return nullptr;
1182 cur_node = cur_node->southwest.get();
1183 break;
1184 default:
1185 throw general_error("unknown quadrant");
1186 }
1187 }
1188 return nullptr;
1189}
1190
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
1194{
1195 using namespace std;
1196
1197 // Try to get a replacement candidate in each quadrant.
1198 node_distance dx_node, dy_node, min_city_block_node;
1199
1200#if DEBUG_POINT_QUAD_TREE
1201 cout << "northeast" << endl;
1202#endif
1203 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northeast);
1204
1205#if DEBUG_POINT_QUAD_TREE
1206 cout << "northwest" << endl;
1207#endif
1208 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northwest);
1209
1210#if DEBUG_POINT_QUAD_TREE
1211 cout << "southwest" << endl;
1212#endif
1213 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southwest);
1214
1215#if DEBUG_POINT_QUAD_TREE
1216 cout << "southeast" << endl;
1217#endif
1218 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southeast);
1219
1220 // Check Criterion 1.
1221
1222#if DEBUG_POINT_QUAD_TREE
1223 if (dx_node.node)
1224 cout << "node closest to x axis: " << *dx_node.node->data << " (dx=" << dx_node.dist << ")" << endl;
1225
1226 if (dy_node.node)
1227 cout << "node closest to y axis: " << *dy_node.node->data << " (dy=" << dy_node.dist << ")" << endl;
1228#endif
1229
1230 if (dx_node.node == dy_node.node && ((dx_node.quad == quad_northwest) || (dx_node.quad == quad_southeast)))
1231 {
1232#if DEBUG_POINT_QUAD_TREE
1233 cout << "node that satisfies Criterion 1: " << *dx_node.node->data << endl;
1234#endif
1235 return dx_node.node;
1236 }
1237 else
1238 {
1239#if DEBUG_POINT_QUAD_TREE
1240 cout << "unable to find node that satisfies Criterion 1." << endl;
1241#endif
1242 }
1243
1244 // Move on to Criterion 2.
1245
1246 if (min_city_block_node.node)
1247 {
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;
1251#endif
1252 return min_city_block_node.node;
1253 }
1254
1255 return node_ptr();
1256}
1257
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
1262{
1263 using namespace std;
1264
1265 node_ptr repl_node = delete_node->get_quadrant_node(quad);
1266 if (!repl_node)
1267 {
1268 // No candidate in this quadrant.
1269#if DEBUG_POINT_QUAD_TREE
1270 cout << " no candidate in this quadrant" << endl;
1271#endif
1272 return;
1273 }
1274
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);
1278
1279#if DEBUG_POINT_QUAD_TREE
1280 cout << " candidate: " << repl_node->x << "," << repl_node->y << " (" << *repl_node->data << ")" << endl;
1281#endif
1282
1283 // Calculate its distance to each of the borders.
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;
1288#endif
1289
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);
1294
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);
1297}
1298
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)
1303{
1304 using namespace std;
1305
1306 if (!quad_root)
1307 return;
1308
1309#if DEBUG_POINT_QUAD_TREE
1310 cout << "adjust_quad: checking " << *quad_root->data << " (" << quad_root->x << "," << quad_root->y << ")" << endl;
1311#endif
1312
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))
1315 {
1316#if DEBUG_POINT_QUAD_TREE
1317 cout << " " << *quad_root->data << " is in the hatched region" << endl;
1318#endif
1319 // Insert the whole tree, including the root, into the insert list.
1320 disconnect_node_from_parent(quad_root);
1321 quad_root->parent.reset();
1322 insert_list.push_back(quad_root);
1323 return;
1324 }
1325
1326 switch (dir)
1327 {
1328 case dir_east:
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);
1331 break;
1332 case dir_north:
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);
1335 break;
1336 case dir_south:
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);
1339 break;
1340 case dir_west:
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);
1343 break;
1344 default:;
1345 }
1346}
1347
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)
1352{
1353 node_ptr cur_node = quad_root;
1354 while (cur_node)
1355 {
1356 switch (dir)
1357 {
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);
1361 break;
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);
1365 break;
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);
1369 break;
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);
1373 break;
1374 default:
1375 throw general_error("unspecified quadrant");
1376 }
1377 cur_node = cur_node->get_quadrant_node(dir);
1378 }
1379}
1380
1381template<typename Key, typename Value>
1382void point_quad_tree<Key, Value>::insert_node(node_ptr& dest, node_ptr& this_node)
1383{
1384 node_ptr cur_node = dest;
1385 while (true)
1386 {
1387 if (cur_node->x == this_node->x && cur_node->y == this_node->y)
1388 {
1389 // When inserting a node instance directly (likely as part of tree
1390 // re-insertion), we are not supposed to have another node at
1391 // identical position.
1392 throw general_error("node with identical position encountered.");
1393 }
1394
1395 node_quadrant_t quad = cur_node->get_quadrant(this_node->x, this_node->y);
1396 switch (quad)
1397 {
1398 case quad_northeast:
1399 if (cur_node->northeast)
1400 cur_node = cur_node->northeast;
1401 else
1402 {
1403 cur_node->northeast = this_node;
1404 this_node->parent = cur_node;
1405 return;
1406 }
1407 break;
1408 case quad_northwest:
1409 if (cur_node->northwest)
1410 cur_node = cur_node->northwest;
1411 else
1412 {
1413 cur_node->northwest = this_node;
1414 this_node->parent = cur_node;
1415 return;
1416 }
1417 break;
1418 case quad_southeast:
1419 if (cur_node->southeast)
1420 cur_node = cur_node->southeast;
1421 else
1422 {
1423 cur_node->southeast = this_node;
1424 this_node->parent = cur_node;
1425 return;
1426 }
1427 break;
1428 case quad_southwest:
1429 if (cur_node->southwest)
1430 cur_node = cur_node->southwest;
1431 else
1432 {
1433 cur_node->southwest = this_node;
1434 this_node->parent = cur_node;
1435 return;
1436 }
1437 break;
1438 default:
1439 throw general_error("unknown quadrant");
1440 }
1441 }
1442 assert(!"This should never be reached.");
1443}
1444
1445template<typename Key, typename Value>
1446void point_quad_tree<Key, Value>::reinsert_tree(node_ptr& dest, node_ptr& root)
1447{
1448 assert(dest); // Destination node should not be null.
1449
1450 if (!root)
1451 // Nothing to re-insert. Bail out.
1452 return;
1453
1454 if (root->northeast)
1455 {
1456 reinsert_tree(dest, root->northeast);
1457 root->northeast.reset();
1458 }
1459 if (root->northwest)
1460 {
1461 reinsert_tree(dest, root->northwest);
1462 root->northwest.reset();
1463 }
1464 if (root->southeast)
1465 {
1466 reinsert_tree(dest, root->southeast);
1467 root->southeast.reset();
1468 }
1469 if (root->southwest)
1470 {
1471 reinsert_tree(dest, root->southwest);
1472 root->southwest.reset();
1473 }
1474
1475 root->parent.reset();
1476 insert_node(dest, root);
1477}
1478
1479template<typename Key, typename Value>
1480void point_quad_tree<Key, Value>::reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root)
1481{
1482 if (!root)
1483 // Nothing to re-insert. Bail out.
1484 return;
1485
1486 switch (quad)
1487 {
1488 case quad_northeast:
1489 if (dest->northeast)
1490 reinsert_tree(dest->northeast, root);
1491 else
1492 {
1493 dest->northeast = root;
1494 root->parent = dest;
1495 }
1496 break;
1497 case quad_northwest:
1498 if (dest->northwest)
1499 reinsert_tree(dest->northwest, root);
1500 else
1501 {
1502 dest->northwest = root;
1503 root->parent = dest;
1504 }
1505 break;
1506 case quad_southeast:
1507 if (dest->southeast)
1508 reinsert_tree(dest->southeast, root);
1509 else
1510 {
1511 dest->southeast = root;
1512 root->parent = dest;
1513 }
1514 break;
1515 case quad_southwest:
1516 if (dest->southwest)
1517 reinsert_tree(dest->southwest, root);
1518 else
1519 {
1520 dest->southwest = root;
1521 root->parent = dest;
1522 }
1523 break;
1524 default:
1525 throw general_error("reinsert_tree: quadrant unspecified");
1526 }
1527}
1528
1529template<typename Key, typename Value>
1530void point_quad_tree<Key, Value>::clear_all_nodes()
1531{
1532 ::mdds::disconnect_all_nodes(m_root);
1533 m_root.reset();
1534}
1535
1536} // namespace mdds
Definition global.hpp:54
Definition point_quad_tree.hpp:94
Definition point_quad_tree.hpp:135
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