00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
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
00051
00052
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
00075
00076
00077
00078
00079
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
00092 double pt;
00093 int level;
00094
00095 BinTreeInterval *interval;
00096 void computeInterval(int level,BinTreeInterval *itemInterval);
00097 };
00098
00099 class BinTreeNode;
00100
00101
00102
00103
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
00130
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
00154
00155
00156
00157
00158
00159 class Root: public NodeBase {
00160 private:
00161
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
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
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