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(
54  const _NodeType* p, _Key x1, _Key y1, _Key x2, _Key y2, _Inserter& result)
55 {
56  using namespace std;
57 
58  if (!p)
59  return;
60 
61  search_region_space_t region = ::mdds::get_search_region_space(p, x1, y1, x2, y2);
62 
63  switch (region)
64  {
65  case region_center:
66  result(p);
67  search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
68  search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
69  search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
70  search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
71  break;
72  case region_east:
73  search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
74  search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
75  break;
76  case region_north:
77  search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
78  search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
79  break;
80  case region_northeast:
81  search_region_node(p->southwest.get(), x1, y1, x2, y2, result);
82  break;
83  case region_northwest:
84  search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
85  break;
86  case region_south:
87  search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
88  search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
89  break;
90  case region_southeast:
91  search_region_node(p->northwest.get(), x1, y1, x2, y2, result);
92  break;
93  case region_southwest:
94  search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
95  break;
96  case region_west:
97  search_region_node(p->northeast.get(), x1, y1, x2, y2, result);
98  search_region_node(p->southeast.get(), x1, y1, x2, y2, result);
99  break;
100  default:
101  throw general_error("unknown search region");
102  }
103 }
104 
105 
106 template<typename _Key, typename _Value>
108 {
109 private:
110  class search_result_inserter;
111 
112 public:
113  typedef _Key key_type;
114  typedef _Value value_type;
115  typedef size_t size_type;
116  typedef ::std::vector<value_type> data_array_type;
117 
118  class data_not_found : public ::std::exception {};
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) :
128  quad_node_base<node_ptr, node, key_type>(_x, _y),
129  data(_data) {}
130 
131  node(const node& r) :
132  quad_node_base<node_ptr, node, key_type>(r),
133  data(r.data) {}
134 
135  void dispose() {}
136 
137  bool operator== (const node& r) const
138  {
139  return quad_node_base<node_ptr, node, key_type>::operator ==(r) && data == r.data;
140  }
141 
142  node& operator= (const node& r)
143  {
145  data = r.data;
146  return *this;
147  }
148  };
149 
150  typedef ::std::vector<node_ptr> reinsert_tree_array_type;
151  typedef ::std::pair<key_type, key_type> key_range_type;
152 
153 public:
154 
160  {
161  friend class point_quad_tree<_Key,_Value>;
162  public:
163  node_access northeast() const { return node_access(mp->northeast.get()); }
164  node_access northwest() const { return node_access(mp->northwest.get()); }
165  node_access southeast() const { return node_access(mp->southeast.get()); }
166  node_access southwest() const { return node_access(mp->southwest.get()); }
167 
168  value_type data() const { return mp->data; }
169  key_type x() const { return mp->x; }
170  key_type y() const { return mp->y; }
171 
172  operator bool() const { return mp != nullptr; }
173  bool operator== (const node_access& r) const { return mp == r.mp; }
174 
175  node_access() : mp(nullptr) {}
176  ~node_access() {}
177 
178  private:
179  node_access(const node* p) : mp(p) {}
180 
181  private:
182  const node* mp;
183  };
184 
185  struct point
186  {
187  key_type x;
188  key_type y;
189  point(key_type _x, key_type _y) : x(_x), y(_y) {}
190  point() : x(0), y(0) {}
191  };
192 
194  {
195  friend class search_result_inserter;
196 
197  typedef std::vector<const node*> res_nodes_type;
198  typedef std::shared_ptr<res_nodes_type> res_nodes_ptr;
199  public:
200 
202  {
203  friend class point_quad_tree<_Key,_Value>::search_results;
204  typedef typename point_quad_tree<_Key,_Value>::point point;
205  typedef typename point_quad_tree<_Key,_Value>::value_type parent_value_type;
206 
207  public:
208  // Iterator traits
209  typedef std::pair<point, parent_value_type> value_type;
210  typedef value_type* pointer;
211  typedef value_type& reference;
212  typedef ptrdiff_t difference_type;
213  typedef ::std::bidirectional_iterator_tag iterator_category;
214 
215  const_iterator(res_nodes_ptr& ptr) : mp_res_nodes(ptr), m_end_pos(false) {}
216 
217  const_iterator(const const_iterator& r) :
218  mp_res_nodes(r.mp_res_nodes),
219  m_cur_pos(r.m_cur_pos),
220  m_cur_value(r.m_cur_value),
221  m_end_pos(r.m_end_pos) {}
222 
223  const_iterator& operator= (const const_iterator& r)
224  {
225  mp_res_nodes = r.mp_res_nodes;
226  m_cur_pos = r.m_cur_pos;
227  m_cur_value = r.m_cur_value;
228  m_end_pos = r.m_end_pos;
229  return *this;
230  }
231 
232  bool operator== (const const_iterator& r) const
233  {
234  if (mp_res_nodes)
235  {
236  // Non-empty result set.
237  return mp_res_nodes.get() == r.mp_res_nodes.get() &&
238  m_cur_pos == r.m_cur_pos && m_end_pos == r.m_end_pos;
239  }
240 
241  // Empty result set.
242  if (r.mp_res_nodes)
243  return false;
244 
245  return m_end_pos == r.m_end_pos;
246  }
247 
248  bool operator!= (const const_iterator& r) const
249  {
250  return !operator==(r);
251  }
252 
253  const value_type& operator*() const
254  {
255  return m_cur_value;
256  }
257 
258  const value_type* operator->() const
259  {
260  return get_current_value();
261  }
262 
263  const value_type* operator++()
264  {
265  // The only difference between the last data position and the
266  // end iterator position must be the value of m_end_pos;
267  // m_cur_pos needs to point to the last data position even
268  // when the iterator is at the end-of-iterator position.
269 
270  typename res_nodes_type::const_iterator cur_pos = m_cur_pos;
271  if (++cur_pos == mp_res_nodes->end())
272  {
273  m_end_pos = true;
274  return nullptr;
275  }
276  m_cur_pos = cur_pos;
277  update_current_value();
278  return operator->();
279  }
280 
281  const value_type* operator--()
282  {
283  if (m_end_pos)
284  {
285  m_end_pos = false;
286  return get_current_value();
287  }
288  --m_cur_pos;
289  update_current_value();
290  return get_current_value();
291  }
292 
293  private:
294  void move_to_front()
295  {
296  if (!mp_res_nodes)
297  {
298  // Empty data set.
299  m_end_pos = true;
300  return;
301  }
302 
303  m_cur_pos = mp_res_nodes->begin();
304  m_end_pos = false;
305  update_current_value();
306  }
307 
308  void move_to_end()
309  {
310  m_end_pos = true;
311  if (!mp_res_nodes)
312  // Empty data set.
313  return;
314 
315  m_cur_pos = mp_res_nodes->end();
316  --m_cur_pos; // Keep the position at the last data position.
317  }
318 
319  void update_current_value()
320  {
321  const node* p = *m_cur_pos;
322  m_cur_value.first = point(p->x, p->y);
323  m_cur_value.second = p->data;
324  }
325 
326  const value_type* get_current_value() const
327  {
328  return &m_cur_value;
329  }
330 
331  private:
332  res_nodes_ptr mp_res_nodes;
333  typename res_nodes_type::const_iterator m_cur_pos;
334  value_type m_cur_value;
335  bool m_end_pos:1;
336  };
337 
338  search_results() : mp_res_nodes(static_cast<res_nodes_type*>(nullptr)) {}
339  search_results(const search_results& r) : mp_res_nodes(r.mp_res_nodes) {}
340 
341  typename search_results::const_iterator begin()
342  {
343  typename search_results::const_iterator itr(mp_res_nodes);
344  itr.move_to_front();
345  return itr;
346  }
347 
348  typename search_results::const_iterator end()
349  {
350  typename search_results::const_iterator itr(mp_res_nodes);
351  itr.move_to_end();
352  return itr;
353  }
354 
355  private:
356  void push_back(const node* p)
357  {
358  if (!mp_res_nodes)
359  mp_res_nodes.reset(new res_nodes_type);
360  mp_res_nodes->push_back(p);
361  }
362 
363  private:
364  res_nodes_ptr mp_res_nodes;
365  };
366 
367  point_quad_tree();
368  point_quad_tree(const point_quad_tree& r);
369  ~point_quad_tree();
370 
379  void insert(key_type x, key_type y, value_type data);
380 
393  void search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result) const;
394 
408  search_results search_region(key_type x1, key_type y1, key_type x2, key_type y2) const;
409 
420  value_type find(key_type x, key_type y) const;
421 
429  void remove(key_type x, key_type y);
430 
436  void swap(point_quad_tree& r);
437 
441  void clear();
442 
448  bool empty() const;
449 
455  size_t size() const;
456 
462  node_access get_node_access() const;
463 
464  point_quad_tree& operator= (const point_quad_tree& r);
465 
466  bool operator== (const point_quad_tree& r) const;
467 
468  bool operator!= (const point_quad_tree& r) const { return !operator== (r); }
469 
470 #ifdef MDDS_UNIT_TEST
471 public:
472 #else
473 private:
474 #endif
479  struct node_data
480  {
481  key_type x;
482  key_type y;
483  value_type data;
484  node_data(key_type _x, key_type _y, value_type _data) :
485  x(_x), y(_y), data(_data) {}
486  node_data(const node_data& r) :
487  x(r.x), y(r.y), data(r.data) {}
488 
489  bool operator== (const node_data& r) const
490  {
491  return (x == r.x) && (y == r.y) && (data == r.data);
492  }
493 
494  bool operator!= (const node_data& r) const
495  {
496  return !operator==(r);
497  }
498 
499  struct sorter
500  {
501  bool operator() (const node_data& left, const node_data& right) const
502  {
503  if (left.x != right.x)
504  return left.x < right.x;
505  if (left.y != right.y)
506  return left.y < right.y;
507  return left.data < right.data;
508  }
509  };
510  };
511 
512  static bool equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2);
513 
514  bool verify_data(::std::vector<node_data>& expected) const;
515 
516  bool verify_node_iterator(const node_access& nac) const;
517  static bool verify_node_iterator(const node_access& nac, const node* p);
518 
519  void get_all_stored_data(::std::vector<node_data>& stored_data) const;
520 
521  void dump_tree_svg(const ::std::string& fpath) const;
522 
523 private:
524  class array_inserter
525  {
526  public:
527  array_inserter(data_array_type& result) : m_result(result) {}
528 
529  void operator() (const node* p)
530  {
531  m_result.push_back(p->data);
532  }
533  private:
534  data_array_type& m_result;
535  };
536 
537  class search_result_inserter
538  {
539  public:
540  search_result_inserter(search_results& result) : m_result(result) {}
541 
542  void operator() (const node* p)
543  {
544  m_result.push_back(p);
545  }
546  private:
547  search_results& m_result;
548  };
549 
550  class data_inserter
551  {
552  public:
553  data_inserter(point_quad_tree& db) : m_db(db) {}
554 
555  void operator() (const node_data& v)
556  {
557  m_db.insert(v.x, v.y, v.data);
558  }
559  private:
560  point_quad_tree& m_db;
561  };
562 
563  struct node_distance
564  {
565  node_quadrant_t quad;
566  key_type dist;
567  node_ptr node;
568 
569  node_distance() : quad(quad_unspecified), dist(0), node(nullptr) {}
570  node_distance(node_quadrant_t _quad, key_type _dist, const node_ptr& _node) :
571  quad(_quad), dist(_dist), node(_node) {}
572  };
573 
574  node_ptr find_node(key_type x, key_type y) const;
575  const node* find_node_ptr(key_type x, key_type y) const;
576  node_ptr find_replacement_node(key_type x, key_type y, const node_ptr& delete_node) const;
577 
578  void find_candidate_in_quad(key_type x, key_type y,
579  node_distance& dx_node, node_distance& dy_node, node_distance& min_city_block_node,
580  const node_ptr& delete_node, node_quadrant_t quad) const;
581 
582  void adjust_quad(const key_range_type& hatched_xrange, const key_range_type& hatched_yrange,
583  node_ptr quad_root, direction_t dir, reinsert_tree_array_type& insert_list);
584 
585  void set_new_root(const key_range_type& hatched_xrange, const key_range_type& hatched_yrange,
586  node_ptr& quad_root, node_quadrant_t dir, reinsert_tree_array_type& insert_list);
587 
588  void insert_node(node_ptr& dest, node_ptr& node);
589  void reinsert_tree(node_ptr& dest, node_ptr& root);
590  void reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root);
591  void clear_all_nodes();
592  void dump_node_svg(const node* p, ::std::ofstream& file) const;
593  void count_all_nodes(const node* p, size_t& node_count) const;
594  void insert_data_from(const point_quad_tree& r);
595  void get_all_stored_data(const node* p, ::std::vector<node_data>& stored_data) const;
596 
597 private:
598  node_ptr m_root;
599 
600  key_range_type m_xrange;
601  key_range_type m_yrange;
602 };
603 
604 template<typename _Key, typename _Value>
605 point_quad_tree<_Key,_Value>::point_quad_tree() :
606  m_root(nullptr),
607  m_xrange(0,0),
608  m_yrange(0,0)
609 {
610 }
611 
612 template<typename _Key, typename _Value>
613 point_quad_tree<_Key,_Value>::point_quad_tree(const point_quad_tree& r) :
614  m_root(nullptr),
615  m_xrange(0,0),
616  m_yrange(0,0)
617 {
618  insert_data_from(r);
619 }
620 
621 template<typename _Key, typename _Value>
622 point_quad_tree<_Key,_Value>::~point_quad_tree()
623 {
624  clear_all_nodes();
625 }
626 
627 template<typename _Key, typename _Value>
628 void point_quad_tree<_Key,_Value>::insert(key_type x, key_type y, value_type data)
629 {
630  m_xrange.first = ::std::min(m_xrange.first, x);
631  m_xrange.second = ::std::max(m_xrange.second, x);
632  m_yrange.first = ::std::min(m_yrange.first, y);
633  m_yrange.second = ::std::max(m_yrange.second, y);
634 
635  if (!m_root)
636  {
637  // The very first node.
638  m_root.reset(new node(x, y, data));
639  return;
640  }
641 
642  node_ptr cur_node = m_root;
643  while (true)
644  {
645  if (cur_node->x == x && cur_node->y == y)
646  {
647  // Replace the current data with this, and we are done!
648  cur_node->data = data;
649  return;
650  }
651 
652  node_quadrant_t quad = cur_node->get_quadrant(x, y);
653  switch (quad)
654  {
655  case quad_northeast:
656  if (cur_node->northeast)
657  cur_node = cur_node->northeast;
658  else
659  {
660  cur_node->northeast.reset(new node(x, y, data));
661  cur_node->northeast->parent = cur_node;
662  return;
663  }
664  break;
665  case quad_northwest:
666  if (cur_node->northwest)
667  cur_node = cur_node->northwest;
668  else
669  {
670  cur_node->northwest.reset(new node(x, y, data));
671  cur_node->northwest->parent = cur_node;
672  return;
673  }
674  break;
675  case quad_southeast:
676  if (cur_node->southeast)
677  cur_node = cur_node->southeast;
678  else
679  {
680  cur_node->southeast.reset(new node(x, y, data));
681  cur_node->southeast->parent = cur_node;
682  return;
683  }
684  break;
685  case quad_southwest:
686  if (cur_node->southwest)
687  cur_node = cur_node->southwest;
688  else
689  {
690  cur_node->southwest.reset(new node(x, y, data));
691  cur_node->southwest->parent = cur_node;
692  return;
693  }
694  break;
695  default:
696  throw general_error("unknown quadrant");
697  }
698  }
699  assert(!"This should never be reached.");
700 }
701 
702 template<typename _Key, typename _Value>
703 void point_quad_tree<_Key,_Value>::search_region(key_type x1, key_type y1, key_type x2, key_type y2, data_array_type& result) const
704 {
705  using namespace std;
706  const node* p = m_root.get();
707  array_inserter _inserter(result);
708  ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
709 }
710 
711 template<typename _Key, typename _Value>
713 point_quad_tree<_Key,_Value>::search_region(key_type x1, key_type y1, key_type x2, key_type y2) const
714 {
715  using namespace std;
716  search_results result;
717  const node* p = m_root.get();
718  search_result_inserter _inserter(result);
719  ::mdds::search_region_node(p, x1, y1, x2, y2, _inserter);
720  return result;
721 }
722 
723 template<typename _Key, typename _Value>
724 typename point_quad_tree<_Key,_Value>::value_type
725 point_quad_tree<_Key,_Value>::find(key_type x, key_type y) const
726 {
727  const node* p = find_node_ptr(x, y);
728  if (!p)
729  throw data_not_found();
730  return p->data;
731 }
732 
733 template<typename _Key, typename _Value>
734 void point_quad_tree<_Key,_Value>::remove(key_type x, key_type y)
735 {
736  using namespace std;
737  node_ptr delete_node = find_node(x, y);
738  if (!delete_node)
739  // No node exists at this coordinate.
740  return;
741 
742 #if DEBUG_POINT_QUAD_TREE
743  cout << "found the node to be removed at " << delete_node->x << "," << delete_node->y << " (" << *delete_node->data << ")" << endl;
744 #endif
745 
746  // Check if this is a leaf node, in which case we can just delete it
747  // without further processing.
748  if (delete_node->leaf())
749  {
750 #if DEBUG_POINT_QUAD_TREE
751  cout << "deleting a leaf node." << endl;
752 #endif
753  if (delete_node.get() == m_root.get())
754  m_root.reset();
755  else
756  disconnect_node_from_parent(delete_node);
757  delete_node.reset();
758  return;
759  }
760 
761  node_ptr repl_node = find_replacement_node(x, y, delete_node);
762  if (!repl_node)
763  // Non-leaf node should have at least one replacement candidate.
764  throw general_error("failed to find a replacement candidate node.");
765 
766  node_quadrant_t repl_quad = delete_node->get_quadrant(repl_node->x, repl_node->y);
767 
768  key_range_type xrange(delete_node->x, repl_node->x);
769  key_range_type yrange(delete_node->y, repl_node->y);
770  ensure_order(xrange);
771  ensure_order(yrange);
772  reinsert_tree_array_type insert_list;
773 
774  // Call the quadrant where the replacement node is quadrant I. Adjust the
775  // quadrants adjacent to quadrant I first, then adjust quadrant I
776  // afterwards.
777  switch (repl_quad)
778  {
779  case quad_northeast:
780  adjust_quad(xrange, yrange, delete_node->northwest, dir_south, insert_list);
781  adjust_quad(xrange, yrange, delete_node->southeast, dir_west, insert_list);
782  set_new_root(xrange, yrange, delete_node->northeast, quad_southwest, insert_list);
783  break;
784  case quad_northwest:
785  adjust_quad(xrange, yrange, delete_node->northeast, dir_south, insert_list);
786  adjust_quad(xrange, yrange, delete_node->southwest, dir_east, insert_list);
787  set_new_root(xrange, yrange, delete_node->northwest, quad_southeast, insert_list);
788  break;
789  case quad_southeast:
790  adjust_quad(xrange, yrange, delete_node->northeast, dir_west, insert_list);
791  adjust_quad(xrange, yrange, delete_node->southwest, dir_north, insert_list);
792  set_new_root(xrange, yrange, delete_node->southeast, quad_northwest, insert_list);
793  break;
794  case quad_southwest:
795  adjust_quad(xrange, yrange, delete_node->northwest, dir_east, insert_list);
796  adjust_quad(xrange, yrange, delete_node->southeast, dir_north, insert_list);
797  set_new_root(xrange, yrange, delete_node->southwest, quad_northeast, insert_list);
798  break;
799  default:
800  throw general_error("quadrant for the replacement node is unspecified.");
801  }
802 
803  // Reinsert all child nodes from the replacement node into the node to be
804  // "deleted".
805  switch (repl_quad)
806  {
807  case quad_northeast:
808  case quad_southwest:
809  {
810  node_ptr root = repl_node->northwest;
811  repl_node->northwest.reset();
812  reinsert_tree(delete_node, quad_northwest, root);
813 
814  root = repl_node->southeast;
815  repl_node->southeast.reset();
816  reinsert_tree(delete_node, quad_southeast, root);
817  }
818  break;
819  case quad_northwest:
820  case quad_southeast:
821  {
822  node_ptr root = repl_node->northeast;
823  repl_node->northeast.reset();
824  reinsert_tree(delete_node, quad_northeast, root);
825 
826  root = repl_node->southwest;
827  repl_node->southwest.reset();
828  reinsert_tree(delete_node, quad_southwest, root);
829  }
830  break;
831  default:
832  throw general_error("quadrant for the replacement node is unspecified.");
833  }
834 
835  // Finally, replace the node to be removed with the replacement node.
836  delete_node->x = repl_node->x;
837  delete_node->y = repl_node->y;
838  delete_node->data = repl_node->data;
839 
840  // Reset the parent node.
841  delete_node->parent = repl_node->parent;
842  repl_node->parent.reset();
843 
844  switch (repl_quad)
845  {
846  case quad_northeast:
847  delete_node->northeast = repl_node->northeast;
848  repl_node->northeast.reset();
849  break;
850  case quad_northwest:
851  delete_node->northwest = repl_node->northwest;
852  repl_node->northwest.reset();
853  break;
854  case quad_southeast:
855  delete_node->southeast = repl_node->southeast;
856  repl_node->southeast.reset();
857  break;
858  case quad_southwest:
859  delete_node->southwest = repl_node->southwest;
860  repl_node->southwest.reset();
861  break;
862  default:
863  throw general_error("quadrant for the replacement node is unspecified.");
864  }
865 
866  // Lastly, re-insert all those trees that have been cut during the quad
867  // adjustment into the new root.
868  typename reinsert_tree_array_type::iterator
869  itr = insert_list.begin(), itr_end = insert_list.end();
870  for (; itr != itr_end; ++itr)
871  reinsert_tree(delete_node, *itr);
872 }
873 
874 template<typename _Key, typename _Value>
876 {
877  m_root.swap(r.m_root);
878  ::std::swap(m_xrange, r.m_xrange);
879  ::std::swap(m_yrange, r.m_yrange);
880 }
881 
882 template<typename _Key, typename _Value>
884 {
885  clear_all_nodes();
886 }
887 
888 template<typename _Key, typename _Value>
890 {
891  return (m_root.get() == nullptr);
892 }
893 
894 template<typename _Key, typename _Value>
896 {
897  size_t node_count = 0;
898  count_all_nodes(m_root.get(), node_count);
899  return node_count;
900 }
901 
902 template<typename _Key, typename _Value>
905 {
906  return node_access(m_root.get());
907 }
908 
909 template<typename _Key, typename _Value>
911 {
912  m_xrange = key_range_type(0, 0);
913  m_yrange = key_range_type(0, 0);
914  clear_all_nodes();
915  insert_data_from(r);
916  return *this;
917 }
918 
919 template<typename _Key, typename _Value>
920 bool point_quad_tree<_Key,_Value>::operator== (const point_quad_tree& r) const
921 {
922  ::std::vector<node_data> v1, v2;
923  get_all_stored_data(v1);
924  r.get_all_stored_data(v2);
925  return equals(v1, v2);
926 }
927 
928 template<typename _Key, typename _Value>
929 void point_quad_tree<_Key,_Value>::dump_tree_svg(const ::std::string& fpath) const
930 {
931  using namespace std;
932  ofstream file(fpath.c_str());
933  file << "<svg width=\"60cm\" height=\"60cm\" viewBox=\"-2 -2 202 202\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">" << endl;
934  file << "<defs>"
935  << " <marker id=\"Triangle\""
936  << " viewBox=\"0 0 10 10\" refX=\"10\" refY=\"5\" "
937  << " markerUnits=\"strokeWidth\""
938  << " markerWidth=\"9\" markerHeight=\"6\""
939  << " orient=\"auto\">"
940  << " <path d=\"M 0 0 L 10 5 L 0 10 z\" />"
941  << " </marker>"
942  << "</defs>" << endl;
943 
944  file << "<path d=\"M 0 0 L 0 " << m_yrange.second + 1 << "\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
945  file << "<path d=\"M 0 0 L " << m_xrange.second + 1 << " 0\" stroke=\"blue\" stroke-width=\"0.2\" marker-end=\"url(#Triangle)\"/>" << endl;
946  dump_node_svg(m_root.get(), file);
947  file << "</svg>" << endl;
948 }
949 
950 template<typename _NodePtr>
951 void draw_svg_arrow(::std::ofstream& file, const _NodePtr start, const _NodePtr end)
952 {
953  using namespace std;
954  file << "<g stroke=\"red\" marker-end=\"url(#Triangle)\">" << endl;
955  file << "<line x1=\"" << start->x << "\" y1=\"" << start->y << "\" x2=\""
956  << end->x << "\" y2=\"" << end->y << "\" stroke-width=\"0.2\"/>" << endl;
957  file << "</g>" << endl;
958 }
959 
960 template<typename _Key, typename _Value>
961 void point_quad_tree<_Key,_Value>::dump_node_svg(const node* p, ::std::ofstream& file) const
962 {
963  using namespace std;
964 
965  if (!p)
966  return;
967 
968  file << "<circle cx=\"" << p->x << "\" cy=\"" << p->y << "\" r=\"0.1\""
969  << " fill=\"black\" stroke=\"black\"/>" << endl;
970  file << "<text x=\"" << p->x + 1 << "\" y=\"" << p->y + 2 << "\" font-size=\"1.2\" fill=\"black\">"
971  << *p->data << " (" << p->x << "," << p->y << ")</text>" << endl;
972 
973  if (p->northwest)
974  draw_svg_arrow<const node*>(file, p, p->northwest.get());
975 
976  if (p->northeast)
977  draw_svg_arrow<const node*>(file, p, p->northeast.get());
978 
979  if (p->southwest)
980  draw_svg_arrow<const node*>(file, p, p->southwest.get());
981 
982  if (p->southeast)
983  draw_svg_arrow<const node*>(file, p, p->southeast.get());
984 
985  dump_node_svg(p->northeast.get(), file);
986  dump_node_svg(p->northwest.get(), file);
987  dump_node_svg(p->southeast.get(), file);
988  dump_node_svg(p->southwest.get(), file);
989 }
990 
991 template<typename _Key, typename _Value>
992 bool point_quad_tree<_Key,_Value>::equals(::std::vector<node_data>& v1, ::std::vector<node_data>& v2)
993 {
994  using namespace std;
995 
996  if (v1.size() != v2.size())
997  return false;
998 
999  sort(v1.begin(), v1.end(), typename node_data::sorter());
1000  sort(v2.begin(), v2.end(), typename node_data::sorter());
1001 
1002  typename vector<node_data>::const_iterator
1003  itr1 = v1.begin(), itr1_end = v1.end(), itr2 = v2.begin(), itr2_end = v2.end();
1004 
1005  for (; itr1 != itr1_end; ++itr1, ++itr2)
1006  {
1007  if (itr2 == itr2_end)
1008  return false;
1009 
1010  if (*itr1 != *itr2)
1011  return false;
1012  }
1013  if (itr2 != itr2_end)
1014  return false;
1015 
1016  return true;
1017 }
1018 
1019 template<typename _Key, typename _Value>
1020 void point_quad_tree<_Key,_Value>::get_all_stored_data(::std::vector<node_data>& stored_data) const
1021 {
1022  stored_data.clear();
1023  if (!m_root)
1024  return;
1025 
1026  get_all_stored_data(m_root.get(), stored_data);
1027 }
1028 
1029 template<typename _Key, typename _Value>
1030 void point_quad_tree<_Key,_Value>::count_all_nodes(const node* p, size_t& node_count) const
1031 {
1032  if (!p)
1033  return;
1034 
1035  ++node_count;
1036 
1037  count_all_nodes(p->northeast.get(), node_count);
1038  count_all_nodes(p->northwest.get(), node_count);
1039  count_all_nodes(p->southeast.get(), node_count);
1040  count_all_nodes(p->southwest.get(), node_count);
1041 }
1042 
1043 template<typename _Key, typename _Value>
1044 void point_quad_tree<_Key,_Value>::insert_data_from(const point_quad_tree& r)
1045 {
1046  using namespace std;
1047  vector<node_data> all_data;
1048  r.get_all_stored_data(all_data);
1049  for_each(all_data.begin(), all_data.end(), data_inserter(*this));
1050 }
1051 
1052 template<typename _Key, typename _Value>
1053 bool point_quad_tree<_Key,_Value>::verify_data(::std::vector<node_data>& expected) const
1054 {
1055  ::std::vector<node_data> stored;
1056  get_all_stored_data(stored);
1057  return equals(stored, expected);
1058 }
1059 
1060 template<typename _Key, typename _Value>
1061 bool point_quad_tree<_Key,_Value>::verify_node_iterator(const node_access& nac) const
1062 {
1063  return verify_node_iterator(nac, m_root.get());
1064 }
1065 
1066 template<typename _Key, typename _Value>
1067 bool point_quad_tree<_Key,_Value>::verify_node_iterator(const node_access& nac, const node* p)
1068 {
1069  if (!nac)
1070  return (p == nullptr);
1071 
1072  if (!p)
1073  return false;
1074 
1075  if (!verify_node_iterator(nac.northeast(), p->northeast.get()))
1076  return false;
1077  if (!verify_node_iterator(nac.northwest(), p->northwest.get()))
1078  return false;
1079  if (!verify_node_iterator(nac.southeast(), p->southeast.get()))
1080  return false;
1081  if (!verify_node_iterator(nac.southwest(), p->southwest.get()))
1082  return false;
1083 
1084  return true;
1085 }
1086 
1087 template<typename _Key, typename _Value>
1088 void point_quad_tree<_Key,_Value>::get_all_stored_data(const node* p, ::std::vector<node_data>& stored_data) const
1089 {
1090  if (!p)
1091  return;
1092 
1093  stored_data.push_back(node_data(p->x, p->y, p->data));
1094 
1095  get_all_stored_data(p->northeast.get(), stored_data);
1096  get_all_stored_data(p->northwest.get(), stored_data);
1097  get_all_stored_data(p->southeast.get(), stored_data);
1098  get_all_stored_data(p->southwest.get(), stored_data);
1099 }
1100 
1101 template<typename _Key, typename _Value>
1102 typename point_quad_tree<_Key,_Value>::node_ptr
1103 point_quad_tree<_Key,_Value>::find_node(key_type x, key_type y) const
1104 {
1105  node_ptr cur_node = m_root;
1106  while (cur_node)
1107  {
1108  if (cur_node->x == x && cur_node->y == y)
1109  {
1110  // Found the node.
1111  return cur_node;
1112  }
1113 
1114  node_quadrant_t quad = cur_node->get_quadrant(x, y);
1115  switch (quad)
1116  {
1117  case quad_northeast:
1118  if (!cur_node->northeast)
1119  return node_ptr();
1120  cur_node = cur_node->northeast;
1121  break;
1122  case quad_northwest:
1123  if (!cur_node->northwest)
1124  return node_ptr();
1125  cur_node = cur_node->northwest;
1126  break;
1127  case quad_southeast:
1128  if (!cur_node->southeast)
1129  return node_ptr();
1130  cur_node = cur_node->southeast;
1131  break;
1132  case quad_southwest:
1133  if (!cur_node->southwest)
1134  return node_ptr();
1135  cur_node = cur_node->southwest;
1136  break;
1137  default:
1138  throw general_error("unknown quadrant");
1139  }
1140  }
1141  return node_ptr();
1142 }
1143 
1144 template<typename _Key, typename _Value>
1145 const typename point_quad_tree<_Key,_Value>::node*
1146 point_quad_tree<_Key,_Value>::find_node_ptr(key_type x, key_type y) const
1147 {
1148  const node* cur_node = m_root.get();
1149  while (cur_node)
1150  {
1151  if (cur_node->x == x && cur_node->y == y)
1152  {
1153  // Found the node.
1154  return cur_node;
1155  }
1156 
1157  node_quadrant_t quad = cur_node->get_quadrant(x, y);
1158  switch (quad)
1159  {
1160  case quad_northeast:
1161  if (!cur_node->northeast)
1162  return nullptr;
1163  cur_node = cur_node->northeast.get();
1164  break;
1165  case quad_northwest:
1166  if (!cur_node->northwest)
1167  return nullptr;
1168  cur_node = cur_node->northwest.get();
1169  break;
1170  case quad_southeast:
1171  if (!cur_node->southeast)
1172  return nullptr;
1173  cur_node = cur_node->southeast.get();
1174  break;
1175  case quad_southwest:
1176  if (!cur_node->southwest)
1177  return nullptr;
1178  cur_node = cur_node->southwest.get();
1179  break;
1180  default:
1181  throw general_error("unknown quadrant");
1182  }
1183  }
1184  return nullptr;
1185 }
1186 
1187 template<typename _Key, typename _Value>
1188 typename point_quad_tree<_Key,_Value>::node_ptr
1189 point_quad_tree<_Key,_Value>::find_replacement_node(key_type x, key_type y, const node_ptr& delete_node) const
1190 {
1191  using namespace std;
1192 
1193  // Try to get a replacement candidate in each quadrant.
1194  node_distance dx_node, dy_node, min_city_block_node;
1195 
1196 #if DEBUG_POINT_QUAD_TREE
1197  cout << "northeast" << endl;
1198 #endif
1199  find_candidate_in_quad(
1200  x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northeast);
1201 
1202 #if DEBUG_POINT_QUAD_TREE
1203  cout << "northwest" << endl;
1204 #endif
1205  find_candidate_in_quad(
1206  x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_northwest);
1207 
1208 #if DEBUG_POINT_QUAD_TREE
1209  cout << "southwest" << endl;
1210 #endif
1211  find_candidate_in_quad(
1212  x, y, dx_node, dy_node, min_city_block_node, delete_node, quad_southwest);
1213 
1214 #if DEBUG_POINT_QUAD_TREE
1215  cout << "southeast" << endl;
1216 #endif
1217  find_candidate_in_quad(
1218  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 << " (dist=" << min_city_block_node.dist << ")" << endl;
1250 #endif
1251  return min_city_block_node.node;
1252  }
1253 
1254  return node_ptr();
1255 }
1256 
1257 template<typename _Key, typename _Value>
1258 void point_quad_tree<_Key,_Value>::find_candidate_in_quad(
1259  key_type x, key_type y,
1260  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 
1299 template<typename _Key, typename _Value>
1300 void point_quad_tree<_Key,_Value>::adjust_quad(
1301  const key_range_type& hatched_xrange, const key_range_type& hatched_yrange,
1302  node_ptr quad_root, direction_t dir, 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 }
1348 
1349 template<typename _Key, typename _Value>
1350 void point_quad_tree<_Key,_Value>::set_new_root(
1351  const key_range_type& hatched_xrange, const key_range_type& hatched_yrange,
1352  node_ptr& quad_root, node_quadrant_t dir, reinsert_tree_array_type& insert_list)
1353 {
1354  node_ptr cur_node = quad_root;
1355  while (cur_node)
1356  {
1357  switch (dir)
1358  {
1359  case quad_northeast:
1360  adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_east, insert_list);
1361  adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_north, insert_list);
1362  break;
1363  case quad_northwest:
1364  adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_north, insert_list);
1365  adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_west, insert_list);
1366  break;
1367  case quad_southeast:
1368  adjust_quad(hatched_xrange, hatched_yrange, cur_node->northeast, dir_east, insert_list);
1369  adjust_quad(hatched_xrange, hatched_yrange, cur_node->southwest, dir_south, insert_list);
1370  break;
1371  case quad_southwest:
1372  adjust_quad(hatched_xrange, hatched_yrange, cur_node->northwest, dir_west, insert_list);
1373  adjust_quad(hatched_xrange, hatched_yrange, cur_node->southeast, dir_south, insert_list);
1374  break;
1375  default:
1376  throw general_error("unspecified quadrant");
1377  }
1378  cur_node = cur_node->get_quadrant_node(dir);
1379  }
1380 }
1381 
1382 template<typename _Key, typename _Value>
1383 void point_quad_tree<_Key,_Value>::insert_node(node_ptr& dest, node_ptr& this_node)
1384 {
1385  node_ptr cur_node = dest;
1386  while (true)
1387  {
1388  if (cur_node->x == this_node->x && cur_node->y == this_node->y)
1389  {
1390  // When inserting a node instance directly (likely as part of tree
1391  // re-insertion), we are not supposed to have another node at
1392  // identical position.
1393  throw general_error("node with identical position encountered.");
1394  }
1395 
1396  node_quadrant_t quad = cur_node->get_quadrant(this_node->x, this_node->y);
1397  switch (quad)
1398  {
1399  case quad_northeast:
1400  if (cur_node->northeast)
1401  cur_node = cur_node->northeast;
1402  else
1403  {
1404  cur_node->northeast = this_node;
1405  this_node->parent = cur_node;
1406  return;
1407  }
1408  break;
1409  case quad_northwest:
1410  if (cur_node->northwest)
1411  cur_node = cur_node->northwest;
1412  else
1413  {
1414  cur_node->northwest = this_node;
1415  this_node->parent = cur_node;
1416  return;
1417  }
1418  break;
1419  case quad_southeast:
1420  if (cur_node->southeast)
1421  cur_node = cur_node->southeast;
1422  else
1423  {
1424  cur_node->southeast = this_node;
1425  this_node->parent = cur_node;
1426  return;
1427  }
1428  break;
1429  case quad_southwest:
1430  if (cur_node->southwest)
1431  cur_node = cur_node->southwest;
1432  else
1433  {
1434  cur_node->southwest = this_node;
1435  this_node->parent = cur_node;
1436  return;
1437  }
1438  break;
1439  default:
1440  throw general_error("unknown quadrant");
1441  }
1442  }
1443  assert(!"This should never be reached.");
1444 }
1445 
1446 template<typename _Key, typename _Value>
1447 void point_quad_tree<_Key,_Value>::reinsert_tree(node_ptr& dest, node_ptr& root)
1448 {
1449  assert(dest); // Destination node should not be null.
1450 
1451  if (!root)
1452  // Nothing to re-insert. Bail out.
1453  return;
1454 
1455  if (root->northeast)
1456  {
1457  reinsert_tree(dest, root->northeast);
1458  root->northeast.reset();
1459  }
1460  if (root->northwest)
1461  {
1462  reinsert_tree(dest, root->northwest);
1463  root->northwest.reset();
1464  }
1465  if (root->southeast)
1466  {
1467  reinsert_tree(dest, root->southeast);
1468  root->southeast.reset();
1469  }
1470  if (root->southwest)
1471  {
1472  reinsert_tree(dest, root->southwest);
1473  root->southwest.reset();
1474  }
1475 
1476  root->parent.reset();
1477  insert_node(dest, root);
1478 }
1479 
1480 template<typename _Key, typename _Value>
1481 void point_quad_tree<_Key,_Value>::reinsert_tree(node_ptr& dest, node_quadrant_t quad, node_ptr& root)
1482 {
1483  if (!root)
1484  // Nothing to re-insert. Bail out.
1485  return;
1486 
1487  switch (quad)
1488  {
1489  case quad_northeast:
1490  if (dest->northeast)
1491  reinsert_tree(dest->northeast, root);
1492  else
1493  {
1494  dest->northeast = root;
1495  root->parent = dest;
1496  }
1497  break;
1498  case quad_northwest:
1499  if (dest->northwest)
1500  reinsert_tree(dest->northwest, root);
1501  else
1502  {
1503  dest->northwest = root;
1504  root->parent = dest;
1505  }
1506  break;
1507  case quad_southeast:
1508  if (dest->southeast)
1509  reinsert_tree(dest->southeast, root);
1510  else
1511  {
1512  dest->southeast = root;
1513  root->parent = dest;
1514  }
1515  break;
1516  case quad_southwest:
1517  if (dest->southwest)
1518  reinsert_tree(dest->southwest, root);
1519  else
1520  {
1521  dest->southwest = root;
1522  root->parent = dest;
1523  }
1524  break;
1525  default:
1526  throw general_error("reinsert_tree: quadrant unspecified");
1527  }
1528 }
1529 
1530 template<typename _Key, typename _Value>
1531 void point_quad_tree<_Key,_Value>::clear_all_nodes()
1532 {
1533  ::mdds::disconnect_all_nodes(m_root);
1534  m_root.reset();
1535 }
1536 
1537 }
1538 
1539 #endif
Definition: global.hpp:82
Definition: point_quad_tree.hpp:118
Definition: point_quad_tree.hpp:160
Definition: point_quad_tree.hpp:194
Definition: point_quad_tree.hpp:108
void insert(key_type x, key_type y, value_type data)
Definition: point_quad_tree.hpp:628
void swap(point_quad_tree &r)
Definition: point_quad_tree.hpp:875
bool empty() const
Definition: point_quad_tree.hpp:889
size_t size() const
Definition: point_quad_tree.hpp:895
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:703
void clear()
Definition: point_quad_tree.hpp:883
void remove(key_type x, key_type y)
Definition: point_quad_tree.hpp:734
node_access get_node_access() const
Definition: point_quad_tree.hpp:904
value_type find(key_type x, key_type y) const
Definition: point_quad_tree.hpp:725
Definition: point_quad_tree.hpp:500
Definition: point_quad_tree.hpp:186
Definition: quad_node.hpp:119
quad_node_base & operator=(const quad_node_base &r)
Definition: quad_node.hpp:182