rtkey.h

此文件包含了在linux下实现tpr-tree索引的源代码

// -*- Mode: C++ -*-
//--------------------------------------------------------------------
//      RTkey.h
//      -------
//      Implements the key of the tree node  
//
//      Classes declared: 
//      RTkey  - TPR-tree key (both leaf level and internal), 
//               suitable for queries too. 
//
//      Inheritance hierarchy:
//      GiSTobject 
//        RTkey
//
//      TPR-tree - Index for continuously moving objects
//      July 2001 release, Aalborg University
//

#ifndef RTKEY_H
#define RTKEY_H


#include <limits.h>

#include <float.h>
#include "GiSTdefs.h"
#include "rtsettings.h"

typedef float RTtimeStamp;      // Time instant 
typedef float RTperiod;         // Period of time 
typedef float RTcoord;          // Spatial coordinate or speed value   


const RTtimeStamp TPR_TS_INF = FLT_MAX;     // Inifinity in the domain of RTtimeStamp
const RTcoord     TPR_SS_INF = FLT_MAX;     // Inifinity in the domain of RTcoord

extern RTtimeStamp CT;                      // The current time 

class RT;

//-------------------------------------------------------------
//   RTkey is a class that represnts evolving rectangles 
//   (moving and changing extents). 
//   Points are supported as special cases of rectangles.
//   By storing both beginning and ending times, RTkey also 
//   supports a wide range of queries. Beginning time (t1) represents the 
//   time for which the reference position is stored. For queries it 
//   also represents the "valid-time begin", but for objects the
//   "valid-time begin" is the current time.
// 
//   Name of a method tells how a key object is treated:
//    n  -  as an n-dimensional object at a specific time (CT + d)
//    n1 -  as an (n+1)-dimensional representation of object's evolution 
//          in sapce+time from CT to infinite future or to CT + h 
//    2n -  as a 2n-dimensional object in dual space (reference pos. + velocity)
//    br -  bounding rectangle rounding. IEEE 754 floating point rounding in the 
//          direction of plus or minus infinity (for upper or lower bound) to ensure 
//          that floating point addition imprecision does not result in the enclosed 
//          points "slipping" out of the bounding rectangle. 
//           

class RTkey : public GiSTobject
{
 public:
   
   RTkey();
   RTkey(const RTkey& k);
   RTkey(const RTcoord* pc,                      // For points
         RTtimeStamp ts1 = 0, RTtimeStamp ts2 = TPR_TS_INF);
   RTkey(const RTcoord* lc, const RTcoord* hc,   // For rectangles
         RTtimeStamp ts1 = 0, RTtimeStamp ts2 = TPR_TS_INF);  
   
   RTkey&      operator= (const RTkey& k) { return *::new(this) RTkey(k); }      
   GiSTobject* Copy() const { return new RTkey(*this); }
   GiSTobjid   IsA()  const { return RTKEY_CLASS;      }

   // Methods controlling disk representation of the key
   //
   virtual char*      ToString  (RT* tree,       char* str, int isLeaf) const;
   virtual RTkey&     FromString(RT* tree, const char* str, int isLeaf);
  
   virtual int        Length(RT* tree, int isLeaf) const;  

   // SetRefTS sets t1 and adjusts accordingly the intercept (in coords) 
   //
   void        SetRefTS    (RTtimeStamp rts);
   void        SetRefTS_br (RTtimeStamp rts);
   RTtimeStamp RefTS       () const { return t1; }
   
   // ComputeNaturalt2 computes assigns t2 a time, when rectangle becomes invalid
   //
   void        ComputeNaturalt2 ();

   // CoordT - coordinates as a function of time s(t) = s(t0) + v*(t-t0)
   //
   RTcoord     Coordtp(int dim, int j, RTtimeStamp tp) const
   { return coords[dim][j] + coords[Settings.GetDims() + dim][j] * (tp - t1); } 
   RTcoord     CoordT(int dim, int j = 0, RTperiod d = 0) const
   { return coords[dim][j] + coords[Settings.GetDims() + dim][j] * (CT + d - t1); }  
   RTcoord     Coordtp_br(int dim, int j, RTtimeStamp tp) const;
   RTcoord     CoordT_br (int dim, int j = 0, RTperiod d = 0) const
   { return Coordtp_br(dim, j, CT + d); }
  
   bool        shrinking () const;
   bool        expired   (RTperiod d = 0) const 
   { return t2 < CT + d; }   

   // Geometric topological operations
   //
   bool isEqual_2n  (const RTkey& k) const;
   bool isEqual_n   (const RTkey& k, RTperiod d = 0) const;   
   bool overlap_n   (const RTkey& k, RTperiod d = 0) const;
   bool overlap_n1  (const RTkey& k) const;
   bool contained_n (const RTkey& k, RTperiod d = 0) const;
   bool contain_n   (const RTkey& k, RTperiod d = 0) const;
   bool contained_n1(const RTkey& k) const;
   bool contain_n1  (const RTkey& k) const;
   bool contain_2n  (const RTkey& k) const;
    
   RTkey *intersect_n (const RTkey& k, RTperiod d = 0) const;
   double intersectArea_n1 (const RTkey& k, RTperiod h = 0) const;

   // expand functionality corresponds to RTnode::Union, only for two keys   
   //
   RTkey *expand (const RTkey& k, RTperiod h = 0) const;
 
   // contain should return true iff expand (k) returns a key equal to *this
   //
   bool contain (const RTkey& k) const;

   // Geometric metric operations
   //
   double area_n    (RTperiod d = 0) const; 
   double area_n1   (RTperiod h = 0) const;
   double margin_n  (RTperiod d = 0) const;  
   double margin_n1 (RTperiod h = 0) const;  
   double dist_n   (const RTkey& k, RTperiod d = 0) const;
   double dist_n1  (const RTkey& k, RTperiod h = 0) const;

#ifdef PRINTING_OBJECTS
   void Print(ostream& os) const;
#endif

   // coords[i][0] and coords[i][1] for i=0..Settings.GetDims()-1
   // store intercept (spatial extent) of an object at time instant
   // t1, for i=Settings.GetDims()..Settings.GetDims()*2-1 they store
   // speed values for the coresponding dimensions. This simplifies
   // coding of algorithms working in dual space.
   //
   RTcoord&     Speed(int dim, int j = 0)       { return coords[Settings.GetDims() + dim][j]; }
   RTcoord      Speed(int dim, int j = 0) const { return coords[Settings.GetDims() + dim][j]; }

   RTtimeStamp  t1;
   RTtimeStamp  t2;    
   RTcoord      coords[TPR_MAX_DIMS*2][2];

protected:
   // Time-interval versions of functions 
   //
   bool   overlapInt_n1  (const RTkey& k, RTtimeStamp& tmin, RTtimeStamp& tmax) const;
   bool   overlapInt_n1a (const RTkey& k, RTtimeStamp& tmin, RTtimeStamp& tmax) const;
   double areaInt_n1     (RTtimeStamp tmin, RTtimeStamp tmax) const;
};

#endif