GEOS  3.9.0dev
AbstractSTRtree.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2006 Refractions Research Inc.
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU Lesser General Public Licence as published
10  * by the Free Software Foundation.
11  * See the COPYING file for more information.
12  *
13  **********************************************************************/
14 
15 #ifndef GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
16 #define GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
17 
18 #include <geos/export.h>
19 
20 #include <geos/index/strtree/AbstractNode.h> // for inlines
21 
22 #include <vector>
23 #include <list>
24 #include <memory> // for unique_ptr
25 #include <cassert> // for inlines
26 #include <algorithm>
27 
28 // Forward declarations
29 namespace geos {
30 namespace index {
31 class ItemVisitor;
32 namespace strtree {
33 class Boundable;
34 class AbstractNode;
35 }
36 }
37 }
38 
39 namespace geos {
40 namespace index { // geos::index
41 namespace strtree { // geos::index::strtree
42 
44 typedef std::vector<Boundable*> BoundableList;
45 
48 class ItemsList;
49 
50 class ItemsListItem {
51 public:
52  enum type {
53  item_is_geometry,
54  item_is_list
55  };
56 
57  ItemsListItem(void* item_)
58  : t(item_is_geometry)
59  {
60  item.g = item_;
61  }
62  ItemsListItem(ItemsList* item_)
63  : t(item_is_list)
64  {
65  item.l = item_;
66  }
67 
68  type
69  get_type() const
70  {
71  return t;
72  }
73 
74  void*
75  get_geometry() const
76  {
77  assert(t == item_is_geometry);
78  return item.g;
79  }
80  ItemsList*
81  get_itemslist() const
82  {
83  assert(t == item_is_list);
84  return item.l;
85  }
86 
87  type t;
88  union {
89  void* g;
90  ItemsList* l;
91  } item;
92 };
93 
94 class ItemsList : public std::vector<ItemsListItem> {
95 private:
96  typedef std::vector<ItemsListItem> base_type;
97 
98  static void
99  delete_item(ItemsListItem& item)
100  {
101  if(ItemsListItem::item_is_list == item.t) {
102  delete item.item.l;
103  }
104  }
105 
106 public:
107  ~ItemsList()
108  {
109  std::for_each(begin(), end(), &ItemsList::delete_item);
110  }
111 
112  // lists of items need to be deleted in the end
113  void
114  push_back(void* item)
115  {
116  this->base_type::push_back(ItemsListItem(item));
117  }
118 
119  // lists of items need to be deleted in the end
120  void
121  push_back_owned(ItemsList* itemList)
122  {
123  this->base_type::push_back(ItemsListItem(itemList));
124  }
125 };
126 
139 class GEOS_DLL AbstractSTRtree {
140 
141 private:
142  bool built;
143  BoundableList* itemBoundables;
144 
155  virtual AbstractNode* createHigherLevels(
156  BoundableList* boundablesOfALevel,
157  int level);
158 
159  virtual std::unique_ptr<BoundableList> sortBoundables(const BoundableList* input) = 0;
160 
161  bool remove(const void* searchBounds, AbstractNode& node, void* item);
162  bool removeItem(AbstractNode& node, void* item);
163 
164  ItemsList* itemsTree(AbstractNode* node);
165 
166  AbstractSTRtree(const AbstractSTRtree&) = delete;
167  AbstractSTRtree& operator=(const AbstractSTRtree&) = delete;
168 
169 protected:
170 
176  class GEOS_DLL IntersectsOp {
177  public:
186  virtual bool intersects(const void* aBounds,
187  const void* bBounds) = 0;
188 
189  virtual
190  ~IntersectsOp() {}
191  };
192 
193  AbstractNode* root;
194 
195  std::vector <AbstractNode*>* nodes;
196 
197  // Ownership to caller (TODO: return by unique_ptr)
198  virtual AbstractNode* createNode(int level) = 0;
199 
204  virtual std::unique_ptr<BoundableList> createParentBoundables(
205  BoundableList* childBoundables, int newLevel);
206 
207  virtual AbstractNode*
208  lastNode(BoundableList* nodeList)
209  {
210  assert(!nodeList->empty());
211  // Cast from Boundable to AbstractNode
212  return static_cast<AbstractNode*>(nodeList->back());
213  }
214 
215  virtual AbstractNode*
216  getRoot()
217  {
218  assert(built);
219  return root;
220  }
221 
223  virtual void insert(const void* bounds, void* item);
224 
226  void query(const void* searchBounds, std::vector<void*>& foundItems);
227 
229  void query(const void* searchBounds, ItemVisitor& visitor);
230 
231  void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
232 
234  bool remove(const void* itemEnv, void* item);
235 
236  std::unique_ptr<BoundableList> boundablesAtLevel(int level);
237 
238  // @@ should be size_t, probably
239  std::size_t nodeCapacity;
240 
247  virtual IntersectsOp* getIntersectsOp() = 0;
248 
249 
250 public:
251 
256  AbstractSTRtree(std::size_t newNodeCapacity)
257  :
258  built(false),
259  itemBoundables(new BoundableList()),
260  nodes(new std::vector<AbstractNode *>()),
261  nodeCapacity(newNodeCapacity)
262  {
263  assert(newNodeCapacity > 1);
264  }
265 
266  static bool
267  compareDoubles(double a, double b)
268  {
269  // NOTE - strk:
270  // Ternary operation is a workaround for
271  // a probable MingW bug, see
272  // http://trac.osgeo.org/geos/ticket/293
273  return (a < b) ? true : false;
274  }
275 
276  virtual ~AbstractSTRtree();
277 
286  virtual void build();
287 
291  virtual std::size_t
293  {
294  return nodeCapacity;
295  }
296 
297  virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
298 
303  void iterate(ItemVisitor& visitor);
304 
305 
311  virtual void boundablesAtLevel(int level, AbstractNode* top,
312  BoundableList* boundables);
313 
328  ItemsList* itemsTree();
329 };
330 
331 
332 } // namespace geos::index::strtree
333 } // namespace geos::index
334 } // namespace geos
335 
336 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
virtual std::size_t getNodeCapacity()
Returns the maximum number of child nodes that a node may have.
Definition: AbstractSTRtree.h:292
Base class for STRtree and SIRtree.
Definition: AbstractSTRtree.h:139
AbstractSTRtree(std::size_t newNodeCapacity)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have...
Definition: AbstractSTRtree.h:256
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition: AbstractSTRtree.h:176
A visitor for items in an index.
Definition: ItemVisitor.h:29
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26
A node of the STR tree.
Definition: AbstractNode.h:44
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition: AbstractSTRtree.h:44