Created
May 9, 2020 12:12
-
-
Save aliev/253364a1ceb9303e101784674317be47 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node: | |
def __init__(self, value, key=None, next=None, prev=None): | |
self.value = value | |
self.next = next | |
self.prev = prev | |
self.key = key | |
class LRUCache: | |
def __init__(self, capacity): | |
self.capacity = capacity | |
self.size = 0 | |
self.hash = {} | |
self.tail = None | |
self.head = None | |
self.key = None | |
def get(self, key): | |
node = self.hash.get(key, None) | |
if node is None: | |
return -1 | |
next = node.next | |
prev = node.prev | |
tail = self.tail | |
if next is not None: | |
if prev is None: | |
self.head = next | |
next.prev = None | |
else: | |
prev.next = next | |
next.prev = prev | |
node.prev = tail | |
tail.next = node | |
node.next = None | |
self.tail = node | |
return node.value | |
def _delete_tail(self, node): | |
prev = node.prev | |
prev.next = None | |
node.prev = None | |
self.tail = prev | |
def _delete_head(self, node): | |
next = node.next | |
next.prev = None | |
node.next = None | |
self.head = next | |
def _delete_node(self, node): | |
if node.prev == None: | |
self._delete_head(node) | |
elif node.next == None: | |
self._delete_tail(node) | |
else: | |
# Node in middle | |
prev = node.prev | |
next = node.next | |
prev.next = next | |
next.prev = prev | |
def put(self, key, value): | |
node = Node(value) | |
node.key = key | |
if self.tail is None and self.head is None: | |
self.tail = node | |
self.head = node | |
else: | |
tail = self.tail | |
tail.next = node | |
node.prev = tail | |
node.next = None | |
self.tail = node | |
key_exists = self.hash.get(key) | |
if key_exists: | |
self.size -= 1 | |
self._delete_node(key_exists) | |
self.hash[key] = node | |
self.size += 1 | |
if self.size > self.capacity and not key_exists: | |
head = self.head | |
self._delete_head(self.head) | |
del self.hash[head.key] | |
self.size -= 1 | |
if __name__ == "__main__": | |
def test_1(): | |
cache = LRUCache(2) | |
cache.put(2, 1) | |
cache.put(1, 1) | |
cache.put(2, 3) | |
cache.put(4, 1) | |
assert cache.get(1) == -1 | |
assert cache.get(2) == 3 | |
def test_2(): | |
cache = LRUCache(2) | |
cache.put(1, 1) | |
cache.put(2, 2) | |
assert cache.get(1) == 1 | |
cache.put(3, 3) | |
assert cache.get(2) == -1 | |
cache.put(4, 4) | |
assert cache.get(1) == -1 | |
assert cache.get(3) == 3 | |
assert cache.get(4) == 4 | |
def test_3(): | |
cache = LRUCache(10) | |
cache.put(10, 13) | |
cache.put(3, 17) | |
cache.put(6, 11) | |
cache.put(10, 5) | |
cache.put(9, 10) | |
assert cache.get(13) == -1 | |
cache.put(2, 19) | |
assert cache.get(2) == 19 | |
assert cache.get(3) == 17 | |
cache.put(5, 25) | |
assert cache.get(8) == -1 | |
cache.put(9, 22) | |
cache.put(5, 5) | |
cache.put(1, 30) | |
assert cache.get(11) == -1 | |
cache.put(9, 12) | |
assert cache.get(7) == -1 | |
assert cache.get(5) == 5 | |
assert cache.get(8) == -1 | |
assert cache.get(9) == 12 | |
cache.put(4, 30) | |
head = cache.head | |
cache.put(9, 3) | |
assert cache.get(9) == 3 | |
assert cache.get(10) == 5 | |
assert cache.get(10) == 5 | |
cache.put(6, 14) | |
cache.put(3, 1) | |
assert cache.get(3) == 1 | |
cache.put(10, 11) | |
assert cache.get(8) == - 1 | |
cache.put(2, 14) | |
assert cache.get(1) == 30 | |
assert cache.get(5) == 5 | |
assert cache.get(4) == 30 | |
test_1() | |
test_2() | |
test_3() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment