GEOS  3.12.0
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 #pragma once
16 
17 #include <geos/export.h>
18 
19 #include <geos/index/strtree/AbstractNode.h> // for inlines
20 
21 #include <vector>
22 #include <list>
23 #include <memory> // for unique_ptr
24 #include <cassert> // for inlines
25 #include <algorithm>
26 
27 // Forward declarations
28 namespace geos {
29 namespace index {
30 class ItemVisitor;
31 namespace strtree {
32 class Boundable;
33 class AbstractNode;
34 }
35 }
36 }
37 
38 namespace geos {
39 namespace index { // geos::index
40 namespace strtree { // geos::index::strtree
41 
43 typedef std::vector<Boundable*> BoundableList;
44 
47 class ItemsList;
48 
49 class ItemsListItem {
50 public:
51  enum type {
52  item_is_geometry,
53  item_is_list
54  };
55 
56  ItemsListItem(void* item_)
57  : t(item_is_geometry)
58  {
59  item.g = item_;
60  }
61  ItemsListItem(ItemsList* item_)
62  : t(item_is_list)
63  {
64  item.l = item_;
65  }
66 
67  type
68  get_type() const
69  {
70  return t;
71  }
72 
73  void*
74  get_geometry() const
75  {
76  assert(t == item_is_geometry);
77  return item.g;
78  }
79  ItemsList*
80  get_itemslist() const
81  {
82  assert(t == item_is_list);
83  return item.l;
84  }
85 
86  type t;
87  union {
88  void* g;
89  ItemsList* l;
90  } item;
91 };
92 
93 class ItemsList : public std::vector<ItemsListItem> {
94 private:
95  typedef std::vector<ItemsListItem> base_type;
96 
97  static void
98  delete_item(ItemsListItem& item)
99  {
100  if(ItemsListItem::item_is_list == item.t) {
101  delete item.item.l;
102  }
103  }
104 
105 public:
106  ~ItemsList()
107  {
108  std::for_each(begin(), end(), &ItemsList::delete_item);
109  }
110 
111  // lists of items need to be deleted in the end
112  void
113  push_back(void* item)
114  {
115  this->base_type::push_back(ItemsListItem(item));
116  }
117 
118  // lists of items need to be deleted in the end
119  void
120  push_back_owned(ItemsList* itemList)
121  {
122  this->base_type::push_back(ItemsListItem(itemList));
123  }
124 };
125 
138 class GEOS_DLL AbstractSTRtree {
139 
140 private:
141  bool built;
142  BoundableList* itemBoundables;
143 
154  virtual AbstractNode* createHigherLevels(
155  BoundableList* boundablesOfALevel,
156  int level);
157 
158  std::unique_ptr<BoundableList> sortBoundablesY(const BoundableList* input);
159 
160  bool remove(const void* searchBounds, AbstractNode& node, void* item);
161  bool removeItem(AbstractNode& node, void* item);
162 
163  ItemsList* itemsTree(AbstractNode* node);
164 
165  AbstractSTRtree(const AbstractSTRtree&) = delete;
166  AbstractSTRtree& operator=(const AbstractSTRtree&) = delete;
167 
168 protected:
169 
175  class GEOS_DLL IntersectsOp {
176  public:
185  virtual bool intersects(const void* aBounds,
186  const void* bBounds) = 0;
187 
188  virtual
189  ~IntersectsOp() {}
190  };
191 
192  AbstractNode* root;
193 
194  std::vector <AbstractNode*>* nodes;
195 
196  // Ownership to caller (TODO: return by unique_ptr)
197  virtual AbstractNode* createNode(int level) = 0;
198 
203  virtual std::unique_ptr<BoundableList> createParentBoundables(
204  BoundableList* childBoundables, int newLevel);
205 
206  virtual AbstractNode*
207  lastNode(BoundableList* nodeList)
208  {
209  assert(!nodeList->empty());
210  // Cast from Boundable to AbstractNode
211  return static_cast<AbstractNode*>(nodeList->back());
212  }
213 
214  virtual AbstractNode*
215  getRoot()
216  {
217  assert(built);
218  return root;
219  }
220 
222  virtual void insert(const void* bounds, void* item);
223 
225  void query(const void* searchBounds, std::vector<void*>& foundItems);
226 
228  void query(const void* searchBounds, ItemVisitor& visitor);
229 
230  void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
231 
233  bool remove(const void* itemEnv, void* item);
234 
235  std::unique_ptr<BoundableList> boundablesAtLevel(int level);
236 
237  // @@ should be size_t, probably
238  std::size_t nodeCapacity;
239 
246  virtual IntersectsOp* getIntersectsOp() = 0;
247 
248 
249 public:
250 
255  AbstractSTRtree(std::size_t newNodeCapacity)
256  :
257  built(false),
258  itemBoundables(new BoundableList()),
259  nodes(new std::vector<AbstractNode *>()),
260  nodeCapacity(newNodeCapacity)
261  {
262  assert(newNodeCapacity > 1);
263  }
264 
265  virtual ~AbstractSTRtree();
266 
275  virtual void build();
276 
280  virtual std::size_t
282  {
283  return nodeCapacity;
284  }
285 
286  virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
287 
292  void iterate(ItemVisitor& visitor);
293 
294 
300  virtual void boundablesAtLevel(int level, AbstractNode* top,
301  BoundableList* boundables);
302 
317  ItemsList* itemsTree();
318 };
319 
320 
321 } // namespace geos::index::strtree
322 } // namespace geos::index
323 } // namespace geos
324 
virtual std::size_t getNodeCapacity()
Returns the maximum number of child nodes that a node may have.
Definition: AbstractSTRtree.h:281
Base class for STRtree and SIRtree.
Definition: AbstractSTRtree.h:138
Definition: Coordinate.h:572
AbstractSTRtree(std::size_t newNodeCapacity)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have...
Definition: AbstractSTRtree.h:255
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition: AbstractSTRtree.h:175
A visitor for items in an index.
Definition: ItemVisitor.h:28
Basic namespace for all GEOS functionalities.
Definition: Angle.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:43