GEOS  3.4.2
AbstractSTRtree.h
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