bitvector.py

java bitvector implementation.

#!/usr/bin/env python

__version__ = '1.2'
__date__    = '2006-Mar-14'

__doc__ = '''

    BitVector.py

    Version: ''' + __version__ + '''
   
    Author: Avinash Kak ([e-mail])

    Date: ''' + __date__ + '''


    CHANGE LOG:

       Version 1.2:

           (a) One more constructor mode included: You can now construct
           a bit vector directly from a string of 1's and 0's.  (b) The
           class now constructs a shortest possible bit vector from an
           integer value.  So the bit vector for the integer value 0 is
           just one bit of value 0, and so on. (c) All the rich
           comparison operators are now overloaded. (d) The class now
           includes a new method 'intValue()' that returns the unsigned
           integer value of a bit vector.  This can also be done through
           '__int__'. (e) The package now includes a unittest based
           framework for testing out an installation.  This is in a
           separate directory called "TestBitVector".
       
       Version 1.1.1:

           The function that does block reads from a disk file now peeks
           ahead at the end of each block to see if there is anything
           remaining to be read in the file.  If nothing remains, the
           more_to_read attribute of the BitVector object is set to
           False.  This simplifies reading loops. This version also
           allows BitVectors of size 0 to be constructed


       Version 1.1:

           I have changed the API significantly to provide more ways for
           constructing a bit vector.  As a result, it is now necessary
           to supply a keyword argument to the constructor.
       


    INTRODUCTION:
   
       The BitVector class for a memory-efficient packed representation
       of bit arrays and for logical operations on such arrays.  The
       core idea used in this Python script for bin packing is based on
       an internet posting by Josiah Carlson to the Pyrex mailing list.

       Operations supported on bit vectors:

              __getitem__
              __setitem__
              __len__
              __iter__
              __getslice__
              __str__
              __int__
              __add__
              __eq__, __ne__, __lt__, __le__, __gt__, __ge__
              |            for bitwise or
              &            for bitwise and              
              ^            for bitwise xor
              ~            for bitwise inversion
              <<           for circular rotation to the left
              >>           for circular rotation to the right
              +            for concatenation
              intValue()   for returning the integer value 
              divide_into_two
              permute
              unpermute
              pad_from_left
              pad_from_right
              read_bits_from_file
              write_to_file
              read_bits_from_fileobject
              write_bits_to_fileobject




    CONSTRUCTING BIT VECTORS:


        You can construct a bit vector in six different ways.
   
        (1) You can construct a bit vector directly from either a tuple
            or a list of bits, as in

               bv =  BitVector( bitlist = [1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1] )   
 
        (2) You can construct a bit vector from an integer by

               bv =  BitVector( intVal = 56789 )

            The bits stored now will correspond to the binary
            representation of the integer.

        (3) You can create a zero-initialized bit vector of a given size
            by

               bv  = BitVector( size = 62 )

            This bit vector will hold exactly 62 bits, all initialized to
            the 0 bit value.

        (4) You can construct a bit vector from a disk file by a two-step
            procedure. First you construct an instance of bit vector by
   
               bv  =  BitVector( filename = 'somefile' )   

            This bit vector itself is incapable of holding the bits.  To
            now create bit vectors that actually hold the bits, you need
            to make the following sort of a call on the above variable
            bv:
 
               bv1 =  bv.read_bits_from_file( 64 )    

            bv1 will be a regular bit vector containing 64 bits from the
            disk file. If you want to re-read a file from the beginning
            for some reason, you must obviously first close the file
            object that was acquired with a call to the BitVector
            constructor with a filename argument.  This can be
            accomplished by

              bv.close_file_object()

        (5) You can construct a bit vector from a string of 1's and 0's
            by
 
               bv  =  BitVector( bitstring = '110011110000' )      
   
        (6) Yet another way to construct a bit vector is to read the bits
            directly from a file-like object, as in
  
               x = "111100001111"
               fileobj = StringIO.StringIO( x )
               bv = BitVector( fp = fileobj )


   

    DISPLAYING BIT VECTORS:


        Since the BitVector class implements the __str__ method, a
        bit vector can be displayed on a terminal by

              print bitvec

        Basically, you can always obtain the string representation
        of a bit vector by

              str( bitvec )

        and integer value by

              int( bitvec )



    ACCESSING AND SETTING INDIVIDUAL BITS AND SLICES:

   
        Any single bit of a bit vector bv can be set to 1 or 0 by

              bv[M] = 1_or_0
              print bv[M]

        for accessing (and setting) the bit at the position that is
        indexed M.  You can retrieve the bit at position M by bv[M].

        A slice of a bit vector obtained by

              bv[i:j]

        is a bit vector constructed from the bits at index positions
        from i through j-1.

        You can iterate over a bit vector, as illustrated by

              for item in bitvec:
                  print item,   

        Negative subscripts for array-like indexing are supported.
        Therefore,

              bitvec[ -i ]

        is legal assuming that the index range is not violated.



    LOGICAL OPERATIONS ON BIT VECTORS:
   
        Given two bit vectors bv1 and bv2, you can perform bitwise
        logical operations on them by

               result_bv  =  bv1 ^ bv2
               result_bv  =  bv1 & bv2
               result_bv  =  bv1 | bv2
               result_bv  =  ~bv1



    COMPARING BIT VECTORS:

        Given two bit vectors bv1 and bv2, you can carry out the
        following comparisons that return Boolean values:

               bv1 ==  bv2
               bv1 !=  bv2
               bv1 <   bv2
               bv1 <=  bv2
               bv1 >   bv2
               bv1 >=  bv2

        The equalities and inequalities are determined by the integer
        values associated with the bit vectors.


   

    OTHER SUPPORTED OPERATIONS:

   
        (1)  You can permute and un-permute bit vectors:

                 bv_permuted     =  bv.permute( permutation_list )

                 bv_unpermuted   =  bv.unpermute( permutation_list )


        (2)  Left and right circular rotations can be carried out by
 
                 bitvec  << N 

                 bitvec  >> N

             for circular rotations to the left and right by N bit
             positions.


        (3)  A bit vector containing an even number of bits can be
             divided into two equal parts by

                [left_half, right_half] = bitvec.divide_into_two()

             where left_half and right_half hold references to the two
             returned bit vectors.


        (4)  You can find the integer value of a bit array by

                 bitvec.invValue()

            or by

                 int( bitvec )


        (5)  You can convert a bit vector into its string representation
             by

                  str( bitvec )


        (6)  Because __add__ is supplied, you can always join two
             bit vectors by

                  bitvec3  =  bitvec1  +  bitvec2

             bitvec3 is a new bit vector that contains all the
             bits of bitvec1 followed by all the bits of bitvec2.

             
        (7)  You can write a bit vector directly to a file, as
             illustrated by the following example that reads one bit
             vector from a file and then writes it to another
             file

                bv = BitVector( filename = 'input.txt' )
                bv1 = bv.read_bits_from_file(64)        
                print bv1           
                FILEOUT = open( 'output.txt', 'w' )
                bv1.write_to_file( FILEOUT )
                FILEOUT.close()

             IMPORTANT:  The size of bit vector must be a multiple of
                         of 8 for this write function to work.  If this
                         condition is not met, the function throws an
                         exception.

        (8)  You can also write a bit vector directly to a stream
             object, as illustrated by

                fp_write = StringIO.StringIO()
                bitvec.write_bits_to_fileobject( fp_write )
                print fp_write.getvalue()         # 111100001111