Tree driving me nuts!

[Travis]

So this is a driving me nuts. I need some more eyes on this. I have a
written a Tree structure that mimics a Menu tree for a kiosk (no
sorting, infinite children per node). Each node contains a pointer to
its parent and a vector of children nodes. Here is a snippet of the
pertinent bits driving me crazy.

MenuTreeNode(const NODE_TYPE &d, MenuTreeNode<NODE_TYPE> *p = NULL) :
data(d)
{
parent = p;
}

template< class NODE_TYPE >
MenuTreeNode<NODE_TYPE>* MenuTree<NODE_TYPE>::InsertNode(const
NODE_TYPE &parent, const NODE_TYPE &value)
{
if (menutree::debug) { std::cout << "(MenuTree::InsertNode)
Entering..." << std::endl; }

MenuTreeNode<NODE_TYPE>* newNode = NULL;

if (rootPtr == NULL)
{
if (menutree::debug) { std::cout << "(MenuTree::InsertNode)
Empty tree, adding node as root..." << std::endl; }

// root/first node
// disregard the parent
newNode = rootPtr = new MenuTreeNode<NODE_TYPE>(value);
}
else
{
if (menutree::debug) { std::cout << "(MenuTree::InsertNode)
Looking for parent " << parent << "..." << std::endl; }

// find the parent
MenuTreeNode<NODE_TYPE>* parentNode = GetNode(parent);
if (menutree::debug) { std::cout << "(MenuTree::InsertNode)
Found parent node " << parentNode->GetData() << "..." << std::endl; }
// create the new node
//newNode = new MenuTreeNode<NODE_TYPE>(value, parentNode);
MenuTreeNode<NODE_TYPE>* newN = new
MenuTreeNode<NODE_TYPE>(value, parentNode);
if (menutree::debug) { std::cout << "(MenuTree::InsertNode)
parent node = " << parentNode->GetData() << "..." << std::endl; }
if (menutree::debug) { std::cout << "(MenuTree::InsertNode)
Inserting new node " << newN->GetData() << " with parent " <<
parentNode->GetData() << "..." << std::endl; }

// insert new node as a child of the parent
parentNode->children.push_back( newN );
}

if (menutree::debug) { std::cout << "(MenuTree::InsertNode)
Exiting..." << std::endl; }

return newNode;
}


so here's the part driving me crazy. My GetNode() function appears to
work. The output of "Found parent node" is correct. Then I allocate
the new node with the value and parentNode and the next output of
"Parent Node = " is wrong! It says that the parentNode->GetData() is
newN just created.

Heeeelllpppp!

 

[Travis]

My bad I realize the formatting is miserable here. This should be
easier http://pastebin.com/m6d12f27c . Thanks.

 

[kwikius]

My bad I realize the formatting is miserable here. This should be
easierhttp://pastebin.com/m6d12f27c. Thanks.

Difficult to say, but don't see why you need to call GetNode(parent)
as you pass in parent as arg..

If the function is static member function of MenuTree,

template< class NODE_TYPE >
MenuTreeNode<NODE_TYPE>*
MenuTree<NODE_TYPE>::InsertNode(const
NODE_TYPE &parent, const NODE_TYPE &value
)
{
MenuTreeNode<NODE_TYPE>* node
= new MenuTreeNode<NODE_TYPE>(
value, parent
);
parent.children.push_back(
node;
);
return node;
}

But difficult to say from what you provided.

regards
Andy little

 

[Travis]

Difficult to say, but don't see why you need to call GetNode(parent)
as you pass in parent as arg..

If the function is static member function of MenuTree,

template< class NODE_TYPE >
MenuTreeNode<NODE_TYPE>*
MenuTree<NODE_TYPE>::InsertNode(const
NODE_TYPE &parent, const NODE_TYPE &value
)
{
   MenuTreeNode<NODE_TYPE>* node
   = new MenuTreeNode<NODE_TYPE>(
         value, parent
   );
   parent.children.push_back(
      node;
   );
   return node;

}

But difficult to say from what you provided.

regards
Andy little

Well I pass in the NODE_TYPE of the parent, not the pointer to the
parent in the tree. So I have to find it and then add the new node as
a child of that new node. Is there an easier way to accomplish the
same thing?

Thanks

 

[kwikius]

Well I pass in the NODE_TYPE of the parent, not the pointer to the
parent in the tree. So I have to find it and then add the new node as
a child of that new node. Is there an easier way to accomplish the
same thing?

Whats the NODE_TYPE of the parent?

Ideally you should post a cut down version of your code showing enough
so that the types and functions and relevant contexts are available.
Otherwise its not really possible to help.

regards
Andy Litle

 

[Travis]

Whats the NODE_TYPE of the parent?

Ideally you should post a cut down version of your code showing enough
so that the types and functions and relevant contexts are available.
Otherwise its not really possible to help.

regards
Andy Litle

Yeah I apologize. It's just a lot of code to attach. The NODE_TYPE in
this case is actually a custom class. Nothing fancy, basically just
holds some strings.

 

[kwikius]

Yeah I apologize. It's just a lot of code to attach. The NODE_TYPE in
this case is actually a custom class. Nothing fancy, basically just
holds some strings

Ah. That explains everything.. Not!



regards
Andy Little

 

[Travis]

Ah. That explains everything.. Not!



regards
Andy Little

Haha sorry. I'm going to try using the tree with a standard type as
the NODE_TYPE like int and see if that exposes a problem elsewhere. I
will let you know. Thanks.

 

[Travis]

Ah. That explains everything.. Not!



regards
Andy Little

Well of course worst possible scenario. The tree works like a champ
with string and int as the node type. As soon as I use my custom type
I get the weird-as-all-get-out problems I described initially.

 

[Jerry Coffin]

(e-mail address removed)>, (e-mail address removed)
says...

So this is a driving me nuts. I need some more eyes on this. I have a
written a Tree structure that mimics a Menu tree for a kiosk (no
sorting, infinite children per node). Each node contains a pointer to
its parent and a vector of children nodes. Here is a snippet of the
pertinent bits driving me crazy.

Why not have each node literally contain a vector of child nodes?

struct node {
std::vector<node> children;

std::string name_;
node *parent_;

node(node *parent, std::string const &name)
: parent_(parent), name_(name)
{}
};

Of course, the code you posted isn't sufficient to figure out exactly
what a node should really support, but from your description, it sounds
like you have a problem with the memory management. That's fairly common
when manually managing dynamic memory, especially for a semi-complex
structure like an N-way tree. Eliminating the manual memory management
tends to help keep the complexity under control, though until or unless
you describe the remainder of what you want the code to do, it's
impossible to say what else will be needed or where your problem may be
arising.

 

[Kai-Uwe Bux]

(e-mail address removed)>, (e-mail address removed)
says...

Why not have each node literally contain a vector of child nodes?

struct node {
std::vector<node> children;

Do you mean std::vector<node*>?

If you mean what you wrote, the code is not guaranteed to compile and if it
does, it has undefined behavior since node is an incomplete type at this
point and therefore std::vector<node> is not good. See [17.4.3.6/2].

std::string name_;
node *parent_;

node(node *parent, std::string const &name)
: parent_(parent), name_(name)
{}
};

Of course, the code you posted isn't sufficient to figure out exactly
what a node should really support, but from your description, it sounds
like you have a problem with the memory management. That's fairly common
when manually managing dynamic memory, especially for a semi-complex
structure like an N-way tree. Eliminating the manual memory management
tends to help keep the complexity under control, though until or unless
you describe the remainder of what you want the code to do, it's
impossible to say what else will be needed or where your problem may be
arising.

Best

Kai-Uwe Bux

 

[kwikius]

Well of course worst possible scenario. The tree works like a champ
with string and int as the node type. As soon as I use my custom type
I get the weird-as-all-get-out problems I described initially.

Try doing some tests on the nodetype outside the tree. Things such as
copy construction, assignment etc, and/or whatever functions you are
calling in the real situation.

Post the code for your node-type class (or ideally a minimally cut
down version that demonstrates the same problem) and I bet someone
here will see what the problem is.

regards
Andy Little

 

[Jerry Coffin]

Jerry Coffin wrote:

[ ... ]

Do you mean std::vector<node*>?

Oops -- yes. Looking back at it, that may have been kind of a Freudian
slip; if you could put a vector<node> there, it would be kind of cool,
quite possibly relieving you of even more of the memory management, but
I was just thinking of removing the requirement for managing a dynamic
array.

 

[James Kanze]

Do you mean std::vector<node*>?

If you mean what you wrote, the code is not guaranteed to
compile and if it does, it has undefined behavior since node
is an incomplete type at this point and therefore
std::vector<node> is not good. See [17.4.3.6/2].

And even if it happens to work in some cases... I hate to think
of what's going to happen to the parent pointer he used (a
node*) when the parent's parent gets more children.

Within a graph, nodes more or less have identity. Which means
no copying. Unless...

struct node
{
std::vector< int > children ;
int parent ;
static std::vector< node >
ourHome ;
// ...
} ;

All of the nodes in ourHome, with links being implemented as
indexes into ourHome.

(And no, I'm not really recommending anything like that.
Except maybe as a joke, or for programmers used to Fortran IV.)