#!/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_class.__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_class.__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


# 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_class
@memoise_class
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))