Python: module Bit2DArray
 
 
Bit2DArray (version 2.0, 2011-March-20)


     NOTE:   The module Bit2DArray has been renamed BitArray2D in response to user requests.
             If you would like to use this software under its new name, click here


    Bit2DArray.py
 
    Version: 2.0        (Works with both Python 2.x and Python 3.x)
 
    Author: Avinash Kak (kak@purdue.edu)
 
    Date: 2011-March-20
 
 
    Download Version 2.0   gztar   bztar

 
    View version 2.0 code in browser 



    CHANGE LOG:
 
      Version 2.0:
 
          This is a Python 3.x compliant version of the Bit2DArray module.
          This version should work 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 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 = 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.
 
            The following call will return an empty Bit2DArray instance:
 
                ba = Bit2DArray( rows=0, columns=0 )
 
        (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)  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 Bit2DArray ba.  This assumes that you
            have specifically imported the name 'godel' from the Bit2DArray
            module.  If that is not the case, the above call will look like
 
                  bit = ba[ Bit2DArray.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 Bit2DArray 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 = Bit2DArray( 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 Bit2DArray 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 = 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
 
       (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 = Bit2DArray( 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 = 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
        from Bit2DArray import godel
        
        print(" Constructing an empty 2D bit array:")
        ba = Bit2DArray.Bit2DArray( rows=0, columns=0 )
        print(ba)
        
        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
110
111" )
        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 = Bit2DArray.Bit2DArray( 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 = Bit2DArray.Bit2DArray( 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 Bit2DArrayDemo.py file in the
         Examples sub-directory.)

 
Imported Modules
       
BitVector
re

 
Classes
       
__builtin__.object
Bit2DArray

 
class Bit2DArray(__builtin__.object)
     Methods defined here:
__and__(self, other)
Take a bitwise 'AND' of the bit array on which the method is
invoked with the argument bit array.  Return the result as a new
bit array.
__eq__(self, other)
__getitem__(self, pos)
Get the bit from the designated position
__getslice__(self, arg1, arg2)
A slice of a 2D array is defined as a rectangular region whose one
corner is at the (i,j) coordinates, which is represented by the
mapped integer arg1 produced by calling godel(i,j). The other
corner of the slice is at the coordinates (k,l) that is represented
by the integer arg2 produced by calling godel(k,l).  The slice is
returned as a new Bit2DArray instance.
__init__(self, *args, **kwargs)
__invert__(self)
Invert the bits in the bit array on which the method is invoked
and return the result as a new bit array.
__ne__(self, other)
__or__(self, other)
Take a bitwise 'OR' of the bit array on which the method is
invoked with the argument bit array.  Return the result as a new
bit array.
__setitem__(self, pos, item)
This is needed for both slice assignments and for index-based
assignments.  It checks the type of pos and item to see if the call
is for slice assignment.  For slice assignment, the second argument
must be of type slice '[m:n]' whose two numbers m and n are
produced by calling godel() on the two corners of the rectangular
regions whose values you want to set by calling this function.  So
for slice assignments, think of pos as consisting of
'[(i,j):(k,l)]' where (i,j) defines one corner of the slice and
(k,l) the other slice.  As you would expect, for slice assignments,
the argument item must of type Bit2DArray.  For index-based
assignment, the pos consists of the tuple (i,j), the point in the
array where you want to change the value.  Again, for index-based
assignment, the last argument will either be 1 or 0.
__str__(self)
To create a print representation
__xor__(self, other)
Take a bitwise 'XOR' of the bit array on which the method is
invoked with the argument bit array.  Return the result as a new
bit array.
deep_copy(self)
Make a deep copy of a bit array
dilate(self, m)
erode(self, m)
read_bit_array_from_binary_file(self, rows, columns)
This assumes that the bit array is stored in the form of ASCII
characters 1 and 0 in a text file. We further assume that the
different rows are separated by the newline character.
read_bit_array_from_char_file(self)
This assumes that the bit array is stored in the form of
ASCII characters 1 and 0 in a text file. We further assume
that the different rows are separated by the newline character.
shift(self, rowshift, colshift)
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.
size(self)
write_bit_array_to_char_file(self, file_out)
Note that this write function for depositing a bit array into
text file uses the newline as the row delimiter.
write_bit_array_to_packed_binary_file(self, file_out)
This creates a packed disk storage for your bit array.  But for
this to work, the total number of bits in your bit array must be a
multiple of 8 since all file I/O is byte oriented.  Also note that
now you cannot use any byte as a row delimiter.  So when reading
such a file back into a bit array, you have to tell the read
function how many rows and columns to create.

Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

 
Functions
       
godel(i, j)
ungodel(m)

 
Data
        __author__ = 'Avinash Kak (kak@purdue.edu)'
__copyright__ = '(C) 2011 Avinash Kak. Python Software Foundation.'
__date__ = '2011-March-20'
__url__ = 'http://RVL4.ecn.purdue.edu/~kak/distBit2DArray/Bit2DArray-2.0.html'
__version__ = '2.0'
bitvector_version = '3.0'

 
Author
        Avinash Kak (kak@purdue.edu)