GEOS  3.8.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 //typedef std::list<Boundable*> BoundableList;
46 
49 class ItemsList;
50 
51 class ItemsListItem {
52 public:
53  enum type {
54  item_is_geometry,
55  item_is_list
56  };
57 
58  ItemsListItem(void* item_)
59  : t(item_is_geometry)
60  {
61  item.g = item_;
62  }
63  ItemsListItem(ItemsList* item_)
64  : t(item_is_list)
65  {
66  item.l = item_;
67  }
68 
69  type
70  get_type() const
71  {
72  return t;
73  }
74 
75  void*
76  get_geometry() const
77  {
78  assert(t == item_is_geometry);
79  return item.g;
80  }
81  ItemsList*
82  get_itemslist() const
83  {
84  assert(t == item_is_list);
85  return item.l;
86  }
87 
88  type t;
89  union {
90  void* g;
91  ItemsList* l;
92  } item;
93 };
94 
95 class ItemsList : public std::vector<ItemsListItem> {
96 private:
97  typedef std::vector<ItemsListItem> base_type;
98 
99  static void
100  delete_item(ItemsListItem& item)
101  {
102  if(ItemsListItem::item_is_list == item.t) {
103  delete item.item.l;
104  }
105  }
106 
107 public:
108  ~ItemsList()
109  {
110  std::for_each(begin(), end(), &ItemsList::delete_item);
111  }
112 
113  // lists of items need to be deleted in the end
114  void
115  push_back(void* item)
116  {
117  this->base_type::push_back(ItemsListItem(item));
118  }
119 
120  // lists of items need to be deleted in the end
121  void
122  push_back_owned(ItemsList* itemList)
123  {
124  this->base_type::push_back(ItemsListItem(itemList));
125  }
126 };
127 
140 class GEOS_DLL AbstractSTRtree {
141 
142 private:
143  bool built;
144  BoundableList* itemBoundables;
145 
156  virtual AbstractNode* createHigherLevels(
157  BoundableList* boundablesOfALevel,
158  int level);
159 
160  virtual std::unique_ptr<BoundableList> sortBoundables(const BoundableList* input) = 0;
161 
162  bool remove(const void* searchBounds, AbstractNode& node, void* item);
163  bool removeItem(AbstractNode& node, void* item);
164 
165  ItemsList* itemsTree(AbstractNode* node);
166 
167 protected:
168 
174  class GEOS_DLL IntersectsOp {
175  public:
184  virtual bool intersects(const void* aBounds,
185  const void* bBounds) = 0;
186 
187  virtual
188  ~IntersectsOp() {}
189  };
190 
191  AbstractNode* root;
192 
193  std::vector <AbstractNode*>* nodes;
194 
195  // Ownership to caller (TODO: return by unique_ptr)
196  virtual AbstractNode* createNode(int level) = 0;
197 
202  virtual std::unique_ptr<BoundableList> createParentBoundables(
203  BoundableList* childBoundables, int newLevel);
204 
205  virtual AbstractNode*
206  lastNode(BoundableList* nodeList)
207  {
208  assert(!nodeList->empty());
209  // Cast from Boundable to AbstractNode
210  return static_cast<AbstractNode*>(nodeList->back());
211  }
212 
213  virtual AbstractNode*
214  getRoot()
215  {
216  assert(built);
217  return root;
218  }
219 
221  virtual void insert(const void* bounds, void* item);
222 
224  void query(const void* searchBounds, std::vector<void*>& foundItems);
225 
226 #if 0
227  std::vector<void*>*
229  query(const void* searchBounds)
230  {
231  vector<void*>* matches = new vector<void*>();
232  query(searchBounds, *matches);
233  return matches;
234  }
235 #endif
236  void query(const void* searchBounds, ItemVisitor& visitor);
238 
239  void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
240 
242  bool remove(const void* itemEnv, void* item);
243 
244  std::unique_ptr<BoundableList> boundablesAtLevel(int level);
245 
246  // @@ should be size_t, probably
247  std::size_t nodeCapacity;
248 
255  virtual IntersectsOp* getIntersectsOp() = 0;
256 
257 
258 public:
259 
264  AbstractSTRtree(std::size_t newNodeCapacity)
265  :
266  built(false),
267  itemBoundables(new BoundableList()),
268  nodes(new std::vector<AbstractNode *>()),
269  nodeCapacity(newNodeCapacity)
270  {
271  assert(newNodeCapacity > 1);
272  }
273 
274  static bool
275  compareDoubles(double a, double b)
276  {
277  // NOTE - strk:
278  // Ternary operation is a workaround for
279  // a probable MingW bug, see
280  // http://trac.osgeo.org/geos/ticket/293
281  return (a < b) ? true : false;
282  }
283 
284  virtual ~AbstractSTRtree();
285 
292  virtual void build();
293 
297  virtual std::size_t
299  {
300  return nodeCapacity;
301  }
302 
303  virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
304 
309  void iterate(ItemVisitor& visitor);
310 
311 
315  virtual void boundablesAtLevel(int level, AbstractNode* top,
316  BoundableList* boundables);
317 
332  ItemsList* itemsTree();
333 };
334 
335 
336 } // namespace geos::index::strtree
337 } // namespace geos::index
338 } // namespace geos
339 
340 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
virtual std::size_t getNodeCapacity()
Definition: AbstractSTRtree.h:298
Base class for STRtree and SIRtree.
Definition: AbstractSTRtree.h:140
AbstractSTRtree(std::size_t newNodeCapacity)
Definition: AbstractSTRtree.h:264
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition: AbstractSTRtree.h:174
A visitor for items in an index.
Definition: ItemVisitor.h:29
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:25
A node of the STR tree.
Definition: AbstractNode.h:43
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition: AbstractSTRtree.h:44