Defining a recursive pattern

Question

I have a recursive template definition (I just made up this term). I think the code explains this better.

template<typename X> class Domain { public: X begin; X end; Domain( X _begin, X _end) : begin(_begin) , end(_end) { // ... } bool Contains( const X& t) const { // ... } }; template<typename X, typename Y> class IFunction { public: Domain<X> myDomain; public: IFunction( const Domain<X>& dom) : myDomain(dom) { } virtual Y Calc( const X& IV) const = 0; virtual IFunction<X, Y>* GetDerivative() const = 0; }; template<typename X, typename Y, int n> class NthOrderFunction : public IFunction<X, Y> { public: double coeffs[n+1]; public: NthOrderFunction( const Domain<X>& dom, ... ) : IFunction(dom) { } virtual Y Calc( const X& IV) const { // temporary compile solution return Y(); } virtual IFunction<X, Y>* GetDerivative() const { if ( n > 1 ) { return new NthOrderFunction<X, Y, n-1>(dom, ...); } return new FlatLine<X, Y>(dom); } }; 

I took out a lot of inheritance and other relationships to keep it readable, simple, and mysterious. Therefore, when editing the code, a new typo may appear, but please ignore it. The code has worked perfectly for many years, the only problem I am facing is the one I am going to point out.

I recently added a GetDerivative function, and its implementation in the NthOrderFunction class gives me problems. I know that template classes are defined before compilation, but after preprocessing. Thus, I cannot figure out how to use this functionality to work. Each NthOrderFunction with a template parameter n requires an NthOrderFunction with a template parameter n-1. You can see that this is a problem. The fact is that although n will never be negative in use, I will not do any amount of coding; it will convince the "template definition mechanism" not to worry about cases n <1;

Has anyone had a problem with this? And what solutions did you come up with?

Answer 1

Add something like:

 template<typename X, typename Y> class NthOrderFunction<X, Y, 1> : public IFunction<X, Y> { public: double coeffs[n+1]; public: NthOrderFunction( const Domain<X>& dom, ... ) : IFunction(dom) { } virtual Y Calc( const X& IV) const { // temporary compile solution return Y(); } virtual IFunction<X, Y>* GetDerivative() const { return new FlatLine<X, Y>(dom); } }; 

and remove the case n == 1 from your recursive case.

As a tip, get some kind of book or textbook or one in metaprogramming templates. One of the basic methods is to use recursion in templates this way. Strictly speaking, this is not metaprogramming; these are just recursive patterns. The book / tutorial describes how more advanced tricks work, which you can take advantage of when expanding this.

The reason for this is that the original will still extend the if compilation time to the runtime code (which will never be executed). This code replaces one case where it can be compiled with one where it is not, so there is no way for infinite recursion.

Answer 2

This is the same as metaprogramming the 101 example-factorial template, only the content is a bit more complicated.

 template<int N> struct factorial { enum { value = N * factorial<N-1>::value }; }; 

And you need the same solution - specialization for the base case.

 template<> struct factorial<1> { enum { value = 1 }; }; 

Yours will be incomplete, not complete, but it will still work.