"""Original bounded access-order cache versus independent list model and FIFO."""
from collections import OrderedDict
from itertools import product
import json
class Cache:
 def __init__(self,capacity,lru=True):
  if type(capacity) is not int or not 0<=capacity<=8:raise ValueError('capacity0..8')
  self.capacity=capacity;self.lru=lru;self.data=OrderedDict()
 def access(self,key,value):
  if type(key) is not str or len(key)!=1:raise ValueError('single-codepoint key')
  hit=key in self.data;evicted=None
  if hit:
   result=self.data[key]
   if self.lru:self.data.move_to_end(key)
  else:
   result=value
   if self.capacity:
    self.data[key]=value
    if len(self.data)>self.capacity:evicted=self.data.popitem(last=False)[0]
  return {'key':key,'hit':hit,'value':result,'evicted':evicted,'oldest_to_newest':list(self.data)}
 def put(self,key,value):
  if type(key) is not str or len(key)!=1:raise ValueError('single-codepoint key')
  if not self.capacity:return
  self.data[key]=value
  if self.lru:self.data.move_to_end(key)
  if len(self.data)>self.capacity:self.data.popitem(last=False)
def list_oracle(seq,cap):
 order=[];hits=[]
 for x in seq:
  hit=x in order;hits.append(hit)
  if hit:order.remove(x)
  if cap:
   order.append(x)
   if len(order)>cap:order.pop(0)
 return hits,order
def demo():
 seq='ABACB';lru=Cache(2);fifo=Cache(2,False);a=[lru.access(x,x.lower()) for x in seq];b=[fifo.access(x,x.lower()) for x in seq]
 assert sum(x['hit'] for x in a)==1 and sum(x['hit'] for x in b)==2
 checks=0
 for n in range(7):
  for seq2 in product('ABC',repeat=n):
   for cap in [0,1,2,3]:
    c=Cache(cap);r=[c.access(x,None) for x in seq2];h,o=list_oracle(seq2,cap);assert [x['hit'] for x in r]==h and list(c.data)==o;checks+=1
 c=Cache(2);c.put('A',None);c.put('B',2);n=c.access('A','would be miss');assert n['hit'] and n['value'] is None
 c.put('B',9);assert list(c.data)==['A','B'] and c.data['B']==9
 rejected=[]
 for cap in [True,-1,9,1.5]:
  try:Cache(cap)
  except ValueError:rejected.append(repr(cap))
  else:raise AssertionError('expected rejection')
 return {'requests':'ABACB','capacity':2,'lru_trace':a,'fifo_trace':b,'lru_hits':1,'fifo_hits':2,'all_short_sequence_capacity_checks':checks,'cached_None_read':n,'overwrite_B9_order':list(c.data),'invalid_capacity_rejected':rejected,'scope':'no TTL, authorization, concurrency, persistence, API or real product cache'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))