BitVector Expand function: 'BitVector out of range' error

[nyvrem]

My task requirement to implement an 'Expand' function of a bit vector in the BitVector class is as follows (header and main files are provided):

1. Implement the method BitVector::Expand(size_t nb) so that it has the effect enlarging the number of bits to at least nb while keeping the state of each of the existing bits in the enlarged object. The necessary steps in this implementation are:
a. Calculate newByteArraySize = the number of bytes required for nb bits
b. Using a locally declared pointer, create a new byte array of size newByteArraySize
c. Initialize the new byte array to be the same as the old one where they share indices and to be zero for the "new" bits
d. Set byteArraySize_ to newByteArraySize
e. Delete the old byteArray_
f. Point byteArray_ to the newly allocated byte array

2. Expand(nb) should do nothing if nb does not excede the number of bits already allocated.

3. In all cases a call to Expand() should not change the bit values for any existing bits and should initialize all new bits to 0

I have coded according to the above steps with additional loop structures to determine the conditions for expansion of loop to size_t n as stated in parameter. The class successfully compiles with main into executable function 'fbitvect.x' and it runs by calling the command with a size_t integer e.g. 'fbitvect.x 24'.

Inside the function, when I call the 'Expand' function by redefining a larger size_t integer than 24, I get "** BitVector error: index out of range".

What else is wrong with implementation code below ? Is it the way I organize my code?

My implementation code so far:

#include <iostream>
#include <bitvect.h>

namespace fsu
{

bool operator!= (const BitVector& v1 , const BitVector& v2)
{
return !(v1 == v2);
}

bool operator== (const BitVector& v1 , const BitVector& v2)
{
if (v1.Size() != v2.Size())
return 0;
for (size_t i = 0; i < v1.Size(); ++i)
{
if (v1.Test(i) && !v2.Test(i))
return 0;
if (v2.Test(i) && !v2.Test(i))
return 0;
}
return 1;
}

std::ostream& operator << (std::ostream& os, const BitVector& bv)
{
for (size_t i = 0; i < bv.Size(); ++i)
os << bv.Test(i);
return os;
}

//----------------------------------
// BitVector
//----------------------------------

// public methods

void BitVector::Expand (size_t newsize) // increase number of bits, retaining current values
{
// syntactically correct, non-functional implementation

unsigned char * newByteArray;
size_t newByteArraySize;

if (newsize > Size() )
{
newByteArraySize = (newsize + 7)/8;
newByteArray = new unsigned char [newByteArraySize];

// initialize new byte array same as old, share indices and set to 0 for
// new bits

for (size_t i = 0; i <= Size(); ++i)
{
newByteArray[i] = Test(i);
}
for (size_t i = 0; i > Size(); ++i)
{
Unset(i);
newByteArray[i] = Test(i);
}

byteArraySize_ = newByteArraySize;
delete [] byteArray_;
byteArray_ = newByteArray;
}
else if (newsize <= Size())
{
//return byteArray_ with unchanged size
}

else if (newsize == 0)
{
std::cerr << "** BitVector error: memory allocation failure -- terminating program.\n";
exit (EXIT_FAILURE);
//return;
}

}

[xismn]

Here is your 'Expand' member function with code tags:

void BitVector::Expand(size_t newsize) // increase number of bits, retaining current values
{
	// syntactically correct, non-functional implementation

	unsigned char * newByteArray;
	size_t newByteArraySize;

	if (newsize > Size())
	{
		newByteArraySize = (newsize + 7) / 8;
		newByteArray = new unsigned char[newByteArraySize];

		// initialize new byte array same as old, share indices and set to 0 for
		// new bits

		for (size_t i = 0; i <= Size(); ++i)
		{
			newByteArray[i] = Test(i);
		}
		for (size_t i = 0; i > Size(); ++i)
		{
			Unset(i);
			newByteArray[i] = Test(i);
		}

		byteArraySize_ = newByteArraySize;
		delete[] byteArray_;
		byteArray_ = newByteArray;
	}
	else if (newsize <= Size())
	{
		//return byteArray_ with unchanged size
	}

	else if (newsize == 0)
	{
		std::cerr << "** BitVector error: memory allocation failure -- terminating program.\n";
		exit(EXIT_FAILURE);
		//return;
	}

}

Now, I don't know what the 'Size' member function returns exactly, but it's safe to assume it naively returns the number of elements in the bit vector, which is fine.

In that case, what do you think lines 16 and 30 are doing? How many iterations will the for-loop on line 16 perform?

[nyvrem]

Hi xismn,

Thank you for putting my code into codetags. My javascript wasn't working on my browser.

Yes the Size member function returns the number of elements in the bit vector. Its implementation is

   size_t BitVector::Size()
   // return size of bitvector
  {
    return 8 * byteArraySize_;
  }

So my intention for line 16 is to set each index in each bit in the newByteArray to be the same to have the same value in the original byteArray_. The for-loop is intended to perform iterations for every bit up to the original number of bits found in the original byteArray_. So if the original size is 24, when I call expand function with size_t 30 parameter value, the remaining 6 will be 'Unset' to '0' value in the loop in line 20.


Meanwhile the Test member function I used in the for-loops to set the value to the indices is implemented as shown:

bool BitVector::Test  (size_t index) const
  // return bit value
  // ByteNumber returns number of bytes in bitvector given index 
  // Mask returns bit number of the byte given index
  {
    return 0 != (byteArray_[ByteNumber(index)] & Mask(index));
  }

If size_t newsize is less than the size of the original byteArray_ as in line 30, I intend for no changes to the values of the bits.

[xismn]

I reread your original post. You're saying that 'Expand' only fails when you give it a 'newsize' larger than 24? That would surprise me, it seems to me your code should fail all the time.

What I was getting at in my first post was that you've got an "off-by-one" error. On line 16 of the snippet I copy-and-pasted in my previous post, the value of 'i' in the for-loop will go from 0-Size(). However, the last element in your container is located at index Size()-1, so accessing index Size() is like trying to access an non-existent element just past the very last element, hence the error.

You may fix this by changing this:
for (size_t i = 0; i <= Size(); ++i)

to this:
for (size_t i = 0; i < Size(); ++i)

Disregard what I said in my previous post about line 30.