rtentry.cpp

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

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

#include "rtprofile.h"
#include "rt.h"
#include <algorithm>

using namespace std;

//------------------------------------------------------------------------
//  RTpenalty
//

int RTpenalty::operator < (GiSTpenalty &p)
{
   RTpenalty& rtp = (RTpenalty&) p;

   if (amount == DBL_MIN) insertedInto->RefinePenalty(*this);
   if (rtp.amount == DBL_MIN) rtp.insertedInto->RefinePenalty(rtp);

   if (amount < rtp.amount) return 1;
   if (amount > rtp.amount) return 0;

   if (amount2 == DBL_MIN) insertedInto->RefinePenalty(*this);
   if (rtp.amount2 == DBL_MIN) rtp.insertedInto->RefinePenalty(rtp);

   if (amount2 < rtp.amount2) return 1;
   if (amount2 > rtp.amount2) return 0;

   if (amount3 == DBL_MIN) insertedInto->RefinePenalty(*this);
   if (rtp.amount3 == DBL_MIN) rtp.insertedInto->RefinePenalty(rtp);

   if (amount3 < rtp.amount3) return 1;

   return 0;
}

//------------------------------------------------------------------------
//  RTentry
//
   
void RTentry::InitKey()       
{ 
   if (key) delete key;
   key = CreateKey(); 
}

//------------------------------------------------
void RTentry::SetKey(const RTkey* k)       
{ 
   if (key) delete key;
   key = k->Copy(); 
}   

//------------------------------------------------
void RTentry::SetValues(const RTsortEntry* se)
{
   if (!key) InitKey();
   SetPtr(se->pid);
   if (IsLeaf())
      for (int i = 0; i < Settings.GetDims()*2; i++) 
      {
         memcpy(&Key().coords[i][0], se->coords + i, sizeof(RTcoord)); 
         Key().coords[i][1] = Key().coords[i][0];
      }
   else 
      memcpy(Key().coords, se->coords, 4*Settings.GetDims()*sizeof(RTcoord));
} 

//------------------------------------------------
void RTentry::GetValues(RTsortEntry* se) const
{
   assert(key);
   se->pid = Ptr();
   if (IsLeaf())
      for (int i = 0; i < Settings.GetDims()*2; i++) 
         memcpy(se->coords + i, &Key().coords[i][0], sizeof(RTcoord));
   else
      memcpy(se->coords, Key().coords, 4*Settings.GetDims()*sizeof(RTcoord));  
}

//------------------------------------------------
int RTentry::CompressedLength() const
{
   if (key) return ((RTkey*)key)->Length((RT*) Node()->Tree(), IsLeaf());
   else     return 0;
}

//------------------------------------------------
void RTentry::Compress (char *data) const
{
   assert (key);
   ((RTkey*)key)->ToString((RT*) Node()->Tree(), data, IsLeaf());   

   memcpy(data + CompressedLength(), &ptr, sizeof(ptr));
}

//------------------------------------------------
void RTentry::Decompress(const char *data, int entry_len)
{
   if (!key) key = CreateKey ();

   ((RTkey*)key)->FromString((RT*) Node()->Tree(), data, IsLeaf());
   //   assert (entry_len == ((RTkey*)key)->Length(IsLeaf()) + sizeof(GiSTpage));

   // Setting the key's reference time stamp. 
   // Not using RTkey::SetRefTS, because it would recompute the intercept
   if (Settings.GetTreeType() != RTsettings::tRtree) ((RTkey*)key)->t1 = ((RTnode*)node)->RefTS();

   memcpy(&ptr, data + entry_len - sizeof(ptr), sizeof(ptr));
}

//------------------------------------------------
//  RTentry::Penalty returns undefined penalty,
//  actual computation will be performed only when needed 
//  by means of RefinePenalty

void RTentry::Penalty(const GiSTentry &newEntry, GiSTpenalty &penalty, bool first) const
{
//   assert(newEntry.IsA() == RTENTRY_CLASS);
   RTpenalty& pen = (RTpenalty&) penalty; 
   RT*        rt  = (RT*) Node()->Tree();

   pen.SetEntries((const RTentry*) &newEntry, this);
 
   if (Key().expired()) pen.SetToMax();  // if it is expired 
   else  
      if (first)
      {
          RTentry&    e     = (RTentry &) *pen.insertee;
          RTkey&      myKey = (RTkey&)     Key(); 
          RTtimeStamp oldet2, oldmyKeyt2;
          
          if (myKey.contain (e.Key()))
          {
              pen         = 0.0;
              pen.amount2 = 0.0;
              pen.amount3 = myKey.area_n1(rt->GetParam());
          }   
          else pen = 1;
      }      
}

//------------------------------------------------
double RTentry::OverlapArea(const RTkey &k) const
{
   const GiSTnode& n      = *Node();
         double    retval = 0;

   PROFILE_ACTION_BEGIN(profile_overlaparea);
   
   for (int i = 0; i < n.NumEntries(); i++)
      if (i != Position())
         retval += k.intersectArea_n1(((RTentry *)n[i].Ptr())->bbox(), 
                                      ((RT*) n.Tree())->GetParam());

   PROFILE_ACTION_END(profile_overlaparea);

   return retval;
}

//---------------------------------------------------
//  TPR-tree penalty metric returns three numbers:
//  The first entry is the "Overlap Enlargement", which is used only 
//  at the level above the leaves. The second entry is the area enlargement, 
//  which is used everywhere else, and to break ties in the first entry. 
//  The third entry is just area, which is used to break ties 
//  in the second entry.
//

void RTentry::RefinePenalty (RTpenalty &penalty) const
{
  RT*          rt    = (RT*) Node()->Tree();
  RTentry&     e     = (RTentry &) *penalty.insertee;
  RTkey&       myKey = (RTkey&)     Key(); 
  RTtimeStamp  oldet2, oldmyKeyt2;

  PROFILE_ACTION_BEGIN(profile_choosesubtree);   

  if (!penalty.Definedness())
  {  
     // If we're one level up from the leaves, return overlap enlargement
     if (Level() == 1 && Settings.GetChoosesubtreeAlg() != RTsettings::cstArea)
     {
        RTkey* tmpkey     = myKey.expand(e.Key(), rt->GetParam());
        double curoverlap = OverlapArea(myKey);
        double newoverlap = OverlapArea(*tmpkey);
        penalty = max(newoverlap - curoverlap, 0.0);
        delete tmpkey;
     }
     else penalty = 0;
  }
  else if (penalty.Definedness() < 2)   
  {
     RTkey* tmpkey   = myKey.expand(e.Key(), rt->GetParam());
     penalty.amount2 = max(tmpkey->area_n1(rt->GetParam()) - 
                           myKey.area_n1(rt->GetParam()), 0.0);
     delete tmpkey;
  }
  else if (penalty.Definedness() < 3)   
        penalty.amount3 = myKey.area_n1(rt->GetParam());       

  PROFILE_ACTION_END(profile_choosesubtree);     
}

#ifdef PRINTING_OBJECTS
//---------------------------------------------------
void RTentry::Print(ostream& os) const
{
   key->Print(os);
   os << "->" << Ptr();
}
#endif