00001 #ifndef __MGRTREE_rtreeH__
00002 #define __MGRTREE_rtreeH__
00003
00004 #include <mgrtree/BasDef.h>
00005 #include <mgrtree/CsizeStr.h>
00006 #include <mgrtree/Assert.h>
00007
00008 #undef EndOfIncludesSection
00009
00010 #if !defined (MG_EI_Rt)
00011 #define MG_EI_Rt MG_DllImport
00012 #endif
00013
00014 class MG_EI_Rt XyPoint {
00015 public:
00016 double x;
00017 double y;
00018 public:
00019 XyPoint () {};
00020 XyPoint (double x, double y) : x(x), y(y) {}
00021 };
00022
00023 #ifndef LONG_MIN
00024 #define LONG_MIN (-2147483647L - 1)
00025 #define LONG_MAX 2147483647L
00026 #endif
00027
00028 class XyRangeI;
00029 class XyRangeD;
00030
00031 class MG_EI_Rt XyRange {
00032 public:
00033 XyPoint ll;
00034 XyPoint ur;
00035 public:
00036 XyRange () {}
00037 XyRange (XyPoint & ll, XyPoint & ur) { fromLlUr (ll, ur); }
00038 void fromLlUr (XyPoint & ll, XyPoint & ur) {
00039 this->ll = ll; this->ur = ur; }
00040 void fromCoords (int * coords) {
00041 ll.x = coords[0]; ll.y = coords[1]; ur.x = coords[2]; ur.y = coords[3]; }
00042 XyRange (int * coords) { fromCoords (coords); }
00043 void toCoords (int * coords) {
00044 coords[0] = (int) ll.x; coords[1] = (int) ll.y;
00045 coords[2] = (int) ur.x; coords[3] = (int) ur.y; }
00046 void fromRngI (XyRangeI & r);
00047 XyRange (XyRangeI & r) { fromRngI (r); }
00048 XyRangeD & rngD () { return *((XyRangeD *)this); }
00049 XyRangeI rngI ();
00050 public:
00051 void setEmpty () { ll.x = ll.y = 0; ur.x = -1; ur.y = 1; }
00052 void setUnlimited () { ll.x = ll.y = LONG_MIN; ur.x = ur.y = LONG_MAX; }
00053 public:
00054 sbool isEmpty () const { return ll.x > ur.x; }
00055 sbool isUnlimited () const { return ll.x == LONG_MIN && ll.y == LONG_MIN
00056 && ur.x == LONG_MAX && ur.y == LONG_MAX; }
00057 public:
00058 const char * str ();
00059 };
00060
00061 class UfXyRtreeRep;
00062
00063
00064
00065
00066 class Rec {
00067 };
00068
00069 #define MG_RtreeStrSize_RecId 16
00070
00071
00072 union MG_EI_Rt RecId {
00073 Rec * rec;
00074 long idx;
00075 RecId () {};
00076 RecId (void * rec) { this->rec = (Rec *) rec; };
00077 RecId (Rec * rec) { this->rec = rec; };
00078 RecId (int idx) { this->idx = idx; };
00079 void fromIdx (int idx) { this->idx = idx; }
00080 void setNull () { idx = -1; }
00081 sbool isNull () { return idx == -1; }
00082 sbool isEqual (RecId & recId) { return idx == recId.idx; }
00083 CsizeString<MG_RtreeStrSize_RecId> alpha ();
00084 };
00085
00086
00087 class Rh {
00088 public:
00089 RecId recId;
00090 public:
00091 Rh () {};
00092 void init (RecId & recId) { this->recId = recId; }
00093 Rh (RecId & recId) { init (recId); }
00094 public:
00095 virtual ~Rh () {}
00096 virtual XyRange range () = 0;
00097 virtual Rec * rec () { return recId.rec; }
00098 };
00099
00100 class Searcher;
00101
00102 class SearcherRep {
00103 friend class Searcher;
00104 public:
00105 Searcher * owner;
00106 XyRange searchRng;
00107 public:
00108 void init () { owner = NULL; searchRng.setEmpty(); }
00109 SearcherRep () { init(); }
00110 public:
00111 virtual ~SearcherRep () {};
00112 virtual void setRange (XyRange & range) = 0;
00113
00114
00115 virtual void setPreStart () = 0;
00116 virtual int nextStep () = 0;
00117
00118
00119
00120
00121 virtual int processVisits ();
00122 virtual int visit () { return FAILURE; }
00123
00124 };
00125
00126 class MG_EI_Rt CurRec {
00127 public:
00128 int idx;
00129 RecId recId;
00130 XyRange recRng;
00131 public:
00132 void init () { idx = -1; recId.setNull(); recRng.setEmpty(); }
00133 };
00134
00135 class XyRtree;
00136
00137 class MG_EI_Rt Searcher {
00138 public:
00139 SearcherRep * rep;
00140 CurRec cur;
00141 public:
00142 void init () { rep = NULL; cur.init(); }
00143 Searcher () { init(); }
00144 void setRep (SearcherRep * rep);
00145 Searcher (SearcherRep * rep) { init(); setRep (rep); }
00146 void init (XyRtree &);
00147 Searcher (XyRtree & rtree) { init (rtree); }
00148 public:
00149 ~Searcher () { if ( rep != NULL ) delete (rep); }
00150 public:
00151 void setRange (XyRange & r) { rep->setRange (r); }
00152 void setPreStart () { rep->setPreStart(); }
00153 int nextStep () { return rep->nextStep(); }
00154 int processVisits () { return rep->processVisits(); }
00155 int visit () { return rep->visit(); }
00156 public:
00157 int processVisits (XyRange & r) { setRange (r); return processVisits(); }
00158 public:
00159 XyRange & searchRng () { return rep->searchRng; }
00160 public:
00161 void expropriate () { init(); }
00162 Searcher & operator= (Searcher &);
00163 };
00164
00165 class XyRtreeRep {
00166 public:
00167 XyRtree * owner;
00168 public:
00169 Rh * rh (RecId & recId) { rh()->recId = recId; return rh(); }
00170 protected:
00171 void init () { owner = NULL; }
00172 XyRtreeRep () { init(); }
00173 public:
00174 virtual ~XyRtreeRep () {};
00175 virtual Rh * rh ();
00176 virtual void removeAll () = 0;
00177 virtual int insertRecord (RecId &) = 0;
00178 virtual int deleteRecord (RecId & recId) { return FAILURE; }
00179 virtual SearcherRep * newSearcherRep () = 0;
00180 public:
00181 virtual void printLevel (short levelIdx) {}
00182 virtual void printLevels (short topLevelIdx = 0,
00183 short bottomLevelIdx = -1) {};
00184 public:
00185 int insertRecord (int idx) {
00186 RecId recId (idx); return insertRecord (recId); }
00187 int deleteRecord (int idx) {
00188 RecId recId (idx); return deleteRecord (recId); }
00189 int createSearcher (Searcher & searcher);
00190 int createSearcher (Searcher & searcher, XyRange & searchRng);
00191 public:
00192
00193 };
00194
00195 class MG_EI_Rt XyRtree {
00196 friend class Searcher;
00197 protected:
00198 XyRtreeRep * rep;
00199 public:
00200 Rh * rhPrototype;
00201
00202 XyRange overallRange;
00203 int numRecords;
00204 public:
00205 Rh * rh () { return rep->rh(); }
00206 Rh * rh (RecId & recId) { return rep->rh(recId); }
00207 public:
00208 void init ();
00209 XyRtree () { init(); }
00210 void setRep (XyRtreeRep * rep);
00211 XyRtree (XyRtreeRep * rep) { init(); setRep (rep); }
00212 public:
00213 void setUfRep ();
00214 public:
00215 ~XyRtree ();
00216 public:
00217 void destroyRep ();
00218 public:
00219 void removeAll () { rep->removeAll(); }
00220 public:
00221 int insertRecord (RecId & recId) { return rep->insertRecord (recId); }
00222 int insertRecord (int idx) { RecId recId (idx);
00223 return insertRecord (recId); }
00224 int deleteRecord (RecId & recId) { return rep->deleteRecord (recId); }
00225 int deleteRecord (int idx) { RecId recId (idx);
00226 return deleteRecord (recId); }
00227 public:
00228 int createSearcher (Searcher & searcher) {
00229 return rep->createSearcher (searcher); }
00230 int createSearcher (Searcher & searcher, XyRange & rng) {
00231 return rep->createSearcher (searcher, rng); }
00232 public:
00233 void printLevel (short levelIdx) { rep->printLevel (levelIdx); }
00234 void printLevels (short topLevelIdx = 0, short bottomLevelIdx = -1) {
00235 rep->printLevels (topLevelIdx, bottomLevelIdx); }
00236 public:
00237 void printSearch (Searcher & searcher);
00238 void printSearch (Searcher & searcher, XyRange & rng) {
00239 searcher.setRange (rng); printSearch (searcher); }
00240 void printSearch (Searcher & searcher, XyPoint & ll, XyPoint & ur) {
00241 printSearch (searcher, XyRange (ll, ur)); }
00242 void printSearch (XyRange & rng) { printSearch (Searcher(*this), rng); }
00243 void printSearch (XyPoint & ll, XyPoint & ur) {
00244 printSearch (Searcher(*this), ll, ur); }
00245 public:
00246 void expropriate () { init (); }
00247 XyRtree & operator= (XyRtree &);
00248 };
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258 #endif
00259
00260
00261
00262
00263