Bit2DArray (version 1.0, 2011-March-13) |
Bit2DArray.py
Version: 1.0
Author: Avinash Kak (kak@purdue.edu)
Date: 2011-March-13
Download Version 1.0
gztar
bztar
View version 1.0 code in browser
Switch to Version 2.0 (Version 2.0 works with both Python 2.x and Python 3.x)
INSTALLATION:
The Bit2DArray class was 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 tar archive):
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.6/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 Bit2DArray class
import sys
sys.path.append( "pathname_to_Bit2DArray_directory" )
To uninstall the module, simply delete the source directory, locate
where Bit2DArray was installed with "locate Bit2DArray" and delete
those files. As mentioned above, the full pathname to the installed
version is likely to look like
/usr/lib/python2.6/site-packages/Bit2DArray*
If you want to carry out a non-standard install of Bit2DArray, look
up the on-line information on Disutils by pointing your browser to
http://docs.python.org/dist/dist.html
INTRODUCTION:
The Bit2DArray class is for a memory-efficient packed representation
of 2D bit arrays and for logical operations on such arrays. The
implementation of the class takes advantage of the facilities of the
BitVector class for the memory representation and for logical
operations.
Operations supported on 2D bit arrays:
__str__
__getitem__
__setitem__
__getslice__
__eq__
__ne__
__and__
__or__
__xor__
__invert__
deep_copy
size
read_bit_array_from_char_file
read_bit_array_from_binary_file
write_bit_array_to_char_file
write_bit_array_to_packed_binary_file
shift
dilate
erode
CONSTRUCTING 2D BIT ARRAYS:
You can construct a 2D bit array in four different ways:
(1) You can construct a packed 2D bit array of all zeros by a
call like
ba = Bit2DArray( rows = 20, columns = 10 )
This will create a 2D array of size 20x10. You can then set
the individual bits in this array using syntax that is shown
later in this documentation.
(2) You can construct a 2D bit array from a string in the following
manner:
ba = Bit2DArray( bitstring = "111\n110\n011"
)
This will create the following bit array in the memory:
111
110
011
There is no limit on the either the row size or the column size
of the bit array created in this manner. However, the rows
must all be of exactly the same size. An exception is thrown
when that condition is violated.
Note that even though you are supplying to the Bit2DArray
constructor a string made of ASCII 1's and 0's, the 2D bit
array that is created is stored in a packed form. So a row
with, say, sixteen 1's and/or 0's will be stored as just two
bytes in the memory. So a 16x16 bit array will occupy only
32 bytes in the memory.
(3) You can create a 2D bit array by reading the bits directly from
a text file by calls that look like
ba = Bit2DArray( filename = "data.txt" )
ba.read_bit_array_from_char_file()
You first have to create an empty Bit2DArray instance, as in
the first statement above, and then call the method
read_bit_array_from_char_file() on the instance.
Even though the text file supplies ASCII 1's and 0's, the
internal representation of the bit array will be packed, as
mentioned for the case (2) above.
Note that when you create a bit array in this manner, the
newline character in the text file is used as a row delimiter.
(4) You can create a 2D bit array by reading the bits directly from
a binary file through calls like:
ba = Bit2DArray( filename = "data_binary.dat" )
ba.read_bit_array_from_binary_file(rows = 5, cols = 8)
Since you are creating a bit array from a binary file, you
cannot designate any particular byte as a row delimiter. That's
the reason for why you must now specify the number of rows and
the number of columns to the read method in the second
statement. If the number of bits in the binary file is less
than what you need for the 2D bit array in the second statement
above, an exception is thrown.
To illustre creating a bit array by reading a file in the binary
mode, assume that the file has the characters 'hello' in it
and you read this file into a bit array by calling:
ba = Bit2DArray( filename = "hello_file.dat" )
ba.read_bit_array_from_binary_file(rows = 5, cols = 8)
If you now say
print ba
you will see the following array displayed in your terminal
window:
01101000
01100101
01101100
01101100
01101111
These are the ASCII representations of the characters 'h', 'e',
'l', 'l', and 'o'.
OPERATIONS SUPPORTED BY THE Bit2DArray CLASS:
DISPLAYING BIT ARRAYS:
(5) Since the Bit2DArray class implements the __str__ method, a bit
array can be displayed in a terminal window by
print ba
where ba is an instance of Bit2DArray. This will display in
your terminal window the bit array ba, with each row of the
array in a separate line. (Obviously, this is not what you
would do for very large bit arrays. But, for diagnostic work,
such displays can be very helpful.) You can always obtain the
string representation of a bit array by
str( ba )
In the string representation, the rows are separated by the
newline character.
ACCESSING AND SETTING INDIVIDUAL BITS AND SLICES:
(6) Any single bit of a bit array ba at row index i and column index
j can be set to 1 or 0 by
ba[i,j] = 1_or_0
print ba[i,j]
As shown by the second statement, you can directly retrieve the
bit at any position in the array simply by indexing to it. The
call in the first statement is handled by the __setitem__ method
and the call in the second by __getitem__.
(7) A slice of a bit array, defined by the corner coordinates (i,j)
and (k,l), can be retrieved by
ba[ godel(i,j) : godel(k,l) ]
where godel(a,b) is used to map a pair of integers into a unique
integer with the help of the Godel pairing formula. In the
implementation of the __getslice__ method that handles the above
invocation, calls to ungodel(m) are used to recover the
components i and j of a pair whose Godel map is m. To demonstrate
the working of slice retrieval:
ba1 = Bit2DArray( bitstring = "111111\n110111\n111111\n111111\n111111\n111111"
)
ba2 = ba3[godel(2,3) : godel(4,5)]
print ba4
yields
11
11
(8) You can also carry out slice assignment by using syntax like
ba1[ godel(i,j) : godel(k,l) ] = ba2
where the 2D bit array ba1 is presumably larger than the 2D bit
array ba2. The above call will replace the rectangular region
of ba1 that is defined by the corner coordinates (i,j) and
(k,l) by the bit array ba2, assuming that that the row width of
ba2 is (k-i) and the column width (l-j). So in a call like
ba1 = Bit2DArray( bitstring = "101\n110\n111"
) # 101
# 110
# 111
ba2 = Bit2DArray( rows = 5, columns = 5 ) # 00000
# 00000
# 00000
# 00000
# 00000
ba2[ godel(2, 2+ba2.rows) : godel(2,2+ba2.columns) ] = ba1
print ba2 # 00000
# 00000
# 00101
# 00110
# 00111
(9) You can construct a deep copy of a bit array by
ba2 = ba1.deep_copy()
The bit array in ba2 will exactly the same as in ba1, except
that the two bit arrays will be two different objects in the
memory.
LOGICAL OPERATIONS ON 2D BIT ARRAYS:
(10) You can carry out all of the logical operations on 2D bit arrays:
result_ba = ba1 & ba2 # for bitwise AND
result_ba = ba1 | ba2 # for bitwise OR
result_ba = ba1 ^ ba2 # for bitwise XOR
result_ba = ~ ba # for bitwise negation
COMPARING 2D BIT ARRAYS:
(11) Given two 2D bit arrays, you can test for equality and inequality
through the following boolean comparisons:
ba1 == ba2
ba1 != ba2
OTHER SUPPORTED OPERATIONS:
(12) You can shift a bit array array by
ba.shift( rowshift = m, colshift = n )
where m is the number of positions row-wise by which you
want to shift the array and the n the same column-wise.
The values for m and n are allowed to be negative. A positive
value for m will cause a bit array to shift downwards and a
positive value for n to shift rightwards.
What may make this method confusing at the beginning is the
orientation of the positive row direction and the positive
column direction. The origin of the array is at the upper left
hand corner of your display. Rows are positive going downwards
and columns are positive going rightwards:
X-----> +ve col direction
|
|
|
V
+ve row direction
So a positive value for rowshift will shift the array downwards
and a positive value for colshift will shift it rightwards.
Just remember that if you want the shifts to seem more
intuitive, use negative values for the rowshift argument.
(13) In order to patch small holes, you can dilate the blobs made up
of 1's that are connected through neighborhood relationship by
calling dilate():
result_ba = ba.dilate( m )
The returned bit array is an OR of the bit arrays obtained by
shifting ba by m positions in all four cardinal directions.
(14) The opposite of dilate is erode. An erosion operation should
shrink the blobs by the deletion of 1's that are at the boundary
up to a depth determined by the argument supplied to erode():
result_ba = ba.erode(m)
Logically, the array returned by the above call is an AND of
the the bit arrays obtained by shifting ba by m positions in
each of the four cardinal directions.
(15) You can write a bit array directly to a text file if you want
the bits to be written out as ASCII 1's and 0's:
ba.write_bit_array_to_char_file("out_file.txt")
This can be a useful thing to do when you are playing with
small to medium sized bit arrays. This call will deposit the
newline character at the end of each row of the bit array.
Subsequently, you can re-create the bit array in the memory by
reading the file with the calls
ba = Bit2DArray( filename = "filename.txt" )
ba.read_bit_array_from_char_file()
that were mentioned earlier in item (3) above.
(16) You can write a bit array in its packed binary representation
to a file (that would obviously be a binary file) by calling
ba.write_bit_array_to_packed_binary_file("filename.dat")
The overall size of bit array ba must be a multiple of 8 for
this write function to work. If this condition is not met, the
function will throw an exception.
When writing an internally generated bit array out to a disk
file, the implementation of the write function opens the file
in the binary mode. This is particularly important on Windows
machines since, if the file were to be opened in the text mode,
the bit pattern 00001010 ('\n') in a bit array will be written
out as 0000110100001010 ('\r\n').
A binary file created by the above call can be read back into
the memory by the calls shown in item (4) above:
ba = Bit2DArray( filename = "filename.dat" )
ba.read_bit_array_from_binary_file(rows = 5, cols = 8)
As mentioned in (4) above, since no bytes can serve as row
delimiters for binary files, you have to tell the read function
how many rows and columns to read off the file.
HOW A BIT ARRAY IS STORED:
Through the facilities provided by the BitVector class, the bits of
a bit array are stored in 16-bit unsigned ints.
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. Avi Kak is also the author of "Scripting
with Objects: A Comparative Presentation of Object-Oriented
Scripting with Perl and Python," published in 2008 by John-Wiley.
SOME EXAMPLE CODE:
import Bit2DArray
print "
Constructing a bit array of size 10x10 with zero bits -- ba:"
ba = Bit2DArray.Bit2DArray( rows = 10, columns = 10 )
print ba
print "
Constructing a bit array from a bit string -- ba2:"
ba2 = Bit2DArray.Bit2DArray( bitstring = "111\n110\n111"
)
print ba2
print "
Print a specific bit in the array -- bit at 1,2 in ba2:"
print ba2[1,2]
print "
Set a specific bit in the array --- set bit (0,1) of ba2:"
ba2[0,1] = 0
print ba2
print "
Experiments in slice getting and setting:"
print "Printing an array -- ba3:"
ba3 = Bit2DArray.Bit2DArray( bitstring = "111111\n110111\n111111\n111111\n111111\n111111"
)
print ba3
print
ba4 = ba3[ Bit2DArray.godel(2,3) : Bit2DArray.godel(4,5)]
print "Printing a slice of the larger array -- slice b4 of ba3:"
print ba4
(For a more complete working example, see the
example code in the Bit2DArrayDemo.py file in the
Examples sub-directory.)
Imported Modules | ||||||
|
Classes | ||||||||
|
Functions | ||
|
Data | ||
__author__ = 'Avinash Kak (kak@purdue.edu)' __copyright__ = '(C) 2011 Avinash Kak. Python Software Foundation.' __date__ = '2011-March-13' __url__ = 'http://RVL4.ecn.purdue.edu/~kak/distBit2DArray/Bit2DArray-1.0.html' __version__ = '1.0' |
Author | ||
Avinash Kak (kak@purdue.edu) |