bitvector.py

java bitvector implementation.

        elif bitlist:                                               #(A56)
            if filename or fp or size or intVal or bitstring:       #(A57)
                raise ValueError(                                   #(A58)
                  '''When bits are specified, you cannot
                     give values to any other constructor args''')
            self.size = len( bitlist )                              #(A59)
        else:                                                       #(A60)
            raise ValueError("wrong arg(s) for constructor")        #(A61) 
        two_byte_ints_needed = (len(bitlist) + 15) // 16            #(A62)
        self.vector = array.array( 'H', [0]*two_byte_ints_needed )  #(A63)
        map( self._setbit, enumerate(bitlist), bitlist)             #(A64)

    # Set the bit at the designated position to the value shown:
    def _setbit( self, posn, val ):                                  #(B1)
        if val not in (0, 1):                                        #(B2)
            raise ValueError( "incorrect value for a bit" )          #(B3)
        if isinstance( posn, (tuple) ):                              #(B4)
            posn = posn[0]                                           #(B5)
        if  posn >= self.size or posn < -self.size:                  #(B6)
            raise ValueError( "index range error" )                  #(B7)   
        if posn < 0: posn = self.size + posn                         #(B8)
        block_index = posn // 16                                     #(B9)
        shift = posn & 15                                           #(B10)
        cv = self.vector[block_index]                               #(B11)
        if ( cv >> shift ) & 1 != val:                              #(B12)
            self.vector[block_index] = cv ^ (1 << shift)            #(B13)

    # Get the bit from the designated position:
    def _getbit( self, posn ):                                       #(C1)
        if  posn >= self.size or posn < -self.size:                  #(C2)
            raise ValueError( "index range error" )                  #(C3)   
        if posn < 0: posn = self.size + posn                         #(C4)
        return ( self.vector[posn//16] >> (posn&15) ) & 1            #(C5)

    # Take a bitwise 'xor' of the bit vector on which the method is
    # invoked with the argument bit vector.  Return the result as
    # a new bit vector.  If the two bit vectors are not of the same
    # size, pad the shorter one with zero's from the left.        
    def __xor__(self, other):                                        #(E1)
        if self.size < other.size:                                   #(E2)
            bv1 = self._resize_pad_from_left(other.size - self.size) #(E3)
            bv2 = other                                              #(E4)
        else:                                                        #(E5)
            bv1 = self                                               #(E6)
            bv2 = other._resize_pad_from_left(self.size - other.size)#(E7)
        res = BitVector( size = bv1.size )                           #(E8)
        res.vector = map(operator.__xor__, bv1.vector, bv2.vector)   #(E9) 
        return res                                                  #(E10)

    # Take a bitwise 'and' of the bit vector on which the method is
    # invoked with the argument bit vector.  Return the result as
    # a new bit vector.  If the two bit vectors are not of the same
    # size, pad the shorter one with zero's from the left.    
    def __and__(self, other):                                        #(F1)
        if self.size < other.size:                                   #(F2)
            bv1 = self._resize_pad_from_left(other.size - self.size) #(F3)
            bv2 = other                                              #(F4)
        else:                                                        #(F5)
            bv1 = self                                               #(F6)
            bv2 = other._resize_pad_from_left(self.size - other.size)#(F7)
        res = BitVector( size = bv1.size )                           #(F8)
        res.vector = map(operator.__and__, bv1.vector, bv2.vector)   #(F9)
        return res                                                  #(F10)

    # Take a bitwise 'or' of the bit vector on which the method is
    # invoked with the argument bit vector.  Return the result as
    # a new bit vector.  If the two bit vectors are not of the same
    # size, pad the shorter one with zero's from the left.
    def __or__(self, other):                                         #(G1)
        if self.size < other.size:                                   #(G2)
            bv1 = self._resize_pad_from_left(other.size - self.size) #(G3)
            bv2 = other                                              #(G4)
        else:                                                        #(G5)
            bv1 = self                                               #(G6)
            bv2 = other._resize_pad_from_left(self.size - other.size)#(G7)
        res = BitVector( size = bv1.size )                           #(G8)
        res.vector = map( operator.__or__, bv1.vector, bv2.vector)   #(G9)
        return res                                                  #(G10)

    # Invert the bits in the bit vector on which the method is
    # invoked and return the result as a new bit vector.
    def __invert__(self):                                            #(H1)
        res = BitVector( size = self.size )                          #(H2)
        res.vector = map( operator.__inv__, self.vector )            #(H3)
        return res                                                   #(H4)

    # Concatenate the argument bit vector with the bit vector
    # on which the method is invoked.  Return the concatenated
    # bit vector as a new BitVector object:
    def __add__(self, other):                                        #(J1)
        i = 0                                                        #(J2)
        outlist = []                                                 #(J3)
        while ( i < self.size ):                                     #(J4)
            outlist.append( self[i] )                                #(J5)
            i += 1                                                   #(J6)
        i = 0                                                        #(J7)
        while ( i < other.size ):                                    #(J8)
            outlist.append( other[i] )                               #(J9)
            i += 1                                                  #(J10)
        return BitVector( bitlist = outlist )                       #(J11)

    # Return the number of bits in a bit vector:
    def _getsize(self):                                              #(K1)
        return self.size                                             #(K2)

    # Read blocksize bits from a disk file and return a
    # BitVector object containing the bits.  If the file
    # contains fewer bits than blocksize, construct the
    # BitVector object from however many bits there are
    # in the file.  If the file contains zero bits, return
    # a BitVector object of size attribute set to 0.
    def read_bits_from_file(self, blocksize):                        #(L1)
        error_str = '''You need to first construct a BitVector
        object with a filename as  argument'''                       #(L2)
        if self.filename == None:                                    #(L3)
            raise SyntaxError( error_str )                           #(L4)
        if blocksize % 8 != 0:                                       #(L5)
            raise ValueError( "block size must be a multiple of 8" ) #(L6)
        bitstr = _readblock( blocksize, self )                       #(L7)
        if len( bitstr ) == 0:                                       #(L8)
            return BitVector( size = 0 )                             #(L9)
        else:                                                       #(L10)
            return BitVector( bitstring = bitstr )                  #(L11)

    # This function is meant to read a bit string from a
    # file like object.
    def read_bits_from_fileobject( self, fp ):                       #(M1)
        bitlist = []                                                 #(M2)
        while True:                                                  #(M3)
            bit = fp.read()                                          #(M4)
            if bit == '': return bitlist                             #(M5)
            bitlist += bit                                           #(M6)

    # This function is meant to write a bit vector directly to
    # a file like object.  Note that whereas 'write_to_file'
    # method creates a memory footprint that corresponds exactly
    # to the bit vector, the 'write_bits_to_fileobject' actually
    # writes out the 1's and 0's as individual items to the
    # file object.  That makes this method convenient for
    # creating a string representation of a bit vector,
    # especially if you use the StringIO class, as shown in
    # the test code.
    def write_bits_to_fileobject( self, fp ):                        #(N1)
        for bit_index in range(self.size):                           #(N2)
            if self[bit_index] == 0:                                 #(N3)
                fp.write( '0' )                                      #(N4)
            else:                                                    #(N5)
                fp.write( '1' )                                      #(N6)

    # Divides an even-sized bit vector into two and returns
    # the two halves as a list of two bit vectors.
    def divide_into_two(self):                                       #(P1)
        if self.size % 2 != 0:                                       #(P2)
            raise ValueError( "must have even num bits" )            #(P3)
        i = 0                                                        #(P4)
        outlist1 = []                                                #(P5)
        while ( i < self.size /2 ):                                  #(P6)
            outlist1.append( self[i] )                               #(P7)
            i += 1                                                   #(P8)
        outlist2 = []                                                #(P9)
        while ( i < self.size ):                                    #(P10)
            outlist2.append( self[i] )                              #(P11)
            i += 1                                                  #(P12)
        return [ BitVector( bitlist = outlist1 ),
                 BitVector( bitlist = outlist2 ) ]                  #(P13)

    # Permute a bit vector according to the indices shown in the
    # second argument list.  Return the permuted bit vector as a
    # new bit vector.
    def permute(self, permute_list):                                 #(Q1)
        if max(permute_list) > self.size -1:                         #(Q2)
            raise ValueError( "Bad permutation index" )              #(Q3)
        outlist = []                                                 #(Q4)
        i = 0                                                        #(Q5)
        while ( i < len( permute_list ) ):                           #(Q6)
            outlist.append( self[ permute_list[i] ] )                #(Q7)
            i += 1                                                   #(Q8)
        return BitVector( bitlist = outlist )                        #(Q9)

    # Unpermute the bit vector according to the permutation list
    # supplied as the second argument.  If you first permute a
    # bit vector by using permute() and then unpermute() it using
    # the same permutation list, you will get back the original bit
    # vector.
    def unpermute(self, permute_list):                               #(S1)
        if max(permute_list) > self.size -1:                         #(S2)
            raise exceptions.ValueError, "Bad permutation index"     #(S3)
        if self.size != len( permute_list ):                         #(S4)
            raise exceptions.ValueError,"Bad size for permute list"  #(S5)
        out_bv = BitVector( size = self.size )                       #(S6)
        i = 0                                                        #(S7)
        while ( i < len(permute_list) ):                             #(S8)
            out_bv[ permute_list[i] ] = self[i]                      #(S9)
            i += 1                                                  #(S10)
        return out_bv                                               #(S11)

    # (Contributed by Joe Davidson) Write the bitvector to the file
    # object file_out.  (A file object is returned by a call to open()).
    # Since all file I/O is byte oriented, the bitvector must be
    # multiple of 8 bits. Each byte treated as MSB first (0th index)
    def write_to_file(self, file_out):                               #(T1)
        err_str = '''Only a bit vector whose length is a multiple of 8
            can be written to a file.  Use the padding functions
            to satisfy this constraint.'''                           #(T2)
        if self.size % 8:                                            #(T3)
            raise exceptions.ValueError, err_str                     #(T4)
        for byte in range(self.size/8 ):                             #(T5)
            value = 0                                                #(T6)
            for bit in range(8):                                     #(T7)
                value += (self._getbit( byte*8 + (7 - bit) ) << bit )#(T8)
            file_out.write( chr(value) )                             #(T9)

    # For closing a file object that was used for reading
    # the bits into one or more BitVector objects
    def close_file_object(self):                                     #(U1)
        if self.filename == None:                                    #(U2)
            raise exceptions.SyntaxError, "No associated open file"  #(U3)
        self.FILEIN.close()                                          #(U4)

    # Return the integer value of a bitvector:
    def intValue(self):                                              #(V1)
        intVal = 0                                                   #(V2)
        for i in range(self.size):                                   #(V3)
            intVal += self[i] * (2 ** (self.size - i - 1))           #(V4)
        return intVal                                                #(V5)
            
    # For an in-place left circular shift by n bit positions:
    def __lshift__( self, n ):                                       #(W1)
        for i in range(n):                                           #(W2)
            self.circular_rotate_left_by_one()                       #(W3)
    # For an in-place right circular shift by n bit positions:
    def __rshift__( self, n ):                                       #(W4)
        for i in range(n):                                           #(W5)
            self.circular_rotate_right_by_one()                      #(W6)

    # For a one-bit in-place left circular shift:
    def circular_rotate_left_by_one(self):                           #(X1)
        size = len(self.vector)                                      #(X2)
        bitstring_leftmost_bit = self.vector[0] & 1                  #(X3)
        left_most_bits = map(operator.__and__, self.vector, [1]*size)#(X4)
        left_most_bits.append(left_most_bits[0])                     #(X5)
        del(left_most_bits[0])                                       #(X6)
        self.vector = map(operator.__rshift__, self.vector, [1]*size)#(X7)
        self.vector = map( operator.__or__, self.vector, \
             map(operator.__lshift__, left_most_bits, [15]*size) )   #(X8)
        self._setbit(self.size -1, bitstring_leftmost_bit)           #(X9)

    # For a one-bit in-place right circular shift:
    def circular_rotate_right_by_one(self):                          #(Y1)
        size = len(self.vector)                                      #(Y2)
        bitstring_rightmost_bit = self[self.size - 1]                #(Y3)
        right_most_bits = map( operator.__and__,
                               self.vector, [0x8000]*size )          #(Y4)
        map( operator.__and__, self.vector, [~0x8000]*size )         #(Y5)
        right_most_bits.insert(0, bitstring_rightmost_bit)           #(Y6)
        right_most_bits.pop()                                        #(Y7)
        self.vector = map(operator.__lshift__, self.vector, [1]*size)#(Y8)
        self.vector = map( operator.__or__, self.vector, \
             map(operator.__rshift__, right_most_bits, [15]*size) )  #(Y9)
        self._setbit(0, bitstring_rightmost_bit)                    #(Y10)

    # This is merely another implementation of the method
    # circular_rotate_left_by_one() shown above.  This one
    # does NOT use map functions.  This method carries out a
    # one-bit left circular shift of a bit vector.
    def circular_rot_left(self):                                     #(Z1)
        max_index = (self.size -1)  // 16                            #(Z2)
        left_most_bit = self.vector[0] & 1                           #(Z3)
        self.vector[0] = self.vector[0] >> 1                         #(Z4)
        for i in range(1, max_index + 1):                            #(Z5)
            left_bit = self.vector[i] & 1                            #(Z6)
            self.vector[i] = self.vector[i] >> 1                     #(Z7)
            self.vector[i-1] |= left_bit << 15                       #(Z8)
        self._setbit(self.size -1, left_most_bit)                    #(Z9)

    # This is merely another implementation of the method
    # circular_rotate_right_by_one() shown above.  This one
    # does NOT use map functions.  This method does a one-bit
    # right circular shift of a bit vector.
    def circular_rot_right(self):                                    #(a1)
        max_index = (self.size -1)  // 16                            #(a2)
        right_most_bit = self[self.size - 1]                         #(a3)
        self.vector[max_index] &= ~0x8000                            #(a4)
        self.vector[max_index] = self.vector[max_index] << 1         #(a5)
        for i in range(max_index-1, -1, -1):                         #(a6)
            right_bit = self.vector[i] & 0x8000                      #(a7)
            self.vector[i] &= ~0x8000                                #(a8)
            self.vector[i] = self.vector[i] << 1                     #(a9)
            self.vector[i+1] |= right_bit >> 15                     #(a10)
        self._setbit(0, right_most_bit)                             #(a11)


    # Allow array like subscripting for getting and setting:
    __getitem__ = _getbit                                            #(b1)
    __setitem__ = _setbit                                            #(b2)

    # Allow slicing with [i:j], [:], etc.
    def __getslice__(self, i, j):                                    #(c1)
        slicebits = []                                               #(c2)
        if j > self.size: j = self.size                              #(c3)
        for x in range(i,j):                                         #(c4)
            slicebits.append( self[x] )                              #(c5)
        return BitVector( bitlist = slicebits )                      #(c6)

    # Allow len() to work:
    __len__ = _getsize                                               #(d1)
    # Allow int() to work:
    __int__ = intValue                                               #(d2)
    # To allow iterations over a bit vector: