p_1_LRU_Cache.py

'''
Least Recently Used Cache
We have briefly discussed caching as part of a practice problem while studying hash maps.

The lookup operation (i.e., get()) and put() / set() is supposed to be fast for a cache memory.

While doing the get() operation, if the entry is found in the cache, it is known as a cache hit. 
If, however, the entry is not found, it is known as a cache miss.

When designing a cache, we also place an upper bound on the size of the cache. 
If the cache is full and we want to add a new entry to the cache, 
we use some criteria to remove an element. 
After removing an element, we use the put() operation to insert the new element. 
The remove operation should also be fast.

For our first problem, the goal will be to design a data structure known 
as a Least Recently Used (LRU) cache. 
An LRU cache is a type of cache in which we remove the least recently used entry 
when the cache memory reaches its limit. 
For the current problem, consider both get and set operations as an use operation.

Your job is to use an appropriate data structure(s) to implement the cache.

In case of a cache hit, your get() operation should return the appropriate value.
In case of a cache miss, your get() should return -1.
While putting an element in the cache, your put() / set() operation must insert the element. If the cache is full, you must write code that removes the least recently used entry first and then insert the element.
All operations must take O(1) time.

For the current problem, you can consider the size of cache = 5.

Here is some boiler plate code and some example test cases to get you started on this problem:
'''
class Node:

    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRU_Cache:

    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = dict()
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.value
        return - 1

    def set(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            node = self.head.next
            self._remove(node)
            del self.cache[node.key]

    def _remove(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add(self, node):
        prev_node = self.tail.prev
        prev_node.next = node
        self.tail.prev = node
        node.prev = prev_node
        node.next = self.tail

our_cache = LRU_Cache(5)

our_cache.set(1, 1)
print('Current Cache: {}'.format(our_cache.cache))
our_cache.set(2, 2)
print('Current Cache: {}'.format(our_cache.cache))
our_cache.set(3, 3)
print('Current Cache: {}'.format(our_cache.cache))
our_cache.set(4, 4)
print('Current Cache: {}'.format(our_cache.cache))

print(our_cache.get(1))    # returns 1
print(our_cache.get(2))    # returns 2
print(our_cache.get(9))    # returns -1 because 9 is not present in the cache

our_cache.set(5, 5)
print(our_cache.cache)
our_cache.set(6, 6)
print(our_cache.cache)

print(our_cache.get(3))    # returns -1 because the cache reached its capacity and 
                    # 3 was the least recently used entry 

# Test for cache capacity 0. Should return -1 
cache = LRU_Cache(0)
cache.set(1, 1)
assert cache.get(1) == -1
cache.set(2, 2)
assert cache.get(2) == -1

# Test for cache capacity 3
cache = LRU_Cache(3)
cache.set(1, 1)
cache.set(2, 2)
cache.set(3, 3)
assert cache.get(3) == 3
assert cache.get(2) == 2
assert cache.get(1) == 1

# Test for cache capacity 7
cache = LRU_Cache(7)
cache.set(1, 10)
cache.set(2, 20)
cache.set(5, 50)
assert cache.get(5) == 50
assert cache.get(2) == 20
assert cache.get(1) == 10