#!/usr/bin/env python
# coding: utf-8

'''
>>> lru=LRU()
>>> lru.put('a', 'aaaa')
>>> lru.put('b', 'bbb')
>>> lru.put('c', 'ccc')
>>> lru.get('a')
>>> lru=LRU()
>>> lru.put('a', 'aaaa')
>>> lru.put('b', 'bbb')
>>> lru.get('a')
'aaaa'
>>> lru.put('c', 'ccc')
>>> lru.get('b')
'''

class LRU:
    '''LRUキャッシュクラス'''
    _max_len=2
    _order=[]
    _stack={}

    def put(self, key, value):
        # キーがあったら並び順だけ入れ替える
        if self._stack.has_key(key):
            self._order.pop(self._order.index(key))
            self._order.append(key)
        else:
            # キーが無ければ追加
            self._order.append(key)
            self._stack[key]=value

        # 並び順の長さがmax_lenを超えたら先頭を消す
        if len(self._order) > self._max_len:
            nkey=self._order.pop(0)
            del(self._stack[nkey])
    
    def get(self, key):
        try:
            # スタックから値を取り出して返す
            ret=self._stack[key]
            
            # キーを取り出して最後尾に放り込む
            self._order.pop(self._order.index(key))
            self._order.append(key)

        except KeyError:
            # キーが無ければNoneを返す
            return None

        return ret

def _test():
    '''テスト起動用の関数'''
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    _test()