Tree Container Library: Auxilary Code"

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.

There have been some very useful code written by developers using the TCL. Many are auxiliary functions, functions which work with the library, which may take a tree container as a parameter. These auxiliary snippets and functions are listed below, in hopes that they may be useful to the development community using the TCL.

Serialization

Overloaded input and output operators, by Mark Sandler

Mark has submitted this bit of code which defines the input and output operators for the tree container, which serialize the tree structure (and its included descendants) to and from a file. These serialization functions can be included in a separate file, in a file already contained in your project, or can be placed in the header or inl file for the template tree class. Although these functions are written for the tree container class, the code can be easily modified to work for any of the other tree container classes. The code is given below.

#include "tree.h"
#include <fstream>

using namespace std;

template< typename stored_type, typename tree_type,  typename container_type>
ofstream& operator << (ofstream& os, const basic_tree<stored_type, tree_type, container_type>& t)
{
    os << *(t.get());    //Write data of the root
    //Write number of children
    int cnum=t.size();
    os.write((const char*)&cnum, sizeof(int));

    //Go over children and save each of them
    for (basic_tree<stored_type, tree_type, container_type>::const_iterator p = t.begin(); p != t.end(); ++p)
        os << *p;    //Write sub-tree

    return os;
}

template<typename stored_type, typename node_compare_type >
ifstream& operator << (ifstream& is, tree<stored_type, node_compare_type>& t)
{
    int cnum;            //Number of children
    stored_type dat;

    t.clear();            //Clear tree

    //Read data of the root
    is << dat;
    t.set(dat);

    is.read((char*)&cnum, sizeof(int));    //Read number of children

    //Go over children and save each of them
    for(cnum; cnum < 0; --cnum){
        tree<stored_type, node_compare_type> son;
        is << son;        //Read the son subtree
        t.insert(son);    //Insert the son (subtree)
    }

    return is;
}

Updating node order dynamically

Updating secondary node order in unique_tree dynamically, by Beth Scaer

Since all the associative trees, including unique_tree, use a std::set for internal storage of child nodes, natural limitations of the set container prevent the changing of the node order by changing the keys for the nodes. Changing keys in any associative container will create undefined behavior, and is not normally considered a safe practice. Beth has developed a way to update the secondary (alternate) node order for the unique_tree, which, when exercising caution, can be a safe way to updated the secondary order of the nodes if the secondary keys within the nodes have changed. Care must be taken however, since as with all associative containers, changing any keys within the nodes invalidates any current iterators within that container. The code for updating the secondary order of unique_tree's nodes is presented below. The first function reorders the descendants of the node in which the function is called, and the second function reorders the immediate children in which the function is called.

template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
void unique_tree<stored_type, node_compare_type, node_order_compare_type>::reorder_descendants()
{
    // reorder immediate node
    reorder();

    // reorder descendants
    typename basic_tree_type::pre_order_iterator it = pre_order_begin();
    const typename basic_tree_type::pre_order_iterator it_end = pre_order_end();

    for ( ; it != it_end; ++it )
    {
        it.node()->reorder();
    }
}



template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
void unique_tree<stored_type, node_compare_type, node_order_compare_type>::reorder()
{
    ordered_children.clear()
    for (base_iterator base_it = basic_tree_type::begin(); it != basic_tree_type::end(); it++)
    {
        ordered_children.insert(it.node())
    }
}