Main Page   Compound List   File List   Compound Members   File Members   Related Pages  

Rtree.h

Go to the documentation of this file.
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) /* minimum (signed) long value */
00025 #define LONG_MAX          2147483647L   /* maximum (signed) long value */
00026 #endif
00027 
00028 class XyRangeI;
00029 class XyRangeD;
00030 
00031 class MG_EI_Rt XyRange {
00032  public:
00033   XyPoint  ll;   // lower left  corner
00034   XyPoint  ur;   // upper right corner
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 //namespace XyRt {
00064 
00065 // Xy R-tree record
00066 class Rec {
00067 };
00068 
00069 #define MG_RtreeStrSize_RecId  16
00070 
00071 // Record's Id. Either pointer or index.
00072 union MG_EI_Rt RecId {
00073   Rec *  rec;
00074   long   idx;  // assert (sizeof(long) == sizeof(Rec *))
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 // Record Handle
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; } // default is pointer
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   // preferred way of the search iteration: while SUCCESS == nextStep
00115   virtual void setPreStart () = 0;
00116   virtual int nextStep () = 0;
00117 
00118   // more restrictive way (in user's point of view) to perform search:
00119   // in each step the state (including position) is saved using the call
00120   // stack
00121   virtual int processVisits ();
00122   virtual int visit () { return  FAILURE; }  // callback in processVisits,
00123                          // returns SUCCESS to continue with the process
00124 };
00125 
00126 class MG_EI_Rt CurRec {
00127  public:
00128   int              idx;     // count in iteration
00129   RecId            recId;   // current record Id
00130   XyRange          recRng;  // rec range, probably as stored in rtree
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; // current info in searcher
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 (); // default is owner's rhPrototype
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 //  sbool hasOwner () { return owner != NULL; }
00193 };
00194 
00195 class MG_EI_Rt XyRtree {
00196                              friend class Searcher;
00197  protected:
00198   XyRtreeRep *   rep;
00199  public:
00200   Rh *           rhPrototype;   // possible to set record handle
00201                                 // prototype outside the rep
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 //}  // end of namespace XyRt
00251 //#ifndef MG_No_XyRt_namespace
00252 //using namespace XyRt;
00253 //#endif
00254 
00255 /*------------------------------------------------------------------------- o
00256 o -------------------------------------------------------------------------*/
00257 
00258 #endif      /* __MGRTREE_rtreeH__ */
00259 
00260 
00261 
00262 
00263 

Generated on Mon Mar 24 22:59:19 2003 for Mg R-tree Library by doxygen1.2.16