rtobserver.cpp

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

   }
   level_stats[level].avgMBRsize.t2 += unionentry->t2();

   // compute overlap, add all entry areas
   //
   areaAll = 0;
   for (i = 0; i < node.NumEntries(); i++)
   {
      tmpentry = (RTentry*) node[i].Ptr();
      areaAll += tmpentry->bbox().area_n(0);
   }

   areaFilled = FilledArea (node, *unionentry);

// asserts may incorrectly fire because of the floating point errors
// assert(unionarea >= areaFilled);
   deadspace = unionarea - areaFilled;
   
// assert(areaAll >= areaFilled);
   overlap   = areaAll - areaFilled;

// assert (deadspace >= 0 && deadspace <= unionarea);
// assert (overlap   >= 0);
   level_stats[level].overlap   += overlap;
   level_stats[level].deadspace += deadspace;

   delete unionentry;
   count_++;
}

//----------------------------------------------------
//  OutTreeNodeInfo
//
//  It is a visitor function for TraverseTree. It outputs textual info
//  about each node into nodeinf file
//

void RTobserver::OutTreeNodeInfo (RTnode& node)
{
   RT* maintree = (RT*)GetGiST();

   if (!node.NumEntries()) return; 

   int level = node.Level();

   nodeinf << "Level: " << level << " " 
           << "Page: "  << node.Path().Page() << endl; 
   for (int i = 0; i < node.NumEntries(); i++)
      nodeinf << (GiSTentry&) node[i] << endl;  
   nodeinf << endl;
 
// nodeinf << (node.Size() * 100)/(maintree->PageSize()) << "%  " << endl;
}

//----------------------------------------------------
//  CountNodes 
//
//  It is a visitor function for TraverseTree. It counts the number of
//  nodes in a tree. Needed for progress percentage output in ReadTree
//  only
//

void RTobserver::CountNodes (RTnode& node)
{
   if (node.Level()) size_internal += node.Size();
   else              size_leaves   += node.Size();
   if (node.Level()) allNodes      += node.NumEntries();
}

//----------------------------------------------------
//  VisualizeTreeNode 
//
//  It is a visitor function for TraverseTree. It visualizes the
//  levels of the tree according to visDepth.
//

void RTobserver::VisualizeTreeNode (RTnode& node)
{
   if (node.Path().IsRoot()) visualizer.Measure (node);
   if (!visDepth || node.Path().Length() <= visDepth || node.Level() <= -visDepth)
      visualizer.Visualize (node);
}

//----------------------------------------------------
//  VisualizeLevelNode 
//
//  It is a visitor function for TraverseTree. It visualizes one
//  level of the tree according to visDepth.
//

void RTobserver::VisualizeLevelNode (RTnode& node)
{
   if (node.Path().IsRoot()) visualizer.Measure (node);
   if (node.Path().Length() == visDepth - 1 || node.Level() == -visDepth)
      for (int i = 0; i < node.NumEntries(); i++)
         visualizer.Visualize (*(RTentry*)node[i].Ptr());   
   else if (node.Path().Length() == visDepth || node.Level() + 1 == -visDepth)
      visualizer.Visualize (node);
}

//----------------------------------------------------
void RTobserver::ChooseRandomPath(GiSTpath& path)
{
   GiSTnode* node;
   GiSTpage  page = GiSTRootPage;

   path.Clear();
   for (;;)
   {
      path.MakeChild(page);
      node = ReadNode(path);
      if (node->IsLeaf() || !node->NumEntries()) break;
      page = (*node)[(int) (rand() / ((double)RAND_MAX + 1) * node->NumEntries())]->Ptr();
      delete node;
   }
   delete node;
}

//----------------------------------------------------
void RTobserver::OutNodeInfo()
{
   GiSTpath path;

   nodeinf << "- - - - - - - - - - - - - - - - - - - - - - - - " << endl;
   nodeinf << "CT: " << CT << endl << endl;
   
   path.MakeRoot();
   TraverseTree (path, &RTobserver::OutTreeNodeInfo);
}

//----------------------------------------------------
RTtreeStats* RTobserver::TreeProperties()
{
   RTtreeStats* ret;
   GiSTpath     path;
   int          i, j, levels;
   long         nodes_internal; 
   long         entries_internal;
   RT*          maintree = (RT*)GetGiST();
  
   level_stats = new RTlevelStats[GIST_MAX_LEVELS];
 
   for (i = 0; i < GIST_MAX_LEVELS; i++)
   {
      level_stats[i].avgMBRsize.t1  = CT;
      level_stats[i].avgMBRsize.t2  = 0;
      memset( level_stats[i].avgMBRsize.coords, 0, 4*Settings.GetDims()*sizeof(RTcoord));
      level_stats[i].nodes          = 0;
      level_stats[i].entries        = 0;
      level_stats[i].deadspace      = 0;
      level_stats[i].overlap        = 0;
      level_stats[i].volume         = 0;
      level_stats[i].margin         = 0;
   }

   allNodes = 1;
   count_   = 0;

   size_internal = 0;
   size_leaves = 0;

   // to enable progress measure...
   path.MakeRoot();
   TraverseTree (path, &RTobserver::CountNodes);

   path.MakeRoot();
   TraverseTree (path, &RTobserver::ReadTree);

   nodes_internal = allNodes - level_stats[0].nodes;

   cout << "\rProgress : 100%" << endl;

   // how many levels are not empty?
   levels = GIST_MAX_LEVELS;
   while (!level_stats[levels - 1].nodes) levels--;

   for (entries_internal = 0, i = 1; i < levels; i++)
      entries_internal += level_stats[i].entries; 

   if (!entries_internal && !level_stats[0].entries)
      ret = NULL;
   else
   {
      ret = new RTtreeStats;
      
      ret->levels          = levels;
      ret->entriesInternal = entries_internal;
      ret->entriesLeaf     = level_stats[0].entries;

      for (i = 0; i < levels; i++)
      {
         ret->avgMBRsizes[i].t1 = CT;
         for (j = 0; j < Settings.GetDims()*2; j++) 
            ret->avgMBRsizes[i].coords[j][0] = 
            ret->avgMBRsizes[i].coords[j][1] = level_stats[i].avgMBRsize.coords[j][0] /
                                               level_stats[i].nodes;
         if (finite(level_stats[i].avgMBRsize.t2)) 
            ret->avgMBRsizes[i].t2 = level_stats[i].avgMBRsize.t2 / level_stats[i].nodes;
         else ret->avgMBRsizes[i].t2 = TPR_TS_INF;
      }
   
      for (ret->deadspace = 0, i = 0; i < levels; i++) 
         ret->deadspace += level_stats[i].deadspace;
      for (ret->overlap = 0, i = 1; i < levels; i++) 
         ret->overlap += level_stats[i].overlap;
      ret->volumeLeaf = level_stats[0].volume;
      for (ret->volumeAll = 0, i = 0; i < levels; i++) 
         ret->volumeAll += level_stats[i].volume;
      for (ret->marginAll = 0, i = 0; i < levels; i++) 
         ret->marginAll += level_stats[i].margin;
      
      ret->utilInternal = nodes_internal ? 
                          (double)(size_internal * 100) / 
	                       (nodes_internal * maintree->PageSize()) : 0; 
      ret->utilLeaf     = (double)(size_leaves * 100) / 
                          (level_stats[0].nodes * maintree->PageSize());
   }
   delete[] level_stats;

   return ret;
}

//----------------------------------------------------
void RTobserver::Properties(ostream& os, bool opt)
{
   RTtreeStats  *props = TreeProperties();

   if (!props)
   {
      os << "Tree is empty" << endl;
      return;
   }
   
   os << "CT: " << setprecision(4) << setw(7) << CT 
      << " All vol: " << setprecision(6) << setw(8) << props->volumeAll 
      << " Leaf vol: " << setprecision(6) << setw(8) << props->volumeLeaf
//    << " Dead vol: " << setprecision(6) << setw(8) << props->deadspace 
      << " Margin: "  << setprecision(6) << setw(8) << props->marginAll 
      << " Overlap: " << setprecision(6) << setw(8) << props->overlap << endl;

   os << "Levels: " << props->levels << ",  ";
   os << "Fill: ";
   if (props->utilInternal != 0.0)
      os << "Internal = " << setprecision(3) << props->utilInternal << "% ";
   os << "Leaf = " << setprecision(3) << props->utilLeaf << "%" << endl;
   os << "Entries: ";
   if (props->entriesInternal)
      os << "Internal = " << props->entriesInternal << " ";
   os << "Leaf = " << props->entriesLeaf << endl;        

   if (opt)
   {
      RTtreeStats*              optProps;
      RT                        optTree;
      RTsettings::LoadAlgorithm old_alg  = Settings.GetLoadAlg();
      char                      tmpname[40] = "Properties.";   
      RT*                       mainTree = (RT*) GetGiST(); 
      RTsortArray*              data     = mainTree->Unload();

      // we sort the data according to page ids asssuming that
      // this is the order in which the data were loaded initially  
      data->Sort(ComparePid);          
   
      Settings.SetLoadAlg (old_alg == RTsettings::aDualHilbert || 
                           old_alg == RTsettings::aNormalHilbert ? 
                           RTsettings::aNormalHilbert : RTsettings::aNormal);
      sprintf(tmpname + strlen(tmpname), "%u", (unsigned) time(NULL));
      optTree.Create(tmpname);
      //      optTree.LoadTopDownSTR(*data);
      optTree.LoadBottomUp(*data);
      delete data;
      SetGiST(&optTree);
      optProps = TreeProperties();
      SetGiST(mainTree);
      optTree.Drop();
      Settings.SetLoadAlg (old_alg); 
   
      os << "Overhead of All vol: " << setprecision(6) << setw(8)
         << props->volumeAll - optProps->volumeAll
         << " Leaf vol: " << setprecision(6) << setw(8) 
         << props->volumeLeaf - optProps->volumeLeaf 
//         << " Dead vol: " << setprecision(6) << setw(8) 
//         << props->deadspace - optProps->deadspace 
         << " Overlap: " << setprecision(6) << setw(8) 
         << props->overlap - optProps->overlap << endl;

      os << "Overhead %  All vol: " << setprecision(6) << setw(8)
         << (props->volumeAll - optProps->volumeAll) / optProps->volumeAll * 100 
         << " Leaf vol: " << setprecision(6) << setw(8) 
         << (props->volumeLeaf - optProps->volumeLeaf) / optProps->volumeLeaf * 100 
//         << " Dead vol: " << setprecision(6) << setw(8) 
//         << (props->deadspace - optProps->deadspace) / optProps->deadspace * 100 
         << " Overlap: " << setprecision(6) << setw(8) 
         << (props->overlap - optProps->overlap) / optProps->overlap * 100  << endl;

      delete optProps;
   }
   else 
   {
      os << "Average size of leaf     level MBR: " << props->avgMBRsizes[0] << endl; 
      os << "Average size of pre-leaf level MBR: " << props->avgMBRsizes[1] << endl; 
   }
   os << "- - - - - - - - - - - - - - - - - - - - - - - - " << endl;
   
   delete props; 
}

//----------------------------------------------------
void RTobserver::Refresh ()
{
   if (visObject != voNone && CT - visLast >= visInterval)
   {
      RTtimeStamp oldCT = CT;

      CT = visLast + visInterval;
      DoVisualization();
      visLast = CT;
      CT = oldCT;
   }
}

//----------------------------------------------------
void RTobserver::Visualize (RTvisobject what, int level, RTperiod interval)
{
   visObject   = what;
   visDepth    = level;
   visInterval = interval;
   if (visObject == voPath || visObject == voNode)
   {
      ChooseRandomPath (visPath);     // choosing a random path
      if (visDepth > 0) 
         while (visPath.Length() > visDepth) visPath.MakeParent();
      if (visObject == voNode && !visDepth) visDepth = -1;
   }
   else if (visObject == voLevel && !visDepth) visDepth = -1;
   if (visInterval == 0.0) 
   {
      DoVisualization ();
      visObject = voNone;
   }
   else visLast = CT;
}

//----------------------------------------------------
void RTobserver::DoVisualization ()
{
   static char*        prefixes[] = {"tree", "path", "node", "level"}; 
          char         fn[20];
  
   if (visObject != voNone) 
   {
      sprintf (fn, "%s%f.fig", prefixes[visObject], CT);
      visualizer.OpenFig (fn, ((RT*) GetGiST())->GetParam());
   }

   switch (visObject)
   {
   case voNode:      
   case voPath:
      VisualizePathNodes ();
      break;

   case voTree :
   case voLevel:
      GiSTpath path;

      path.MakeRoot();
      if (visObject == voTree) 
         TraverseTree (path, &RTobserver::VisualizeTreeNode);
      else
      {
         visualizer.Colorful (true);
         TraverseTree (path, &RTobserver::VisualizeLevelNode);
         visualizer.Colorful (false);
      }
   }
}

//----------------------------------------------------
void RTobserver::VisualizePathNodes ()
{
   RTnode*      node;
   RTentry*     entry;
   GiSTpath     path;

   for (int l = 0; true;)
   {
      path.MakeChild (visPath[l++]);
      node = (RTnode*) ReadNode (path);
      if (!node->NumEntries()) break;    // abort - everything has expired
      if (visDepth == l || node->Level() + 1 == -visDepth || 
          visObject == voPath && (visDepth >= 0 || node->Level() < -visDepth))
      {
         if (path.IsRoot()) visualizer.Measure(*node);
         visualizer.Visualize(*node);   // draw the node
      }

      // aborting if leaves or necessary depth is reached
      if (visDepth == l || node->IsLeaf()) break;

      // aborting if the whole visPath can not be found anymore,
      // e.g., beacause of large portions of the tree being expired
      //
      if ((entry = (RTentry*) node->SearchPtr(visPath[l])) == NULL) break; 
      if (entry->Level() == -visDepth || visObject == voNode && l == visDepth - 1)
      {
         visualizer.Measure  (*entry);
         visualizer.Visualize(*entry);  // draw the entry enclosing the visualized nodes
      }
      delete entry;
      delete node;
   }
   delete node;
}