// fibo6.cpp
// Glenn G. Chappell
// 6 Nov 2009
//
// For CS 311 Fall 2009
// Computing Fibonacci Numbers
// Version #6: Recursion Eliminated (brute force method)
//
// This program is based on fibo1.cpp.
// Recursion has been eliminated using the "brute force" technique
//  described in class, applying as little intelligence as possible.

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <stack>
using std::stack;


// Define numeric type for holding a (large?) Fibonacci number
typedef long long bignum;
// NOTE: (long long) is not a built-in type in ANSI-1998 C++.
// Use "long" above to make this program ANSI-1998 compliant.
// (And probably reduce the upper limit of the loop in function main.)


/*
Original function fibo, from fibo1.cpp:

bignum fibo(int n)
{
    // BASE CASE
    if (n <= 1)
        return bignum(n);

    // RECURSIVE CASE
    return fibo(n-2) + fibo(n-1);
}

Modified version used as the basis of this code:

bignum fibo(int n)
{
    bignum v1, v2;

    // BASE CASE
    if (n <= 1)
        return bignum(n);

    // RECURSIVE CASE
    v1 = fibo(n-2);  // Recursive call #1
    v2 = fibo(n-1);  // Recursive call #2
    return v1 + v2;  // Return the result
}
*/


// struct FiboStackFrame
// "Stack frame" - holds local values for function fibo.
// In a structure so that they can be saved on a stack.
struct FiboStackFrame {
    int n;               // Parameter
    bignum v1;           // Result of recursive call #1
    bignum v2;           // Result of recursive call #2
    bignum returnValue;  // Value to return
    int returnAddr;      // Return address:
                         //     0: outside world (return from function)
                         //     1: recursive call #1 (return to label1)
                         //     2: recursive call #2 (return to label2)
};


// fibo
// Given n, returns F(n) (the nth Fibonacci number).
// F(0) = 0. F(1) = 1. For n >= 2, F(n) = F(n-2) + F(n-1).
// Pre:
//     n >= 0.
//     F(n) is a valid bignum value.
// Notes:
//     If bignum is 32-bit signed integer,
//      then preconditions hold for 0 <= n <= 46.
//     If bignum is 64-bit signed integer,
//      then preconditions hold for 0 <= n <= 92.
// Post:
//     Return value is F(n).
// May throw std:bad_alloc on out-of-memory.
// Strong Guarantee
bignum fibo(int n)
{
    // ***************************************
    // ORIGINAL CODE:
    // bignum fibo(int n)
    // {
    //     bignum v1, v2;
    // ***************************************

    // Local variables
    stack<FiboStackFrame> s;
                  // Stack, used for recursion elimination
                  // Top of stack holds current local variables
                  //  and place for return value, and return location
    int tmpi;     // Temp value - holds an int during stack op's
    bignum tmpb;  // Temp value - holds a bignum during stack op's

    // Set up stack frame
    s.push(FiboStackFrame());  // Make new stack frame
    s.top().n = n;             // Set parameter
    s.top().returnAddr = 0;    // Set return address (called by outside world)

    // ***************************************
    // BEGIN LOOP
    // while (true) loop used for recursion
    //  elimination
    // ***************************************
    while (true)
    {

        // ***************************************
        // ORIGINAL CODE:
        // // BASE CASE
        // if (n <= 1)
        //     return bignum(n);
        // ***************************************
        if (s.top().n <= 1)
        {
            // Do "return n;"
            s.top().returnValue = bignum(s.top().n);

            if (s.top().returnAddr == 1)       // Back to recursive call #1
                goto label1;
            else if (s.top().returnAddr == 2)  // Back to recursive call #2
                goto label2;
            else                               // Back to outside world
            {
                tmpb = s.top().returnValue;
                s.pop();
                return tmpb;
            }
        }

        // ***************************************
        // ORIGINAL CODE:
        // // RECURSIVE CASE
        // v1 = fibo(n-2);  // Recursive call #1
        // ***************************************
        tmpi = s.top().n - 2;
        s.push(FiboStackFrame());  // Make new stack frame
        s.top().n = tmpi;          // Set parameter
        s.top().returnAddr = 1;    // Set return address (recursive call #1)
        continue;                  // Do "recursive call"
label1:                            // Place to return to
        tmpb = s.top().returnValue;
        s.pop();
        s.top().v1 = tmpb;         // Put returned value in v1

        // ***************************************
        // ORIGINAL CODE:
        // v2 = fibo(n-1);  // Recursive call #2
        // ***************************************
        tmpi = s.top().n - 1;
        s.push(FiboStackFrame());  // Make new stack frame
        s.top().n = tmpi;          // Set parameter
        s.top().returnAddr = 2;    // Set return address (recursive call #2)
        continue;                  // Do "recursive call"
label2:                            // Place to return to
        tmpb = s.top().returnValue;
        s.pop();
        s.top().v2 = tmpb;         // Put returned value in v2

        // ***************************************
        // ORIGINAL CODE:
        // return v1 + v2;  // Return the result
        // ***************************************
        s.top().returnValue = s.top().v1 + s.top().v2;

        if (s.top().returnAddr == 1)       // Back to recursive call #1
            goto label1;
        else if (s.top().returnAddr == 2)  // Back to recursive call #2
            goto label2;
        else                               // Back to outside world
        {
            tmpb = s.top().returnValue;
            s.pop();
            return tmpb;
        }

    // ***************************************
    // END LOOP
    // while (true) loop used for recursion
    //  elimination
    // ***************************************
    }
}


// main
// From fibo1.cpp.
int main()
{
    cout << "Fibonacci Numbers" << endl;
    cout << endl;
    for (int i = 0; i <= 92; ++i)
    {
        cout << i << ": " << fibo(i) << endl;
    }
    cout << endl;

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}