polynomialt.cc.txt

压缩文件中是Error Correction Coding - Mathematical Methods and Algorithms(Wiley 2005)作者:(Todd K. Moon )的配

   if(nshift == 0) {			// no shift
	  return *this;
   }
   else if(nshift < 0) {		// shifting the other way
	  return (*this) >> -nshift;
   }
   else {
	  out = polytemp<T>::gettemppoly(degree+nshift);
	  for(i=degree; i>=0; i--) {
		 out->coeff[i+nshift] = coeff[i];
	  }
	  for(i = 0; i < nshift; i++) {
		 out->coeff[i] = z;
	  }
   }
   return *out;
} // overloaded <<

// multiply by x -- increase the degree (non-cyclic shift)
template <class T> const polynomialT<T>& 
polynomialT<T>:: operator<<=(const int nshift) 
{
   int i;
   T save;
   T z(0);						// build a zero
   T *newcoeff;
   if(nshift == 0) {			// no shift
	  polytemp<T>::resettemplist();
	  return *this;
   }
   else if(nshift < 0) {		// shifting the other way
	  int degleft = degree - nshift;
	  if(degleft < 0) {			// nothing left
		 newcoeff = new T[1];
		 newcoeff[0] = z;
		 delete[] coeff;
		 coeff = newcoeff;
		 degree = 0;
	  }
	  else {					// stuff left
		 newcoeff = new T[degleft+1];
		 for(i = 0; i <= degleft; i++) {
			newcoeff[i] = coeff[i+nshift];
		 }
		 delete [] coeff;
		 coeff = newcoeff;
		 degree = degleft;
	  }
   }
   else {
	  newcoeff = new T[degree+nshift+1];
	  for(i=degree; i>=0; i--) {
		 newcoeff[i+nshift] = coeff[i];
	  }
	  for(i = 0; i < nshift; i++) {
		 newcoeff[i] = z;
	  }
	  degree = degree+nshift;
	  delete [] coeff;
	  coeff = newcoeff;
   }
   polytemp<T>::resettemplist();
   return *this;
} // overloaded <<

// divide by x -- decrease the degree (non-cyclic shift)
template <class T> const polynomialT<T>& 
polynomialT<T>:: operator>>=(const int nshift) 
{
   int i;
   T save;
   T z(0);						// build a zero
   T *newcoeff;
   if(nshift == 0) {			// no shift
	  polytemp<T>::resettemplist();
	  return *this;
   }
   else if(nshift < 0) {		// shifting the other way (increae the degree)
	  newcoeff = new T[degree+nshift+1];
	  for(i=degree; i>=0; i--) {
		 newcoeff[i+nshift] = coeff[i];
	  }
	  for(i = 0; i < nshift; i++) {
		 newcoeff[i] = z;
	  }
	  degree = degree+nshift;
	  delete [] coeff;
	  coeff = newcoeff;
   }
   else {
	  int degleft = degree - nshift;
	  if(degleft < 0) {			// nothing left
		 newcoeff = new T[1];
		 newcoeff[0] = z;
		 delete[] coeff;
		 coeff = newcoeff;
		 degree = 0;
	  }
	  else {					// stuff left
		 newcoeff = new T[degleft+1];
		 for(i = 0; i <= degleft; i++) {
			newcoeff[i] = coeff[i+nshift];
		 }
		 delete [] coeff;
		 coeff = newcoeff;
		 degree = degleft;
	  }
   }
   polytemp<T>::resettemplist();
   return *this;
} // overloaded <<


// indexing []
template <class T> T&
polynomialT<T>:: operator[](const int idx) const // const function
{
   assert(idx >= 0 && idx <= degree);
   return coeff[idx];
} // overloaded []


// evaluate the polynomial at the point 'x' (same as function evaluate)
template <class T> T
polynomialT<T>:: operator()(const T &x) const 
{
   T polyval = T(0);
   int i = degree;
   
   for(; i>=0; i--)
	  polyval = polyval*x + coeff[i];
   
   return polyval;
} // overloaded ()

// evaluate the polynomial at the point 'x'
template <class T> T
polynomialT<T>:: evaluate(const T &x) const 
{
   T polyval = T(0);
   int i = degree;
   
   for(; i>=0; i--)
	  polyval = polyval*x + coeff[i];
   
   return polyval;
} // evaluate

// compare (test if equal)
template <class T> int 
polynomialT<T>:: operator==(const polynomialT<T> &r) const
{
   int i = degree;
   
   if(degree != r.degree) return 0;
   
   for(; i>=0; i--)
	  if(coeff[i] != r.coeff[i]) return 0;
   
   return 1;
} // overloaded ==


// compare (test if not equal)
template <class T> int
polynomialT<T>:: operator!=(const polynomialT<T> &r) const 
{
	int i = degree;
	
	if(degree != r.degree) return 1;
	
	for(; i>=0; i--)
	   if(coeff[i] != r.coeff[i]) return 1;
	
	return 0;
} // overloaded !=


// test for equality to constant
template <class T> int 
polynomialT<T>:: operator==(const T &r) const 
{
   T z(0);						// build a zero
   // if any higher terms are nonzero, cannot be equal
   for(int i = 1; i <= degree; i++) {
	  if(coeff[i] != z) return 0;
   }
   if(coeff[0] != r) return 0;
   return 1;
} // overloaded ==


// test for inequality to constant
template <class T> int 
polynomialT<T>:: operator!=(const T &r) const 
{
   T z(0);						// build a zero

   // if any higher terms are nonzero, then it is not equal
   for(int i = 1; i <= degree; i++) {
	  if(coeff[i] != z) return 1;
   }
   if(coeff[0] == r) return 0;
   return 1;
} // overloaded ==



template <class T> ostream&
polynomialT<T>:: printvarname(ostream &os) const 
{
   char *vn;
   if(varname) {
	  vn = varname;
   }
   else {
	  vn = polynomialT<T>::defvarname;
   }
   os << vn;
   return os;
}

template <class T> ostream&
polynomialT<T>:: printcoeff(ostream &os, const T &coeff) const 
{
   char *vn;
   if(varname) {
	  vn = varname;
   }
   else {
	  vn = polynomialT<T>::defvarname;
   }
   if(!strcmp(vn,beforeafterprint[0]))
	  os << beforeafterprint[1];
   os << coeff;
   if(!strcmp(vn,beforeafterprint[0]))
	  os << beforeafterprint[2];
   return os;
}


// print function
template <class T> ostream&
polynomialT<T>:: printpolynomialT(ostream &os) const 
{
   int i;

   if(degree==0) {
	  os << coeff[0];
	  return os;
   }

   if(polynomialT<T>::decreasingprint == 0) { // print in increasing order
	  // do first two terms to take care of the possiblity
	  // that they are the 0 and 1 degree coefficients
	  
	  // find start (first nonzero term)
	  for(i=0; coeff[i]==0 && i < degree; i++);
	  
	  if((i==0) || ((i>0) && (coeff[i]!=1))) printcoeff(os,coeff[i]);
	  
	  if(i>0) printvarname(os);
	  if(i>1) os << "^" << i;
	  
	  // is there only 1 term?
	  if(i>=degree) return os;
	  
	  // find next non-zero term
	  for(i++; coeff[i]==0 && i < degree; i++);
	  
	  os << " + ";
	  if(coeff[i]!=1) printcoeff(os,coeff[i]);
	  printvarname(os);
	  if(i>1) os << "^" << i;
	  if(i>=degree) return os;
	  
	  // output remaining polynomial
	  for(i++; i<degree; i++) {
		 if(coeff[i] == 1) {
			os << " + " ;
			printvarname(os);
			os << "^" << i;
		 }
		 else if(coeff[i] != 0) {
			os << " + ";  printcoeff(os,coeff[i]);
			printvarname(os);
			os << "^" << i;
		 }
	  }
	  // output highest degree term always (in case it is 0)
	  os << " + ";
	  if(coeff[i] != 1) {
		 printcoeff(os,coeff[i]);
		 printvarname(os);
		 os << "^" << degree;
	  }
	  else {
		 printvarname(os);
		 os << "^" << degree;
	  }
   }
   else { // print in decreasing order
	  // always print the first term (in case it is 0)
	  if(coeff[degree] != 1) printcoeff(os,coeff[degree]);
	  printvarname(os);
	  if(degree > 1) os << "^" << degree;
	  
	  // find next
	  for(i = degree-1; i >= 0; i--) {
		 if(coeff[i] != 0) {
			os << " + ";
			if(coeff[i] != 1 || i==0) printcoeff(os,coeff[i]);
			if(i > 0) {
			   printvarname(os);
			}
			if(i > 1) os << "^" << i;
		 }
	  }
   }
   return os;
}

template <class T> void 
polynomialT<T>::setprintdir(const int dir)
{ decreasingprint=dir;
}


template <class T> void
polynomialT<T>::setdefvarname(const char *newvarname)
{ if(strlen(newvarname) < 5)
	 strcpy(polynomialT<T>::defvarname,newvarname);
}

template <class T> void
polynomialT<T>::setbeforeafterprint(const char *name,const char *before,
									const char *after)
{
   if(strlen(name) < 6) 
	 strcpy(polynomialT<T>::beforeafterprint[0],name);
   if(strlen(before) < 6)
	 strcpy(polynomialT<T>::beforeafterprint[1],before);
   if(strlen(after) < 6)
	 strcpy(polynomialT<T>::beforeafterprint[2],after);
}


template <class T> void
polynomialT<T>::setvarname(const char *newvarname)
{ 
   if(varname) {
	  delete[] varname;
   }
   varname = new char[strlen(newvarname)+1];
   strcpy(varname,newvarname);
}

// polytemp class functions

// Initialize the protected static variables
template <class T> polytemp<T>*
polytemp<T>:: start_temp = NULL;

template <class T> polytemp<T>*
polytemp<T>:: current_temp = NULL;

template <class T> polytemp<T>*
polytemp<T>:: next_temp = NULL;

template <class T> int 
polytemp<T>:: numpolytemp = 0;

template <class T> int 
polytemp<T>:: maxpolytemp = 0;

// Initialize variables for quotient and remainder
template <class T> polytemp<T>* polytemp<T>:: tempquotient = NULL;
template <class T> polytemp<T>* polytemp<T>:: temprem = NULL;

// polytemp class protected member functions

// resize coeff array and set new maxsize
template <class T> void 
polytemp<T>:: tempresize(const int newdegree) {
   degree = newdegree;
   maxdegree = newdegree;
   delete [] coeff;
   coeff = new T[newdegree+1];
}


// polytemp class public static functions

// return pointer to an unused polytemp with a specific size
template <class T> polytemp<T>*
polytemp<T>:: gettemppoly(const int degree) 
{
   polytemp<T>* temp;

   // We need to do one of four things:
   // 1) Return pointer to next available polytemp. 
   // 2) Resize next available polytemp, then return it.
   // 3) Create a new poly temp and add it on to the list.
   // 4) Create the first node in the list.
   
   // This will be the order that these cases are addressed
   // because on average, the higher number cases are less
   // likely (case 4 is only addressed once).

   // case 1 and 2
   if(polytemp<T>::numpolytemp < polytemp<T>::maxpolytemp) {
	   
	  polytemp<T>::numpolytemp++;
	  
	  temp = polytemp<T>::current_temp = polytemp<T>::next_temp;
	  polytemp<T>::next_temp = temp->next;
	  
	  temp->degree = degree;
	  
	  // case 2 (case 1 if this test is false)
	  if(degree > temp->maxdegree) temp->tempresize(degree);
	  
	  return temp;
   }
   
   // case 3 and 4
   // (note: For case 3 and 4, we know that next_temp = NULL
   // coming into this function.  Since we are adding onto
   // the list at this point, next_temp is going to remain
   // NULL.)
   
   polytemp<T>::numpolytemp++;
   polytemp<T>::maxpolytemp++;
   
   temp = new polytemp<T>;
   temp->tempresize(degree);
   
   // case 3 
   // (note: maxpolytemp was just incremented, so
   // to test if it used to be > 0, test if it is > 1)
   if(polytemp<T>::maxpolytemp > 1) 
	  polytemp<T>::current_temp->next = temp;
   
   // case 4 (start list for first time)
   else
	  polytemp<T>::start_temp = temp;
   
   polytemp<T>::current_temp = temp;
   
   return temp;
}


// print information about list size, etc.
template <class T> void
polytemp<T>:: dumptemps() 
{

   polytemp<T>* temp = polytemp<T>::start_temp;
   int counttemps = 0;
   
   cout<<"Temporary information:"<<endl
	   <<"maxpolytemp="<<polytemp<T>::maxpolytemp<<endl;
   
   for( ; temp!=NULL; temp=temp->next, counttemps++)
	  cout<<"ctr="<<counttemps// <<" address: "<<temp
		  <<" maxdegree="<<temp->maxdegree<<": "
		  <<*temp<<endl;
   
   if(counttemps != polytemp<T>::maxpolytemp)
	  cout<<"Warning: queue length does not match number allocated"
		  <<endl;
   if(polytemp<T>::tempquotient) { // have a quotient
	  cout << "Temp quotient: " << *polytemp<T>::tempquotient << endl;
   }
   if(polytemp<T>::temprem) { // have a quotient
	  cout << "Temp remainder: " << *polytemp<T>::temprem << endl;
   }
}

template <class T> polytemp<T>*
polytemp<T>:: gettempquot(int newdegree) 
{
   if(polytemp<T>::tempquotient == NULL) {
	  polytemp<T>::tempquotient = new polytemp<T>;
   }
   if(newdegree > polytemp<T>::tempquotient->maxdegree)
	  polytemp<T>::tempquotient->tempresize(newdegree);
   polytemp<T>::tempquotient->degree = newdegree;
   return polytemp<T>::tempquotient;
}

template <class T> polytemp<T>*
polytemp<T>:: gettemprem(int newdegree) 
{
   if(polytemp<T>::temprem == NULL) {
	  polytemp<T>::temprem = new polytemp<T>;
   }
   if(newdegree > polytemp<T>::temprem->maxdegree)
	  polytemp<T>::temprem->tempresize(newdegree);
   polytemp<T>::temprem->degree = newdegree;
   return polytemp<T>::temprem;
}


// assignment
template <class T> const polytemp<T>&
polytemp<T>:: operator=(const polytemp<T> &r) 
{
   if(this != &r) {
	  degree = r.degree;
	  for(int i = r.degree; i>=0; i--)
		 coeff[i] = r.coeff[i];
   }
   // polytemp<T>::resettemplist(); // don't do this: other's might grab this
   return *this;
} // overloaded =

template <class T> const polytemp<T>&
polytemp<T>:: operator=(const polynomialT<T> &r) 
{
   if(this != &r) {
	  degree = r.getdegree();
	  for(int i = r.getdegree(); i>=0; i--)
		 coeff[i] = r[i];
   }
   // polytemp<T>::resettemplist(); // don't do this: other's might grab this
   return *this;
} // overloaded =


/*
Local Variables:
compile-command: "g++ -c -g polynomialT.cc"
End:
*/