GEOS
3.4.2
|
00001 /********************************************************************** 00002 * 00003 * GEOS - Geometry Engine Open Source 00004 * http://geos.osgeo.org 00005 * 00006 * Copyright (C) 2006 Refractions Research Inc. 00007 * 00008 * This is free software; you can redistribute and/or modify it under 00009 * the terms of the GNU Lesser General Public Licence as published 00010 * by the Free Software Foundation. 00011 * See the COPYING file for more information. 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> // for inlines 00021 00022 #include <vector> 00023 #include <list> 00024 #include <memory> // for auto_ptr 00025 #include <cassert> // for inlines 00026 #include <algorithm> 00027 00028 // Forward declarations 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 { // geos::index 00041 namespace strtree { // geos::index::strtree 00042 00044 typedef std::vector<Boundable*> BoundableList; 00045 //typedef std::list<Boundable*> BoundableList; 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 // lists of items need to be deleted in the end 00108 void push_back(void* item) 00109 { 00110 this->base_type::push_back(ItemsListItem(item)); 00111 } 00112 00113 // lists of items need to be deleted in the end 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 // Ownership to caller (TODO: return by auto_ptr) 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* nodes) 00197 { 00198 assert(!nodes->empty()); 00199 // Cast from Boundable to AbstractNode 00200 return static_cast<AbstractNode*>( nodes->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 00215 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 00222 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 // @@ should be size_t, probably 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 // NOTE - strk: 00262 // Ternary operation is a workaround for 00263 // a probable MingW bug, see 00264 // http://trac.osgeo.org/geos/ticket/293 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 } // namespace geos::index::strtree 00317 } // namespace geos::index 00318 } // namespace geos 00319 00320 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H