00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #ifndef GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
00016 #define GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
00017
00018 #include <geos/export.h>
00019
00020 #include <geos/index/strtree/AbstractNode.h>
00021
00022 #include <vector>
00023 #include <list>
00024 #include <memory>
00025 #include <cassert>
00026 #include <algorithm>
00027
00028
00029 namespace geos {
00030 namespace index {
00031 class ItemVisitor;
00032 namespace strtree {
00033 class Boundable;
00034 class AbstractNode;
00035 }
00036 }
00037 }
00038
00039 namespace geos {
00040 namespace index {
00041 namespace strtree {
00042
00044 typedef std::vector<Boundable*> BoundableList;
00045
00046
00049 class ItemsList;
00050
00051 class ItemsListItem
00052 {
00053 public:
00054 enum type {
00055 item_is_geometry,
00056 item_is_list
00057 };
00058
00059 ItemsListItem(void *item_)
00060 : t(item_is_geometry)
00061 {
00062 item.g = item_;
00063 }
00064 ItemsListItem(ItemsList* item_)
00065 : t(item_is_list)
00066 {
00067 item.l = item_;
00068 }
00069
00070 type get_type() const { return t; }
00071
00072 void* get_geometry() const
00073 {
00074 assert(t == item_is_geometry);
00075 return item.g;
00076 }
00077 ItemsList* get_itemslist() const
00078 {
00079 assert(t == item_is_list);
00080 return item.l;
00081 }
00082
00083 type t;
00084 union {
00085 void* g;
00086 ItemsList* l;
00087 } item;
00088 };
00089
00090 class ItemsList : public std::vector<ItemsListItem>
00091 {
00092 private:
00093 typedef std::vector<ItemsListItem> base_type;
00094
00095 static void delete_item(ItemsListItem& item)
00096 {
00097 if (ItemsListItem::item_is_list == item.t)
00098 delete item.item.l;
00099 }
00100
00101 public:
00102 ~ItemsList()
00103 {
00104 std::for_each(begin(), end(), &ItemsList::delete_item);
00105 }
00106
00107
00108 void push_back(void* item)
00109 {
00110 this->base_type::push_back(ItemsListItem(item));
00111 }
00112
00113
00114 void push_back_owned(ItemsList* itemList)
00115 {
00116 this->base_type::push_back(ItemsListItem(itemList));
00117 }
00118 };
00119
00132 class GEOS_DLL AbstractSTRtree {
00133
00134 private:
00135 bool built;
00136 BoundableList* itemBoundables;
00137
00148 virtual AbstractNode* createHigherLevels(
00149 BoundableList* boundablesOfALevel,
00150 int level);
00151
00152 virtual std::auto_ptr<BoundableList> sortBoundables(const BoundableList* input)=0;
00153
00154 bool remove(const void* searchBounds, AbstractNode& node, void* item);
00155 bool removeItem(AbstractNode& node, void* item);
00156
00157 ItemsList* itemsTree(AbstractNode* node);
00158
00159 protected:
00160
00166 class GEOS_DLL IntersectsOp {
00167 public:
00176 virtual bool intersects(const void* aBounds,
00177 const void* bBounds)=0;
00178
00179 virtual ~IntersectsOp() {}
00180 };
00181
00182 AbstractNode *root;
00183
00184 std::vector <AbstractNode *> *nodes;
00185
00186
00187 virtual AbstractNode* createNode(int level)=0;
00188
00193 virtual std::auto_ptr<BoundableList> createParentBoundables(
00194 BoundableList* childBoundables, int newLevel);
00195
00196 virtual AbstractNode* lastNode(BoundableList* nodeList)
00197 {
00198 assert(!nodeList->empty());
00199
00200 return static_cast<AbstractNode*>(nodeList->back() );
00201 }
00202
00203 virtual AbstractNode* getRoot() {
00204 assert(built);
00205 return root;
00206 }
00207
00209 virtual void insert(const void* bounds,void* item);
00210
00212 void query(const void* searchBounds, std::vector<void*>& foundItems);
00213
00214 #if 0
00216 std::vector<void*>* query(const void* searchBounds) {
00217 vector<void*>* matches = new vector<void*>();
00218 query(searchBounds, *matches);
00219 return matches;
00220 }
00221 #endif
00223 void query(const void* searchBounds, ItemVisitor& visitor);
00224
00225 void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
00226
00228 bool remove(const void* itemEnv, void* item);
00229
00230 std::auto_ptr<BoundableList> boundablesAtLevel(int level);
00231
00232
00233 std::size_t nodeCapacity;
00234
00241 virtual IntersectsOp *getIntersectsOp()=0;
00242
00243
00244 public:
00245
00250 AbstractSTRtree(std::size_t newNodeCapacity)
00251 :
00252 built(false),
00253 itemBoundables(new BoundableList()),
00254 nodes(new std::vector<AbstractNode *>()),
00255 nodeCapacity(newNodeCapacity)
00256 {
00257 assert(newNodeCapacity>1);
00258 }
00259
00260 static bool compareDoubles(double a, double b) {
00261
00262
00263
00264
00265 return ( a < b ) ? true : false;
00266 }
00267
00268 virtual ~AbstractSTRtree();
00269
00276 virtual void build();
00277
00281 virtual std::size_t getNodeCapacity() { return nodeCapacity; }
00282
00283 virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
00284
00289 void iterate(ItemVisitor& visitor);
00290
00291
00295 virtual void boundablesAtLevel(int level, AbstractNode* top,
00296 BoundableList* boundables);
00297
00312 ItemsList* itemsTree();
00313 };
00314
00315
00316 }
00317 }
00318 }
00319
00320 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H