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
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
00054
00055
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
00078
00079
00080
00081
00082
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
00095 double pt;
00096 int level;
00097
00098 BinTreeInterval *interval;
00099 void computeInterval(int level,BinTreeInterval *itemInterval);
00100 };
00101
00102 class BinTreeNode;
00103
00104
00105
00106
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
00133
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
00157
00158
00159
00160
00161
00162 class Root: public NodeBase {
00163 private:
00164
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
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
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