1 # Copyright (C) 2011 Google Inc. All rights reserved. 2 # 3 # Redistribution and use in source and binary forms, with or without 4 # modification, are permitted provided that the following conditions are 5 # met: 6 # 7 # * Redistributions of source code must retain the above copyright 8 # notice, this list of conditions and the following disclaimer. 9 # * Redistributions in binary form must reproduce the above 10 # copyright notice, this list of conditions and the following disclaimer 11 # in the documentation and/or other materials provided with the 12 # distribution. 13 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 14 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 15 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 16 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 17 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 18 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 19 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 21 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 25 26 class Node(): 27 def __init__(self, key, value): 28 self.key = key 29 self.value = value 30 self.prev = None 31 self.next = None 32 33 34 class LRUCache(): 35 """An implementation of Least Recently Used (LRU) Cache.""" 36 37 def __init__(self, capacity): 38 """Initializes a lru cache with the given capacity. 39 40 Args: 41 capacity: The capacity of the cache. 42 """ 43 assert capacity > 0, "capacity (%s) must be greater than zero." % capacity 44 self._first = None 45 self._last = None 46 self._dict = {} 47 self._capacity = capacity 48 49 def __setitem__(self, key, value): 50 if key in self._dict: 51 self.__delitem__(key) 52 if not self._first: 53 self._one_node(key, value) 54 return 55 if len(self._dict) >= self._capacity: 56 del self._dict[self._last.key] 57 if self._capacity == 1: 58 self._one_node(key, value) 59 return 60 self._last = self._last.next 61 self._last.prev = None 62 node = Node(key, value) 63 node.prev = self._first 64 self._first.next = node 65 self._first = node 66 self._dict[key] = node 67 68 def _one_node(self, key, value): 69 node = Node(key, value) 70 self._dict[key] = node 71 self._first = node 72 self._last = node 73 74 def __getitem__(self, key): 75 if not self._first: 76 raise KeyError(str(key)) 77 if self._first.key == key: 78 return self._first.value 79 80 if self._last.key == key: 81 next_last = self._last.next 82 next_last.prev = None 83 next_first = self._last 84 next_first.prev = self._first 85 next_first.next = None 86 self._first.next = next_first 87 self._first = next_first 88 self._last = next_last 89 return self._first.value 90 91 node = self._dict[key] 92 node.next.prev = node.prev 93 node.prev.next = node.next 94 node.prev = self._first 95 node.next = None 96 self._first.next = node 97 self._first = node 98 return self._first.value 99 100 def __delitem__(self, key): 101 node = self._dict[key] 102 del self._dict[key] 103 if self._first is self._last: 104 self._last = None 105 self._first = None 106 return 107 if self._first is node: 108 self._first = node.prev 109 self._first.next = None 110 return 111 if self._last is node: 112 self._last = node.next 113 self._last.prev = None 114 return 115 node.next.prev = node.prev 116 node.prev.next = node.next 117 118 def __len__(self): 119 return len(self._dict) 120 121 def __contains__(self, key): 122 return key in self._dict 123 124 def __iter__(self): 125 return iter(self._dict) 126 127 def items(self): 128 return [(key, node.value) for key, node in self._dict.items()] 129 130 def values(self): 131 return [node.value for node in self._dict.values()] 132 133 def keys(self): 134 return self._dict.keys() 135
