<s> import itertools <EOL> import marshal <EOL> import math <EOL> from dpark . portable_hash import portable_hash <EOL> BYTE_SHIFT = <NUM_LIT:3> <EOL> BYTE_SIZE = <NUM_LIT:1> << BYTE_SHIFT <EOL> BYTE_MASK = BYTE_SIZE - <NUM_LIT:1> <EOL> _table = [ ( ) , ( <NUM_LIT:0> , ) , ( <NUM_LIT:1> , ) , ( <NUM_LIT:0> , <NUM_LIT:1> ) , ( <NUM_LIT:2> , ) , ( <NUM_LIT:0> , <NUM_LIT:2> ) , ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:3> , ) , <EOL> ( <NUM_LIT:0> , <NUM_LIT:3> ) , ( <NUM_LIT:1> , <NUM_LIT:3> ) , ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:3> ) , ( <NUM_LIT:2> , <NUM_LIT:3> ) , ( <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:3> ) , ( <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ) , ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ) ] <EOL> class BitIndex ( object ) : <EOL> def __init__ ( self ) : <EOL> self . array = bytearray ( ) <EOL> self . size = <NUM_LIT:0> <EOL> def __nonzero__ ( self ) : <EOL> return any ( self . array ) <EOL> def __repr__ ( self ) : <EOL> def to_bin ( x , s ) : <EOL> return bin ( x ) [ <NUM_LIT:2> : ] . zfill ( s ) [ : : - <NUM_LIT:1> ] <EOL> index , offset = self . _get_offset ( self . size ) <EOL> rep = [ to_bin ( x , BYTE_SIZE ) for x in self . array [ : index ] ] <EOL> if offset : <EOL> rep . append ( to_bin ( self . array [ index ] & ( <NUM_LIT:1> << offset ) - <NUM_LIT:1> , offset ) ) <EOL> return '<STR_LIT>' . join ( rep ) <EOL> def __len__ ( self ) : <EOL> return self . size <EOL> @ staticmethod <EOL> def _get_offset ( pos ) : <EOL> return pos >> BYTE_SHIFT , pos & BYTE_MASK <EOL> @ staticmethod <EOL> def _bitwise ( iterable , op ) : <EOL> for i , it in enumerate ( iterable ) : <EOL> if op : <EOL> byte = reduce ( op , it ) <EOL> else : <EOL> byte = it <EOL> if not byte : <EOL> continue <EOL> for x in _table [ byte & <NUM_LIT> ] : <EOL> yield i * BYTE_SIZE + x <EOL> for x in _table [ byte >> <NUM_LIT:4> ] : <EOL> yield i * BYTE_SIZE + <NUM_LIT:4> + x <EOL> def set ( self , pos , value = True ) : <EOL> if pos < <NUM_LIT:0> : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> index , offset = self . _get_offset ( pos ) <EOL> length = len ( self . array ) <EOL> if index >= length : <EOL> self . array . extend ( [ <NUM_LIT:0> ] * ( index - length + <NUM_LIT:1> ) ) <EOL> if value : <EOL> self . array [ index ] |= ( <NUM_LIT:1> << offset ) <EOL> else : <EOL> self . array [ index ] &= ~ ( <NUM_LIT:1> << offset ) <EOL> self . size = max ( self . size , pos + <NUM_LIT:1> ) <EOL> def sets ( self , positions , value = True ) : <EOL> for pos in positions : <EOL> self . set ( pos , value ) <EOL> def append ( self , value = True ) : <EOL> self . set ( self . size , value ) <EOL> def appends ( self , values ) : <EOL> for value in values : <EOL> self . append ( value ) <EOL> def get ( self , pos ) : <EOL> if pos < <NUM_LIT:0> : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> if pos >= self . size : <EOL> return False <EOL> index , offset = self . _get_offset ( pos ) <EOL> return ( self . array [ index ] & ( <NUM_LIT:1> << offset ) ) != <NUM_LIT:0> <EOL> def gets ( self , positions ) : <EOL> for pos in positions : <EOL> yield self . get ( pos ) <EOL> def intersect ( self , * other ) : <EOL> return self . _bitwise ( <EOL> itertools . izip ( self . array , * [ o . array for o in other ] ) , lambda x , y : x & y ) <EOL> def union ( self , * other ) : <EOL> return self . _bitwise ( <EOL> itertools . izip_longest ( self . array , * [ o . array for o in other ] , fillvalue = <NUM_LIT:0> ) , <EOL> lambda x , y : x | y ) <EOL> def xor ( self , other ) : <EOL> return self . _bitwise ( itertools . izip_longest ( self . array , other . array , fillvalue = <NUM_LIT:0> ) , <EOL> lambda x , y : x ^ y ) <EOL> def excepts ( self , * other ) : <EOL> return self . _bitwise ( <EOL> itertools . izip_longest ( self . array , * [ o . array for o in other ] , fillvalue = <NUM_LIT:0> ) , <EOL> lambda x , y : x & ~ y ) <EOL> def positions ( self ) : <EOL> return self . _bitwise ( self . array , None ) <EOL> class Bloomfilter ( object ) : <EOL> def __init__ ( self , m , k ) : <EOL> self . m = m <EOL> self . k = k <EOL> self . bitindex = BitIndex ( ) <EOL> """<STR_LIT>""" <EOL> @ staticmethod <EOL> def calculate_parameters ( n , p ) : <EOL> m = int ( math . ceil ( n * math . log ( p ) * - <NUM_LIT> ) ) <EOL> k = int ( round ( <NUM_LIT> * m / n ) ) <EOL> return m , k <EOL> '''<STR_LIT>''' <EOL> def _get_offsets ( self , obj ) : <EOL> hash_1 = portable_hash ( obj ) <EOL> hash_2 = portable_hash ( marshal . dumps ( obj ) ) <EOL> for i in xrange ( self . k ) : <EOL> yield ( ( hash_1 + i * hash_2 ) & <NUM_LIT> ) % self . m <EOL> def add ( self , objs ) : <EOL> for obj in objs : <EOL> self . bitindex . sets ( self . _get_offsets ( obj ) ) <EOL> def _match ( self , objs ) : <EOL> for obj in objs : <EOL> yield all ( self . bitindex . gets ( self . _get_offsets ( obj ) ) ) <EOL> def match ( self , objs ) : <EOL> return list ( self . _match ( objs ) ) <EOL> def __contains__ ( self , obj ) : <EOL> return self . _match ( [ obj ] ) . next ( ) </s>
