The Tree Container Library

Since the TCL containers are STL compatible, you can insert elements from STL containers into TCL containers, and vice-versa. All tree containers in the TCL have two operations which allow the insertion of elements from TCL containers. The first of these operations is a TCL container constructor, which accepts an input iterator range. This iterator range can be a range from an STL container of another TCL container. The constructor signature is shown below for all the tree containers.

• template<typename iterator_type> tree(iterator_type it_beg, iterator_type it_end)
• template<typename iterator_type> multitree(iterator_type it_beg, iterator_type it_end)
• template<typename iterator_type> unique_tree(iterator_type it_beg, iterator_type it_end)
• template<typename iterator_type> sequential_tree(iterator_type it_beg, iterator_type it_end)

These constructors allow the insertion of elements within the specified range from another container, on the tree container's creation. This is a required constructor for both associative containers and sequential containers.

The second TCL container operation which allows the insertion of elements from STL containers, is a particular insert() operation which is also available for all TCL tree containers. This operation is shown below. The signature is the same for all four tree containers.

• template<typename iterator_type> void insert(iterator_type it_beg, iterator_type it_end) (for associative trees)
• template<typename iterator_type> void insert(const_iterator pos, iterator_type it_beg, iterator_type it_end) (for sequential_tree)

This insert operation can be used on the root node of a tree container, or on any node in the tree. The iterator range can be from as STL container, or another TCL container.

Using the TCL iterators, elements from TCL tree containers can also be used to create and insert elements into STL containers. Both STL sequence and associative containers contain constructors and insert operations accepting an iterator range. This iterator range can be specified with either TCL child iterators or TCL descendant iterators.

The following examples illustrate the above concepts. The functions populate_tree() and populate_container() are operations which populate tree containers and STL containers. The details of these populate operations are unimportant, but are present only to show that the source containers have elements.

Using the TCL container range constructors

The range constructors (see list above) allow users to create a new tree node while populating the node with elements from an STL container or another TCL container. The example code below shows this concept.

// create a sequential_tree node with elements from a vector
std::vector<Employee> emplVec;

populate_container(emplVec); // populate the employee vector




// create a sequential_tree container node of the same type, and initialize it with elements from the vector
sequential_tree<Employee> emplTree(emplVec.begin(), emplVec.end());

The same concept can be applied to any of the TCL containers, and many of the STL containers. The following example illustrates creating a unique_tree node with elements from an STL set.

// create a unique_tree node with elements from a set
std::set<Employee> emplVec;

populate_container(emplVec); // populate the employee set




// create a unique_tree container node of the same type, and initialize it with elements from the set
unique_tree<Employee> emplTree(emplVec.begin(), emplVec.end());

The range constructor also allows you to create a tree container using a range of elements from another TCL container, as shown below.

// create a multitree node with elements from a unique_tree node.
unique_tree<Employee> emplTree;
populate_tree(emplTree); // populate the employee tree

// create a multitree container node of the same type, and initialize it with elements from one of the unique_tree nodes
unique_tree::const_iterator it = emplTree.begin();  // first node of the tree
if (it != emplTree.end()) { // insure iterator is valid
   create a multitree node with all child elements from the first child node of the unique_tree
   multitree<Employee> emplTree2(it.node()->begin(), it.node()->end());
}

Using the TCL container insert range operations

All TCL tree containers provide an insert range operation, discussed further above, which allow you to insert a range of elements from an iterator range into a tree container node. The iterator range can be from an STL container or another TCL container. The example code below shows how elements may be inserted in a TCL container from an iterator range of elements from an STL container.

// create and populate vector with military personnel for a particular division
std::vector<MilitaryPersonnel> divisionVec;
populate_container(emplVec);

// militaryTree here is an object of unique_tree<MilitaryPersonnel>,
// used as a tree structure to track military personnel in their proper company/division/etc.
// find the correct division
unique_tree<MilitaryPersonnel>::iterator it = militaryTree.find_deep("div305");
if (it != militaryPersonnel.end()) {  // insure we found the appropriate node to insert the children in
   it.node()->insert(divisionVec.begin(), divisionVec.end());
}

When specifying an iterator range, the range does not always have to include all the elements in the container or node. The only requirements is that the iterator pair belong to the same container (or TCL node) and the end iterator is >= to the begin iterator. When inserting elements from an STL set into a tree container, one could use the results of std::equal_range() on the set, to insert those elements into a TCL container/node.

The TCL container insert range operations also allow you to insert elements from one tree to another. The iterator range can consists of either child iterators or descendant iterators. This provides much flexibility for inserting/copying nodes from one tree container to another. The examples below illustrate this concept.

// create and populate source tree
tree<Location> locationTree;
populate_tree(locationTree);

// create destination trees
unique_tree<Location> locationUniqueTree;
sequential_tree<Location> locationSeqTree;

// find a specific child of the root node
tree<Location>::const_iterator it = locationTree.find(Location("Ia"));
if (it != locationTree.end()) {
   // insert children of node in unique tree node
   locationUniqueTree.insert(it.node()->begin(), it.node()->end());






// insert descendants of node in sequential tree node
   locationSeqTree.insert(locationSeqTree.end(), it.node()->pre_order_begin(), it.node()->pre_order_end());
}

In these examples, the destination trees have been root nodes (or trees). Keep in mind that the destination can be any node in the tree, not just the root node.

Using the STL range constructors with TCL iterators

STL containers also have iterator range constructors, which accept an input iterator range. Since the TCL iterators qualify as input iterators, they can be used to create STL containers. Both the TCL child and descendant iterators can be used for this purpose. This is very handy for the purpose of creating an STL container of a whole tree structure, as illustrated below.

// create and populate source tree
tree<Project> projectTree;
populate_tree(projectTree);

// create a vector from all elements in the tree
// The type of descendant iterator used will determine the resulting order in the vector
std::vector<Project> projectVec(projectTree.level_order_begin(), projectTree.level_order_end());

// Now create a std::set container with just the immediate children of the tree
std::set<Project> projectSet(projectTree.begin(), projectTree.end());

Using the STL insert range operations with TCL iterators

STL containers also provide an insert range operation, that accepts a pair of input iterators which specify the range of elements to insert. The example below illustrates their use with TCL iterators.

// create and populate source tree
sequential_tree<Rank> rankTree;
populate_tree(rankTree);
std::set<Rank> rankSet;
// insert all elements from tree into set
rankSet.insert(rankTree.pre_order_begin(), rankTree.pre_order_end());