I have noticed that the user defined polymorphic storage is unsymmetric: (deallocate_stored_type vs pClone_fcn)
void basic_tree<>::set(const stored_type& stored_obj)
{
if ( pData ) // if data node already exists, free memory
deallocate_stored_type(pData);
if ( pClone_fcn ) // use clone fcn if available
pData = pClone_fcn(stored_obj);
else
allocate_stored_type(pData, stored_obj);
}
deallocate_stored_type always use ::delete to free memory. If the user provide a Clone method by using some different memory model, the default ::delete may lead to violations. In my opinion, set_clone() should take parameters for both cloner and destroyer. Moreover, if it is feasible, exposing one policies: stored_type_allocator might be better because every STL container has a policy field for user-defined allocator.
Another thing, would you please tell me the constraints on stored_type and container_type of basic_tree? Does stored_type should support def_ctor, copy_ctor, opr= ? What interfaces should I provide to fit a container_type?
The last, I want to know why level_order_iterator is only forward_iterator? What is the complexity of its ++?
I'm a beginner of Generic programming. Please do not be annoyed by my rude questions. Answer them only when you feel good and very free. :P
Some comment on TCL:
Actually, last few days I was trying to build up a STL-like Tree container. It would be much similar to your TCL if accomplished. ^_^ I encountered a hardnut for iterators in 2D dimensions (extent / depth) and finally gave it up. Occasionally, I found TCL which is exactly what I wanted: tree & sequential_tree & unique_tree. When I designed my Tree container, these 3 trees are implemented by employing a policy on the template parameter. Your design is much better than mine and is tricky to avoid serveral technical swamp. Well done.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hello! The deallocation while providing a clone function is a good point that you noticed. The way that allocation and deallocation are set up in the TCL, which has recently changed to allow for custom allocation, is for the user to modify the two member variables in basic_tree, 'stored_type_allocator' and 'tree_type_allocator' to fit their needs. I tried to modify the TCL to allow the passing of an extra template parameter for the allocator, but due to limitations of VC6, was not allowed, and this was the next best solution. Thus, with this being the case, whether the user does or doesn't supply thier own clone function to the TCL, they will modify those allocator members to provide their custom allocation.
stored_type needs a default constructor, since objects of those types will be stored in STL containers. An explicit copy constructor for stored_type may be needed, if stored_type is a complex object or contains member pointers. The assignment operator is not needed by TCL, but, as always a good practice, if the copy constructor is provided, the assignment operator also should be.
The only interface needed for stored type, besides the ones mentioned above, are those for convienience. As mentioned in my other post, a constructor which allows you to build an object containing the 'key' for searching would be benifitial. Also, and public operation in stored type that could be accessed from the nodes 'get()' operation would be helpful.
You are very observant to notice that the level_order_iterator is a forward_iterator, rather than a bi-directional. This is because I found it impossible to implement a decrement operator for this descendant iterator due to the nature of this iteration type. It may be that there is a way, and I'd be open and grateful to any supplied code which performs this action.
You asked a good question about the complexity of the descendant iterators. Actually, I need to provide them on the website, along with the complexity of the child iterators also. Thanks for pointing this out, and I'll try to get this info on the site soon. ;)
Thanks again for your nice comments and suggestions on the TCL. It sounds like you have also spent some time on some of the same difficulties that I encountered when developing the TCL. One of the greatest challenges I encountered besides the normal complexities, was keeping the TCL compatible with the major versions of compilers, especially VC6. Many of the decisions I made during the development were due to the limitations from this particular compiler version.
Good luck with your project, and hope to hear back from you.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Yeah! I have ported your TCL to map-like trees. Would you please give your email to me? I can send it as well as examples to you.
Several improvement has been done:
- Remove the support for user-defined Cloner and Destroy.
- No longer store pointers in the node. Instread, store the entities of std::pair<key_type, mapped_type>. A lot of related functions has been modified.
- Remove the function basic_tree<>::insert(value_type* pStored_obj, tree_type* parent). Because now only entities of value_type can be stored in the tree, this function which overrided from basic_tree<>::insert(value_type& pStored_obj, tree_type* parent) is no use. This decision also improves type-safty.
- A helper function has been added.
Add
iterator insert(const value_type& obj);
for
iterator insert(const key_type& oid, const mapped_type& mapped_obj);
This function simplifies the modification in example codes.
Comment:
I have to give you many thanks due to your originally fantastic design. The class layers are very good deployed that only a few codes need modification for the transition from pointer to map-like entity version of TCL. It saves me a lot of time. Great!
Now there will be 2 versions for map-like TCL.
1. tree<key_type, mapped_type...>::insert(key, mapped, parentkey);
2. tree<value_type, key_extractor...>::insert(value_type_node, value_type_parent);
#1 has been implemented. #2 is under construction.
These 2 versions of tree will be used in very different cases.
#1 is for isolated key and mapped object. In another words, mapped_type do not possess the key.
#2 is for compond objects that the key is holded by value_type (ex: CAlpha, cRental). This is the case in original TCL.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Congratulations on getting your implemtation of a mapped tree working. If you'd like, you could email me your work to me via the link on my web page. I'll most likely be keeping my current implementation as it is, as I still feel it's better to have the design or the TCL like it is, with the heap allocation of the stored_type, and because there is already a large user base of the TCL. I'm glad that your implementation is working for your needs, however, and would be happy to check it out in the next couple weeks as I get time.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I have sent a revised TCL to the address < mhaas@datasoftsolutions.net >
Here are comments. This time I will focus on some insight of my design.
- The most important different between original and revised TCL is: the latter one DO NOT support default ctor.
To create a tree, the user should use the form below:
tree<key_type, mapped_type> mytree(key, obj);
instead of
tree<key_type, mapped_type> mytree;
mytree.set(key, obj);
This is reasonable because all trees should have their roots before growing up. ^_^ It is directly avoid key collision for all kinds of trees. Now the tree<>::set can only receive one parament with the type of mapped_type. After the tree is created or a node is inserted, the value of key_type becomes constant. There is no way to change the key unless erase that node. Therefore, now, unique_tree works well and the complexity of unique_tree<>::set function becomes Constant. This function in original TCL is wrong because of unguarded key-value modification.
- Unfortunately, I have to disable Orphan functions in unique_tree because they will use the default ctor of unique_tree which is forbidden in my design. But orphan mechanism is very useful. Maybe we can do some change in the implementation of Orphan funcitons to re-enable it.
- Although there is still a node_compare_type policy in unique_tree, I still want to argue to discard it. I'm worried about the efficiency of iterations along node_compare_type. Take std::map as example, an iterator of map implies an single order of nodes. If other orders of those nodes are needed, the user should build up different std::map with different key_type. It is important that the choice depends on the aim of users. Again, it is not the responsibility of TCL. Actually, I haven't go through find_ordered yet, but I guess if no other std::set holds nodes ordered by node_compare_type, the complexity of find_ordered can not go down to Logarithmic. Anyway, the original design of node_compare_type means there are 2 indexes for one node. If you implement to support this optional searching method on unique_tree, why didn't you implement it on all associate_tree? Why didn't you try to support multiple-index-searching policy? ex: tree<key_type, mapped_type, order1_cmp, order2_cmp, ... orderN_cmp>. In my opinion, we should keep TCL simple, neat, clean and perfect. ^_^
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Thank you for your kind help. This afternoon, when I rewrote TCL to bases on std::map container_type, I found a big design defect for the policy of allocators. As comparison, STL containers use allocator policy to manage NODES rather than value_type. But TCL impose an allocator to serve for value_type. I acknowledge that storing pointers in a tree will be spacial efficient if value_type is memory consuming. However, if only simple objects (ex: int, double, std::complex) will be stored, the dynamic allocation process will be redundant and will lead to poor performance for both space and time.
In my opinion, it is not TCL's resposibility to make the decision for storing entities or pointers. If we intrinsically implement TCL to store pointers, there will be no chance for users to store entities. TCL's allocator should serve storage for tree_type (the NODEs of trees), rather than value_type (or stored_type in your words).
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I have noticed that the user defined polymorphic storage is unsymmetric: (deallocate_stored_type vs pClone_fcn)
void basic_tree<>::set(const stored_type& stored_obj)
{
if ( pData ) // if data node already exists, free memory
deallocate_stored_type(pData);
if ( pClone_fcn ) // use clone fcn if available
pData = pClone_fcn(stored_obj);
else
allocate_stored_type(pData, stored_obj);
}
deallocate_stored_type always use ::delete to free memory. If the user provide a Clone method by using some different memory model, the default ::delete may lead to violations. In my opinion, set_clone() should take parameters for both cloner and destroyer. Moreover, if it is feasible, exposing one policies: stored_type_allocator might be better because every STL container has a policy field for user-defined allocator.
Another thing, would you please tell me the constraints on stored_type and container_type of basic_tree? Does stored_type should support def_ctor, copy_ctor, opr= ? What interfaces should I provide to fit a container_type?
The last, I want to know why level_order_iterator is only forward_iterator? What is the complexity of its ++?
I'm a beginner of Generic programming. Please do not be annoyed by my rude questions. Answer them only when you feel good and very free. :P
Some comment on TCL:
Actually, last few days I was trying to build up a STL-like Tree container. It would be much similar to your TCL if accomplished. ^_^ I encountered a hardnut for iterators in 2D dimensions (extent / depth) and finally gave it up. Occasionally, I found TCL which is exactly what I wanted: tree & sequential_tree & unique_tree. When I designed my Tree container, these 3 trees are implemented by employing a policy on the template parameter. Your design is much better than mine and is tricky to avoid serveral technical swamp. Well done.
Hello! The deallocation while providing a clone function is a good point that you noticed. The way that allocation and deallocation are set up in the TCL, which has recently changed to allow for custom allocation, is for the user to modify the two member variables in basic_tree, 'stored_type_allocator' and 'tree_type_allocator' to fit their needs. I tried to modify the TCL to allow the passing of an extra template parameter for the allocator, but due to limitations of VC6, was not allowed, and this was the next best solution. Thus, with this being the case, whether the user does or doesn't supply thier own clone function to the TCL, they will modify those allocator members to provide their custom allocation.
stored_type needs a default constructor, since objects of those types will be stored in STL containers. An explicit copy constructor for stored_type may be needed, if stored_type is a complex object or contains member pointers. The assignment operator is not needed by TCL, but, as always a good practice, if the copy constructor is provided, the assignment operator also should be.
The only interface needed for stored type, besides the ones mentioned above, are those for convienience. As mentioned in my other post, a constructor which allows you to build an object containing the 'key' for searching would be benifitial. Also, and public operation in stored type that could be accessed from the nodes 'get()' operation would be helpful.
You are very observant to notice that the level_order_iterator is a forward_iterator, rather than a bi-directional. This is because I found it impossible to implement a decrement operator for this descendant iterator due to the nature of this iteration type. It may be that there is a way, and I'd be open and grateful to any supplied code which performs this action.
You asked a good question about the complexity of the descendant iterators. Actually, I need to provide them on the website, along with the complexity of the child iterators also. Thanks for pointing this out, and I'll try to get this info on the site soon. ;)
Thanks again for your nice comments and suggestions on the TCL. It sounds like you have also spent some time on some of the same difficulties that I encountered when developing the TCL. One of the greatest challenges I encountered besides the normal complexities, was keeping the TCL compatible with the major versions of compilers, especially VC6. Many of the decisions I made during the development were due to the limitations from this particular compiler version.
Good luck with your project, and hope to hear back from you.
Yeah! I have ported your TCL to map-like trees. Would you please give your email to me? I can send it as well as examples to you.
Several improvement has been done:
- Remove the support for user-defined Cloner and Destroy.
- No longer store pointers in the node. Instread, store the entities of std::pair<key_type, mapped_type>. A lot of related functions has been modified.
- Remove the function basic_tree<>::insert(value_type* pStored_obj, tree_type* parent). Because now only entities of value_type can be stored in the tree, this function which overrided from basic_tree<>::insert(value_type& pStored_obj, tree_type* parent) is no use. This decision also improves type-safty.
- A helper function has been added.
Add
iterator insert(const value_type& obj);
for
iterator insert(const key_type& oid, const mapped_type& mapped_obj);
This function simplifies the modification in example codes.
Comment:
I have to give you many thanks due to your originally fantastic design. The class layers are very good deployed that only a few codes need modification for the transition from pointer to map-like entity version of TCL. It saves me a lot of time. Great!
Now there will be 2 versions for map-like TCL.
1. tree<key_type, mapped_type...>::insert(key, mapped, parentkey);
2. tree<value_type, key_extractor...>::insert(value_type_node, value_type_parent);
#1 has been implemented. #2 is under construction.
These 2 versions of tree will be used in very different cases.
#1 is for isolated key and mapped object. In another words, mapped_type do not possess the key.
#2 is for compond objects that the key is holded by value_type (ex: CAlpha, cRental). This is the case in original TCL.
Congratulations on getting your implemtation of a mapped tree working. If you'd like, you could email me your work to me via the link on my web page. I'll most likely be keeping my current implementation as it is, as I still feel it's better to have the design or the TCL like it is, with the heap allocation of the stored_type, and because there is already a large user base of the TCL. I'm glad that your implementation is working for your needs, however, and would be happy to check it out in the next couple weeks as I get time.
I have sent a revised TCL to the address < mhaas@datasoftsolutions.net >
Here are comments. This time I will focus on some insight of my design.
- The most important different between original and revised TCL is: the latter one DO NOT support default ctor.
To create a tree, the user should use the form below:
tree<key_type, mapped_type> mytree(key, obj);
instead of
tree<key_type, mapped_type> mytree;
mytree.set(key, obj);
This is reasonable because all trees should have their roots before growing up. ^_^ It is directly avoid key collision for all kinds of trees. Now the tree<>::set can only receive one parament with the type of mapped_type. After the tree is created or a node is inserted, the value of key_type becomes constant. There is no way to change the key unless erase that node. Therefore, now, unique_tree works well and the complexity of unique_tree<>::set function becomes Constant. This function in original TCL is wrong because of unguarded key-value modification.
- Unfortunately, I have to disable Orphan functions in unique_tree because they will use the default ctor of unique_tree which is forbidden in my design. But orphan mechanism is very useful. Maybe we can do some change in the implementation of Orphan funcitons to re-enable it.
- Although there is still a node_compare_type policy in unique_tree, I still want to argue to discard it. I'm worried about the efficiency of iterations along node_compare_type. Take std::map as example, an iterator of map implies an single order of nodes. If other orders of those nodes are needed, the user should build up different std::map with different key_type. It is important that the choice depends on the aim of users. Again, it is not the responsibility of TCL. Actually, I haven't go through find_ordered yet, but I guess if no other std::set holds nodes ordered by node_compare_type, the complexity of find_ordered can not go down to Logarithmic. Anyway, the original design of node_compare_type means there are 2 indexes for one node. If you implement to support this optional searching method on unique_tree, why didn't you implement it on all associate_tree? Why didn't you try to support multiple-index-searching policy? ex: tree<key_type, mapped_type, order1_cmp, order2_cmp, ... orderN_cmp>. In my opinion, we should keep TCL simple, neat, clean and perfect. ^_^
Thank you for your kind help. This afternoon, when I rewrote TCL to bases on std::map container_type, I found a big design defect for the policy of allocators. As comparison, STL containers use allocator policy to manage NODES rather than value_type. But TCL impose an allocator to serve for value_type. I acknowledge that storing pointers in a tree will be spacial efficient if value_type is memory consuming. However, if only simple objects (ex: int, double, std::complex) will be stored, the dynamic allocation process will be redundant and will lead to poor performance for both space and time.
In my opinion, it is not TCL's resposibility to make the decision for storing entities or pointers. If we intrinsically implement TCL to store pointers, there will be no chance for users to store entities. TCL's allocator should serve storage for tree_type (the NODEs of trees), rather than value_type (or stored_type in your words).