 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Mitchel Haas
Guest
|
 Posted: Fri Dec 16, 2005 4:54 pm Post subject: Tree container library |
 |
|
Hello,
Feeling a need for a generic tree container to supplement the available
containers in the STL,
I've created a generic tree container library (TCL). The library usage is
very much like the containers in the STL, including iterator usage.
Info on the library can be found here..
http://www.visuallandlord.com/developers_corner/open_source/tree_container_library/overview.php
The library can be downloaded from this site also.
The TCL is open source, and has been thoroughly tested,
but still needs a workout to reveal possible remaining bugs.
The library is certainly no matching quality to that of the STL or BOOST.
It's purpose is to simply to provide a dependable tree type container
storage.
The library offers three flavors of tree containers:
tree<> : every child within a given parent must be unique
multitree<>: duplicates can exist within a given parent
unique_tree<>: no duplicates can exist within the entire tree structure.
All nodes in the tree must be unique. The unique_tree offers
a handy insert operation of the form insert(parent, child).
In the unique_tree, orphans may be enabled or disabled.
Enabling orphans allows the insertion of nodes in an order
where the parent isn't guarenteed to be present before one
of it's children are inserted.
All three tree classes are derived from a base class, basic_tree<>.
Standard node iterators are provided for iterating children within a parent.
Special "descendent" iterators are avalilable to traverse children and
descendents of nodes:
pre_order_iterator, post_order_iterator, and level_order_iterator.
I'd welcome any feedback, questions, comments, or suggestions regarding the
library.
Thanks,
Mitch Haas
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Roland Pibinger
Guest
|
| Posted: Thu Dec 29, 2005 12:11 pm Post subject: Re: Tree container library |
|
|
On 16 Dec 2005 11:54:24 -0500, "Mitchel Haas"
<mjh (AT) datasoftsolutions (DOT) net> wrote:
The TCL library has many interesting aspects, especially the
'traversal iterators' and could be handy and useful in many
situations. Some remarks on design and implementation:
Design:
The current 'standard interface' has ambiguous semantics (esp. the
insert functions). It's not clear if a transfer of ownership takes
place and if a 'clone' function is used. (I know, Boost also has some
libraries with 'clone' functions but they really only obfuscate
things.) STL strictly obeys to the dogma of 'value semantics'. TCL
rather uses 'reference semantics'. The user should not be left unclear
about the overall design philosophy. If you lean towards 'value
semantics' you could use splice and merge functions similar to
std::list to split and combine trees.
Implementation:
You need to become acquainted with a template (mis-)feature called
'two-phase name lookup'
([url]http://womble.decadentplace.org.uk/c++/template-faq.html)[/url]. I had to
change dozens of lines of code to compile just "tree<CMyClass>
my_tree;" with gcc 3.4 (mostly just add a 'this->' everywhere an error
occurs). Also, the code in the CMyClass ... example is not correct.
Best wishes,
Roland Pibinger
P.S. The library would be more usable if you included unit tests.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Mitchel Haas
Guest
|
| Posted: Fri Dec 30, 2005 12:49 am Post subject: Re: Tree container library |
|
|
"Roland Pibinger" <rpbg123 (AT) yahoo (DOT) com> wrote
| Quote: | On 16 Dec 2005 11:54:24 -0500, "Mitchel Haas"
[email]mjh (AT) datasoftsolutions (DOT) net[/email]> wrote:
Feeling a need for a generic tree container to supplement the available
containers in the STL,
I've created a generic tree container library (TCL). The library usage is
very much like the containers in the STL, including iterator usage.
Info on the library can be found here..
http://www.visuallandlord.com/developers_corner/open_source/tree_container_library/overview.php
[...]
I'd welcome any feedback, questions, comments, or suggestions regarding
the
library.
The TCL library has many interesting aspects, especially the
'traversal iterators' and could be handy and useful in many
situations. Some remarks on design and implementation:
Design:
The current 'standard interface' has ambiguous semantics (esp. the
insert functions). It's not clear if a transfer of ownership takes
place and if a 'clone' function is used. (I know, Boost also has some
libraries with 'clone' functions but they really only obfuscate
things.) STL strictly obeys to the dogma of 'value semantics'. TCL
rather uses 'reference semantics'. The user should not be left unclear
about the overall design philosophy. If you lean towards 'value
semantics' you could use splice and merge functions similar to
std::list to split and combine trees.
Implementation:
You need to become acquainted with a template (mis-)feature called
'two-phase name lookup'
([url]http://womble.decadentplace.org.uk/c++/template-faq.html)[/url]. I had to
change dozens of lines of code to compile just "tree<CMyClass
my_tree;" with gcc 3.4 (mostly just add a 'this->' everywhere an error
occurs). Also, the code in the CMyClass ... example is not correct.
Best wishes,
Roland Pibinger
P.S. The library would be more usable if you included unit tests.
|
Thanks for the input, Roland.
I'll take a closer look at your notes on the design.
I'm giving some thought about removing the insert(stored_type*) operations,
which would help a little with the semantics.
I'd like to keep the polymorphic behavior of the stored_type in the library
if possible,
which necessitates the clone operations, but will spend a little time to see
if there's a way to change the interface and keep the polymorphic behavior.
I appreciate the info and link on the 'two-phase name lookup'.
I've been having a tough time getting the library to compile
on VC 6.0, also. Reviewing "C++ Templates" will also be helpful,
as the text seems to mention some info on this behavior also.
VC 6.0 also seems to dislike member templates of template classes
defined in the inl files, which should also be resolved in the next
release of TCL.
I recently added a generic example to the site, which should replace
the example code that you found to be faulty.
I appreciate you taking the time to do some testing on the library yourself,
with the gcc. I'll be sure to make the next version more
compatible.
Thanks again,
Mitch Haas
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Sun Jan 01, 2006 11:28 am Post subject: Re: Tree container library |
|
|
On 29 Dec 2005 19:49:38 -0500, "Mitchel Haas"
<mjh (AT) datasoftsolutions (DOT) net> wrote:
| Quote: | I appreciate the info and link on the 'two-phase name lookup'.
I've been having a tough time getting the library to compile
on VC 6.0, also.
|
If that is the only compiler that you have, your project is doomed. It
also needs to compile on a current mostly compliant compiler.
| Quote: | I recently added a generic example to the site, which should replace
the example code that you found to be faulty.
|
The faulty code is still present. The generic example generates 138
errors with gcc-3.4 The more interesting template errors don't come
until those are fixed.
Here is some simple code to show you the majority of the errors.
template <class T>
struct S {
int i;
struct S2S {
};
};
template <class T>
struct S2 : S<T> { // The bad code
void f () {
i = 5; // not visible
}
typedef S<T> SofT;
friend class SofT; // invalid use of typedef
S2S s; // not visible
};
template <class T>
struct S3 : S<T> { // A simple fix
using S<T>::i; // bring in the member
typedef typename S<T>::S2S S2S; // bring in the type
void f () {
i = 5;
}
friend class S<T>;
S2S s;
};
errs.cpp:13: error: using typedef-name `S2<T>::SofT' after `class'
errs.cpp:14: error: `S2S' does not name a type
errs.cpp:14: error: (perhaps `typename S<T>::S2S' was intended)
errs.cpp: In member function `void S2<T>::f()':
errs.cpp:10: error: `i' undeclared (first use this function)
You may be noticing that inheritance with templates does not get you as
much as you think. You will need a using for each data member and each
function member which is not overridden and a typedef for each nested
type. Roland mentioned the alternative of using this-> with each data
or function member. One using may be easier than many this->.
Opinion: The "convience" members of the iterators produce a fat
interface that is of little use. Like functions, classes which do one
thing well are much more useful and easier to maintain.
Note: set<>::iterator and set<>::const_iterator may be the same type.
You have constructors overloaded on those types. Remove the one that
takes an iterator since set<>::iterator is convertable to
set<>::const_iterator.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Mitchel Haas
Guest
|
| Posted: Wed Jan 04, 2006 1:35 pm Post subject: Re: Tree container library |
|
|
"John Potter" <jpotter (AT) lhup (DOT) edu> wrote
| Quote: | On 29 Dec 2005 19:49:38 -0500, "Mitchel Haas"
[email]mjh (AT) datasoftsolutions (DOT) net[/email]> wrote:
I appreciate the info and link on the 'two-phase name lookup'.
I've been having a tough time getting the library to compile
on VC 6.0, also.
If that is the only compiler that you have, your project is doomed. It
also needs to compile on a current mostly compliant compiler.
I recently added a generic example to the site, which should replace
the example code that you found to be faulty.
The faulty code is still present. The generic example generates 138
errors with gcc-3.4 The more interesting template errors don't come
until those are fixed.
You may be noticing that inheritance with templates does not get you as
much as you think. You will need a using for each data member and each
function member which is not overridden and a typedef for each nested
type. Roland mentioned the alternative of using this-> with each data
or function member. One using may be easier than many this->.
Opinion: The "convience" members of the iterators produce a fat
interface that is of little use. Like functions, classes which do one
thing well are much more useful and easier to maintain.
Note: set<>::iterator and set<>::const_iterator may be the same type.
Remove the one that takes an iterator since set<>::iterator is convertable |
to
| Quote: | set<>::const_iterator.
John
|
Thanks for the additional suggestions. I've never used gcc before now, but
have just
set up cygwin/gcc, and have the TCL gcc compliant now. I see what you mean
by the term 'compliant compiler'! I had no idea VC was so lax.
I've also removed the convienience operations from the iterator and
unique_tree,
agreeing with your opinion about the bloat. I made a drastic change in the
iterators
interface, having the iterators return refs/ptrs to the underlying nodes
with * and ->,
rather than to the stored_type.
I was still having problems with the using's, so used a couple handy
typedefs in unique_tree to qualify the base iterator classes.
Version 1.05 of the TCL is available now for download, and have most of the
web pages
updated accordingly. Thanks again for your suggestions.
Mitch Haas
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
