tree_util.tpp

Go to the documentation of this file.

/***
 * Copyright (c) 2005, SkeTo Project
 * All rights reserved.
 */
#ifdef __TREE_UTIL_H__
#ifndef __TREE_UTIL_TPP__
#define __TREE_UTIL_TPP__

#include <stdio.h>
#include <fstream>
#include <assert.h>

// Private definitions
namespace tree_util {

  template< typename A >
  struct IntermediateVal {
    int size;
    node< IntermediateVal > *cutnode;
    const node< A >* orgnode;
  };

  template< typename A >
  static node< A >*
  construct_tree_from_array_rec( const int** flags,
                 const A** values );

  static inline int
  ceil_divided_by_m( int x, int m );

  template< typename A >
  static bool
  compute_size_and_mark_critical( const node< A >* tree,
                  const int nprocs,
                  node< tree_util::IntermediateVal< A > >** size_critical_tree,
                  int *global_size );
  
  template< typename A >
  static bool
  write_distributed_tree_to_fstream( node< tree_util::IntermediateVal< A > >* size_critical_tree,
                     int globalsize,
                     std::fstream &fout );

  template< typename A >
  static node< tree_util::IntermediateVal< A > >*
  compute_size_rec( const node< A >* tree );

  template< typename A >
  static int
  mark_critical_node( node< tree_util::IntermediateVal< A > >* size_critical_tree,
              const int m );

  template< typename A >
  static void
  get_global_tree( node< tree_util::IntermediateVal< A > >* root,
           int *flags,
           int *sizes,
           node< tree_util::IntermediateVal< A > >** subroots );

  template< typename A >
  static void
  get_global_tree_rec( node< tree_util::IntermediateVal< A > >* root,
               int *flags,
               int *sizes,
               node< tree_util::IntermediateVal< A > >** subroots,
               int *count );
  
  template< typename A >
  static void
  get_local_tree( const node< tree_util::IntermediateVal< A > > *root,
          int *local_flags,
          A* local_values );
  

  template< typename A >
  static void
  get_local_tree_rec( const node< tree_util::IntermediateVal< A > > *root,
              int *local_flags,
              A* local_values,
              int *local_count );

  template< typename A >
  static void
  serialize_subtree( const node< A > *root,
             int **flags,
             A **valus );
  
}

// Implementations

template< typename A >
node< A >*
tree_util::read_tree_from_file( const char* filename )
{
  std::fstream fin( filename, std::ios::in );
  if ( fin.fail( ) ) return NULL;

  int nNodes; fin >> nNodes;
  if ( nNodes <= 0 ) return NULL;

  int *flags = new int[ nNodes ];
  A* values = new A[ nNodes ];

  for ( int i = 0; i < nNodes; i++ ) {
    fin >> flags[ i ] >> values[ i ];
  }

  return construct_tree_from_array( flags, values );
}

template< typename A >
node< A >*
tree_util::construct_tree_from_array( const int* flags,
                      const A* values )
{
  return construct_tree_from_array_rec( &flags, &values );
}

template< typename A >
static node< A >*
tree_util::construct_tree_from_array_rec( const int** flags,
                      const A** values )
{
  const int &flag = *((*flags)++);
  const A &value = *((*values)++);

  node< A >* rettree = new node< A >( value );
  if ( flag == node< A >::SER_NODE ) {
    rettree->left  = construct_tree_from_array_rec( flags, values );
    rettree->left->parent = rettree;

    rettree->right = construct_tree_from_array_rec( flags, values );
    rettree->right->parent = rettree;
  }
  return rettree;
}

template< typename A > 
void
tree_util::free_all_tree( node< A >* root )
{
  if ( root == NULL ) return;

  free_all_tree( root->left );
  free_all_tree( root->right );
  delete root;
}

template< typename A >
bool
tree_util::check_perfect_binary_tree( const node< A >* tree )
{
  if ( tree->isLeaf( ) ) return true;
  if ( !tree->left || !tree->right ) return false;
  return ( check_perfect_binary_tree( tree->left ) &&
       check_perfect_binary_tree( tree->right ) );
}

template< typename A >
bool
tree_util::dist_and_write_to_file( const node< A >* tree,
                   const int nprocs,
                   const char *filename )
{
  if ( !check_perfect_binary_tree( tree ) ) {
    return false;
  }

  node< IntermediateVal< A > > *size_critical_tree;
  int global_size;

  if ( !compute_size_and_mark_critical( tree,
                    nprocs,
                    &size_critical_tree,
                    &global_size ) ) {
    return false;
  }

  std::fstream fout( filename, std::ios::out );
  if ( fout.fail( ) ) return false;

  if ( !write_distributed_tree_to_fstream( size_critical_tree,
                       global_size,
                       fout ) ) {
    return false;
  }

  free_all_tree( size_critical_tree );
  return true;
}

static int
tree_util::ceil_divided_by_m( int x, int m )
{
  return ( x + ( m - 1 ) ) / m;
}

template< typename A >
static bool
tree_util::compute_size_and_mark_critical( const node< A >* tree,
                       const int nprocs,
                       node< IntermediateVal< A > >** size_critical_tree,
                       int *global_size )
{
  *size_critical_tree = compute_size_rec( tree );
  
  int size = (*size_critical_tree)->value.size;
  int m = 2 * size / ( nprocs / 2 + 1 );
  
  int ncritical = mark_critical_node( *size_critical_tree, m );

  // check the number of distributed trees is not greater than nprocs. 
  assert( ncritical * 2 + 1 <= nprocs );
    
  *global_size = ncritical * 2 + 1;

  return true;
}

template< typename A >
static bool
tree_util::write_distributed_tree_to_fstream( node< tree_util::IntermediateVal< A > >* size_critical_tree,
                          int globalsize,
                          std::fstream &fout )
{
  fout << globalsize << std::endl;

  // write global structure
  int *sizes = new int[ globalsize ];
  node< tree_util::IntermediateVal< A > > **subroots
    = new node< tree_util::IntermediateVal< A > >*[ globalsize ];
  {
    int *flags = new int[ globalsize ];
    get_global_tree( size_critical_tree, flags, sizes, subroots );

    for ( int p = 0; p < globalsize; p++ ) {
      fout << flags[ p ] << " " << sizes[ p ] << std::endl;
    }

    delete [] flags;
  }

  // write local subtrees
  {
    for ( int p = 0; p < globalsize; p++ ) {
      int *local_flags = new int[ sizes[ p ] ];
      A *local_values = new A[ sizes[ p ] ];
      
      get_local_tree( subroots[ p ], local_flags, local_values );
      
      for ( int i = 0; i < sizes[ p ]; i++ ) {
    fout << local_flags[ i ] << " " << local_values[ i ] << std::endl;
      }
      
      delete [] local_values;
      delete [] local_flags;
    }
  }

  delete [] subroots;
  delete [] sizes;

  return true;
}

template< typename A >
static node< tree_util::IntermediateVal< A > >*
tree_util::compute_size_rec( const node< A >* tree )
{
  node< IntermediateVal< A > >* rettree;
  if ( tree->isLeaf( ) ) {
    IntermediateVal< A > val;
    val.size = 1;
    val.cutnode = NULL;
    val.orgnode = tree;
    rettree = new node< tree_util::IntermediateVal< A > >( val );
  } else {
    node< tree_util::IntermediateVal< A > >* left
      = compute_size_rec( tree->left );
    node< tree_util::IntermediateVal< A > >* right
      = compute_size_rec( tree->right );
      
    IntermediateVal< A > val;
    val.size = 1 + left->value.size + right->value.size;
    val.cutnode = NULL;
    val.orgnode = tree;
    rettree = new node< IntermediateVal< A > >( val );
    rettree->left  = left;  rettree->left->parent  = rettree;
    rettree->right = right; rettree->right->parent = rettree;
  }
  return rettree;
}

template< typename A >
static int
tree_util::mark_critical_node( node< IntermediateVal< A > >* size_critical_tree,
                   const int m )
{
  int n_critical = 0;
  if ( size_critical_tree->isLeaf( ) ) {
  } else {
    n_critical += mark_critical_node( size_critical_tree->left,  m );
    n_critical += mark_critical_node( size_critical_tree->right, m );

    int size       = size_critical_tree->value.size;
    int left_size  = size_critical_tree->left->value.size;
    int right_size = size_critical_tree->right->value.size;

    if ( ceil_divided_by_m( size, m ) > ceil_divided_by_m( left_size, m ) &&
     ceil_divided_by_m( size, m ) > ceil_divided_by_m( right_size, m ) ) {
      size_critical_tree->nodetype = node< IntermediateVal< A > >::CUTNODE;
      n_critical += 1;
      size_critical_tree->value.cutnode = size_critical_tree;
    } else {
      node< IntermediateVal< A > >* left_critical
    = size_critical_tree->left->value.cutnode;
      node< IntermediateVal< A > >* right_critical
    = size_critical_tree->right->value.cutnode;
      if ( left_critical )  size_critical_tree->value.cutnode = left_critical;
      if ( right_critical ) size_critical_tree->value.cutnode = right_critical;
    }

  }
  return n_critical;
}

template< typename A >
static void
tree_util::get_global_tree( node< IntermediateVal< A > >* root,
                int *flags,
                int *sizes,
                node< IntermediateVal< A > >** subroots )
{
  int count = 0;
  get_global_tree_rec( root, flags, sizes, subroots, &count );
}

template< typename A >
static void
tree_util::get_global_tree_rec( node< IntermediateVal< A > >* root,
                int *flags,
                int *sizes,
                node< IntermediateVal< A > >** subroots,
                int *count )
{
  int count_this = (*count)++;
  if ( root->value.cutnode ) {
    flags[ count_this ]    = node< A >::SER_NODE;
    sizes[ count_this ]    = root->value.size - root->value.cutnode->value.size + 1;
    subroots[ count_this ] = root;

    get_global_tree_rec( root->value.cutnode->left,
             flags, sizes, subroots, count );
    get_global_tree_rec( root->value.cutnode->right,
             flags, sizes, subroots, count );
  } else {
    flags[ count_this ]    = node< A >::SER_LEAF;
    sizes[ count_this ]    = root->value.size;
    subroots[ count_this ] = root;
  }
}

template< typename A >
static void
tree_util::get_local_tree( const node< IntermediateVal< A > > *root,
               int *local_flags,
               A* local_values )
{
  int local_count = 0;
  get_local_tree_rec( root, local_flags, local_values, &local_count );
}
          
template< typename A >
static void
tree_util::get_local_tree_rec( const node< IntermediateVal< A > > *root,
                   int *local_flags,
                   A* local_values,
                   int *local_count )
{
  int current_count = ( *local_count )++;
  local_values[ current_count ] = root->value.orgnode->value;
  if ( root->isLeaf( ) ) {
    local_flags[ current_count ] = node< A >::SER_LEAF;

  } else if ( root->nodetype == node< IntermediateVal< A > >::NORMAL ) {
    local_flags[ current_count ] = node< A >::SER_NODE;

  } else {
    local_flags[ current_count ] = node< A >::SER_CUTNODE;
  }

  if ( !root->isLeaf( ) &&
       root->nodetype == node< IntermediateVal< A > >::NORMAL ) {
    get_local_tree_rec( root->left,  local_flags, local_values, local_count );
    get_local_tree_rec( root->right, local_flags, local_values, local_count );
  }
}

template< typename A >
bool
tree_util::write_to_file( const node< A >* tree,
              const char *filename )
{
  std::fstream fout( filename, std::ios::out );
  if ( fout.fail( ) ) return false;
  
  int size = get_size_rec( tree );
  fout << size << std::endl;
  
  int *local_flags = new int[ size ];
  A *local_values = new A[ size ];
      
  int *p_flags = local_flags;
  A *p_values = local_values;
  serialize_subtree( tree, &p_flags, &p_values );

  for ( int i = 0; i < size; i++ ) {
    fout << local_flags[ i ] << " " << local_values[ i ] << std::endl;
  }

  delete [] local_values;
  delete [] local_flags;

  return true;
}

template< typename A >
int
tree_util::get_size_rec( const node< A >* tree )
{
  if ( tree->isLeaf( ) ) {
    return 1;
  } else {
    return 1 + get_size_rec( tree->left )
      + get_size_rec( tree->right );
  }
}

template< typename A >
static void
tree_util::serialize_subtree( const node< A > *root,
                  int **flags,
                  A **values )
{
  if ( root->isLeaf( ) && root->nodetype == node< A >::NORMAL ) {
    *((*flags)++) = node< A >::SER_LEAF;
    *((*values)++) = root->value;
  } else if ( root->isLeaf( ) && root->nodetype == node< A >::CUTNODE ) {
    *((*flags)++) = node< A >::SER_CUTNODE;
    *((*values)++) = root->value;
  } else if ( !root->isLeaf( ) ) {
    *((*flags)++) = node< A >::SER_NODE;
    *((*values)++) = root->value;

    serialize_subtree( root->left,  flags, values );
    serialize_subtree( root->right, flags, values );
  } else {
    assert( false );
  }
}

#endif /* __TREE_UTIL_TPP__ */
#endif /* __TREE_UTIL_H__ */

---