Math issues

[PiMaster]

I'm making a struct for creating arrays that have any number of dimensions, with any given type (templates), and I'm having a bit of trouble with the math for resizing the array... Any help?

http://pastebin.com/8bugysYT <--- array.h

http://pastebin.com/L9ivkfA0 <--- simple test

The test is supposed to output the fibonacci numbers going from top to bottom, left to right, like this:

1 8
1 13
2 21
3 34
5 55

[PiMaster]

Eh, maybe I was a bit naive to think you guys would look over 100 lines of code voluntarily... Here's the snippet I need help with:

//resizes the array, even with different dimensions
//resize(number of dimensions (-1 for current),<dimension sizes>...)
int resize(int ndim,...){
	if(ndim==0){
		error=no_dimensions;
		return 1;}
	int w=dimensions[0],size=1,a;
	int* ndata;
	va_list args;
	va_start(args,ndim);
	if(ndim==-1 || ndim==num_dimensions){
		for(a=0;a<ndim;++a){
			dimensions[a]=va_arg(args,int);
			size*=dimensions[a];}
		ndata=new T[size];
		size=size/dimensions[0];
		for(a=0;a<size;++a){
			memcpy(ndata+a*dimensions[0],data+a*w,MIN(w,dimensions[0]));}
		delete[] data;
		data=ndata;}
	else{
		delete[] dimensions;
		dimensions=new int[ndim];
		for(a=0;a<ndim;++a){
			dimensions[a]=va_arg(args,int);
			size*=dimensions[a];}
		ndata=new T[size];
		size=size/dimensions[0];
		for(a=0;a<size;++a){
			memcpy(ndata+a*dimensions[0],data+a*w,MIN(w,dimensions[0]));}
		delete[] data;
		data=ndata;}
	va_end(args);
	return 0;}

What I'm trying to do is resize the array and move the old elements to their corresponding positions, like this:

1 2
5 9

to

1 2 0 0
5 9 0 0

instead of

1 2 5 9
0 0 0 0

[PiMaster]

Ok, ok, maybe 35 lines is too much too... How's this?

delete[] dimensions;
dimensions=new int[ndim];
for(a=0;a<ndim;++a){
	dimensions[a]=va_arg(args,int);
	size*=dimensions[a];}
ndata=new T[size];
size=size/dimensions[0];
for(a=0;a<size;++a){
	memcpy(ndata+a*dimensions[0],data+a*w,MIN(w,dimensions[0]));}
delete[] data;
data=ndata;

[kbw]

Is resize a plain old function, or is it a member of the template class you mentioned?

[PiMaster]

It's a member function.

[kbw]

I think your resize is suffering from the same problems as realloc, it's doing too much. By too much, I mean it appears to be changing the number of dimensions as well as the size of each dimension. This is untenable.

The problem is you cannot validate your inputs, any possible input is a valid command for you to act on. Ultimately, the result is a long complicate functions who's correctness is difficult to validate.

I suggest you have a function that redimensions and a seperate one that resizes the dimensions. You can pass in a temporary that wraps an array of dimensions to help with the variable number of dimensions.

[abdallahijazi]

would you send the whole code please?

[PiMaster]

@kbw, I'll try to do that, and @abdallahijazi, I put the entire code (header and example) in the pastebin links above...

[PiMaster]

Ok, here's what I have so far:

T* change_dim(unsigned ndim,int* ndimv){
	int size=1,a;
	T* ndata;
	delete[] dimensions;
	dimensions=new int[ndim];
	for(a=0;a<ndim;++a){
		dimensions[a]=ndimv[a];
		size*=dimensions[a];}
	ndata=new T[size];
	return ndata;}

int resize(int ndim,...){
	if(ndim==0){
		error=no_dimensions;
		return 1;}
	int size=1,a;
	int* ndimv=new int[ndim];
	T* ndata;
	va_arg args;
	va_start(args,ndim);
	for(a=0;a<ndim;++a){
		ndimv[a]=va_arg(args,unsigned);}
	va_end(args);
	if(ndim!=-1 && ndim!=num_dimensions){
		T* ndata=change_dim(ndim,ndimv);
		???}
	else{
		???}
	delete[] ndimv;
	return 0;}

What do I put in place of "???"? I think that's where I'd put moving the old data to the new array, but what formula do I use?

[kbw]

I assume these are member functions of a templated class. I'd go for:

// change the number of dimensions to ndim.
// if ndim reduces the number of dimensions, elements are removed
// if ndim increases the number of dimensions, new elements are initialised with default_value 
void change_dim(unsigned ndim, T default_value = T());

With resize, you can either resize all the dimensions in one go:

// resize each dimension
int resize(const std::vector<size_t> &sizes);

or resize one dimension at a time:

// resize one dimension
int resize(unsigned dimension, size_t size);

[PiMaster]

But what about moving the old data?

[sanzilla]

But what about moving the old data?

are you looking for this function?
http://www.cplusplus.com/reference/stl/vector/reserve/

[PiMaster]

Something similar, I guess, except with any number of dimensions, and my array uses dynamically allocated arrays, not vectors...

Seriously, guys, the source is right here ---> http://pastebin.com/8bugysYT

[PiMaster]

Hello?

[kbw]

But what about moving the old data?

Quite simply, you create the new structure first, then copy the data over, then release the old data structures.

[Disch]

Nobody is really answering this guy's question.

Before I start... I see memcpy in there. You should not be using memcpy. memcpy works fine for POD types, but if you put a complex type (like a string) in this array, it will explode.

There are really 2 ways of doing this:

1) The harder way, which is similar to what vector does, is it allocates memory separately, then places the objects in memory with placement new.

2) The easier way, which is to just use the assignment operator.

Since you're having a hard time, I'd suggest option 2 for this task. The big downside to #2 is it doesn't allow you to destruct individual obejects which means every resize means a full reallocation and copy, even if you're reducing the overall size of the array.

Option 1 would be more efficient since you could over-allocate and reduce the number of buffer copies, but it would also make the code much more complicated.


When the dimension is shrinking, you simply only copy the necessary elements to the new buffer. When it grows, you copy all of them, and leave the others default constructed (assuming you're using option #2). But remember to copy with the assignment operator or std::copy. Don't ever use memcpy on templated types or the template will not work with complex types.

Anyway this is tricky since the dimension count is variable, so it's going to take some crafty pointer math.

Also, it's actually one of the few places I would use recursion. I'd probably do something like this:

void resize(const unsigned* newdims)  //you might want to use va_arg here, but I'm using an array to keep it simple.
{
  // ...error check and stuff...

  unsigned* mindims = new unsigned[num_dimensions];
  for(unsigned i = 0; i < num_dimensions; ++i)
    mindims[i] = std::min( newdims[i], dimensions[i] );

  T* newbuf = new T[newsize];

  T* dst = newbuf; // to prevent 'copy_dim' from changing newbuf/data
  T* src = data;

  copy_dim( num_dimensions - 1, dst, src, mindims, newdims );

  delete[] mindims;

  delete[] data;
  data = newbuf;
  std::copy(newdims,newdims + num_dimensions, dimensions);
}

// a private function
void copy_dim( unsigned dim, T*& newbuf, T*& oldbuf, const unsigned* mindims, const unsigned* newdims)
{
  if(!dim)  // if this is the lowest dim...
  {
    // copy the data over
    std::copy( newbuf, newbuf + mindims[dim], oldbuf );

    // then move the pointers to the next row
    newbuf += newdims[dim];
    oldbuf += dimensions[dim];
  }
  else  // otherwise, this is one of the higher dims
  {
    // copy the lower dims over
    for(unsigned i = 0; i < mindims[dim]; ++i)
        copy_dim( dim - 1, newbuf, oldbuf, mindims, newdims );

    // EDIT
    //   you'll need to adjust newbuf ptr here if newdims[i] is > mindims[i]
  }
}