// g++ -ftemplate-depth-50 -c fibo.C &> log
// grep matching log

template <int n, int f> struct FibOutput { FibOutput(int); };

template <int n> struct Fibonacci {
    static const int fib = Fibonacci<n-1>::fib + Fibonacci<n-2>::fib;
};
template <> struct Fibonacci<1> { static const int fib = 1; };
template <> struct Fibonacci<0> { static const int fib = 0; };

template <int i> struct fibo_output {
    fibo_output<i-1> a;
    static const int fib = Fibonacci<i>::fib;
    void fibo() { a.fibo(); FibOutput<i, fib > b; }

};
template<> struct fibo_output<1> {
    static const int fib = Fibonacci<1>::fib;
    void fibo() { FibOutput<1, fib> b; }
};

void OutputAllFiboNumbers() {
    const int M = 10;
    fibo_output<M> f;
    f.fibo();
}


/*
 * If template instantiations are not cached by compiler the cost of
 * instantiation for Fibonnacci<i> is C(i) = C(i-1) + C(i-2) + O(1) = O(2^i). 
 * Additionaly for each ith fibonacci number the whole instantiation history is printed, 
 * which is O(i). Therefore error message complexity is E(n) = O(n^2)
 * Total complexity: T(n) = C(n) + C(n-1) + ... + C(1) + E(n) = O(2^i)
 *
 * If template instantiations are cached (Fibonnacci<i> for each i is instantiated only once)
 * then whole instantiation costs O(n). But because of warning output,
 * total complexity is T(n) = O(n) + E(n) = O(2^i)
 * 
 */