BitVector (version 1.2, 2006-Mar-14)

BitVector.py
 
Version: 1.2
 
Author: Avinash Kak (kak@purdue.edu)
 
Date: 2006-Mar-14
 
 


Download Version 1.2 
 
gztar
 
bztar


View version 1.2 code in browser

Switch to Version 1.3

Switch to Version 1.3.1


Switch to Version 1.3.2 

           

Switch to Version 1.4


 
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 
         
 
    (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 & Sons, New York, 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, 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.)

 
Modules
       
array
exceptions
operator
sys

 
Classes
       
BitVectorIterator
__builtin__.object
BitVector

 
class BitVector(__builtin__.object)
     Methods defined here:
__add__(self, other)
# 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:
__and__(self, other)
# 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.
__eq__(self, other)
# Compare two bit vectors:
__ge__(self, other)
__getitem__ = _getbit(self, posn)
__getslice__(self, i, j)
# Allow slicing with [i:j], [:], etc.
__gt__(self, other)
__init__(self, *args, **kwargs)
__int__ = intValue(self)
__invert__(self)
# Invert the bits in the bit vector on which the method is
# invoked and return the result as a new bit vector.
__iter__(self)
# To allow iterations over a bit vector:
__le__(self, other)
__len__ = _getsize(self)
__lshift__(self, n)
# For an in-place left circular shift by n bit positions:
__lt__(self, other)
__ne__(self, other)
__or__(self, other)
# 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.
__rshift__(self, n)
# For an in-place right circular shift by n bit positions:
__setitem__ = _setbit(self, posn, val)
__str__(self)
# To create a print representation
__xor__(self, other)
# 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.
circular_rot_left(self)
# 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.
circular_rot_right(self)
# 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.
circular_rotate_left_by_one(self)
# For a one-bit in-place left circular shift:
circular_rotate_right_by_one(self)
# For a one-bit in-place right circular shift:
close_file_object(self)
# For closing a file object that was used for reading
# the bits into one or more BitVector objects
divide_into_two(self)
# Divides an even-sized bit vector into two and returns
# the two halves as a list of two bit vectors.
intValue(self)
# Return the integer value of a bitvector:
pad_from_left(self, n)
# Pad a bit vector with n zeros from the left
pad_from_right(self, n)
# Pad a bit vector with n zeros from the right
permute(self, permute_list)
# Permute a bit vector according to the indices shown in the
# second argument list.  Return the permuted bit vector as a
# new bit vector.
read_bits_from_file(self, blocksize)
# 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.
read_bits_from_fileobject(self, fp)
# This function is meant to read a bit string from a
# file like object.
unpermute(self, permute_list)
# 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.
write_bits_to_fileobject(self, fp)
# 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.
write_to_file(self, file_out)
# (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)

Data and other attributes defined here:
__dict__ = <dictproxy object>
dictionary for instance variables (if defined)
__weakref__ = <attribute '__weakref__' of 'BitVector' objects>
list of weak references to the object (if defined)

 
class BitVectorIterator
     Methods defined here:
__init__(self, bitvec)
__iter__(self)
next(self)

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