135 lines
4.3 KiB
Python
135 lines
4.3 KiB
Python
# 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()
|