sl@0: /***************************************************************************
sl@0: *                         Arrays of Arbitrary Bit Length
sl@0: *
sl@0: *   File    : bitarray.cpp
sl@0: *   Purpose : Provides object with methods for creation and manipulation of
sl@0: *             arbitrary length arrays of bits.
sl@0: *
sl@0: *             Bit arrays are implemented as vectors of unsigned chars.  Bit
sl@0: *             0 is the MSB of char 0, and the last bit is the least
sl@0: *             significant (non-spare) bit of the last unsigned char.
sl@0: *
sl@0: *             Example: array of 20 bits (0 through 19) with 8 bit unsigned
sl@0: *                      chars requires 3 unsigned chars (0 through 2) to
sl@0: *                      store all the bits.
sl@0: *
sl@0: *                        char       0       1         2
sl@0: *                               +--------+--------+--------+
sl@0: *                               |        |        |        |
sl@0: *                               +--------+--------+--------+
sl@0: *                        bit     01234567 8911111111111XXXX
sl@0: *                                           012345 6789
sl@0: *
sl@0: *   Author  : Michael Dipperstein
sl@0: *   Date    : July 23, 2004
sl@0: *
sl@0: ****************************************************************************
sl@0: *   HISTORY
sl@0: *
sl@0: *   $Id: bitarray.cpp,v 1.7 2010/02/04 03:31:43 michael Exp $
sl@0: *   $Log: bitarray.cpp,v $
sl@0: *   Revision 1.7  2010/02/04 03:31:43  michael
sl@0: *   Replaced vector<unsigned char> with an array of unsigned char.
sl@0: *
sl@0: *   Made updates for GCC 4.4.
sl@0: *
sl@0: *   Revision 1.5  2007/08/06 05:23:29  michael
sl@0: *   Updated for LGPL Version 3.
sl@0: *
sl@0: *   All methods that don't modify object have been made
sl@0: *   const to increase functionality of const bit_array_c.
sl@0: *
sl@0: *   All assignment operators return a reference to the object being assigned a value so that operator chaining will work.
sl@0: *
sl@0: *   Added >> and << operators.
sl@0: *
sl@0: *   Revision 1.3  2006/04/30 23:34:07  michael
sl@0: *   Improved performance by incorporating Benjamin Schindler's
sl@0: *   <bschindler@student.ethz.ch> changes to pass arguments as a reference.
sl@0: *
sl@0: *   Revision 1.2  2004/08/05 22:16:49  michael
sl@0: *   Add overloads for bitwise operators returning values.
sl@0: *   Add a more natural looking way to set bit values.
sl@0: *
sl@0: *   Revision 1.1.1.1  2004/08/04 13:28:20  michael
sl@0: *   bit_array_c
sl@0: *
sl@0: ****************************************************************************
sl@0: *
sl@0: * Bitarray: An ANSI C++ class for manipulating arbitrary length bit arrays
sl@0: * Copyright (C) 2004, 2006-2007, 2010 by
sl@0: *       Michael Dipperstein (mdipper@alumni.engr.ucsb.edu)
sl@0: *
sl@0: * This file is part of the bit array library.
sl@0: *
sl@0: * The bit array library is free software; you can redistribute it and/or
sl@0: * modify it under the terms of the GNU Lesser General Public License as
sl@0: * published by the Free Software Foundation; either version 3 of the
sl@0: * License, or (at your option) any later version.
sl@0: *
sl@0: * The bit array library is distributed in the hope that it will be useful,
sl@0: * but WITHOUT ANY WARRANTY; without even the implied warranty of
sl@0: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser
sl@0: * General Public License for more details.
sl@0: *
sl@0: * You should have received a copy of the GNU Lesser General Public License
sl@0: * along with this program.  If not, see <http://www.gnu.org/licenses/>.
sl@0: *
sl@0: ***************************************************************************/
sl@0: 
sl@0: /***************************************************************************
sl@0: *                             INCLUDED FILES
sl@0: ***************************************************************************/
sl@0: #include <iostream>
sl@0: #include <climits>
sl@0: #include "bitarray.h"
sl@0: 
sl@0: using namespace std;
sl@0: 
sl@0: /***************************************************************************
sl@0: *                                 MACROS
sl@0: ***************************************************************************/
sl@0: 
sl@0: /* make CHAR_BIT 8 if it's not defined in limits.h */
sl@0: #ifndef CHAR_BIT
sl@0: #warning CHAR_BIT not defined.  Assuming 8 bits.
sl@0: #define CHAR_BIT 8
sl@0: #endif
sl@0: 
sl@0: /* position of bit within character */
sl@0: #define BIT_CHAR(bit)         ((bit) / CHAR_BIT)
sl@0: 
sl@0: /* array index for character containing bit */
sl@0: //SL: We had to change that macro since bits in our frame buffer are the other way around
sl@0: //TODO: Find a solution to tackle that problem
sl@13: 
sl@13: //Bits are indexed: 01234567
sl@0: //#define BIT_IN_CHAR(bit)      (1 << (CHAR_BIT - 1 - ((bit)  % CHAR_BIT)))
sl@13: 
sl@13: //Bits are indexed: 76543210
sl@13: //#define BIT_IN_CHAR(bit)      (1 << (((bit)  % CHAR_BIT)))
sl@0: 
sl@0: /* number of characters required to contain number of bits */
sl@0: #define BITS_TO_CHARS(bits)   ((((bits) - 1) / CHAR_BIT) + 1)
sl@0: 
sl@0: /* most significant bit in a character */
sl@0: #define MS_BIT                (1 << (CHAR_BIT - 1))
sl@0: 
sl@0: /***************************************************************************
sl@0: *                                 METHODS
sl@0: ***************************************************************************/
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : bit_array_c - constructor
sl@0: *   Description: This is the bit_array_c constructor.  It reserves memory
sl@0: *                for the vector storing the array.
sl@0: *   Parameters : numBits - number of bits in the array
sl@0: *   Effects    : Allocates vectory for array bits
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>::BitArray(const int numBits):
sl@0:     m_NumBits(numBits),
sl@0:     m_Array(NULL),
sl@0:     m_OwnsBuffer(true)
sl@0: {
sl@0:     m_SizeInBytes = BITS_TO_CHARS(numBits);
sl@0: 
sl@0: 
sl@0:     /* allocate space for bit array */
sl@0:     m_Array = new unsigned char[m_SizeInBytes];
sl@0: 
sl@0:     /* set all bits to 0 */
sl@0:     fill_n(m_Array, m_SizeInBytes, 0);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : bit_array_c - constructor
sl@0: *   Description: This is the bit_array_c constructor.  It copies the
sl@0: *                for contents of a vector of unsigned char into the
sl@0: *                bitarray.
sl@0: *   Parameters : vect - vector to be copied
sl@0: *                numBits - number of bits in the array
sl@0: *   Effects    : Allocates vectory for array bits
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>::BitArray(unsigned char *array, const int numBits,bool aOwnsBuffer):
sl@0:     m_NumBits(numBits),
sl@0:     m_Array(array),
sl@0:     m_OwnsBuffer(aOwnsBuffer)
sl@0: {
sl@0: 
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : ~bit_array_c - destructor
sl@0: *   Description: This is the bit_array_c destructor.  At this point it's
sl@0: *                just a place holder.
sl@0: *   Parameters : None
sl@0: *   Effects    : None
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>::~BitArray(void)
sl@0: {
sl@0:     if (m_OwnsBuffer)
sl@0:     {
sl@0:         delete[] m_Array;
sl@0:         m_Array = NULL;
sl@0:     }
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : Dump
sl@0: *   Description: This method dumps the conents of a bit array to stdout.
sl@0: *                The format of the dump is a series of bytes represented in
sl@0: *                hexadecimal.
sl@0: *   Parameters : outStream - stream to write to
sl@0: *   Effects    : Array contents are dumped to stdout
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: void BitArray<F>::Dump(std::ostream &outStream)
sl@0: {
sl@0:     int size;
sl@0: 
sl@0:     size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:     outStream.width(2);
sl@0:     outStream.fill('0');
sl@0:     outStream << uppercase << hex << (int)(m_Array[0]);  /* first byte */
sl@0: 
sl@0:     for (int i = 1; i < size; i++)
sl@0:     {
sl@0:         /* remaining bytes with a leading space */
sl@0:         outStream << " ";
sl@0:         outStream.width(2);
sl@0:         outStream.fill('0');
sl@0:         outStream << (int)(m_Array[i]);
sl@0:     }
sl@0: 
sl@0:     outStream << dec;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : SetAll
sl@0: *   Description: This method sets every bit in the bit array to 1.  This
sl@0: *                method uses UCHAR_MAX to determine what it means to set
sl@0: *                all bits in an unsigned char, so it is crucial that the
sl@0: *                machine implementation of unsigned char utilizes all of
sl@0: *                the bits in the memory allocated for an unsigned char.
sl@0: *   Parameters : None
sl@0: *   Effects    : Each of the bits used in the bit array are set to 1.
sl@0: *                Unused (spare) bits are set to 0.
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: void BitArray<F>::SetAll(void)
sl@0: {
sl@0:     int bits, size;
sl@0:     unsigned char mask;
sl@0: 
sl@0:     size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:     /* set bits in all bytes to 1 */
sl@0:     fill_n(m_Array, size, UCHAR_MAX);
sl@0: 
sl@0:     /* zero any spare bits so increment and decrement are consistent */
sl@0:     bits = m_NumBits % CHAR_BIT;
sl@0:     if (bits != 0)
sl@0:     {
sl@0:         mask = UCHAR_MAX << (CHAR_BIT - bits);
sl@0:         m_Array[BIT_CHAR(m_NumBits - 1)] = mask;
sl@0:     }
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : ClearAll
sl@0: *   Description: This method sets every bit in the bit array to 0.
sl@0: *   Parameters : None
sl@0: *   Effects    : Each of the bits in the bit array are set to 0.
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: void BitArray<F>::ClearAll(void)
sl@0: {
sl@0:     int size;
sl@0: 
sl@0:     size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:     /* set bits in all bytes to 0 */
sl@0:     fill_n(m_Array, size, 0);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : SetBit
sl@0: *   Description: This method sets a bit in the bit array to 1.
sl@0: *   Parameters : bit - the number of the bit to set
sl@0: *   Effects    : The specified bit will be set to 1.
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: void BitArray<F>::SetBit(const unsigned int bit)
sl@0: {
sl@0:     if (m_NumBits <= bit)
sl@0:     {
sl@0:         return;         /* bit out of range */
sl@0:     }
sl@0: 
sl@13:     m_Array[BIT_CHAR(bit)] |= F(bit);
sl@0: }
sl@0: 
sl@0: /**
sl@0: */
sl@13: template <TBitInChar F>
sl@13: void BitArray<F>::SetBitValue(const unsigned int bit, bool aValue)
sl@0: 	{
sl@0: 	if (aValue)
sl@0: 		{
sl@0: 		SetBit(bit);
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		ClearBit(bit);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : ClearBit
sl@0: *   Description: This method sets a bit in the bit array to 0.
sl@0: *   Parameters : bit - the number of the bit to clear
sl@0: *   Effects    : The specified bit will be set to 0.
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: void BitArray<F>::ClearBit(const unsigned int bit)
sl@0: {
sl@0:     unsigned char mask;
sl@0: 
sl@0:     if (m_NumBits <= bit)
sl@0:     {
sl@0:         return;         /* bit out of range */
sl@0:     }
sl@0: 
sl@0:     /* create a mask to zero out desired bit */
sl@13:     mask =  F(bit);
sl@0:     mask = ~mask;
sl@0: 
sl@0:     m_Array[BIT_CHAR(bit)] &= mask;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator()
sl@0: *   Description: Overload of the () operator.  This method approximates
sl@0: *                array indices used for assignment.  It returns a
sl@0: *                bit_array_index_c which includes an = method used to
sl@0: *                set bit values.
sl@0: *   Parameters : bit - index of array bit
sl@0: *   Effects    : None
sl@0: *   Returned   : bit_array_index_c (pointer to bit)
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArrayIndex<F> BitArray<F>::operator()(const unsigned int bit)
sl@0: {
sl@13:     BitArrayIndex<F> result(this, bit);
sl@0: 
sl@0:     return result;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator[]
sl@0: *   Description: Overload of the [] operator.  This method returns the
sl@0: *                value of a bit in the bit array.
sl@0: *   Parameters : bit - index of array bit
sl@0: *   Effects    : None
sl@0: *   Returned   : The value of the specified bit.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: bool BitArray<F>::operator[](const unsigned int bit) const
sl@0: {
sl@13:     return((m_Array[BIT_CHAR(bit)] & F(bit)) != 0);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator==
sl@0: *   Description: overload of the == operator
sl@0: *   Parameters : other - bit array to compare
sl@0: *   Effects    : None
sl@0: *   Returned   : True if this == other.  Otherwise false.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: bool BitArray<F>::operator==(const BitArray &other) const
sl@0: {
sl@0:     if (m_NumBits != other.m_NumBits)
sl@0:     {
sl@0:         /* unequal sizes */
sl@0:         return false;
sl@0:     }
sl@0: 
sl@0:     return (this->m_Array == other.m_Array);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator!=
sl@0: *   Description: overload of the != operator
sl@0: *   Parameters : other - bit array to compare
sl@0: *   Effects    : None
sl@0: *   Returned   : True if this != other.  Otherwise false.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: bool BitArray<F>::operator!=(const BitArray &other) const
sl@0: {
sl@0:     if (m_NumBits != other.m_NumBits)
sl@0:     {
sl@0:         /* unequal sizes */
sl@0:         return true;
sl@0:     }
sl@0: 
sl@0:     return (this->m_Array != other.m_Array);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator<
sl@0: *   Description: overload of the < operator
sl@0: *   Parameters : other - bit array to compare
sl@0: *   Effects    : None
sl@0: *   Returned   : True if this < other.  Otherwise false.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: bool BitArray<F>::operator<(const BitArray &other) const
sl@0: {
sl@0:     if (m_NumBits != other.m_NumBits)
sl@0:     {
sl@0:         /* unequal sizes */
sl@0:         return false;
sl@0:     }
sl@0: 
sl@0:     return (this->m_Array < other.m_Array);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator<=
sl@0: *   Description: overload of the <= operator
sl@0: *   Parameters : other - bit array to compare
sl@0: *   Effects    : None
sl@0: *   Returned   : True if this <= other.  Otherwise false.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: bool BitArray<F>::operator<=(const BitArray &other) const
sl@0: {
sl@0:     if (m_NumBits != other.m_NumBits)
sl@0:     {
sl@0:         /* unequal sizes */
sl@0:         return false;
sl@0:     }
sl@0: 
sl@0:     return (this->m_Array <= other.m_Array);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator>
sl@0: *   Description: overload of the > operator
sl@0: *   Parameters : other - bit array to compare
sl@0: *   Effects    : None
sl@0: *   Returned   : True if this > other.  Otherwise false.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: bool BitArray<F>::operator>(const BitArray &other) const
sl@0: {
sl@0:     if (m_NumBits != other.m_NumBits)
sl@0:     {
sl@0:         /* unequal sizes */
sl@0:         return false;
sl@0:     }
sl@0: 
sl@0:     return (this->m_Array > other.m_Array);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator>=
sl@0: *   Description: overload of the >= operator
sl@0: *   Parameters : other - bit array to compare
sl@0: *   Effects    : None
sl@0: *   Returned   : True if this >= other.  Otherwise false.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: bool BitArray<F>::operator>=(const BitArray &other) const
sl@0: {
sl@0:     if (m_NumBits != other.m_NumBits)
sl@0:     {
sl@0:         /* unequal sizes */
sl@0:         return false;
sl@0:     }
sl@0: 
sl@0:     return (this->m_Array >= other.m_Array);
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator~
sl@0: *   Description: overload of the ~ operator.  Negates all non-spare bits in
sl@0: *                bit array
sl@0: *   Parameters : None
sl@0: *   Effects    : None
sl@0: *   Returned   : value of this after bitwise not
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F> BitArray<F>::operator~(void) const
sl@0: {
sl@0:     BitArray result(this->m_NumBits);
sl@0:     result = *this;
sl@0:     result.Not();
sl@0: 
sl@0:     return result;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator&
sl@0: *   Description: overload of the & operator.  Performs a bitwise and
sl@0: *                between the source array and this bit array.
sl@0: *   Parameters : other - bit array on righthand side of &
sl@0: *   Effects    : None
sl@0: *   Returned   : value of bitwise and of this and other.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F> BitArray<F>::operator&(const BitArray<F> &other) const
sl@0: {
sl@13:     BitArray<F> result(this->m_NumBits);
sl@0:     result = *this;
sl@0:     result &= other;
sl@0: 
sl@0:     return result;
sl@0: }
sl@0: 
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator^
sl@0: *   Description: overload of the ^ operator.  Performs a bitwise xor
sl@0: *                between the source array and this bit array.
sl@0: *   Parameters : other - bit array on righthand side of ^
sl@0: *   Effects    : None
sl@0: *   Returned   : value of bitwise xor of this and other.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F> BitArray<F>::operator^(const BitArray<F> &other) const
sl@0: {
sl@13:     BitArray<F> result(this->m_NumBits);
sl@0:     result = *this;
sl@0:     result ^= other;
sl@0: 
sl@0:     return result;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator|
sl@0: *   Description: overload of the | operator.  Performs a bitwise or
sl@0: *                between the source array and this bit array.
sl@0: *   Parameters : other - bit array on righthand side of |
sl@0: *   Effects    : None
sl@0: *   Returned   : value of bitwise or of this and other.
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F> BitArray<F>::operator|(const BitArray<F> &other) const
sl@0: {
sl@13:     BitArray<F> result(this->m_NumBits);
sl@0:     result = *this;
sl@0:     result |= other;
sl@0: 
sl@0:     return result;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator<<
sl@0: *   Description: overload of the << operator.  Performs a bitwise left
sl@0: *                shift of this bit array.
sl@0: *   Parameters : count - the number of bits to shift left
sl@0: *   Effects    : None
sl@0: *   Returned   : result of bitwise left shift
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F> BitArray<F>::operator<<(const unsigned int count) const
sl@0: {
sl@13:     BitArray<F> result(this->m_NumBits);
sl@0:     result = *this;
sl@0:     result <<= count;
sl@0: 
sl@0:     return result;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator>>
sl@0: *   Description: overload of the >> operator.  Performs a bitwise right
sl@0: *                shift of this bit array.
sl@0: *   Parameters : count - the number of bits to shift right
sl@0: *   Effects    : None
sl@0: *   Returned   : result of bitwise right shift
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F> BitArray<F>::operator>>(const unsigned int count) const
sl@0: {
sl@13:     BitArray<F> result(this->m_NumBits);
sl@0:     result = *this;
sl@0:     result >>= count;
sl@0: 
sl@0:     return result;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator++ (prefix)
sl@0: *   Description: overload of the ++ operator.  Increments the contents of
sl@0: *                a bit array.  Overflows cause rollover.
sl@0: *   Parameters : None
sl@0: *   Effects    : Bit array contents are incremented
sl@0: *   Returned   : Reference to this array after increment
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator++(void)
sl@0: {
sl@0:     int i;
sl@0:     unsigned char maxValue;     /* maximum value for current char */
sl@0:     unsigned char one;          /* least significant bit in current char */
sl@0: 
sl@0:     if (m_NumBits == 0)
sl@0:     {
sl@0:         return *this;           /* nothing to increment */
sl@0:     }
sl@0: 
sl@0:     /* handle arrays that don't use every bit in the last character */
sl@0:     i = (m_NumBits % CHAR_BIT);
sl@0:     if (i != 0)
sl@0:     {
sl@0:         maxValue = UCHAR_MAX << (CHAR_BIT - i);
sl@0:         one = 1 << (CHAR_BIT - i);
sl@0:     }
sl@0:     else
sl@0:     {
sl@0:         maxValue = UCHAR_MAX;
sl@0:         one = 1;
sl@0:     }
sl@0: 
sl@0:     for (i = BIT_CHAR(m_NumBits - 1); i >= 0; i--)
sl@0:     {
sl@0:         if (m_Array[i] != maxValue)
sl@0:         {
sl@0:             m_Array[i] = m_Array[i] + one;
sl@0:             return *this;
sl@0:         }
sl@0:         else
sl@0:         {
sl@0:             /* need to carry to next byte */
sl@0:             m_Array[i] = 0;
sl@0: 
sl@0:             /* remaining characters must use all bits */
sl@0:             maxValue = UCHAR_MAX;
sl@0:             one = 1;
sl@0:         }
sl@0:     }
sl@0: 
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator++ (postfix)
sl@0: *   Description: overload of the ++ operator.  Increments the contents of
sl@0: *                a bit array.  Overflows cause rollover.
sl@0: *   Parameters : dumy - needed for postfix increment
sl@0: *   Effects    : Bit array contents are incremented
sl@0: *   Returned   : Reference to this array after increment
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator++(int dummy)
sl@0: {
sl@0:     ++(*this);
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator-- (prefix)
sl@0: *   Description: overload of the -- operator.  Decrements the contents of
sl@0: *                a bit array.  Underflows cause rollover.
sl@0: *   Parameters : None
sl@0: *   Effects    : Bit array contents are decremented
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator--(void)
sl@0: {
sl@0:     int i;
sl@0:     unsigned char maxValue;     /* maximum value for current char */
sl@0:     unsigned char one;          /* least significant bit in current char */
sl@0: 
sl@0:     if (m_NumBits == 0)
sl@0:     {
sl@0:         return *this;           /* nothing to decrement */
sl@0:     }
sl@0: 
sl@0:     /* handle arrays that don't use every bit in the last character */
sl@0:     i = (m_NumBits % CHAR_BIT);
sl@0:     if (i != 0)
sl@0:     {
sl@0:         maxValue = UCHAR_MAX << (CHAR_BIT - i);
sl@0:         one = 1 << (CHAR_BIT - i);
sl@0:     }
sl@0:     else
sl@0:     {
sl@0:         maxValue = UCHAR_MAX;
sl@0:         one = 1;
sl@0:     }
sl@0: 
sl@0:     for (i = BIT_CHAR(m_NumBits - 1); i >= 0; i--)
sl@0:     {
sl@0:         if (m_Array[i] >= one)
sl@0:         {
sl@0:             m_Array[i] = m_Array[i] - one;
sl@0:             return *this;
sl@0:         }
sl@0:         else
sl@0:         {
sl@0:             /* need to borrow from the next byte */
sl@0:             m_Array[i] = maxValue;
sl@0: 
sl@0:             /* remaining characters must use all bits */
sl@0:             maxValue = UCHAR_MAX;
sl@0:             one = 1;
sl@0:         }
sl@0:     }
sl@0: 
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator-- (postfix)
sl@0: *   Description: overload of the -- operator.  Decrements the contents of
sl@0: *                a bit array.  Underflows cause rollover.
sl@0: *   Parameters : dumy - needed for postfix decrement
sl@0: *   Effects    : Bit array contents are decremented
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator--(int dummy)
sl@0: {
sl@0:     --(*this);
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator=
sl@0: *   Description: overload of the = operator.  Copies source contents into
sl@0: *                this bit array.
sl@0: *   Parameters : src - Source bit array
sl@0: *   Effects    : Source bit array contents are copied into this array
sl@0: *   Returned   : Reference to this array after copy
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator=(const BitArray<F> &src)
sl@0: {
sl@0:     if (*this == src)
sl@0:     {
sl@0:         /* don't do anything for a self assignment */
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     if (m_NumBits != src.m_NumBits)
sl@0:     {
sl@0:         /* don't do assignment with different array sizes */
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     if ((m_NumBits == 0) || (src.m_NumBits == 0))
sl@0:     {
sl@0:         /* don't do assignment with unallocated array */
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     /* copy bits from source */
sl@0:     int size;
sl@0:     size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:     copy(src.m_Array, &src.m_Array[size], this->m_Array);
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator&=
sl@0: *   Description: overload of the &= operator.  Performs a bitwise and
sl@0: *                between the source array and this bit array.  This bit
sl@0: *                array will contain the result.
sl@0: *   Parameters : src - Source bit array
sl@0: *   Effects    : Results of bitwise and are stored in this array
sl@0: *   Returned   : Reference to this array after and
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator&=(const BitArray<F> &src)
sl@0: {
sl@0:     int size;
sl@0: 
sl@0:     size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:     if (m_NumBits != src.m_NumBits)
sl@0:     {
sl@0:         /* don't do assignment with different array sizes */
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     /* AND array one unsigned char at a time */
sl@0:     for(int i = 0; i < size; i++)
sl@0:     {
sl@0:         m_Array[i] = m_Array[i] & src.m_Array[i];
sl@0:     }
sl@0: 
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator^=
sl@0: *   Description: overload of the ^= operator.  Performs a bitwise xor
sl@0: *                between the source array and this bit array.  This bit
sl@0: *                array will contain the result.
sl@0: *   Parameters : src - Source bit array
sl@0: *   Effects    : Results of bitwise xor are stored in this array
sl@0: *   Returned   : Reference to this array after xor
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator^=(const BitArray<F> &src)
sl@0: {
sl@0:     int size;
sl@0: 
sl@0:     size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:     if (m_NumBits != src.m_NumBits)
sl@0:     {
sl@0:         /* don't do assignment with different array sizes */
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     /* XOR array one unsigned char at a time */
sl@0:     for(int i = 0; i < size; i++)
sl@0:     {
sl@0:         m_Array[i] = m_Array[i] ^ src.m_Array[i];
sl@0:     }
sl@0: 
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator|=
sl@0: *   Description: overload of the |= operator.  Performs a bitwise or
sl@0: *                between the source array and this bit array.  This bit
sl@0: *                array will contain the result.
sl@0: *   Parameters : src - Source bit array
sl@0: *   Effects    : Results of bitwise or are stored in this array
sl@0: *   Returned   : Reference to this array after or
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator|=(const BitArray<F> &src)
sl@0: {
sl@0:     int size;
sl@0: 
sl@0:     size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:     if (m_NumBits != src.m_NumBits)
sl@0:     {
sl@0:         /* don't do assignment with different array sizes */
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     /* OR array one unsigned char at a time */
sl@0:     for(int i = 0; i < size; i++)
sl@0:     {
sl@0:         m_Array[i] = m_Array[i] | src.m_Array[i];
sl@0:     }
sl@0: 
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : Not
sl@0: *   Description: Negates all non-spare bits in bit array.
sl@0: *   Parameters : None
sl@0: *   Effects    : Contents of bit array are negated.  Any spare bits are
sl@0: *                left at 0.
sl@0: *   Returned   : Reference to this array after not
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::Not(void)
sl@0: {
sl@0:     int bits;
sl@0:     unsigned char mask;
sl@0:     int size;
sl@0: 
sl@0:     size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:     if (m_NumBits == 0)
sl@0:     {
sl@0:         /* don't do not with unallocated array */
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     /* NOT array one unsigned char at a time */
sl@0:     for(int i = 0; i < size; i++)
sl@0:     {
sl@0:         m_Array[i] = ~m_Array[i];
sl@0:     }
sl@0: 
sl@0:     /* zero any spare bits so increment and decrement are consistent */
sl@0:     bits = m_NumBits % CHAR_BIT;
sl@0:     if (bits != 0)
sl@0:     {
sl@0:         mask = UCHAR_MAX << (CHAR_BIT - bits);
sl@0:         m_Array[BIT_CHAR(m_NumBits - 1)] &= mask;
sl@0:     }
sl@0: 
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator<<=
sl@0: *   Description: overload of the <<= operator.  Performs a left shift on
sl@0: *                this bit array.  This bit array will contain the result.
sl@0: *   Parameters : shifts - number of bit positions to shift
sl@0: *   Effects    : Results of the shifts are stored in this array
sl@0: *   Returned   : Reference to this array after shift
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator<<=(const unsigned int shifts)
sl@0: {
sl@0:     int i;
sl@0:     int chars = shifts / CHAR_BIT; /* number of whole byte shifts */
sl@0: 
sl@0:     if (shifts >= m_NumBits)
sl@0:     {
sl@0:         /* all bits have been shifted off */
sl@0:         this->ClearAll();
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     /* first handle big jumps of bytes */
sl@0:     if (chars > 0)
sl@0:     {
sl@0:         int size;
sl@0: 
sl@0:         size = BITS_TO_CHARS(m_NumBits);
sl@0: 
sl@0:         for (i = 0; (i + chars) < size; i++)
sl@0:         {
sl@0:             m_Array[i] = m_Array[i + chars];
sl@0:         }
sl@0: 
sl@0:         /* now zero out new bytes on the right */
sl@0:         for (i = size; chars > 0; chars--)
sl@0:         {
sl@0:             m_Array[i - chars] = 0;
sl@0:         }
sl@0:     }
sl@0: 
sl@0:     /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
sl@0:     for (i = 0; i < (int)(shifts % CHAR_BIT); i++)
sl@0:     {
sl@0:         for (unsigned int j = 0; j < BIT_CHAR(m_NumBits - 1); j++)
sl@0:         {
sl@0:             m_Array[j] <<= 1;
sl@0: 
sl@0:             /* handle shifts across byte bounds */
sl@0:             if (m_Array[j + 1] & MS_BIT)
sl@0:             {
sl@0:                 m_Array[j] |= 0x01;
sl@0:             }
sl@0:         }
sl@0: 
sl@0:         m_Array[BIT_CHAR(m_NumBits - 1)] <<= 1;
sl@0:     }
sl@0: 
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator>>=
sl@0: *   Description: overload of the >>= operator.  Performs a right shift on
sl@0: *                this bit array.  This bit array will contain the result.
sl@0: *   Parameters : shifts - number of bit positions to shift
sl@0: *   Effects    : Results of the shifts are stored in this array
sl@0: *   Returned   : Reference to this array after shift
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArray<F>& BitArray<F>::operator>>=(const unsigned int shifts)
sl@0: {
sl@0:     int i;
sl@0:     char mask;
sl@0:     int chars = shifts / CHAR_BIT;  /* number of whole byte shifts */
sl@0: 
sl@0:     if (shifts >= m_NumBits)
sl@0:     {
sl@0:         /* all bits have been shifted off */
sl@0:         this->ClearAll();
sl@0:         return *this;
sl@0:     }
sl@0: 
sl@0:     /* first handle big jumps of bytes */
sl@0:     if (chars > 0)
sl@0:     {
sl@0:         for (i = BIT_CHAR(m_NumBits - 1); (i - chars) >= 0; i--)
sl@0:         {
sl@0:             m_Array[i] = m_Array[i - chars];
sl@0:         }
sl@0: 
sl@0:         /* now zero out new bytes on the right */
sl@0:         for (; chars > 0; chars--)
sl@0:         {
sl@0:             m_Array[chars - 1] = 0;
sl@0:         }
sl@0:     }
sl@0: 
sl@0:     /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
sl@0:     for (i = 0; i < (int)(shifts % CHAR_BIT); i++)
sl@0:     {
sl@0:         for (unsigned int j = BIT_CHAR(m_NumBits - 1); j > 0; j--)
sl@0:         {
sl@0:             m_Array[j] >>= 1;
sl@0: 
sl@0:             /* handle shifts across byte bounds */
sl@0:             if (m_Array[j - 1] & 0x01)
sl@0:             {
sl@0:                 m_Array[j] |= MS_BIT;
sl@0:             }
sl@0:         }
sl@0: 
sl@0:         m_Array[0] >>= 1;
sl@0:     }
sl@0: 
sl@0:     /***********************************************************************
sl@0:     * zero any spare bits that are shifted beyond the end of the bit array
sl@0:     * so that increment and decrement are consistent.
sl@0:     ***********************************************************************/
sl@0:     i = m_NumBits % CHAR_BIT;
sl@0:     if (i != 0)
sl@0:     {
sl@0:         mask = UCHAR_MAX << (CHAR_BIT - i);
sl@0:         m_Array[BIT_CHAR(m_NumBits - 1)] &= mask;
sl@0:     }
sl@0: 
sl@0:     return *this;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : bit_array_index_c - constructor
sl@0: *   Description: This is the bit_array_index_c constructor.  It stores a
sl@0: *                pointer to the bit array and the bit index.
sl@0: *   Parameters : array - pointer to bit array
sl@0: *                index - index of bit in array
sl@0: *   Effects    : Pointer to bit array and bit index are stored.
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: BitArrayIndex<F>::BitArrayIndex(BitArray<F> *array,
sl@0:     const unsigned int index)
sl@0: {
sl@0:     m_BitArray = array;
sl@0:     m_Index = index;
sl@0: }
sl@0: 
sl@0: /***************************************************************************
sl@0: *   Method     : operator=
sl@0: *   Description: overload of the = operator.  Sets the bit array bit to
sl@0: *                the value of src.
sl@0: *   Parameters : src - bit value
sl@0: *   Effects    : Bit pointed to by this object is set to the value of
sl@0: *                source.
sl@0: *   Returned   : None
sl@0: ***************************************************************************/
sl@13: template <TBitInChar F>
sl@13: void BitArrayIndex<F>::operator=(const bool src)
sl@0: {
sl@0:     if (m_BitArray == NULL)
sl@0:     {
sl@0:         return;     /* no array */
sl@0:     }
sl@0: 
sl@0:     if (m_BitArray->SizeInBits() <= m_Index)
sl@0:     {
sl@0:         return;     /* index is out of bounds */
sl@0:     }
sl@0: 
sl@0:     if (src)
sl@0:     {
sl@0:         m_BitArray->SetBit(m_Index);
sl@0:     }
sl@0:     else
sl@0:     {
sl@0:         m_BitArray->ClearBit(m_Index);
sl@0:     }
sl@0: }
sl@13: 
sl@13: 
sl@13: template class BitArray<HighBitHighIndex>;
sl@13: template class BitArray<HighBitLowIndex>;
sl@13: template class BitArrayIndex<HighBitHighIndex>;
sl@13: template class BitArrayIndex<HighBitLowIndex>;