• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • File List

AbstractSTRtree.h

00001 /**********************************************************************
00002  * $Id: AbstractSTRtree.h 2685 2009-10-20 16:59:30Z strk $
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 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     // 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 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         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                 // 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 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 

Generated on Thu Jul 22 2010 for GEOS by  doxygen 1.7.1