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