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 
43 namespace mdds {
44 
45 template<typename _PairType>
46 void ensure_order(_PairType& v)
47 {
48  if (v.first > v.second)
49  ::std::swap(v.first, v.second);
50 }
51 
52 template<typename _Key, typename _NodeType, typename _Inserter>
53 void 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 
104 template<typename _Key, typename _Value>
106 {
107 private:
108  class search_result_inserter;
109 
110 public:
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 
120 private:
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 
152 public:
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  {}
203  ~node_access()
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
507 public:
508 #else
509 private:
510 #endif
511 
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 
559 private:
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 
643 private:
644  node_ptr m_root;
645 
646  key_range_type m_xrange;
647  key_range_type m_yrange;
648 };
649 
650 template<typename _Key, typename _Value>
651 point_quad_tree<_Key, _Value>::point_quad_tree() : m_root(nullptr), m_xrange(0, 0), m_yrange(0, 0)
652 {}
653 
654 template<typename _Key, typename _Value>
655 point_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 
661 template<typename _Key, typename _Value>
662 point_quad_tree<_Key, _Value>::~point_quad_tree()
663 {
664  clear_all_nodes();
665 }
666 
667 template<typename _Key, typename _Value>
668 void 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 
742 template<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 
752 template<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 
764 template<typename _Key, typename _Value>
765 typename 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 
773 template<typename _Key, typename _Value>
774 void 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 
914 template<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 
922 template<typename _Key, typename _Value>
924 {
925  clear_all_nodes();
926 }
927 
928 template<typename _Key, typename _Value>
930 {
931  return (m_root.get() == nullptr);
932 }
933 
934 template<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 
942 template<typename _Key, typename _Value>
944 {
945  return node_access(m_root.get());
946 }
947 
948 template<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 
958 template<typename _Key, typename _Value>
959 bool 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 
967 template<typename _Key, typename _Value>
968 void 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 
993 template<typename _NodePtr>
994 void 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 
1003 template<typename _Key, typename _Value>
1004 void 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 
1034 template<typename _Key, typename _Value>
1035 bool 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 
1062 template<typename _Key, typename _Value>
1063 void 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 
1072 template<typename _Key, typename _Value>
1073 void 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 
1086 template<typename _Key, typename _Value>
1087 void 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 
1095 template<typename _Key, typename _Value>
1096 bool 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 
1103 template<typename _Key, typename _Value>
1104 bool 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 
1109 template<typename _Key, typename _Value>
1110 bool 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 
1130 template<typename _Key, typename _Value>
1131 void 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 
1144 template<typename _Key, typename _Value>
1145 typename 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 
1186 template<typename _Key, typename _Value>
1187 const 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 
1229 template<typename _Key, typename _Value>
1230 typename 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 
1296 template<typename _Key, typename _Value>
1297 void 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 
1337 template<typename _Key, typename _Value>
1338 void 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 
1386 template<typename _Key, typename _Value>
1387 void 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 
1419 template<typename _Key, typename _Value>
1420 void 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 
1483 template<typename _Key, typename _Value>
1484 void 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 
1517 template<typename _Key, typename _Value>
1518 void 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 
1567 template<typename _Key, typename _Value>
1568 void 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
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 remove(key_type x, key_type y)
Definition: point_quad_tree.hpp:774
Definition: point_quad_tree.hpp:157
void swap(point_quad_tree &r)
Definition: point_quad_tree.hpp:915
size_t size() const
Definition: point_quad_tree.hpp:935
Definition: point_quad_tree.hpp:214
Definition: point_quad_tree.hpp:224
Definition: point_quad_tree.hpp:105
void insert(key_type x, key_type y, value_type data)
Definition: point_quad_tree.hpp:668
void clear()
Definition: point_quad_tree.hpp:923
Definition: global.hpp:83
Definition: point_quad_tree.hpp:116
value_type find(key_type x, key_type y) const
Definition: point_quad_tree.hpp:765
bool empty() const
Definition: point_quad_tree.hpp:929
node_access get_node_access() const
Definition: point_quad_tree.hpp:943
Definition: flat_segment_tree.hpp:46
quad_node_base & operator=(const quad_node_base &r)
Definition: quad_node.hpp:169
Definition: point_quad_tree.hpp:535
Definition: quad_node.hpp:117