#!/usr/bin/env python3
# An example of using Python decorators to implement memoisation
# Based on this online article: http://www.artima.com/weblogs/viewpost.jsp?thread=240808
# by Bruce Eckel

# tracing function calls, using a class-based decorator
class trace_class(object):
    """Perform memoisation on the 1-argument function @func@, with @n@ as argument."""

    def __init__(self, f):
        print(".. trace.__init__\n")
        self.f = f

    def __call__(self, n):
        print("++ computing", self.f.__name__," with ", str(n))
        return self.f(n)

# memoisation decorator, implemented as a class    
class memoise_class(object):
    """Perform memoisation on the 1-argument function @func@, with @n@ as argument."""

    def __init__(self, f):
        print(".. memoise.__init__\n")
        self.f = f

    def __call__(self, n, memo_dict=dict()):
        assert not(memo_dict is None)
        if n in memo_dict.keys():
            # print("!! Found "+str(n)+" in memo dictionary\n")
            return memo_dict[n]
        else:
            print("++ computing", self.f.__name__," with ", str(n))
            x = self.f(n)
            memo_dict[n] = x
            print(".. keys in memo_dict: ", str(memo_dict.keys()));
            return x
        # print("<< Exited", self.f.__name__)

def trace(f):
    """Perform tracing on the 1-argument function @func@, with @n@ as argument."""

    def trace_func(n):
        print("++ computing", f.__name__," with ", str(n))
        return f(n)

    return trace_func

# memoisation decorator, function-based
def memoise(f):
    """Perform memoisation on the 1-argument function @func@, with @n@ as argument."""

    def memo_func(n, memo_dict=dict()):
        assert not(memo_dict is None)
        if n in memo_dict.keys():
            #print("!! Found "+str(n)+" in memo dictionary")
            return memo_dict[n]
        else:
            print("++ computing", f.__name__," with ", str(n))
            x = f(n)
            memo_dict[n] = x
            print(".. keys in memo_dict: ", str(memo_dict.keys()));
            return x

    return memo_func

# plain old fib
# use a trace decorator to show all function calls to fib
# use a memoise decorator to remember values from previous calls
#@trace
@memoise
def fib(n):
    """Compute Fibonacci number of @n@."""
    if n==0 or n==1:
         return 1
    else:
        return fib(n-1)+fib(n-2)

    
# Main -------------------------------------------------------
# depending on decoration above, this uses memoisation; the code here is unchanged!
print(fib(8))