Ordered Dictionary

from collections import OrderedDict

Make Ordered Dict

my_ord_dict = OrderedDict.fromkeys('abcde')

Pop Item

The popitem() method for ordered dictionaries returns and removes a (key, value) pair. The pairs are returned in LIFO order if last is true or FIFO order if false.

my_ord_dict.popitem(last=True)

Move to End

Move an existing key to either end of an ordered dictionary. The item is moved to the right end if last is true (the default) or to the beginning if last is false. Raises KeyError if the key does not exist

my_ord_dict.move_to_end(key, last=True)¶
> my_ord_dict.move_to_end('b')
> ''.join(my_ord_dict.keys())
'acdeb'
> my_ord_dict.move_to_end('b', last=False)
> ''.join(my_ord_dict.keys())
'bacde'

LRU

class LRU(OrderedDict):
    'Limit size, evicting the least recently looked-up key when full'

    def __init__(self, maxsize=128, /, *args, **kwds):
        self.maxsize = maxsize
        super().__init__(*args, **kwds)

    def __getitem__(self, key):
        value = super().__getitem__(key)
        self.move_to_end(key)
        return value

    def __setitem__(self, key, value):
        if key in self:
            self.move_to_end(key)
        super().__setitem__(key, value)
        if len(self) > self.maxsize:
            oldest = next(iter(self))
            del self[oldest]