tvsplit2.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: split2.C,v 1.3 1996/04/18 21:50:24 kilin Exp kilin $ 
// Please change sig_dim to active_dim

#include <iostream.h>
#include <assert.h>
#include <stdlib.h>
#include <fstream.h>
#include "TVdefine.h"
#include "TVconstants.h"
#include "TVvector.h"
#include "TVrectangle.h"
//#include "TVrectangle.h"
#include "TVelement.h"
#include "TVsimbuf.h"
#include "TVnode.h"
#include "TVutil.h"

int SortDim;

// Pick the best division
// return the cutpoint [0..cutpoint], [cutpoint + 1.. entrycount - 1]
// return -1 if no valid one found

int makePick(TVRectangle *lower_rectangle, TVRectangle *upper_rectangle, int *lower_size, int *upper_size, int node_fix_size, int entrycount, int min_fill, int min_size, int pagesize, int alwaysvalid = FALSE)
{
   float min_radius = 0.0, max_diff;
   int max_dim, short_dim, min_index = -1;
   TVRectangle *shortd, *longd;
   int valid = FALSE;
   int curcutpoint = min_fill - 1;

   // find the first valid one

   for (; (curcutpoint < entrycount - min_fill) && (!valid); curcutpoint++)
     {
       valid = ((lower_size[curcutpoint] + node_fix_size) <= pagesize) &&
               ((lower_size[curcutpoint] + node_fix_size) >= min_size) &&
               ((upper_size[curcutpoint + 1] + node_fix_size) <= pagesize) &&
               ((upper_size[curcutpoint + 1] + node_fix_size) >= min_size) ;

       if (valid || alwaysvalid)
	  {
	     min_radius = lower_rectangle[curcutpoint].GetRadius() + upper_rectangle[curcutpoint + 1].GetRadius();
	     max_dim = lower_rectangle[curcutpoint].GetCenterDim() + upper_rectangle[curcutpoint + 1].GetCenterDim();
	     if (lower_rectangle[curcutpoint].GetCenterDim() < upper_rectangle[curcutpoint + 1].GetCenterDim())
		{
		    shortd = &(lower_rectangle[curcutpoint]);
		    longd = &(upper_rectangle[curcutpoint + 1]);
		}
	     else
		{
		    longd = &(lower_rectangle[curcutpoint]);
		    shortd = &(upper_rectangle[curcutpoint + 1]);
		}
	    short_dim = shortd->GetCenterDim();
	    max_diff = shortd->GetCenter().Distance(longd->GetCenter().ProjectFront(short_dim));
	    min_index = min_fill -  1;
	  }
     }

   // Find the optimal one
   for (; curcutpoint < entrycount - min_fill; curcutpoint++)
     {
        valid = ((lower_size[curcutpoint] + node_fix_size) <= pagesize) &&
                ((lower_size[curcutpoint] + node_fix_size) >= min_size) &&
                ((upper_size[curcutpoint + 1] + node_fix_size) <= pagesize) &&
                ((upper_size[curcutpoint + 1] + node_fix_size) >= min_size); 

        if (valid || alwaysvalid)
	   {
	       float condf1, condf2;
	       int cond1;
               float radius, diff;
	       int dim;

	       if (lower_rectangle[curcutpoint].GetCenterDim() < upper_rectangle[curcutpoint + 1].GetCenterDim())
	          {
		      shortd = &(lower_rectangle[curcutpoint]);
		      longd = &(upper_rectangle[curcutpoint + 1]);
	          }
	       else
	          {
		      longd = &(lower_rectangle[curcutpoint]);
		      shortd = &(upper_rectangle[curcutpoint + 1]);
	         }

	       short_dim = shortd->GetCenterDim();
	       condf1 = (radius = lower_rectangle[curcutpoint].GetRadius() + upper_rectangle[curcutpoint + 1].GetRadius()) - min_radius;

	       condf2  = (diff = shortd->GetCenter().Distance(longd->GetCenter().ProjectFront(short_dim))) - max_diff;
	       cond1 = (dim = lower_rectangle[curcutpoint].GetCenterDim() + upper_rectangle[curcutpoint + 1].GetCenterDim()) - max_dim;
               if ( (cond1 > 0) ||
                     (  (cond1 == 0) &&
                        ( (condf1 < 0) || (condf1 < 1e-8 ) && (condf2 > 0)) ) )
	          {
		     min_radius = radius;
		     max_diff = diff;
		     max_dim = dim;	
		     min_index = curcutpoint;
		  }
	   }
     }

  return min_index;
}


// Code for splitting leaves

// comparsion routines for qsort

int sort_lexical(const void *n1, const void *n2)
{
   int out1;
   TVector v1, v2;
   v1 =  ((Leaf_Element *)n1)->GetTVector();
   v2 =  ((Leaf_Element *)n2)->GetTVector();
   if (v1[SortDim] < v2[SortDim])
      out1 = -1 ;
   else
      { 
        if (v1[SortDim] > v2[SortDim])
	   out1 = 1;
	else
	   {
              if (v1 < v2)
		 out1 = -1;
	      else
		 out1 = (v1 > v2);
	   }
      }
   return out1;
}

int sort_size(const void *n1, const void *n2)
{
   return ((Leaf_Element *)n1)->Size() -  ((Leaf_Element *)n2)->Size();
}

// Calculate the number of bytes needed to store the elements of larray[first..last]
// with a maximum vector of dimension d stored
// (d = 0 --> store leaf element as it is now)
int calSizeNeeded(Leaf_Element *larray, int first, int last, int dim = 0)
{
   int result = 0;

   if (dim)
     for (int i = first; i <= last; i++)
        result += larray[i].ExpectedSize(dim);
   else
     for (int i = first; i <= last; i++)
        result += larray[i].Size();
	
   return result;
} 

// Examine the leaf array[first..last]  so that the vectors with 
// dimensions less than  (minimum + sig_dim)
// will have at "dimtoadd" dimensions added
// Update the corresponding varray also
// Update the new minimum dimensions of the vectors expanded 

void expandElement(Leaf_Element *larray, TVector *varray, int first, int last, int sig_dim, int& curmindim, VCOM_TYPE (*gfeat)(int, char*))
{
   int newmindim = larray[first].GetTVector().GetDim();

   for (int i = first; i <= last; i++)
     {
	 if (larray[i].GetTVector().GetDim() < curmindim + sig_dim)
	    varray[i] = larray[i].GetTVector(curmindim + sig_dim, gfeat);
	 newmindim = min(newmindim, varray[i].GetDim());
     }

}

// Shortern dimensions of vectors carried by larray elements to a maximum of maxdim
void dropDim(Leaf_Element *larray, int first, int last, int maxdim)
{
  int gdim;
  for (int i = first; i <= last; i++)
     if ((gdim = larray[i].GetTVector().GetDim()) > maxdim)
	larray[i].DropDim(gdim - maxdim);
}


// Find the cut that split the leaf array into two groups 
// Return FALSE if such split cannot be found

int FindSplit(SplitReturn& sret, Leaf_Element *larray, VCOM_TYPE (*gfeat)(int, char*), int node_fix_size, int pagesize, float min_fill_percent, int sig_dim)
{
    // At least 2 entries after split
    assert(sret.entrycount >= 4);

    TVector *varray = new TVector[sret.entrycount];

    // lower_rectangle[i] :rectangle formed by combining elements[0..i];
    TVRectangle *lower_rectangle = new TVRectangle[sret.entrycount]; 

    // Number of bytes required by the elements[0..i]
    int *lower_bytes= new int[sret.entrycount];
    // Minimum dimensions among the lower vectors[0..i]
    int *lower_mindim = new int[sret.entrycount];  
    // First position where difference in value among the lower vectors[0..i]
    int *lower_firstdiff = new int[sret.entrycount];  
    // Number of bytes required by the elements[0..i]
    int *newlower_bytes= new int[sret.entrycount];


    // upper_rectangle[i] :rectangle formed by combining elements[i..sret.entrycount];
    TVRectangle *upper_rectangle = new TVRectangle[sret.entrycount]; // rectangle formed by co
    int *upper_bytes = new int[sret.entrycount];
    int *upper_mindim = new int[sret.entrycount];  
    int *upper_firstdiff = new int[sret.entrycount];  
    int *newupper_bytes = new int[sret.entrycount];

    int min_size = min_fill_percent * (pagesize * 1.0) / 100.0;
    int min_fill = min_fill_percent * (sret.entrycount * 1.0) / 100.0;
 
    int lower_size = 0, upper_size = 0;
 
    int i;

    if (min_fill < 2)
      min_fill = 2;
    if (min_fill > sret.entrycount / 2)
      min_fill = sret.entrycount / 2;

    assert(min_fill >= 2);

    varray[0] = larray[0].GetTVector();
    lower_bytes[0] = larray[0].Size();
    lower_firstdiff[0] = lower_mindim[0] = varray[0].GetDim();

    for (i = 1; i < sret.entrycount ; i++) 
	{
	  varray[i] = larray[i].GetTVector(); // just retrieve the currently expanded
          lower_bytes[i] =  lower_bytes[i - 1] + larray[i].Size();
	  lower_mindim[i] = min(lower_mindim[i - 1], varray[i].GetDim());
	  lower_firstdiff[i] = min(lower_firstdiff[i - 1], 
                                   (varray[i - 1].FirstDiffDim(varray[i]) == -1 ? min(varray[i].GetDim(), varray[i - 1].GetDim()) : varray[i - 1].FirstDiffDim(varray[i])));
	}

    upper_bytes[sret.entrycount - 1] = larray[sret.entrycount - 1].Size();
    upper_firstdiff[sret.entrycount - 1] = upper_mindim[sret.entrycount - 1] = varray[sret.entrycount - 1].GetDim();
    for (i = sret.entrycount - 2; i >=0 ; i--)
	{
          upper_bytes[i] =  upper_bytes[i + 1] + larray[i].Size();
	  upper_mindim[i] = min(upper_mindim[i + 1], varray[i].GetDim());
	  upper_firstdiff[i] = min(upper_firstdiff[i + 1], 
                                   (varray[i + 1].FirstDiffDim(varray[i]) == -1 ? min(varray[i].GetDim(), varray[i + 1].GetDim()) : varray[i + 1].FirstDiffDim(varray[i])));
        }

  
    // Find the lower minimum bounding rectangles
    // lower_rectangle[curcutpoint] : Group vectors [0..curcutpoint]


   int curcutpoint;
   for (curcutpoint = min_fill - 1 ; curcutpoint < sret.entrycount -  min_fill; curcutpoint++)