bitvector.py

java bitvector implementation.

        (9)  You can pad a bit vector from the left or from the
             right with a designated number of zeros

                bitvec.pad_from_left( n )

                bitvec.pad_from_right( n )

             In the first case, the new bit vector will be the same
             as the old bit vector except for the additional n zeros
             on the left.  The same thing happens in the second
             case except that now the additional n zeros will be on
             the right.



    HOW THE BIT VECTORS ARE STORED:

   
        The bits of a bit array are stored in 16-bit unsigned ints.
        After resolving the argument with which the constructor is
        called (which happens in lines (A2) through (A61) of the file
        BitVector.py), the very first thing that the constructor does is
        to figure out in line (A62) as to how many of those 2-byte ints
        it needs for the bits.  For example, if you wanted to store a
        64-bit array, the variable 'two_byte_ints_needed' in line (A62)
        would be set to 4. (This does not mean that the size of a bit
        vector must be a multiple of 16.  Any sized bit vectors can
        constructed using the required number of two-byte ints.) Line
        (A63) then creates an array of 2-byte ints and initializes it
        with the required number of zeros.  Lines (A64) then shifts the
        bits into the array of two-byte ints.

        As mentioned above, note that it is not necessary for the size
        of the vector to be a multiple of 16 even though we are using
        C's unsigned short as as a basic unit for storing the bit
        arrays.  The class BitVector keeps track of the actual number of
        bits in the bit vector through the "size" instance attribute.

        With regard to the code in lines (A2) through (A61) of the file
        BitVector.py, note that the constructor must be called with a
        single keyword argument, which determines how the bit vector
        will be constructed.  Lines (A11) through (A18) are for the
        following sort of a call

               bv = BitVector( filename = 'myfilename' )

        This calls returns a bit vector on which you must subsequently
        invoke the 'read_bits_from_file' method to actually obtain a bit
        vector consisting of the bits that constitute the information
        stored in the file.  Lines (A19) through (A24) are for the case
        when you want to construct a bit vector by reading the bits off
        a file-like object, as in

              x = "111100001111"
              fileobj = StringIO.StringIO( x )
              bv = BitVector( fp = fileobj )

        Lines (A25) through (A29) are for constructing a bit vector with
        just the size information, as in

              bv = BitVector( size = 61 )

        This returns a bit vector that will hold exactly 61 bits, all
        initialized to the zero value.  Lines (A30) through (A50) are
        for the case when you want to construct a bit vector from an
        integer, as in

              bv = BitVector( intVal = 123456 )

        The bits stored in the bit vector will correspond to the binary
        representation of the integer argument provided.  Lines (51)
        through (55) are for constructing a bit vector from a bitstring,
        as in

              bv = BitVector( bitstring = '00110011111' )

        Finally, lines (A56) through (A59) are for constructing a bit
        vector from a list or a tuple of the individual bits:
          
              bv = BitVector( bitlist = (1, 0, 1, 1, 0, 0, 1) )

        Now the bit vector constructed will be initialized at the same
        time with the supplied bits.

   

    ACKNOWLEDGEMENTS:

        The author is grateful to Oleg Broytmann for suggesting many
        improvements that were incorporated in Version 1.1 of this
        package.  The author would like to thank Kurt Schwehr whose
        email resulted in the creation of Version 1.2.  Kurt also caught
        an error in my earlier version of 'setup.py' and suggested a
        unittest based approach to the testing of the package.  Kurt
        also supplied the Makefile that is included in this
        distribution.  The author would also like to thank all (Scott
        Daniels, Blair Houghton, and Steven D'Aprano) for their
        responses to my comp.lang.python query concerning how to make a
        Python input stream peekable.  This feature was included in
        Version 1.1.1.
   


    ABOUT THE AUTHOR:

        Avi Kak is the author of "Programming with Objects: A
        Comparative Presentation of Object-Oriented Programming
        with C++ and Java", published by John-Wiley in 2003. This
        book presents a new approach to the combined learning of
        two large object-oriented languages, C++ and Java.  It is
        being used as a text in a number of educational programs
        around the world.  This book has also been translated into
        Chinese.  For further information, please visit
        www.programming-with-objects.com
        


    SOME EXAMPLE CODE:

        #!/usr/bin/env python
        import BitVector

        # Construct a bit vector from a list or tuple of bits:
        bv = BitVector.BitVector( bitlist = (1, 0, 0, 1) )
        print bv                                # 1001

        # Construct a bit vector from an integer:
        bv = BitVector.BitVector( intVal = 5678 )
        print bv                                # 0001011000101110

        # Construct a zero-initialized bit vector of a given size:
        bv = BitVector.BitVector( size = 5 )
        print bv                                # 00000

        # Construct a bit vector from a bit string:
        bv = BitVector.BitVector( bitstring = '110001' )     
        print bv[0], bv[1], bv[2], bv[3], bv[4], bv[5]       # 1 1 0 0 0 1
        print bv[-1], bv[-2], bv[-3], bv[-4], bv[-5], bv[-6] # 1 0 0 0 1 1

        # Construct a bit vector from a file like object:
        import StringIO
        x = "111100001111"
        fp_read = StringIO.StringIO( x )
        bv = BitVector.BitVector( fp = fp_read )
        print bv                                    # 111100001111 

        # Experiments with bit-wise logical operations:
        bv3 = bv1 | bv2                              
        bv3 = bv1 & bv2
        bv3 = bv1 ^ bv2
        bv6 = ~bv5

        # Find the length of a bit vector
        print len( bitvec )

        # Find the integer value of a bit vector
        print int( bitvec )

        # Open a file for reading bit vectors from
        bv = BitVector.BitVector( filename = 'TestBitVector/testinput1.txt' )
        print bv                                    # nothing yet
        bv1 = bv.read_bits_from_file(64)    
        print bv1                            # first 64 bits from the file

        # Divide a bit vector into two equal sub-vectors:
        [bv1, bv2] = bitvec.divide_into_two()

        # Permute and Un-Permute a bit vector:
        bv2 = bitvec.permute( permutation_list )
        bv2 = bitvec.unpermute( permutation_list )

        # Try circular shifts to the left and to the right
        bitvec << 7
        bitvec >> 7

        .....
        .....

        (For a more complete working example, see the example code in
         the BitVectorDemo.py file in the Examples sub-directory.)

'''


import sys
import array
import exceptions
import operator

_hexdict = { '0' : '0000', '1' : '0001', '2' : '0010', '3' : '0011',
             '4' : '0100', '5' : '0101', '6' : '0110', '7' : '0111',
             '8' : '1000', '9' : '1001', 'a' : '1010', 'b' : '1011',
             'c' : '1100', 'd' : '1101', 'e' : '1110', 'f' : '1111' }

# If this function can read all blocksize bits, it peeks ahead
# to see if there is anything more to be read in the file. It
# uses tell-read-seek mechanism for this in lines (R18) through
# (R21).  If there is nothing further to be read, it sets the
# more_to_read attribute of the bitvector object to False.
# Obviously, this can only be done for seekable streams such
# as those connected with disk files.  According to Blair Houghton,
# a similar feature could presumably be implemented for socket
# streams by using recv() or recvfrom() if you set the flags
# argument to MSG_PEEK. 
def _readblock( blocksize, bitvector ):                              #(R1)
    global hexdict                                                   #(R2)
    bitstring = ''                                                   #(R3)
    i = 0                                                            #(R4)
    while ( i < blocksize / 8 ):                                     #(R5)
        i += 1                                                       #(R6)
        byte = bitvector.FILEIN.read(1)                              #(R7)
        if byte == '':                                               #(R8)
            if len(bitstring) < blocksize:                           #(R9)
                bitvector.more_to_read = False                      #(R10)
            return bitstring                                        #(R11)
        hexvalue = hex( ord( byte ) )                               #(R12)
        hexvalue = hexvalue[2:]                                     #(R13)
        if len( hexvalue ) == 1:                                    #(R14)
            hexvalue = '0' + hexvalue                               #(R15)
        bitstring += _hexdict[ hexvalue[0] ]                        #(R16)
        bitstring += _hexdict[ hexvalue[1] ]                        #(R17)
    file_pos = bitvector.FILEIN.tell()                              #(R18)
    # peek at the next byte; moves file position only if a
    # byte is read
    next_byte = bitvector.FILEIN.read(1)                            #(R19)
    if next_byte:                                                   #(R20)
        # pretend we never read the byte                   
        bitvector.FILEIN.seek( file_pos )                           #(R21)
    else:                                                           #(R22)
        bitvector.more_to_read = False                              #(R23)
    return bitstring                                                #(R24)


#--------------------  BitVector Class Definition   ----------------------

class BitVector( object ):                                           #(A1)

    def __init__( self, *args, **kwargs ):                           #(A2)
        if args:                                                     #(A3)
               raise ValueError(
                      '''BitVector constructor can only be called
                         with keyword arguments for the following
                         keywords: filename, fp (for fileobject),
                         size, intValue, bitlist (for a list or
                         tuple of bits, or bitstring)''')
        filename = fp = size = intVal = bitlist = bitstring = None   #(A4)
        if kwargs.has_key('filename'):filename=kwargs.pop('filename')#(A5)
        if kwargs.has_key('fp'):           fp = kwargs.pop('fp')     #(A6)
        if kwargs.has_key('size'):       size = kwargs.pop('size')   #(A7)
        if kwargs.has_key('intVal'):   intVal = kwargs.pop('intVal') #(A8)
        if kwargs.has_key('bitlist'): bitlist = kwargs.pop('bitlist')#(A9)
        if kwargs.has_key('bitstring') :
                               bitstring = kwargs.pop('bitstring')  #(A10)

        if filename:                                                #(A11)
            if fp or size or intVal or bitlist or bitstring:        #(A12)
                raise ValueError(                                   #(A13)
                  '''When filename is specified, you cannot
                     give values to any other constructor args''')
            self.filename = filename                                #(A14)
            self.FILEIN = open( filename, 'rb' )                    #(A15)
            self.size = 0                                           #(A16)
            self.more_to_read = True                                #(A17)
            return                                                  #(A18)
        elif fp:                                                    #(A19)
            if filename or size or intVal or bitlist or bitstring:  #(A20)
                raise ValueError(                                   #(A21)
                  '''When fileobject is specified, you cannot      
                     give values to any other constructor args''')
            bits = self.read_bits_from_fileobject( fp )             #(A22)
            bitlist =  map( lambda x: int(x), bits )                #(A23)
            self.size = len( bitlist )                              #(A24)
        elif size >= 0:                                             #(A25)
            if filename or fp or intVal or bitlist or bitstring:    #(A26)
                raise ValueError(                                   #(A27)
                  '''When size is specified, you cannot
                     give values to any other constructor args''')
            self.size = size                                        #(A28)
            bitlist = tuple( [0] * size )                           #(A29)
        elif intVal or intVal == 0:                                 #(A30)
            if filename or fp or size or bitlist or bitstring:      #(A31)
                raise ValueError(                                   #(A32)
                  '''When intVal is specified, you cannot
                     give values to any other constructor args''')
            if intVal == 0:                                         #(A33)
                bitlist = [0]                                       #(A34)
                self.size = 1                                       #(A35)
            else:                                                   #(A36)
                hexVal = hex( intVal )                              #(A37)
                hexVal = hexVal[2:]                                 #(A38)
                if len( hexVal ) == 1:                              #(A39)
                    hexVal = '0' + hexVal                           #(A40)
                bitlist = []                                        #(A41)
                for item in hexVal[:]:                              #(A42)
                    bitlist += _hexdict[item][:]                    #(A43)
                bitlist =  map( lambda x: int(x), bitlist )         #(A44)
                i = 0                                               #(A45)
                while ( i < len( bitlist ) ):                       #(A46)
                    if bitlist[i] == 1: break                       #(A47)
                    i += 1                                          #(A48)
                del bitlist[0:i]                                    #(A49)
                self.size = len( bitlist )                          #(A50)
        elif bitstring or bitstring == '':                          #(A51)
            if filename or fp or size or intVal or bitlist:         #(A52)
                raise ValueError(                                   #(A53)
                  '''When a bitstring is specified, you cannot
                     give values to any other constructor args''')
            bitlist =  map( lambda x: int(x), list(bitstring) )     #(A54)
            self.size = len( bitlist )                              #(A55)