Exposing partial order of Tree
Brought to you by:
mitcheljh
Menu
▾
▴
I appreciate your TCL. It is very useful in real world applications. It should be pointed out that, a tree (except seq_tree) implies an partial order just like your design of node_compare_type policy. But, currently, this partial order is hidden in the internal of tree rather than exposed in public interface. For explicitly, here may be 2 patterns available: (Take unique_tree as example)
1. std::map-like interface:
unique_tree<>::insert(key_type parentid, key_type id, stored_type obj), Here stored_type is mapped_type.
original: unique_tree<>::insert(stored_type parent, stored_type obj).
2. functor-based interface:
unique_tree <key_type, stored_type, GetKeyFunctor>::insert(key_type parentid, stored_type obj)
{
// Call pattern #1
unique_tree<>::insert(parentid, GetKeyFunctor(obj), obj);
}
key_type GetKeyFunctor(stored_type obj)
{
return obj.GetKey();
}
Summary: Original tree interface binds key_type and store_type too tightly, because key_type is enough. When searching in the tree or pointing out the parent node, possibly, we do not have the entire store_type but only a key_type. Decoupling the key_type and stored_type may improve TCL usage.
Helllo, and thangs again for your nice comments and suggestions. There would certainly be advantages to having the tree's modeled more in more of a 'key' fashion, but I decided against that when designing the tree, as it would make the tree more complicated to use. There are, however, a couple of ways the node order can be customized by the user. One, is by defining the < operator for the stored_type. Another method is to provide a second 'node_compare_type' template parameter. This would be similar to providing a comparison type to std::set, which determines the order of the objects in the set.
It's true that the entire node object might not be known to perform a search for one of the nodes. However, just as when searching for an object in the std::set, only the object members which determine the order of the set need be populated in the object to perform a search. So, if you provide a constructor to your stored_type which accepts only the parameter(s) necessary to set the 'key' members of the object, searching for a node is as easy as...
my_tree.find(CEmployee(2354));
Again, your suggestion about using a map for internal storage and modeling the trees as 'keyed' type containers is very understandable, and something I gave a lot of consideration to while developing the TCL. In the end, simplicity and ease of use were the deciding factor.
Thank you for your smart and detailed reply. My opinion coincides with you that I know you will answer like above.
Let me give you a stronger argument. :P
std::map which decouples key_type and mapped_type has a big advantage for node modification. You can only change the value of mapped_type rather than key_type due to the intrinsic order of std::map. Therefore, through iterator, the complexity of modifying mapped_type is Const, while the complexity of modifying key_type is Logarithmic due to the extra inserting operation.
In your TCL, tree::set should provide similar functions. If it is in the form of tree::set(stored_type), again, through iterator, the complexity of modifying stored_type will become Logarithmic due to the correlation of key_type and mapped_type. Anyway, you can change the function to tree::set that it only can set the node pointed by iterator and the input key_type should be exactly same with that of current node, otherwise throw a exception. ^_^
Moreover, there is a serious problem in tree, especially in unique_tree. The unique_tree::set function gives the ability for changing key_type freely, but without key_type collision check. Consequently, I can easily build a unique_tree with un-unique nodes. :P
unique_tree<cRental> rental_tree;
rental_tree.set(cRental(0, "My Properties"));
rental_tree.insert( cRental(0), cProperty(100, "Riverside Property", 35.5, 1000.00));
rental_tree.set(cRental(100)); // !! key_type collision. Now we have 2 nodes with id=100.