cmmtree.cpp

Go to the documentation of this file.

#include "node.cpp"
#include "hpp/cmmtree.hpp"
#include "hpp/predicates.hpp"
 
template <class X1, template<typename> class predicate>
void CMMTree<X1, predicate>::join_data( std::vector < X1 >const* const& adr)  {
  if( p_dataset ) throw std::runtime_error("CMMTree<X1, predicate>::join_data(): This tree is already assigned with data.\nConsider using the tree_clear() function.");
  p_dataset = adr;
}
 
template <class X1, template<typename> class predicate>
void CMMTree<X1, predicate>::join_data(std::vector < X1 >const* const& adr, typename std::vector<X1>::const_iterator const& pos){
  if( p_dataset ) throw std::runtime_error("CMMTree<X1, predicate>::join_data(): This tree is already assigned with data.\nConsider using the tree_clear() function.");
  p_dataset = adr;
  root->data_address()=pos;
}
 
template <class X1, template<typename> class predicate>
inline
void CMMTree<X1, predicate>::add_next_firstborn(size_t generation, node<X1>* const& node_adr){
  if( generation == MTree.size() ){
    MTree.emplace_back( firstborns( 1, node_adr ) );
  }  
  else{
    MTree[generation].push_back(node_adr);
  }  
}
 
template <class X1, template<typename> class predicate>
void CMMTree<X1, predicate>::find_new_generation( size_t generation ) {
  size_t k, sn;
  node<X1>* p_current_node;
  typename std::vector<X1>::const_iterator pos ;
  
  for(size_t i = 0; i < MTree[generation].size(); ++i ){
    k=0;
    sn = MTree[generation][i]->siblings_number() ;
    p_current_node = MTree[generation][i];        
    p_current_node->change_children_capacity();   
    do{
      if(generation){       
        p_current_node=(*p_current_node->parent->children)[k];
      }
      pos = p_dataset->begin();
      while( pos != p_dataset->end() ){
        if( condition( p_current_node, pos ) ) {  
          p_current_node->add_new_node( pos );
          if( p_current_node->children_number() == 1 ){
            add_next_firstborn(generation+1, (*p_current_node->children)[0] ); 
          }
        }
        pos++;
      }
    }while(sn > k++ );
  }
}
 
template <class X1, template<typename> class predicate> 
void CMMTree<X1, predicate>::create_subtrees_roots( std::vector < X1 > const& roots_data ) {
  if( !root->isNULLit(root->d_iterator) || root->children )
    throw std::runtime_error("CMMTree<X1, predicate>::create_subtrees_roots():\nThis function can only be called if the root node is not associated with any element of the input dataset and has no children yet.");
 
  typename std::vector<X1>::const_iterator pos = roots_data.begin();
  while( pos != roots_data.end() ){
    root->add_new_node( pos );
    if( root->children_number() == 1 ){
      add_next_firstborn(1, (*root->children)[0] ); 
    }
    ++pos;
  }
}
 
template <class X1, template<typename> class predicate>
long long CMMTree<X1, predicate>::tree_create()   {
  if(!p_dataset) throw std::runtime_error("CMMTree<X1, predicate>::tree_create(): The tree is not assigned to the data.\nConsider using the join_data() function.\n");
  size_t cht; //The current height of a tree;
  auto t1 = std::chrono::high_resolution_clock::now();
  do{
    cht=MTree.size();
    find_new_generation( cht-1 );
  }while(cht < MTree.size());
  auto t2 = std::chrono::high_resolution_clock::now();
  return std::chrono::duration_cast<std::chrono::microseconds> (t2 - t1).count();
}//tree_create
 
template <class X1, template<typename> class predicate>
size_t CMMTree<X1, predicate>::firstborns_number(size_t i)const  {
  if(i>=MTree.size() )
    throw std::runtime_error("CMMTree<X1, predicate>::firstborns_number(): The argument out of range.");
  return MTree[i].size();
}
 
template <class X1, template<typename> class predicate>
size_t CMMTree<X1, predicate>::leaves_number(size_t i)const  {
  if(i>=MTree.size() )
    throw std::runtime_error("CMMTree<X1, predicate>::leaves_number(): The argument out of range.");
  size_t tmp(0);
  if(i==0){
    if( !MTree[0][0]->children ) return 1;
    else return tmp;
  }
  for(size_t j = 0; j < MTree[i].size(); ++j )
    for(size_t k = 0; k < MTree[i][j]->parent->children_number(); ++k )
      if( !(*MTree[i][j]->parent->children)[k]->children )
        tmp++;
  return tmp;
}
 
template <class X1, template<typename> class predicate>
size_t CMMTree<X1, predicate>::generation_size(size_t i)const  {
  if(i>=MTree.size() )
    throw std::runtime_error("CMMTree<X1, predicate>::generation_size(size_t i): The argument out of range.");
  if(i==0) return 1;
  size_t tmp(0);
  for(size_t j = 0; j < MTree[i].size(); ++j )
    tmp+=MTree[i][j]->parent->children_number();
  return tmp;
}
 
template <class X1, template<typename> class predicate>
inline
void CMMTree<X1, predicate>::generation_addresses(size_t i, std::vector< node<X1>const* > & vec)const{
  if(i>=MTree.size() )
    throw std::runtime_error("CMMTree<X1, predicate>::generation_addresses(): The first argument out of range.");
  vec.clear();
  if( i==0 ) {
      vec.push_back( MTree[0][0] );
  }
  else{
    for(size_t j = 0; j < MTree[i].size(); ++j ){
      for(size_t k = 0; k < MTree[i][j]->parent->children_number(); ++k ){
        vec.push_back( (*MTree[i][j]->parent->children)[k] );
      }
    }
  }
}
 
template <class X1, template<typename> class predicate>
inline
void CMMTree<X1, predicate>::generation_addresses(size_t i, std::vector< node<X1>* > & vec)const{
  if(i>=MTree.size() )
    throw std::runtime_error("CMMTree<X1, predicate>::generation_addresses(): The first argument out of range.");
  vec.clear();
  if( i==0 ) {
      vec.push_back( MTree[0][0] );
  }
  else{
    for(size_t j = 0; j < MTree[i].size(); ++j ){
      for(size_t k = 0; k < MTree[i][j]->parent->children_number(); ++k ){
       vec.push_back( (*MTree[i][j]->parent->children)[k] );
      }
    }    
  }
}
 
template <class X1, template<typename> class predicate>
inline
void CMMTree<X1, predicate>::leaves_addresses(size_t i, std::vector< node<X1>const* > & vec)const  {
  vec.clear();
  if(i>=MTree.size() )
    throw std::runtime_error("CMMTree<X1, predicate>::leaves_addresses(): The first argument out of range.");
  if( i==0 ) {
    if(!MTree[0][0]->children ){
      vec.push_back( MTree[0][0] );
    }  
  }
  else{
    for(size_t j = 0; j < MTree[i].size(); ++j ){
      for(size_t k = 0; k < MTree[i][j]->parent->children_number(); ++k ){
        if( !(*MTree[i][j]->parent->children)[k]->children ){
          vec.push_back( (*MTree[i][j]->parent->children)[k] );
        }  
      }    
    }      
  }
}
 
template <class X1, template<typename> class predicate>
inline
node<X1>const* CMMTree<X1, predicate>::brother_address( node<X1>const* ptr, size_t i)const {  
  if(ptr->prev)
    if( i < ptr->prev->children->size() )
      return ptr->prev->children->operator[](i); 
  return nullptr;
}
 
template <class X1, template<typename> class predicate>
inline node<X1>const* const& CMMTree<X1, predicate>::firstborn_address(size_t i, size_t j)const  {
  if(i >= MTree.size() ) throw std::runtime_error("CMMTree<X1, predicate>::firstborn_address(): The first argument out of range.");
  if(j >= MTree[i].size() ) throw std::runtime_error("CMMTree<X1, predicate>::firstborn_address(): The second argument out of range.");
  return MTree[i][j];
}
 
template <class X1, template<typename> class predicate>
inline
void CMMTree<X1, predicate>::jagged_table_reconstruction(size_t lev){
  for(size_t i=lev; i<MTree.size();++i){
    MTree[i].clear();
    if(i == 1){
      if( root->children_number() ){
        MTree[i].push_back(root->children->operator[](0));
      }  
      else{
        MTree.resize(i);
      }  
    }
    else{
      for(auto& r: MTree[i-1]){                                 // for each firsborn 
        for(auto& rc: *r->parent->children ){                   // for each of brothers
          if( rc->children_number() ){
            MTree[i].push_back(rc->children->operator[](0));
          }  
        }
      }
      if( !MTree[i].size() ){
        MTree.resize(i);
      }  
    }
  }
}
 
template <class X1, template<typename> class predicate>
void CMMTree<X1, predicate>::delete_one_node( node<X1>* &to_del ){
  // NOTE ! Deleting any node also deletes all its descendants
  if(!to_del->parent) throw std::runtime_error("CMMTree<X1, predicate>::delete_node(): The root node can not be deleted!\n");
  node<X1>* prev=to_del->parent;
  size_t i=0, cs=prev->children->size();
  for(; i<cs; ++i){
    if(prev->children->operator[](i) == to_del){
      delete prev->children->operator[](i);
      cs-=1;
      for(; i<cs; ++i){
        prev->children->operator[](i)=prev->children->operator[](i+1);
      }
    }
  }
  prev->children->pop_back();
  if(!prev->children->size()){
    delete prev->children;
    prev->children = nullptr;
  }
  jagged_table_reconstruction( to_del->node_level() );
}
 
template <class X1, template<typename> class predicate>
void CMMTree<X1, predicate>::delete_nodes( std::vector< node<X1>* > & to_del, size_t lev ) {
  if(!lev) throw std::runtime_error("CMMTree<X1, predicate>::delete_node(): The root node can not be deleted!\n");
  for(auto& r: to_del){
    node<X1>* prev=r->parent;
    size_t i=0, cs=prev->children->size();
    for(; i<cs; ++i){
      if(prev->children->operator[](i) == r){
        delete prev->children->operator[](i);
        cs-=1;
        for(; i<cs; ++i){
          prev->children->operator[](i)=prev->children->operator[](i+1);
        }
      }
    }
    prev->children->pop_back();
    if(!prev->children->size()){
      delete prev->children;
      prev->children = nullptr;
    }
  }
  jagged_table_reconstruction( lev );
}
 
template <class X1, template<typename> class predicate>
void CMMTree<X1, predicate>::tree_clear() {
  if(root->children_number()){
    for (auto& r : *root->children)
      delete r;
    delete root->children;
    root->children=0;
    MTree.resize(1);
  }
  p_dataset = nullptr;
  root->data_address()=Null_iterator( X1() );
}
 
template <class X1, template<typename> class predicate>
void CMMTree<X1, predicate>::tree_shape(std::ostream& out)const{
  out<< "\nThe shape of the CMMTree  ( N - number of nodes, F - number of firstborns, L - number of leaves ).\n";
 
  size_t T_s= MTree.size();
  long N_i= 0, N_ip= 0;
  long F_i= 0, F_ip= 0;
  long L_i= 0, L_ip= 0;
  long SN1= 0, SN2 = 0;
  long SF1= 0, SF2 = 0;
 
  size_t j;
  std::vector< const node<X1>* > N_ip_vec;
  std::vector< const node<X1>* > F_ip_vec;
 
// NOTE !!!
// dF/Ni and dL/Ni are not normalized to 1 and therefore may go outside the range of the normalized graph. 
  out<< "Lev ;      N     ;      F     ;      L     ;     F/N    ;     L/N    ;    dF/Ni   ;    dL/Ni   ; dF/(Fi+Fip); dF/(Ni+Nip); dL/(Ni+Nip);(SN2-SN1)/Ni;(SF2-SF1)/Ni;\n";
  out<< "----;------------;------------;------------;------------;------------;------------;------------;------------;------------;------------;------------;------------;\n";
 
  for(size_t i=0; i<T_s ; ++i){
    N_i= (long)generation_size(i);
    F_i= (long)firstborns_number(i);
    L_i= (long)leaves_number(i);
 
    // Sums based on the firstborn of the previous generation.
    if(i>0){
      if(F_ip % 2){
        SF1=SF2=0; j=0;
 
        for( ; j < MTree[i-1].size()/2; ++j ){
          MTree[i-1][j]->all_siblings_addresses( F_ip_vec );
          for(auto&& r:F_ip_vec){
            SF1+= (long)r->children_number();
          }  
        }
        j++;
        for( ; j < MTree[i-1].size(); ++j ){
          MTree[i-1][j]->all_siblings_addresses( F_ip_vec );
          for(auto&& r:F_ip_vec){
            SF2+= (long)r->children_number();
          }  
        }
      }
      else{
        SF1=SF2=0; j=0;
        for( ; j < MTree[i-1].size()/2; ++j ){
          MTree[i-1][j]->all_siblings_addresses( F_ip_vec );
          for(auto&& r:F_ip_vec){
            SF1+= (long)r->children_number();
          }  
        }
        for( ; j < MTree[i-1].size(); ++j ){
          MTree[i-1][j]->all_siblings_addresses( F_ip_vec );
          for(auto&& r:F_ip_vec) {
            SF2+= (long)r->children_number();
          }  
        }
      }
    }
 
    if(i>0){ // Sums based on previous generation nodes
      generation_addresses(i-1, N_ip_vec) ;
      if(N_ip_vec.size() % 2){
        SN1=SN2=0; j=0;
        for( ; j < N_ip_vec.size()/2; ++j ){
          SN1+= (long)N_ip_vec[j]->children_number();
        }
        j++;
        for( ; j < N_ip_vec.size(); ++j ){
          SN2+= (long)N_ip_vec[j]->children_number();
        }
      }
      else{
        SN1=SN2=0; j=0;
        for( ; j < N_ip_vec.size()/2; ++j ){
          SN1+= (long)N_ip_vec[j]->children_number();
        }  
        for( ; j < N_ip_vec.size(); ++j ){
          SN2+= (long)N_ip_vec[j]->children_number();
        }  
      }
    }
 
    out.width(4);
    out << i << ";" ;
 
    out.width(12);
    out << N_i << ';';  //  N
    out.width(12);
    out << F_i << ';';  //  F
    out.width(12);
    out << L_i << ';';  //  L
    out.width(12);
    out << (double)F_i/(double)N_i << ';';  //  F/N
    out.width(12);
    out << (double)L_i/(double)N_i << ';';  //  L/N
    out.width(12);
    out << (double)(F_i - F_ip)/(double)N_i << ';';  //  dF/Ni
    out.width(12);
    out << (double)(L_i - L_ip)/(double)N_i << ';';  //  dL/Ni
    out.width(12);
    out << (double)(F_i - F_ip)/(double)(F_i + F_ip) << ';';  //  dF/(Fi + Fip)
    out.width(12);
    out << (double)(F_i - F_ip)/(double)(N_i + N_ip) << ';';  //  dF/(Ni + Nip)
    out.width(12);
    out << (double)(L_i - L_ip)/(double)(N_i + N_ip) << ';';  //  dL/(Ni + Nip)
    out.width(12);
    out << (double)(SN2 - SN1)/(double)N_i << ';';  //  (SN2-SN1)/Ni
    out.width(12);
    out << (double)(SF2 - SF1)/(double)N_i << ';';   //  (SF2-SF1)/Ni
    out.width(12);
    out << std::endl;
 
    N_ip= (long)generation_size(i);
    F_ip= (long)firstborns_number(i);
    L_ip= (long)leaves_number(i);
  }
  out<< "----;------------;------------;------------;------------;------------;------------;------------;------------;------------;------------;------------;------------;\n";
}//tree_shape
 
template <class X1, template<typename> class predicate>
std::ostream& operator<<(std::ostream& out, CMMTree<X1, predicate> const& r)   {
  int c(0);
  std::string msg("\n");
 
  #ifdef NODE_COUNTER
    #ifdef MAX_NODES_TO_PRINT
      if( r.all_nodes_number() <= MAX_NODES_TO_PRINT ) 
        c = 1;
      else
        msg = ("\nCMMTree has more nodes than was defined using the \'MAX_NODES_TO_PRINT\' directive.\n");
    #else
      msg = "\n\'MAX_NODES_TO_PRINT\' is not defined.\n";
    #endif // MAX_NODES_TO_PRINT
  #else
    msg = "\nPlease define the \'NODE_COUNTER\' and \'MAX_NODES_TO_PRINT\' directives.\n";
  #endif // NODE_COUNTER
 
  if(c){
    std::vector< node<X1>const* > vec;
    #ifdef PRINT_ALL_PATHS
      std::vector< typename std::vector<X1>::const_iterator > path;
      size_t k;
      for(size_t i=0; i<r.MTree.size() ; ++i){
        r.generation_addresses(i, vec);
        out << "--Level : " << i << " --" << std::endl;
        path.clear();
        for(size_t j=0; j<vec.size() ; ++j){
          out << "---Path : " << j << " ---" << std::endl;
          vec[j]->data_on_path(path);
          k = path.size();
          while(k>0){
            out<<*path[--k] << "\n"; //";";
          }
        }
        out << std::endl;
      }
    #else
      for(size_t i=0; i<r.MTree.size() ; ++i){
        r.generation_addresses(i, vec);
        for(size_t j=0; j<vec.size() ; ++j){
          //out << *vec[j] << ':';
          out << '(' ;
          if( vec[j]->data_address() != Null_iterator( X1() ) )
            out<< *vec[j]->data_address();
          out<< ") ";
        }
        out <<'\n';
      }
    #endif // PRINT_ALL_PATHS
  }
  else
    out << "CMMTree hight : " << r.tree_height() << msg;
  return out;
}