The Tree Container Library
A C++ generic tree container library which, not only works much like the STL, but is also compatible with the STL algorithms. The Tree Container Library is used worldwide in thousands of industries and organizations. It is completely free to use, and is licensed under the zlib/libpng license.
| Date | Version | Description |
|---|---|---|
| Aug 16, 2014 | Version 5.3.1 |
Now properly resolving the use of std::ptrdiff_t, and deallocate_tree_type(), to make compliant with the latest GCC compiler versions. Thanks to Tom Cook for finding, and providing a solution for this issue. |
| Aug 31, 2008 | Version 5.3.0 |
Added two operations to unique_tree, provided by Beth Scaer. reindex_children() and reindex_descendants().Fixed polymorphic copy issue in unique_tree which occured when elements were orphaned. |
| Aug 2, 2008 | Version 5.2.0 | Modified all iterator classes to allow the removal of all self referencing friend declarations, which were causing issues with the GCC compiler for linux. Thanks to John Yao for discovering this issue and working with me to find and implement a suitable fix for the problem. |
| April 2, 2008 | Version 5.1.0 |
Completely redesigned all iterators in the TCL, so they no longer have separate classes for const and non-const varieties. Added base() operation to all descendant iterators, which returns a child iterator pointing to the same element/node.
|
| Mar 12, 2008 | Version 5.0.8 |
Optimize destroying root of unique_tree. Corrected typename placement in child_iterator for gcc compilers. Also, related to this version is a fix to the STL Test Suite in Visual Studio 2008, by Andreas Schniertshauer, who discovered an issue where the test suite was pushing an iterator temporarily out of bounds, which conflicted with Visual Studio 2008's strict bounds checking on iterators. |
| Jan 17, 2008 | Version 5.0.7 | Changed child_iterator and child_node_iterator constructors to accept a const reference param rather than a value param. |
| Jan 1, 2008 | Version 5.0.6 |
Fixed const correctness issues in multiple dereference operations in all iterator classes, as noted by Adrian
Secord. Also per Adrian Secord, all descendant iterators now (correctly) traverse the top (called) node. See Development History for more details. Converted all iterator comparison operators to friend functions, to correctly convert left operands if needed. Linted library and test suite Removed inconsistancies in typedefs in multiple classes, as noted by Andreas Schniertshauer. Changed version schema to major.minor.maintenance. |
| Nov 28, 2007 | Version 4.09 |
Fixed an issue found and resolved by Andreas Schniertshauer, involving std::numeric_limits::max(). When using the TCL with the windows API, a max()
macro is defined which conflicts with the std numeric_limits max() operation. This conflict created warning messages in basic_tree.h when using the
library with the windows api (windows.h). Andreas informed me that the conflict could be resolved by forcing the call operation on the fully
qualified std::max operation, as so (std::numeric_limits<int>::max)(). Since the technique is ansi C++ compatible, the fix works
well with all VC compilers as well as GCC.
|
| July 28, 2007 | Version 4.08 |
With some good advice and code submissions from Adrian Secord, TCL is now enclosed in the 'tcl' namespace. This may be a little annoying for current
users upgrading to this version, but the benifits are worth the little effort. For current users, one or more well placed using namespace tcl;'s
will do the trick. All examples in the downloadable and online documentation have been updated to include the new namespace changes.
|
| Mar 1, 2007 | Version 4.07 | Removed insert range operations for VC6 only, as they were causing ambiguity problems for VC6. |
| Feb 28, 2007 | Version 4.06 | Corrected issue in associative trees which prevented the use of the user defined comparison operator passed as the second template parameter. |
| Feb 20, 2007 | Version 4.05 | Moved declaration of distance_type from sequential_tree to basic_tree, to be shared by all trees. |
| Jan 28, 2007 | Version 4.04 |
Fixed problem with pre_order_iterator decrement operation when decrementing from pre_order_end().
|
| Jan 25, 2007 | Version 4.03 |
Added a const variety parent() operation to basic_tree. Removed range constructors which accept TCL iterators from all trees. The template range constructors will be valid for TCL iterator range use. |
| Jan 23, 2007 | Version 4.02 |
Removed depth() operation from level-order iterators. Created default constructors for reverse_iterator and reverse_node_iterator. Removed public access from child non-default iterators. |
| Jan 15, 2007 | Version 4.01 |
Added overloaded addition/subtraction operations for new node iterators. Removed unneeded line from basic_tree's assignment operation which cleared parent pointer. |
| Jan 11, 2007 | Version 4.00 |
Added the concept of node iterators. There is now a node iterator
for all child, reverse, and descendant iterator type, in addition to the standard previous iterators, which are now known as element iterators. The interface has not changed in any respect. The introduction of the node iterators has left the interface of the normal element iterators unchanged. All node iterator and node iterator interface operations have a 'node' prefix, to keep them seperate from the normal element iterators and iterator access operations. |
| Jan 9, 2007 | Version 3.68 |
Consolidated default constructor and root node constructor for all trees. Consolidated initializing constructors in sequential_tree. Changed all 'element' value references to 'value' |
| Jan 8, 2007 | Version 3.67 |
Fixed typo in unique_tree::find_ordered(). For associative trees, now allowing assignment operation to succeed only on the root node. |
| Jan 6, 2007 | Version 3.66 | Fixed issue with associative_tree::insert(iterator, const stored_type&, tree_type*). |
| Jan 5, 2007 | Version 3.65 | Updated Range constructors for all trees. Range constructors now accept iterators only from the same tree type. |
| Dec 23, 2006 | Version 3.64 |
Fixed problem with range constructors. Fixed problem in == and <, where only immediate children were being checked. |
| Dec 22, 2006 | Version 3.63 |
Modified associative_reverse_iterator to inherit from const_associative_reverse_iterator. Modified sequential_reverse_iterator to inherit from const_sequential_reverse_iterator. |
| Dec 17, 2006 | Version 3.62 |
Modified associative_tree::erase(stored_type&) to work more efficiently, and not to require an overloaded == operator for stored_type. Added and implemented child reverse iterator classes (see reverse_iterator.h). Removed empty files child_iterator.inl and ordered_iterator.inl from the library. |
| Dec 14, 2006 | Version 3.61 | Correctly implemented max_size() in basic_tree. |
| Nov 11, 2006 | Version 3.60 |
Replaced delete it.node(); with deallocate_tree_type(it.node()) in associative_tree and sequential_tree erase() operations.
This didn't seem to cause a problem on 32 bit machines using the standard allocators in basic_tree, but caused a problem on 64 bit machines or when
custom allocators would be used.(Thanks to Glen Davidson for discovering this issue and providing the locations where the fix was needed.) |
| Nov 5, 2006 | Version 3.59 | For all trees, fixed possible issue with == and < operator, which could crash if all descendants were equal for all the rhs descendants, but the rhs tree having less elements than the other. |
| Nov 2, 2006 | Version 3.58 |
In sequential_tree child iterators, changed references of sequential_tree to tree_type. For all trees, fixed possible issue with == operator, which would incorrectly return true if all descendants were equal, but one having more elements than the other. |
| Sept 4, 2006 | Version 3.57 |
Added a (default) parameter to the range constructors, which allow the parent element to be set. Added reverse child iterators for all trees. |
| Aug 21, 2006 | Version 3.56 | Fixed issue with unique_tree's copy constructor and assignment operator with regards to the ordered_iterators. |
| Aug 20, 2006 | Version 3.55 |
No changes in this version involve changes to the interface. Changed all occurances of the name stored_obj to element.Changed name of basic_tree's member, pData to pElement.
|
| Aug 6, 2006 | Version 3.54 |
No changes in this version involve changes to the interface. Removed unneeded typedefs for basic_tree, in the child iterators. Changed name of child iterators, iterator and const_iterator, to associative_iterator and const_associative_iterator. Changed names of descendant iterator classes. Removed base_iterator and const_base_iterator typedefs in unique_tree. Made appropriate const function and variable changes noted by PC Lint 8.0. |
| Aug 2, 2006 | Version 3.53 |
Corrected problem in sequential_tree's insert(pos, it_beg, it_end) operation Added insert(pos, num, stored_type&) operation to sequential_tree. Changed file name Tree.h/Tree.inl to tree.h/tree.inl (Thanks to Jean-Francois Ostiguy for suggesting the addition of the second operation above, informing me of the unix problem with case sensitive filenames, and offering many more useful suggestions for the TCL, which may be implemented soon) |
| Aug 1st 2006 | Version 3.52 | Changed insert(iterator, stored_type&) and insert(iterator, tree_type&) to insert(const_iterator, stored_type&) and insert(const_iterator, tree_type&). |
| July 31 2006 | Version 3.51 | Corrected typo's in sequential_tree's pop_back(), insert(pos, tree_type&), and sort_descendants(). |
| July 27 2006 | Version 3.50 |
iterator and const_iterator classes now derive from std::iterator<std::bidirectional_iterator_tag, stored_type> iterator and const_iterator */-> operations now return a reference/pointer to the node's "open_help_file('/tree_container_library/help/stored_type.htm') ">stored_type, rather than the node's tree_type. All descendant and ordered iterators have undergone the same changes. This change provides more standard compatibility with the STL. Unfortunately, the change also results in a change to all iterators' interface. See the download page for more info. |
| July 20 2006 | Version 3.02 | Added insert(iterator, stored_type&) and insert(iterator, tree_type&) operations to associative trees. |
| July 19 2006 | Version 3.01 |
Consolidated seq_tree insert() and set() ops, added push_back() in sequential_tree. In sequential_tree, added fill constructors, capacity(), reserve(), front(), back(), pop_back(). removed unneeded insert(stored_type*, parent*). In unique_tree, removed insert(stored_type*). Removed insert(stored_type*, parent*) from associative_tree. In sequential_tree, added insert range operation. Added typedef for key_type in associative_tree. In basic_tree, corrected typedefs for value_type, reference, and const_reference. In tree, multitree, and unique_tree, added typedefs for key_compare and value_compare. In basic_tree, added typedef for allocator_type |
| July 17 2006 | Version 3.00 |
Almost full STL compatibility! Fixed problem with pre_order_iterator_end() operation, which had problems iterating backwards from the end. Fixed problem with post_order_constructor. (for post_order_begin(), when node has no children, operation crashed.) Optimized sequential_tree's index operations. (Possible because seq iterator is now a true random access iterator. Now defining all iterators OUTSIDE of basic_tree, which cleans up basic tree immensely. Child iterators defined in a separate file, and associative child iterators are now separate from sequential_tree child iterators. Descendant iterators now defined in a separate file. Ordered iterators (for unique_tree) now defined in a separate file. Iterators are now contained within the trees by using appropriate typedefs in associative_tree and sequential_tree. Associative tree iterators are now derived correctly from std::iterator<bidirectional_iterator_tag, tree_type> sequential_tree iterator is now derived correctly from std::iterator<random_access_iterator_tag, tree_type> pre and post order iterators are now derived correctly from std::iterator<bidirectional_iterator_tag, tree_type> level order iterators now derived correctly from std::iterator<forward_iterator_tag, tree_type> Added required operations for STL compatibility, upper_bound(), lower_bound(), range constructors and insert() operations, etc. |
| May 8 2006 | Version 2.07 |
Fixed bug in assignment operators in all trees, which were not clearing previous child nodes. (Thanks again to Jean-Francois Ostiguy for discovering this issue, and providing examples showing where the problem was occuring.) |
| May 6 2006 | Version 2.06 |
Fixed problem with const descendant iterator end() operations. (Thanks to Jean-Francois Ostiguy for discovering this issue, and providing examples and insight into the solution) |
| May 1 2006 | Version 2.05 |
Made a number of changes, most of which don't affect the functionality or interface, noted below. Also, added subscript operations to sequential_tree, as suggested by Martin Wirth. Changed all iterator classes to correctly derive from std::iterator<std::bidirectional_iterator_tag, tree_type*>. Some of the smaller changes, which don't affect functionality are... Made constructors in all classes explicit where possible. Properly resolved all references in derived classes to base class members. Removed all unneeded #include "xxx.h" directives in the inl files. Removed unneeded basic_tree_type typedef in basic_tree. Changed post_order_iterator operator --() to return a reference. Initializing needed members in basic_tree's initializer list. Added check for self assignment in basic_tree's assignment operator. Made local variables const where possible. (Thanks to Martin Wirth for his suggestions for changes to sequential_tree) |
| Mar 28 2006 | Version 2.04 | After considering other license agreements, I decided to vastly simplify the license agreement used in the TCL. The new agreement is based on the zlib license agreement, and is simple, clear, and very less restricting. |
| Mar 26 2006 | Version 2.03 |
Added an exception to the GNU LGPL, which allows users to use the TCL, unmodified, in closed applications by including the files in their project, or
linking statically to the TCL in a static library. (Thanks to Guglielmo Scotilanza for pointing out the inconsistency in using the unmodified LGPL as the open source license) |
| Mar 23 2006 | Version 2.02 |
Created custom allocation/deallocation operations in basic_tree, which use two new member allocators to allocate and deallocate stored_type and
tree_type objects. Change all allocation/deallocation operations in basic_tree and derived trees to use these functions. Added erase(iterator) operation for all trees. (Thanks to Bjorn Madsen for proposing the concept of custom allocators and supplying the initial allocator code and design.) |
| Mar 20 2006 | Version 2.01 |
In basic_tree, simplified operator * and operator -> operations for iterator and const iterator to make them VC6 compatible with sequential_tree. VC6 compatibility changes and changed signature of sort functions() accepting function object in sequential_tree. |
| Mar 16, 2006 | Version 2.00 |
TCL 2.0 is now available. The new version includes the latest container member, sequential_tree<>. This container class uses a std::vector to store the child nodes, rather than std::set. Thus, child nodes remain in the order in which they are added (or inserted). Multiple operations are provided to sort the child nodes if desired. The following changes were also made to the TCL. Changed all occurences of template parameter name 'set_container_type' to 'container_type'. Changed "using const_iterator::it;" to protected in iterator class. Moved find() and erase() operations from basic_tree to associative_tree. Changed basic_tree::children access from private to protected. Change tree, multitree, and unique_tree to inherit from associative_tree rather than from basic_tree. Change constructor taking stored_type parameter to explicit in tree, multitree, and unique_tree. Add delegation operation set(stored_type&) to tree, multitree, and unique_tree. |
| Feb 16, 2006 | Version 1.20 |
The TCL is now Visual Studio 2005 (VC8) compliant! Change access of basic_tree's non-default iterator constructors to protected. Removed unneeded friend declarations in descendant iterators. Removed clear() from tree, multitree. Changed access of basic_tree::clear() from protected to public. Change operator==() in unique_tree to use operator <(). Remove member function object for unique_tree deref comparison, and replace it with a typedef to the external deref comparison. Change secondary constructor in unique_tree to initialize allow_orphans to false. Removed unneeded overloaded operators == and != from non-const iterator classes. Pass parent pointer to iterator/const_iterator constructors for iterator comparisons. Resolve problem with polluted namespace in descendant iterator classes. Thanks to Volker Bijewitz for discovering TCL issues in the VC8 (Studio 2005) compiler. |
| Feb 5, 2006 | Version 1.19 |
In basic_tree, changed access type to protected for all constructors and destructor. Commented all code. |
| Jan 27, 2006 | Version 1.18 |
In basic_tree, set the parent node to 0 in the copy constructor and assignment operator, which fixes the problem with newly created subtree's
containing a dangling parent. In basic_tree, changed for_each(function ptr) and for_each(function obj) to accept function and function object signatures which accept a reference to the stored_type, rather that a tree_type pointer. This is more consistent with the STL. Also, for_each() will now perform the operation on the calling node, as well as it's descendants. (Thanks to Quynh Nguyen for discovering these issues) |
| Jan 26, 2006 | Version 1.17 |
In unique_tree, added a non const version of find_ordered() for const correctness. Corrected basic_tree::clear() operation to use correct iterator type retrieval. In basic_tree, added const stored_type* get() const operation for const correctness. In basic_tree, made iterator and const_iterator constructors explicit. In basic_tree, corrected problems in descendant iterator incr/decr operations, due to implicit construction of iterators. |
| Jan 23, 2006 | Version 1.16 |
VC6 compliant changes. Corrected problem with descendant iterator *() operations. (Thanks to Quynh Nguyen for discovering this problem and providing a fix) |
| Jan 23, 2006 | Version 1.15 |
One line fix in basic_tree for VC 6 compatibility. |
| Jan 21, 2006 | Version 1.14 |
Added protected set_parent() operation to basic_tree to make library VC 6 compatible. |
| Jan 19, 2006 | Version 1.13 |
Changed open source license agreement to GNU Lesser General Public License. |
| Jan 19, 2006 | Version 1.12 |
Replaced NULL's with the more standard 0's. Removed unnecessary friend declarations in basic_tree and it's iterators. Inlined descendant iterator implementation, and for_each() operation. TCL now Visual Studio 6 compatible! |
| Jan 18, 2006 | Version 1.11 |
Changed license agreement and disclosure statement. License agreement now based on BSD open source license agreement. |
| Jan 18, 2006 | Version 1.10 |
Removed erase(key) operation from unique_tree. Moved appropriate destructor activities from derived class destructors to basic_tree destructor. Moved copy constructor and assignment operator details in derived classes to basic_tree. Changed all data member access in basic_tree to private access. |
| Jan 16, 2006 | Version 1.09 |
Added assignment operators for all three tree containers |
| Jan 11, 2006 | Version 1.08 |
In unique_tree, corrected insert(parent, child) to return end iterator if parent can't be found. In unique_tree, added is_orphan() operation. |
| Jan 10, 2006 | Version 1.07 |
In unique_tree, added check if stored type is in the root, in check_for_duplicate() In unique_tree, changed const_ordered_begin() and const_ordered_end() to ordered_begin() and ordered_end() In unique_tree, correctly returning end() to proper parent node in insert(parent, child) |
| Jan 5, 2006 | Version 1.06 |
Removed (gcc) compiler errors from descendant and ordered iterators. |
| Jan 3, 2006 | Version 1.05 |
The TCL generic example is now gcc compliant! Complete library to become gcc compliant soon. Added typedefs in unique_tree to qualify base class iterators. Removed all convenience operations from unique_tree and all iterators. Changed interface to iterators: Iterators now return ref/ptr to node rather than stored_type. (Thanks to John Potter for these and other suggestions) (Thanks to Santhosh Shetty for getting me up to speed with gcc and cygwin) |
| Dec 30, 2005 | Version 1.04 |
Qualified references to base class members in derived classes. Removed insert(stored_type*) operations from tree/multitree Changed insert(stored_type*) operation access to private in unique_tree. (Thanks to Roland Pibinger for these and other suggestions, including 1.05 changes) |
| Dec 27, 2005 | Version 1.03 |
Corrected basic_tree template parameter to use multiset rather than set. Corrected return iterator to return end() for unsuccessful insert() operations. Removed set (const char*) operations. |
| Dec 26, 2005 | Version 1.02 |
Added depth() operation to level_order_iteratorChanged access of implementation constructor of descendant iterators to protected. |
| Dec 23, 2005 | Version 1.01 |
Fixed const-ness issues with child & descendant iterator operations. Insured iterator/const_iterator operations are const-correct. |
| Dec 21, 2005 | Version 1.0 |
Removed memory leaks. Added const descendant iterators. Moved descendant iterator implementation to composed classes. Changed clone function signature to accept const reference. |
| Dec 15, 2005 | Version 0.99 |
Added allow_orphan() operations to unique_tree. Fixed orphan behavior on inserts, in unique_tree |
| Dec 8, 2005 | Version 0.98 |
Derived const_iterator, & hence all other iterators, from std::iterator<std::bidirectional_iterator_tag, stored_type> (Thanks
to Stephen Howe for this and other suggestions).Implemented decrement operators for pre_order_iterator and post_order_iterator. Disallow duplicate nodes in unique_tree
|
| Dec 4, 2005 | Version 0.97 |
Tree Container Library (TCL) is available for download. |
| Aug 22, 2005 | Version 0.0 | Design and construction of TCL started. |