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 | ||||||
|
Classes | ||||||||||||||
|
Data | ||
__date__ = '2006-Mar-14' __version__ = '1.2' |