514     '''cache most recent gets from or sets to this dictionary'''

   533     """Dict that caches most recent accesses and sets.

   515     def __init__(self, maxsize):

   534 

   535     The dict consists of an actual backing dict - indexed by original

   536     key - and a doubly linked circular list defining the order of entries in

   537     the cache.

   538 

   539     The head node is the newest entry in the cache. If the cache is full,

   540     we recycle head.prev and make it the new head. Cache accesses result in

   541     the node being moved to before the existing head and being marked as the

   542     new head node.

   543 

   544     NOTE: construction of this class doesn't scale well if the cache size

   545     is in the thousands. Avoid creating hundreds or thousands of instances

   546     with large capacities.

   547     """

   548     def __init__(self, max):

   517         self._maxsize = maxsize

   550 

   518         self._order = collections.deque()

   551         self._head = head = _lrucachenode()

   519 

   552         head.prev = head

   520     def __getitem__(self, key):

   553         head.next = head

   521         value = self._cache[key]

   554         self._size = 1

   522         self._order.remove(key)

   555         self._capacity = max

   523         self._order.append(key)

   556 

   524         return value

   557     def __len__(self):

   525 

   558         return len(self._cache)

   526     def __setitem__(self, key, value):

   559 

   527         if key not in self._cache:

   560     def __contains__(self, k):

   528             if len(self._cache) >= self._maxsize:

   561         return k in self._cache

   529                 del self._cache[self._order.popleft()]

   562 

   563     def __iter__(self):

   564         # We don't have to iterate in cache order, but why not.

   565         n = self._head

   566         for i in range(len(self._cache)):

   567             yield n.key

   568             n = n.next

   569 

   570     def __getitem__(self, k):

   571         node = self._cache[k]

   572         self._movetohead(node)

   573         return node.value

   574 

   575     def __setitem__(self, k, v):

   576         node = self._cache.get(k)

   577         # Replace existing value and mark as newest.

   578         if node is not None:

   579             node.value = v

   580             self._movetohead(node)

   581             return

   582 

   583         if self._size < self._capacity:

   584             node = self._addcapacity()

   531             self._order.remove(key)

   586             # Grab the last/oldest item.

   532         self._cache[key] = value

   587             node = self._head.prev

   533         self._order.append(key)

   588 

   534 

   589         # At capacity. Kill the old entry.

   535     def __contains__(self, key):

   590         if node.key is not _notset:

   536         return key in self._cache

   591             del self._cache[node.key]

   592 

   593         node.key = k

   594         node.value = v

   595         self._cache[k] = node

   596         # And mark it as newest entry. No need to adjust order since it

   597         # is already self._head.prev.

   598         self._head = node

   599 

   600     def __delitem__(self, k):

   601         node = self._cache.pop(k)

   602         node.markempty()

   603 

   604         # Temporarily mark as newest item before re-adjusting head to make

   605         # this node the oldest item.

   606         self._movetohead(node)

   607         self._head = node.next

   608 

   609     # Additional dict methods.

   610 

   611     def get(self, k, default=None):

   612         try:

   613             return self._cache[k]

   614         except KeyError:

   615             return default

   540         self._order = collections.deque()

   624 

   625     def _movetohead(self, node):

   626         """Mark a node as the newest, making it the new head.

   627 

   628         When a node is accessed, it becomes the freshest entry in the LRU

   629         list, which is denoted by self._head.

   630 

   631         Visually, let's make ``N`` the new head node (* denotes head):

   632 

   633             previous/oldest <-> head <-> next/next newest

   634 

   635             ----<->--- A* ---<->-----

   636             |                       |

   637             E <-> D <-> N <-> C <-> B

   638 

   639         To:

   640 

   641             ----<->--- N* ---<->-----

   642             |                       |

   643             E <-> D <-> C <-> B <-> A

   644 

   645         This requires the following moves:

   646 

   647            C.next = D  (node.prev.next = node.next)

   648            D.prev = C  (node.next.prev = node.prev)

   649            E.next = N  (head.prev.next = node)

   650            N.prev = E  (node.prev = head.prev)

   651            N.next = A  (node.next = head)

   652            A.prev = N  (head.prev = node)

   653         """

   654         head = self._head

   655         # C.next = D

   656         node.prev.next = node.next

   657         # D.prev = C

   658         node.next.prev = node.prev

   659         # N.prev = E

   660         node.prev = head.prev

   661         # N.next = A

   662         # It is tempting to do just "head" here, however if node is

   663         # adjacent to head, this will do bad things.

   664         node.next = head.prev.next

   665         # E.next = N

   666         node.next.prev = node

   667         # A.prev = N

   668         node.prev.next = node

   669 

   670         self._head = node

   671 

   672     def _addcapacity(self):

   673         """Add a node to the circular linked list.

   674 

   675         The new node is inserted before the head node.

   676         """

   677         head = self._head

   678         node = _lrucachenode()

   679         head.prev.next = node

   680         node.prev = head.prev

   681         node.next = head

   682         head.prev = node

   683         self._size += 1

   684         return node