Re: [boost] [Boost Review] Property Tree Library

From: Andy Little (andy_at_[hidden])
Date: 2006-04-20 04:18:31

"Sebastian Redl" <sebastian.redl_at_[hidden]> wrote in message
news:444656AB.2010207_at_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