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 protected:
167 
173  class GEOS_DLL IntersectsOp {
174  public:
183  virtual bool intersects(const void* aBounds,
184  const void* bBounds) = 0;
185 
186  virtual
187  ~IntersectsOp() {}
188  };
189 
190  AbstractNode* root;
191 
192  std::vector <AbstractNode*>* nodes;
193 
194  // Ownership to caller (TODO: return by unique_ptr)
195  virtual AbstractNode* createNode(int level) = 0;
196 
201  virtual std::unique_ptr<BoundableList> createParentBoundables(
202  BoundableList* childBoundables, int newLevel);
203 
204  virtual AbstractNode*
205  lastNode(BoundableList* nodeList)
206  {
207  assert(!nodeList->empty());
208  // Cast from Boundable to AbstractNode
209  return static_cast<AbstractNode*>(nodeList->back());
210  }
211 
212  virtual AbstractNode*
213  getRoot()
214  {
215  assert(built);
216  return root;
217  }
218 
220  virtual void insert(const void* bounds, void* item);
221 
223  void query(const void* searchBounds, std::vector<void*>& foundItems);
224 
226  void query(const void* searchBounds, ItemVisitor& visitor);
227 
228  void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
229 
231  bool remove(const void* itemEnv, void* item);
232 
233  std::unique_ptr<BoundableList> boundablesAtLevel(int level);
234 
235  // @@ should be size_t, probably
236  std::size_t nodeCapacity;
237 
244  virtual IntersectsOp* getIntersectsOp() = 0;
245 
246 
247 public:
248 
253  AbstractSTRtree(std::size_t newNodeCapacity)
254  :
255  built(false),
256  itemBoundables(new BoundableList()),
257  nodes(new std::vector<AbstractNode *>()),
258  nodeCapacity(newNodeCapacity)
259  {
260  assert(newNodeCapacity > 1);
261  }
262 
263  static bool
264  compareDoubles(double a, double b)
265  {
266  // NOTE - strk:
267  // Ternary operation is a workaround for
268  // a probable MingW bug, see
269  // http://trac.osgeo.org/geos/ticket/293
270  return (a < b) ? true : false;
271  }
272 
273  virtual ~AbstractSTRtree();
274 
283  virtual void build();
284 
288  virtual std::size_t
290  {
291  return nodeCapacity;
292  }
293 
294  virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
295 
300  void iterate(ItemVisitor& visitor);
301 
302 
308  virtual void boundablesAtLevel(int level, AbstractNode* top,
309  BoundableList* boundables);
310 
325  ItemsList* itemsTree();
326 };
327 
328 
329 } // namespace geos::index::strtree
330 } // namespace geos::index
331 } // namespace geos
332 
333 #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:289
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:253
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition: AbstractSTRtree.h:173
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