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.
unique_tree<> offers the same common interface
multitree<> containers, plus additional operations, which are available because each
node in the tree is guaranteed to be unique. Because of this, any node can be found from the root. In the
multitree<> containers, it's only possible to find children nodes from their immediate parent.
One of the most useful additions to the
unique_tree>< interface, is the
find_deep() operation. This and other
operations unique (no pun intended) to the
unique_tree<> are described below. In the definitions, stored_type
is used to refer to the type of element
being stored in the tree container. Similarly, the term derived_type is used to refer to an object of a class derived from
documentation below applies to TCL versions 3.50 and higher. The latest version of the TCL can be downloaded from the TCL download page.
iterator insert(const stored_type& parent_obj, const stored_type& element)
Inserts a child node containing the element in the parent node specified by the parent_obj. This is a polymorphic operation, so
elementcan be of any type derived from
stored_type, and it will keep its type identity while stored in the container, provided a
cloneoperation is provided. An iterator is returned pointing to the inserted node. This insert operation, and the one immediately below, differ from the standard insert operations with take one argument. This insert operation need not fail even when the parent is not found. In this case, if orphans are allowed (see below) the
unique_treecreates the parent/child pair within an internal temporary storage (orphans). The parent, and associated children and descendants remain in the orphan storage until a matching node for the parent is inserted which has a valid parent. When this occurs, the element of the new matching node replaces the element of the node in orphan storage, and it (along with any of it's descendants)
are removed from the temporary storage, and placed in its appropriate position in the tree container structure. The reason for this behavior is when inserting nodes using these parent/child insert operations from data in a database or sequential container, it's not always guaranteed that its parent or it's ancestors have already been inserted.
iterator find_deep(const stored_type& element)
Searches descendant nodes for the
stored_typeobject. Returns an iterator pointing to the found node, or the
end nodeif unsuccessful. The difference between this operation and the
find()operation, is that the
find()operation only searches the children nodes, while
find_deep()searches the descendant nodes. Since multitree can have multiple occurences in a single parent, the iterator will return a pointer to the first found occurrence, or the end iterator if not found. Remember that when searching nodes, the
node_compare_typewill determine the equality of the node that's being sought.
const_iterator find_deep(const stored_type& element) const
Identical to the operation above, but returns a
const_iteratorrather than an
ordered_iterator find_ordered(const stored_type& element)
Searches child nodes using the alternate ordering operation. Returns an
ordered_iteratorto the found child, or
ordered_end()if not found.
const_ordered_iterator find_ordered(const stored_type& element) const
Searches child nodes using the alternate ordering operation. Returns a
const_ordered_iteratorto the found child, or
const_ordered_end()if not found.
Returns an ordered iterator pointing to the first child in the node, if present. The ordered iterator gives an alternate way in which child nodes are traversed. It traverses the children in an order which uses the third template parameter to the unique_tree, the node_order_compare_type. Use of the ordered_iterator can be handy if you wish to traverse the child nodes in an order different than offered by the standard iterator, which uses the
node_compare_typefor it's comparisons.
Returns an end ordered_iterator. This iterator points just beyond the last ordered child node in the parent. When traversing a parent's children with an ordered_iterator, you would need to test it against
ordered_end()to determine when all child nodes have been traversed.
const_ordered_iterator ordered_begin() const
const_ordered_iteratorpointing to the first child in the node, if present. Otherwise, returns
const_ordered_iterator ordered_end() const
Returns an end
void allow_orphans(bool bAllow)
Allows orphans in the container. Allowing orphans is necessary if you are using the
insert(parent, child)operation, and are unable to insure that all parents will be inserted before their associated children or descendants. If orphans are not allowed, any insertion using the operation
insert(parent, child)will fail, if the parent can not be found in the tree.
Indicates if orphans are currently allowed in the container.
Indicates if the current node is an orphan.