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
29namespace geos {
30namespace index {
31class ItemVisitor;
32namespace strtree {
33class Boundable;
34class AbstractNode;
35}
36}
37}
38
39namespace geos {
40namespace index { // geos::index
41namespace strtree { // geos::index::strtree
42
44typedef std::vector<Boundable*> BoundableList;
45
48class ItemsList;
49
50class ItemsListItem {
51public:
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
94class ItemsList : public std::vector<ItemsListItem> {
95private:
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
106public:
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
139class GEOS_DLL AbstractSTRtree {
140
141private:
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
169protected:
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
250public:
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::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 std::size_t getNodeCapacity()
Returns the maximum number of child nodes that a node may have.
Definition AbstractSTRtree.h:282
ItemsList * itemsTree()
Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in thi...
virtual void boundablesAtLevel(int level, AbstractNode *top, BoundableList *boundables)
virtual void build()
Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been...
virtual IntersectsOp * getIntersectsOp()=0
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