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/index/strtree/AbstractNode.h>
00020
00021 #include <vector>
00022 #include <list>
00023 #include <memory>
00024 #include <cassert>
00025 #include <algorithm>
00026
00027
00028 namespace geos {
00029 namespace index {
00030 class ItemVisitor;
00031 namespace strtree {
00032 class Boundable;
00033 class AbstractNode;
00034 }
00035 }
00036 }
00037
00038 namespace geos {
00039 namespace index {
00040 namespace strtree {
00041
00043 typedef std::vector<Boundable*> BoundableList;
00044
00045
00048 class ItemsList;
00049
00050 class ItemsListItem
00051 {
00052 public:
00053 enum type {
00054 item_is_geometry,
00055 item_is_list
00056 };
00057
00058 ItemsListItem(void *item_)
00059 : t(item_is_geometry)
00060 {
00061 item.g = item_;
00062 }
00063 ItemsListItem(ItemsList* item_)
00064 : t(item_is_list)
00065 {
00066 item.l = item_;
00067 }
00068
00069 type get_type() const { return t; }
00070
00071 void* get_geometry() const
00072 {
00073 assert(t == item_is_geometry);
00074 return item.g;
00075 }
00076 ItemsList* get_itemslist() const
00077 {
00078 assert(t == item_is_list);
00079 return item.l;
00080 }
00081
00082 type t;
00083 union {
00084 void* g;
00085 ItemsList* l;
00086 } item;
00087 };
00088
00089 class ItemsList : public std::vector<ItemsListItem>
00090 {
00091 private:
00092 typedef std::vector<ItemsListItem> base_type;
00093
00094 static void delete_item(ItemsListItem& item)
00095 {
00096 if (ItemsListItem::item_is_list == item.t)
00097 delete reinterpret_cast<ItemsList*>(item.item.l);
00098 }
00099
00100 public:
00101 ~ItemsList()
00102 {
00103 std::for_each(begin(), end(), &ItemsList::delete_item);
00104 }
00105
00106
00107 void push_back(void* item)
00108 {
00109 this->base_type::push_back(ItemsListItem(item));
00110 }
00111
00112
00113 void push_back_owned(ItemsList* itemList)
00114 {
00115 this->base_type::push_back(ItemsListItem(itemList));
00116 }
00117 };
00118
00131 class AbstractSTRtree {
00132
00133 private:
00134 bool built;
00135 BoundableList* itemBoundables;
00136
00147 virtual AbstractNode* createHigherLevels(
00148 BoundableList* boundablesOfALevel,
00149 int level);
00150
00151 virtual std::auto_ptr<BoundableList> sortBoundables(const BoundableList* input)=0;
00152
00153 bool remove(const void* searchBounds, AbstractNode& node, void* item);
00154 bool removeItem(AbstractNode& node, void* item);
00155
00156 ItemsList* itemsTree(AbstractNode* node);
00157
00158 protected:
00159
00165 class IntersectsOp {
00166 public:
00175 virtual bool intersects(const void* aBounds,
00176 const void* bBounds)=0;
00177
00178 virtual ~IntersectsOp() {}
00179 };
00180
00181 AbstractNode *root;
00182
00183 std::vector <AbstractNode *> *nodes;
00184
00185
00186 virtual AbstractNode* createNode(int level)=0;
00187
00192 virtual std::auto_ptr<BoundableList> createParentBoundables(
00193 BoundableList* childBoundables, int newLevel);
00194
00195 virtual AbstractNode* lastNode(BoundableList* nodes)
00196 {
00197 assert(!nodes->empty());
00198
00199 return static_cast<AbstractNode*>( nodes->back() );
00200 }
00201
00202 virtual AbstractNode* getRoot() {
00203 return root;
00204 }
00205
00207 virtual void insert(const void* bounds,void* item);
00208
00210 void query(const void* searchBounds, std::vector<void*>& foundItems);
00211
00212 #if 0
00214 std::vector<void*>* query(const void* searchBounds) {
00215 vector<void*>* matches = new vector<void*>();
00216 query(searchBounds, *matches);
00217 return matches;
00218 }
00219 #endif
00220
00221
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 size_t nodeCapacity;
00234
00241 virtual IntersectsOp *getIntersectsOp()=0;
00242
00243
00244 public:
00245
00250 AbstractSTRtree(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 return a<b;
00262 }
00263
00264 virtual ~AbstractSTRtree();
00265
00272 virtual void build();
00273
00277 virtual size_t getNodeCapacity() { return nodeCapacity; }
00278
00279 virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
00280
00284 virtual void boundablesAtLevel(int level, AbstractNode* top,
00285 BoundableList* boundables);
00286
00301 ItemsList* itemsTree();
00302 };
00303
00304
00305 }
00306 }
00307 }
00308
00309 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323