| BitArray2D (version 2.1, 2011-March-22) |
BitArray2D.py
Version: 2.1
Author: Avinash Kak (kak@purdue.edu)
Date: 2011-March-22
Download Version 2.1
gztar
bztar
View version 2.1 code in browser
CHANGE LOG:
Version 2.1:
BitArray2D is a renamed version of Bit2DArray. This name change
was made in response to user requests. BitArray2D is Python 3.x
compliant. It should work with both Python 2.x and Python 3.x.
INSTALLATION:
The BitArray2D 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.7/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 BitArray2D class
import sys
sys.path.append( "pathname_to_BitArray2D_directory" )
To uninstall the module, simply delete the source directory, locate
where BitArray2D was installed with "locate BitArray2D" 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/BitArray2D*
If you want to carry out a non-standard install of BitArray2D, look
up the on-line information on Disutils by pointing your browser to
http://docs.python.org/dist/dist.html
INTRODUCTION:
The BitArray2D class is for a memory-efficient packed representation
of 2D bit arrays and for logical and other operations (such as blob
dilations, erosions, etc.) on such arrays. The implementation of the
class takes advantage of the facilities of the BitVector class for
the memory representation and for the allowed 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 = BitArray2D( 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.
The following call will return an empty BitArray2D instance:
ba = BitArray2D( rows=0, columns=0 )
(2) You can construct a 2D bit array from a string in the following
manner:
ba = BitArray2D( 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 BitArray2D
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 = BitArray2D( filename = "data.txt" )
ba.read_bit_array_from_char_file()
You first have to create an empty BitArray2D 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 = BitArray2D( 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 = BitArray2D( 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 BitArray2D CLASS:
DISPLAYING BIT ARRAYS:
(5) Since the BitArray2D class implements the __str__ method, a bit
array can be displayed in a terminal window by
print( ba )
where ba is an instance of BitArray2D. 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) You can access any individual bit of a 2D bit array by
bit = ba[ godel(i,j) ]
The call on the right will return the bit in the i-th row and
the j-th column of the BitArray2D ba. This assumes that you
have specifically imported the name 'godel' from the BitArray2D
module. If that is not the case, the above call will look like
bit = ba[ BitArray2D.godel(i,j) ]
The function godel(a,b) is used to map a pair of integers a and
b into a unique integer with the help of the Godel pairing
formula.
(7) 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
(8) A slice of a bit array, defined by the corner coordinates (i,j)
and (k,l), can be retrieved by
from BitArray2D import godel
ba[ godel(i,j) : godel(k,l) ]
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 = BitArray2D( bitstring = "111111\n110111\n111111\n111111\n111111\n111111" )
ba2 = ba3[godel(2,3) : godel(4,5)]
print( ba4 )
yields
11
11
(9) You can also carry out slice assignment by using syntax like
from BitArray2D import godel
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 = BitArray2D( bitstring = "101\n110\n111" ) # 101
# 110
# 111
ba2 = BitArray2D( 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
(10) 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:
(11) 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:
(12) Given two 2D bit arrays, you can test for equality and inequality
through the following boolean comparisons:
ba1 == ba2
ba1 != ba2
OTHER SUPPORTED OPERATIONS:
(13) 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.
(14) 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.
(15) 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.
(16) 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 = BitArray2D( filename = "filename.txt" )
ba.read_bit_array_from_char_file()
that were mentioned earlier in item (3) above.
(17) 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 = BitArray2D( 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 BitArray2D
from BitArray2D import godel
print("
Constructing an empty 2D bit array:")
ba = BitArray2D.BitArray2D( rows=0, columns=0 )
print(ba)
print("
Constructing a bit array of size 10x10 with zero bits -- ba:")
ba = BitArray2D.BitArray2D( rows = 10, columns = 10 )
print(ba)
print("
Constructing a bit array from a bit string -- ba2:")
ba2 = BitArray2D.BitArray2D( bitstring = "111\n110\n111" )
print(ba2)
print("
Print a specific bit in the array -- bit at 1,2 in ba2:")
print( ba2[ godel(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 = BitArray2D.BitArray2D( bitstring = "111111\n110111\n111111\n111111\n111111\n111111" )
print(ba3)
ba4 = ba3[godel(2,3) : godel(4,5)]
print("Printing a slice of the larger array -- slice b4 of ba3:")
print(ba4)
ba5 = BitArray2D.BitArray2D( rows = 5, columns = 5 )
print("
Printing an array for demonstrating slice setting:")
print(ba5)
ba5[godel(2, 2+ba2.rows) : godel(2,2+ba2.columns)] = ba2
print("
Setting a slice of the array - setting slice of ba5 to ba2:")
print(ba5)
print("
Constructing a deep copy of ba, will call it ba6:")
ba6 = ba.deep_copy()
ba6[ godel(3,3+ba2.rows) : godel(3,3+ba2.columns) ] = ba2
print("Setting a slice of the larger array -- set slice of ba6 to ba2:")
print(ba6)
(For a more complete working example, see the
example code in the BitArray2DDemo.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-22' __url__ = 'http://RVL4.ecn.purdue.edu/~kak/dist2d/BitArray2D-2.1.html' __version__ = '2.1' bitvector_version = '3.0' | ||
| Author | ||
| Avinash Kak (kak@purdue.edu) | ||