The Tree Container Library

The unique_tree<> offers the same common interface as the tree<> and 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 tree<> and 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 stored_type. The documentation below applies to TCL versions 3.50 and higher. The latest version of the TCL can be downloaded from the TCL download page.

Inserting nodes

• 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 element can be of any type derived from stored_type, and it will keep its type identity while stored in the container, provided a clone operation 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_tree creates 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.
  Complexity: Logarithmic

Searching nodes

• iterator find_deep(const stored_type& element)
  Searches descendant nodes for the stored_type object. Returns an iterator pointing to the found node, or the end node if 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_type will determine the equality of the node that's being sought.
  Complexity: Logarithmic
• const_iterator find_deep(const stored_type& element) const
  Identical to the operation above, but returns a const_iterator rather than an iterator
  Complexity: Logarithmic
• ordered_iterator find_ordered(const stored_type& element)
  Searches child nodes using the alternate ordering operation. Returns an ordered_iterator to the found child, or ordered_end() if not found.
  Complexity: Logarithmic
• const_ordered_iterator find_ordered(const stored_type& element) const
  Searches child nodes using the alternate ordering operation. Returns a const_ordered_iterator to the found child, or const_ordered_end() if not found.
  Complexity: Logarithmic

Iterator retrieval

• ordered_iterator ordered_begin()
  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_type for it's comparisons.
  Complexity: Constant
• ordered_iterator ordered_end()
  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.
  Complexity: Constant
• const_ordered_iterator ordered_begin() const
  Returns a const_ordered_iterator pointing to the first child in the node, if present. Otherwise, returns const_ordered_end().
  Complexity: Constant
• const_ordered_iterator ordered_end() const
  Returns an end const_ordered_iterator.
  Complexity: Constant

Miscellaneous operations

• 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.
  Complexity: Constant
• bool allow_orphans()
  Indicates if orphans are currently allowed in the container.
  Complexity: Constant
• bool is_orphan()
  Indicates if the current node is an orphan.
  Complexity: Constant