GEOS  3.6.1
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 auto_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 {
53 public:
54  enum type {
55  item_is_geometry,
56  item_is_list
57  };
58 
59  ItemsListItem(void *item_)
60  : t(item_is_geometry)
61  {
62  item.g = item_;
63  }
64  ItemsListItem(ItemsList* item_)
65  : t(item_is_list)
66  {
67  item.l = item_;
68  }
69 
70  type get_type() const { return t; }
71 
72  void* get_geometry() const
73  {
74  assert(t == item_is_geometry);
75  return item.g;
76  }
77  ItemsList* get_itemslist() const
78  {
79  assert(t == item_is_list);
80  return item.l;
81  }
82 
83  type t;
84  union {
85  void* g;
86  ItemsList* l;
87  } item;
88 };
89 
90 class ItemsList : public std::vector<ItemsListItem>
91 {
92 private:
93  typedef std::vector<ItemsListItem> base_type;
94 
95  static void delete_item(ItemsListItem& item)
96  {
97  if (ItemsListItem::item_is_list == item.t)
98  delete item.item.l;
99  }
100 
101 public:
102  ~ItemsList()
103  {
104  std::for_each(begin(), end(), &ItemsList::delete_item);
105  }
106 
107  // lists of items need to be deleted in the end
108  void push_back(void* item)
109  {
110  this->base_type::push_back(ItemsListItem(item));
111  }
112 
113  // lists of items need to be deleted in the end
114  void push_back_owned(ItemsList* itemList)
115  {
116  this->base_type::push_back(ItemsListItem(itemList));
117  }
118 };
119 
132 class GEOS_DLL AbstractSTRtree {
133 
134 private:
135  bool built;
136  BoundableList* itemBoundables;
137 
148  virtual AbstractNode* createHigherLevels(
149  BoundableList* boundablesOfALevel,
150  int level);
151 
152  virtual std::auto_ptr<BoundableList> sortBoundables(const BoundableList* input)=0;
153 
154  bool remove(const void* searchBounds, AbstractNode& node, void* item);
155  bool removeItem(AbstractNode& node, void* item);
156 
157  ItemsList* itemsTree(AbstractNode* node);
158 
159 protected:
160 
166  class GEOS_DLL IntersectsOp {
167  public:
176  virtual bool intersects(const void* aBounds,
177  const void* bBounds)=0;
178 
179  virtual ~IntersectsOp() {}
180  };
181 
182  AbstractNode *root;
183 
184  std::vector <AbstractNode *> *nodes;
185 
186  // Ownership to caller (TODO: return by auto_ptr)
187  virtual AbstractNode* createNode(int level)=0;
188 
193  virtual std::auto_ptr<BoundableList> createParentBoundables(
194  BoundableList* childBoundables, int newLevel);
195 
196  virtual AbstractNode* lastNode(BoundableList* nodes)
197  {
198  assert(!nodes->empty());
199  // Cast from Boundable to AbstractNode
200  return static_cast<AbstractNode*>( nodes->back() );
201  }
202 
203  virtual AbstractNode* getRoot() {
204  assert(built);
205  return root;
206  }
207 
209  virtual void insert(const void* bounds,void* item);
210 
212  void query(const void* searchBounds, std::vector<void*>& foundItems);
213 
214 #if 0
215  std::vector<void*>* query(const void* searchBounds) {
217  vector<void*>* matches = new vector<void*>();
218  query(searchBounds, *matches);
219  return matches;
220  }
221 #endif
222  void query(const void* searchBounds, ItemVisitor& visitor);
224 
225  void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
226 
228  bool remove(const void* itemEnv, void* item);
229 
230  std::auto_ptr<BoundableList> boundablesAtLevel(int level);
231 
232  // @@ should be size_t, probably
233  std::size_t nodeCapacity;
234 
241  virtual IntersectsOp *getIntersectsOp()=0;
242 
243 
244 public:
245 
250  AbstractSTRtree(std::size_t newNodeCapacity)
251  :
252  built(false),
253  itemBoundables(new BoundableList()),
254  nodes(new std::vector<AbstractNode *>()),
255  nodeCapacity(newNodeCapacity)
256  {
257  assert(newNodeCapacity>1);
258  }
259 
260  static bool compareDoubles(double a, double b) {
261  // NOTE - strk:
262  // Ternary operation is a workaround for
263  // a probable MingW bug, see
264  // http://trac.osgeo.org/geos/ticket/293
265  return ( a < b ) ? true : false;
266  }
267 
268  virtual ~AbstractSTRtree();
269 
276  virtual void build();
277 
281  virtual std::size_t getNodeCapacity() { return nodeCapacity; }
282 
283  virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
284 
289  void iterate(ItemVisitor& visitor);
290 
291 
295  virtual void boundablesAtLevel(int level, AbstractNode* top,
296  BoundableList* boundables);
297 
312  ItemsList* itemsTree();
313 };
314 
315 
316 } // namespace geos::index::strtree
317 } // namespace geos::index
318 } // namespace geos
319 
320 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
virtual std::size_t getNodeCapacity()
Definition: AbstractSTRtree.h:281
Base class for STRtree and SIRtree.
Definition: AbstractSTRtree.h:132
AbstractSTRtree(std::size_t newNodeCapacity)
Definition: AbstractSTRtree.h:250
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition: AbstractSTRtree.h:166
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:42
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition: AbstractSTRtree.h:44