rtkey.cpp

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

//------------------------------------------------------------------------
//      RTkey.cpp
//      ---------
//      Implements the key of the tree node
//            
//      TPR-tree - Index for continuously moving objects
//      July 2001 release, Aalborg University
//

#include "rt.h"
#include <string.h>
#include <fenv.h>
#include <algorithm>

#define min(a, b) ((a) < (b)? (a) : (b))
#define max(a, b) ((a) > (b)? (a) : (b))


//------------------------------------------------------------------------
//    RTkey 
//           

RTkey::RTkey() : 
       t1(0), t2(TPR_TS_INF) 
{ 
//  memset(coords, 0, 4*Settings.GetDims()*sizeof(RTcoord)); 
}

//-----------------------------------------------------------
RTkey::RTkey(const RTkey& k)
{
   t1   = k.t1;
   t2   = k.t2;
   for (int i = 0; i < Settings.GetDims()*2; i++)
   { 
      coords[i][0] = k.coords[i][0];
      coords[i][1] = k.coords[i][1]; 
   }    
}


//-----------------------------------------------------------
// Constructor for points
//
RTkey::RTkey(const RTcoord* pc,
             RTtimeStamp ts1, RTtimeStamp ts2) :
       t1 (ts1), t2 (ts2)
{
   for (int i = 0; i < Settings.GetDims()*2; i++) 
      coords[i][0] = coords[i][1] = pc[i];
}

//-----------------------------------------------------------
// Constructor for rectangles
//
RTkey::RTkey(const RTcoord* lc, const RTcoord* hc,
             RTtimeStamp ts1, RTtimeStamp ts2) :
       t1 (ts1), t2 (ts2)
{
   for (int i = 0; i < Settings.GetDims()*2; i++) 
   {
      coords[i][0] = lc[i];
      coords[i][1] = hc[i];
   }
}

//-----------------------------------------------------------
char* RTkey::ToString  (RT* tree, char* str, int isLeaf) const
{
   int i;
   int ln = Length(tree, isLeaf);

   if (Settings.GetTreeType() == RTsettings::tRtree) ln -= 2 * sizeof(RTtimeStamp);

   if (isLeaf)
      for (i = 0; i <  Settings.GetDims()*2; i++) 
         memcpy(str + i * sizeof(RTcoord), &coords[i][0], sizeof(RTcoord));
   else 
      memcpy(str, coords, ln); 

   if (Settings.GetTreeType() == RTsettings::tRtree) 
   {
      memcpy (str + ln, &t1, sizeof(RTtimeStamp));
      memcpy (str + ln + sizeof(RTtimeStamp), &t2, sizeof(RTtimeStamp));
   }

   return str;
}

//-----------------------------------------------------------
RTkey& RTkey::FromString(RT* tree, const char* str, int isLeaf)
{
   int i;
   int ln = Length(tree, isLeaf);
   
   if (Settings.GetTreeType() == RTsettings::tRtree) ln -= 2 * sizeof(RTtimeStamp);

   if (isLeaf) 
      for (i = 0; i < Settings.GetDims()*2; i++)
      {  
	 memcpy(&coords[i][0], str + i * sizeof(RTcoord), sizeof(RTcoord));
         coords[i][1] = coords[i][0];
      }
   else 
     memcpy(coords, str, ln); 

   if (Settings.GetTreeType() != RTsettings::tTPRtree && !isLeaf)
      for (i = Settings.GetDims(); i < Settings.GetDims()*2; i++) 
 	 coords[i][1] = coords[i][0] = 0;     // all rectangles are static

   if (Settings.GetTreeType() == RTsettings::tRtree) 
   {
      memcpy (&t1, str + ln, sizeof(RTtimeStamp));
      memcpy (&t2, str + ln + sizeof(RTtimeStamp), sizeof(RTtimeStamp));
   }
  
   return *this;
}

//-----------------------------------------------------------
int RTkey::Length(RT* tree, int isLeaf) const
{
  return tree->MinKeyLength(isLeaf);
} 

//-----------------------------------------------------------
bool RTkey::shrinking () const
{
   for (int i = 0; i < Settings.GetDims(); i++)
      if (Speed(i, 1) < Speed(i, 0)) return true;

   return false;
}

//-----------------------------------------------------------
void RTkey::ComputeNaturalt2 ()
{
   RTtimeStamp xt;  

   t2 = TPR_TS_INF;
   for (int i = 0; i < Settings.GetDims(); i++)
      if (Speed(i, 1) < Speed(i, 0)) 
      {
         xt = (coords[i][1] - coords[i][0]) / (Speed(i, 0) - Speed(i, 1));
         if (finite(xt) && t1 + xt < t2) t2 = t1 + xt;
      }
}

//-----------------------------------------------------------
void RTkey::SetRefTS (RTtimeStamp rts)
{
   for (int i = 0; i < Settings.GetDims(); i++)
   {
      coords[i][0] += coords[Settings.GetDims() + i][0] * (rts - t1);
      coords[i][1] += coords[Settings.GetDims() + i][1] * (rts - t1);
   } 
   t1 = rts;
}


//-----------------------------------------------------------
void RTkey::SetRefTS_br (RTtimeStamp rts)
{

// Linux  modified by dvu linbin UCSB

   fesetround(FE_DOWNWARD);      // lower bound - round towards minus infinity 
   for (int i = 0; i < Settings.GetDims(); i++) {      
      coords[i][0] += coords[Settings.GetDims() + i][0] * (rts - t1);
   }
   fesetround(FE_UPWARD);        // upper bound - round towards plus infinity 
   for (int i = 0; i < Settings.GetDims(); i++) {
         coords[i][1] += coords[Settings.GetDims() + i][1] * (rts - t1); 
   } 
   fesetround(FE_TONEAREST);        // restore rounding mode 
   t1 = rts;
}

//-----------------------------------------------------------
RTcoord RTkey::Coordtp_br(int dim, int j, RTtimeStamp tp) const
{ 

// Linux  modified by dvu & linbin UCSB

    fesetround(j ? FE_UPWARD : FE_DOWNWARD);
    RTcoord rez = coords[dim][j] + coords[Settings.GetDims() + dim][j] * (tp - t1);
    fesetround(FE_TONEAREST);    // retore rounding mode
    return rez;
} 


//-----------------------------------------------------------
bool RTkey::isEqual_2n  (const RTkey& k) const
{
   for (int i = 0; i < Settings.GetDims()*2; i++)
   {
      if (coords[i][0] != k.coords[i][0]) return false;
      if (coords[i][1] != k.coords[i][1]) return false;
   }
   return (t1 == k.t1 && t2 == k.t2);
}

//-----------------------------------------------------------
bool RTkey::isEqual_n  (const RTkey& k, RTperiod d) const
{
   if (expired(d) || k.expired(d)) return false; 

   for (int i = 0; i < Settings.GetDims(); i++)
   {
      if (CoordT(i, 0, d) != k.CoordT(i, 0, d) ||
          CoordT(i, 1, d) != k.CoordT(i, 1, d)) return false;
   }
   return true;
}

//-----------------------------------------------------------
bool RTkey::overlap_n (const RTkey& k, RTperiod d) const
{
   if (expired(d) || k.expired(d)) return false; 
 
   for (int i = 0; i < Settings.GetDims(); i++)
      if (CoordT(i, 0, d) > k.CoordT(i, 1, d) || 
          CoordT(i, 1, d) < k.CoordT(i, 0, d)) return false;
   return true;
}

//-----------------------------------------------------------
bool RTkey::overlap_n1  (const RTkey& k) const
{
   RTtimeStamp tmin = max(t1, k.t1);
   RTtimeStamp tmax = min(t2, k.t2);

   return overlapInt_n1(k, tmin, tmax);   
}

//-----------------------------------------------------------
//  RTkey::overlapInt_n1 checks if two moving hyper-rectangles intersect
//  between tmin and tmax, if so, returns a time period (tmin..tmax) when 
//  they intersect 
//   

bool RTkey::overlapInt_n1 (const RTkey& k, RTtimeStamp& tmin, RTtimeStamp& tmax) const
{
   
   for (int i = 0; i < Settings.GetDims(); i++)
   {
      if (tmin > tmax) return false;
      // k is completely above or bellow in i-th dimension
      if (k.Coordtp(i, 0, tmin) > Coordtp(i, 1, tmin) &&  
          k.Coordtp(i, 0, tmax) > Coordtp(i, 1, tmax) ||
          k.Coordtp(i, 1, tmin) < Coordtp(i, 0, tmin) &&
          k.Coordtp(i, 1, tmax) < Coordtp(i, 0, tmax)) 
         return false;
       
      // adjust tmin
      if (k.Coordtp(i, 0, tmin) > Coordtp(i, 1, tmin))  // k above *this at tmin
         tmin = (Coordtp(i, 1, 0) - k.Coordtp(i, 0, 0)) /
                (k.Speed(i, 0) - Speed(i, 1));
      else if (k.Coordtp(i, 1, tmin) < Coordtp(i, 0, tmin)) // k below *this at tmin
              tmin = (Coordtp(i, 0, 0) - k.Coordtp(i, 1, 0)) /
                     (k.Speed(i, 1) - Speed(i, 0)); 

      // adjust tmax
      if (k.Coordtp(i, 0, tmax) > Coordtp(i, 1, tmax))  // k above *this at tmax
         tmax = (Coordtp(i, 1, 0) - k.Coordtp(i, 0, 0)) /
                (k.Speed(i, 0) - Speed(i, 1));
      else if (k.Coordtp(i, 1, tmax) < Coordtp(i, 0, tmax)) // k below *this at tmax
              tmax = (Coordtp(i, 0, 0) - k.Coordtp(i, 1, 0)) /
                     (k.Speed(i, 1) - Speed(i, 0)); 
   }   
   return true;
}

//-----------------------------------------------------------
// This version is used only from the intersectArea_n1 !!!
// It is a little speeded up version 
// (based on the assumption that both keys have the same t1)
// 
bool RTkey::overlapInt_n1a (const RTkey& k, RTtimeStamp& tmin, RTtimeStamp& tmax) const
{
   float k0tmin, k0tmax, k1tmin, k1tmax, a0tmin, a0tmax, a1tmin, a1tmax;
   
   for (int i = 0; i < Settings.GetDims(); i++)
   {
      // !!! 
      // If tmin == tmax regions may overlap (according to
      // inclusive semantics used everywhere else (expiration,
      // queries)), but their intersection area is 0 
      // !!!
      if (tmin >= tmax) return false;    

      k0tmin = k.Coordtp(i, 0, tmin);
      k0tmax = k.Coordtp(i, 0, tmax);
      k1tmin = k.Coordtp(i, 1, tmin);
      k1tmax = k.Coordtp(i, 1, tmax);
      a1tmin = Coordtp(i, 1, tmin);
      a1tmax = Coordtp(i, 1, tmax);
      a0tmin = Coordtp(i, 0, tmin);
      a0tmax = Coordtp(i, 0, tmax);

      // k is completely above or bellow in i-th dimension
      if (k0tmin > a1tmin && k0tmax > a1tmax ||
          k1tmin < a0tmin && k1tmax < a0tmax ) return false;
       
      // adjust tmin
      if (k0tmin > a1tmin)  // k above *this at tmin
         tmin = (coords[i][1] - k.coords[i][0]) /
                (k.Speed(i, 0) - Speed(i, 1));
      else if (k1tmin < a0tmin) // k below *this at tmin
              tmin = (coords[i][0] - k.coords[i][1]) /
                     (k.Speed(i, 1) - Speed(i, 0)); 

      // adjust tmax
      if (k0tmax > a1tmax)  // k above *this at tmax
         tmax = (coords[i][1] - k.coords[i][0]) /
                (k.Speed(i, 0) - Speed(i, 1));
      else if (k1tmax < a0tmax) // k below *this at tmax
              tmax = (coords[i][0] - k.coords[i][1]) /
                     (k.Speed(i, 1) - Speed(i, 0)); 
   }   
   return true;
}

//-----------------------------------------------------------
bool RTkey::contained_n (const RTkey& k, RTperiod d) const
{
   if (expired(d) || k.expired(d)) return false; 

   for (int i = 0; i < Settings.GetDims(); i++)
       if (CoordT_br(i, 1, d) > k.CoordT_br(i, 1, d) || 
           CoordT_br(i, 0, d) < k.CoordT_br(i, 0, d)) return false;  
   return true;
}

//-----------------------------------------------------------
bool RTkey::contained_n1 (const RTkey& k) const
{
   if (Settings.GetTreeType() == RTsettings::tRtree) 
   {
      float beg, end, kbeg, kend;

      if (t1 < k.t1) return false; 
      if (t2 > k.t2) return false; 

      for (int i = 0; i < Settings.GetDims(); i++)
      {
         if (Speed(i, 0) == 0.0)
         {
            beg = coords[i][0];
            end = coords[i][1];
         }
         else if (Speed(i, 0) > 0.0)
	      {
                 beg = coords[i][0];
                 end = Coordtp(i, 1, t2);
              }
              else
	           {
                 beg = Coordtp(i, 0, t2);
                 end = coords[i][1];
              }
         if (k.Speed(i, 0) == 0.0)
         {
            kbeg = k.coords[i][0];
            kend = k.coords[i][1];
         }
         else if (k.Speed(i, 0) > 0.0)
	      {
                 kbeg = k.coords[i][0];
                 kend = k.Coordtp(i, 1, t2);
              }
              else
	      {
                 kbeg = k.Coordtp(i, 0, t2);
                 kend = k.coords[i][1];
              }

         if (beg < kbeg || end > kend) return false;
      }
   }
   else
   {
      if (t2 > k.t2) return false;           // It should be contained in time
      if (!contained_n (k)) return false;    // It should be contained at CT
      
      if (t2 == TPR_TS_INF) 
      {                             // Its velocity vector(s) should be contained
         for (int i = 0; i < Settings.GetDims(); i++) 
            if (Speed(i, 1) > k.Speed(i, 1) || 
                Speed(i, 0) < k.Speed(i, 0)) return false; 
      }
      else                         // It should be contained at t2
         for (int i = 0; i < Settings.GetDims(); i++) {
            if (Coordtp_br(i, 1, t2) > k.Coordtp_br(i, 1, t2) || 
                Coordtp_br(i, 0, t2) < k.Coordtp_br(i, 0, t2)) return false;  
         }   
   }

   return true;
}

//-----------------------------------------------------------
bool RTkey::contain_n (const RTkey& k, RTperiod d) const
{
   return k.contained_n (*this, d);
}

//-----------------------------------------------------------
bool RTkey::contain_n1 (const RTkey& k) const
{
   return k.contained_n1 (*this);
}

//-----------------------------------------------------------
bool RTkey::contain_2n (const RTkey& k) const
{
   if (Settings.IsCTUnionMode())
   {
      for (int i = 0; i < Settings.GetDims(); i++)
         if (k.Coordtp(i, 0, CT) < Coordtp(i, 0, CT) ||
             k.Coordtp(i, 1, CT) > Coordtp(i, 1, CT) ||
             k.Speed(i, 0) < Speed(i, 0) ||
             k.Speed(i, 1) > Speed(i, 1)) return false;
   }
   else
   {
      for (int i = 0; i < Settings.GetDims() * 2; i++)
         if (k.coords[i][0] < coords[i][0] ||
             k.coords[i][1] > coords[i][1]) return false;
   }
   return true;   
}

//-----------------------------------------------------------
//  contain should return true iff expand (k) returns a key equal to *this
//
bool RTkey::contain (const RTkey& k) const
{
   if (Settings.GetTreeType() == RTsettings::tTPRtree && 
       Settings.GetUnionMode() == RTsettings::unInsRefT) 
      return contain_2n(k);

   return contain_n1 (k); 
}

//-----------------------------------------------------------
//   In this implementation RTkey::intersect_n returns a static 
//   result (with zero speeds) - a snapshot of the intersection 
//   at time CT + d.
//
RTkey* RTkey::intersect_n(const RTkey& k, RTperiod d) const
{
   RTkey *result;

   if (!overlap_n(k, d))  return((RTkey*) NULL);

   result = (RTkey*) k.Copy();

   for (int i = 0; i < Settings.GetDims(); i++)
   {
      result->coords[i][0] = max(k.CoordT(i, 0, d), CoordT(i, 0, d));
      result->coords[i][1] = min(k.CoordT(i, 1, d), CoordT(i, 1, d)); 
   }
   result->t1 = CT + d; 

   return result;
}

//-----------------------------------------------------------
//   RTkey::intersectarea_n1 returns an integral of intersection area of