1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#!/usr/bin/env 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()
|
