tvindexinsert.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: indexinsert.C,v 1.4 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 "TVreinsert.h"
#include "TVindexstat.h"
#include "TVindexpara.h"
#include "TVindex.h"
#include "TVutil.h"


// Class to return information from recursive calls to insert

RecurInsertReturn::RecurInsertReturn()
{
   irt = nochange;
   newcount = 0;
   branch = NULL;
   bound = NULL;
}

RecurInsertReturn::RecurInsertReturn(const RecurInsertReturn& rir)
{
   irt = rir.irt;
   newcount = rir.newcount;

   switch (irt) {
     case  newbound : {bound = new TVRectangle[newcount];
		      branch = NULL;
		      for (int i = 0; i < newcount; i++)
			 bound[i] = rir.bound[i];
                      }
		      break;
     case  newbranch : {
                       branch = new TVBranch[newcount];
		       bound = NULL;
		       for (int j = 0; j < newcount; j++)
			 branch[j] = rir.branch[j];
                       }
		       break;
     case  fromsplit : {
                       branch = new TVBranch[newcount];
		       bound = new TVRectangle[newcount+1];
		       for (int k = 0; k < newcount; k++)
			 {
			   branch[k] = rir.branch[k];
			   bound[k] = rir.bound[k];
			 }
		       bound[newcount] = rir.bound[newcount];
                       }
		       break;
     default :  {branch = NULL;
		bound = NULL;
		}
		break;
       }
     
}

RecurInsertReturn::~RecurInsertReturn()
{
   if (branch) 
     delete [] branch;
   if (bound)
     delete [] bound; 
}

RecurInsertReturn& RecurInsertReturn::operator=(const RecurInsertReturn& rir)
{
   irt = rir.irt;
   newcount = rir.newcount;

   switch (irt) {
     case  newbound : {
                      bound = new TVRectangle[newcount];
		      branch = NULL;
		      for (int i = 0; i < newcount; i++)
			 bound[i] = rir.bound[i];
		      }
		      break;
     case  newbranch : {
                       branch = new TVBranch[newcount];
		       bound = NULL;
		       for (int j = 0; j < newcount; j++)
			 branch[j] = rir.branch[j];
		       }
		       break;
     case  fromsplit : {
                       branch = new TVBranch[newcount];
		       bound = new TVRectangle[newcount+1];
		       for (int k = 0; k < newcount; k++)
			 {
			   branch[k] = rir.branch[k];
			   bound[k] = rir.bound[k];
			 }
		       bound[newcount] = rir.bound[newcount];
		       }
		       break;
     default : 
		break;
       }
     

   return *this;
}

RecurInsertReturn& RecurInsertReturn::FromSplit(const SplitReturn& sret)
{
   if (bound)
      delete [] bound;
   if (branch)
      delete [] branch;
   irt = fromsplit;
   newcount = sret.parts - 1;
   branch = new TVBranch[newcount];
   for (int i = 0; i < newcount; i++)
	{
          branch[i] = TVBranch(sret.bound[i + 1], sret.newnode[i]);
	  branch[i].WriteChild();
	}
   bound = new TVRectangle[sret.parts];
   for (int j = 0; j < sret.parts; j++)
	bound[j] = sret.bound[j];
   return *this;
}

RecurInsertReturn& RecurInsertReturn::Onebound(const TVRectangle& d)
{
   if (branch)
      delete [] branch;
   branch = NULL;
   if (bound)
      delete [] bound;
   irt = newbound;
   newcount = 1;
   bound = new TVRectangle[1];
   bound[0] = d;
   return *this;
}

RecurInsertReturn& RecurInsertReturn::Twobound(const TVRectangle& d0, const TVRectangle& d1)
{
   if (branch)
      delete [] branch;
   branch = NULL;
   if (bound)
      delete [] bound;
   irt = newbound;
   newcount = 2;
   bound = new TVRectangle[2];
   bound[0] = d0;
   bound[1] = d1;
   return *this;
}

RecurInsertReturn& RecurInsertReturn::Nbound(TVRectangle *d, int n)
{
   if (branch)
      delete [] branch;
   branch = NULL;
   if (bound)
      delete [] bound;
   irt = newbound;
   newcount = n;
   bound = new TVRectangle[n];
   for (int i = 0; i < n; i++)
      bound[i] = d[i];
   return *this;
}

RecurInsertReturn& RecurInsertReturn::Nbound(TVBranch *b, int n)
{
   if (branch)
      delete [] branch;
   branch = NULL;
   if (bound)
      delete [] bound;
   irt = newbound;
   newcount = n;
   bound = new TVRectangle[n];
   for (int i = 0; i < n; i++)
      bound[i] = b[i].GetBound();
   return *this;
}


// Recursion during insertion
// n : points to the current node on the traversal
// e1 : elements to be reinserted
// reinsertd : reinsert class, storing stuff to be reinserted
// *gfeat : pointer to the feature generation function
RecurInsertReturn  TVTree::RecurInsertElement(TVNode* n, Leaf_Element e1, const TVNodehandle& thishandle, ReInsertClass& reinsertd, VCOM_TYPE (*gfeat)(int, char*))
{
  RecurInsertReturn insertreturn, returnfromchild;
  TVBranch newb;

  if (n->TVNodeType() == INTERNAL_NODE)
     {
	int needwrite = FALSE;
        // Internal TVNode

        // accounting for the node read in
        stats.IncrementStat(READCOUNT);

        // pick branch
        int branchpicked = ((Internal_TVNode *)n)->PickTVBranch(e1, gfeat, ip.pickbranch_compare_count, ip.unfold_dim);

	// temporary removed the fetched branch from the tree
        // to be inserted back later
        // This is done because so the code can be made simpler 

        TVBranch bin = *((n->Fetch(branchpicked)).u.b);
        n->Remove(branchpicked, ip.min_fill_percent);


        // Recursion

        returnfromchild = RecurInsertElement(bin.FetchChild(), e1, bin.GetHandle(), reinsertd, gfeat);


        // Check result of recursion

	switch (returnfromchild.irt){
	  case newele   : // Parent of leaf level
			  {
                          if (((Internal_TVNode *)n)->ParentOfLeaf())
			     {
				// Check if new element is in the bounding region
				TVector evec = e1.GetTVector(bin.GetBound().GetCenterDim(), gfeat);
				if (!(bin.GetBound().Contain(evec)))
				   {
				      // Adjust bound
				      bin.UpdateBound(evec, ip.unfold_dim);
				      insertreturn.Onebound(bin.GetBound());
				      stats.IncrementStat(WRITECOUNT);
				      needwrite = TRUE;
				   }
			     }
			   else
			     {
				assert(0);
			     }
			   }
			   break;
	  case newbound  : // New bound at the child, see if update necessary    
			   {
			   int curbound = 0;
			   for (; (curbound < returnfromchild.newcount) && (bin.GetBound().Contain(returnfromchild.bound[curbound])); curbound++)
			       ;
			   if (curbound < returnfromchild.newcount)
			      {
				 for (; (curbound < returnfromchild.newcount); curbound++)
				    bin.UpdateBound(returnfromchild.bound[curbound], ip.unfold_dim);
				 insertreturn.Onebound(bin.GetBound());
				 stats.IncrementStat(WRITECOUNT);
				 needwrite = TRUE;
			      }
			   }
			   break;
	   case fromsplit : // Adjust the old branch first
			    {
			    bin.SetBound(returnfromchild.bound[0]);
				 needwrite = TRUE;
			    }
	   case newbranch : // Try to insert the new branches into the node
			    {
			    int curbranch = 0;
			    for (; (curbranch < returnfromchild.newcount) && (n->Put(returnfromchild.branch[curbranch],ip.page_size)); curbranch++)
				 ;
			    if (returnfromchild.newcount - curbranch) 
                              {
				// There are branch to be inserted, put it in the stack and insert later
				for (; (curbranch < returnfromchild.newcount); curbranch++)
				   reinsertd.Add(returnfromchild.branch[curbranch], n->GetLevel());
			        stats.IncrementStat(REINSERTCOUNT);
                              }
			    else
			      {
				 // All extra branches are reinserted, pass the new bound info up
				 if (returnfromchild.irt == fromsplit)
				    insertreturn.Nbound(returnfromchild.bound, returnfromchild.newcount + 1); // the bounding region for the (original) node need to be stored too
				 else
				    insertreturn.Nbound(returnfromchild.branch, returnfromchild.newcount);
			      }
				 needwrite = TRUE;
			     }
			     break;
	    default  :  
			 break;
             }


          // Try to put back the selected branch, to see if splitting necessary
          if (n->Put(bin, ip.page_size) == NODE_FULL)
             {
                 // splitting necessary
                 SplitReturn splitre = n->Split(bin, thishandle, ip.page_size, ip.min_fill_percent, ip.unfold_dim);
                 insertreturn.FromSplit(splitre);
		 for (int i = 0; i < splitre.parts; i++)
                      stats.IncrementStat(WRITECOUNT);
                 stats.IncrementStat(SPLITNODECOUNT);
             }
	  else
	     {
		if (needwrite)
		   thishandle.write();

	     }
     }
  else
     {
        // Leaf node
        // update stat
        stats.IncrementStat(LEAFREADCOUNT);

        if (n->Put(e1, ip.page_size) == NODE_FULL)
           {
	      // Leaf TVNode full

              // check for reinsert
              if (reinsertd.NonEmpty(0))
                 {
                      // Reinsert have been done during this insertion, split
                      SplitReturn splitre = n->Split(e1, thishandle, gfeat, ip.page_size, ip.min_fill_percent, ip.unfold_dim);
                      insertreturn.FromSplit(splitre);
		      for (int i = 0; i < splitre.parts; i++)