OK. I complain about this every time. Please don't do this.
using namespace std;
It may be in every C++ book but in real programs (more than 100) lines it causes more problems than it is worth. You can easily get tangled up in all sorts of problems with name look-up. The whole point of std being so short (not standard) is so that it is simple to prefix items in the standard library easily. You can also selectively use using to bring specific objects into the current namespace.
using std::cout; // now you can use cout
// But try and scope it as much as possible
// preventing pollution is a good thing.
But personally I have got used to typing std:: in-front of everything.
When returning objects
string GetName() const;
prefer to return by reference. If you want to keep the object immutable return by const reference. Depending on usage it may be worth having two version a const and a non const version.
string& GetName();
string const& GetName() const;
Why do you need a SetParent()?
void SetParent(Node * parent);
This seems like you are exposing the implementation via the interface. This is binding your interface and tightly binding your implementation to this interface. I would remove this method. Remember that Node is a friend of itself so methods in Node can access and manipulate other objects of type Node (you trust yourself don't you).
There is absoilutely no reason to expose this.
Node * GetParent() const;
You pass pointers around too much.
Node * AddChild(Node * child);
OK. In a tree the ownership may seem obvious. But I would prefer to ownership explicitly defined by the code (this will prevent mistakes later). Thus you need to use smart pointers so that you explicitly define how ownership of pointers as they are passed around.
// No need to return anything.
// Explicitly pass ownership of the pointer.
void AddChild(std::auto_ptr<Node> child);
These are OK returning pointers. As here you are saying that there may be no result and you need to validate any result (checking for NULL) before it can be used. But you can pass string by const reference.
vector<Node*> FindChildren(string name) const;
Node * FindFirstChild(string name) const;
Node * FindLastChild(string name) const;
Node * FindNthChild(int nth, string name) const;
vector<string> ChildrenNames() const;
OK. Parent can be a pointer (as it potentially may be NULL).
Node * parent;
Children on the other hand are owned.
Normally I would go with boost::ptr_vector (as it exposes its members as object references rather than pointers) but in this particular case I would go with a vector of smart pointers (because I want to manage the pointers in this case).
No need to test for NULL before deleting
if (*it)
{
delete * it;
}
Just use::
delete (*it);
No point in calling clear. The destructor is about to destroy this object any way. By putting this here you are making the mainter think that there is something none obvious going on here.
children.clear();
// Just delete this function it is not required.
// See below on how to replace it.
/* void Node::SetParent(Node * parent_)
{
parent = parent_;
}*/
// No need for this. It is exposing internals without needing too.
/*Node * Node::GetParent() const
{
return parent;
}*/
// Replace call to set parent
void Node::AddChild(std::auto_ptr<Node> child)
{
// Check if the child is valid
if (child.get() == NULL)
{ return;
}
// child->SetParent(this);
// Check that the child is not already in a tree.
if (child->parent != NULL)
{ throw std::runtime_error("Something bad happened this node is already in a tree");
}
// Add it to the tree.
child->parent = this;
children.push_back(child);
// No need to return this
// You have to think why does this return the child
// I see no reason for this.
// return child;
}
So you only check this node and its children!!!!!
If so this function seems to be named incorrectly. Searching a tree is normally recursive. The function should check the current node then RECUSIVELY check each child.
vector<Node*> Node::FindChildren(string name) const
Iterators are not compared with < you need to test against !=. While we are here prefer to use prefix ++ (here it does not make much difference but in other places it can so it is a nice habbit to get into (especially with iterators)).
for(vector<Node*>::const_iterator it = children.begin(); it < children.end(); it++)
Is there a particular reason you use compare() rather than the more natural ==?
if (name.compare((*it)->name) == 0)
Try this:
std::vector<Node*> Node::FindChildren(std::string const& name) const
{
std::vector<Node*> children;
if (name == this->name)
{
children.push_back(this);
}
for(vector<Node*>::const_iterator it = children.begin(); it != children.end(); ++it)
{
if (*it)
{ it->FindChildren(name);
}
}
return children;
}
Again. Only checking the children. See notes above. Same comments as last function.
Node * Node::FindFirstChild(string name) const
Does this really have any meaning for a tree? The nth child in this tree. What about the next tree down. Seems like a very strange interface.
Node * Node::FindNthChild(int nth, string name) const
Why are you looping over the vector.
std::vector has direct element access with operator[] if you want to make sure you don't exceed the size of the array then use at() and it will validate the index before use.
What about granchildren?
vector<string> Node::ChildrenNames() const
Sure it works. But initialize variables on declaration (d). And scope your variables (ancestor) so there lifespan does not exceed their need. Also your control loop is all messed up (you are incrementing d not the value you are testing in the condition!!!!
int Node::Depth() const
{
int d;
Node * ancestor = parent;
for (d = 0; ancestor != NULL; d++)
{
ancestor = ancestor->parent;
}
return d;
}
Try this:
int Node::Depth() const
{
// I hate single letter variables.
// Make the name meaningful and represent what you are going to do with it.
//
// Short functions it does not matter. But for larger functions it makes
// it so much easier to search see all the usage of the variable.
int result = 0;
for (Node * ancestor = parent; ancestor;ancestor = ancestor->parent)
{
++result;
}
return result;
}
bool Node::IsLeaf() const
{
return (children.size() == 0) ? true : false;
// Easier to read/write as
return children.size() == 0;
}
bool Node::IsRoot() const
{
return (parent == NULL) ? true : false;
// Easier to read/write as
return parent == NULL;
}
