rt.cpp

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

                      int num_rem)
{
    GiSTlist<GiSTentry*> deleted;
    int i;
    RTentry *uentry, *e;
    distix  *dvec = new distix[node->NumEntries()];

    assert(num_rem > 0 && num_rem <= remains.GetNum());

    uentry = ((RTnode*)node)->UnionEntries(remains, 0, remains.GetNum());

    // compute distance of each node to center of bounding box,
    // and sort by decreasing distance
    for (i = 0; i < remains.GetNum(); i++)
    {
       dvec[i].ix   = remains[i];
       e = ((RTentry *)((*node)[remains[i]].Ptr()));
       dvec[i].dist = (RTcoord) e->bbox().dist_n1(uentry->bbox(), GetParam());
       if (!finite(dvec[i].dist)) dvec[i].dist = TPR_SS_INF;
    }
    delete uentry;

    sort (dvec, dvec + remains.GetNum());
    for (i = 0; i < num_rem; i++)
    {
       out.Add(dvec[i].ix);
       remains.Remove(dvec[i].ix);
    }

    delete dvec;
}

//----------------------------------------------------
//  Bulk loading methods.
//  Both LoadTopDownSTR and LoadBottomUp assume that data contains 
//  moving points with GiSTpage's
//  These methods should be called right after Create(). 
//  If the tree allready contains some data, it will be lost, 
//  but pages won't be deallocated.
//

void RT::LoadTopDownSTR (RTsortArray& data)
{
   int maxKeysLeaf;        // # of entries in a leaf node
   int maxKeysInternal;    // # of entries in an internal node   
   int numFullNodes;       // # of full nodes in one level
   int numLevels;          // # of levels in tree
   int numKeys;            // # of keys(points) in data
   int maxKeysInNode;      // max. # of keys (data-points) in or below one node
   int maxKeysInParent;    // max. # of keys (data-points) in or below the parent node
   int restKeys;           // # of keys left for last node that is not full
   RTsortArray *inArray, *outArray; // arrays used for loading the tree
   int level, i, j;            // loop counters
   int (*cmpf)(const void *, const void *); 

   assert (FixedKeyLength(true) && FixedKeyLength(false));

   lastChange = reft = CT;
   numEntries = data.GetNum();  
 
   RToffset = 0;
   RTparam  = GetParam();
   cmpf = (Settings.GetLoadAlg() == RTsettings::aNormal && GetParam() != 0.0) ? 
          CompareCoordParam : CompareCoord;

   if (Settings.GetLoadAlg() == RTsettings::aCSD || 
       Settings.GetLoadAlg() == RTsettings::aCDS || 
       Settings.GetLoadAlg() == RTsettings::aDSC || 
       Settings.GetLoadAlg() == RTsettings::aSDC)
   {
      RTsortEntry* se;
      outArray = new RTsortArray(data.GetNum(), SIZEOF_PLUSREC); 
     
      // Precomputing absolute speeds and velocity angles
      for (i = 0; i < data.GetNum(); i++)
      {
         se = (RTsortEntry*) outArray->NewRec();
         memcpy (se, data[i], SIZEOF_LEAFREC);
         if (Settings.GetDims() == 1) se->AbsSpeed() = se->Velocity(0); 
         else
	 {
            se->AbsSpeed() = 0;
            for (j = 0; j < Settings.GetDims(); j++) 
               se->AbsSpeed() += se->Velocity(j) * se->Velocity(j);
            se->AbsSpeed() = sqrt (se->AbsSpeed());

            // All angles are in a range from -PI/2 to 3*PI/2
            for (j = 0; j < Settings.GetDims() - 1; j++) 
	    {
               se->VelocityAngle(j) = se->Velocity(j) != 0.0 || se->Velocity(j+1) != 0.0 ?
  		                      atan(se->Velocity(j+1) / se->Velocity(j)) : 0;
               if (se->Velocity(j) < 0.0) se->VelocityAngle(j) += M_PI;
            }
	 }
      }      
   }
   else outArray = &data;

   numKeys         = outArray->GetNum();
   maxKeysLeaf     = MaxEntries(true);
   maxKeysInternal = MaxEntries(false);
   numLevels       = 1 + (int)ceil(::log(ceil((double)numKeys/maxKeysLeaf))/
                                   ::log(maxKeysInternal));
   // sort from top down
   cout << "sorting" << endl;
   if (numLevels > 1)
   {
      // level 1 below root
      maxKeysInNode = maxKeysLeaf * (int)::pow(maxKeysInternal, numLevels - 2); 
      outArray->SortNTimes(0, numKeys, maxKeysInNode, GetAlpha(), cmpf);  
      
      // lower levels (non-GiST numbering of levels!)
      for (level = 2; level < numLevels; level++)  
      {
         maxKeysInParent = maxKeysInNode;
         maxKeysInNode   = maxKeysLeaf * 
                           (int)::pow(maxKeysInternal, numLevels - level - 1); 
         numFullNodes = numKeys / maxKeysInParent;
         // all the full nodes
         for (i = 0; i < numFullNodes; i++) 
            outArray->SortNTimes(i * maxKeysInParent, maxKeysInParent, 
                                 maxKeysInNode, GetAlpha(), cmpf);
         // now the last node which might not be full
         if ((restKeys = numKeys - numFullNodes * maxKeysInParent) > 0)
            outArray->SortNTimes(numFullNodes * maxKeysInParent, restKeys, 
                                 maxKeysInNode, GetAlpha(), cmpf);  
      }
   }

   // Now load the tree bottom up

   cout << "loading leaf level" << endl;
   inArray = LoadNodes(*outArray, 0);
   cout << "   # nodes in leaf level = " << inArray->GetNum() << endl;
 
   if (outArray != &data) delete outArray; 
 
   // Load all other levels
   for (level = 1; level < numLevels; level++)
   {
//    cout << "loading next level" << endl;
      outArray = LoadNodes(*inArray, level);
//    cout << "   # nodes in level = " << outArray->GetNum() << endl;
      // Free inArray and make outArray the new inArray
      delete inArray;
      inArray = outArray;
   }
   delete inArray;

#ifdef RT_DEL_LOOKUP
   levels = numLevels;
#endif
}

//----------------------------------------------------
//   LoadBottomUp, depending on the value of Settings.GetLoadAlg(), calls eihter
//   Hilbert sort or STR sort
// 

void RT::LoadBottomUp(RTsortArray& data)
{
   int maxKeysLeaf;        // # of entries in a leaf node
   int maxKeysInternal;    // # of entries in an internal node   
   int numLevels;          // # of levels in tree
   RTsortArray *inArray, *outArray; // arrays used for loading the tree
   RTsortEntry* se;
   int level, i, j;            // loop counters
   int (*cmpf)(const void *, const void *); 

   assert (FixedKeyLength(true) && FixedKeyLength(false));

   RTparam = GetParam();
   maxKeysLeaf     = MaxEntries(true);
   maxKeysInternal = MaxEntries(false);
   numLevels       = 1 + (int)ceil(::log(ceil((double)data.GetNum()/maxKeysLeaf))/
                                   ::log(maxKeysInternal));   
   lastChange = reft = CT;
   numEntries = data.GetNum();  

   outArray = &data;

   for (level = 0; level < numLevels; level++)
   {
      // At this point outArray can be either point data or rectangle data
      // First we produce inArray by augmenting outArray with:
      //   1. Center points, if outArray is rectangles
      //   2. Velocity angles and absolute speed, if the algorithm requires

      RToffset = level ? FixedKeyLength(false) / sizeof(RTcoord) : 0;
      cmpf = (Settings.GetLoadAlg() == RTsettings::aNormal && GetParam() != 0.0) ? 
             CompareCoordParam : CompareCoord;

      if (level || Settings.IsDSAlg())  
      {
         inArray = new RTsortArray(outArray->GetNum(), 
                                   !level ? SIZEOF_PLUSREC :
                                   (Settings.IsDSAlg() ? SIZEOF_LEVCPLUSREC : SIZEOF_LEVCREC));
         
         for (i = 0; i < outArray->GetNum(); i++)
         {
            se = (RTsortEntry*) inArray->NewRec();
            
            if (level)  // compute center - at the beginning of coord, temporarily
	    {
               se->pid = ((RTsortEntry*) (*outArray)[i])->pid;
	       for (j = 0; j < Settings.GetDims()*2; j++) 
                  se->coords[j] = (((RTsortEntry*) (*outArray)[i])->Rcoord(j,0) +
                                   ((RTsortEntry*) (*outArray)[i])->Rcoord(j,1)) / 2; 
            }
            else memcpy (se, (*outArray)[i], SIZEOF_LEAFREC);
            
            if (Settings.IsDSAlg()) 
	    {  
               // Precompute absolute speeds and velocity angles
               if (Settings.GetDims() == 1) se->AbsSpeed() = se->Velocity(0); 
               else
    	       {
                  se->AbsSpeed() = 0;
                  for (j = 0; j < Settings.GetDims(); j++) 
                     se->AbsSpeed() += se->Velocity(j) * se->Velocity(j);
                  se->AbsSpeed() = sqrt (se->AbsSpeed());

                  // All angles are in the range from -PI/2 to 3*PI/2
                  for (j = 0; j < Settings.GetDims() - 1; j++) 
	          {
                     se->VelocityAngle(j) = se->Velocity(j)   != 0.0 || 
                                            se->Velocity(j+1) != 0.0 ?
  		                            atan(se->Velocity(j+1) / se->Velocity(j)) : 0;
                     if (se->Velocity(j) < 0.0) se->VelocityAngle(j) += M_PI;
                  }
	       }
            } 
           
            if (level)      
	    {
	       // Make so that rectangle goes first followed by additional info
	       // That is how LoadNodes likes it and comparison routines are programed
               memmove(se->coords + FixedKeyLength(false) / sizeof(RTcoord), se->coords,
                       Settings.IsDSAlg() ? 3 *sizeof(RTcoord) * Settings.GetDims() : 
                                     2 *sizeof(RTcoord) * Settings.GetDims());
               memcpy(se->coords, ((RTsortEntry*) (*outArray)[i])->coords, 
                      FixedKeyLength(false));
            }                 
         }
         if (outArray != &data) delete outArray; 
      }
      else inArray = outArray;    // nothing to add (!level && !Settings.IsDSAlg())
             
      cout << "sorting";
      if (Settings.GetLoadAlg() == RTsettings::aNormalHilbert || 
          Settings.GetLoadAlg() == RTsettings::aDualHilbert)
         inArray->HilbertSort();
      else
         inArray->SortNTimes(0, inArray->GetNum(), 
                             level ? maxKeysInternal : maxKeysLeaf, GetAlpha(), cmpf);
      cout << ", loading" << endl;
      outArray = LoadNodes(*inArray, level);
      if (inArray != &data) delete inArray;  
   }

   delete outArray;

#ifdef RT_DEL_LOOKUP
   levels = numLevels;
#endif
}

//----------------------------------------------------
// LoadNodes loads the coresponding tree level, returning the sortArray 
// of the next level 
//

RTsortArray* RT::LoadNodes(RTsortArray& data, int level)
{
   RTsortArray* outArray;
   RTnode*      node;
   RTentry*     entry;
   int          i, j, k;
   int          dataNum1 = data.GetNum() - 1;      
   int          maxKeys  = MaxEntries(level == 0); 
  
   outArray = new RTsortArray((int)ceil((double)data.GetNum() / maxKeys), 
                              SIZEOF_LEVELREC);
   
   node = (RTnode*) CreateNode();
   node->SetTree(this);
   node->SetLevel(level);
   node->SetRefTS(reft);
   node->Path().MakeChild(Store()->Allocate());  

#ifdef RT_DEL_LOOKUP
   if (!delLookUp0) InitDelLookUp(data.GetNum());
   levels++;
   assert(levels == level + 1);
#endif
 
   // Form a node of empty entries to make a loop faster 
   entry = (RTentry*) node->CreateEntry();
   for (j = 0; j < maxKeys; j++) node->InsertBefore(*entry, j);
   delete entry;

   for (i = 0, j = 0; i < data.GetNum(); i++)
   {
      // Stick the values into the entry in the node
      ((RTentry*)(*node)[j].Ptr())->SetValues((RTsortEntry*) data[i]);
      
#ifdef RT_DEL_LOOKUP
      if (!level) delLookUp0[(*node)[j].Ptr()->Ptr()] = node->Path().Page();     
      else        delLookUp [(*node)[j].Ptr()->Ptr()] = node->Path().Page(); 
#endif
      if (Settings.GetTreeType() == RTsettings::tRtree)
      {
         ((RTentry*)(*node)[j].Ptr())->Sett1(CT);
         ((RTentry*)(*node)[j].Ptr())->Sett2(CT + GetParam());
      }  
    
      // When the node is full 
      if (++j == maxKeys || i == dataNum1)
      {
      	// Write the node, create UnionEntry, add it to outArray
 	      if (j < maxKeys)     // the last half-full node  
            for (k = maxKeys - 1; k >= j; k--) node->DeleteEntry(k);
         WriteNode(node);

         entry = (RTentry*) node->Union();
         entry->SetLevel(level+1);
         entry->SetPtr(node->Path().Page());
         entry->GetValues((RTsortEntry*) outArray->NewRec());
         delete entry;

         // if we still have entries, allocate new page 
         if (i < dataNum1) 
            node->Path().MakeSibling(Store()->Allocate());  
         j = 0;
      } 
   } 

   // if we have only one element in outArray, make our node the root node
   if (outArray->GetNum() == 1) 
   {
      Store()->Deallocate(node->Path().Page());     
      node->Path().MakeRoot();

#ifdef RT_DEL_LOOKUP
      // correct delLookUp arrays  
      for (i = 0; i < node->NumEntries(); i++) 
      {
         if (!level) delLookUp0[(*node)[i].Ptr()->Ptr()] = node->Path().Page();     
         else        delLookUp [(*node)[i].Ptr()->Ptr()] = node->Path().Page(); 
      }
#endif
      WriteNode(node);
   }  

   delete node;

   return outArray;  
}

//----------------------------------------------------
RTsortArray* RT::Unload() const
{
   RTsortArray* ret;   
   RTnode*      node;
   RTentry*     e;
   GiSTpath     path;
   int          maxKeysLeaf;
   int          maxKeysInternal; 
   int          numRecs;     // estimate of # of records in a leaf-level
   GiSTcursor*  cursor;
    
   path.MakeRoot();
   node    = (RTnode*) ReadNode(path);
   maxKeysLeaf     = MaxEntries(true);
   maxKeysInternal = MaxEntries(false);
   numRecs = node->IsLeaf() ? node->NumEntries() : 
             maxKeysLeaf * node->NumEntries() * 
             (int)::pow (maxKeysInternal, node->Level() - 1);
   delete node;

   ret = new RTsortArray(numRecs, SIZEOF_LEAFREC);

   cursor = Search(truePredicate);
   while((e = (RTentry*) cursor->Next()) != NULL)
   {
      e->SetRefTS(CT);
      e->GetValues((RTsortEntry*) ret->NewRec());
      delete e;
   }
   delete cursor;      

   return ret;
}