GEOS  3.9.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 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  std::unique_ptr<BoundableList> sortBoundablesY(const BoundableList* input);
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 
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  virtual ~AbstractSTRtree();
267 
276  virtual void build();
277 
281  virtual std::size_t
283  {
284  return nodeCapacity;
285  }
286 
287  virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
288 
293  void iterate(ItemVisitor& visitor);
294 
295 
301  virtual void boundablesAtLevel(int level, AbstractNode* top,
302  BoundableList* boundables);
303 
318  ItemsList* itemsTree();
319 };
320 
321 
322 } // namespace geos::index::strtree
323 } // namespace geos::index
324 } // namespace geos
325 
326 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
A visitor for items in an index.
Definition: ItemVisitor.h:29
A node of the STR tree.
Definition: AbstractNode.h:44
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition: AbstractSTRtree.h:176
virtual bool intersects(const void *aBounds, const void *bBounds)=0
Base class for STRtree and SIRtree.
Definition: AbstractSTRtree.h:139
void iterate(ItemVisitor &visitor)
virtual void insert(const void *bounds, void *item)
Also builds the tree, if necessary.
void query(const void *searchBounds, ItemVisitor &visitor)
Also builds the tree, if necessary.
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
bool remove(const void *itemEnv, void *item)
Also builds the tree, if necessary.
void query(const void *searchBounds, std::vector< void * > &foundItems)
Also builds the tree, if necessary.
virtual std::size_t getNodeCapacity()
Returns the maximum number of child nodes that a node may have.
Definition: AbstractSTRtree.h:282
virtual IntersectsOp * getIntersectsOp()=0
virtual std::unique_ptr< BoundableList > createParentBoundables(BoundableList *childBoundables, int newLevel)
Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.
virtual void boundablesAtLevel(int level, AbstractNode *top, BoundableList *boundables)
ItemsList * itemsTree()
Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in thi...
virtual void build()
Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been...
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition: AbstractSTRtree.h:44
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26