mdds
point_quad_tree.hpp
1/*************************************************************************
2 *
3 * Copyright (c) 2010-2015 Kohei Yoshida
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 *
26 ************************************************************************/
27
28#ifndef INCLUDED_MDDS_POINT_QUAD_TREE_HPP
29#define INCLUDED_MDDS_POINT_QUAD_TREE_HPP
30
31#include "mdds/quad_node.hpp"
32
33#include <cstdlib>
34#include <cassert>
35#include <iostream>
36#include <fstream>
37#include <string>
38#include <vector>
39#include <memory>
40
41#define DEBUG_POINT_QUAD_TREE 0
42
43namespace mdds {
44
45template<typename _PairType>
46void ensure_order(_PairType& v)
47{
48 if (v.first > v.second)
49 ::std::swap(v.first, v.second);
50}
51
52template<typename _Key, typename _NodeType, typename _Inserter>
53void search_region_node(const _NodeType* p, _Key x1, _Key y1, _Key x2, _Key y2, _Inserter& result)
54{
55 using namespace std;
56
57 if (!p)
58 return;
59
60 search_region_space_t region = ::mdds::get_search_region_space(p, x1, y1, x2, y2);
61
62 switch (region)
63 {
64 case region_center:
65 result(p);
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);
70 break;
71 case region_east:
72 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
73 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
74 break;
75 case region_north:
76 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
77 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
78 break;
79 case region_northeast:
80 search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
81 break;
82 case region_northwest:
83 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
84 break;
85 case region_south:
86 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
87 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
88 break;
89 case region_southeast:
90 search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
91 break;
92 case region_southwest:
93 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
94 break;
95 case region_west:
96 search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
97 search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
98 break;
99 default:
100 throw general_error("unknown search region");
101 }
102}
103
104template<typename _Key, typename _Value>
106{
107private:
108 class search_result_inserter;
109
110public:
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;
115
116 class data_not_found : public ::std::exception
117 {
118 };
119
120private:
121 struct node;
122 typedef ::boost::intrusive_ptr<node> node_ptr;
123
124 struct node : quad_node_base<node_ptr, node, key_type>
125 {
126 value_type data;
127 node(key_type _x, key_type _y, value_type _data) : quad_node_base<node_ptr, node, key_type>(_x, _y), data(_data)
128 {}
129
130 node(const node& r) : quad_node_base<node_ptr, node, key_type>(r), data(r.data)
131 {}
132
133 void dispose()
134 {}
135
136 bool operator==(const node& r) const
137 {
138 return quad_node_base<node_ptr, node, key_type>::operator==(r) && data == r.data;
139 }
140
141 node& operator=(const node& r)
142 {
144 data = r.data;
145 return *this;
146 }
147 };
148
149 typedef ::std::vector<node_ptr> reinsert_tree_array_type;
150 typedef ::std::pair<key_type, key_type> key_range_type;
151
152public:
158 {
159 friend class point_quad_tree<_Key, _Value>;
160
161 public:
162 node_access northeast() const
163 {
164 return node_access(mp->northeast.get());
165 }
166 node_access northwest() const
167 {
168 return node_access(mp->northwest.get());
169 }
170 node_access southeast() const
171 {
172 return node_access(mp->southeast.get());
173 }
174 node_access southwest() const
175 {
176 return node_access(mp->southwest.get());
177 }
178
179 value_type data() const
180 {
181 return mp->data;
182 }
183 key_type x() const
184 {
185 return mp->x;
186 }
187 key_type y() const
188 {
189 return mp->y;
190 }
191
192 operator bool() const
193 {
194 return mp != nullptr;
195 }
196 bool operator==(const node_access& r) const
197 {
198 return mp == r.mp;
199 }
200
201 node_access() : mp(nullptr)
202 {}
204 {}
205
206 private:
207 node_access(const node* p) : mp(p)
208 {}
209
210 private:
211 const node* mp;
212 };
213
214 struct point
215 {
216 key_type x;
217 key_type y;
218 point(key_type _x, key_type _y) : x(_x), y(_y)
219 {}
220 point() : x(0), y(0)
221 {}
222 };
223
225 {
226 friend class search_result_inserter;
227
228 typedef std::vector<const node*> res_nodes_type;
229 typedef std::shared_ptr<res_nodes_type> res_nodes_ptr;
230
231 public:
233 {
234 friend class point_quad_tree<_Key, _Value>::search_results;
235 typedef typename point_quad_tree<_Key, _Value>::point point;
236 typedef typename point_quad_tree<_Key, _Value>::value_type parent_value_type;
237
238 public:
239 // Iterator traits
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;
245
246 const_iterator(res_nodes_ptr& ptr) : mp_res_nodes(ptr), m_end_pos(false)
247 {}
248
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)
252 {}
253
254 const_iterator& operator=(const const_iterator& r)
255 {
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;
260 return *this;
261 }
262
263 bool operator==(const const_iterator& r) const
264 {
265 if (mp_res_nodes)
266 {
267 // Non-empty result set.
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;
270 }
271
272 // Empty result set.
273 if (r.mp_res_nodes)
274 return false;
275
276 return m_end_pos == r.m_end_pos;
277 }
278
279 bool operator!=(const const_iterator& r) const
280 {
281 return !operator==(r);
282 }
283
284 const value_type& operator*() const
285 {
286 return m_cur_value;
287 }
288
289 const value_type* operator->() const
290 {
291 return get_current_value();
292 }
293
294 const value_type* operator++()
295 {
296 // The only difference between the last data position and the
297 // end iterator position must be the value of m_end_pos;
298 // m_cur_pos needs to point to the last data position even
299 // when the iterator is at the end-of-iterator position.
300
301 typename res_nodes_type::const_iterator cur_pos = m_cur_pos;
302 if (++cur_pos == mp_res_nodes->end())
303 {
304 m_end_pos = true;
305 return nullptr;
306 }
307 m_cur_pos = cur_pos;
308 update_current_value();
309 return operator->();
310 }
311
312 const value_type* operator--()
313 {
314 if (m_end_pos)
315 {
316 m_end_pos = false;
317 return get_current_value();
318 }
319 --m_cur_pos;
320 update_current_value();
321 return get_current_value();
322 }
323
324 private:
325 void move_to_front()
326 {
327 if (!mp_res_nodes)
328 {
329 // Empty data set.
330 m_end_pos = true;
331 return;
332 }
333
334 m_cur_pos = mp_res_nodes->begin();
335 m_end_pos = false;
336 update_current_value();
337 }
338
339 void move_to_end()
340 {
341 m_end_pos = true;
342 if (!mp_res_nodes)
343 // Empty data set.
344 return;
345
346 m_cur_pos = mp_res_nodes->end();
347 --m_cur_pos; // Keep the position at the last data position.
348 }
349
350 void update_current_value()
351 {
352 const node* p = *m_cur_pos;
353 m_cur_value.first = point(p->x, p->y);
354 m_cur_value.second = p->data;
355 }
356
357 const value_type* get_current_value() const
358 {
359 return &m_cur_value;
360 }
361
362 private:
363 res_nodes_ptr mp_res_nodes;
364 typename res_nodes_type::const_iterator m_cur_pos;
365 value_type m_cur_value;
366 bool m_end_pos : 1;
367 };
368
369 search_results() : mp_res_nodes(static_cast<res_nodes_type*>(nullptr))
370 {}
371 search_results(const search_results& r) : mp_res_nodes(r.mp_res_nodes)
372 {}
373
374 typename search_results::const_iterator begin()
375 {
376 typename search_results::const_iterator itr(mp_res_nodes);
377 itr.move_to_front();
378 return itr;
379 }
380
381 typename search_results::const_iterator end()
382 {
383 typename search_results::const_iterator itr(mp_res_nodes);
384 itr.move_to_end();
385 return itr;
386 }
387
388 private:
389 void push_back(const node* p)
390 {
391 if (!mp_res_nodes)
392 mp_res_nodes.reset(new res_nodes_type);
393 mp_res_nodes->push_back(p);
394 }
395
396 private:
397 res_nodes_ptr mp_res_nodes;
398 };
399
400 point_quad_tree();
401 point_quad_tree(const point_quad_tree& r);
402 ~point_quad_tree();
403
412 void insert(key_type x, key_type y, value_type data);
413
426 void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result) const;
427
441 search_results search_region(key_type x1, key_type y1, key_type x2, key_type y2) const;
442
453 value_type find(key_type x, key_type y) const;
454
462 void remove(key_type x, key_type y);
463
469 void swap(point_quad_tree& r);
470
474 void clear();
475
481 bool empty() const;
482
488 size_t size() const;
489
495 node_access get_node_access() const;
496
497 point_quad_tree& operator=(const point_quad_tree& r);
498
499 bool operator==(const point_quad_tree& r) const;
500
501 bool operator!=(const point_quad_tree& r) const
502 {
503 return !operator==(r);
504 }
505
506#ifdef MDDS_UNIT_TEST
507public:
508#else
509private:
510#endif
515 struct node_data
516 {
517 key_type x;
518 key_type y;
519 value_type data;
520 node_data(key_type _x, key_type _y, value_type _data) : x(_x), y(_y), data(_data)
521 {}
522 node_data(const node_data& r) : x(r.x), y(r.y), data(r.data)
523 {}
524
525 bool operator==(const node_data& r) const
526 {
527 return (x == r.x) && (y == r.y) && (data == r.data);
528 }
529
530 bool operator!=(const node_data& r) const
531 {
532 return !operator==(r);
533 }
534
535 struct sorter
536 {
537 bool operator()(const node_data& left, const node_data& right) const
538 {
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;
544 }
545 };
546 };
547
548 static bool equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2);
549
550 bool verify_data(::std::vector<node_data>& expected) const;
551
552 bool verify_node_iterator(const node_access& nac) const;
553 static bool verify_node_iterator(const node_access& nac, const node* p);
554
555 void get_all_stored_data(::std::vector<node_data>& stored_data) const;
556
557 void dump_tree_svg(const ::std::string& fpath) const;
558
559private:
560 class array_inserter
561 {
562 public:
563 array_inserter(data_array_type& result) : m_result(result)
564 {}
565
566 void operator()(const node* p)
567 {
568 m_result.push_back(p->data);
569 }
570
571 private:
572 data_array_type& m_result;
573 };
574
575 class search_result_inserter
576 {
577 public:
578 search_result_inserter(search_results& result) : m_result(result)
579 {}
580
581 void operator()(const node* p)
582 {
583 m_result.push_back(p);
584 }
585
586 private:
587 search_results& m_result;
588 };
589
590 class data_inserter
591 {
592 public:
593 data_inserter(point_quad_tree& db) : m_db(db)
594 {}
595
596 void operator()(const node_data& v)
597 {
598 m_db.insert(v.x, v.y, v.data);
599 }
600
601 private:
602 point_quad_tree& m_db;
603 };
604
605 struct node_distance
606 {
607 node_quadrant_t quad;
608 key_type dist;
609 node_ptr node;
610
611 node_distance() : quad(quad_unspecified), dist(0), node(nullptr)
612 {}
613 node_distance(node_quadrant_t _quad, key_type _dist, const node_ptr& _node)
614 : quad(_quad), dist(_dist), node(_node)
615 {}
616 };
617
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;
621
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;
625
626 void adjust_quad(
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);
629
630 void set_new_root(
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);
633
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;
642
643private:
644 node_ptr m_root;
645
646 key_range_type m_xrange;
647 key_range_type m_yrange;
648};
649
650template<typename _Key, typename _Value>
651point_quad_tree<_Key, _Value>::point_quad_tree() : m_root(nullptr), m_xrange(0, 0), m_yrange(0, 0)
652{}
653
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)
657{
658 insert_data_from(r);
659}
660
661template<typename _Key, typename _Value>
662point_quad_tree<_Key, _Value>::~point_quad_tree()
663{
664 clear_all_nodes();
665}
666
667template<typename _Key, typename _Value>
668void point_quad_tree<_Key, _Value>::insert(key_type x, key_type y, value_type data)
669{
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);
674
675 if (!m_root)
676 {
677 // The very first node.
678 m_root.reset(new node(x, y, data));
679 return;
680 }
681
682 node_ptr cur_node = m_root;
683 while (true)
684 {
685 if (cur_node->x == x && cur_node->y == y)
686 {
687 // Replace the current data with this, and we are done!
688 cur_node->data = data;
689 return;
690 }
691
692 node_quadrant_t quad = cur_node->get_quadrant(x, y);
693 switch (quad)
694 {
695 case quad_northeast:
696 if (cur_node->northeast)
697 cur_node = cur_node->northeast;
698 else
699 {
700 cur_node->northeast.reset(new node(x, y, data));
701 cur_node->northeast->parent = cur_node;
702 return;
703 }
704 break;
705 case quad_northwest:
706 if (cur_node->northwest)
707 cur_node = cur_node->northwest;
708 else
709 {
710 cur_node->northwest.reset(new node(x, y, data));
711 cur_node->northwest->parent = cur_node;
712 return;
713 }
714 break;
715 case quad_southeast:
716 if (cur_node->southeast)
717 cur_node = cur_node->southeast;
718 else
719 {
720 cur_node->southeast.reset(new node(x, y, data));
721 cur_node->southeast->parent = cur_node;
722 return;
723 }
724 break;
725 case quad_southwest:
726 if (cur_node->southwest)
727 cur_node = cur_node->southwest;
728 else
729 {
730 cur_node->southwest.reset(new node(x, y, data));
731 cur_node->southwest->parent = cur_node;
732 return;
733 }
734 break;
735 default:
736 throw general_error("unknown quadrant");
737 }
738 }
739 assert(!"This should never be reached.");
740}
741
742template<typename _Key, typename _Value>
744 key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result) const
745{
746 using namespace std;
747 const node* p = m_root.get();
748 array_inserter _inserter(result);
749 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
750}
751
752template<typename _Key, typename _Value>
754 key_type x1, key_type y1, key_type x2, key_type y2) const
755{
756 using namespace std;
757 search_results result;
758 const node* p = m_root.get();
759 search_result_inserter _inserter(result);
760 ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
761 return result;
762}
763
764template<typename _Key, typename _Value>
765typename point_quad_tree<_Key, _Value>::value_type point_quad_tree<_Key, _Value>::find(key_type x, key_type y) const
766{
767 const node* p = find_node_ptr(x, y);
768 if (!p)
769 throw data_not_found();
770 return p->data;
771}
772
773template<typename _Key, typename _Value>
774void point_quad_tree<_Key, _Value>::remove(key_type x, key_type y)
775{
776 using namespace std;
777 node_ptr delete_node = find_node(x, y);
778 if (!delete_node)
779 // No node exists at this coordinate.
780 return;
781
782#if DEBUG_POINT_QUAD_TREE
783 cout << "found the node to be removed at " << delete_node->x << "," << delete_node->y << " (" << *delete_node->data
784 << ")" << endl;
785#endif
786
787 // Check if this is a leaf node, in which case we can just delete it
788 // without further processing.
789 if (delete_node->leaf())
790 {
791#if DEBUG_POINT_QUAD_TREE
792 cout << "deleting a leaf node." << endl;
793#endif
794 if (delete_node.get() == m_root.get())
795 m_root.reset();
796 else
797 disconnect_node_from_parent(delete_node);
798 delete_node.reset();
799 return;
800 }
801
802 node_ptr repl_node = find_replacement_node(x, y, delete_node);
803 if (!repl_node)
804 // Non-leaf node should have at least one replacement candidate.
805 throw general_error("failed to find a replacement candidate node.");
806
807 node_quadrant_t repl_quad = delete_node->get_quadrant(repl_node->x, repl_node->y);
808
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;
814
815 // Call the quadrant where the replacement node is quadrant I. Adjust the
816 // quadrants adjacent to quadrant I first, then adjust quadrant I
817 // afterwards.
818 switch (repl_quad)
819 {
820 case quad_northeast:
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);
824 break;
825 case quad_northwest:
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);
829 break;
830 case quad_southeast:
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);
834 break;
835 case quad_southwest:
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);
839 break;
840 default:
841 throw general_error("quadrant for the replacement node is unspecified.");
842 }
843
844 // Reinsert all child nodes from the replacement node into the node to be
845 // "deleted".
846 switch (repl_quad)
847 {
848 case quad_northeast:
849 case quad_southwest:
850 {
851 node_ptr root = repl_node->northwest;
852 repl_node->northwest.reset();
853 reinsert_tree(delete_node, quad_northwest, root);
854
855 root = repl_node->southeast;
856 repl_node->southeast.reset();
857 reinsert_tree(delete_node, quad_southeast, root);
858 }
859 break;
860 case quad_northwest:
861 case quad_southeast:
862 {
863 node_ptr root = repl_node->northeast;
864 repl_node->northeast.reset();
865 reinsert_tree(delete_node, quad_northeast, root);
866
867 root = repl_node->southwest;
868 repl_node->southwest.reset();
869 reinsert_tree(delete_node, quad_southwest, root);
870 }
871 break;
872 default:
873 throw general_error("quadrant for the replacement node is unspecified.");
874 }
875
876 // Finally, replace the node to be removed with the replacement node.
877 delete_node->x = repl_node->x;
878 delete_node->y = repl_node->y;
879 delete_node->data = repl_node->data;
880
881 // Reset the parent node.
882 delete_node->parent = repl_node->parent;
883 repl_node->parent.reset();
884
885 switch (repl_quad)
886 {
887 case quad_northeast:
888 delete_node->northeast = repl_node->northeast;
889 repl_node->northeast.reset();
890 break;
891 case quad_northwest:
892 delete_node->northwest = repl_node->northwest;
893 repl_node->northwest.reset();
894 break;
895 case quad_southeast:
896 delete_node->southeast = repl_node->southeast;
897 repl_node->southeast.reset();
898 break;
899 case quad_southwest:
900 delete_node->southwest = repl_node->southwest;
901 repl_node->southwest.reset();
902 break;
903 default:
904 throw general_error("quadrant for the replacement node is unspecified.");
905 }
906
907 // Lastly, re-insert all those trees that have been cut during the quad
908 // adjustment into the new root.
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);
912}
913
914template<typename _Key, typename _Value>
916{
917 m_root.swap(r.m_root);
918 ::std::swap(m_xrange, r.m_xrange);
919 ::std::swap(m_yrange, r.m_yrange);
920}
921
922template<typename _Key, typename _Value>
924{
925 clear_all_nodes();
926}
927
928template<typename _Key, typename _Value>
930{
931 return (m_root.get() == nullptr);
932}
933
934template<typename _Key, typename _Value>
936{
937 size_t node_count = 0;
938 count_all_nodes(m_root.get(), node_count);
939 return node_count;
940}
941
942template<typename _Key, typename _Value>
944{
945 return node_access(m_root.get());
946}
947
948template<typename _Key, typename _Value>
950{
951 m_xrange = key_range_type(0, 0);
952 m_yrange = key_range_type(0, 0);
953 clear_all_nodes();
954 insert_data_from(r);
955 return *this;
956}
957
958template<typename _Key, typename _Value>
959bool point_quad_tree<_Key, _Value>::operator==(const point_quad_tree& r) const
960{
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);
965}
966
967template<typename _Key, typename _Value>
968void point_quad_tree<_Key, _Value>::dump_tree_svg(const ::std::string& fpath) const
969{
970 using namespace std;
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\" "
973 "version=\"1.1\">"
974 << endl;
975 file << "<defs>"
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\" />"
982 << " </marker>"
983 << "</defs>" << endl;
984
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;
991}
992
993template<typename _NodePtr>
994void draw_svg_arrow(::std::ofstream& file, const _NodePtr start, const _NodePtr end)
995{
996 using namespace std;
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;
1001}
1002
1003template<typename _Key, typename _Value>
1004void point_quad_tree<_Key, _Value>::dump_node_svg(const node* p, ::std::ofstream& file) const
1005{
1006 using namespace std;
1007
1008 if (!p)
1009 return;
1010
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;
1015
1016 if (p->northwest)
1017 draw_svg_arrow<const node*>(file, p, p->northwest.get());
1018
1019 if (p->northeast)
1020 draw_svg_arrow<const node*>(file, p, p->northeast.get());
1021
1022 if (p->southwest)
1023 draw_svg_arrow<const node*>(file, p, p->southwest.get());
1024
1025 if (p->southeast)
1026 draw_svg_arrow<const node*>(file, p, p->southeast.get());
1027
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);
1032}
1033
1034template<typename _Key, typename _Value>
1035bool point_quad_tree<_Key, _Value>::equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2)
1036{
1037 using namespace std;
1038
1039 if (v1.size() != v2.size())
1040 return false;
1041
1042 sort(v1.begin(), v1.end(), typename node_data::sorter());
1043 sort(v2.begin(), v2.end(), typename node_data::sorter());
1044
1045 typename vector<node_data>::const_iterator itr1 = v1.begin(), itr1_end = v1.end(), itr2 = v2.begin(),
1046 itr2_end = v2.end();
1047
1048 for (; itr1 != itr1_end; ++itr1, ++itr2)
1049 {
1050 if (itr2 == itr2_end)
1051 return false;
1052
1053 if (*itr1 != *itr2)
1054 return false;
1055 }
1056 if (itr2 != itr2_end)
1057 return false;
1058
1059 return true;
1060}
1061
1062template<typename _Key, typename _Value>
1063void point_quad_tree<_Key, _Value>::get_all_stored_data(::std::vector<node_data>& stored_data) const
1064{
1065 stored_data.clear();
1066 if (!m_root)
1067 return;
1068
1069 get_all_stored_data(m_root.get(), stored_data);
1070}
1071
1072template<typename _Key, typename _Value>
1073void point_quad_tree<_Key, _Value>::count_all_nodes(const node* p, size_t& node_count) const
1074{
1075 if (!p)
1076 return;
1077
1078 ++node_count;
1079
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);
1084}
1085
1086template<typename _Key, typename _Value>
1087void point_quad_tree<_Key, _Value>::insert_data_from(const point_quad_tree& r)
1088{
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));
1093}
1094
1095template<typename _Key, typename _Value>
1096bool point_quad_tree<_Key, _Value>::verify_data(::std::vector<node_data>& expected) const
1097{
1098 ::std::vector<node_data> stored;
1099 get_all_stored_data(stored);
1100 return equals(stored, expected);
1101}
1102
1103template<typename _Key, typename _Value>
1104bool point_quad_tree<_Key, _Value>::verify_node_iterator(const node_access& nac) const
1105{
1106 return verify_node_iterator(nac, m_root.get());
1107}
1108
1109template<typename _Key, typename _Value>
1110bool point_quad_tree<_Key, _Value>::verify_node_iterator(const node_access& nac, const node* p)
1111{
1112 if (!nac)
1113 return (p == nullptr);
1114
1115 if (!p)
1116 return false;
1117
1118 if (!verify_node_iterator(nac.northeast(), p->northeast.get()))
1119 return false;
1120 if (!verify_node_iterator(nac.northwest(), p->northwest.get()))
1121 return false;
1122 if (!verify_node_iterator(nac.southeast(), p->southeast.get()))
1123 return false;
1124 if (!verify_node_iterator(nac.southwest(), p->southwest.get()))
1125 return false;
1126
1127 return true;
1128}
1129
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
1132{
1133 if (!p)
1134 return;
1135
1136 stored_data.push_back(node_data(p->x, p->y, p->data));
1137
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);
1142}
1143
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
1146{
1147 node_ptr cur_node = m_root;
1148 while (cur_node)
1149 {
1150 if (cur_node->x == x && cur_node->y == y)
1151 {
1152 // Found the node.
1153 return cur_node;
1154 }
1155
1156 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1157 switch (quad)
1158 {
1159 case quad_northeast:
1160 if (!cur_node->northeast)
1161 return node_ptr();
1162 cur_node = cur_node->northeast;
1163 break;
1164 case quad_northwest:
1165 if (!cur_node->northwest)
1166 return node_ptr();
1167 cur_node = cur_node->northwest;
1168 break;
1169 case quad_southeast:
1170 if (!cur_node->southeast)
1171 return node_ptr();
1172 cur_node = cur_node->southeast;
1173 break;
1174 case quad_southwest:
1175 if (!cur_node->southwest)
1176 return node_ptr();
1177 cur_node = cur_node->southwest;
1178 break;
1179 default:
1180 throw general_error("unknown quadrant");
1181 }
1182 }
1183 return node_ptr();
1184}
1185
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
1189{
1190 const node* cur_node = m_root.get();
1191 while (cur_node)
1192 {
1193 if (cur_node->x == x && cur_node->y == y)
1194 {
1195 // Found the node.
1196 return cur_node;
1197 }
1198
1199 node_quadrant_t quad = cur_node->get_quadrant(x, y);
1200 switch (quad)
1201 {
1202 case quad_northeast:
1203 if (!cur_node->northeast)
1204 return nullptr;
1205 cur_node = cur_node->northeast.get();
1206 break;
1207 case quad_northwest:
1208 if (!cur_node->northwest)
1209 return nullptr;
1210 cur_node = cur_node->northwest.get();
1211 break;
1212 case quad_southeast:
1213 if (!cur_node->southeast)
1214 return nullptr;
1215 cur_node = cur_node->southeast.get();
1216 break;
1217 case quad_southwest:
1218 if (!cur_node->southwest)
1219 return nullptr;
1220 cur_node = cur_node->southwest.get();
1221 break;
1222 default:
1223 throw general_error("unknown quadrant");
1224 }
1225 }
1226 return nullptr;
1227}
1228
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
1232{
1233 using namespace std;
1234
1235 // Try to get a replacement candidate in each quadrant.
1236 node_distance dx_node, dy_node, min_city_block_node;
1237
1238#if DEBUG_POINT_QUAD_TREE
1239 cout << "northeast" << endl;
1240#endif
1241 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northeast);
1242
1243#if DEBUG_POINT_QUAD_TREE
1244 cout << "northwest" << endl;
1245#endif
1246 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northwest);
1247
1248#if DEBUG_POINT_QUAD_TREE
1249 cout << "southwest" << endl;
1250#endif
1251 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southwest);
1252
1253#if DEBUG_POINT_QUAD_TREE
1254 cout << "southeast" << endl;
1255#endif
1256 find_candidate_in_quad(x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southeast);
1257
1258 // Check Criterion 1.
1259
1260#if DEBUG_POINT_QUAD_TREE
1261 if (dx_node.node)
1262 cout << "node closest to x axis: " << *dx_node.node->data << " (dx=" << dx_node.dist << ")" << endl;
1263
1264 if (dy_node.node)
1265 cout << "node closest to y axis: " << *dy_node.node->data << " (dy=" << dy_node.dist << ")" << endl;
1266#endif
1267
1268 if (dx_node.node == dy_node.node && ((dx_node.quad == quad_northwest) || (dx_node.quad == quad_southeast)))
1269 {
1270#if DEBUG_POINT_QUAD_TREE
1271 cout << "node that satisfies Criterion 1: " << *dx_node.node->data << endl;
1272#endif
1273 return dx_node.node;
1274 }
1275 else
1276 {
1277#if DEBUG_POINT_QUAD_TREE
1278 cout << "unable to find node that satisfies Criterion 1." << endl;
1279#endif
1280 }
1281
1282 // Move on to Criterion 2.
1283
1284 if (min_city_block_node.node)
1285 {
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;
1289#endif
1290 return min_city_block_node.node;
1291 }
1292
1293 return node_ptr();
1294}
1295
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
1300{
1301 using namespace std;
1302
1303 node_ptr repl_node = delete_node->get_quadrant_node(quad);
1304 if (!repl_node)
1305 {
1306 // No candidate in this quadrant.
1307#if DEBUG_POINT_QUAD_TREE
1308 cout << " no candidate in this quadrant" << endl;
1309#endif
1310 return;
1311 }
1312
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);
1316
1317#if DEBUG_POINT_QUAD_TREE
1318 cout << " candidate: " << repl_node->x << "," << repl_node->y << " (" << *repl_node->data << ")" << endl;
1319#endif
1320
1321 // Calculate its distance to each of the borders.
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;
1326#endif
1327
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);
1332
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);
1335}
1336
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)
1341{
1342 using namespace std;
1343
1344 if (!quad_root)
1345 return;
1346
1347#if DEBUG_POINT_QUAD_TREE
1348 cout << "adjust_quad: checking " << *quad_root->data << " (" << quad_root->x << "," << quad_root->y << ")" << endl;
1349#endif
1350
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))
1353 {
1354#if DEBUG_POINT_QUAD_TREE
1355 cout << " " << *quad_root->data << " is in the hatched region" << endl;
1356#endif
1357 // Insert the whole tree, including the root, into the insert list.
1358 disconnect_node_from_parent(quad_root);
1359 quad_root->parent.reset();
1360 insert_list.push_back(quad_root);
1361 return;
1362 }
1363
1364 switch (dir)
1365 {
1366 case dir_east:
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);
1369 break;
1370 case dir_north:
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);
1373 break;
1374 case dir_south:
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);
1377 break;
1378 case dir_west:
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);
1381 break;
1382 default:;
1383 }
1384}
1385
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)
1390{
1391 node_ptr cur_node = quad_root;
1392 while (cur_node)
1393 {
1394 switch (dir)
1395 {
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);
1399 break;
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);
1403 break;
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);
1407 break;
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);
1411 break;
1412 default:
1413 throw general_error("unspecified quadrant");
1414 }
1415 cur_node = cur_node->get_quadrant_node(dir);
1416 }
1417}
1418
1419template<typename _Key, typename _Value>
1420void point_quad_tree<_Key, _Value>::insert_node(node_ptr& dest, node_ptr& this_node)
1421{
1422 node_ptr cur_node = dest;
1423 while (true)
1424 {
1425 if (cur_node->x == this_node->x && cur_node->y == this_node->y)
1426 {
1427 // When inserting a node instance directly (likely as part of tree
1428 // re-insertion), we are not supposed to have another node at
1429 // identical position.
1430 throw general_error("node with identical position encountered.");
1431 }
1432
1433 node_quadrant_t quad = cur_node->get_quadrant(this_node->x, this_node->y);
1434 switch (quad)
1435 {
1436 case quad_northeast:
1437 if (cur_node->northeast)
1438 cur_node = cur_node->northeast;
1439 else
1440 {
1441 cur_node->northeast = this_node;
1442 this_node->parent = cur_node;
1443 return;
1444 }
1445 break;
1446 case quad_northwest:
1447 if (cur_node->northwest)
1448 cur_node = cur_node->northwest;
1449 else
1450 {
1451 cur_node->northwest = this_node;
1452 this_node->parent = cur_node;
1453 return;
1454 }
1455 break;
1456 case quad_southeast:
1457 if (cur_node->southeast)
1458 cur_node = cur_node->southeast;
1459 else
1460 {
1461 cur_node->southeast = this_node;
1462 this_node->parent = cur_node;
1463 return;
1464 }
1465 break;
1466 case quad_southwest:
1467 if (cur_node->southwest)
1468 cur_node = cur_node->southwest;
1469 else
1470 {
1471 cur_node->southwest = this_node;
1472 this_node->parent = cur_node;
1473 return;
1474 }
1475 break;
1476 default:
1477 throw general_error("unknown quadrant");
1478 }
1479 }
1480 assert(!"This should never be reached.");
1481}
1482
1483template<typename _Key, typename _Value>
1484void point_quad_tree<_Key, _Value>::reinsert_tree(node_ptr& dest, node_ptr& root)
1485{
1486 assert(dest); // Destination node should not be null.
1487
1488 if (!root)
1489 // Nothing to re-insert. Bail out.
1490 return;
1491
1492 if (root->northeast)
1493 {
1494 reinsert_tree(dest, root->northeast);
1495 root->northeast.reset();
1496 }
1497 if (root->northwest)
1498 {
1499 reinsert_tree(dest, root->northwest);
1500 root->northwest.reset();
1501 }
1502 if (root->southeast)
1503 {
1504 reinsert_tree(dest, root->southeast);
1505 root->southeast.reset();
1506 }
1507 if (root->southwest)
1508 {
1509 reinsert_tree(dest, root->southwest);
1510 root->southwest.reset();
1511 }
1512
1513 root->parent.reset();
1514 insert_node(dest, root);
1515}
1516
1517template<typename _Key, typename _Value>
1518void point_quad_tree<_Key, _Value>::reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root)
1519{
1520 if (!root)
1521 // Nothing to re-insert. Bail out.
1522 return;
1523
1524 switch (quad)
1525 {
1526 case quad_northeast:
1527 if (dest->northeast)
1528 reinsert_tree(dest->northeast, root);
1529 else
1530 {
1531 dest->northeast = root;
1532 root->parent = dest;
1533 }
1534 break;
1535 case quad_northwest:
1536 if (dest->northwest)
1537 reinsert_tree(dest->northwest, root);
1538 else
1539 {
1540 dest->northwest = root;
1541 root->parent = dest;
1542 }
1543 break;
1544 case quad_southeast:
1545 if (dest->southeast)
1546 reinsert_tree(dest->southeast, root);
1547 else
1548 {
1549 dest->southeast = root;
1550 root->parent = dest;
1551 }
1552 break;
1553 case quad_southwest:
1554 if (dest->southwest)
1555 reinsert_tree(dest->southwest, root);
1556 else
1557 {
1558 dest->southwest = root;
1559 root->parent = dest;
1560 }
1561 break;
1562 default:
1563 throw general_error("reinsert_tree: quadrant unspecified");
1564 }
1565}
1566
1567template<typename _Key, typename _Value>
1568void point_quad_tree<_Key, _Value>::clear_all_nodes()
1569{
1570 ::mdds::disconnect_all_nodes(m_root);
1571 m_root.reset();
1572}
1573
1574} // namespace mdds
1575
1576#endif
Definition: global.hpp:84
Definition: point_quad_tree.hpp:117
Definition: point_quad_tree.hpp:158
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