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
geos::index::strtree::AbstractSTRtree::insert
virtual void insert(const void *bounds, void *item)
Also builds the tree, if necessary.
geos::index::strtree::BoundableList
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition: AbstractSTRtree.h:44
geos
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26
geos::index::strtree::AbstractSTRtree::boundablesAtLevel
virtual void boundablesAtLevel(int level, AbstractNode *top, BoundableList *boundables)
geos::index::strtree::AbstractSTRtree::getNodeCapacity
virtual std::size_t getNodeCapacity()
Returns the maximum number of child nodes that a node may have.
Definition: AbstractSTRtree.h:282
geos::index::strtree::AbstractSTRtree::query
void query(const void *searchBounds, std::vector< void * > &foundItems)
Also builds the tree, if necessary.
geos::index::strtree::AbstractSTRtree::AbstractSTRtree
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
geos::index::strtree::AbstractSTRtree::remove
bool remove(const void *itemEnv, void *item)
Also builds the tree, if necessary.
geos::index::strtree::AbstractSTRtree::itemsTree
ItemsList * itemsTree()
Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in thi...
geos::index::ItemVisitor
A visitor for items in an index.
Definition: ItemVisitor.h:29
geos::index::strtree::AbstractSTRtree::getIntersectsOp
virtual IntersectsOp * getIntersectsOp()=0
geos::index::strtree::AbstractNode
A node of the STR tree.
Definition: AbstractNode.h:44
geos::index::strtree::AbstractSTRtree::iterate
void iterate(ItemVisitor &visitor)
geos::index::strtree::AbstractSTRtree::query
void query(const void *searchBounds, ItemVisitor &visitor)
Also builds the tree, if necessary.
geos::index::strtree::AbstractSTRtree
Base class for STRtree and SIRtree.
Definition: AbstractSTRtree.h:139
geos::index::strtree::AbstractSTRtree::createParentBoundables
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.
geos::index::strtree::AbstractSTRtree::IntersectsOp::intersects
virtual bool intersects(const void *aBounds, const void *bBounds)=0
geos::index::strtree::AbstractSTRtree::build
virtual void build()
Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been...
geos::index::strtree::AbstractSTRtree::IntersectsOp
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition: AbstractSTRtree.h:176