tvindex.c

TV-tree的c实现源码

/* 
 
                  COPYRIGHT NOTICE
 
This material was developed by Christos Faloutsos and King-Ip Lin
at the University of Maryland, College Park, Department of Computer Science.
Permission is granted to copy this software, to redistribute it
on a nonprofit basis, and to use it for any purpose, subject to
the following restrictions and understandings.
 
1. Any copy made of this software must include this copyright notice
in full.
 
2. All materials developed as a consequence of the use of this
software shall duly acknowledge such use, in accordance with the usual
standards of acknowledging credit in academic research.
 
3. The authors have made no warranty or representation that the
operation of this software will be error-free or suitable for any
application, and they are under under no obligation to provide any
services, by way of maintenance, update, or otherwise.  The software
is an experimental prototype offered on an as-is basis.
 
4. Redistribution for profit requires the express, written permission
of the authors.
 
*/

// Author : $Author$
// Date : $Date$
// Id : $Id$
// $Id: index.C,v 1.3 1996/04/18 21:50:24 kilin Exp kilin $ 
#include <iostream.h>
#include <fstream.h>
#include <assert.h>
#include <stdlib.h>
#include "TVdefine.h"
#include "TVconstants.h"
#include "TVvector.h"
#include "TVelement.h"
#include "TVrectangle.h"
#include "TVsimbuf.h"
#include "TVnode.h"
#include "TVindexstat.h"
#include "TVindexpara.h"
#include "TVindex.h"
#include "TVutil.h"


TVTree::TVTree() : stats(PHASES)
{
  root = NULL;

}

TVTree::TVTree(istream& is)
{
  int phases;

  root = NULL;
  is >> ip;
  cout << "Input no of phases : ";
  is >> phases;
  stats = TVTree_Stat(phases);
  stats.SetPageSize(ip.page_size);
}

TVTree::TVTree(istream& is, int phases) : stats(phases)
{

  root = NULL;
  is >> ip;
  cout << "Input no of phases : ";
  stats.SetPageSize(ip.page_size);
}

TVTree::TVTree(ifstream& is)
{
  int phases;

  root = NULL;
  is >> ip;
  is >> phases;
  stats = TVTree_Stat(phases);
  stats.SetPageSize(ip.page_size);
}

TVTree::TVTree(ifstream& is, int phases)
{

  root = NULL;
  is >> ip;
  stats = TVTree_Stat(phases);
  stats.SetPageSize(ip.page_size);
}

TVTree::TVTree(TVTree_Para& nip, int phases) : ip(nip), stats(phases)
{
  root = NULL;
  stats.SetPageSize(ip.page_size);
}

TVTree::TVTree(const TVTree& ind)
{
  root = ind.root;
  ip = ind.ip;
  stats = ind.stats;
}

// Load index from disk
// Requires: ReadData(ifstream&, int&) function to read in the data item
//	     where the int will return the number of bytes            

void CreateLeaf(ifstream& ifile, TVNode** nptr, int pagesize, char *(*ReadData)(ifstream&, int&), VCOM_TYPE (*gfeat)(int, char*), int loaddim)
{
  int c, maxc;
  ifile >> maxc >> c;
  *nptr = new Leaf_TVNode(maxc);
  for (int i = 0; i < c; i++)
      {
	 int bytes;
         char* word = ReadData(ifile, bytes);
         Leaf_Element e(word, bytes);
	 e.GetTVector(loaddim, gfeat);
         (*nptr)->Put(e, pagesize);
      }
}

void RecurCreateInternal(ifstream& ifile, TVNode** nptr, int level, int pagesize, char *(*ReadData)(ifstream&, int&), VCOM_TYPE (*gfeat)(int, char*))
{
  int c, maxc;
  ifile >> maxc >> c;
  *nptr = new Internal_TVNode(level, maxc);
  for (int i = 0; i < c; i++)
      {
         TVBranch b;
         TVRectangle d;
         TVNode *newchild;
         ifile > d;
         b = d;
         if (level > 1)
            RecurCreateInternal(ifile, &newchild, level - 1, pagesize, ReadData, gfeat);
         else
            CreateLeaf(ifile, &newchild, pagesize, ReadData, gfeat, d.GetCenterDim());
         b.ConnectChild(newchild);
         (*nptr)->Put(b, pagesize);
      }
}

TVTree::TVTree(char *filename, char *(*ReadData)(ifstream&, int&), VCOM_TYPE (*gfeat)(int, char*))
{
  ifstream ifile(filename, ios::in);
  int level;

  ifile >> ip.page_size >> ip.unfold_dim >> ip.min_fill_percent >> ip.reinsert_percent >> ip.pickbranch_compare_count;
  ifile >> level;
  if (level)
       // create an internal root
       RecurCreateInternal(ifile, &root, level, ip.page_size, ReadData, gfeat);
  else
       CreateLeaf(ifile, &root, ip.page_size, ReadData, gfeat, ip.unfold_dim);
  ifile.close();
  stats.SetPageSize(ip.page_size);
}

TVTree::~TVTree()
{
  delete root;
}

// Save a TV-tree to disk
// WriteData : A procedure to write the data onto the disk

void SaveTVBranch(ofstream& of, TVBranch* b)
{
   TVector center = b->GetBound().GetCenter();
   of < b->GetBound();
   of << endl;
/*  For non-rectangle
   of << center.GetDim() << "\n";
   for (int j=0; j < center.GetDim(); j++)
      of << center[j] << "  ";
   of << "\n" << b->GetBound().GetRadius() << "  " << b->GetBound().GetSigDim() << endl;
*/
}

void RecurSaveTVNode(ofstream& of, TVNode* n, void(*WriteData)(ofstream&, char *, int), int rootlevel)
{
  TVNodeIter nit(n);
  if (n->TVNodeType() == INTERNAL_NODE)
     {
        // preorder transveral, store itself first

        for (int i = 0; i < rootlevel - n->GetLevel(); i++)
            of << "  ";
        of << n->MaxCount() << "  " << n->GetCount() << endl;
        for (TVNodeEntry ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
           {
            SaveTVBranch(of, ne.u.b);
            RecurSaveTVNode(of, ne.u.b->FetchChild(), WriteData, rootlevel);
           }
     }
  else
     {
	// At leaf
        for (int i = 0; i < rootlevel - n->GetLevel(); i++)
            of << "  ";
        of << n->MaxCount() << "  " << n->GetCount() << endl;
        for (TVNodeEntry ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
	   {
	      WriteData(of, (*(ne.u.e))(), ne.u.e->BytearraySize());
	      of << endl;
	   }
     }
}

void TVTree::SaveTVTree(char* filename, void(*WriteData)(ofstream&, char *, int))
{
   ofstream ofile(filename, ios::out);

   ofile << ip.page_size << "  " << ip.unfold_dim << "  " << ip.min_fill_percent << " " << ip.reinsert_percent << "  " << ip.pickbranch_compare_count <<  "\n";
   if (root)
      {
            ofile << root->GetLevel() << "\n";
            RecurSaveTVNode(ofile, root, WriteData, root->GetLevel());
      }
  ofile.close();
}

TVTree& TVTree::operator=(const TVTree& ind)
{
  root = ind.root;
  ip = ind.ip;
  stats = ind.stats;
  return *this;
}

float TVTree::GetMinFillPercent() const
{
  return ip.min_fill_percent;
}

int TVTree::GetUnfolddim() const
{
  return ip.unfold_dim;
}

int TVTree::GetHeight() const
{
  if ((root) && (root->TVNodeType() == INTERNAL_NODE))
    return root->GetLevel() + 1;  // height of tree, 1 = only one node
  else
    return 1;
}

void TVTree::IncrementPhase()
{
   stats.IncrementPhase();
}


int RecurValidityCheck(TVNode *n)
{
   int result = TRUE;
   TVNodeIter nit(n);
   if (((Internal_TVNode *)n)->ParentOfLeaf())
      {
        // parent of leaf
        for (TVNodeEntry ne = nit.Iter(); (result && ne.Defined()); ne = nit.Iter())
            {
                 TVNodeIter nit2(ne.u.b->FetchChild());
                 TVRectangle Bound = ne.u.b->GetBound();
                 for (TVNodeEntry ne2 = nit2.Iter(); result && ne2.Defined(); ne2 = nit2.Iter())
                     {
                       result = Bound.Contain(ne2.u.e->GetTVector().ProjectFront(Bound.GetCenterDim()));
                         if (!(result))
                           {
                              cout << "INVALID! Error in :\n";
                              cout << "Parent branch : " << ne.u.b << "\n";
                              cout << "Child  : " << ne2.u.e << "   TVector (first dimens) " << ne2.u.e->GetTVector().ProjectFront(ne.u.b->GetBound().GetCenterDim()) << "\n";
                           }
                      }
            }
      }
   else
      {
	// Internal node
        for (TVNodeEntry ne = nit.Iter(); (result && ne.Defined()); ne = nit.Iter())
            {
                 TVNodeIter nit2(ne.u.b->FetchChild());
                 TVRectangle Bound = ne.u.b->GetBound();
                 for (TVNodeEntry ne2 = nit2.Iter(); result && ne2.Defined(); ne2 = nit2.Iter())
                     {
                       result = Bound.Contain(ne2.u.b->GetBound());
                         if (!(result))
                           {
                              cout << "INVALID! Error in :\n";
                              cout << "Parent branch : " << ne.u.b << "\n";
                              cout << "Child  branch : " << ne2.u.b << "\n";
                           }
                     }
                 if (result)
                    result = RecurValidityCheck(ne.u.b->FetchChild());
            }
      }
   return result;
}


int TVTree::ValidityCheck()
{
   int result= TRUE;
   if (root)
      {
         if (root->TVNodeType() == INTERNAL_NODE)
            result = RecurValidityCheck(root);
      }
   return result;
}

int RecurCount(TVNode* n)
{
  int hit = 0;
  TVNodeIter nit(n);
  if (n->TVNodeType() == INTERNAL_NODE)
     {

        for (TVNodeEntry ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
           {
             hit += RecurCount(ne.u.b->FetchChild());
           }
     }
  else
     {
        for (TVNodeEntry ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
	   {
		hit++;
	   }
     }
   return hit;
}


int TVTree::Count() const
{
  return (root ? RecurCount(root) : 0);
}



// Print TVTree

void RecurPrintTVTree(ostream& os,  TVNode* n, void(*PrintData)(ostream&, char *), int oneperline)
{
   int count=0;
   TVNodeIter nit(n);
   TVNodeEntry ne;
   if (n->TVNodeType() == INTERNAL_NODE)
      {
         os << "\nChild no. " << count++ << "\n";
         os << *((Internal_TVNode *)n);
         for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
             RecurPrintTVTree(os, ne.u.b->FetchChild(), PrintData, oneperline);
         os << "\n";
      }
   else
      {
        os << "\nLeaf : ";
        ((Leaf_TVNode *)n)->PrintLeaf(os, PrintData, oneperline);
      }
}

ostream& TVTree::TVTreePrint(ostream& os, void(*PrintData)(ostream&, char *), int oneperline)
{
   stats.DummyPhase();
   os << ip;
   if (root)
      {
         if (root->TVNodeType() == INTERNAL_NODE)
            RecurPrintTVTree(os, root, PrintData, oneperline);
         else
           ((Leaf_TVNode *)root)->PrintLeaf(os, PrintData, oneperline);
      }
   else
      os << "TVTree empty.";
   stats.RestorePhase();
   return os;
}

// This version don't print leaf data
void RecurPrintTVTree(ostream& os,  TVNode* n)
{
   int count=0;
   TVNodeIter nit(n);
   TVNodeEntry ne;
   if (n->TVNodeType() == INTERNAL_NODE)
      {
         os << "\nChild no. " << count++ << "\n";
         os << (Internal_TVNode *)n;
         for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
             RecurPrintTVTree(os, ne.u.b->FetchChild());
         os << "\n";
      }
   else
      {
        os << "\nLeaf : ";
	os << *((Leaf_TVNode *)n);
      }
}


ostream& operator<<(ostream& os, TVTree& ind)
{

   ind.stats.DummyPhase();
   os << ind.ip;
   if (ind.root)
      {
         if (ind.root->TVNodeType() == INTERNAL_NODE)
            RecurPrintTVTree(os, ind.root);
         else
           os << *((Leaf_TVNode*)ind.root);
      }
   else
      os << "TVTree empty.";
   ind.stats.RestorePhase();
   return os;
}


// Print stats

void TVTree::PrintStats(ostream& os)
{
  os << stats;
}

// Gathering statistics

void TVTree::RecurGatherTreeStats(TVNode *n)
{
  TVNodeIter nit(n);
  TVNodeEntry ne;
  stats.AddIntStat(TREESIZE, n->Size());
  if (n->TVNodeType() == INTERNAL_NODE)
     {
        stats.IncrementStat(NODECOUNT);
        for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
            RecurGatherTreeStats(ne.u.b->FetchChild());
     }
  else
     stats.IncrementStat(LEAFCOUNT);
}


void TVTree::GatherTreeStats()
{
   stats.SetZero(NODECOUNT).SetZero(LEAFCOUNT).SetZero(TREESIZE);
   if (root)
      RecurGatherTreeStats(root);
}

int TVTree::GetIntStat(int  code)
{
   return stats.GetIntStat(code);
}

void TVTree::RecurFreeTree(TVNode *n)
{
  TVNodeIter nit(n);
  TVNodeEntry ne;
  if (n->TVNodeType() == INTERNAL_NODE)
     {
        for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
            RecurGatherTreeStats(ne.u.b->FetchChild());
	((Internal_TVNode *)n)->Internal_TVNode::~Internal_TVNode();
     }
  else
    ((Leaf_TVNode *)n)->Leaf_TVNode::~Leaf_TVNode();
}


void TVTree::FreeTree()
{
   RecurFreeTree(root); 
}