<s> """<STR_LIT>""" <EOL> from array import array <EOL> import codecs , re <EOL> from collections import deque , defaultdict <EOL> from functools import wraps <EOL> from struct import pack , unpack <EOL> from time import time , clock <EOL> utf8encode = codecs . getencoder ( "<STR_LIT>" ) <EOL> utf8decode = codecs . getdecoder ( "<STR_LIT>" ) <EOL> def _varint ( i ) : <EOL> s = "<STR_LIT>" <EOL> while ( i & ~ <NUM_LIT> ) != <NUM_LIT:0> : <EOL> s += chr ( ( i & <NUM_LIT> ) | <NUM_LIT> ) <EOL> i = i >> <NUM_LIT:7> <EOL> s += chr ( i ) <EOL> return s <EOL> _varint_cache_size = <NUM_LIT> <EOL> _varint_cache = [ ] <EOL> for i in xrange ( <NUM_LIT:0> , _varint_cache_size ) : <EOL> _varint_cache . append ( _varint ( i ) ) <EOL> _varint_cache = tuple ( _varint_cache ) <EOL> def varint ( i ) : <EOL> """<STR_LIT>""" <EOL> if i < len ( _varint_cache ) : <EOL> return _varint_cache [ i ] <EOL> return _varint ( i ) <EOL> def read_varint ( readfn ) : <EOL> """<STR_LIT>""" <EOL> b = ord ( readfn ( <NUM_LIT:1> ) ) <EOL> i = b & <NUM_LIT> <EOL> shift = <NUM_LIT:7> <EOL> while b & <NUM_LIT> != <NUM_LIT:0> : <EOL> b = ord ( readfn ( <NUM_LIT:1> ) ) <EOL> i |= ( b & <NUM_LIT> ) << shift <EOL> shift += <NUM_LIT:7> <EOL> return i <EOL> _fib_cache = { } <EOL> def fib ( n ) : <EOL> """<STR_LIT>""" <EOL> if n <= <NUM_LIT:2> : return n <EOL> if n in _fib_cache : return _fib_cache [ n ] <EOL> result = fib ( n - <NUM_LIT:1> ) + fib ( n - <NUM_LIT:2> ) <EOL> _fib_cache [ n ] = result <EOL> return result <EOL> def float_to_byte ( value , mantissabits = <NUM_LIT:5> , zeroexp = <NUM_LIT:2> ) : <EOL> """<STR_LIT>""" <EOL> fzero = ( <NUM_LIT> - zeroexp ) << mantissabits <EOL> bits = unpack ( "<STR_LIT:i>" , pack ( "<STR_LIT:f>" , value ) ) [ <NUM_LIT:0> ] <EOL> smallfloat = bits >> ( <NUM_LIT> - mantissabits ) <EOL> if smallfloat < fzero : <EOL> if bits <= <NUM_LIT:0> : <EOL> return chr ( <NUM_LIT:0> ) <EOL> else : <EOL> return chr ( <NUM_LIT:1> ) <EOL> elif smallfloat >= fzero + <NUM_LIT> : <EOL> return chr ( <NUM_LIT:255> ) <EOL> else : <EOL> return chr ( smallfloat - fzero ) <EOL> def byte_to_float ( b , mantissabits = <NUM_LIT:5> , zeroexp = <NUM_LIT:2> ) : <EOL> """<STR_LIT>""" <EOL> b = ord ( b ) <EOL> if b == <NUM_LIT:0> : <EOL> return <NUM_LIT:0.0> <EOL> bits = ( b & <NUM_LIT> ) << ( <NUM_LIT> - mantissabits ) <EOL> bits += ( <NUM_LIT> - zeroexp ) << <NUM_LIT> <EOL> return unpack ( "<STR_LIT:f>" , pack ( "<STR_LIT:i>" , bits ) ) [ <NUM_LIT:0> ] <EOL> def first_diff ( a , b ) : <EOL> """<STR_LIT>""" <EOL> i = - <NUM_LIT:1> <EOL> for i in xrange ( <NUM_LIT:0> , len ( a ) ) : <EOL> if a [ i ] != b [ <NUM_LIT:1> ] : <EOL> return i <EOL> if i == <NUM_LIT:255> : return i <EOL> def prefix_encode ( a , b ) : <EOL> """<STR_LIT>""" <EOL> i = first_diff ( a , b ) <EOL> return chr ( i ) + b [ i : ] . encode ( "<STR_LIT:utf8>" ) <EOL> def prefix_encode_all ( ls ) : <EOL> """<STR_LIT>""" <EOL> last = u'<STR_LIT>' <EOL> for w in ls : <EOL> i = first_diff ( last , w ) <EOL> yield chr ( i ) + w [ i : ] . encode ( "<STR_LIT:utf8>" ) <EOL> last = w <EOL> def to_7bit ( x , islong ) : <EOL> if not islong : <EOL> shift = <NUM_LIT> <EOL> nchars = <NUM_LIT:5> <EOL> else : <EOL> shift = <NUM_LIT> <EOL> nchars = <NUM_LIT:10> <EOL> buffer = array ( "<STR_LIT:c>" , "<STR_LIT:\x00>" * nchars ) <EOL> x += ( <NUM_LIT:1> << shift ) - <NUM_LIT:1> <EOL> while x : <EOL> buffer [ nchars - <NUM_LIT:1> ] = chr ( x & <NUM_LIT> ) <EOL> x >>= <NUM_LIT:7> <EOL> nchars -= <NUM_LIT:1> <EOL> return buffer . tostring ( ) <EOL> def from_7bit ( text ) : <EOL> if len ( text ) == <NUM_LIT:5> : <EOL> shift = <NUM_LIT> <EOL> elif len ( text ) == <NUM_LIT:10> : <EOL> shift = <NUM_LIT> <EOL> else : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> x = <NUM_LIT:0> <EOL> for char in text : <EOL> x <<= <NUM_LIT:7> <EOL> char = ord ( char ) <EOL> if char > <NUM_LIT> : <EOL> raise Exception <EOL> x |= char <EOL> x -= ( <NUM_LIT:1> << shift ) - <NUM_LIT:1> <EOL> return x <EOL> def prefix_decode_all ( ls ) : <EOL> """<STR_LIT>""" <EOL> last = u'<STR_LIT>' <EOL> for w in ls : <EOL> i = ord ( w [ <NUM_LIT:0> ] ) <EOL> decoded = last [ : i ] + w [ <NUM_LIT:1> : ] . decode ( "<STR_LIT:utf8>" ) <EOL> yield decoded <EOL> last = decoded <EOL> _nkre = re . compile ( r"<STR_LIT>" , re . UNICODE ) <EOL> def _nkconv ( i ) : <EOL> try : <EOL> return int ( i ) <EOL> except ValueError : <EOL> return i . lower ( ) <EOL> def natural_key ( s ) : <EOL> """<STR_LIT>""" <EOL> return tuple ( _nkconv ( m ) for m in _nkre . findall ( s ) ) <EOL> class ClosableMixin ( object ) : <EOL> """<STR_LIT>""" <EOL> def __enter__ ( self ) : <EOL> return self <EOL> def __exit__ ( self , * exc_info ) : <EOL> self . close ( ) <EOL> def protected ( func ) : <EOL> """<STR_LIT>""" <EOL> @ wraps ( func ) <EOL> def wrapper ( self , * args , ** kwargs ) : <EOL> if self . is_closed : <EOL> raise Exception ( "<STR_LIT>" % self ) <EOL> if self . _sync_lock . acquire ( False ) : <EOL> try : <EOL> return func ( self , * args , ** kwargs ) <EOL> finally : <EOL> self . _sync_lock . release ( ) <EOL> else : <EOL> raise Exception ( "<STR_LIT>" ) <EOL> return wrapper <EOL> def lru_cache ( size ) : <EOL> """<STR_LIT>""" <EOL> def decorate_function ( func ) : <EOL> prefix = "<STR_LIT>" % func . __name__ <EOL> @ wraps ( func ) <EOL> def wrapper ( self , * args ) : <EOL> if not hasattr ( self , prefix + "<STR_LIT>" ) : <EOL> cache = { } <EOL> queue = deque ( ) <EOL> refcount = defaultdict ( int ) <EOL> setattr ( self , prefix + "<STR_LIT>" , cache ) <EOL> setattr ( self , prefix + "<STR_LIT>" , queue ) <EOL> setattr ( self , prefix + "<STR_LIT>" , refcount ) <EOL> else : <EOL> cache = getattr ( self , prefix + "<STR_LIT>" ) <EOL> queue = getattr ( self , prefix + "<STR_LIT>" ) <EOL> refcount = getattr ( self , prefix + "<STR_LIT>" ) <EOL> qpend = queue . append <EOL> qpop = queue . popleft <EOL> try : <EOL> result = cache [ args ] <EOL> except KeyError : <EOL> result = cache [ args ] = func ( self , * args ) <EOL> qpend ( args ) <EOL> refcount [ args ] += <NUM_LIT:1> <EOL> while len ( cache ) > size : <EOL> k = qpop ( ) <EOL> refcount [ k ] -= <NUM_LIT:1> <EOL> if not refcount [ k ] : <EOL> del cache [ k ] <EOL> del refcount [ k ] <EOL> if len ( queue ) > size * <NUM_LIT:4> : <EOL> for _ in xrange ( len ( queue ) ) : <EOL> k = qpop ( ) <EOL> if refcount [ k ] == <NUM_LIT:1> : <EOL> qpend ( k ) <EOL> else : <EOL> refcount [ k ] -= <NUM_LIT:1> <EOL> return result <EOL> return wrapper <EOL> return decorate_function </s>
