What could I improve in this code? Any constructive criticism is highly appreciated, especially about the recursion and how I could make the code more legible/understandable - because even I'll have issues to understand what's what if I look at it in a few days (and I couldn't really find a way to explain in comments the recursive methods):

#include <vector>
#include <string>
#include <iostream>
#include <fstream>

class Branch
{
	friend class Tree;

private:
	Branch* parent;
	std::vector<Branch*> children;
	
	int y;
	int x;

private:
	Branch()
		:parent(0), x(0), y(0)
	{
	}

	Branch(const Branch& another)
	{
	}

	~Branch()
	{
		parent = 0;
		children.clear();
		x = 0;
		y = 0;
	}

private:

	//find the index in the children
	unsigned int findIndex()
	{
		//assume parent != 0
		for (unsigned int k = 0; k < parent->children.size(); k++)
		{
			if (parent->children[k] == this)
				return k;
		}
		//if it's not part of the children I messed somewhere else in the code
		//so you'll get an out of bounds index
		return parent->children.size(); 
	}

	void shiftChildren(int shift)
	{
		for (auto iter = children.begin(); iter != children.end(); iter++)
		{
			(*iter)->x += 2 * shift;
			(*iter)->shiftChildren(shift);
		}
		return;
	}
	
	//shift the parents by shift
	//and every other cell right of our cell by shift
	void shiftRightSide( int shift )
	{
		if (parent == 0)
			return;
		parent->x += shift;
		for (unsigned int k = findIndex()+1; k<parent->children.size(); k++)
		{
			parent->children[k]->x += 2 * shift;
			parent->children[k]->shiftChildren(shift);
		}
		return parent->shiftRightSide( shift );
	}

	Branch* findRightmost()
	{
		if (children.empty())
			return this;
		children.back()->findRightmost();
	}

	//ignore this
	int countSpaces(const std::string& str)
	{
		if (str == "")
			return 0;
		unsigned int counter = 0;
		for (unsigned int k = 0; k < str.size(); k++)
		{
			if (str[k] == ' ')
				counter++;
		}
		return counter+1;
	}

	void displayChildren(std::vector<std::string>& map, unsigned int level)
	{
		if (children.empty())
			return;
		level++;
		if (map.size()-1 < level)
		{
			map.push_back("");
		}

		int prevX = map[level].size();
		for (auto iter = children.begin(); iter != children.end(); iter++)
		{
			for (int k = 0; k < (*iter)->x - prevX; k++)
			{
				map[level] += " ";
			}
			map[level] += "*";
			(*iter)->displayChildren(map, level);
			prevX = (*iter)->x+1;
		}

		return;
	}


};

class Tree
{


private:
	std::vector<Branch*> branches;

public:

	Branch root;
	int dx;
	int dy;

public:

	Tree( int dx = 1, int dy = 1)
		:dx(dx), dy(dy)
	{
	}

	Branch* add(Branch& another)
	{
		Branch* temp = new Branch();
		branches.push_back(temp);

		temp->parent = &another;
		temp->x = another.x;
		temp->y = another.y + dy;
		if (!another.children.empty())
		{
			//just for spacing - doesn't work
			//if (another.children.back()->findRightmost() == another.children.back())
			//{
				temp->x = another.children.back()->findRightmost()->x + 2*dx;
				temp->shiftRightSide(dx);
			/*}
			else
			{
				temp->x = another.children.back()->findRightmost()->x + 4 * dx;
				temp->shiftRightSide(2*dx);
			}*/
			
			
		}
		another.children.push_back(temp);

		return temp;
	}

	void printStructure( std::ostream& os )
	{
		std::vector<std::string> map;
		map.push_back("");
		for (int k = 0; k < root.x; k++)
		{
			map[0] += " ";
		}
		map[0] += "*";
		root.displayChildren(map, 0);

		for (unsigned int k = 0; k < map.size(); k++)
		{
			/*map[k] += "\n";
			os.write(map[k].c_str(), map[k].size());*/
			os << map[k] << std::endl;
		}

		return;
	}

	void populate(Branch& another, int level)
	{
		level--;
		if (level == 0)
			return;
		Branch* temp = 0;
		for (int k = 0; k < std::rand() % 5; k++)
		{
			temp = add(another);
			populate(*temp, level);
		}
	}

	~Tree()
	{
		for (auto iter = branches.begin(); iter != branches.end(); iter++)
		{
			delete *iter;
		}

		branches.clear();
		dx = 0;
		dy = 0;
	}
};


int main()
{
	Tree myTree;
	myTree.populate(myTree.root, 10);
	std::ofstream file("tree.txt");
	myTree.printStructure(file);
	file.close();

	//std::cin.sync();
	//std::cin.ignore();
	return 0;
}

It's supposed to create a structure of a tree and print it (use notepad to open it).

A few things I saw:

• It's weird that Branch class has everything set to private and Tree class almost everything set to public. Usually you have a class with both private and public stuff, objects should be designed to live "alone" as much as possible. A Branch should have some behaviour as a branch itself, right now only the Tree class have access to it. I'm not saying this is wrong, just think it would be better if Branch wasn't a friend class of Tree and had some public methods. Most languages do not support friend classes, C++ is the only one I know.
• Some times to create a Tree you don't need 2 classes, you can think of a Branch as another smaller Tree. A Tree then consists of a list of Tree childrens and, if you need the parent, a reference to the parent Tree.
• Your Branch copy constructor doesn't do anything. It should set the object's values, but now it's setting the object on an undefined state.
• You don't need to set int (or float, or boolean) values to 0 on the destructors, they're ment to release memory, close streams and things like that. The children branches could be destroyed there instead of the Tree destructor.
• The error checking will give you some problems. For example, in "findIndex" instead of a comment saying "assume parent != 0", check if it's null, and throw an exception or do an assert. If you couldn't find the index you return an "out of bounds index" that's the size of parent->children, which from the outside of the function would look like a perfectly valid index value. I would return a signed int, and "-1" if the item isn't there.
• The Tree class has dx and dy as public and there's no need for it. Also, you have a "root" Branch and a vector of Branches, that looks weird too. The branches in the vector are all the branches of the tree? Why do you need that? Can't you access them recursivelly starting from the root? It looks like you can have problems updating 2 vectors (this one and the childrens of a branch) for one object.
• I don't understand what "x", "y", "dx" and "dy" do, it doesn't look like something a Tree and Branches would have, and can't follow what the code does with them. Maybe you can name them with something more meaningful?
• The printStructure and displayChildren methods are hard to follow, some comments could be useful.

• It's weird that Branch class has everything set to private and Tree class almost everything set to public. Usually you have a class with both private and public stuff, objects should be designed to live "alone" as much as possible. A Branch should have some behaviour as a branch itself, right now only the Tree class have access to it. I'm not saying this is wrong, just think it would be better if Branch wasn't a friend class of Tree and had some public methods. Most languages do not support friend classes, C++ is the only one I know.

It's because I don't want people to be able to create/delete instances of class branch. I basically want to abstract that functionality from the user. So that class Tree can manage the allocated memory. I don't like using friend too, but I couldn't think up anything better.

• Some times to create a Tree you don't need 2 classes, you can think of a Branch as another smaller Tree. A Tree then consists of a list of Tree childrens and, if you need the parent, a reference to the parent Tree.

Before I coded the tree variant, I had made it with only a branch class. I had to code a freeBranches() function that deallocates the memory for the branches - my concern was that you could easily forget to free the branches at the end of the program, while with the Tree approach, whenever the Tree destructor is called it deallocates the memory for the branches of that tree. dx,dy,branches used to be static too.

• Your Branch copy constructor doesn't do anything. It should set the object's values, but now it's setting the object on an undefined state.

It's not supposed to do anything, I just wanted to define it as private so it won't be accessible outside of the class.

• You don't need to set int (or float, or boolean) values to 0 on the destructors, they're ment to release memory, close streams and things like that. The children branches could be destroyed there instead of the Tree destructor.

I have the habit to do it, so that in case I mess up and try to access an instance that I've already deleted I can see from the variables (all =0) that it was deleted earlier on.

• The error checking will give you some problems. For example, in "findIndex" instead of a comment saying "assume parent != 0", check if it's null, and throw an exception or do an assert. If you couldn't find the index you return an "out of bounds index" that's the size of parent->children, which from the outside of the function would look like a perfectly valid index value. I would return a signed int, and "-1" if the item isn't there.

It used to have a check - hence the comment, but it's a helper function that is called only once in shiftRightSide(), and it's called right after a parent check so I should be sure that parent != 0. I am returning out of bounds, because again - the function is only used as a helper function - and what's more it's result is added with 1 - which would basically make shiftRightSide() behave incorrectly if I return -1.

• The Tree class has dx and dy as public and there's no need for it. Also, you have a "root" Branch and a vector of Branches, that looks weird too. The branches in the vector are all the branches of the tree? Why do you need that? Can't you access them recursivelly starting from the root? It looks like you can have problems updating 2 vectors (this one and the childrens of a branch) for one object.

The user is supposed to have access to them - if he wants to have a different spacing between the branches.I need the branches vector so I can deallocate the memory easily. I could probably do the same with recursion, but I am not that confident in my recursive functions authoring skills - I code them by intuition for now - I should probably systematize my knowledge. I didn't get what you meant with "you can have problems updating 2 vectors"

• I don't understand what "x", "y", "dx" and "dy" do, it doesn't look like something a Tree and Branches would have, and can't follow what the code does with them. Maybe you can name them with something more meaningful?

I can't think up more meaningful names to be honest. x and y are the x and y coordinates of a branch, and dx and dy is the offset between branches (dy serves nothing for now - it could if I had a graphical visualization).

• The printStructure and displayChildren methods are hard to follow, some comments could be useful.

Note taken.

It's also fine to return -1 as an unsigned int to indicate an error condition.

I would get a wrong result in shiftRightSide() if I do this:

for (unsigned int k = findIndex()+1; k<parent->children.size(); k++)
        {
            parent->children[k]->x += 2 * shift;
            parent->children[k]->shiftChildren(shift);
        }

-1 + 1 = 0, no matter whether it's singed or unsigned.

If you are using a C++11 compiler, when initializing your pointers to nothing, you should use nullptr instead of 0.

From what I read on msdn, I didn't quite get what are the advantages to be honest, can you explain it in a simple fashion(with an example)?

Also, member functions that don't modify anything can be declared const.

I know that, though I fail to apply it in practice...

Thanks a lot for the feedback guys. If you think that any of the reasons I gave for the design decisions are flawed (or if it could be done better) please say so.

P.S. Gamedev killed my whole post, after it got stuck on code...

It's because I don't want people to be able to create/delete instances of class branch. I basically want to abstract that functionality from the user. So that class Tree can manage the allocated memory. I don't like using friend too, but I couldn't think up anything better.

Maybe you can define the Branch class inside the Tree class, so the Branch class can't even be accessed form outside. It's good for implementing Lists and Nodes for example, and could apply to a Tree and Branches. Look here: http://stackoverflow.com/questions/4571355/why-would-one-use-nested-classes-in-c

It doesn't look pretty, but this way you really hide that Branch class.

Before I coded the tree variant, I had made it with only a branch class. I had to code a freeBranches() function that deallocates the memory for the branches - my concern was that you could easily forget to free the branches at the end of the program, while with the Tree approach, whenever the Tree destructor is called it deallocates the memory for the branches of that tree. dx,dy,branches used to be static too.

If you deallocate all the children branches of a branch on the destructor it would work, you only need to remember deleting the root branch if you created it on the heap.

Something like this:

class Branch {
  std::vector<Branch*> childrens;

  ~Branch() {
    for (//iterate over childrens)  {
      delete childBranch;
    }
  }

  // everything else
}

void main() {
  Branch tree; //the destructor will be called automatically when exiting
  
  Branch* anotherTree = new Branch();

  //more stuff

  delete anotherTree; //this will call the destructors of every branch
}

It's not supposed to do anything, I just wanted to define it as private so it won't be accessible outside of the class.

OK, it was hard to tell since everything was private. If you define the Branch class inside the Tree class as I said before you don't need to worry about this.

I have the habit to do it, so that in case I mess up and try to access an instance that I've already deleted I can see from the variables (all =0) that it was deleted earlier on.

You can't see the variables inside an instance you already deleted, the memory it was using could have anything, even data from a newer object. It's not "bad" to set everything to 0, but don't use it for debugging purposes.

It used to have a check - hence the comment, but it's a helper function that is called only once in shiftRightSide(), and it's called right after a parent check so I should be sure that parent != 0. I am returning out of bounds, because again - the function is only used as a helper function - and what's more it's result is added with 1 - which would basically make shiftRightSide() behave incorrectly if I return -1.

That's OK, if you know something would be there don't need to recheck, the comment confused me, it looked like a parent == 0 could happen. About the problem using the returned value for shiftRightSide, consider doing it differently. It's harder to understand your code if it's intended to work the same way for every valid value AND the "out of bounds" value. It may be a clever way to avoid some "if" checks, but it doesn't make sense that what would be an error code makes everything work. I would do an extra step:

int index = findIndex(/* args... */);

if (index == -1)
  index = parent->childrens.size();

The user is supposed to have access to them - if he wants to have a different spacing between the branches.I need the branches vector so I can deallocate the memory easily. I could probably do the same with recursion, but I am not that confident in my recursive functions authoring skills - I code them by intuition for now - I should probably systematize my knowledge. I didn't get what you meant with "you can have problems updating 2 vectors"

What I ment was that, if you add a child to a branch, you also have to add it to the branches vector of the Tree. If you wanted to add more branches later, or delete some, you would need to update both the branches childrens and the tree branches. Putting everything in 2 places is adding one more source for bugs :P.

I can't think up more meaningful names to be honest. x and y are the x and y coordinates of a branch, and dx and dy is the offset between branches (dy serves nothing for now - it could if I had a graphical visualization).

I'm not sure, isn't "y" the level for example? Or it means something else?

It doesn't look pretty, but this way you really hide that Branch class.

It's plenty good actually - I guess that's what I was looking for, thanks.

There's an issue with this though:

class Branch {
  std::vector<Branch*> childrens;

  ~Branch() {
    for (//iterate over childrens)  {
      delete childBranch;
    }
  }

  // everything else
}

Well I guess it would work with a recursive function:

void destroyChildren()
{
        for (auto iter = children.begin(); iter != children.end(); iter++)
	{
		childBranch->destroyChildren();
		delete childBranch;
	}
	return;
}

I hope I didn't think up some bs recursive function, cause I'm scared to test it in my code.

Though I guess now is the moment to ask - what works better(faster) - going through your structure with a recursive function, or having things stored in a vector and using brute force to solve the issues (for example I had a variant of the same program that did everything with loops rather than recursive functions (though it did pretty much the same now that I think about it))?

It's harder to understand your code if it's intended to work the same way for every valid value AND the "out of bounds" value. It may be a clever way to avoid some "if" checks, but it doesn't make sense that what would be an error code makes everything work. I would do an extra step:

You are right. Till now whenever I was facing such situations I was always wondering whether to hardcode it or to do a check even if I know what I am going to get. I'd try to go for readability over needless optimizations from now on.

What I ment was that, if you add a child to a branch, you also have to add it to the branches vector of the Tree. If you wanted to add more branches later, or delete some, you would need to update both the branches childrens and the tree branches. Putting everything in 2 places is adding one more source for bugs

I actually wanted to dodge this issue by implementing branches.push_back() in the ctor of branches, but for that reason it would need to see the branches vector which is in Tree. And I've actually faced the problems with deleting you are talking about the previous time I coded something like this (it was not in c++ though ,and had a graphical visualization), I had to manage a few storage class instances, and I must say I was accessing a lot of null pointers, just because I forgot to remove an element here or there.

I'm not sure, isn't "y" the level for example? Or it means something else?

It should be - but I got tired of trying to visualize the tree in text format - especially when I know how easy it is to do with a graphics library. This visualization is just a makeshift solution.

The project used to be for an editor for a text adventure game(I dropped it a long time ago, but decided to code the structure with recursion just as an exercise), basically the branching represents the branching of the story, so the tree/branches was more like a data container + info for graphical visualization(x,y,dx,dy). It could be used to represent folders too.

Thanks a lot for all the feedback.

On a side note (I'm not really sure whether I should make a new thread for this) speaking of nested classes and classes design. I cannot think of a way to code this without a friend declaration:

//Let's say we have a class Engine that can draw and load our meshes
//However we shouldn't be able to create a mesh - that should be delegated to
//the engine's function loadMesh, We should be able to do something like this.
Engine myEngine;
Mesh* myMesh = myEngine.loadMesh( "some_filename.3ds" );
myMesh.translate(1,3,5);
myMesh.rotate( 30, 45, 0 );

//however this should be illegal:
Mesh* mesh2 = new Mesh();

And here's what I think up of as a construction:

// ... includes
#include <vector>

class Mesh
{
	friend class Engine;

private:
	float transformationMatrix[4][4];
	ID3D11Buffer* vertexBuffer;
	ID3D11Buffer* indexBuffer;

public:
	void translate(const float vec[3]);
	void rotate(const float vec[3]);

private:
	Mesh();
	Mesh(const Mesh&);
	~Mesh();
};

class Engine
{
private:
	std::vector<Mesh*> meshes;
	//... stuff
public:
	//... stuff
	void loadMesh(std::string filename)
	{
		Mesh* temp = new Mesh;
		meshes.push_back(temp);
	}

	void drawMesh()
	{
		//draw the mesh by using the vertex and index buffers
		//and the transformation matrix
	}

	~Engine()
	{
		//...free stuff
		for (auto iter = meshes.begin(); iter != meshes.end(); iter++)
		{
			delete *iter;
		}
		meshes.clear();
	}
};

Any way to do it without friend declarations?