include/geos/index/strtree/AbstractSTRtree.h

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2006 Refractions Research Inc.
   7  *
   8  * This is free software; you can redistribute and/or modify it under
   9  * the terms of the GNU Lesser General Public Licence as published
  10  * by the Free Software Foundation.
  11  * See the COPYING file for more information.
  12  *
  13  **********************************************************************/
  14
  15 #ifndef GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
  16 #define GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
  17
  18 #include <geos/export.h>
  19
  20 #include <geos/index/strtree/AbstractNode.h> // for inlines
  21
  22 #include <vector>
  23 #include <list>
  24 #include <memory> // for auto_ptr
  25 #include <cassert> // for inlines
  26 #include <algorithm>
  27
  28 // Forward declarations
  29 namespace geos {
  30         namespace index {
  31                 class ItemVisitor;
  32                 namespace strtree {
  33                         class Boundable;
  34                         class AbstractNode;
  35                 }
  36         }
  37 }
  38
  39 namespace geos {
  40 namespace index { // geos::index
  41 namespace strtree { // geos::index::strtree
  42
  43 /// A list of boundables. TODO: use a list
  44 typedef std::vector<Boundable*> BoundableList;
  45 //typedef std::list<Boundable*> BoundableList;
  46
  47 /// list contains boundables or lists of boundables. The lists are owned by
  48 /// this class, the plain boundables are held by reference only.
  49 class ItemsList;
  50
  51 class ItemsListItem
  52 {
  53 public:
  54     enum type {
  55         item_is_geometry,
  56         item_is_list
  57     };
  58
  59     ItemsListItem(void *item_)
  60       : t(item_is_geometry)
  61     {
  62         item.g = item_;
  63     }
  64     ItemsListItem(ItemsList* item_)
  65       : t(item_is_list)
  66     {
  67         item.l = item_;
  68     }
  69
  70     type get_type() const { return t; }
  71
  72     void* get_geometry() const
  73     {
  74         assert(t == item_is_geometry);
  75         return item.g;
  76     }
  77     ItemsList* get_itemslist() const
  78     {
  79         assert(t == item_is_list);
  80         return item.l;
  81     }
  82
  83     type t;
  84     union {
  85         void* g;
  86         ItemsList* l;
  87     } item;
  88 };
  89
  90 class ItemsList : public std::vector<ItemsListItem>
  91 {
  92 private:
  93     typedef std::vector<ItemsListItem> base_type;
  94
  95     static void delete_item(ItemsListItem& item)
  96     {
  97         if (ItemsListItem::item_is_list == item.t)
  98             delete item.item.l;
  99     }
 100
 101 public:
 102     ~ItemsList()
 103     {
 104         std::for_each(begin(), end(), &ItemsList::delete_item);
 105     }
 106
 107     // lists of items need to be deleted in the end
 108     void push_back(void* item)
 109     {
 110         this->base_type::push_back(ItemsListItem(item));
 111     }
 112
 113     // lists of items need to be deleted in the end
 114     void push_back_owned(ItemsList* itemList)
 115     {
 116         this->base_type::push_back(ItemsListItem(itemList));
 117     }
 118 };
 119
 120 /** \brief
 121  * Base class for STRtree and SIRtree.
 122  *
 123  * STR-packed R-trees are described in:
 124  * P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With
 125  * Application To GIS. Morgan Kaufmann, San Francisco, 2002.
 126  *
 127  * This implementation is based on Boundables rather than just AbstractNodes,
 128  * because the STR algorithm operates on both nodes and
 129  * data, both of which are treated here as Boundables.
 130  *
 131  */
 132 class GEOS_DLL AbstractSTRtree {
 133
 134 private:
 135         bool built;
 136         BoundableList* itemBoundables;
 137
 138         /**
 139          * Creates the levels higher than the given level
 140          *
 141          * @param boundablesOfALevel
 142          *            the level to build on
 143          * @param level
 144          *            the level of the Boundables, or -1 if the boundables are item
 145          *            boundables (that is, below level 0)
 146          * @return the root, which may be a ParentNode or a LeafNode
 147          */
 148         virtual AbstractNode* createHigherLevels(
 149                         BoundableList* boundablesOfALevel,
 150                         int level);
 151
 152         virtual std::auto_ptr<BoundableList> sortBoundables(const BoundableList* input)=0;
 153
 154         bool remove(const void* searchBounds, AbstractNode& node, void* item);
 155         bool removeItem(AbstractNode& node, void* item);
 156
 157     ItemsList* itemsTree(AbstractNode* node);
 158
 159 protected:
 160
 161         /** \brief
 162          * A test for intersection between two bounds, necessary because
 163          * subclasses of AbstractSTRtree have different implementations of
 164          * bounds.
 165          */
 166         class GEOS_DLL IntersectsOp {
 167                 public:
 168                         /**
 169                          * For STRtrees, the bounds will be Envelopes; for
 170                          * SIRtrees, Intervals; for other subclasses of
 171                          * AbstractSTRtree, some other class.
 172                          * @param aBounds the bounds of one spatial object
 173                          * @param bBounds the bounds of another spatial object
 174                          * @return whether the two bounds intersect
 175                          */
 176                         virtual bool intersects(const void* aBounds,
 177                                         const void* bBounds)=0;
 178
 179                         virtual ~IntersectsOp() {}
 180         };
 181
 182         AbstractNode *root;
 183
 184         std::vector <AbstractNode *> *nodes;
 185
 186         // Ownership to caller (TODO: return by auto_ptr)
 187         virtual AbstractNode* createNode(int level)=0;
 188
 189         /**
 190          * Sorts the childBoundables then divides them into groups of size M, where
 191          * M is the node capacity.
 192          */
 193         virtual std::auto_ptr<BoundableList> createParentBoundables(
 194                         BoundableList* childBoundables, int newLevel);
 195
 196         virtual AbstractNode* lastNode(BoundableList* nodeList)
 197         {
 198                 assert(!nodeList->empty());
 199                 // Cast from Boundable to AbstractNode
 200                 return static_cast<AbstractNode*>(nodeList->back() );
 201         }
 202
 203         virtual AbstractNode* getRoot() {
 204                 assert(built);
 205                 return root;
 206         }
 207
 208         ///  Also builds the tree, if necessary.
 209         virtual void insert(const void* bounds,void* item);
 210
 211         ///  Also builds the tree, if necessary.
 212         void query(const void* searchBounds, std::vector<void*>& foundItems);
 213
 214 #if 0
 215         ///  Also builds the tree, if necessary.
 216         std::vector<void*>* query(const void* searchBounds) {
 217                 vector<void*>* matches = new vector<void*>();
 218                 query(searchBounds, *matches);
 219                 return matches;
 220         }
 221 #endif
 222         ///  Also builds the tree, if necessary.
 223         void query(const void* searchBounds, ItemVisitor& visitor);
 224
 225         void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
 226
 227         ///  Also builds the tree, if necessary.
 228         bool remove(const void* itemEnv, void* item);
 229
 230         std::auto_ptr<BoundableList> boundablesAtLevel(int level);
 231
 232         // @@ should be size_t, probably
 233         std::size_t nodeCapacity;
 234
 235         /**
 236          * @return a test for intersection between two bounds,
 237          * necessary because subclasses
 238          * of AbstractSTRtree have different implementations of bounds.
 239          * @see IntersectsOp
 240          */
 241         virtual IntersectsOp *getIntersectsOp()=0;
 242
 243
 244 public:
 245
 246         /**
 247          * Constructs an AbstractSTRtree with the specified maximum number of child
 248          * nodes that a node may have
 249          */
 250         AbstractSTRtree(std::size_t newNodeCapacity)
 251                 :
 252                 built(false),
 253                 itemBoundables(new BoundableList()),
 254                 nodes(new std::vector<AbstractNode *>()),
 255                 nodeCapacity(newNodeCapacity)
 256         {
 257                 assert(newNodeCapacity>1);
 258         }
 259
 260         static bool compareDoubles(double a, double b) {
 261                 // NOTE - strk:
 262                 // Ternary operation is a workaround for
 263                 // a probable MingW bug, see
 264                 // http://trac.osgeo.org/geos/ticket/293
 265                 return ( a < b ) ? true : false;
 266         }
 267
 268         virtual ~AbstractSTRtree();
 269
 270         /**
 271          * Creates parent nodes, grandparent nodes, and so forth up to the root
 272          * node, for the data that has been inserted into the tree. Can only be
 273          * called once, and thus can be called only after all of the data has been
 274          * inserted into the tree.
 275          */
 276         virtual void build();
 277
 278         /**
 279          * Returns the maximum number of child nodes that a node may have
 280          */
 281         virtual std::size_t getNodeCapacity() { return nodeCapacity; }
 282
 283         virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
 284
 285         /**
 286          * Iterate over all items added thus far.  Explicitly does not build
 287          * the tree.
 288          */
 289         void iterate(ItemVisitor& visitor);
 290
 291
 292         /**
 293          * @param level -1 to get items
 294          */
 295         virtual void boundablesAtLevel(int level, AbstractNode* top,
 296                         BoundableList* boundables);
 297
 298     /**
 299      * Gets a tree structure (as a nested list)
 300      * corresponding to the structure of the items and nodes in this tree.
 301      * <p>
 302      * The returned {@link List}s contain either {@link Object} items,
 303      * or Lists which correspond to subtrees of the tree
 304      * Subtrees which do not contain any items are not included.
 305      * <p>
 306      * Builds the tree if necessary.
 307      *
 308      * @note The caller is responsible for releasing the list
 309      *
 310      * @return a List of items and/or Lists
 311      */
 312     ItemsList* itemsTree();
 313 };
 314
 315
 316 } // namespace geos::index::strtree
 317 } // namespace geos::index
 318 } // namespace geos
 319
 320 #endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H