GEOS
3.3.9
|
00001 /********************************************************************** 00002 * $Id: AbstractSTRtree.h 3255 2011-03-01 17:56:10Z mloskot $ 00003 * 00004 * GEOS - Geometry Engine Open Source 00005 * http://geos.refractions.net 00006 * 00007 * Copyright (C) 2006 Refractions Research Inc. 00008 * 00009 * This is free software; you can redistribute and/or modify it under 00010 * the terms of the GNU Lesser General Public Licence as published 00011 * by the Free Software Foundation. 00012 * See the COPYING file for more information. 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> // for inlines 00022 00023 #include <vector> 00024 #include <list> 00025 #include <memory> // for auto_ptr 00026 #include <cassert> // for inlines 00027 #include <algorithm> 00028 00029 // Forward declarations 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 { // geos::index 00042 namespace strtree { // geos::index::strtree 00043 00045 typedef std::vector<Boundable*> BoundableList; 00046 //typedef std::list<Boundable*> BoundableList; 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 item.item.l; 00100 } 00101 00102 public: 00103 ~ItemsList() 00104 { 00105 std::for_each(begin(), end(), &ItemsList::delete_item); 00106 } 00107 00108 // lists of items need to be deleted in the end 00109 void push_back(void* item) 00110 { 00111 this->base_type::push_back(ItemsListItem(item)); 00112 } 00113 00114 // lists of items need to be deleted in the end 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 GEOS_DLL 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 // Ownership to caller (TODO: return by auto_ptr) 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 // Cast from Boundable to AbstractNode 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 // @@ should be size_t, probably 00234 std::size_t nodeCapacity; 00235 00242 virtual IntersectsOp *getIntersectsOp()=0; 00243 00244 00245 public: 00246 00251 AbstractSTRtree(std::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 // NOTE - strk: 00263 // Ternary operation is a workaround for 00264 // a probable MingW bug, see 00265 // http://trac.osgeo.org/geos/ticket/293 00266 return ( a < b ) ? true : false; 00267 } 00268 00269 virtual ~AbstractSTRtree(); 00270 00277 virtual void build(); 00278 00282 virtual std::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 } // namespace geos::index::strtree 00318 } // namespace geos::index 00319 } // namespace geos 00320 00321 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H 00322 00323 /********************************************************************** 00324 * $Log$ 00325 * Revision 1.3 2006/06/12 10:49:43 strk 00326 * unsigned int => size_t 00327 * 00328 * Revision 1.2 2006/06/08 11:20:24 strk 00329 * Added missing virtual destructor to abstract classes. 00330 * 00331 * Revision 1.1 2006/03/21 10:47:34 strk 00332 * indexStrtree.h split 00333 * 00334 **********************************************************************/ 00335