tvsplit2.c

TV-tree的c实现源码

	{
	    lower_rectangle[curcutpoint] = MinBoundTVRectangle(varray, curcutpoint + 1, sig_dim);
	
            int canexpand = TRUE;
	
            while (((lower_rectangle[curcutpoint].GetRadius() < PRECISION) || (lower_rectangle[curcutpoint].GetSigDim() < sig_dim)) && canexpand)
		{
		   // zero radius, get new dimension
		   int tempmin = lower_mindim[curcutpoint];
                   expandElement(larray, varray, 0, curcutpoint,  sig_dim, lower_mindim[curcutpoint], gfeat);
	           lower_rectangle[curcutpoint] = MinBoundTVRectangle(varray, curcutpoint + 1, sig_dim);
		   canexpand = (tempmin != lower_mindim[curcutpoint]);
		}

	    newlower_bytes[curcutpoint] = calSizeNeeded(larray, 0, curcutpoint, lower_rectangle[curcutpoint].GetCenterDim());
	}

    // Find the upper minimum bounding rectangles
    // upper_rectangle[curcutpoint] : Group vectors [curcutpoint..sret.entrycount - 1]


   for (curcutpoint = sret.entrycount - min_fill ; curcutpoint >= min_fill; curcutpoint--)
	{
	    upper_rectangle[curcutpoint] = MinBoundTVRectangle(&(varray[curcutpoint]), sret.entrycount - curcutpoint, sig_dim);
	
            int canexpand = TRUE;
	
            while (((upper_rectangle[curcutpoint].GetRadius() < PRECISION) || (upper_rectangle[curcutpoint].GetSigDim() < sig_dim)) && canexpand)
		{
		   // zero radius, get new dimension
		   int tempmin = upper_mindim[curcutpoint];
                   expandElement(larray, varray, curcutpoint, sret.entrycount - 1,  sig_dim, upper_mindim[curcutpoint], gfeat);
	           upper_rectangle[curcutpoint] = MinBoundTVRectangle(&(varray[curcutpoint]), sret.entrycount - curcutpoint, sig_dim);
		   canexpand = (tempmin != upper_mindim[curcutpoint]);
		}

	    newupper_bytes[curcutpoint] = calSizeNeeded(larray, curcutpoint, sret.entrycount - 1, upper_rectangle[curcutpoint].GetCenterDim());
	}

    // Check for validity (grouping can actually be put into pages)
    // And for valid ones, check for maximum

   int minindex = makePick(lower_rectangle, upper_rectangle, newlower_bytes, newupper_bytes, node_fix_size, sret.entrycount, min_fill, min_size, pagesize);

   // This is needed,because contracting back may cause both node to be of less than
   // minimum size
   if (minindex == -1)
      minindex = makePick(lower_rectangle, upper_rectangle, lower_bytes, upper_bytes, node_fix_size, sret.entrycount, min_fill, min_size, pagesize);

   // Worst case, disregard byte requirement
   if (minindex == -1)
      minindex = makePick(lower_rectangle, upper_rectangle, lower_bytes, upper_bytes, node_fix_size, sret.entrycount, min_fill, min_size, pagesize, TRUE);

   if (minindex)
      {
         dropDim(larray, 0, minindex, lower_rectangle[minindex].GetCenterDim());
         dropDim(larray, minindex + 1, sret.entrycount - 1, upper_rectangle[minindex + 1].GetCenterDim());
         
         for (i = 0; i <= minindex; i++)
	   sret.distribute[i] = 0;
         for (; i < sret.entrycount; i++)
	   sret.distribute[i] = 1;
	 sret.parts = 2;
         sret.bound = new TVRectangle[2];
	 sret.bound[0] = lower_rectangle[minindex];
	 sret.bound[1] = upper_rectangle[minindex + 1];
      }
    delete [] varray;
    delete [] lower_rectangle;
    delete [] lower_bytes;
    delete [] newlower_bytes;
    delete [] lower_mindim;
    delete [] lower_firstdiff;
    delete [] upper_rectangle;
    delete [] upper_bytes;
    delete [] newupper_bytes;
    delete [] upper_mindim;
    delete [] upper_firstdiff;
   return (minindex > -1);
}



// Splitting Leaf TVNode
// The elements to be splitted is stored in the larray
// After splitting, sret will store the organization of the 2 nodes
// The elements of larray WILL BE PERMUTED.

// This is splitting by sorting

// Return FALSE if split failed to find a split

int SplitLeafAlg(SplitReturn& sret, Leaf_Element *larray, VCOM_TYPE (*gfeat)(int, char*), int node_fix_size, int pagesize, float min_fill_percent, int sig_dim)
{
   int result = TRUE;

   // Determine the dimension to sort
   TVector maxv = larray[0].GetTVector(), minv = larray[0].GetTVector();
   for (int i = 1; i < sret.entrycount; i++)
       {
	  TVector v = larray[i].GetTVector();
          maxv = maxv.MaxCompo(v);
          minv = minv.MinCompo(v);
       }

   TVector v1 = maxv - minv;
   VCOM_TYPE maxdiff = v1[0];
   int maxdiffpos = 0;
   for (int d = 1; d < v1.GetDim(); d++)
      if (maxdiff < v1[d])
         {
            maxdiff = v1[d];
	    maxdiffpos = d;
         } 
   SortDim = maxdiffpos;
   


   // sort the items lexicalgraphically
   qsort(larray, sret.entrycount, sizeof(Leaf_Element), sort_lexical);

   // Find the best cut

   if (!FindSplit(sret, larray, gfeat, node_fix_size, pagesize, min_fill_percent, sig_dim))
     {
	 // Failed to find a split, use another sort criteria
         qsort(larray, sret.entrycount, sizeof(Leaf_Element), sort_size);
         result = FindSplit(sret, larray, gfeat, node_fix_size, pagesize, min_fill_percent, sig_dim);
     }
  
  return result;
}


// Code for splitting Internal nodes


int sort_branch_lexical(const void *n1, const void *n2)
{
   int out1;
   TVector v1, v2;
   v1 =  ((TVBranch *)n1)->GetCenter();
   v2 =  ((TVBranch *)n2)->GetCenter();
   if (v1[SortDim] < v2[SortDim])
      out1 = -1 ;
   else
      {
	if (v1[SortDim] > v2[SortDim])
	   out1 = 1;
	else
	   {
	      if (v1 < v2)
		out1 = -1;
	      else
		{
		   if (v1 > v2)
		      out1 = 1;
		   else
		      {
		        float r1 = ((TVBranch *)n1)->GetRadius();
		        float r2 = ((TVBranch *)n2)->GetRadius();
		        if (r1 < r2)
			  out1 = -1;	 
		        else
			  out1 = (r1 > r2);	
		      }
		}
	   }
      }
   return out1;
}

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

    TVRectangle *darray = new TVRectangle[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];  


    // 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 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;
    int equalfirst;

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

    assert(min_fill >= 2);

    darray[0] = barray[0].GetBound(); 
    lower_bytes[0] = barray[0].Size();
    
    for (i = 1; i < sret.entrycount; i++)
	{
	   darray[i] = barray[i].GetBound(); 
	   lower_bytes[i] = lower_bytes[i - 1] + barray[i].Size();
	}

    upper_bytes[sret.entrycount - 1] = barray[sret.entrycount - 1].Size();
    for (i = sret.entrycount - 2; i >= min_fill; i--)
	   upper_bytes[i] = upper_bytes[i + 1] + barray[i].Size();

    for (i = min_fill - 1; i < sret.entrycount - min_fill; i++)
	lower_rectangle[i] = MinBoundTVRectangle(darray, i + 1, sig_dim);

    for (i = sret.entrycount - min_fill; i >= min_fill; i--)
	upper_rectangle[i] = MinBoundTVRectangle(&(darray[i]), sret.entrycount - i, sig_dim);

   int minindex = makePick(lower_rectangle, upper_rectangle, lower_bytes, upper_bytes, node_fix_size, sret.entrycount, min_fill, min_size, pagesize);

   if (minindex)
      {
         for (i = 0; i <= minindex; i++)
	   sret.distribute[i] = 0;
         for (; i < sret.entrycount; i++)
	   sret.distribute[i] = 1;
	 sret.parts = 2;
         sret.bound = new TVRectangle[2];
	 sret.bound[0] = lower_rectangle[minindex];
	 sret.bound[1] = upper_rectangle[minindex + 1];
      }

    delete [] darray;
    delete [] lower_rectangle;
    delete [] lower_bytes;
    delete [] lower_mindim;
    delete [] lower_firstdiff;
    delete [] upper_rectangle;
    delete [] upper_bytes;
    delete [] upper_mindim;
    delete [] upper_firstdiff;

   return (minindex > -1);
}

int SplitTVBranchAlg(SplitReturn& sret, TVBranch *barray, int node_fix_size, int pagesize, float min_fill_percent, int sig_dim)
{

   // Determine the dimension to sort
   TVector maxv = barray[0].GetCenter(), minv = barray[0].GetCenter();
   for (int i = 1; i < sret.entrycount; i++)
       {
	  TVector v = barray[i].GetCenter();
          maxv = maxv.MaxCompo(v);
          minv = minv.MinCompo(v);
       }

   TVector v1 = maxv - minv;
   VCOM_TYPE maxdiff = v1[0];
   int maxdiffpos = 0;
   for (int d = 1; d < v1.GetDim(); d++)
      if (maxdiff < v1[d])
         {
            maxdiff = v1[d];
	    maxdiffpos = d;
         } 
   SortDim = maxdiffpos;
   

  qsort(barray, sret.entrycount, sizeof(TVBranch), sort_branch_lexical);

  return FindSplit(sret, barray, node_fix_size, pagesize, min_fill_percent, sig_dim);

}