======Least Recently Used Cache======

**LRU**

Good explanation at [[https://www.geeksforgeeks.org/lru-cache-implementation/|LRU Cache Implementation]]

From Data Algo class:

<code>

"""
Implement an LRU cache

The trick here is to use an OrderdDict. When adding a value delete
it from the dict if it exists, then put it on so it is at the end 
of the dict. If over capacity then remove the first value and
add the new value, thus removing the least used.
"""
from collections import OrderedDict

class LRU_Cache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    # Attemt to get a value. If this value is not in the 
    # cache, add it. If this value is in the cache, pop it 
    # (which gets the value and removed it from the dict)
    # and add it back to the dict, placing it last. This
    # will allow up to effectively know which is the last used.
    def get(self, key):
        
        """ Retrieve item from provided key. Return -1 if nonexistent. """

        #Try to remove it and then put it back on
        try:
            value = self.cache.pop(key)
            self.cache[key] = value
            return value
        except KeyError:
            # Exception thrown if not in cache
            return -1

    def set(self, key, value):

        """ Set the value if the key is not present in the cache. 
        If the cache is at capacity remove the oldest item.
        """

        # Check to see if the value exists. If not, add it .
        # and also check the capacity
        if self.get(key) == -1:
            # Check to see if adding this item will overflow the capacity
            # If os, remove the least recently used
            if len(self.cache) == self.capacity:
                self.cache.popitem(last=False)

        # Now add or replace the value for the key
        self.cache[key] = value

    def __str__(self):

        string = ""
        for value in self.cache.values():
            string += str(value) + ","

        return string[:-1] # remove last comma

def test(cache, value, expected_answer):
    if len(cache.cache) == 0:
        print("Testing seaching for value in empty cache")
    else:
        print("Testing value %d in %s" % (value, str(cache)))
    #print("Answer should be %d" % expected_answer)
    answer = our_cache.get(value)
    if answer != expected_answer:
        print("Error: our_cache.get(%d) should = %d, got %d" %(value, expected_answer, answer))

# Test 1, test simple get
our_cache = LRU_Cache(5)
our_cache.set(1, 1);
our_cache.set(2, 2);
our_cache.set(3, 3);
our_cache.set(4, 4);
test(our_cache, 1, 1)

# Test 2
our_cache = LRU_Cache(1)
our_cache.set(1, 1);
test(our_cache, 1, 1)

# Test 3, value not in cache
test(our_cache, 9, -1) # Not in cache

# Test edge case: cache capacity only 1, but more than one added
our_cache = LRU_Cache(1)
our_cache.set(1, 1);
our_cache.set(2, 2);
our_cache.set(3, 3);
our_cache.set(4, 4);
test(our_cache, 4, 4)

# Test edge case: capacity 3, first added value should not exist
our_cache = LRU_Cache(3)
our_cache.set(1, 1);
our_cache.set(2, 2);
our_cache.set(3, 3);
our_cache.set(4, 4);
test(our_cache, 1, -1)

# Edge case: empty cache
our_cache = LRU_Cache(3)
test(our_cache, 1, -1)
</code>