Lesson of 24 February 2011 (part A)

Example of use of class and template

Basic polynomial class header

File polyBasic.hh

 1/*
 2 * An example of class implementing integer polynomial
 3 */
 4 
 5#include <vector>
 6#include <iostream>
 7
 8template <typename T>
 9class polyBasic {
10
11  /*
12   * Add public types to the class polyBasic
13   */
14public:
15  typedef T              value_type ;
16  typedef std::vector<T> coeffs_type ;
17
18private:
19  coeffs_type coeffs ; // data are in the private part of the class
20  void reduce() ;
21
22public:
23  
24  // contructors
25  polyBasic() ; // make a zero polinomial
26  polyBasic( polyBasic const & ) ; // copy constructor
27  polyBasic( value_type coeffs[], int degree ) ; // make a polynomial from a C vector
28  polyBasic( coeffs_type const & coeffs ) ; // make a polynomial from a C vector
29
30  int degree() const { return coeffs.size()-1 ; }
31
32  // access to the coefficients
33  value_type const & operator [] ( int i ) const { return coeffs[i] ; }
34  value_type       & operator [] ( int i )       { return coeffs[i] ; } 
35
36  value_type get( int i ) const { return i < coeffs.size() ? coeffs[i] : 0 ; } 
37
38  // internal operator
39  polyBasic<T> const & operator  = ( polyBasic<T> const & a ) ;
40  polyBasic<T> const & operator += ( polyBasic<T> const & a ) ;
41  polyBasic<T> const & operator -= ( polyBasic<T> const & a ) ;
42  
43  // evaluation operator
44  T operator () ( T x ) const ;
45
46  void print( std::ostream & s ) const ;
47} ;
48
49// external operator
50
51template <typename T> polyBasic<T> operator + ( polyBasic<T> const & a, polyBasic<T> const & b ) ;
52template <typename T> polyBasic<T> operator - ( polyBasic<T> const & a, polyBasic<T> const & b ) ;
53
54template <typename T> 
55inline
56std::ostream & operator << ( std::ostream & s, polyBasic<T> const & a )
57{ a . print(s) ; return s ; }

Body of the templated functions and methods

File polyBasic.hxx

  1// contructors
  2template <typename T>
  3polyBasic<T>::polyBasic() {
  4  std::cout << "call polyBasic::polyBasic()\n" ;
  5  coeffs . clear() ;
  6}
  7
  8template <typename T>
  9polyBasic<T>::polyBasic( polyBasic<T> const & a ) {
 10  std::cout << "call polyBasic::polyBasic( polyBasic const & )\n" ;
 11  coeffs . resize( a . coeffs . size() ) ;
 12  std::copy( a.coeffs.begin(), a.coeffs.end(), coeffs.begin() ) ; 
 13}
 14
 15template <typename T>
 16polyBasic<T>::polyBasic( T coeffs[], int degree ) {
 17  std::cout << "call polyBasic::polyBasic( int coeffs[], int degree )\n" ;
 18  this -> coeffs . resize( degree + 1 ) ;
 19  std::copy( coeffs, coeffs + degree + 1, this -> coeffs . begin() ) ;
 20  reduce() ;
 21}
 22
 23template <typename T>
 24polyBasic<T>::polyBasic( std::vector<T> const & coeffs ) {
 25  std::cout << "call polyBasic::polyBasic(std::vector<T> const & coeffs)\n" ;
 26  this -> coeffs . resize( coeffs.size() ) ;
 27  std::copy( coeffs . begin(), coeffs . end(), this -> coeffs . begin() ) ;
 28  reduce() ;
 29}
 30
 31template <typename T>
 32void
 33polyBasic<T>::reduce() {
 34  while ( (!coeffs.empty()) && coeffs.back() == 0 )
 35    this -> coeffs . pop_back() ;
 36}
 37
 38template <typename T>
 39void
 40polyBasic<T>::print( std::ostream & s ) const {
 41  if ( coeffs . size() == 0 ) {
 42    s << "0" ;
 43  } else if ( coeffs . size() == 1 ) {
 44    s << coeffs[0] ;
 45  } else {
 46    if ( coeffs[0] != 0 ) s << coeffs[0] ;
 47    if ( coeffs[1] != 0 ) {
 48      if ( coeffs[0] != 0 ) s << " + " ;
 49      if ( coeffs[1] == 1 ) s << "x" ;
 50      else                  s << coeffs[1] << "*x" ;
 51    }
 52    for ( int i = 2 ; i < coeffs.size() ; ++i )
 53      if ( coeffs[i] != 0 )
 54        if ( coeffs[i] == 1 ) s << " + x^" << i ;
 55        else                  s << " + " << coeffs[i] << "*x^" << i ;
 56  }
 57}
 58
 59// evaluation operator
 60template <typename T>
 61T
 62polyBasic<T>::operator () ( T x ) const {
 63  T res = 0, xi = 1 ;
 64  for ( int i = 0 ; i < coeffs . size() ; ++i, xi *= x )
 65    res += coeffs[i] * xi ;
 66  return res ;
 67}
 68
 69template <typename T>
 70polyBasic<T> const & 
 71polyBasic<T>::operator = ( polyBasic<T> const & a ) {
 72  if ( coeffs . size() < a . coeffs . size() )
 73    coeffs . resize( a . coeffs . size() ) ;
 74  for ( int i = 0 ; i <= a . degree() ; ++i )
 75    coeffs[i] = a[i] ;
 76  reduce() ;
 77  return *this ;
 78}
 79
 80template <typename T>
 81polyBasic<T> const & 
 82polyBasic<T>::operator += ( polyBasic<T> const & a ) {
 83  if ( coeffs . size() < a . coeffs . size() )
 84    coeffs . resize( a . coeffs . size() ) ;
 85  for ( int i = 0 ; i <= a . degree() ; ++i )
 86    coeffs[i] += a[i] ;
 87  reduce() ;
 88  return *this ;
 89}
 90
 91template <typename T>
 92polyBasic<T> const & 
 93polyBasic<T>::operator -= ( polyBasic<T> const & a ) {
 94  if ( coeffs . size() < a . coeffs . size() )
 95    coeffs . resize( a . coeffs . size() ) ;
 96  for ( int i = 0 ; i <= a . degree() ; ++i )
 97    coeffs[i] -= a[i] ;
 98  reduce() ;
 99  return *this ;
100}
101
102template <typename T>
103polyBasic<T> operator + ( polyBasic<T> const & a, polyBasic<T> const & b ) {
104  int degree = std::max(a.degree(), b.degree()) ;
105  std::vector<T> coeffs(degree+1) ;
106  for ( int i = 0 ; i <= degree ; ++i )
107    coeffs[i] = a.get(i) + b.get(i) ;
108  return polyBasic<T>( coeffs ) ;
109}
110
111template <typename T>
112polyBasic<T> operator - ( polyBasic<T> const & a, polyBasic<T> const & b ) {
113  int degree = std::max(a.degree(), b.degree()) ;
114  std::vector<T> coeffs(degree+1) ;
115  for ( int i = 0 ; i <= degree ; ++i )
116    coeffs[i] = a.get(i) - b.get(i) ;
117  return polyBasic<T>( coeffs ) ;
118}

Explicit instantiation of the functions and methods

File polyBasic.cc

 1#include "polyBasic.hh"  // include definition of class polyBasic
 2#include "polyBasic.hxx" // include declaration of template implementation
 3
 4#define EXPLICIT_INSTANTIATION(TYPE) \
 5template class polyBasic<TYPE> ;     \
 6template polyBasic<TYPE> operator + ( polyBasic<TYPE> const &, polyBasic<TYPE> const &) ; \
 7template polyBasic<TYPE> operator - ( polyBasic<TYPE> const &, polyBasic<TYPE> const &) ; \
 8
 9// explicit instantiation polyBasic for int type
10EXPLICIT_INSTANTIATION(int) ;
11EXPLICIT_INSTANTIATION(long) ;
12EXPLICIT_INSTANTIATION(unsigned) ;
13EXPLICIT_INSTANTIATION(float) ;
14EXPLICIT_INSTANTIATION(double) ;

Extend the class basic polynomial

Polinomial class header

File poly.hh

 1/*
 2 * An example of class implementing integer polynomial
 3 */
 4 
 5#include "polyBasic.hh"
 6
 7template <typename T>
 8class poly : public polyBasic<T> { // inherith all the definition and methods of polyBasic
 9
10  double stupid[1000] ;
11
12public:
13
14  // propagate type to the poly class
15  typedef typename polyBasic<T>::value_type  value_type  ;
16  typedef typename polyBasic<T>::coeffs_type coeffs_type ;
17
18  // contructors
19  poly()
20  : polyBasic<T>()
21  {
22    std::cout << "call poly::poly()\n" ;
23  } // make a zero polinomial
24  
25  poly( poly const & a ) 
26  : polyBasic<T>(a)
27  {
28    std::cout << "call poly::poly( poly const & )\n" ;
29  } // copy constructor
30
31  poly( value_type coeffs[], int degree ) 
32  : polyBasic<T>( coeffs, degree )
33  {
34    std::cout << "call poly::poly( value_type [], int )\n" ;
35  } // make a polynomial from a C vector
36
37  poly( coeffs_type const & coeffs )
38  : polyBasic<T>( coeffs )
39  {
40    std::cout << "call poly::poly( coeffs_type const & )\n" ;  
41  } // make a polynomial from a C vector
42
43  // internal operator
44  poly<T> const & operator *= ( poly<T> const & a ) ;
45  poly<T> const & operator /= ( poly<T> const & a ) ;
46  poly<T> const & operator %= ( poly<T> const & a ) ;
47} ;
48
49// external operator
50template <typename T> poly<T> operator + ( poly<T> const & a, poly<T> const & b ) ;
51template <typename T> poly<T> operator - ( poly<T> const & a, poly<T> const & b ) ;
52template <typename T> poly<T> operator * ( poly<T> const & a, poly<T> const & b ) ;
53template <typename T> poly<T> operator / ( poly<T> const & a, poly<T> const & b ) ;
54template <typename T> poly<T> operator % ( poly<T> const & a, poly<T> const & b ) ;

Body of the templated functions and methods

File poly.hxx

 1// contructors
 2
 3template <typename T>
 4poly<T> operator + ( poly<T> const & a, poly<T> const & b ) {
 5  int degree = std::max(a.degree(), b.degree()) ;
 6  std::vector<T> coeffs(degree+1) ;
 7  for ( int i = 0 ; i <= degree ; ++i )
 8    coeffs[i] = a.get(i) + b.get(i) ;
 9  return poly<T>( coeffs ) ;
10}
11
12template <typename T>
13poly<T> operator - ( poly<T> const & a, poly<T> const & b ) {
14  int degree = std::max(a.degree(), b.degree()) ;
15  std::vector<T> coeffs(degree+1) ;
16  for ( int i = 0 ; i <= degree ; ++i )
17    coeffs[i] = a.get(i) - b.get(i) ;
18  return poly<T>( coeffs ) ;
19}
20
21template <typename T>
22poly<T> operator * ( poly<T> const & a, poly<T> const & b ) {
23  int degree = a . degree() + b . degree() ;
24  std::vector<T> coeffs(degree+1) ;
25  for ( int i = 0 ; i <= degree ; ++i ) {
26    coeffs[i] = 0 ;
27    for ( int k = 0 ; k <= i ; ++k )
28      coeffs[i] += a.get(k)*b.get(i-k) ;
29  }
30  return poly<T>( coeffs ) ;
31}

Explicit instantiation of the functions and methods

File poly.cc

 1#include "poly.hh"  // include definition of class polyBasic
 2#include "poly.hxx" // include declaration of template implementation
 3
 4#define EXPLICIT_INSTANTIATION(TYPE) \
 5template class poly<TYPE> ;          \
 6template poly<TYPE> operator + ( poly<TYPE> const &, poly<TYPE> const &) ; \
 7template poly<TYPE> operator - ( poly<TYPE> const &, poly<TYPE> const &) ; \
 8template poly<TYPE> operator * ( poly<TYPE> const &, poly<TYPE> const &) ; \
 9
10// explicit instantiation polyBasic for int type
11EXPLICIT_INSTANTIATION(int) ;
12EXPLICIT_INSTANTIATION(long) ;
13EXPLICIT_INSTANTIATION(unsigned) ;
14EXPLICIT_INSTANTIATION(float) ;
15EXPLICIT_INSTANTIATION(double) ;

Testing the class

File test.cc

 1#include "poly.hh"
 2#include <iostream>
 3#include <cmath>
 4
 5using std::abs ; // extract only abs fron std namespace
 6
 7typedef float vtype ;
 8
 9class polyMinimal {
10public:
11  typedef int value_type ;
12  int coeffs[100] ;
13  int deg ;
14  // access to the coefficients
15  int const & operator [] ( int i ) const { return coeffs[i] ; }
16  int       & operator [] ( int i )       { return coeffs[i] ; } 
17  int degree() const { return deg ; }
18} ;
19
20/*
21 * Trivial way to define a (quite) generic routine
22 * for the sum of the abs of coeffs.
23 */
24template <typename T>
25T
26addAbsCoeffsOld( polyBasic<T> const & p ) {
27  T res = 0 ;
28  for ( int i = 0 ; i <= p.degree() ; ++i )
29    res += abs(p[i]) ;
30  return res ;
31}
32
33/*
34 * More general routine 
35 */
36template <typename POLY>
37typename POLY::value_type
38addAbsCoeffs( POLY const & p ) {
39  typename POLY::value_type res = 0 ;
40  for ( int i = 0 ; i <= p.degree() ; ++i )
41    res += abs(p[i]) ;
42  return res ;
43}
44
45int
46main() {
47  poly<vtype> a, b, c, d ;
48  poly<vtype> e(a) ;
49  vtype coeffs[] = { 1, 0, 2, 3, 4, 0 } ;
50  int   degree   = sizeof(coeffs)/sizeof(coeffs[0])-1 ;
51  poly<vtype> f(coeffs,degree) ;
52  
53  a = f+f ;
54  
55  std::cout << "POLY f   = " << f << '\n' ;
56  std::cout << "POLY a   = " << a << '\n' ;
57  std::cout << "POLY a*f = " << a*f << '\n' ;
58  
59  std::cout << "|f|      = " << addAbsCoeffs(f) << '\n' ;
60  
61  polyMinimal pp ;
62  pp . deg = 1 ;
63  pp . coeffs[0] = pp . coeffs[1] = 2 ;
64
65  std::cout << "|pp|    = " << addAbsCoeffs(pp) << '\n' ;
66
67  return 0 ;
68}