Elephants 1.0.0
Memoization utilities with fading memory.
License: MIT
Keywords: memo,memoize,cache

=========
Elephants
=========

This is a memoize package using StrongDict a class
introduced in this package.  StrongDict described in
detail in the following section uses a linked list of
strong references in combination with a weak reference
dictionary to enable fading memory storage by either
restricting the number of items in the store or imposing a
time limit on items stored.


About the name
--------------

This package is named Elephants because they are the symbol
of remembering, or in a modern Python world, memoizing.

Examples
--------

Simple memoize
^^^^^^^^^^^^^^

::

  from elephants import memo

  @memo
  def fib(n):
    if n<2: return 1
    return fib(n-1) + fib(n-2)

  
Memoize with time limit
^^^^^^^^^^^^^^^^^^^^^^^

The following pattern demonstrates the @memo_until
decorator to cache data object instances for a given
length of time.

::

   from elephants import memo_until

   class MyDataObject(object):
     def __init__(self, x):
       self.x = x

     def __str__(self): return str(self.x)

   @memo_until(tlimit=3600) # seconds
   def get_my_data_obj_instance(x):
     print 'Getting a new instance for x =', x
     return MyDataObject(x)


   y = get_my_data_obj_instance(1)
   y = get_my_data_obj_instance(2)
   y = get_my_data_obj_instance(1)
   y = get_my_data_obj_instance(3)
   y = get_my_data_obj_instance(1)

   print 'The final value of y should be 1.  It is', y

Memoize with length limit
^^^^^^^^^^^^^^^^^^^^^^^^^

The following pattern demonstrates the @memo_until
decorator to cache data object instances for a given
length of time.

::

   from elephants import nmemo

   class MyDataObject(object):
     def __init__(self, x):
       self.x = x

     def __str__(self): return str(self.x)

   @nmemo(limit=2) # Limit the cache to only two items.
   def get_my_data_obj_instance(x):
     print 'Getting a new instance for x =', x
     return MyDataObject(x)


   y = get_my_data_obj_instance(1)
   y = get_my_data_obj_instance(2)
   y = get_my_data_obj_instance(3)
   y = get_my_data_obj_instance(1)

   print 'At this point the cache should only have 1 and 3.'

StrongDict
^^^^^^^^^^

A dictionary using strong and weak references.

Items are stored in a WeakValueDictionary.  They are also
stored in a the linked list, the strong cache, holding
strong references.  Retreival is a fast
WeakValueDictionary lookup.  Items most recently used are
moved to the top of the strong cache list.  Options are
provided to fade from the strong linked list defined by
either a time limit or a list quantity limit.  The default
is to keep everything in strong linked list forever.  If
an item is removed from the strong cache and later queried
and found in the WeakValuedictionary it will be added back
to the strong cache.  This can only happen if an reference
to the removed item exists outside the cache.

As long as items have a strong reference they will stay in
the WeakValueDictionary.  However, if an item no longer
has a strong reference it is not guaranteed to be in the
WeakValueDictionary.  The WeakValueDictionary will
"forget" about objects not also referenced elsewhere, in
this case the StrongDict() strong reference linked list.

The weakref.WeakValueDictionary() cannot hold native types
like int or str.  But it can hold a python object that has
native types.  This StrongDict class uses a Link object
defined above to hold all values stored in the cache.
Therefore the user of StrongDict() does not need to be
concerned with this limitation of the weakref package.

CAVEAT EMPTOR: If a class instance is used as key in the
               dictionary then the __hash__() method may
               need to be implmented.

StrongDict Example
^^^^^^^^^^^^^^^^^^

::

   from elephants import StrongDict

   w = StrongDict(limit=3)

   # populate with test cases
   for i in range(10): w[i] = i * i

   # demonstrate limit is imposed and len() works for StrongDict
   assert(len(w) == 3)

   assert(6 not in w)

   # demonstrate that del works on StrongDict instances
   del w[8]
   assert(len(w) == 2)

   # demonstrate that KeyError is thrown when item is not in the dictionary.
   try:
     del w[6]
     assert(False)
   except KeyError:
     'It cannot delete w[7] since it is not there.'
     assert(True)
     
   # demonstrate for negation on inclusion test.
   del w[9]
   assert(9 not in w)

   # demonstrate equals operator
   x = {}
   for i in range(4):
     w[i] = x[i]= i * i
   del x[0]
   assert(w == x)

   # demonstrate conversion to dict
   x = dict(w)
   print x
   print type(x)


Special Note
^^^^^^^^^^^^

@memo, @nmemo, and @memo_until have two special arguments.

If a decorated method is called with
'size_elephant_cache' as the argument it will return the
number of items in the cache.  If it is called with
'clear_elephant_cache' as the argument it will clear the
cache as shown in the following example.


Example
^^^^^^^

::

   from elephants import memo

   @memo
   def f(x): return x * x

   for i in range(10): f(i)

   print 'There are', f('size_elephant_cache'), 'items in the cache.'
   f('clear_elephant_cache')
   print 'There are', f('size_elephant_cache'), 'items in the cache.'

Thank you
=========

A special thank you to Jonathan Arrender Smith for his
guidance and education.