Tree container library
in [C++]
|
Prev: generate double persision random value
Next: C++ template base class' nested typedefs not visible in derived template class
From: Mitchel Haas on 16 Dec 2005 11:54 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! ]
From: Roland Pibinger on 29 Dec 2005 07:11 On 16 Dec 2005 11:54:24 -0500, "Mitchel Haas" <mjh(a)datasoftsolutions.net> 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' (http://womble.decadentplace.org.uk/c++/template-faq.html). 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! ]
From: Mitchel Haas on 29 Dec 2005 19:49 "Roland Pibinger" <rpbg123(a)yahoo.com> wrote in message news:43b30c28.5715612(a)news.utanet.at... > On 16 Dec 2005 11:54:24 -0500, "Mitchel Haas" > <mjh(a)datasoftsolutions.net> 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' > (http://womble.decadentplace.org.uk/c++/template-faq.html). 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! ]
From: John Potter on 1 Jan 2006 06:28 On 29 Dec 2005 19:49:38 -0500, "Mitchel Haas" <mjh(a)datasoftsolutions.net> 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. 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! ]
From: Mitchel Haas on 4 Jan 2006 08:35
"John Potter" <jpotter(a)lhup.edu> wrote in message news:UpAtf.375$ZA2.357(a)newsread1.news.atl.earthlink.net... > On 29 Dec 2005 19:49:38 -0500, "Mitchel Haas" > <mjh(a)datasoftsolutions.net> 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 > 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! ] |