rtobserver.cpp

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

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

//#define NDEBUG

#include <string.h>
#include <iomanip.h>
#include <time.h>
#include <memory.h>
#include <unistd.h>
#include "rtobserver.h"

struct RTlevelStats
{
   long   nodes;
   long   entries;
   double volume;
   double deadspace;
   double overlap;
   double margin;
   RTkey  avgMBRsize; // average MBR size at this level (differences of spatial 
                      // coordinates and speeds), where spacial coordinates are for CT 
};

static RTlevelStats* level_stats;
static long          allNodes;
static long          count_;
static long          size_internal;
static long          size_leaves;

enum FAedgeType {fa_begin, fa_end};

struct FAedgeix
{
   RTcoord     edge;
   int         ix;
   FAedgeType  edgeType;
};

//----------------------------------------------------
extern "C" int
FAedgeixcmp(const void *x, const void *y)
{
   if (((FAedgeix*) x)->edge > ((FAedgeix*) y)->edge) 
      return 1;
   if (((FAedgeix*) x)->edge < ((FAedgeix*) y)->edge) 
      return -1;
   if (((FAedgeix*) x)->edgeType > ((FAedgeix*) y)->edgeType)
      return 1;
   if (((FAedgeix*) x)->edgeType < ((FAedgeix*) y)->edgeType) 
      return -1;
   
   return 0;
}

//----------------------------------------------------
RTobserver::~RTobserver()
{
   // getting rid of empty files
   //
   if (!insertinf.tellp())  
   {
      insertinf.close();
      unlink (RTOBS_INSERTINF);
   }
   if (!nodeinf.tellp())     
   {
      nodeinf.close();
      unlink (RTOBS_NODESINF);
   }
   if (!queryinf.tellp())     
   {
      queryinf.close();
      unlink (RTOBS_SEARCHINF);
   }
   if (!splitinf.tellp())     
   {
      splitinf.close();
      unlink (RTOBS_SPLITINF);
   }
}

//----------------------------------------------------
void RTobserver::ResetFlowInfo()
{
   num_dealocate = 0;
   num_removetop = 0;
   num_split = 0;
   num_sortsplit = 0;
}

//----------------------------------------------------
void RTobserver::ResetSearchInfo()
{
   for (int i = 0; i < GIST_MAX_LEVELS; i++)
   {
      qual_entries[i]  = 0;
      total_entries[i] = 0;
      total_nodes[i]   = 0;
   }
}

//----------------------------------------------------
void RTobserver::Inform (RTNotification nc, int axis, int index)
{
   static char* axes_names[] = {"d1b", "d1e", "d2b", "d2e", "d3b", "d3e", "d4b", "d4e"};

   if (nc == ON_SOFT_SPLIT)
   {
      if (SplitInfoOn)
         splitinf << "SOFT, Axis " << axes_names[axis]
                  << ", i = " << index << endl;
      if (FlowInfoOn) num_sortsplit++;
   }      
}

//----------------------------------------------------
void RTobserver::Inform (TNotification nc)
{
   if (nc == ON_SEARCHEND)
      OutSearchInfo();

   if (nc == ON_OVERFLOWTEND && InsertInfoOn)
   {
      insertinf << "reinsertion end" << endl;
      insertinf << endl;
   }
}

//----------------------------------------------------
void RTobserver::Inform (TNotification nc, int qual, int total, int level)
{
   if (nc == ON_SEARCHNODE && SearchInfoOn)
   {
      qual_entries[level]  += qual;
      total_entries[level] += total;
      total_nodes[level]++;
   }
}

//----------------------------------------------------
void RTobserver::Inform (TNotification nc, const GiSTentry& entry1,
                         const GiSTentry& entry2, GiSTpage page)
{
}

//----------------------------------------------------
void RTobserver::Inform (TNotification nc, const GiSTnode& node)
{
   switch (nc)
   {
   case ON_WRITENODE:
      if ((visObject == voNode || visObject == voPath) && 
          node.Path().Page() == visPath.Page())
         visPath = node.Path();
      break;

   case ON_DEALOCATE:
      if (FlowInfoOn) num_dealocate++;
      if (InsertInfoOn)
         insertinf << "del " << node.Path().Page() << endl;
      break;

   case ON_OVERFLOWTSTART:
      if (InsertInfoOn)
      {
         insertinf << endl;
         insertinf << "reinsertion start, node " << node.Path().Page() << endl;
      }
      break;

   case ON_SPLITSTART:
      if (SplitInfoOn)
      {
         int          m     = (int)((double)node.NumEntries() *
                                    ((RT*)GetGiST())->m() + 0.5);
         int          k     = node.NumEntries() - m;

         splitinf << "----------------------------------------------------------" << endl
                  << "Split at Level " << node.Level()
                  << " Page: " << node.Path().Page()
                  << " Current time: " << CT
                  << " Entries: " << node.NumEntries()
                  << " m = " << m
                  << " k = " << k << endl;
      }
   }
}

//----------------------------------------------------
void RTobserver::Inform (TNotification nc, GiSTlist<GiSTentry*>& elist)
{
   if (elist.IsEmpty()) return;

   GiSTentry* en = elist.RemoveFront();
   elist.Prepend(en);
   if (nc == ON_REMOVETOP && FlowInfoOn) num_removetop++;
}

//----------------------------------------------------
void RTobserver::Inform (TNotification nc, const GiSTnode& node1,
                                           const GiSTnode& node2)
{
   if (nc == ON_SPLIT && FlowInfoOn) num_split++;

   if (nc == ON_SPLIT && SplitInfoOn)
   {
      splitinf << "Split to: " << node1.NumEntries() << " and " << node2.NumEntries() << endl;
   }

   if (nc == ON_SPLIT && node1.IsLeaf() && InsertInfoOn)
   {
      insertinf << node1.Path().Page() << " -> " <<  node1.Path().Page() << " ";
      insertinf << " and " << node2.Path().Page() << " ";
      insertinf << endl;
   }
}

//----------------------------------------------------
void RTobserver::Inform (TNotification nc, const GiSTpredicate& pred)
{
   if (nc == ON_SEARCH && SearchInfoOn)
   {
      queryinf << "--------------------------------------------------" << endl;
      queryinf << "Query: " << pred << endl;
      queryinf << "--------------------------------------------------" << endl;
      ResetSearchInfo();
   }
}

//----------------------------------------------------
void RTobserver::OutSearchInfo()
{
   int result = 0;

   for (int i = GIST_MAX_LEVELS - 1; i >= 0; i--)
   {
      if (total_nodes[i] > 0)
      {
         result = 1;
         queryinf << "Level " << i << ": " << total_nodes[i]
                  << " nodes accessed; ";
         if (total_entries[i])
            queryinf << setprecision(3)
                     << (qual_entries[i] * 100/total_entries[i])
                     << "% entries qualified ";
         if (total_entries[i] && !i)
            queryinf << "[" << qual_entries[i] << "]";
         queryinf << endl;
      }
   }
   if (result)
      queryinf << endl;
}

//----------------------------------------------------
void RTobserver::OutFlowInfo()
{
   insertinf << "Number of split calls: "     << num_split << endl;
   insertinf << "Number of sort split calls: "<< num_sortsplit << endl;
   insertinf << "Number of removetop calls: " << num_removetop << endl;
   insertinf << "Number of dealocate calls: " << num_dealocate << endl;
}

//----------------------------------------------------
// RecursivePlaneSweep 
// 
// It assumes that cutKey is a static key with refernce timestamp
// equal to CT
// 

static double RecursivePlaneSweep (GiSTnode& node, const RTkey* cutKey,
                                   RTindexArray& curSet, int dim)
{
   int j, k;
   double area = 0;

   if (dim == Settings.GetDims()) area = cutKey->area_n(0);
   else
   {
      RTcoord      lowSide;
      int          Num2 = curSet.GetNum() * 2;
      RTentry*     tmpentry;
      RTindexArray newCurSet(curSet.GetNum());
      RTkey*       newCutKey = (RTkey*) cutKey->Copy();
      FAedgeix*    edges = new FAedgeix[Num2];

      for (j = 0, k = 0; k < curSet.GetNum(); k++, j++)
      {
         tmpentry = (RTentry*)(node[curSet[k]].Ptr());

         edges[j].edge     = tmpentry->CoordT(dim, 0);
         edges[j].edgeType = fa_begin;
         edges[j].ix       = curSet[k];
         edges[++j].edge   = tmpentry->CoordT(dim, 1);
         edges[j].edgeType = fa_end;
         edges[j].ix       = curSet[k];
      }

      qsort(edges, Num2, sizeof(FAedgeix), FAedgeixcmp);

      k = 0;
      lowSide = edges[0].edge;
      newCurSet.Reset();
      for(;;)
      {
         for(; edges[k].edge == lowSide && k < Num2; k++)
         {
            if (edges[k].edgeType == fa_begin) newCurSet.Add(edges[k].ix);
            else newCurSet.Remove(edges[k].ix);
         }
         if (newCurSet.IsEmpty())
            if (k == Num2) break;
            else
            {  // skipping the empty cut
               lowSide = edges[k].edge;
               continue;
            }

         // Form the slice
         newCutKey->coords[dim][0] = lowSide;
         newCutKey->coords[dim][1] = edges[k].edge;
         area += RecursivePlaneSweep(node, newCutKey, newCurSet, dim + 1);
         lowSide = edges[k].edge;
      }
      delete[] edges;
      delete   newCutKey;
   }

   return area;
}

//----------------------------------------------------
double RTobserver::FilledArea(GiSTnode& node, RTentry& uentry)
{
   RTindexArray  curSet(node.NumEntries());

   for (int i = 0; i < node.NumEntries(); i++) curSet.Add(i);
   uentry.SetRefTS_br(CT);

   return RecursivePlaneSweep(node, &uentry.bbox(), curSet, 0);
}

//----------------------------------------------------
// TraverseTree 
// 
// Recursive function that visits all nodes of the tree and calls
// visitor on each node
//

void RTobserver::TraverseTree (GiSTpath& path, void (RTobserver::*visitor)(RTnode& node))
{
   RTnode* node = (RTnode*) ReadNode(path);

   (this->*visitor)(*node);    // visiting the node

   // going down the tree
   //
   if (!node->IsLeaf())
      for (int i = 0; i < node->NumEntries(); i++)
      {
         path.MakeChild((*node)[i]->Ptr());
         TraverseTree (path, visitor);
      }       
   path.MakeParent();   // no (more) children, go one level up

   delete node;
}

//----------------------------------------------------
//  ReadTree 
//
//  It is a visitor function for TraverseTree. It computes overlap,
//  dead space, and a number of entries for each level
//

void RTobserver::ReadTree (RTnode& node)
{
   double     overlap, deadspace, unionarea, areaAll, areaFilled;
   RTentry   *tmpentry, *unionentry;
   int        i, level;

   if (!(count_%100)) 
   {
      cout << "\rProgress : " << count_*100 / allNodes << "%";
      cout.flush();
   }

   if (!node.NumEntries()) return;

   level = node.Level();
   level_stats[level].nodes++;
   level_stats[level].entries += node.NumEntries();

   // compute unionarea
   //
   unionentry = (RTentry*) node.Union();
   assert(unionentry); // cannot be NULL
   unionarea = unionentry->bbox().area_n(0);
   
   if (node.Path().Page() != GiSTRootPage) level_stats[level].volume += unionarea;  
   if (node.Path().Page() != GiSTRootPage) 
      level_stats[level].margin += unionentry->bbox().margin_n(0);  

   for (i = 0; i < Settings.GetDims(); i++) 
   {
      level_stats[level].avgMBRsize.coords[i][0] += unionentry->CoordT(i, 1) - 
                                                    unionentry->CoordT(i, 0);
      level_stats[level].avgMBRsize.coords[Settings.GetDims()+i][0] += unionentry->Speed(i, 1) -
                                                           unionentry->Speed(i, 0);