rtnode.cpp

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

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

//#define NDEBUG       // if NDEBUG is defined asserts do not work

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

#include "rtprofile.h"
#include "rtobserver.h"

struct edgeix
{
   int         ix;
   RTtimeStamp edge;
};

extern "C" int RTcmp(const void *x, const void *y);

//--------------------------------------------------------------------
//    RTindexArray  -  array of entry indexes for split algorithms
//
  
RTindexArray::RTindexArray(const RTindexArray& from)
{ 
   len   = from.len;
   num   = from.num;
   array = new int[len];
   for (int i = 0; i < num; i++) array[i] = from.array[i];  
}

//----------------------------------------------------
RTindexArray& RTindexArray::operator= (const RTindexArray& from)
{
   delete[] array;
   len   = from.len;
   num   = from.num;
   array = new int[len];
   for (int i = 0; i < num; i++) array[i] = from.array[i];

   return *this;
}

//----------------------------------------------------
RTindexArray& RTindexArray::DefaultInit ()
{
   num = len;
   for (int i = 0; i < num; i++) array[i] = i;
   return *this;
}

//----------------------------------------------------
int& RTindexArray::operator[] (int n) const
{
   assert(n < len);
   return array[n];
}

//----------------------------------------------------
RTindexArray& RTindexArray::Add   (int i)
{
   assert(num < len);
   array[num++] = i;
   return *this;
}

//----------------------------------------------------
RTindexArray& RTindexArray::Remove(int n)
{
   for (int i = 0; i < num; i++)
      if (array[i] == n)
      {
         array[i] = array[num-1];
         num--;
         break;
      }
   return *this;
}

//--------------------------------------------------------------------
extern "C" int
RTcmp(const void *x, const void *y)
{
  edgeix* i = (edgeix*)x;
  edgeix* j = (edgeix*)y;

  if (i->edge > j->edge) return  1;
  if (i->edge < j->edge) return -1;
  return 0;
}

//--------------------------------------------------------------------
//    RTnode
//
int RTnode::FixedLength() const 
{ 
   return ((RT*) Tree())->FixedKeyLength(IsLeaf()); 
}

//----------------------------------------------------
int RTnode::HeaderSize() const 
{ 
   return ((RT*) Tree())->HeaderSize(); 
}

//----------------------------------------------------
GiSTnode* RTnode::PickSplit()
{
   RTindexArray group1  (NumEntries());
   RTindexArray group2  (NumEntries());

   DoSplit(group1, group2);

   // distribute according to Group1 and Group2
   RTnode *rightnode = (RTnode *)Copy();

   assert(group1.GetNum() + group2.GetNum() == NumEntries());

   DeleteBulk(group2.GetArrayPointer(), group2.GetNum());
   rightnode->DeleteBulk(group1.GetArrayPointer(), group1.GetNum());

   return rightnode;
}

//----------------------------------------------------
GiSTentry* RTnode::Union() const
{
   return UnionEntries(RTindexArray(NumEntries()).DefaultInit(), 
                       0, NumEntries(), true);
}

//----------------------------------------------------
void RTnode::DoSplit (RTindexArray& group1, RTindexArray& group2)
{
   if (Tree()->Observer())
      Tree()->Observer()->Inform(ON_SPLITSTART, *this);

   PROFILE_ACTION_BEGIN(profile_split);

   RstarSplit(group1, group2);

   PROFILE_ACTION_END(profile_split);
}

//----------------------------------------------------
void RTnode::Pack  (char *page)
{
   PROFILE_ACTION_BEGIN(profile_packnode);

   RT* rt = (RT*) Tree();
         
#ifdef RT_DEL_LOOKUP
   if (!rt->delLookUp0 && NumEntries()) rt->InitDelLookUp(RT_DEF_LOOKUP_SZ);
   if (Path().IsRoot()) rt->levels = Level() + 1;   

   GiSTpage* la = Level() ? rt->delLookUp : rt->delLookUp0;
   GiSTpage  pg = Path().Page();
   for (int i = 0; i < NumEntries(); i++) la[(*this)[i]->Ptr()] = pg;  
#endif 
   GiSTnode::Pack (page);

   PROFILE_ACTION_END(profile_packnode);
}

//----------------------------------------------------
void RTnode::SetRefTS (RTtimeStamp rts)
{
   if (Settings.GetTreeType() == RTsettings::tTPRtree)
   {  
      if (IsLeaf())
         for (int i = 0; i < NumEntries(); i++)
            ((RTentry*)(*this)[i].Ptr())->SetRefTS(rts);
      else 
         for (int i = 0; i < NumEntries(); i++)
            ((RTentry*)(*this)[i].Ptr())->SetRefTS_br(rts);
      refts = rts; 
   }
}

// Delete look up
/*
//----------------------------------------------------
void RTnode::InsertBefore(const GiSTentry &entry, int index)
{
   const RTentry& rte = (const RTentry&) entry;

   assert (Settings.GetTreeType() != RTsettings::tTPRtree || rte.RefTS() == refts);
//   if (rte.RefTS() > refts) SetRefTS(rte.RefTS());
//   else if (rte.RefTS() < refts) rte.SetRefTS(refts);
   GiSTnode::InsertBefore (rte, index);
}
*/

//------------------------------------------------
// SearchMinPenalty returns where a new entry should be inserted.
//

GiSTpage RTnode::SearchMinPenalty(const GiSTentry &newEntry) const
{
    GiSTentry  *minEntry   = NULL;
    RTpenalty  *minPenalty = ((const RTentry&) newEntry).CreatePenalty();
    RTpenalty  *penalty    = ((const RTentry&) newEntry).CreatePenalty();
    RTpenalty  *tmpPenalty;

    for (int i=0; i< NumEntries(); i++)
    {
       RTentry *e = (RTentry*) (*this)[i].Ptr();
       e->Penalty(newEntry, *penalty, true);
       if (*penalty && (!minEntry || (*penalty) < (*minPenalty)))
       {
          minEntry   = e;
          tmpPenalty = minPenalty;
          minPenalty = penalty;
          penalty    = tmpPenalty;
       }
    }
    if (!minEntry)   
       for (int i=0; i< NumEntries(); i++)
       {
          RTentry *e = (RTentry*) (*this)[i].Ptr();
          e->Penalty(newEntry, *penalty);
          if (!minEntry || (*penalty) < (*minPenalty))
          {
             minEntry   = e;
             tmpPenalty = minPenalty;
             minPenalty = penalty;
             penalty    = tmpPenalty;
          }
       }

    delete minPenalty;
    delete penalty;
    return minEntry->Ptr();
}

//----------------------------------------------------
bool RTnode::CheckUnion (const RTindexArray& ix,
                         int min, int max, const RTentry& br) const
{
   for (int i = min; i < max; i++)
      if (!((RTentry*)(*this)[ix[i]].Ptr())->bbox().contained_n1(br.bbox())) 
         return false;
   return true;
}

//----------------------------------------------------
RTentry* RTnode::UnionEntries(const RTindexArray& ix,
                              int min, int max, bool actual) const
{
   if (min == max) return NULL;

   bool first    = true;
   int  j, i, to = Settings.GetTreeType() == RTsettings::tTPRtree ? 
                   Settings.GetDims()*2 : Settings.GetDims();    
   RTentry *u = (RTentry*) (*this)[ix[min]].Ptr()->Copy();
   RTentry *RTe;
   RTcoord  c;