// fibonacci.C
// ----------------------------------------------------------------
// COMP 290-001: Algorithm Library Design, Lutz Kettner, 01/19/2000
// Example solution to exercise 2.
// View output with "|& grep Output".

// Output complexity: assume that the compiler caches instantiated
// templates, here fibo<n>, which drops the complexity from exp to linear.
// But the error messages are quadratic in n, since the whole instantiation
// history is printed for each message with g++.

// Class to create "output" at compile time (error messages)
template <int n, int f> struct Output {};    // creates output

// Class to compute n-th Fibonacci number
template <int n> struct fibo {
    enum { val = fibo<n-1>::val + fibo<n-2>::val };
};
template<> struct fibo<1> { enum { val = 1}; };
template<> struct fibo<0> { enum { val = 0}; };

// Class to iterate through all values: 1..i
template <int i> struct Fibo_print {
    Fibo_print<i-1> a;
    enum { val = fibo<i>::val };
    void f() { a.f(); Output<i,val> d = val; }
};
template<> struct Fibo_print<1> { 
    enum { val = fibo<1>::val };
    void f() { Output<1,val> d = val; }
};

void foo() {
    Fibo_print<17> a;
    a.f();
}