Subject: Re: [boost] hierarchy_tree container
From: Morgan Freeberg (mkfreeberg_at_[hidden])
Date: 2012-11-10 07:27:37
Okay thanks Jose, that helps. My search through the libraries did not pick up on these. By the time I did that I already had the application behavior I wanted, so on my end this has been a refactoring process; I can take a look at these and see if I did that the right way, or if perhaps these could've provided the functionality I need.
>From skimming over the documentation, my initial impression is that they're both very cool implementations which might help me in future work, but some of what I did here is falling somewhat outside of that is provided by these. If you're still interested, I can provide an approximation of the challenges met here:
1. From a rather large not-quite-completely-standard XML file, I needed to parse from top to bottom, understanding the structure being created as containers are declared, sub-containers & leafs are added in, and each construct is eventually terminated. The process that does this would need to store not only the instantiation of the tree container, but a vector/array of references to the ancestors of some "current node" being built. That is so that, as it encounters terminating tags, the internal logic can say...this is ended, now this is ended, now this is ended...essentially so that it can "outdent" again. I can see with treetree and st_tree this is do-able if I write some level of intermediate code that builds such an array and maintains it, as I know lots of "standard" XML readers already do. (This I know from my attempts to find one I could actually use in my project.) The issue that would arise here is, I'd still need to write and test that code, and the result would in turn be redundant with what I did here...so it seems these two libraries recognize the same structure mine does, but the scope of purpose is a little bit different. My container internalizes all this parentage information so that when you're reading data sequentially in this way, the client code only needs to track the depth by way of counting the opening and closing tags, then make a call to the container that essentially says "add this, at this depth." Implication being: As a child of whatever. The container internally tracks the concept of "we are currently defining children of so-and-so."
2. In a configuration file of my own making, I needed to pre-declare what the tree should look like. This is not XML, it's a list of statements that say "that class we already defined on line 3, here on line 9 we are defining a class that is a child of that." The method described above that is good for reading these pseudo-XML files, it would not work for that. What is needed here is either a sequential or random-access search by name...In this case you need to write code on top of my container, as well as on top of treetree and s_tree. So in this requirement, all three provide the same functionality.
3. I chose an enumerator/callback interface that works by way of numeric return codes, because I needed it for a variety of commands to be executed on the trees -- some do searches, some validate, some filter (search without terminate after find), et al. The point to dynamically constructing a tree was to be able to do integrity checks on it, and then execute some different application behavior on each node within what I could be sure was the same tree as what I had seen before. So for my particular implementation this is a big benefit, because I can use a chain-of-responsibility design pattern to associate each command with a name, an invoker, some help text, and then a callback routine that defines the behavior. Again, it seems those other two containers can meet the requirement, after intermediate code has been written to adapt them to this application-specific purpose, which in turn has been internalized in my container.
Much shorter version: Enum/callback pair for listing the contents of the tree, with numeric return codes; two distinctly separate methods for getting the data in at run-time, one method for reading a streaming mechanism such as XML, the other method for specifically identifying the parent of a new node -- "child of that guy, you made before, over there." The test program I provided mixes those two methods up, so that it is demonstrated they can both work on the same container once it is instantiated.
I'll run some tests with these and, if you're interested, provide you with a more fully-informed report on where there may & may not be full redundancy.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk