| # Copyright (C) 2011 Google Inc. All rights reserved. |
| # |
| # Redistribution and use in source and binary forms, with or without |
| # modification, are permitted provided that the following conditions are |
| # met: |
| # |
| # * Redistributions of source code must retain the above copyright |
| # notice, this list of conditions and the following disclaimer. |
| # * Redistributions in binary form must reproduce the above |
| # copyright notice, this list of conditions and the following disclaimer |
| # in the documentation and/or other materials provided with the |
| # distribution. |
| # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| |
| class Node(): |
| def __init__(self, key, value): |
| self.key = key |
| self.value = value |
| self.prev = None |
| self.next = None |
| |
| |
| class LRUCache(): |
| """An implementation of Least Recently Used (LRU) Cache.""" |
| |
| def __init__(self, capacity): |
| """Initializes a lru cache with the given capacity. |
| |
| Args: |
| capacity: The capacity of the cache. |
| """ |
| assert capacity > 0, "capacity (%s) must be greater than zero." % capacity |
| self._first = None |
| self._last = None |
| self._dict = {} |
| self._capacity = capacity |
| |
| def __setitem__(self, key, value): |
| if key in self._dict: |
| self.__delitem__(key) |
| if not self._first: |
| self._one_node(key, value) |
| return |
| if len(self._dict) >= self._capacity: |
| del self._dict[self._last.key] |
| if self._capacity == 1: |
| self._one_node(key, value) |
| return |
| self._last = self._last.next |
| self._last.prev = None |
| node = Node(key, value) |
| node.prev = self._first |
| self._first.next = node |
| self._first = node |
| self._dict[key] = node |
| |
| def _one_node(self, key, value): |
| node = Node(key, value) |
| self._dict[key] = node |
| self._first = node |
| self._last = node |
| |
| def __getitem__(self, key): |
| if not self._first: |
| raise KeyError(str(key)) |
| if self._first.key == key: |
| return self._first.value |
| |
| if self._last.key == key: |
| next_last = self._last.next |
| next_last.prev = None |
| next_first = self._last |
| next_first.prev = self._first |
| next_first.next = None |
| self._first.next = next_first |
| self._first = next_first |
| self._last = next_last |
| return self._first.value |
| |
| node = self._dict[key] |
| node.next.prev = node.prev |
| node.prev.next = node.next |
| node.prev = self._first |
| node.next = None |
| self._first.next = node |
| self._first = node |
| return self._first.value |
| |
| def __delitem__(self, key): |
| node = self._dict[key] |
| del self._dict[key] |
| if self._first is self._last: |
| self._last = None |
| self._first = None |
| return |
| if self._first is node: |
| self._first = node.prev |
| self._first.next = None |
| return |
| if self._last is node: |
| self._last = node.next |
| self._last.prev = None |
| return |
| node.next.prev = node.prev |
| node.prev.next = node.next |
| |
| def __len__(self): |
| return len(self._dict) |
| |
| def __contains__(self, key): |
| return key in self._dict |
| |
| def __iter__(self): |
| return iter(self._dict) |
| |
| def items(self): |
| return [(key, node.value) for key, node in self._dict.items()] |
| |
| def values(self): |
| return [node.value for node in self._dict.values()] |
| |
| def keys(self): |
| return self._dict.keys() |
