Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members

indexBintree.h

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

Generated on Tue Apr 19 07:10:18 2005 for GEOS by  doxygen 1.4.2