tvrectangle.c

TV-tree的c实现源码

     {
        if (GetNonSigDim() >= v.GetDim())
           {
	     // TVector shorter than nonsig portion
	     return NewRect(nonsig, v, result_sig_dim);
           }
	else
	   {
	     if (!(GetNonSigDim()))
		{
	           // No nonsig portion
                   NewSigRect(result.lower, result.upper, lower, upper, v, result_sig_dim); 
		}
	     else
		{
		  int min_nonequal = nonsig.FirstDiffDim(v);
	     	  if (min_nonequal == -1)
		     {
		       // TVector have same value at all nonsig portions
		       result.nonsig = nonsig;
                       NewSigRect(result.lower, result.upper, lower, upper, v.ProjectBack(v.GetDim() - GetNonSigDim()), result_sig_dim); 
		     }
		  else
		     {
		       result.nonsig = nonsig.ProjectFront(min_nonequal);
		       int mindim = min(v.GetDim(), GetCenterDim());

		       // calculate the real non sig portion	
		       if (!result_sig_dim)
			  result_sig_dim = mindim - min_nonequal;
		       else
			  if (min_nonequal + result_sig_dim > mindim)
			     result_sig_dim = mindim - min_nonequal;
			  

		       if (min_nonequal + result_sig_dim <= GetNonSigDim())
			  {
		             TVector v1 = nonsig.ProjectMid(min_nonequal, result_sig_dim);
		             TVector v2 = v.ProjectMid(min_nonequal, result_sig_dim);
			     result.lower = v1.MinCompo(v2);
			     result.upper = v1.MaxCompo(v2);
			  } 
		       else
			  {
		             TVector onon = nonsig.ProjectBack(GetNonSigDim() - min_nonequal);
		             TVector v1 = v.ProjectMid(min_nonequal, onon.GetDim());
			          
		             TVector ol = lower.ProjectFront(result_sig_dim - onon.GetDim());
		             TVector ou = upper.ProjectFront(result_sig_dim - onon.GetDim());
		             TVector v2 = v.ProjectMid(GetNonSigDim(),  result_sig_dim - onon.GetDim());
	
			     TVector nl, nu;
			 
                             NewSigRect(nl, nu, ol, ou, v2);

			     result.lower = onon.MinCompo(v1) << nl;
			     result.upper = onon.MaxCompo(v1) << nu;

			  }

		     }
		}
	   }
       return result;
     }
  else
    {
     return *this;
    }
}



TVRectangle TVRectangle::Combine(const TVRectangle& d, int result_sig_dim)
{
  const TVRectangle *dshort, *dlong;
  TVRectangle result;

       //    Algorithm
       //
       //	    dlong : |----------------------------------------|-----------------|
	//		          non-sig   |           |            |    sig
	//			    	    |           |            |
	//			            |           |            |
	//	   dshort : |---------------|-----------|---------------------|
	//		        non-sig                    sig
	//		         (1)             (1a)          (2)         (3)
        //		       <equal>	     <unequal>

  if (GetNonSigDim() > d.GetNonSigDim())
     {
        dshort = &d;
	dlong = this;
     }
  else 
     {
        dshort = this;
	dlong = &d;
     }

  int nonsigshort = dshort->GetNonSigDim();

  int nonsig_firstdiff = nonsig.FirstDiffDim(d.nonsig); 

  int cursigdim = 0;
  int dim1a = 0, dim2 = 0, dim3 = 0;

  // Case (1)
  if (nonsig_firstdiff == -1)
     {
	// Equal nonsigdim
	result.nonsig = dshort->nonsig; 
     }
  else
     {
       if (nonsig_firstdiff)
           result.nonsig = dshort->nonsig.ProjectFront(nonsig_firstdiff); 
     }


  // Case (1a)

  if (nonsig_firstdiff >= 0)
     {
	dim1a = nonsigshort - nonsig_firstdiff; 
	if ((result_sig_dim > 0) && (dim1a > result_sig_dim))
	    dim1a = result_sig_dim;

	result.lower = dshort->nonsig.ProjectMid(nonsig_firstdiff, dim1a).MinCompo(dlong->nonsig.ProjectMid(nonsig_firstdiff, dim1a)); 
	result.upper = dshort->nonsig.ProjectMid(nonsig_firstdiff, dim1a).MaxCompo(dlong->nonsig.ProjectMid(nonsig_firstdiff, dim1a)); 
	cursigdim = dim1a;
     }

  int nonsigdiff = dlong->GetNonSigDim() - nonsigshort;
  // case (2)

  if ( (!result_sig_dim) || (cursigdim < result_sig_dim))
     {
	 if (nonsigdiff)
	    {
		dim2 = nonsigdiff;
	        if ((result_sig_dim > 0) && (dim2 + cursigdim > result_sig_dim))
	            dim2 = result_sig_dim - cursigdim;
		result.lower <<= dlong->nonsig.ProjectMid(nonsigshort, dim2).MinCompo(dshort->lower.ProjectFront(dim2));
		result.upper <<= dlong->nonsig.ProjectMid(nonsigshort, dim2).MaxCompo(dshort->upper.ProjectFront(dim2));
		cursigdim += dim2;
	    }
     }

  // case (3)

  if ( (!result_sig_dim) || (cursigdim < result_sig_dim))
     {
	dim3 = dshort->GetCenterDim() - dlong->GetNonSigDim();
	if (dim3)
	   {
	      dim3 = min(dim3, dlong->GetSigDim());	
	      if ((result_sig_dim > 0) && (dim3 + cursigdim > result_sig_dim))
	            dim3 = result_sig_dim - cursigdim;

		
	      result.lower <<= dlong->lower.ProjectFront(dim3).MinCompo(dshort->lower.ProjectMid(nonsigdiff, dim3));
	      result.upper <<= dlong->upper.ProjectFront(dim3).MaxCompo(dshort->upper.ProjectMid(nonsigdiff, dim3));

	   }
     }


  return result;
}




TVRectangle operator<<(const TVector& v , const TVRectangle& d)
{
   TVRectangle res(v << d.nonsig, d.lower, d.upper);

   return res;
}



int sort_nonsig(const void *d1, const void *d2)
{
  TVRectangle *r1 = (TVRectangle *)d1;
  TVRectangle *r2 = (TVRectangle *)d2;
  
  int n1 = r1->GetNonSigDim();
  int n2 = r2->GetNonSigDim();

  return(n1 - n2);
}


TVRectangle MinBoundTVRectangle(TVRectangle *darray, int count, int res_sig_dim)
{

/*
cout << "Enter minboundrect(rect)\n";
for (int xyy = 0; xyy < count; xyy++)
    cout << xyy << " : " << darray[xyy] << endl;
*/

  assert(count > 0);
  TVRectangle result;
   
  if (count == 1)
     return darray[0];
  
  TVRectangle *darray1 = new TVRectangle[count];
  int i;
  for (i = 0; i < count ; i++)
      darray1[i] = darray[i];
  qsort(darray1, count, sizeof(TVRectangle), sort_nonsig);

  int min_nonsigdim = darray1[0].GetNonSigDim();
  int min_nonequal = -1;
  int min_dim = darray1[0].GetCenterDim();

  for (i = 1; i < count; i++)
    {
       int new_minnonequal = darray1[i-1].GetNonSigCenter().FirstDiffDim(darray1[i].GetNonSigCenter());
       if (min_nonequal == -1)
	  min_nonequal = new_minnonequal;
       else
	  if (new_minnonequal != -1)
	     min_nonequal = min(min_nonequal, new_minnonequal);
       min_dim = min(min_dim, darray1[i].GetCenterDim());

    }

  // Calculate nonsig

  if ((min_nonequal == -1) || (min_nonequal >= min_nonsigdim))
     {
        result.PutNonSig(darray1[0].GetNonSigCenter());
     }
  else
     {
	if (min_nonequal)
	   result.PutNonSig(darray1[0].GetNonSigCenter().ProjectFront(min_nonequal));
     }

  int res_nonsigdim = result.GetNonSigDim();

  // Calculate min dim
  if ((!res_sig_dim) || (res_sig_dim > min_dim))
     {
	res_sig_dim = min_dim;
     }

  result.lower = darray1[0].ProjectMidLow(res_nonsigdim, res_sig_dim);
  result.upper = darray1[0].ProjectMidHigh(res_nonsigdim, res_sig_dim);

  for (i = 1; i < count; i++)
     {
       result.lower = result.lower.MinCompo(darray1[i].ProjectMidLow(res_nonsigdim, res_sig_dim));
       result.upper = result.upper.MaxCompo(darray1[i].ProjectMidHigh(res_nonsigdim, res_sig_dim));
     }
  
  delete [] darray1;
// cout << "Result : " << result << endl;
  return result;
}


TVRectangle MinBoundTVRectangle(TVector *varray, int count, int res_sig_dim)
{
  assert(count > 0);
  TVRectangle result;
   
  if (count == 1)
     {
	result.PutNonSig(varray[0]);
        return result;
     }
  
  int min_nonequal = -1;
  int min_dim = varray[0].GetDim();
  for (int i = 1; i < count; i++)
    {
       int new_minnonequal =  varray[i-1].FirstDiffDim(varray[i]);
       if (min_nonequal == -1) 
	  min_nonequal = new_minnonequal;
       else
	  if (new_minnonequal != -1)
	     min_nonequal = min(min_nonequal, new_minnonequal);
       min_dim = min(min_dim, varray[i].GetDim());

    }
  if (min_nonequal == -1)  
     {
	// all vectors agress in the dimensions
	// create a 0 radius rectangle with specified sig_dim
	result.PutNonSig(varray[0].ProjectFront(min_dim));
     }
  else
    if (min_nonequal >= min_dim)
     {
	result.PutNonSig(varray[0].ProjectFront(min_dim));
     }
    else 
     {
	result.PutNonSig(varray[0].ProjectFront(min_nonequal));

	// determine non-sig-dim & sig-dim; 
	int sigdim;
        if (res_sig_dim)
	   sigdim = min(min_dim - min_nonequal, res_sig_dim);   // can consider just unfold to min_dim
	else
 	   sigdim = min_dim - min_nonequal;
	// MinBoundTVRectangle2 for vectors

        result.lower = varray[0].ProjectMid(min_nonequal, sigdim);
        result.upper = varray[0].ProjectMid(min_nonequal, sigdim);
        for (int i = 1; i < count; i++)
          {
               result.lower = result.lower.MinCompo(varray[i].ProjectMid(min_nonequal, sigdim));
               result.upper = result.upper.MaxCompo(varray[i].ProjectMid(min_nonequal, sigdim));
          }
     }

  return result;
}

TVRectangle NewRect(const TVector& v1, const TVector& v2, int maxsigdim)
{
   TVRectangle res;
   int mindim = min(v1.GetDim(), v2.GetDim());
   int firstdiff = v1.FirstDiffDim(v2);

   if (firstdiff > -1)   
      {
	 // sig dim exists
	if (firstdiff > 0)
	   res.PutNonSig(v1.ProjectFront(firstdiff));
	if ((!maxsigdim) || ((mindim - firstdiff) < maxsigdim))
	   maxsigdim = mindim - firstdiff;
  	TVector v1a = v1.ProjectMid(firstdiff, maxsigdim); 	
  	TVector v2a = v1.ProjectMid(firstdiff, maxsigdim); 	
	
        res.PutSig(v1a.MinCompo(v2a), v1a.MaxCompo(v2a));
      } 
   else
      res.PutNonSig(v1.ProjectFront(mindim));
   
   return res;
}


double TVRectangle::MinDist(const TVector& v) const
{
  assert(v.GetDim() >= GetCenterDim());

  double result = 0.0;

  if (nonsig.GetDim())
     result += nonsig.Distance(v.ProjectFront(nonsig.GetDim()));

  for (int i = 0; i < lower.GetDim(); i++)
      {
        VCOM_TYPE compo = v[nonsig.GetDim() + i];
        if (compo < lower[i])
	   result += (lower[i] - compo);
        else
           if (compo > upper[i])
	    result += (compo - upper[i]);
      }

  return result; 
}




//  befriended functions

ostream& operator<< (ostream& os, const TVRectangle& d)
{
   os << " NonSig : " <<  d.nonsig << "  SigLower : " << d.lower << "  Sig Upper : " << d.upper;
   return os;
}

ostream& operator<< (ostream& os, const TVRectangle*& d)
{
   os << " NonSig : " <<  d->nonsig << "  SigLower : " << d->lower << "  Sig Upper : " << d->upper;
   return os;
}

ofstream& operator< (ofstream& os, const TVRectangle& d)
{
   os < d.nonsig;
   os << " ";
   os < d.lower;
   os << " ";
   os < d.upper; 
   os << " ";
   return os;
}

ofstream& operator< (ofstream& os, const TVRectangle*& d)
{
   os < d->nonsig;
   os << " ";
   os < d->lower;
   os << " ";
   os < d->upper; 
   os << " ";
   return os;
}

istream& operator>> (istream& is, TVRectangle& d)
{
   cout << "Input NonSig : ";
   is >> d.nonsig;
   cout << "Input SigLower : ";
   is >> d.lower;
   cout << "Input SigUpper : ";
   is >> d.upper;
   return is;
}

istream& operator>> (istream& is, TVRectangle*& d)
{
   cout << "Input NonSig : ";
   is >> d->nonsig;
   cout << "Input SigLower : ";
   is >> d->lower;
   cout << "Input SigUpper : ";
   is >> d->upper;
   return is;
}


ifstream& operator> (ifstream& ifs, TVRectangle& d)
{
   ifs > d.nonsig;
   ifs > d.lower;
   ifs > d.upper;
   return ifs;
}

ifstream& operator> (ifstream& ifs, TVRectangle*& d)
{
   ifs > d->nonsig;
   ifs > d->lower;
   ifs > d->upper;
   return ifs;
}