"Sebastian Redl" <sebastian.redl@getdesigned.at> wrote in message news:444656AB.2010207@getdesigned.at...
Andy Little wrote:
Why are all ptree nodes the same type? Commonly a tree will have branch and leaf nodes. In the debug example there are two branch nodes and 4 leaf nodes, which means two empty lists . That is wasteful isnt it?
How do you distinguish, though?
The obvious way is to make a node an abstract base class with interface functions such as (say) is_leaf(), is_branch(). Alternatively provide the abstract base class as a private member of node and manage it privately, changing it from a branch to a leaf as required. user defined leaves hold numeric, coordinate , string, arrays ... whatever efficiently. The interface would probably need an extensible mechanism so that a leaf could be interrogated to find out what type of data it holds. The obvious one is an integer type id per type What happens when you add a node as a
child of what formerly was a leaf node?
You would have to change the leaf to a branch. This could be automatic if the actual type of the node was encapsulated as described above. OTOH if you tried to add a child to a leaf it would clearly be an error. How can you change the type of
the node when some places (including, most likely, the caller) are holding a reference?
In the tree I describe you would copy data or interrogate nodes rather than hold references to nodes. In that case dont hold references. (If a reference is essential you may need to lock or refcount/release the branch to prevent modification). In general use the keys to access mutable data. Thats what they are for. If a caller provides a node reference in a function call expecting the node to be filled, then one would change the type of the argument from a node to a branch as only branches can have nodes added so inputting a node argument makes no sense anyway.
How would you define value_type?
This would be the exclusive concern of leaf nodes. Would you make the tree node
polymorphic?
Yes. Isn't that even more wasteful? (Not to mention cumbersome.)
An empty list is just two pointers, and perhaps a count.
Without trying out an alternative design I dont know if it would be more wasteful. If the hierarchy is flat then polymorphism can be cheap AFAIK. The major use I thought of is a scene graph. This typically consists of a large number of nodes ( Can be many Mb file) many containing structures of points and transforms. I suspect its cheaper to keep these in memory in their binary format rather than as strings. Whatever... it would be interesting to see the rationale behind the design decisions made within the documentation. I *think* that a trade off has been made in favour of convenience and 'light weight' (I think it would not perform well on large files for example) against compactness and performance. That is fine if its explicitly stated as the aim.
Is it necessary to make key a string. Could it not also be (say) an integer id?
It's certainly possible in theory, and the key_type typedef in the traits should make it possible in practice too. From looking at the implementation, it appears, however, that the key type must provide the std::string interface. This makes sense, in a way, as the keys can be concatenated to directly access deep properties. The question is whether making this more flexible, either by having the traits supply a conversion from string to key and do the lookup by tokenizing and converting each token, or by having the traits supply a type-specific concatenation operation, is worth the trouble. Using any key type but string makes most of the readers and writers useless: the existence of any XML where all element and attribute names are numbers is doubtful (and perhaps even forbidden, I'd have to check the specs). In addition, such an interface makes the implementation and the traits that much more complicated.
Maybe the tree with the string key type is a refinement of a more generic property tree? regards Andy Little