<s> """<STR_LIT>""" <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> import itertools <EOL> from collections import deque <EOL> try : <EOL> from threading import RLock <EOL> except Exception : <EOL> class RLock ( object ) : <EOL> '<STR_LIT>' <EOL> def __enter__ ( self ) : <EOL> pass <EOL> def __exit__ ( self , exctype , excinst , exctb ) : <EOL> pass <EOL> try : <EOL> from typeutils import make_sentinel <EOL> _MISSING = make_sentinel ( var_name = '<STR_LIT>' ) <EOL> _KWARG_MARK = make_sentinel ( var_name = '<STR_LIT>' ) <EOL> except ImportError : <EOL> _MISSING = object ( ) <EOL> _KWARG_MARK = object ( ) <EOL> try : <EOL> xrange <EOL> except NameError : <EOL> xrange = range <EOL> PREV , NEXT , KEY , VALUE = range ( <NUM_LIT:4> ) <EOL> DEFAULT_MAX_SIZE = <NUM_LIT> <EOL> class LRU ( dict ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , max_size = DEFAULT_MAX_SIZE , values = None , <EOL> on_miss = None ) : <EOL> if max_size <= <NUM_LIT:0> : <EOL> raise ValueError ( '<STR_LIT>' % max_size ) <EOL> self . hit_count = self . miss_count = self . soft_miss_count = <NUM_LIT:0> <EOL> self . max_size = max_size <EOL> self . _lock = RLock ( ) <EOL> self . _init_ll ( ) <EOL> if on_miss is not None and not callable ( on_miss ) : <EOL> raise TypeError ( '<STR_LIT>' <EOL> '<STR_LIT>' % on_miss ) <EOL> self . on_miss = on_miss <EOL> if values : <EOL> self . update ( values ) <EOL> def _init_ll ( self ) : <EOL> anchor = [ ] <EOL> anchor [ : ] = [ anchor , anchor , _MISSING , _MISSING ] <EOL> self . _link_lookup = { } <EOL> self . _anchor = anchor <EOL> def _print_ll ( self ) : <EOL> link = self . _anchor <EOL> print ( '<STR_LIT>' ) <EOL> while True : <EOL> print ( link [ KEY ] , link [ VALUE ] ) <EOL> link = link [ NEXT ] <EOL> if link is self . _anchor : <EOL> break <EOL> print ( '<STR_LIT>' ) <EOL> return <EOL> def _get_link_and_move_to_front_of_ll ( self , key ) : <EOL> newest = self . _link_lookup [ key ] <EOL> newest [ PREV ] [ NEXT ] = newest [ NEXT ] <EOL> newest [ NEXT ] [ PREV ] = newest [ PREV ] <EOL> anchor = self . _anchor <EOL> second_newest = anchor [ PREV ] <EOL> second_newest [ NEXT ] = anchor [ PREV ] = newest <EOL> newest [ PREV ] = second_newest <EOL> newest [ NEXT ] = anchor <EOL> return newest <EOL> def _set_key_and_add_to_front_of_ll ( self , key , value ) : <EOL> anchor = self . _anchor <EOL> second_newest = anchor [ PREV ] <EOL> newest = [ second_newest , anchor , key , value ] <EOL> second_newest [ NEXT ] = anchor [ PREV ] = newest <EOL> self . _link_lookup [ key ] = newest <EOL> def _set_key_and_evict_last_in_ll ( self , key , value ) : <EOL> oldanchor = self . _anchor <EOL> oldanchor [ KEY ] = key <EOL> oldanchor [ VALUE ] = value <EOL> self . _anchor = anchor = oldanchor [ NEXT ] <EOL> evicted = anchor [ KEY ] <EOL> anchor [ KEY ] = anchor [ VALUE ] = _MISSING <EOL> del self . _link_lookup [ evicted ] <EOL> self . _link_lookup [ key ] = oldanchor <EOL> return evicted <EOL> def _remove_from_ll ( self , key ) : <EOL> link = self . _link_lookup . pop ( key ) <EOL> link [ PREV ] [ NEXT ] = link [ NEXT ] <EOL> link [ NEXT ] [ PREV ] = link [ PREV ] <EOL> def __setitem__ ( self , key , value ) : <EOL> with self . _lock : <EOL> try : <EOL> link = self . _get_link_and_move_to_front_of_ll ( key ) <EOL> except KeyError : <EOL> if len ( self ) < self . max_size : <EOL> self . _set_key_and_add_to_front_of_ll ( key , value ) <EOL> else : <EOL> evicted = self . _set_key_and_evict_last_in_ll ( key , value ) <EOL> super ( LRU , self ) . __delitem__ ( evicted ) <EOL> super ( LRU , self ) . __setitem__ ( key , value ) <EOL> else : <EOL> link [ VALUE ] = value <EOL> def __getitem__ ( self , key ) : <EOL> with self . _lock : <EOL> try : <EOL> link = self . _get_link_and_move_to_front_of_ll ( key ) <EOL> except KeyError : <EOL> self . miss_count += <NUM_LIT:1> <EOL> if not self . on_miss : <EOL> raise <EOL> ret = self [ key ] = self . on_miss ( key ) <EOL> return ret <EOL> self . hit_count += <NUM_LIT:1> <EOL> return link [ VALUE ] <EOL> def get ( self , key , default = None ) : <EOL> try : <EOL> return self [ key ] <EOL> except KeyError : <EOL> self . soft_miss_count += <NUM_LIT:1> <EOL> return default <EOL> def __delitem__ ( self , key ) : <EOL> with self . _lock : <EOL> super ( LRU , self ) . __delitem__ ( key ) <EOL> self . _remove_from_ll ( key ) <EOL> def pop ( self , key , default = _MISSING ) : <EOL> with self . _lock : <EOL> try : <EOL> ret = super ( LRU , self ) . pop ( key ) <EOL> except KeyError : <EOL> if default is _MISSING : <EOL> raise <EOL> ret = default <EOL> else : <EOL> self . _remove_from_ll ( key ) <EOL> return ret <EOL> def popitem ( self ) : <EOL> with self . _lock : <EOL> item = super ( LRU , self ) . popitem ( ) <EOL> self . _remove_from_ll ( item [ <NUM_LIT:0> ] ) <EOL> return item <EOL> def clear ( self ) : <EOL> with self . _lock : <EOL> super ( LRU , self ) . clear ( ) <EOL> self . _init_ll ( ) <EOL> def copy ( self ) : <EOL> return self . __class__ ( max_size = self . max_size , values = self ) <EOL> def setdefault ( self , key , default = None ) : <EOL> with self . _lock : <EOL> try : <EOL> return self [ key ] <EOL> except KeyError : <EOL> self . soft_miss_count += <NUM_LIT:1> <EOL> self [ key ] = default <EOL> return default <EOL> def update ( self , E , ** F ) : <EOL> with self . _lock : <EOL> if E is self : <EOL> return <EOL> setitem = self . __setitem__ <EOL> if callable ( getattr ( E , '<STR_LIT>' , None ) ) : <EOL> for k in E . keys ( ) : <EOL> setitem ( k , E [ k ] ) <EOL> else : <EOL> for k , v in E : <EOL> setitem ( k , v ) <EOL> for k in F : <EOL> setitem ( k , F [ k ] ) <EOL> return <EOL> def __eq__ ( self , other ) : <EOL> with self . _lock : <EOL> if self is other : <EOL> return True <EOL> if len ( other ) != len ( self ) : <EOL> return False <EOL> if not isinstance ( other , LRU ) : <EOL> return other == self <EOL> return super ( LRU , self ) . __eq__ ( other ) <EOL> def __ne__ ( self , other ) : <EOL> return not ( self == other ) <EOL> def __repr__ ( self ) : <EOL> cn = self . __class__ . __name__ <EOL> val_map = super ( LRU , self ) . __repr__ ( ) <EOL> return ( '<STR_LIT>' <EOL> % ( cn , self . max_size , self . on_miss , val_map ) ) <EOL> class LRI ( dict ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , max_size = DEFAULT_MAX_SIZE , values = None , <EOL> on_miss = None ) : <EOL> super ( LRI , self ) . __init__ ( ) <EOL> self . hit_count = self . miss_count = self . soft_miss_count = <NUM_LIT:0> <EOL> self . max_size = max_size <EOL> self . on_miss = on_miss <EOL> self . _queue = deque ( ) <EOL> if values : <EOL> self . update ( values ) <EOL> def __setitem__ ( self , key , value ) : <EOL> if len ( self ) >= self . max_size : <EOL> old = self . _queue . popleft ( ) <EOL> del self [ old ] <EOL> super ( LRI , self ) . __setitem__ ( key , value ) <EOL> self . _queue . append ( key ) <EOL> def update ( self , E , ** F ) : <EOL> if E is self : <EOL> return <EOL> setitem = self . __setitem__ <EOL> if callable ( getattr ( E , '<STR_LIT>' , None ) ) : <EOL> for k in E . keys ( ) : <EOL> setitem ( k , E [ k ] ) <EOL> else : <EOL> for k , v in E : <EOL> setitem ( k , v ) <EOL> for k in F : <EOL> setitem ( k , F [ k ] ) <EOL> return <EOL> def copy ( self ) : <EOL> return self . __class__ ( max_size = self . max_size , values = self ) <EOL> def clear ( self ) : <EOL> self . _queue . clear ( ) <EOL> super ( LRI , self ) . clear ( ) <EOL> def __getitem__ ( self , key ) : <EOL> try : <EOL> ret = super ( LRI , self ) . __getitem__ ( key ) <EOL> except KeyError : <EOL> self . miss_count += <NUM_LIT:1> <EOL> if not self . on_miss : <EOL> raise <EOL> ret = self [ key ] = self . on_miss ( key ) <EOL> return ret <EOL> self . hit_count += <NUM_LIT:1> <EOL> return ret <EOL> def get ( self , key , default = None ) : <EOL> try : <EOL> return self [ key ] <EOL> except KeyError : <EOL> self . soft_miss_count += <NUM_LIT:1> <EOL> return default <EOL> def setdefault ( self , key , default = None ) : <EOL> try : <EOL> return self [ key ] <EOL> except KeyError : <EOL> self . soft_miss_count += <NUM_LIT:1> <EOL> self [ key ] = default <EOL> return default <EOL> class _HashedKey ( list ) : <EOL> """<STR_LIT>""" <EOL> __slots__ = '<STR_LIT>' <EOL> def __init__ ( self , key ) : <EOL> self [ : ] = key <EOL> self . hash_value = hash ( tuple ( key ) ) <EOL> def __hash__ ( self ) : <EOL> return self . hash_value <EOL> def _make_cache_key ( args , kwargs , typed = False , kwarg_mark = _KWARG_MARK , <EOL> fasttypes = frozenset ( [ int , str , frozenset , type ( None ) ] ) ) : <EOL> """<STR_LIT>""" <EOL> key = list ( args ) <EOL> if kwargs : <EOL> sorted_items = sorted ( kwargs . items ( ) ) <EOL> key . append ( kwarg_mark ) <EOL> key . extend ( sorted_items ) <EOL> if typed : <EOL> key . extend ( [ type ( v ) for v in args ] ) <EOL> if kwargs : <EOL> key . extend ( [ type ( v ) for k , v in sorted_items ] ) <EOL> elif len ( key ) == <NUM_LIT:1> and type ( key [ <NUM_LIT:0> ] ) in fasttypes : <EOL> return key [ <NUM_LIT:0> ] <EOL> return _HashedKey ( key ) <EOL> class CachedFunction ( object ) : <EOL> def __init__ ( self , func , cache , typed = False ) : <EOL> self . func = func <EOL> self . cache = cache <EOL> self . typed = typed <EOL> def __call__ ( self , * args , ** kwargs ) : <EOL> key = _make_cache_key ( args , kwargs , typed = self . typed ) <EOL> try : <EOL> ret = self . cache [ key ] <EOL> except KeyError : <EOL> ret = self . cache [ key ] = self . func ( * args , ** kwargs ) <EOL> return ret <EOL> def __repr__ ( self ) : <EOL> cn = self . __class__ . __name__ <EOL> if self . typed : <EOL> return "<STR_LIT>" % ( cn , self . func , self . typed ) <EOL> return "<STR_LIT>" % ( cn , self . func ) <EOL> def cached ( cache , typed = False ) : <EOL> """<STR_LIT>""" <EOL> def cached_func_decorator ( func ) : <EOL> return CachedFunction ( func , cache , typed = typed ) <EOL> return cached_func_decorator <EOL> class ThresholdCounter ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , threshold = <NUM_LIT> ) : <EOL> if not <NUM_LIT:0> < threshold < <NUM_LIT:1> : <EOL> raise ValueError ( '<STR_LIT>' <EOL> % threshold ) <EOL> self . total = <NUM_LIT:0> <EOL> self . _count_map = { } <EOL> self . _threshold = threshold <EOL> self . _thresh_count = int ( <NUM_LIT:1> / threshold ) <EOL> self . _cur_bucket = <NUM_LIT:1> <EOL> @ property <EOL> def threshold ( self ) : <EOL> return self . _threshold <EOL> def add ( self , key ) : <EOL> """<STR_LIT>""" <EOL> self . total += <NUM_LIT:1> <EOL> try : <EOL> self . _count_map [ key ] [ <NUM_LIT:0> ] += <NUM_LIT:1> <EOL> except KeyError : <EOL> self . _count_map [ key ] = [ <NUM_LIT:1> , self . _cur_bucket - <NUM_LIT:1> ] <EOL> if self . total % self . _thresh_count == <NUM_LIT:0> : <EOL> self . _count_map = dict ( [ ( k , v ) for k , v in self . _count_map . items ( ) <EOL> if sum ( v ) > self . _cur_bucket ] ) <EOL> self . _cur_bucket += <NUM_LIT:1> <EOL> return <EOL> def elements ( self ) : <EOL> """<STR_LIT>""" <EOL> repeaters = itertools . starmap ( itertools . repeat , self . iteritems ( ) ) <EOL> return itertools . chain . from_iterable ( repeaters ) <EOL> def most_common ( self , n = None ) : <EOL> """<STR_LIT>""" <EOL> if n <= <NUM_LIT:0> : <EOL> return [ ] <EOL> ret = sorted ( self . iteritems ( ) , key = lambda x : x [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] , reverse = True ) <EOL> if n is None or n >= len ( ret ) : <EOL> return ret <EOL> return ret [ : n ] <EOL> def get_common_count ( self ) : <EOL> """<STR_LIT>""" <EOL> return sum ( [ count for count , _ in self . _count_map . itervalues ( ) ] ) <EOL> def get_uncommon_count ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . total - self . get_common_count ( ) <EOL> def get_commonality ( self ) : <EOL> """<STR_LIT>""" <EOL> return float ( self . get_common_count ( ) ) / self . total <EOL> def __getitem__ ( self , key ) : <EOL> return self . _count_map [ key ] [ <NUM_LIT:0> ] <EOL> def __len__ ( self ) : <EOL> return len ( self . _count_map ) <EOL> def __contains__ ( self , key ) : <EOL> return key in self . _count_map <EOL> def iterkeys ( self ) : <EOL> return iter ( self . _count_map ) <EOL> def keys ( self ) : <EOL> return list ( self . iterkeys ( ) ) <EOL> def itervalues ( self ) : <EOL> count_map = self . _count_map <EOL> for k in count_map : <EOL> yield count_map [ k ] [ <NUM_LIT:0> ] <EOL> def values ( self ) : <EOL> return list ( self . itervalues ( ) ) <EOL> def iteritems ( self ) : <EOL> count_map = self . _count_map <EOL> for k in count_map : <EOL> yield ( k , count_map [ k ] [ <NUM_LIT:0> ] ) <EOL> def items ( self ) : <EOL> return list ( self . iteritems ( ) ) <EOL> def get ( self , key , default = <NUM_LIT:0> ) : <EOL> "<STR_LIT>" <EOL> try : <EOL> return self [ key ] <EOL> except KeyError : <EOL> return default <EOL> def update ( self , iterable , ** kwargs ) : <EOL> """<STR_LIT>""" <EOL> if iterable is not None : <EOL> if callable ( getattr ( iterable , '<STR_LIT>' , None ) ) : <EOL> for key , count in iterable . iteritems ( ) : <EOL> for i in xrange ( count ) : <EOL> self . add ( key ) <EOL> else : <EOL> for key in iterable : <EOL> self . add ( key ) <EOL> if kwargs : <EOL> self . update ( kwargs ) </s>
