Recursive class method crashing the console

[Delca]

Hi everyone. While I have some experience with C, I am learning C++, and didn't found anything on the Internet about my kind of problem (or rather, solving it the way I want to).

My goal is to split a rectangle into different parts that are not overlapping each others.

For that, I decided to use a binary tree to represent each area ; a node being an area and its leaves being the two areas it will be split into.

I have a function called DivideNode which cuts an area, and another called DivideTill which splits the current node and applies itself to this node's children.

The problem is, after outputing the expected answer, the console crashes and doesn't return anything. Weirder, when I call the DivideNode after that, no problem at all.


Here is the class :

class node{

private :

int x,y,xlength,ylength, profondeur;
node* leftchild;
node* rightchild;

public :

node();
void DivideNode();
void DivideTill(int profondeurmax);
int GetX();
int GetY();
int GetXLength();
int GetYLength();
int GetProfondeur();
void SetX(int i);
void SetY(int i);
void SetXLength(int i);
void SetYLength(int i);
void SetProfondeur(int i);
~node();



};

The DivideNode() function :

void node::DivideNode(){

if (xlength==0||ylength==0){}
else{

leftchild = new node;
rightchild = new node;

leftchild->SetProfondeur(profondeur + 1);
rightchild->SetProfondeur(profondeur + 1);

if (leftchild != NULL){

leftchild->SetX(x);
leftchild->SetY(y);
leftchild->SetXLength(xlength);
leftchild->SetYLength(ylength/2);

}

if (rightchild != NULL){

rightchild->SetX(x);
rightchild->SetY(y + ylength/2);
rightchild->SetXLength(xlength);
rightchild->SetYLength(ylength/2);

}

printf("Main node : x%d y%d xL%d yL%d p%d\n", blablabla...);
printf("Left Child : x%d y%d xL%d yL%d p%d\n",  blablabla...);
printf("Right Child : x%d y%d xL%d yL%d p%d\n\n",  blablabla...);


}

}

The DivideTill() function :

void node::DivideTill(int profondeurmax){

if (profondeur<profondeurmax){
DivideNode();
leftchild->DivideTill(profondeurmax);
rightchild->DivideTill(profondeurmax);
}

}

Does anyone see something wrong here ?

[ne555]

¿How hard is to indent code?

void node::DivideTill(int profondeurmax){

  if (profondeur<profondeurmax){
    DivideNode();
    leftchild->DivideTill(profondeurmax);
    rightchild->DivideTill(profondeurmax);
  }

}
void node::DivideNode(){

  if (xlength==0||ylength==0){} //do nothing 

Now suppose that you execute DivideTill in a node were ylenght==0
The profondeur is small enough, so it will call at DivideNode that will do nothing. Later you will apply the recursion to its children...
But they don't exists, they weren't created by DivideNode, so they point to garbage.

You've also got memory leaks, as DivideNode overwrites the value of the pointers.

[Delca]

Sorry for the indentation. Being used to IDE that automatically indent your code isn't a good habit, I guess.

I didn't thought about this case, since the xlength, ylength and profondeur I chose do not allow xlength or ylength to be equal to 0, and removing the "if (xlength==0||ylength==0)" didn't change anything.

But when I run it, I get correct values. If I place a printf("Done."); at the end of DivideTill(), it correctly reaches this part of the function (before crashing at the end), meaning the first part of the function went well (maybe I'm wrong assuming that ?).

Also, if I do something like that :

node root;
//Here I initialize root like this : x=0, y=0, xlength=ylength=20, profondeur=0
root.DivideTill(3);
root.DivideNode();

Then the issue dissapears, and main() returns 0, indicating that all went fine.

Also, about the memory leaks : I thought that a memory leak occured when I overwrite the only pointer that was pointing to some variable, meaning that the latter was "lost" and therefore undeletable.
Since I initialize left/rightchild as NULL in the constructor, and only call DivideNode once on a given node, is this still a problem ?

[ne555]

Being used to IDE that automatically indent your code isn't a good habit, I guess.

It is good. You just need to copy-paste, so the indentation is preserved.

meaning the first part of the function went well (maybe I'm wrong assuming that ?).

Maybe, undefined behaviour is undefined. You could corrupt your memory by dereferencing a garbage pointer, but it will not necessary crash right there.
However get a debugger and perform a backtrace.

node root;
//Here I initialize root like this : x=0, y=0, xlength=ylength=20, profondeur=0
root.DivideTill(3);
root.DivideNode();

There you are calling at DivideNode twice (the first time is inside DivideTill). There you will be overwriting {left,right}child (memory leak)
Your all structure were hided, and you only see:
_root
__left (leaf)
__right (leaf)

So it seems that you've got a dangling pointer that you are trying to delete.

[Delca]

I think you got it right. The problem was in ~node(), which tried to delete children using garbage pointers. It seems solved now.

Thanks a lot, ne555. A debugger really is a useful tool when you know how to use it ; now I don't have excuses anymore.