Tree Container Library: Auxiliary Code

---

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())
      }
  }