<\body> Several important template classes, such as , , and admit a last template parameter , called the (or the traits class, in C++ terminology). For most template classes, the class itself determines the internal representation of instances. For instance, the class corresponds to dense univariate polynomials, determined by a low level vector of coefficients. The implementation variant is used to specify the actual algorithms which are used for common operations. For instance, the variant uses the naive )> algorithm for polynomial multiplication, whereas Karatsuba multiplication is used by the variant polynomial_naive\>. As is suggested by the variant polynomial_naive\>, new variants can be built on top of other variants and existing variants can be customized. Typically, an implementation of dense polynomials provides several features: <\itemize> Vectorial routines on polynomials, such as addition. Other linear-time routines, such as differentiation. Multiplication. Division. Greatest common divisor. Several higher level routines, such as subresultants or multi-point evaluation. Variants and features are essentially empty classes, which are mainly used as template parameters. provides a standard helper class, which allows to associate a concrete implementation to a feature and variant. For instance, polynomial multiplication corresponds to the feature . The main multiplication routine for dense polynomials is a static member function <\cpp-fragment> implementation\polynomial_multiply,polynomial_naive\::mul of the implementation helper class. This routine directly operates on vectors in memory: <\cpp-fragment> template\typename C, typename K\ static void mul (C* dest, const C* s1, const K* s2, nat n1, nat n2) { \ \ if (n1+n2\0) \ \ \ \ Pol::clear (dest, n1+n2-1); \ \ while (n2 != 0) { \ \ \ \ Pol::mul_add (dest, s1, *s2, n1); \ \ \ \ dest++; s2++; n2--; \ \ } } Here is an alias for polynomial_linear,polynomial_naive\>, hence the implementation of naive multiplication relies on the implementation of naive vectorial and linear-time algorithms on polynomials. From the high level point of view, the implementation of polynomial multiplication for the type C,V\> relies on the low level multiplication algorithm determined by the variant : <\cpp-fragment> template\typename C, typename V\ polynomial\C,V\ operator * (const polynomial\C,V\& P1, const polynomial\C,V\& P2) { \ \ typedef implementation\polynomial_multiply,V\ Pol; \ \ nat n1= N(P1), n2= N(P2); \ \ if (n1 == 0 \|\| n2 == 0) return polynomial\C,V\ (); \ \ nat l= aligned_size\C,V\ (n1+n2-1); \ \ C* r= mmx_new\C\ (l); \ \ Pol::mul (r, seg (P1), seg (P2), n1, n2); \ \ return polynomial\C,V\ (r, n1+n2-1, l); } A default variant is usually defined in terms of the remaining template parameters. In the case of polynomials, this is accomplished by means of the template: for any coefficient type , C\::PV> yields the default variant for . In fact, the template takes three arguments: the feature, the polynomial variant and the variant for the actual implementation. This allows for the customization of a specific feature. More precisely, assume that we are given a feature and a variant and that we want to define a new variant V\> with a different implementation of the feature , but unaltered implementations of all other features. This is achieved using a code of the type <\cpp-fragment> template\typename V, typename W\ struct implementation\F,V,customized\W\ \: \ \ public implementation\F,V,W\ { \ \ typedef implementation\F,V,W\ Fallback; \ \ ... }; For the actual implementation of the customized feature, one may rely on the original implementation specified by the variants and . Here we notice that F,V\> is equivalent to F,V,V\>. We recall that the variant mechanism is only used in order to implement different algorithms for a similar functionality, while presupposing a given internal representation. Some higher level functions on polynomials may still be correct for polynomials with alternative internal representations. In that case, a new template class should be defined for each alternative representation, such as . This class should be implemented with care, so as to match the same signature as the usual dense class . For instance, if we have an operation <\cpp-fragment> template\typename C, typename V\ polynomial\C,V\ foo (const polynomial\C,V\& p) { ... } which is not specific to dense polynomials, then we should have its sparse counterpart with the same name <\cpp-fragment> template\typename C, typename V\ sparse_polynomial\C,V\ foo (const sparse_polynomial\C,V\& p) { ... } The high level functionality can then be implemented by using the class of polynomials itself as a template parameter: <\cpp-fragment> template\typename Pol\ Pol bar (const Pol& p) { \ \ return foo (foo (p)); } . If you don't have this file, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.> <\initial> <\collection>