<s> """<STR_LIT>""" <EOL> __docformat__ = "<STR_LIT>" <EOL> import sys <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' ] <EOL> class OrderedDict ( dict ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , * args , ** kw ) : <EOL> dict . __init__ ( self , * args , ** kw ) <EOL> self . __orderedKeys = [ ] <EOL> self . __keyPositions = { } <EOL> def __setitem__ ( self , key , value ) : <EOL> try : <EOL> index = self . __keyPositions [ key ] <EOL> except KeyError : <EOL> index = len ( self . __orderedKeys ) <EOL> self . __orderedKeys += [ key ] <EOL> self . __keyPositions [ key ] = index <EOL> dict . __setitem__ ( self , key , value ) <EOL> def __delitem__ ( self , key ) : <EOL> index = self . __keyPositions [ key ] <EOL> del self . __orderedKeys [ index ] <EOL> del self . __keyPositions [ key ] <EOL> dict . __delitem__ ( self , key ) <EOL> def __iter__ ( self ) : <EOL> for key in self . __orderedKeys : <EOL> yield key <EOL> def __str__ ( self ) : <EOL> s = '<STR_LIT:{>' <EOL> sep = '<STR_LIT>' <EOL> for k , v in self . iteritems ( ) : <EOL> s += sep <EOL> if type ( k ) == str : <EOL> s += "<STR_LIT>" % k <EOL> else : <EOL> s += str ( k ) <EOL> s += '<STR_LIT>' <EOL> if type ( v ) == str : <EOL> s += "<STR_LIT>" % v <EOL> else : <EOL> s += str ( v ) <EOL> sep = '<STR_LIT:U+002CU+0020>' <EOL> s += '<STR_LIT:}>' <EOL> return s <EOL> def keys ( self ) : <EOL> return self . __orderedKeys <EOL> def items ( self ) : <EOL> return [ ( key , self [ key ] ) for key in self . __orderedKeys ] <EOL> def values ( self ) : <EOL> return [ self [ key ] for key in self . __orderedKeys ] <EOL> def iteritems ( self ) : <EOL> for key in self . __orderedKeys : <EOL> yield ( key , self [ key ] ) <EOL> def iterkeys ( self ) : <EOL> for key in self . __orderedKeys : <EOL> yield key <EOL> def update ( self , d ) : <EOL> for key , value in d . iteritems ( ) : <EOL> self [ key ] = value <EOL> def pop ( self , key , default = None ) : <EOL> try : <EOL> result = self [ key ] <EOL> del self [ key ] <EOL> except KeyError : <EOL> if not default : <EOL> raise <EOL> result = default <EOL> return result <EOL> def popitem ( self ) : <EOL> key , value = dict . popitem ( self ) <EOL> del self [ key ] <EOL> return ( key , value ) <EOL> class LRUListEntry ( object ) : <EOL> def __init__ ( self , key , value ) : <EOL> self . key = key <EOL> self . value = value <EOL> self . next = None <EOL> self . prev = None <EOL> def __hash__ ( self ) : <EOL> return self . key . __hash__ ( ) <EOL> def __str__ ( self ) : <EOL> return '<STR_LIT>' % ( self . key , self . value ) <EOL> def __repr__ ( self ) : <EOL> return str ( self ) <EOL> class LRUList ( object ) : <EOL> def __init__ ( self ) : <EOL> self . head = self . tail = None <EOL> self . size = <NUM_LIT:0> <EOL> def __del__ ( self ) : <EOL> self . clear ( ) <EOL> def __str__ ( self ) : <EOL> return '<STR_LIT:[>' + '<STR_LIT:U+002CU+0020>' . join ( [ str ( tup ) for tup in self . items ( ) ] ) + '<STR_LIT:]>' <EOL> def __repr__ ( self ) : <EOL> return self . __class__ . __name__ + '<STR_LIT::>' + str ( self ) <EOL> def __len__ ( self ) : <EOL> return self . size <EOL> def __iter__ ( self ) : <EOL> entry = self . head <EOL> while entry : <EOL> yield entry . key <EOL> entry = entry . next <EOL> def keys ( self ) : <EOL> return [ k for k in self ] <EOL> def items ( self ) : <EOL> result = [ ] <EOL> for key , value in self . iteritems ( ) : <EOL> result . append ( ( key , value ) ) <EOL> return result <EOL> def values ( self ) : <EOL> result = [ ] <EOL> for key , value in self . iteritems ( ) : <EOL> result . append ( value ) <EOL> return result <EOL> def iteritems ( self ) : <EOL> entry = self . head <EOL> while entry : <EOL> yield ( entry . key , entry . value ) <EOL> entry = entry . next <EOL> def iterkeys ( self ) : <EOL> self . __iter__ ( ) <EOL> def itervalues ( self ) : <EOL> entry = self . head <EOL> while entry : <EOL> yield entry . value <EOL> entry = entry . next <EOL> def clear ( self ) : <EOL> while self . head : <EOL> cur = self . head <EOL> next = self . head . next <EOL> cur . next = cur . previous = cur . key = cur . value = None <EOL> self . head = next <EOL> self . tail = None <EOL> self . size = <NUM_LIT:0> <EOL> def remove ( self , entry ) : <EOL> if entry . next : <EOL> entry . next . previous = entry . previous <EOL> if entry . previous : <EOL> entry . previous . next = entry . next <EOL> if entry == self . head : <EOL> self . head = entry . next <EOL> if entry == self . tail : <EOL> self . tail = entry . previous <EOL> entry . next = entry . previous = None <EOL> self . size -= <NUM_LIT:1> <EOL> assert self . size >= <NUM_LIT:0> <EOL> def remove_tail ( self ) : <EOL> result = self . tail <EOL> if result : <EOL> self . remove ( result ) <EOL> return result <EOL> def add_to_head ( self , entry ) : <EOL> if type ( entry ) == tuple : <EOL> key , value = entry <EOL> entry = LRUListEntry ( key , value ) <EOL> else : <EOL> entry . next = entry . previous = None <EOL> if self . head : <EOL> assert self . tail <EOL> entry . next = self . head <EOL> self . head . previous = entry <EOL> self . head = entry <EOL> else : <EOL> assert not self . tail <EOL> self . head = self . tail = entry <EOL> self . size += <NUM_LIT:1> <EOL> def move_to_head ( self , entry ) : <EOL> self . remove ( entry ) <EOL> self . add_to_head ( entry ) <EOL> class LRUDict ( dict ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , * args , ** kw ) : <EOL> """<STR_LIT>""" <EOL> if kw . has_key ( '<STR_LIT>' ) : <EOL> self . __max_capacity = kw [ '<STR_LIT>' ] <EOL> del kw [ '<STR_LIT>' ] <EOL> else : <EOL> self . __max_capacity = sys . maxint <EOL> dict . __init__ ( self ) <EOL> self . __removal_listeners = { } <EOL> self . __lru_queue = LRUList ( ) <EOL> def __del__ ( self ) : <EOL> self . clear ( ) <EOL> def get_max_capacity ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . __max_capacity <EOL> def set_max_capacity ( self , new_capacity ) : <EOL> """<STR_LIT>""" <EOL> self . __max_capacity = new_capacity <EOL> if len ( self ) > new_capacity : <EOL> self . __clear_to ( new_capacity ) <EOL> max_capacity = property ( get_max_capacity , set_max_capacity , <EOL> doc = '<STR_LIT>' ) <EOL> def add_ejection_listener ( self , listener , * args ) : <EOL> """<STR_LIT>""" <EOL> self . __removal_listeners [ listener ] = ( True , args ) <EOL> def add_removal_listener ( self , listener , * args ) : <EOL> """<STR_LIT>""" <EOL> self . __removal_listeners [ listener ] = ( False , args ) <EOL> def remove_listener ( self , listener ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> del self . __removal_listeners [ listener ] <EOL> return True <EOL> except KeyError : <EOL> return False <EOL> def clear_listeners ( self ) : <EOL> """<STR_LIT>""" <EOL> for key in self . __removal_listeners . keys ( ) : <EOL> del self . __removal_listeners [ key ] <EOL> def __setitem__ ( self , key , value ) : <EOL> self . __put ( key , value ) <EOL> def __getitem__ ( self , key ) : <EOL> lru_entry = dict . __getitem__ ( self , key ) <EOL> self . __lru_queue . move_to_head ( lru_entry ) <EOL> return lru_entry . value <EOL> def __delitem__ ( self , key ) : <EOL> lru_entry = dict . __getitem__ ( self , key ) <EOL> self . __lru_queue . remove ( lru_entry ) <EOL> dict . __delitem__ ( self , key ) <EOL> self . __notify_listeners ( False , [ ( lru_entry . key , lru_entry . value ) ] ) <EOL> def __str__ ( self ) : <EOL> s = '<STR_LIT:{>' <EOL> sep = '<STR_LIT>' <EOL> for k , v in self . iteritems ( ) : <EOL> s += sep <EOL> if type ( k ) == str : <EOL> s += "<STR_LIT>" % k <EOL> else : <EOL> s += str ( k ) <EOL> s += '<STR_LIT>' <EOL> if type ( v ) == str : <EOL> s += "<STR_LIT>" % v <EOL> else : <EOL> s += str ( v ) <EOL> sep = '<STR_LIT:U+002CU+0020>' <EOL> s += '<STR_LIT:}>' <EOL> return s <EOL> def __iter__ ( self ) : <EOL> return self . __lru_queue . __iter__ ( ) <EOL> def clear ( self ) : <EOL> self . __clear_to ( <NUM_LIT:0> ) <EOL> def get ( self , key , default = None ) : <EOL> try : <EOL> lru_entry = self . __getitem__ ( key ) <EOL> value = lru_entry . value <EOL> except KeyError : <EOL> value = default <EOL> return value <EOL> def keys ( self ) : <EOL> return self . __lru_queue . keys ( ) <EOL> def items ( self ) : <EOL> return self . __lru_queue . items ( ) <EOL> def values ( self ) : <EOL> return self . __lru_queue . values ( ) <EOL> def iteritems ( self ) : <EOL> return self . __lru_queue . iteritems ( ) <EOL> def iterkeys ( self ) : <EOL> return self . __lru_queue . iterkeys ( ) <EOL> def itervalues ( self ) : <EOL> return self . __lru_queue . itervalues ( ) <EOL> def update ( self , d ) : <EOL> for key , value in d . iteritems ( ) : <EOL> self [ key ] = value <EOL> def pop ( self , key , default = None ) : <EOL> try : <EOL> result = self [ key ] <EOL> del self [ key ] <EOL> except KeyError : <EOL> if not default : <EOL> raise <EOL> result = default <EOL> return result <EOL> def popitem ( self ) : <EOL> """<STR_LIT>""" <EOL> if len ( self ) == <NUM_LIT:0> : <EOL> raise KeyError , '<STR_LIT>' <EOL> lru_entry = self . __lru_queue . remove_tail ( ) <EOL> dict . __delitem__ ( self , lru_entry . key ) <EOL> return lru_entry . key , lru_entry . value <EOL> def __put ( self , key , value ) : <EOL> try : <EOL> lru_entry = dict . __getitem__ ( self , key ) <EOL> lru_entry . value = value <EOL> self . __lru_queue . move_to_head ( lru_entry ) <EOL> except KeyError : <EOL> lru_entry = self . __clear_to ( self . max_capacity - <NUM_LIT:1> ) <EOL> if lru_entry : <EOL> lru_entry . key , lru_entry . value = key , value <EOL> else : <EOL> lru_entry = LRUListEntry ( key , value ) <EOL> self . __lru_queue . add_to_head ( lru_entry ) <EOL> dict . __setitem__ ( self , key , lru_entry ) <EOL> def __clear_to ( self , size ) : <EOL> old_tail = None <EOL> while len ( self . __lru_queue ) > size : <EOL> old_tail = self . __lru_queue . remove_tail ( ) <EOL> assert old_tail <EOL> key = old_tail . key <EOL> value = dict . __delitem__ ( self , key ) <EOL> self . __notify_listeners ( True , [ ( key , value ) ] ) <EOL> assert len ( self . __lru_queue ) <= size <EOL> assert len ( self ) == len ( self . __lru_queue ) <EOL> return old_tail <EOL> def __notify_listeners ( self , ejecting , key_value_pairs ) : <EOL> if self . __removal_listeners : <EOL> for key , value in key_value_pairs : <EOL> for func , func_data in self . __removal_listeners . items ( ) : <EOL> on_eject_only , args = func_data <EOL> if ( not on_eject_only ) or ejecting : <EOL> func ( key , value , * args ) </s>
