<s> """<STR_LIT>""" <EOL> _null_key = object ( ) <EOL> class _LRUNode ( object ) : <EOL> """<STR_LIT>""" <EOL> __slots__ = ( '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT:key>' , '<STR_LIT:value>' , '<STR_LIT>' , '<STR_LIT:size>' ) <EOL> def __init__ ( self , key , value , cleanup = None ) : <EOL> self . prev = None <EOL> self . next_key = _null_key <EOL> self . key = key <EOL> self . value = value <EOL> self . cleanup = cleanup <EOL> self . size = None <EOL> def __repr__ ( self ) : <EOL> if self . prev is None : <EOL> prev_key = None <EOL> else : <EOL> prev_key = self . prev . key <EOL> return '<STR_LIT>' % ( self . __class__ . __name__ , self . key , <EOL> self . next_key , prev_key ) <EOL> def run_cleanup ( self ) : <EOL> if self . cleanup is not None : <EOL> self . cleanup ( self . key , self . value ) <EOL> self . cleanup = None <EOL> self . value = None <EOL> class LRUCache ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , max_cache = <NUM_LIT:100> , after_cleanup_count = None ) : <EOL> self . _cache = { } <EOL> self . _most_recently_used = None <EOL> self . _least_recently_used = None <EOL> self . _update_max_cache ( max_cache , after_cleanup_count ) <EOL> def __contains__ ( self , key ) : <EOL> return key in self . _cache <EOL> def __getitem__ ( self , key ) : <EOL> cache = self . _cache <EOL> node = cache [ key ] <EOL> mru = self . _most_recently_used <EOL> if node is mru : <EOL> return node . value <EOL> node_prev = node . prev <EOL> next_key = node . next_key <EOL> if next_key is _null_key : <EOL> self . _least_recently_used = node_prev <EOL> else : <EOL> node_next = cache [ next_key ] <EOL> node_next . prev = node_prev <EOL> node_prev . next_key = next_key <EOL> node . next_key = mru . key <EOL> mru . prev = node <EOL> self . _most_recently_used = node <EOL> node . prev = None <EOL> return node . value <EOL> def __len__ ( self ) : <EOL> return len ( self . _cache ) <EOL> def _walk_lru ( self ) : <EOL> """<STR_LIT>""" <EOL> node = self . _most_recently_used <EOL> if node is not None : <EOL> if node . prev is not None : <EOL> raise AssertionError ( '<STR_LIT>' <EOL> '<STR_LIT>' <EOL> '<STR_LIT>' % ( node , ) ) <EOL> while node is not None : <EOL> if node . next_key is _null_key : <EOL> if node is not self . _least_recently_used : <EOL> raise AssertionError ( '<STR_LIT>' <EOL> '<STR_LIT>' % ( node , ) ) <EOL> node_next = None <EOL> else : <EOL> node_next = self . _cache [ node . next_key ] <EOL> if node_next . prev is not node : <EOL> raise AssertionError ( '<STR_LIT>' <EOL> '<STR_LIT>' % ( node , ) ) <EOL> if node . prev is None : <EOL> if node is not self . _most_recently_used : <EOL> raise AssertionError ( '<STR_LIT>' <EOL> '<STR_LIT>' <EOL> % ( node , ) ) <EOL> else : <EOL> if node . prev . next_key != node . key : <EOL> raise AssertionError ( '<STR_LIT>' <EOL> '<STR_LIT>' % ( node , ) ) <EOL> yield node <EOL> node = node_next <EOL> def add ( self , key , value , cleanup = None ) : <EOL> """<STR_LIT>""" <EOL> if key is _null_key : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> if key in self . _cache : <EOL> node = self . _cache [ key ] <EOL> node . run_cleanup ( ) <EOL> node . value = value <EOL> node . cleanup = cleanup <EOL> else : <EOL> node = _LRUNode ( key , value , cleanup = cleanup ) <EOL> self . _cache [ key ] = node <EOL> self . _record_access ( node ) <EOL> if len ( self . _cache ) > self . _max_cache : <EOL> self . cleanup ( ) <EOL> def cache_size ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _max_cache <EOL> def get ( self , key , default = None ) : <EOL> node = self . _cache . get ( key , None ) <EOL> if node is None : <EOL> return default <EOL> self . _record_access ( node ) <EOL> return node . value <EOL> def keys ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _cache . keys ( ) <EOL> def items ( self ) : <EOL> """<STR_LIT>""" <EOL> return dict ( ( k , n . value ) for k , n in self . _cache . iteritems ( ) ) <EOL> def cleanup ( self ) : <EOL> """<STR_LIT>""" <EOL> while len ( self . _cache ) > self . _after_cleanup_count : <EOL> self . _remove_lru ( ) <EOL> def __setitem__ ( self , key , value ) : <EOL> """<STR_LIT>""" <EOL> self . add ( key , value , cleanup = None ) <EOL> def _record_access ( self , node ) : <EOL> """<STR_LIT>""" <EOL> if self . _most_recently_used is None : <EOL> self . _most_recently_used = node <EOL> self . _least_recently_used = node <EOL> return <EOL> elif node is self . _most_recently_used : <EOL> return <EOL> if node is self . _least_recently_used : <EOL> self . _least_recently_used = node . prev <EOL> if node . prev is not None : <EOL> node . prev . next_key = node . next_key <EOL> if node . next_key is not _null_key : <EOL> node_next = self . _cache [ node . next_key ] <EOL> node_next . prev = node . prev <EOL> node . next_key = self . _most_recently_used . key <EOL> self . _most_recently_used . prev = node <EOL> self . _most_recently_used = node <EOL> node . prev = None <EOL> def _remove_node ( self , node ) : <EOL> if node is self . _least_recently_used : <EOL> self . _least_recently_used = node . prev <EOL> self . _cache . pop ( node . key ) <EOL> if self . _least_recently_used is None : <EOL> self . _most_recently_used = None <EOL> node . run_cleanup ( ) <EOL> if node . prev is not None : <EOL> node . prev . next_key = node . next_key <EOL> if node . next_key is not _null_key : <EOL> node_next = self . _cache [ node . next_key ] <EOL> node_next . prev = node . prev <EOL> node . prev = None <EOL> node . next_key = _null_key <EOL> def _remove_lru ( self ) : <EOL> """<STR_LIT>""" <EOL> self . _remove_node ( self . _least_recently_used ) <EOL> def clear ( self ) : <EOL> """<STR_LIT>""" <EOL> while self . _cache : <EOL> self . _remove_lru ( ) <EOL> def resize ( self , max_cache , after_cleanup_count = None ) : <EOL> """<STR_LIT>""" <EOL> self . _update_max_cache ( max_cache , <EOL> after_cleanup_count = after_cleanup_count ) <EOL> def _update_max_cache ( self , max_cache , after_cleanup_count = None ) : <EOL> self . _max_cache = max_cache <EOL> if after_cleanup_count is None : <EOL> self . _after_cleanup_count = self . _max_cache * <NUM_LIT:8> / <NUM_LIT:10> <EOL> else : <EOL> self . _after_cleanup_count = min ( after_cleanup_count , <EOL> self . _max_cache ) <EOL> self . cleanup ( ) <EOL> class LRUSizeCache ( LRUCache ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , max_size = <NUM_LIT> * <NUM_LIT> , after_cleanup_size = None , <EOL> compute_size = None ) : <EOL> """<STR_LIT>""" <EOL> self . _value_size = <NUM_LIT:0> <EOL> self . _compute_size = compute_size <EOL> if compute_size is None : <EOL> self . _compute_size = len <EOL> self . _update_max_size ( max_size , after_cleanup_size = after_cleanup_size ) <EOL> LRUCache . __init__ ( self , max_cache = max ( int ( max_size / <NUM_LIT> ) , <NUM_LIT:1> ) ) <EOL> def add ( self , key , value , cleanup = None ) : <EOL> """<STR_LIT>""" <EOL> if key is _null_key : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> node = self . _cache . get ( key , None ) <EOL> value_len = self . _compute_size ( value ) <EOL> if value_len >= self . _after_cleanup_size : <EOL> if node is not None : <EOL> self . _remove_node ( node ) <EOL> if cleanup is not None : <EOL> cleanup ( key , value ) <EOL> return <EOL> if node is None : <EOL> node = _LRUNode ( key , value , cleanup = cleanup ) <EOL> self . _cache [ key ] = node <EOL> else : <EOL> self . _value_size -= node . size <EOL> node . size = value_len <EOL> self . _value_size += value_len <EOL> self . _record_access ( node ) <EOL> if self . _value_size > self . _max_size : <EOL> self . cleanup ( ) <EOL> def cleanup ( self ) : <EOL> """<STR_LIT>""" <EOL> while self . _value_size > self . _after_cleanup_size : <EOL> self . _remove_lru ( ) <EOL> def _remove_node ( self , node ) : <EOL> self . _value_size -= node . size <EOL> LRUCache . _remove_node ( self , node ) <EOL> def resize ( self , max_size , after_cleanup_size = None ) : <EOL> """<STR_LIT>""" <EOL> self . _update_max_size ( max_size , after_cleanup_size = after_cleanup_size ) <EOL> max_cache = max ( int ( max_size / <NUM_LIT> ) , <NUM_LIT:1> ) <EOL> self . _update_max_cache ( max_cache ) <EOL> def _update_max_size ( self , max_size , after_cleanup_size = None ) : <EOL> self . _max_size = max_size <EOL> if after_cleanup_size is None : <EOL> self . _after_cleanup_size = self . _max_size * <NUM_LIT:8> / <NUM_LIT:10> <EOL> else : <EOL> self . _after_cleanup_size = min ( after_cleanup_size , self . _max_size ) </s>
