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

    def __str__(self):
        return '<{}:{}>'.format(self.key, self.value)

    def __repr__(self):
        return self.__str__()

class DoublyLinkedList():
    """ [head] <-> [] <-> [] <-> [tail]
    """

    def __init__(self):
        self.head = None
        self.tail = None
        self.current = self.head

    def append(self, node):
        if self.head is None:
            self.head = self.tail = node
        else:
            # repair the chain
            node.prev = self.tail
            self.tail.next = node
            # insert the new node
            self.tail = node

    def remove(self, node):
        cur = self.head
        while cur is not None:
            if cur == node:
                if cur.prev is not None:
                    cur.prev.next = cur.next
                    cur.next.prev = cur.prev
                else:
                    self.head = cur.next
                    cur.next.prev = None
            cur = cur.next

class LRUCache():
    def __init__(self, size=3):
        self.size = size
        self.cache = {}
        self.eviction_order = DoublyLinkedList()

    def get(self, key):
        node = self.cache[key]
        self.eviction_order.remove(node)
        self.eviction_order.append(node)
        return node

    def set(self, key, value):
        node = Node(key, value)
        if len(self.cache.keys()) < self.size:
            self.cache[key] = node
            self.eviction_order.append(node)

        elif len(self.cache.keys()) >= self.size:
            del self.cache[self.eviction_order.head.key]
            self.eviction_order.remove(self.eviction_order.head)
            self.eviction_order.append(node)
            self.cache[key] = node

        print(self.cache)

if __name__ == '__main__':
    cache = LRUCache()
    cache.set('a', 1)
    cache.set('b', 2)
    cache.set('c', 3)
    cache.get('a')
    cache.set('d', 4)