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
26class 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
34class 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