St_tree insert method

[junwangcas]

Dear Erik, your st_tree is very useful, and fortunately I found it. when I start using it, however, I come across a problem. I want to use the iterator to insert node, and the insert method should return with the child's iterator. I see the insert method return nothing in the source code. Could you help me!

[erikerlandson]

I will take a look and review the st_tree semantics for insertion. What variety of tree are you using? (random access, ordered, keyed?) Can you post your code, or a simple example?

[junwangcas]

I use raw<> CSModel. When I try to use MyTreeType::iterator n_it=MyTree.insert( treenode ); problem occur. Then I see your source code: void insert(*);

[erikerlandson]

----- Original Message -----

I use raw<> CSModel. When I try to use MyTreeType::iterator n_it=MyTree.insert( treenode ); problem occur. Then I see your source code: void insert(*);

I think I now recall the issue. When inserting into a tree<>, only a unique root node is inserted. There is no iterator, per se, at this level: either there is a root node inserted, which is accessible by my_tree.root(), or not. Note that when you insert into a node_type, that does return an iterator. For example, tree.root().insert(*) returns an iterator from tree.root(), as that is a node_type.

This asymmetry is a consequence of my decision to define a tree<> as being a separate kind of object from tree<>::node_type, which I did to allow a well-defined concept of an empty tree containing no nodes. I went back and forth on this for a long time, and truthfully I think I'd not do it that way again if I ever do another tree implementation.

So, this behavior was a deliberate design decision, and not technically a bug. In principle, I might create a new variety of iterator at the tree<> level, which would effectively either iterate over the single root element, or empty sequence if the tree<> is empty and has no root element. Then I could return an iterator for tree<>.insert(). I'm not sure it's worth the extra machinery to support it.

If you want to work in a style where tree<> is a recursive type, and all nodes are trees, my thinking was that you could begin by inserting a root node (of type tree<>::node_type) into the tree<>, and then sort of ignore the tree<>, and work only with tree.root(), so all your logic is focused on tree<>::node_type objects.

[junwangcas]

On 03/01/2014 00:07, Erik Erlandson wrote:

----- Original Message -----

I use raw<> CSModel. When I try to use MyTreeType::iterator n_it=MyTree.insert( treenode ); problem occur. Then I see your source code: void insert(*);

I think I now recall the issue. When inserting into a tree<>, only a unique root node is inserted. There is no iterator, per se, at this level: either there is a root node inserted, which is accessible by my_tree.root(), or not. Note that when you insert into a node_type, that does return an iterator. For example, tree.root().insert(*) returns an iterator from tree.root(), as that is a node_type.

This asymmetry is a consequence of my decision to define a tree<> as being a separate kind of object from tree<>::node_type, which I did to allow a well-defined concept of an empty tree containing no nodes. I went back and forth on this for a long time, and truthfully I think I'd not do it that way again if I ever do another tree implementation.

So, this behavior was a deliberate design decision, and not technically a bug. In principle, I might create a new variety of iterator at the tree<> level, which would effectively either iterate over the single root element, or empty sequence if the tree<> is empty and has no root element. Then I could return an iterator for tree<>.insert(). I'm not sure it's worth the extra machinery to support it.

If you want to work in a style where tree<> is a recursive type, and all nodes are trees, my thinking was that you could begin by inserting a root node (of type tree<>::node_type) into the tree<>, and then sort of ignore the tree<>, and work only with tree.root(), so all your logic is focused on tree<>::node_type objects.

— Reply to this email directly or view it on GitHub https://github.com/erikerlandson/st_tree/issues/12#issuecomment-31462151.

Thank you Erik, You explained very clearly and patiently, now I figure out where the issue lies.

[erikerlandson]

Thank you Erik, You explained very clearly and patiently, now I figure out where the issue lies.

I'm happy to help. If I close this as "not-a-bug", will that work for you?

[junwangcas]

On 03/01/2014 23:54, Erik Erlandson wrote:

Thank you Erik, You explained very clearly and patiently, now I figure out where the issue lies.

I'm happy to help. If I close this as "not-a-bug", will that work for you?

— Reply to this email directly or view it on GitHub https://github.com/erikerlandson/st_tree/issues/12#issuecomment-31531024.

OK! Thank you.

[erikerlandson]

Closing "not-a-bug"