GEOS  3.3.3
AbstractSTRtree.h
1 /**********************************************************************
2  * $Id: AbstractSTRtree.h 3255 2011-03-01 17:56:10Z mloskot $
3  *
4  * GEOS - Geometry Engine Open Source
5  * http://geos.refractions.net
6  *
7  * Copyright (C) 2006 Refractions Research Inc.
8  *
9  * This is free software; you can redistribute and/or modify it under
10  * the terms of the GNU Lesser General Public Licence as published
11  * by the Free Software Foundation.
12  * See the COPYING file for more information.
13  *
14  **********************************************************************/
15 
16 #ifndef GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
17 #define GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
18 
19 #include <geos/export.h>
20 
21 #include <geos/index/strtree/AbstractNode.h> // for inlines
22 
23 #include <vector>
24 #include <list>
25 #include <memory> // for auto_ptr
26 #include <cassert> // for inlines
27 #include <algorithm>
28 
29 // Forward declarations
30 namespace geos {
31  namespace index {
32  class ItemVisitor;
33  namespace strtree {
34  class Boundable;
35  class AbstractNode;
36  }
37  }
38 }
39 
40 namespace geos {
41 namespace index { // geos::index
42 namespace strtree { // geos::index::strtree
43 
45 typedef std::vector<Boundable*> BoundableList;
46 //typedef std::list<Boundable*> BoundableList;
47 
50 class ItemsList;
51 
52 class ItemsListItem
53 {
54 public:
55  enum type {
56  item_is_geometry,
57  item_is_list
58  };
59 
60  ItemsListItem(void *item_)
61  : t(item_is_geometry)
62  {
63  item.g = item_;
64  }
65  ItemsListItem(ItemsList* item_)
66  : t(item_is_list)
67  {
68  item.l = item_;
69  }
70 
71  type get_type() const { return t; }
72 
73  void* get_geometry() const
74  {
75  assert(t == item_is_geometry);
76  return item.g;
77  }
78  ItemsList* get_itemslist() const
79  {
80  assert(t == item_is_list);
81  return item.l;
82  }
83 
84  type t;
85  union {
86  void* g;
87  ItemsList* l;
88  } item;
89 };
90 
91 class ItemsList : public std::vector<ItemsListItem>
92 {
93 private:
94  typedef std::vector<ItemsListItem> base_type;
95 
96  static void delete_item(ItemsListItem& item)
97  {
98  if (ItemsListItem::item_is_list == item.t)
99  delete item.item.l;
100  }
101 
102 public:
103  ~ItemsList()
104  {
105  std::for_each(begin(), end(), &ItemsList::delete_item);
106  }
107 
108  // lists of items need to be deleted in the end
109  void push_back(void* item)
110  {
111  this->base_type::push_back(ItemsListItem(item));
112  }
113 
114  // lists of items need to be deleted in the end
115  void push_back_owned(ItemsList* itemList)
116  {
117  this->base_type::push_back(ItemsListItem(itemList));
118  }
119 };
120 
133 class GEOS_DLL AbstractSTRtree {
134 
135 private:
136  bool built;
137  BoundableList* itemBoundables;
138 
149  virtual AbstractNode* createHigherLevels(
150  BoundableList* boundablesOfALevel,
151  int level);
152 
153  virtual std::auto_ptr<BoundableList> sortBoundables(const BoundableList* input)=0;
154 
155  bool remove(const void* searchBounds, AbstractNode& node, void* item);
156  bool removeItem(AbstractNode& node, void* item);
157 
158  ItemsList* itemsTree(AbstractNode* node);
159 
160 protected:
161 
167  class GEOS_DLL IntersectsOp {
168  public:
177  virtual bool intersects(const void* aBounds,
178  const void* bBounds)=0;
179 
180  virtual ~IntersectsOp() {}
181  };
182 
183  AbstractNode *root;
184 
185  std::vector <AbstractNode *> *nodes;
186 
187  // Ownership to caller (TODO: return by auto_ptr)
188  virtual AbstractNode* createNode(int level)=0;
189 
194  virtual std::auto_ptr<BoundableList> createParentBoundables(
195  BoundableList* childBoundables, int newLevel);
196 
197  virtual AbstractNode* lastNode(BoundableList* nodes)
198  {
199  assert(!nodes->empty());
200  // Cast from Boundable to AbstractNode
201  return static_cast<AbstractNode*>( nodes->back() );
202  }
203 
204  virtual AbstractNode* getRoot() {
205  assert(built);
206  return root;
207  }
208 
210  virtual void insert(const void* bounds,void* item);
211 
213  void query(const void* searchBounds, std::vector<void*>& foundItems);
214 
215 #if 0
216 
217  std::vector<void*>* query(const void* searchBounds) {
218  vector<void*>* matches = new vector<void*>();
219  query(searchBounds, *matches);
220  return matches;
221  }
222 #endif
223 
224  void query(const void* searchBounds, ItemVisitor& visitor);
225 
226  void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
227 
229  bool remove(const void* itemEnv, void* item);
230 
231  std::auto_ptr<BoundableList> boundablesAtLevel(int level);
232 
233  // @@ should be size_t, probably
234  std::size_t nodeCapacity;
235 
242  virtual IntersectsOp *getIntersectsOp()=0;
243 
244 
245 public:
246 
251  AbstractSTRtree(std::size_t newNodeCapacity)
252  :
253  built(false),
254  itemBoundables(new BoundableList()),
255  nodes(new std::vector<AbstractNode *>()),
256  nodeCapacity(newNodeCapacity)
257  {
258  assert(newNodeCapacity>1);
259  }
260 
261  static bool compareDoubles(double a, double b) {
262  // NOTE - strk:
263  // Ternary operation is a workaround for
264  // a probable MingW bug, see
265  // http://trac.osgeo.org/geos/ticket/293
266  return ( a < b ) ? true : false;
267  }
268 
269  virtual ~AbstractSTRtree();
270 
277  virtual void build();
278 
282  virtual std::size_t getNodeCapacity() { return nodeCapacity; }
283 
284  virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
285 
290  void iterate(ItemVisitor& visitor);
291 
292 
296  virtual void boundablesAtLevel(int level, AbstractNode* top,
297  BoundableList* boundables);
298 
313  ItemsList* itemsTree();
314 };
315 
316 
317 } // namespace geos::index::strtree
318 } // namespace geos::index
319 } // namespace geos
320 
321 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
322 
323 /**********************************************************************
324  * $Log$
325  * Revision 1.3 2006/06/12 10:49:43 strk
326  * unsigned int => size_t
327  *
328  * Revision 1.2 2006/06/08 11:20:24 strk
329  * Added missing virtual destructor to abstract classes.
330  *
331  * Revision 1.1 2006/03/21 10:47:34 strk
332  * indexStrtree.h split
333  *
334  **********************************************************************/
335