"""LRU caching.

Author: Erez Shinan
Date  : 28/12/07
"""

from weakref import proxy

class MyDoublyLinkedListNode(object):
	def __init__(self, data, prev=None, next=None):
		self.data = data
		self.prev = prev
		self.next = next
	def remove(self):
		if not self.next:
			raise Exception("I'm the last node!")
		if self.prev:
			self.prev.next = self.next
		self.next.prev = self.prev
	def append(self, node):
		if self.next:
			raise NotImplmentedError("I don't have use for real insertion")
		self.next = node
		node.prev = proxy(self)
	def __repr__(self):
		return '%s(%r, %r)'%(self.__class__.__name__,self.data,self.next)

class LRUDict(dict):
	"""LRUDict - Least Recently Used Dict
	Automatically drops items least recently added to the dict.
	All operations are of same complexity as normal dict.

	Author: Erez Shinan
	Date  : 28/12/07
	"""

	def __init__(self, limit):
		self._limit = limit

		# Use order initialization
		self._ll_head = self._ll_last = MyDoublyLinkedListNode(None)
		self._ll_mapping = {}

	def pop_lru_key(self):
		key = self._ll_head.next.data
		dict.__delitem__(self, key)
		del self._ll_mapping[key]
		self._ll_head.next.remove()
		return key

	def __setitem__(self, key, value):
		# if key is last node (most recent), nothing needs to be done
		if self._ll_last.data == key:
			return dict.__setitem__(self, key, value)
		
		if key in self:
			# remove from llist (in order be appended to the end)
			self._ll_mapping[key].remove()
		elif len(self) == self._limit:
			# remove least recently used item
			self.pop_lru_key()
				
		# append to llist and update mapping
		new_node = MyDoublyLinkedListNode(key)
		self._ll_last.append(new_node)
		self._ll_last = new_node
		self._ll_mapping[key] = new_node

		# Actually set the item
		dict.__setitem__(self, key, value)

		assert len(self) == len(self._ll_mapping) and len(self) <= self._limit

	def __delitem__(self, key):
		raise NotImplmentedError("Not necessary for LRU Cache")



class Cached(object):
	def __init__(self, limit):
		self.limit = limit

	def __call__(self, func):
		cache = LRUDict(self.limit)
		def wrapper_func(*args):
			try:
				result = cache[args]
			except KeyError:
				result = func(*args)
			cache[args] = result	# needed anyway, to update lru
			return result
		wrapper_func.cache = cache
		return wrapper_func