Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | Related Pages

indexBintree.h

00001 /**********************************************************************
00002  * $Id: indexBintree.h,v 1.2 2004/07/19 13:19:31 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions 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  * $Log: indexBintree.h,v $
00016  * Revision 1.2  2004/07/19 13:19:31  strk
00017  * Documentation fixes
00018  *
00019  * Revision 1.1  2004/07/02 13:20:42  strk
00020  * Header files moved under geos/ dir.
00021  *
00022  * Revision 1.6  2004/05/06 16:30:58  strk
00023  * Kept track of newly allocated objects by ensureExtent for Bintree and Quadtree,
00024  * deleted at destruction time. doc/example.cpp runs with no leaks.
00025  *
00026  * Revision 1.5  2004/03/25 02:23:55  ybychkov
00027  * All "index/*" packages upgraded to JTS 1.4
00028  *
00029  * Revision 1.4  2003/11/07 01:23:42  pramsey
00030  * Add standard CVS headers licence notices and copyrights to all cpp and h
00031  * files.
00032  *
00033  *
00034  **********************************************************************/
00035 
00036 
00037 #ifndef GEOS_INDEXBINTREE_H
00038 #define GEOS_INDEXBINTREE_H
00039 
00040 #include <memory>
00041 #include <vector>
00042 #include <geos/platform.h>
00043 #include <geos/geom.h>
00044 
00045 using namespace std;
00046 
00047 namespace geos {
00048 
00049 /*
00050  * \class BinTreeInterval indexBintree.h geos/indexBintree.h
00051  * \brief
00052  * Represents an (1-dimensional) closed interval on the Real number line.
00053  */
00054 class BinTreeInterval {
00055 public:
00056         double min, max;
00057         BinTreeInterval();
00058         virtual ~BinTreeInterval();
00059         BinTreeInterval(double nmin, double nmax);
00060         BinTreeInterval(BinTreeInterval *interval);
00061         void init(double nmin, double nmax);
00062         double getMin();
00063         double getMax();
00064         double getWidth();
00065         void expandToInclude(BinTreeInterval *interval);
00066         bool overlaps(BinTreeInterval *interval);
00067         bool overlaps(double nmin, double nmax);
00068         bool contains(BinTreeInterval *interval);
00069         bool contains(double nmin, double nmax);
00070         bool contains(double p);
00071 };
00072 
00073 /*
00074  * \class Key indexBintree.h geos/indexBintree.h
00075  * \brief
00076  * A Key is a unique identifier for a node in a tree.
00077  *
00078  * It contains a lower-left point and a level number.
00079  * The level number is the power of two for the size of the node envelope
00080  */
00081 class Key {
00082 public:
00083         static int computeLevel(BinTreeInterval *newInterval);
00084         Key(BinTreeInterval *newInterval);
00085         virtual ~Key();
00086         double getPoint();
00087         int getLevel();
00088         BinTreeInterval* getInterval();
00089         void computeKey(BinTreeInterval *itemInterval);
00090 private:
00091         // the fields which make up the key
00092         double pt;
00093         int level;
00094         // auxiliary data which is derived from the key for use in computation
00095         BinTreeInterval *interval;
00096         void computeInterval(int level,BinTreeInterval *itemInterval);
00097 };
00098 
00099 class BinTreeNode;
00100 
00101 /*
00102  * \class NodeBase indexBintree.h geos/indexBintree.h
00103  * \brief The base class for nodes in a Bintree.
00104  */
00105 class NodeBase {
00106 public:
00107         static int getSubnodeIndex(BinTreeInterval *interval, double centre);
00108         NodeBase();
00109         virtual ~NodeBase();
00110         virtual vector<void*> *getItems();
00111         virtual void add(void* item);
00112         virtual vector<void*>* addAllItems(vector<void*> *newItems);
00113         virtual vector<void*>* addAllItemsFromOverlapping(BinTreeInterval *interval,vector<void*> *resultItems);
00114         virtual int depth();
00115         virtual int size();
00116         virtual int nodeSize();
00117 protected:      
00118         vector<void*>* items;
00124         BinTreeNode* subnode[2];
00125         virtual bool isSearchMatch(BinTreeInterval *interval)=0;
00126 };
00127 
00128 /*
00129  * \class BinTreeNode indexBintree.h geos/indexBintree.h
00130  * \brief A node of a Bintree.
00131  */
00132 class BinTreeNode: public NodeBase {
00133 public:
00134         static BinTreeNode* createNode(BinTreeInterval *itemInterval);
00135         static BinTreeNode* createExpanded(BinTreeNode *node,BinTreeInterval *addInterval);
00136         BinTreeNode(BinTreeInterval *newInterval,int newLevel);
00137         virtual ~BinTreeNode();
00138         BinTreeInterval* getInterval();
00139         BinTreeNode* getNode(BinTreeInterval *searchInterval);
00140         NodeBase* find(BinTreeInterval *searchInterval);
00141         void insert(BinTreeNode *node);
00142 private:
00143         BinTreeInterval *interval;
00144         double centre;
00145         int level;
00146         BinTreeNode* getSubnode(int index);
00147         BinTreeNode* createSubnode(int index);
00148 protected:
00149         bool isSearchMatch(BinTreeInterval *itemInterval);
00150 };
00151 
00152 /*
00153  * \class Root indexBintree.h geos/indexBintree.h
00154  * \brief The root node of a single Bintree.
00155  *
00156  * It is centred at the origin,
00157  * and does not have a defined extent.
00158  */
00159 class Root: public NodeBase {
00160 private:
00161         // the singleton root node is centred at the origin.
00162         static double origin;
00163         void insertContained(BinTreeNode *tree,BinTreeInterval *itemInterval,void* item);
00164 public:
00165         Root();
00166         virtual ~Root();
00167         void insert(BinTreeInterval *itemInterval,void* item);
00168 protected:
00169         bool isSearchMatch(BinTreeInterval *interval);
00170 };
00171 
00172 /*
00173  * \class Bintree indexBintree.h geos/indexBintree.h
00174  *
00175  * \brief An BinTree (or "Binary BinTreeInterval Tree")
00176  * is a 1-dimensional version of a quadtree.
00177  *
00178  * It indexes 1-dimensional intervals (which of course may
00179  * be the projection of 2-D objects on an axis).
00180  * It supports range searching
00181  * (where the range may be a single point).
00182  *
00183  * This implementation does not require specifying the extent of the inserted
00184  * items beforehand.  It will automatically expand to accomodate any extent
00185  * of dataset.
00186  * 
00187  * This index is different to the BinTreeInterval Tree of Edelsbrunner
00188  * or the Segment Tree of Bentley.
00189  */
00190 class Bintree {
00191 public:
00192         static BinTreeInterval* ensureExtent(BinTreeInterval *itemInterval, double minExtent);
00193         Bintree();
00194         virtual ~Bintree();
00195         int depth();
00196         int size();
00197         int nodeSize();
00198         void insert(BinTreeInterval *itemInterval,void* item);
00199         vector<void*>* iterator();
00200         vector<void*>* query(double x);
00201         vector<void*>* query(BinTreeInterval *interval);
00202         void query(BinTreeInterval *interval,vector<void*> *foundItems);
00203 private:
00204         vector<BinTreeInterval *>newIntervals;
00205         Root *root;
00216         double minExtent;
00217         void collectStats(BinTreeInterval *interval);
00218 };
00219 }
00220 #endif
00221 

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1