"""
 memoize.py

 Demo of memoization using a python decorator class.

 This example is based closely on 
 http://stackoverflow.com/questions/1988804/
 what-is-memoization-and-how-can-i-use-it-in-python

 # with the "@memoize" line commented out :
 $ python memoize.py 
 fibonacci(10) = 89  (177 calls)
 fibonacci(20) = 10946  (21891 calls)
 fibonacci(30) = 1346269  (2692537 calls)      # Very inefficient.

 # with @memoize :
 $ python memoize.py 
 fibonacci(10) = 89  (11 calls)
 fibonacci(20) = 10946  (10 calls)
 fibonacci(30) = 1346269  (10 calls)           # Ah ... much better

 - - - - - - - - - - - - - - - - - - 

 Note that the python 'decorator' sytax which looks like this :

   @thingy
   def foo(a,b,c):
      stuff

 gets translated into essentially 

   def foo(a,b,c):         # orginal function
      stuff
   foo = thingy(foo)       # replace function with 'decorated' one

 In the code below, this means that the fibonacci function is replaced
 by an instance of the memoize class. Thus the translation is

 fibonacci(n)
    becomes                             fibonacci.__call__(n)
    which looks in the dict             fibonacci.memo[n]
    or calls the orginal function via   ficonacci.f(n)

 - - - - - - - - - - - - - - - - - -

 *Now* we're having fun.

 Jim Mahoney | cs.marlboro.edu | Apr 2012 | MIT License
"""

fibonacci_call_counter = 0

class memoize(object):
    """ A decorator which automatically caches function calls. """
    # As implemented here, this technique requires that the function
    # arguments x be "hashable", that is, something that can be used a
    # dictionary key. Integers, strings, and tuples are all
    # hashable. However, arrays are not.
    def __init__(self, f):
        self.f = f            # original function
        self.memo = {}        # remember {x:y} for every y=f(x)
    def __call__(self, *args):
        if not args in self.memo:             # Did we save this?
            self.memo[args] = self.f(*args)   #   Save it now.
        return self.memo[args]                # Return saved value.

@memoize
def fibonacci(n):
    global fibonacci_call_counter             # 
    fibonacci_call_counter += 1               # increment global counter
    if n < 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

def fibonacci_and_count(n):
    global fibonacci_call_counter             #
    fibonacci_call_counter = 0                # reset global counter
    fib = fibonacci(n)
    return (fib, fibonacci_call_counter)

def main():
    for n in (10, 20, 30):
        (fib, count) = fibonacci_and_count(n)
        print " fibonacci(%i) = %i  (%i calls)" % (n, fib, count)

if __name__ == "__main__":
    main()