#!/usr/bin/env python

__version__ = '1.3.1'
__author__  = "Avinash Kak (kak@purdue.edu)"
__date__    = '2007-September-14'
__url__     = 'http://RVL4.ecn.purdue.edu/~kak/dist/BitVector-1.3.1.html'
__copyright__ = "(C) 2007 Avinash Kak. GNU GPL 2."


import sys
import array
import exceptions
import operator

_hexdict = { '0' : '0000', '1' : '0001', '2' : '0010', '3' : '0011',
             '4' : '0100', '5' : '0101', '6' : '0110', '7' : '0111',
             '8' : '1000', '9' : '1001', 'a' : '1010', 'b' : '1011',
             'c' : '1100', 'd' : '1101', 'e' : '1110', 'f' : '1111' }

def _readblock( blocksize, bitvector ):                              #(R1)
    '''If this function can read all blocksize bits, it peeks ahead to
    see if there is anything more to be read in the file. It uses
    tell-read-seek mechanism for this in lines (R18) through (R21).  If
    there is nothing further to be read, it sets the more_to_read
    attribute of the bitvector object to False.  Obviously, this can
    only be done for seekable streams such as those connected with disk
    files.  According to Blair Houghton, a similar feature could
    presumably be implemented for socket streams by using recv() or
    recvfrom() if you set the flags argument to MSG_PEEK.
    '''
    global hexdict                                                   #(R2)
    bitstring = ''                                                   #(R3)
    i = 0                                                            #(R4)
    while ( i < blocksize / 8 ):                                     #(R5)
        i += 1                                                       #(R6)
        byte = bitvector.FILEIN.read(1)                              #(R7)
        if byte == '':                                               #(R8)
            if len(bitstring) < blocksize:                           #(R9)
                bitvector.more_to_read = False                      #(R10)
            return bitstring                                        #(R11)
        hexvalue = hex( ord( byte ) )                               #(R12)
        hexvalue = hexvalue[2:]                                     #(R13)
        if len( hexvalue ) == 1:                                    #(R14)
            hexvalue = '0' + hexvalue                               #(R15)
        bitstring += _hexdict[ hexvalue[0] ]                        #(R16)
        bitstring += _hexdict[ hexvalue[1] ]                        #(R17)
    file_pos = bitvector.FILEIN.tell()                              #(R18)
    # peek at the next byte; moves file position only if a
    # byte is read
    next_byte = bitvector.FILEIN.read(1)                            #(R19)
    if next_byte:                                                   #(R20)
        # pretend we never read the byte                   
        bitvector.FILEIN.seek( file_pos )                           #(R21)
    else:                                                           #(R22)
        bitvector.more_to_read = False                              #(R23)
    return bitstring                                                #(R24)


#--------------------  BitVector Class Definition   ----------------------

class BitVector( object ):                                           #(A1)

    def __init__( self, *args, **kwargs ):                           #(A2)
        if args:                                                     #(A3)
               raise ValueError(                                     #(A4)
                      '''BitVector constructor can only be called
                         with keyword arguments for the following
                         keywords: filename, fp (for fileobject),
                         size, intValue, bitlist (for a list or
                         tuple of bits, or bitstring)''')
        filename = fp = intVal = size = bitlist = bitstring = None   #(A5)
        if kwargs.has_key('filename'):filename=kwargs.pop('filename')#(A6)
        if kwargs.has_key('fp'):           fp = kwargs.pop('fp')     #(A7)
        if kwargs.has_key('size'):       size = kwargs.pop('size')   #(A8)
        if kwargs.has_key('intVal'):   intVal = kwargs.pop('intVal') #(A9)
        if kwargs.has_key('bitlist'):
                               bitlist = kwargs.pop('bitlist')      #(A10)
        if kwargs.has_key('bitstring') :
                               bitstring = kwargs.pop('bitstring')  #(A11)
        self.filename = None                                        #(A12)
        self.size = 0                                               #(A13)
        
        if filename:                                                #(A14)
            if fp or size or intVal or bitlist or bitstring:        #(A15)
                raise ValueError(                                   #(A16)
                  '''When filename is specified, you cannot
                     give values to any other constructor args''')
            self.filename = filename                                #(A17)
            self.FILEIN = open( filename, 'rb' )                    #(A18)
            self.more_to_read = True                                #(A19)
            return                                                  #(A20)
        elif fp:                                                    #(A21)
            if filename or size or intVal or bitlist or bitstring:  #(A22)
                raise ValueError(                                   #(A23)
                  '''When fileobject is specified, you cannot      
                     give values to any other constructor args''')
            bits = self.read_bits_from_fileobject( fp )             #(A24)
            bitlist =  map( int, bits )                             #(A25)
            self.size = len( bitlist )                              #(A26)
        elif intVal or intVal == 0:                                 #(A27)
            if filename or fp or bitlist or bitstring:              #(A28)
                raise ValueError(                                   #(A29)
                  '''When intVal is specified, you can only give
                     a value to the 'size' constructor arg''')
            if intVal == 0:                                         #(A30)
                bitlist = [0]                                       #(A31)
                if not size:                                        #(A32)
                    self.size = 1                                   #(A33)
                else:                                               #(A34)
                    if size < len(bitlist):                         #(A35)
                        raise ValueError(                           #(A36)
                          '''The value specified for size must be
                             at least as large as for the smallest
                             bit vector possible for intVal''')
                    n = size - len(bitlist)                         #(A37)
                    bitlist = [0]*n + bitlist                       #(A38)
                    self.size = len( bitlist )                      #(A39)
            else:                                                   #(A40)
                hexVal = hex( intVal ).lower().rstrip('l')          #(A41)
                hexVal = hexVal[2:]                                 #(A42)
                if len( hexVal ) == 1:                              #(A43)
                    hexVal = '0' + hexVal                           #(A44)
                bitlist = ''.join(map(lambda x: _hexdict[x],hexVal))#(A45)
                bitlist =  map( int, bitlist )                      #(A46)
                i = 0                                               #(A47)
                while ( i < len( bitlist ) ):                       #(A48)
                    if bitlist[i] == 1: break                       #(A49)
                    i += 1                                          #(A50)
                del bitlist[0:i]                                    #(A51)
                if not size:                                        #(A52)
                    self.size = len( bitlist )                      #(A53)
                else:                                               #(A54)
                    if size < len(bitlist):                         #(A55)
                        raise ValueError(                           #(A56)
                          '''The value specified for size must be
                             at least as large as for the smallest
                             bit vector possible for intVal''')
                    n = size - len(bitlist)                         #(A57)
                    bitlist = [0]*n + bitlist                       #(A58)
                    self.size = len( bitlist )                      #(A59)
        elif size >= 0:                                             #(A60)
            if filename or fp or intVal or bitlist or bitstring:    #(A61)
                raise ValueError(                                   #(A62)
                  '''When size is specified (without an intVal),
                     you cannot give values to any other
                     constructor args''')
            self.size = size                                        #(A63)
            bitlist = tuple( [0] * size )                           #(A64)
        elif bitstring or bitstring == '':                          #(A65)
            if filename or fp or size or intVal or bitlist:         #(A66)
                raise ValueError(                                   #(A67)
                  '''When a bitstring is specified, you cannot
                     give values to any other constructor args''')
            bitlist =  map( int, list(bitstring) )                  #(A68)
            self.size = len( bitlist )                              #(A69)
        elif bitlist:                                               #(A70)
            if filename or fp or size or intVal or bitstring:       #(A71)
                raise ValueError(                                   #(A72)
                  '''When bits are specified, you cannot
                     give values to any other constructor args''')
            self.size = len( bitlist )                              #(A73)
        else:                                                       #(A74)
            raise ValueError("wrong arg(s) for constructor")        #(A75) 
        two_byte_ints_needed = (len(bitlist) + 15) // 16            #(A76)
        self.vector = array.array( 'H', [0]*two_byte_ints_needed )  #(A77)
        map( self._setbit, enumerate(bitlist), bitlist)             #(A78)


    def _setbit( self, posn, val ):                                  #(B1)
        'Set the bit at the designated position to the value shown'
        if val not in (0, 1):                                        #(B2)
            raise ValueError( "incorrect value for a bit" )          #(B3)
        if isinstance( posn, (tuple) ):                              #(B4)
            posn = posn[0]                                           #(B5)
        if  posn >= self.size or posn < -self.size:                  #(B6)
            raise ValueError( "index range error" )                  #(B7)   
        if posn < 0: posn = self.size + posn                         #(B8)
        block_index = posn // 16                                     #(B9)
        shift = posn & 15                                           #(B10)
        cv = self.vector[block_index]                               #(B11)
        if ( cv >> shift ) & 1 != val:                              #(B12)
            self.vector[block_index] = cv ^ (1 << shift)            #(B13)


    def _getbit( self, posn ):                                       #(C1)
        'Get the bit from the designated position'
        if  posn >= self.size or posn < -self.size:                  #(C2)
            raise ValueError( "index range error" )                  #(C3)   
        if posn < 0: posn = self.size + posn                         #(C4)
        return ( self.vector[posn//16] >> (posn&15) ) & 1            #(C5)


    def __xor__(self, other):                                        #(E1)
        '''
        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 zero's from the left.
        '''
        if self.size < other.size:                                   #(E2)
            bv1 = self._resize_pad_from_left(other.size - self.size) #(E3)
            bv2 = other                                              #(E4)
        else:                                                        #(E5)
            bv1 = self                                               #(E6)
            bv2 = other._resize_pad_from_left(self.size - other.size)#(E7)
        res = BitVector( size = bv1.size )                           #(E8)
        lpb = map(operator.__xor__, bv1.vector, bv2.vector)          #(E9) 
        res.vector = array.array( 'H', lpb )                        #(E10)
        return res                                                  #(E11)


    def __and__(self, other):                                        #(F1)
        '''
        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 zero's from the left.
        '''      
        if self.size < other.size:                                   #(F2)
            bv1 = self._resize_pad_from_left(other.size - self.size) #(F3)
            bv2 = other                                              #(F4)
        else:                                                        #(F5)
            bv1 = self                                               #(F6)
            bv2 = other._resize_pad_from_left(self.size - other.size)#(F7)
        res = BitVector( size = bv1.size )                           #(F8)
        lpb = map(operator.__and__, bv1.vector, bv2.vector)          #(F9) 
        res.vector = array.array( 'H', lpb )                        #(F10)
        return res                                                  #(F11)


    def __or__(self, other):                                         #(G1)
        '''
        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.
        '''
        if self.size < other.size:                                   #(G2)
            bv1 = self._resize_pad_from_left(other.size - self.size) #(G3)
            bv2 = other                                              #(G4)
        else:                                                        #(G5)
            bv1 = self                                               #(G6)
            bv2 = other._resize_pad_from_left(self.size - other.size)#(G7)
        res = BitVector( size = bv1.size )                           #(G8)
        lpb = map(operator.__or__, bv1.vector, bv2.vector)           #(G9) 
        res.vector = array.array( 'H', lpb )                        #(G10)
        return res                                                  #(G11)


    def __invert__(self):                                            #(H1)
        '''
        Invert the bits in the bit vector on which the
        method is invoked and return the result as a new
        bit vector.
        '''
        res = BitVector( size = self.size )                          #(H2)
        lpb = map( operator.__inv__, self.vector )                   #(H3) 
        res.vector = array.array( 'H' )                              #(H3)
        for i in range(len(lpb)):                                    #(H4)
            res.vector.append( lpb[i] & 0x0000FFFF )                 #(H5)
        return res                                                   #(H6)


    def __add__(self, other):                                        #(J1)
        '''
        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.
        '''
        i = 0                                                        #(J2)
        outlist = []                                                 #(J3)
        while ( i < self.size ):                                     #(J4)
            outlist.append( self[i] )                                #(J5)
            i += 1                                                   #(J6)
        i = 0                                                        #(J7)
        while ( i < other.size ):                                    #(J8)
            outlist.append( other[i] )                               #(J9)
            i += 1                                                  #(J10)
        return BitVector( bitlist = outlist )                       #(J11)


    def _getsize(self):                                              #(K1)
        'Return the number of bits in a bit vector.'
        return self.size                                             #(K2)


    def read_bits_from_file(self, blocksize):                        #(L1)
        '''
        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
        a BitVector object of size attribute set to 0.
        '''
        error_str = '''You need to first construct a BitVector
        object with a filename as  argument'''                       #(L2)
        if not self.filename:                                        #(L3)
            raise SyntaxError( error_str )                           #(L4)
        if blocksize % 8 != 0:                                       #(L5)
            raise ValueError( "block size must be a multiple of 8" ) #(L6)
        bitstr = _readblock( blocksize, self )                       #(L7)
        if len( bitstr ) == 0:                                       #(L8)
            return BitVector( size = 0 )                             #(L9)
        else:                                                       #(L10)
            return BitVector( bitstring = bitstr )                  #(L11)



    def read_bits_from_fileobject( self, fp ):                       #(M1)
        '''
        This function is meant to read a bit string from a 
        file like object.
        '''
        bitlist = []                                                 #(M2)
        while 1:                                                     #(M3)
            bit = fp.read()                                          #(M4)
            if bit == '': return bitlist                             #(M5)
            bitlist += bit                                           #(M6)


    def write_bits_to_fileobject( self, fp ):                        #(N1)
        '''
        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.
        '''
        for bit_index in range(self.size):                           #(N2)
            if self[bit_index] == 0:                                 #(N3)
                fp.write( '0' )                                      #(N4)
            else:                                                    #(N5)
                fp.write( '1' )                                      #(N6)


    def divide_into_two(self):                                       #(P1)
        '''
        Divides an even-sized bit vector into two and returns
        the two halves as a list of two bit vectors.
        '''
        if self.size % 2 != 0:                                       #(P2)
            raise ValueError( "must have even num bits" )            #(P3)
        i = 0                                                        #(P4)
        outlist1 = []                                                #(P5)
        while ( i < self.size /2 ):                                  #(P6)
            outlist1.append( self[i] )                               #(P7)
            i += 1                                                   #(P8)
        outlist2 = []                                                #(P9)
        while ( i < self.size ):                                    #(P10)
            outlist2.append( self[i] )                              #(P11)
            i += 1                                                  #(P12)
        return [ BitVector( bitlist = outlist1 ),
                 BitVector( bitlist = outlist2 ) ]                  #(P13)


    def permute(self, permute_list):                                 #(Q1)
        '''
        Permute a bit vector according to the indices
        shown in the second argument list.  Return the
        permuted bit vector as a new bit vector.
        '''
        if max(permute_list) > self.size -1:                         #(Q2)
            raise ValueError( "Bad permutation index" )              #(Q3)
        outlist = []                                                 #(Q4)
        i = 0                                                        #(Q5)
        while ( i < len( permute_list ) ):                           #(Q6)
            outlist.append( self[ permute_list[i] ] )                #(Q7)
            i += 1                                                   #(Q8)
        return BitVector( bitlist = outlist )                        #(Q9)


    def unpermute(self, permute_list):                               #(S1)
        '''
        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.
        '''
        if max(permute_list) > self.size -1:                         #(S2)
            raise exceptions.ValueError, "Bad permutation index"     #(S3)
        if self.size != len( permute_list ):                         #(S4)
            raise exceptions.ValueError,"Bad size for permute list"  #(S5)
        out_bv = BitVector( size = self.size )                       #(S6)
        i = 0                                                        #(S7)
        while ( i < len(permute_list) ):                             #(S8)
            out_bv[ permute_list[i] ] = self[i]                      #(S9)
            i += 1                                                  #(S10)
        return out_bv                                               #(S11)


    def write_to_file(self, file_out):                               #(T1)
        '''
        (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).
        '''
        err_str = '''Only a bit vector whose length is a multiple of 8
            can be written to a file.  Use the padding functions
            to satisfy this constraint.'''                           #(T2)
        if self.size % 8:                                            #(T3)
            raise exceptions.ValueError, err_str                     #(T4)
        for byte in range(self.size/8 ):                             #(T5)
            value = 0                                                #(T6)
            for bit in range(8):                                     #(T7)
                value += (self._getbit( byte*8 + (7 - bit) ) << bit )#(T8)
            file_out.write( chr(value) )                             #(T9)


    def close_file_object(self):                                     #(U1)
        '''
        For closing a file object that was used for reading
        the bits into one or more BitVector objects.
        '''
        if not self.filename:                                        #(U2)
            raise exceptions.SyntaxError, "No associated open file"  #(U3)
        self.FILEIN.close()                                          #(U4)


    def intValue(self):                                              #(V1)
        'Return the integer value of a bitvector'
        intVal = 0                                                   #(V2)
        for i in range(self.size):                                   #(V3)
            intVal += self[i] * (2 ** (self.size - i - 1))           #(V4)
        return intVal                                                #(V5)

            
    def __lshift__( self, n ):                                       #(W1)
        'For an in-place left circular shift by n bit positions'
        for i in range(n):                                           #(W2)
            self.circular_rotate_left_by_one()                       #(W3)


    def __rshift__( self, n ):                                       #(W4)
        'For an in-place right circular shift by n bit positions.'
        for i in range(n):                                           #(W5)
            self.circular_rotate_right_by_one()                      #(W6)


    def circular_rotate_left_by_one(self):                           #(X1)
        'For a one-bit in-place left circular shift'
        size = len(self.vector)                                      #(X2)
        bitstring_leftmost_bit = self.vector[0] & 1                  #(X3)
        left_most_bits = map(operator.__and__, self.vector, [1]*size)#(X4)
        left_most_bits.append(left_most_bits[0])                     #(X5)
        del(left_most_bits[0])                                       #(X6)
        self.vector = map(operator.__rshift__, self.vector, [1]*size)#(X7)
        self.vector = map( operator.__or__, self.vector, \
             map(operator.__lshift__, left_most_bits, [15]*size) )   #(X8)
        self._setbit(self.size -1, bitstring_leftmost_bit)           #(X9)


    def circular_rotate_right_by_one(self):                          #(Y1)
        'For a one-bit in-place right circular shift'
        size = len(self.vector)                                      #(Y2)
        bitstring_rightmost_bit = self[self.size - 1]                #(Y3)
        right_most_bits = map( operator.__and__,
                               self.vector, [0x8000]*size )          #(Y4)
        map( operator.__and__, self.vector, [~0x8000]*size )         #(Y5)
        right_most_bits.insert(0, bitstring_rightmost_bit)           #(Y6)
        right_most_bits.pop()                                        #(Y7)
        self.vector = map(operator.__lshift__, self.vector, [1]*size)#(Y8)
        self.vector = map( operator.__or__, self.vector, \
             map(operator.__rshift__, right_most_bits, [15]*size) )  #(Y9)
        self._setbit(0, bitstring_rightmost_bit)                    #(Y10)


    def circular_rot_left(self):                                     #(Z1)
        '''
        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.
        '''
        max_index = (self.size -1)  // 16                            #(Z2)
        left_most_bit = self.vector[0] & 1                           #(Z3)
        self.vector[0] = self.vector[0] >> 1                         #(Z4)
        for i in range(1, max_index + 1):                            #(Z5)
            left_bit = self.vector[i] & 1                            #(Z6)
            self.vector[i] = self.vector[i] >> 1                     #(Z7)
            self.vector[i-1] |= left_bit << 15                       #(Z8)
        self._setbit(self.size -1, left_most_bit)                    #(Z9)


    def circular_rot_right(self):                                    #(a1)
        '''
        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.
        '''
        max_index = (self.size -1)  // 16                            #(a2)
        right_most_bit = self[self.size - 1]                         #(a3)
        self.vector[max_index] &= ~0x8000                            #(a4)
        self.vector[max_index] = self.vector[max_index] << 1         #(a5)
        for i in range(max_index-1, -1, -1):                         #(a6)
            right_bit = self.vector[i] & 0x8000                      #(a7)
            self.vector[i] &= ~0x8000                                #(a8)
            self.vector[i] = self.vector[i] << 1                     #(a9)
            self.vector[i+1] |= right_bit >> 15                     #(a10)
        self._setbit(0, right_most_bit)                             #(a11)


    # Allow array like subscripting for getting and setting:
    __getitem__ = _getbit                                            #(b1)
    __setitem__ = _setbit                                            #(b2)


    def __getslice__(self, i, j):                                    #(c1)
        'Allow slicing with [i:j], [:], etc.'
        slicebits = []                                               #(c2)
        if j > self.size: j = self.size                              #(c3)
        for x in range(i,j):                                         #(c4)
            slicebits.append( self[x] )                              #(c5)
        return BitVector( bitlist = slicebits )                      #(c6)


    # Allow len() to work:
    __len__ = _getsize                                               #(d1)
    # Allow int() to work:
    __int__ = intValue                                               #(d2)

    def __iter__( self ):                                            #(d3)
        '''
        To allow iterations over a bit vector by supporting the
        'for bit in bit_vector' syntax:
        '''
        return BitVectorIterator( self )                             #(d4)


    def __str__( self ):                                             #(e1)
        'To create a print representation'
        if self.size == 0:                                           #(e2)
            return ''                                                #(e3)
        return ''.join( map( str, self ) )                           #(e4)


    # Compare two bit vectors:

    def __eq__(self, other):                                         #(f1)
        if self.size != other.size:                                  #(f2)
            return False                                             #(f3)
        i = 0                                                        #(f4)
        outlist = []                                                 #(f5)
        while ( i < self.size ):                                     #(f6)
            if (self[i] != other[i]): return False                   #(f7)
            i += 1                                                   #(f8)
        return True                                                  #(f9)
    def __ne__(self, other):                                        #(f10)
        return not self == other                                    #(f11)
    def __lt__(self, other):                                        #(f12)
        return self.intValue() < other.intValue()                   #(f13)
    def __le__(self, other):                                        #(f14)
        return self.intValue() <= other.intValue()                  #(f15)
    def __gt__(self, other):                                        #(f16)
        return self.intValue() > other.intValue()                   #(f17)
    def __ge__(self, other):                                        #(f18)
        return self.intValue() >= other.intValue()                  #(f19)

    # Some additional utility functions:

    def _make_deep_copy( self ):                                     #(g1)
        'Make a deep copy of a bit vector'
        copy = str( self )                                           #(g2)
        return BitVector( bitstring = copy )                         #(g3)


    def _resize_pad_from_left( self, n ):                            #(g4)
        '''
        Resize a bit vector by padding with n 0's
        from the left. Return the result as a new bit
        vector.
        '''
        new_str = '0'*n + str( self )                                #(g5)
        return BitVector( bitstring = new_str )                      #(g6)


    def _resize_pad_from_right( self, n ):                           #(g7)
        '''
        Resize a bit vector by padding with n 0's
        from the right. Return the result as a new bit
        vector.
        '''
        new_str = str( self ) + '0'*n                                #(g8)
        return BitVector( bitstring = new_str )                      #(g9)


    def pad_from_left( self, n ):                                   #(g10)
        'Pad a bit vector with n zeros from the left'
        new_str = '0'*n + str( self )                               #(g11)
        bitlist =  map( int, list(new_str) )                        #(g12)
        self.size = len( bitlist )                                  #(g13)
        two_byte_ints_needed = (len(bitlist) + 15) // 16            #(g14)
        self.vector = array.array( 'H', [0]*two_byte_ints_needed )  #(g15)
        map( self._setbit, enumerate(bitlist), bitlist)             #(g16)


    def pad_from_right( self, n ):                                  #(g17)
        'Pad a bit vector with n zeros from the right'
        new_str = str( self ) + '0'*n                               #(g18)
        bitlist =  map( int, list(new_str) )                        #(g19)
        self.size = len( bitlist )                                  #(g20)
        two_byte_ints_needed = (len(bitlist) + 15) // 16            #(g21)
        self.vector = array.array( 'H', [0]*two_byte_ints_needed )  #(g22)
        map( self._setbit, enumerate(bitlist), bitlist)             #(g23)


    def __contains__( self, otherBitVec ):                           #(h1)
        '''
        This supports 'if x in y' and 'if x not in y'
        syntax for bit vectors.
        '''
        if self.size == 0:                                           #(h2)
              raise ValueError, "First arg bitvec has no bits"       #(h3)
        elif self.size < otherBitVec.size:                           #(h4)
              raise ValueError, "First arg bitvec too short"         #(h5)
        max_index = self.size - otherBitVec.size + 1                 #(h6)
        for i in range(max_index):                                   #(h7)
              testbv = self[i:i+otherBitVec.size]                    #(h8)
              if self[i:i+otherBitVec.size] == otherBitVec:          #(h9)
                    return True                                     #(h10)
        return False                                                #(h11)


#-----------------------  BitVectorIterator Class -----------------------

class BitVectorIterator:                                             #(j1)
    def __init__( self, bitvec ):                                    #(j2)
        self.items = []                                              #(j3)
        for i in range( bitvec.size ):                               #(j4)
            self.items.append( bitvec._getbit(i) )                   #(j5)
        self.index = -1                                              #(j6)
    def __iter__( self ):                                            #(j7)
        return self                                                  #(j8)
    def next( self ):                                                #(j9)
        self.index += 1                                             #(j10)
        if self.index < len( self.items ):                          #(j11)
            return self.items[ self.index ]                         #(j12)
        else:                                                       #(j13)
            raise StopIteration                                     #(j14)

       
#------------------------  End of Class Definition -----------------------


#------------------------     Test Code Follows    -----------------------

if __name__ == '__main__':

    # Construct a bit vector of size 0
    bv1 = BitVector( size = 0 )
    print bv1                                   # no output

    # Construct a bit vector of size 1
    bv2 = BitVector( size = 2 )
    print bv2                                   # 00

    # Joining two bit vectors:
    print bv1 + bv2                             # 00

    # Construct a bit vector with a tuple of bits:
    bv = BitVector( bitlist = (1, 0, 0, 1) )
    print bv                                    # 1001

    # Construct a bit vector with a list of bits:    
    bv = BitVector( bitlist = [1, 1, 0, 1] )
    print bv                                    # 1101
    
    # Construct a bit vector from an integer
    bv = BitVector( intVal = 5678 )
    print bv                                    # 1011000101110
    bv = BitVector( intVal = 0 )
    print bv                                    # 0
    bv = BitVector( intVal = 2 )
    print bv                                    # 10
    bv = BitVector( intVal = 3 )
    print bv                                    # 11
    bv = BitVector( intVal = 123456 )
    print bv                                    # 11110001001000000
    print bv.intValue()                         # 123456
    print int( bv )                             # 123456

    # Construct a bit vector directly from a file-like object:
    import StringIO
    x = "111100001111"
    fp_read = StringIO.StringIO( x )
    bv = BitVector( fp = fp_read )
    print bv                                    # 111100001111 

    # Construct a bit vector directly from a bit string:
    bv = BitVector( bitstring = '00110011' )
    print bv                                    # 00110011

    bv = BitVector( bitstring = '' )
    print bv                                    # nothing

    # Get the integer value of a bit vector:
    print bv.intValue()                         # 0

    # Test array-like indexing for a bit vector:
    bv = 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

    # Test setting bit values with positive and negative
    # accessors:
    bv = BitVector( bitstring = '1111' )
    print bv                                    # 1111
    bv[0]=0;bv[1]=0;bv[2]=0;bv[3]=0        
    print bv                                    # 0000
    bv[-1]=1;bv[-2]=1;bv[-4]=1
    print bv                                    # 1011

    # Check equality and inequality operators:
    bv1 = BitVector( bitstring = '00110011' )
    bv2 = BitVector( bitlist = [0,0,1,1,0,0,1,1] )
    print bv1 == bv2                            # True
    print bv1 != bv2                            # False
    print bv1 < bv2                             # False
    print bv1 <= bv2                            # True
    bv3 = BitVector( intVal = 5678 )
    print bv3.intValue()                        # 5678
    print bv3                                   # 10110000101110
    print bv1 == bv3                            # False
    print bv3 > bv1                             # True
    print bv3 >= bv1                            # True


    # Create a string representation of a bit vector:
    fp_write = StringIO.StringIO()
    bv.write_bits_to_fileobject( fp_write )
    print fp_write.getvalue()                   # 1011 

    # Experiments with bitwise logical operations:
    bv3 = bv1 | bv2                              
    print bv3                                   # 00110011
    bv3 = bv1 & bv2
    print bv3                                   # 00110011
    bv3 = bv1 + bv2
    print bv3                                   # 0011001100110011
    bv4 = BitVector( size = 3 )
    print bv4                                   # 000
    bv5 = bv3 + bv4
    print bv5                                   # 0011001100110011000
    bv6 = ~bv5
    print bv6                                   # 1100110011001100111
    bv7 = bv5 & bv6
    print bv7                                   # 0000000000000000000
    bv7 = bv5 | bv6
    print bv7                                   # 1111111111111111111

    # Try logical operations on bit vectors of different sizes:
    print BitVector( intVal = 6 ) ^ BitVector( intVal = 13 )   # 1011
    print BitVector( intVal = 6 ) & BitVector( intVal = 13 )   # 0100
    print BitVector( intVal = 6 ) | BitVector( intVal = 13 )   # 1111

    print BitVector( intVal = 1 ) ^ BitVector( intVal = 13 )   # 1100
    print BitVector( intVal = 1 ) & BitVector( intVal = 13 )   # 0001
    print BitVector( intVal = 1 ) | BitVector( intVal = 13 )   # 1101

    # Try setbit and getsize:
    bv7[7] = 0
    print bv7                                   # 1111111011111111111
    print len( bv7 )                            # 19
    bv8 = (bv5 & bv6) ^ bv7
    print bv8                                   # 1111111011111111111
    
    # Construct a bit vector from a LIST of bits:
    bv = BitVector( bitlist= [0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1] )
    print bv                                    # 0010010100101001

    # Construct a bit vector from a file:
    bv = BitVector( filename = 'TestBitVector/testinput1.txt' )
    print bv                                    # nothing to show
    bv1 = bv.read_bits_from_file(64)    
    print bv1
         # 0100000100100000011010000111010101101110011001110111001001111001
    bv2 = bv.read_bits_from_file(64)    
    print bv2
         # 0010000001100010011100100110111101110111011011100010000001100110
    bv3 = bv1 ^ (bv2)
    print bv3
         # 0110000101000010000110100001101000011001000010010101001000011111

    # Divide into two bit vectors:
    [bv4, bv5] = bv3.divide_into_two()
    print bv4                            # 01100001010000100001101000011010
    print bv5                            # 00011001000010010101001000011111

    # Permute a bit vector:
    bv1 = BitVector( bitlist = [1, 0, 0, 1, 1, 0, 1] )
    print bv1                                    # 1001101
    
    bv2 = bv1.permute( [6, 2, 0, 1] )
    print bv2                                    # 1010
    bv3 = BitVector( bitlist = [1, 1, 0, 0, 0, 1, 1] )
    print bv3                                    # 1100011
    bv4 = bv1 & bv3 
    print bv4                                    # 1000001
    print

    # Read a file from the beginning to end:
    bv = BitVector( filename = 'TestBitVector/testinput4.txt' )
    while (bv.more_to_read):
        bv_read = bv.read_bits_from_file( 64 )
        print bv_read
    print

    # Experiment with closing a file object and start
    # extracting bit vectors from the file from
    # the beginning again:
    bv.close_file_object()
    bv = BitVector( filename = 'TestBitVector/testinput4.txt' )
    bv1 = bv.read_bits_from_file(64)        
    print bv1           
    FILEOUT = open( 'TestBitVector/testinput5.txt', 'w' )
    bv1.write_to_file( FILEOUT )
    FILEOUT.close()

    # Experiment in 64-bit permutation and unpermutation:
    # The permutation array was generated separately by the
    # Fisher-Yates shuffle algorithm:
    bv2 = bv1.permute( [22, 47, 33, 36, 18, 6, 32, 29, 54, 62, 4,
                        9, 42, 39, 45, 59, 8, 50, 35, 20, 25, 49,
                        15, 61, 55, 60, 0, 14, 38, 40, 23, 17, 41,
                        10, 57, 12, 30, 3, 52, 11, 26, 43, 21, 13,
                        58, 37, 48, 28, 1, 63, 2, 31, 53, 56, 44, 24,
                        51, 19, 7, 5, 34, 27, 16, 46] )
    print bv2

    bv3 = bv2.unpermute( [22, 47, 33, 36, 18, 6, 32, 29, 54, 62, 4,
                          9, 42, 39, 45, 59, 8, 50, 35, 20, 25, 49,
                          15, 61, 55, 60, 0, 14, 38, 40, 23, 17, 41,
                          10, 57, 12, 30, 3, 52, 11, 26, 43, 21, 13,
                          58, 37, 48, 28, 1, 63, 2, 31, 53, 56, 44, 24,
                          51, 19, 7, 5, 34, 27, 16, 46] )    
    print bv3

    print
    print
    
    # Try circular shifts to the left and to the right
    print bv3
    bv3 << 7
    print bv3
    bv3 >> 7
    print bv3

    # Test len()    
    print len( bv3 )                      # 64

    # Test slicing
    bv4 = bv3[5:22]
    print bv4                             # 00100100000011010

    # Test the iterator:
    for bit in bv4:
        print bit,                        # 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0
    print
    
    # Demonstrate padding a bit vector from left
    bv = BitVector( bitstring = '101010' )
    bv.pad_from_left( 4 )
    print bv                              # 0000101010
    # Demonstrate padding a bit vector from right
    bv.pad_from_right( 4 )
    print bv                              # 00001010100000

    # Test the syntax 'if bit_vector_1 in bit_vector_2' syntax:
    try:
        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)
    except ValueError, arg:
        print "Error Message: " + str(arg)

    # Test the size modifer when a bit vector is initialized
    # with the intVal method:
    bv = BitVector( intVal = 45, size = 16 )
    print bv                              # 0000000000101101
    bv = BitVector( intVal = 0, size = 8 )    
    print bv                              # 00000000
    bv = BitVector( intVal = 1, size = 8 )    
    print bv                              # 00000001