BitVector (version 1.5.1, 2008-September-4)

BitVector.py
 
Version: 1.5.1
 
Author: Avinash Kak (kak@purdue.edu)
 
Date: 2008-September-4
 
Download Version 1.5.1   gztar   bztar

 
View version 1.5.1 code in browser 
 
Switch to Version 2.0
Switch to Version 2.0.1
Switch to Version 2.1


 
CHANGE LOG:
 
   Version 1.5.1:
 
       Removed a bug from the implementation of the right
       circular shift operator.
 
   Version 1.5:
 
       This version should prove to be much more efficient
       for long bit vectors.  Efficiency in BitVector 
       construction when only its size is specified was 
       achieved by eliminating calls to _setbit().  
       The application of logical operators to two
       BitVectors of equal length was also made efficient 
       by eliminating calls to the padding function.
       Another feature of this version is the count_bits()
       method that returns the total number of bits set
       in a BitVector instance.  Yet another feature of
       this version is the setValue() method that alters
       the bit pattern associated with a previously 
       constructed BitVector.
   
   Version 1.4.1:
 
       The reset() method now returns 'self' to allow for
       cascaded inovocation with the slicing operator.
       Also removed the discrepancy between the value of the
       __copyright__ variable in the module and the value of
      license variable in setup.py.
 
   Version 1.4:
 
       This version includes the following two upgrades: 
       1) code for slice assignment; and 2) A reset function 
       to reinitialize a previously constructed BitVector.  
       Additionally, the code was cleaned up with the help of 
       pychecker.
 
   Version 1.3.2:
 
       Fixed a potentially misleading documentation issue for
       the Windows users of the BitVector class.  If you are 
       writing an internally generated BitVector to a disk file, 
       you must open the file in the binary mode.  If you don't,
       the bit patterns that correspond to line breaks will be
       misinterpreted.  On a Windows machine in the text mode,
       the bit pattern 000001010 ('\n') will be written out
       to the disk as 0000110100001010 ('\r\n').
 
   Version 1.3.1:
 
       Removed the inconsistency in the internal representation
       of bit vectors produced by logical bitwise operations
       vis-a-vis the bit vectors created by the constructor.
       Previously, the logical bitwise operations resulted in bit 
       vectors that had their bits packed into lists of ints, 
       as opposed to arrays of unsigned shorts. 
 
   Version 1.3:
 
       (a) One more constructor mode included: When initializing
       a new bit vector with an integer value, you can now also
       specify a size for the bit vector.  The constructor 
       zero-pads the bit vector from the left with zeros. (b) The 
       BitVector class now supports 'if x in y' syntax to test if 
       the bit pattern 'x' is contained in the bit pattern 'y'. 
       (c) Improved syntax to conform to well-established Python 
       idioms. (d) What used to be a comment before the beginning 
       of each method definition is now a docstring.
 
   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.
   
 
 
INSTALLATION:
 
   The BitVector class has been packaged using Distutils.  
   For installation, execute the following command-line in the 
   source directory (this is the directory that contains the 
   setup.py file after you have downloaded and uncompressed the 
   package):
 
       python setup.py install
 
   You have to have root privileges for this to work.  On Linux 
   distributions, this will install the module file at a location 
   that looks like
 
        /usr/lib/python2.5/site-packages/
 
   If you do not have root access, you have the option of 
   working directly off the directory in which you downloaded 
   the software by simply placing the following statements at 
   the top of your scripts that use the BitVector class
 
       import sys
       sys.path.append( "pathname_to_BitVector_directory" )
 
   To uninstall the module, simply delete the source directory,
   locate where BitVector was installed with "locate BitVector"
   and delete those files.  As mentioned above, the full 
   pathname to the installed version is likely to look like
   /usr/lib/python2.5/site-packages/BitVector*
 
   If you want to carry out a non-standard install of BitVector,
   look up the on-line information on Disutils by pointing your
   browser to 
 
          http://docs.python.org/dist/dist.html
 
 
 
 
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__
          __contains__
          __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
          reset
          slice assignment
          count_bits
          setValue
 
 
 
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.  The resulting bit vector is
        the shortest possible bit vector for the integer value
        supplied.  For example, when intVal is 0, the bit vector
        constructed will consist of just the bit 0.
 
 
    (3) When initializing a bit vector with an intVal as shown
        above, you can also specify a size for the bit vector:
 
           bv = BitVector( intVal = 0, size = 8 )
 
        will return the bit vector consisting of the bit pattern
        00000000.  The zero padding needed for meeting the size
        requirement is always on the left.  If the size supplied is
        smaller than what it takes to create the shortest possible
        bit vector for intVal, an exception is thrown.
 
            
    (4) 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.
 
    (5) 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()
 
    (6) You can construct a bit vector from a string of 1's and 0's
        by
 
           bv  =  BitVector( bitstring = '110011110000' )      
 
    (7) 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 )
 
 
 
OPERATIONS SUPPORTED BY THE BITVECTOR CLASS:
 
DISPLAYING BIT VECTORS:
 
 
    1)  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:
 
 
    2)  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].
 
    3)  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.
 
    4)  You can also carry out slice assignment:
 
              bv1 = BitVector( size = 25 )
              bv2 = BitVector( bitstring = '1010001' )
              bv1[6:9]  = bv2[0:3]
              bv3 = BitVector( bitstring = '101' )                 
              bv1[0:3]  = bv3
 
        The first slice assignment will set the 6th, 7th, and 
        the 8th bits of the bit vector bv1 according to the first
        three bits of bv2.  The second slice assignment will set
        the first three bits of bv1 according to the three bits
        in bv3.
 
    5)  You can iterate over a bit vector, as illustrated by
 
              for bit in bitvec:
                  print bit,   
 
        This is made possible by the override definition for the
        special __iter__() method.
 
    6)  Negative subscripts for array-like indexing are supported.
        Therefore,
 
              bitvec[ -i ]
 
        is legal assuming that the index range is not violated.
 
    7)  You can reset a previously constructed bit vector to
        either the all zeros state or the all ones state by
 
              bv1 = BitVector( size = 25 )
              ...
              ...
              bv1.reset( 1 )
              ...
              ...
              bv1.reset( 0 )
 
        The first call to reset() will set all the bits of
        bv1 to 1's and the second call all bit to 0's.
 
 
 
LOGICAL OPERATIONS ON BIT VECTORS:
 
 
    8) 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:
 
    9) 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:
 
 
   10)  You can permute and un-permute bit vectors:
 
              bv_permuted   =  bv.permute( permutation_list )
 
              bv_unpermuted =  bv.unpermute( permutation_list )
 
 
   11)  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.
 
 
   12)  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.
 
 
   13)  You can find the integer value of a bit array by
 
              bitvec.invValue()
 
        or by
 
              int( bitvec )
 
 
   14)  You can convert a bit vector into its string representation
        by
 
              str( bitvec )
 
 
   15)  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.
 
         
   16)  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.bits', 'wb' )
              bv1.write_to_file( FILEOUT )
              FILEOUT.close()
              bv = BitVector( filename = 'output.bits' )
              bv2 = bv.read_bits_from_file( 64 )
              print bv2
 
         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.
 
         IMPORTANT FOR WINDOWS USERS:  When writing an internally
                     generated bit vector out to a disk file, it
                     is important to open the file in the binary
                     mode as shown.  Otherwise, the bit pattern
                     00001010 ('\n') in your bitstring will be written 
                     out as 0000110100001010 ('\r\n'), which is the
                     linebreak on Windows machine.
 
   17)  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 
         
 
   18)  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.
 
   19)  You can test if a bit vector x is contained in another bit
        vector y by using the syntax 'if x in y'.  This is made
        possible by the override definition for the special
        __contains__() method.
 
   20)  You can count the number of bits set in a BitVector 
        instance by
 
          bv = BitVector( bitstring = '100111' )
          print bv.count_bits()                     # 4
 
   21)  You can change the bit pattern associated with a
        previously constructed BitVector instance:
 
          bv = BitVector( intVal = 7, size =16 )
          print bv                              # 0000000000000111
          bv.setValue( intVal = 45 )
          print bv                              # 101101
          
 
 
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 (A70) of the file
    BitVector.py), the very first thing that the constructor does is
    to figure out in line (A78) 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 (A78)
    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
    (A79) then creates an array of 2-byte ints and initializes it
    with the required number of zeros.  Lines (A80) 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 (A77) of the file
    BitVector.py, note that, except for one case, the constructor
    must be called with a single keyword argument, which determines
    how the bit vector will be constructed.  The single exception to
    this rule is for the keyword argument 'intVal' which can be used
    along with the 'size' keyword argument.  When 'intVal' is used
    with the 'size' option, the bit vector constructed for the
    integer is the shortest possible bit vector.  On the other hand,
    when 'size' is also specified, the bit vector is padded with
    zeroes from the left so that it has the specified size.
 
    Lines (A16) through (A22) are for the following sort of a call
 
           bv = BitVector( filename = 'myfilename' )
 
    This call 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 (A23) through (A28) 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 (A29) through (A61) 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.  The bit vector
    constructed with the above call will be the shortest possible
    bit vector for the integer supplied.  As a case in point, when
    the intVal is 0, the bit vector will consist of a single bit
    which will be 0 also.  The code in lines (A27) through (A59) can
    also handle the following sort of a call
 
          bv = BitVector( intVal = 46, size = 16 )        
 
    which returns a bit vector of a specfic size by padding the
    shortest possible bit vector the the intVal with zeros from the
    left.
    
    Lines (A62) through (A68) 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 (A69) through (A73) are for constructing a bit vector from
    a bitstring, as in
 
          bv = BitVector( bitstring = '00110011111' )
 
    Finally, lines (A74) through (A77) 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) )
 
    The bit vector constructed is initialized 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.
 
    With regard to the changes incorporated in Version 1.3, thanks
    are owed to Kurt Schwehr and Gabriel Ricardo for bringing to my
    attention the bug related to the intVal method of initializing a
    bit vector when the value of intVal exceeded sys.maxint. This
    problem is fixed in Version 1.3.  Version 1.3 also includes many
    other improvements that make the syntax better conform to the
    standard idioms of Python.  These changes and the addition of
    the new constructor mode (that allows a bit vector of a given
    size to be constructed from an integer value) are also owing to
    Kurt's suggestions.
 
    With regard to the changes incorporated in Version 1.3.1, I
    would like to thank Michael Haggerty for noticing that the
    bitwise logical operators resulted in bit vectors that had their
    bits packed into lists of ints, as opposed to arrays of 
    unsigned shorts.  This inconsistency in representation has been 
    removed in version 1.3.1.  Michael has also suggested that 
    since BitVector is mutable, I should be overloading __iand__(), 
    __ior__(), etc., for in-place modifications of bit vectors.  
    Michael certainly makes a good point. But I am afraid that this 
    change will break the code for the existing users of the 
    BitVector class. 
 
    I thank Mathieu Roy for bringing to my attention the problem
    with writing bitstrings out to a disk files on Windows 
    machines.  This turned out to be a problem more with the
    documentation than with the BitVector class itself.  On a 
    Windows machine, it is particularly important that a file
    you are writing a bitstring into be opened in binary mode
    since otherwise the bit pattern 00001010 ('\n') will be written 
    out as 0000110100001010 ('\r\n').  This documentation fix 
    resulted in Version 1.3.2.
 
    With regard to Version 1.4, the suggestions/bug reports
    made by John Kominek, Bob Morse, and Steve Ward contributed
    to this version.  I wish to thank all three. John wanted me 
    to equip the class with a reset() method so that a previously
    constructed class could be reset to either all 0's or all
    1's. Bob spotted loose local variables in the implementation
    --- presumably left over from a debugging phase of the code.
    Bob recommended that I clean up the code with pychecker. That
    has been done.  Steve noticed that slice assignment was not
    working.  It should work now.
 
    Version 1.4.1 was prompted by John Kominek suggesting that
    if reset() returned self, then the slice operation could
    be combined with the reset operation.  Thanks John!  Another
    reason for 1.4.1 was to remove the discrepancy between the 
    value of the __copyright__ variable in the module and the 
    value of license variable in setup.py.  This discrepancy 
    was brought to my attention by David Eyk.  Thanks David!
 
    Version 1.5 has benefited greatly by the suggestions made
    by Ryan Cox.  By examining the BitVector execution with
    cProfile, Ryan observed that my implementation was making
    unnecessary method calls to _setbit() when just the size
    option is used for constructing a BitVector instance.
    Since Python allocates cleaned up memory, it is unnecessary 
    to set the individual bits of a vector if it is known in 
    advance that they are all zero. Ryan made a similar observation 
    for the logical operations applied to two BitVector instances 
    of equal length.  He noticed that I was making unnecessary 
    calls to _resize_pad_from_left() for the case of equal 
    arguments to logical operations.  Ryan also recommended that 
    I include a method that returns the total number of bits 
    set in a BitVector instance.  The new method count_bits() does 
    exactly that. Thanks Ryan for all your suggestions.
    Version 1.5 also includes the method setValue() that allows 
    the internally stored bit pattern associated with a previously
    constructed BitVector to be changed.  A need for this method
    was expressed by Aleix Conchillo.  Thanks Aleix.
    
    Version 1.5.1 is a quick release to fix a bug in the 
    right circular shift operator.  This bug was discovered
    by Jasper Spaans.  Thanks very much Jasper.
 
 
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.  Further information on the book is available at
    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 bit vector of a given size from a given
    # integer:
    bv = BitVector( intVal = 45, size = 16 )
    print bv                                # 0000000000101101
 
    # 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 bitwise 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
 
    # Try 'if x in y' syntax for bit vectors:
    bv1 = BitVector( bitstring = '0011001100' )
    bv2 = BitVector( bitstring = '110011' )
    if bv2 in bv1:
        print "%s is in %s" % (bv2, bv1)
    else:
        print "%s is not in %s" % (bv2, bv1)
 
    .....
    .....
 
    (For a more complete working example, see the example code in
     the BitVectorDemo.py file in the Examples sub-directory.)

 
Modules
       
array
operator

 
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 zeros from the left.
__contains__(self, otherBitVec)
This supports 'if x in y' and 'if x not in y'
syntax for bit vectors.
__eq__(self, other)
__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 by supporting the
'for bit in bit_vector' syntax:
__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__(self, pos, item)
This is needed for both slice assignments and for 
index assignments.  It checks the types of pos and item
to see if the call is for slice assignment.  For slice
assignment, pos must be of type 'slice' and item of 
type BitVector.  For index assignment, the argument types
are checked in the _setbit() method.
__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 zeros 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.
count_bits(self)
Return the number of bits set in a BitVector instance.
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
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.
reset(self, val)
Resets a previously created BitVector to either all
zeros or all ones depending on the argument val.
Returns self to allow for syntax like
       bv = bv1[3:6].reset(1)
or
       bv = bv1[:].reset(1)
setValue(self, *args, **kwargs)
Changes the bit pattern associated with a previously
constructed BitVector instance.  The allowable modes
for chaning the internally stored bit patten are the
same as for the constructor.
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 descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

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

 
Data
        __author__ = 'Avinash Kak (kak@purdue.edu)'
__copyright__ = '(C) 2008 Avinash Kak. Python Software Foundation.'
__date__ = '2008-September-4'
__url__ = 'http://RVL4.ecn.purdue.edu/~kak/dist/BitVector-1.5.1.html'
__version__ = '1.5.1'

 
Author
        Avinash Kak (kak@purdue.edu)