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!

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

On Feb 8, 11:52pm, Travis <travis.bow...@gmail.com> wrote:
> 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

On Feb 8, 8:47pm, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> On Feb 8, 11:52pm, Travis <travis.bow...@gmail.com> wrote:
>
> > 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

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

On Feb 9, 6:39am, Travis <travis.bow...@gmail.com> wrote:
> On Feb 8, 8:47pm, kwikius <a...@servocomm.freeserve.co.uk> wrote:
>
>
>
>
>
> > On Feb 8, 11:52pm, Travis <travis.bow...@gmail.com> wrote:
>
> > > 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
>
> 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 .

regards
Andy Litle

On Feb 9, 11:39am, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> On Feb 9, 6:39am, Travis <travis.bow...@gmail.com> wrote:
>
>
>
> > On Feb 8, 8:47pm, kwikius <a...@servocomm.freeserve.co.uk> wrote:
>
> > > On Feb 8, 11:52pm, Travis <travis.bow...@gmail.com> wrote:
>
> > > > 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
>
> > 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 .
>
> 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.

On Feb 10, 7:02am, Travis <travis.bow...@gmail.com> wrote:
> On Feb 9, 11:39am, kwikius <a...@servocomm.freeserve.co.uk> wrote:

> > Whats the NODE_TYPE of the parent?

<...>

> 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

On Feb 10, 4:17am, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> On Feb 10, 7:02am, Travis <travis.bow...@gmail.com> wrote:
>
> > On Feb 9, 11:39am, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> > > Whats the NODE_TYPE of the parent?
>
> <...>
>
> > 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

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.

On Feb 10, 4:17 am, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> On Feb 10, 7:02 am, Travis <travis.bow...@gmail.com> wrote:
>
> > On Feb 9, 11:39 am, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> > > Whats the NODE_TYPE of the parent?
>
> <...>
>
> > 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

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.

In article <269b4ba8-b244-4dcb-a03f-
65d9d5504cba@i7g2000prf.googlegroups.com>, travis.bowers@gmail.com
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 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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jerry Coffin wrote:

> In article <269b4ba8-b244-4dcb-a03f-
> 65d9d5504cba@i7g2000prf.googlegroups.com>, travis.bowers@gmail.com
> 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;

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 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

On Feb 11, 4:41pm, Travis <travis.bow...@gmail.com> wrote:
> On Feb 10, 4:17 am, kwikius <a...@servocomm.freeserve.co.uk> wrote:
>
>
>
>
>
> > On Feb 10, 7:02 am, Travis <travis.bow...@gmail.com> wrote:
>
> > > On Feb 9, 11:39 am, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> > > > Whats the NODE_TYPE of the parent?
>
> > <...>
>
> > > 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
>
> 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

In article <fpam23$40i$1@aioe.org>, jkherciueh@gmx.net says...
> Jerry Coffin wrote:

[ ... ]

> > struct node {
> > std::vector<node> children;
>
> 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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

On Feb 18, 2:12 am, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
> Jerry Coffin wrote:
> > In article <269b4ba8-b244-4dcb-a03f-
> > 65d9d5504...@i7g2000prf.googlegroups.com>, travis.bow...@gmail.com
> > 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;

> 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.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34