/* Copyright 2020 Christophe Crespelle */

/* This file is part of Coedit. */
/* Coedit is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. */
/* Coedit is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. */
/* You should have received a copy of the GNU General Public License along with Coedit.  If not, see <https://www.gnu.org/licenses/>. */


/**********************************************************************************
 * Name   : Coedit
 * Authors: Christophe Crespelle
 * Mail   : Christophe.Crespelle@inria.fr 
 * Purpose: Minimal cograph edition, completion and deletion of an arbitrary graph
 *********************************************************************************/


#define MAX_LINE_LENGTH 1000

/********************/
/* Global variables */
/********************/

  long int lost_space=0;
  long int tab_truncated=0;

  long int copy_time=0;
  long int tab_expansion=0;
  


// structure for a dynamic cotree in an incremental algo with graphs known in advance
typedef struct dyncotree{
  int n;  // nb of vertices in the graph at the end of incremental algo
  int nl; // current nb of leaves
  int nt; // current nb of internal nodes
  int root;

  int *label;  // for internal nodes only, indexed by position
  int **children;  // for internal nodes only, indexed by position
  int *nb_child;  // for internal nodes only, indexed by position
  int *nb_leaves;  // for internal nodes only, indexed by position

  int *parent;  // for leaves and internal nodes, indexed by position
  int *pos_in_childpar;  // for leaves and internal nodes, indexed by position

//  int *ident; // identifiants of nodes, for leaves and internal nodes, indexed by position
// finalement les identifiants sont inutiles: la position des feuilles est exactement leur position dans le sgraph + dync->n, et la correspondance entre les positions dans le sgraph et les identifiants est stockée dans le sgraph


// NB: all nodes and leaves are referred by their positions instead of their identifiers, in all lists
// in "parent": internal nodes from 0 to n-1, leaves from n to 2n-1
// in "children": internal nodes from 0 to n-1 

} dyncotree;


// structure for additional information on a dynamic cotree where is inserted a new vertex
typedef struct supinfo_edit{
  int *nb_child_nh;  // nb of non-hollow children, only for internal nodes
  int *nb_child_nf;  // nb of non-full children
  int *nb_child_cforced;  // nb of completion forced children
  int *nb_child_dforced; // nb of deletion forced children, only for internal nodes
  int *nb_leaves_touched; // nb of leaves in the subtree that are neighbours with the new vertex, only for internal nodes
  int *nb_child_info;  // auxiliary table that must be initialised only one time during the incremental algorithm. This is the nb of children from which the information has already been received during the forwarding process to determine supinfo at each step of the incremental algo.
} supinfo_edit;





typedef struct cotree{
  int n;  //nb of leaves in the cotree
  int nt; // nb of nodes in the cotree: leaves + internal nodes
  int mt; // useful? (= nt-1???)
  int **children;
  int *parent;
  int *pos_in_childpar;
  int *nbchild;
  int *capacities;
  int root;
  int height;
  int *label;
  int *nb_leaves;

  int *permu1;
  int *deb1_seg;
  int *fin1_seg;
  int *pos_permu1;

  int *permu2;
  int *deb2_seg;
  int *fin2_seg;
  int *pos_permu2;

} cotree;






/******** COTREE MANAGEMENT functions - begin *********/


int is_leaf (int x, dyncotree *dync) {
  return (x >= dync->n);
}


int is_cforced (int pos_node, dyncotree *dync, supinfo_edit *info) {
    // prerequisite: the root is not a leaf
    if (is_leaf(pos_node,dync)) return (dync->pos_in_childpar[pos_node] < info->nb_child_nh[dync->parent[pos_node]]);
    else return ( ((dync->label[pos_node]==0)&&(info->nb_child_nh[pos_node]==dync->nb_child[pos_node])) || ((dync->label[pos_node]==1)&&(info->nb_child_cforced[pos_node]==dync->nb_child[pos_node])) );
  }





////////////////////////////////////////////////////////////////////////
////////// INITIALISE THE DYNCOTREE WITH TWO LEAVES: THE TWO FIRST VERTICES OF THE GRAPH
//----------------------------------------------------------------------
// IN  : g: the graph
// OUT : 
// RETURN : a pointer to the created dyncotree
//----------------------------------------------------------------------
// PREREQUISITE : 3 arrays of supinfo initialised at 0; and all information already assigned in g and in cot
////////////////////////////////////////////////////////////////////////

dyncotree* init_dyncotree_2leaves(sgraph* g) {

  dyncotree* dync;

  if( (dync=(dyncotree *)malloc(sizeof(dyncotree))) == NULL )
    report_error("init_dyncotree_2leaves: malloc() error");

  if( (dync->label=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("init_dyncotree_2leaves: malloc() error");
  if( (dync->children=(int **)malloc(g->n*sizeof(int*))) == NULL )
    report_error("init_dyncotree_2leaves: malloc() error");
  if( (dync->nb_child=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("init_dyncotree_2leaves: malloc() error");
  if( (dync->nb_leaves=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("init_dyncotree_2leaves: malloc() error");

  if( (dync->parent=(int *)malloc(2*g->n*sizeof(int))) == NULL )
    report_error("init_dyncotree_2leaves: malloc() error");
  if( (dync->pos_in_childpar=(int *)malloc(2*g->n*sizeof(int))) == NULL )
    report_error("init_dyncotree_2leaves: malloc() error");

//  if( (dync->ident=(int *)malloc(2*g->n*sizeof(int))) == NULL )
//    report_error("init_dyncotree_2leaves: malloc() error");


  dync->n=g->n;
  dync->nl=2; // current nb of leaves
  dync->nt=1; // current nb of internal nodes
  dync->root=0;


  if (g->sdegrees[1]>0) dync->label[0]=1; else dync->label[0]=0;
  if( (dync->children[0]=(int *)malloc(2*sizeof(int))) == NULL )
    report_error("init_dyncotree_2leaves: malloc() error");
  dync->children[0][0]=dync->n;
  dync->children[0][1]=dync->n+1;
  dync->nb_child[0]=2;
  dync->nb_leaves[0]=2;
  dync->parent[0]=-1;
  dync->pos_in_childpar[0]=-1;


  dync->parent[dync->n]=0;
  dync->pos_in_childpar[dync->n]=0;
  dync->parent[dync->n+1]=0;
  dync->pos_in_childpar[dync->n+1]=1;
//  dync->ident[dync->n]=g->permu[0];
//  dync->ident[dync->n+1]=g->permu[1];

  return dync;
}




////////////////////////////////////////////////////////////////////////
////////// ASSIGN ADDITIONAL INFO TO A COTREE UNDER THE INSERTION OF A NEW VERTEX, FOR GENERAL EDITION ALGORITHM
//----------------------------------------------------------------------
// IN  : cot: the cotree; g: the graph; x: the position (in the permu) of the vertex to be inserted
// OUT : info
// RETURN : 
//----------------------------------------------------------------------
// PREREQUISITE : 3 arrays of supinfo initialised at 0; and all information already assigned in g and in cot
////////////////////////////////////////////////////////////////////////
// IMPORTANT NOTE: TO KNOW IF A NODE IS FORCED, CHECK WHETHER ITS POSITION IN THE CHILDREN OF ITS PARENT IS LESS THAN THE NUMBER OF FORCED NODE OF ITS PARENT, SAME FOR NON HOLLOW : PB for the root...



supinfo_edit * init_supinfo_edit (dyncotree * dync) {
  supinfo_edit * info=NULL;
  int i;

  if( (info=(supinfo_edit *)malloc(sizeof(supinfo_edit))) == NULL )
    report_error("init_supinfo_edit: malloc() error");
  if( (info->nb_child_nh=(int *)malloc(dync->n*sizeof(int))) == NULL )
    report_error("init_supinfo_edit: malloc() error");
  if( (info->nb_child_nf=(int *)malloc(dync->n*sizeof(int))) == NULL )
    report_error("init_supinfo_edit: malloc() error");
  if( (info->nb_child_cforced=(int *)malloc(dync->n*sizeof(int))) == NULL )
    report_error("init_supinfo_edit: malloc() error");
  if( (info->nb_child_dforced=(int *)malloc(dync->n*sizeof(int))) == NULL )
    report_error("init_supinfo_edit: malloc() error");
  if( (info->nb_leaves_touched=(int *)malloc(dync->n*sizeof(int))) == NULL )
    report_error("init_supinfo_edit: malloc() error");
  if( (info->nb_child_info=(int *)malloc(dync->n*sizeof(int))) == NULL )
    report_error("init_supinfo_edit: malloc() error");

  for (i=0;i<dync->n;i++) {info->nb_child_nh[i]=0; info->nb_child_nf[i]=0; info->nb_child_cforced[i]=0; info->nb_child_dforced[i]=0; info->nb_leaves_touched[i]=0; info->nb_child_info[i]=0;}

  return info;
}






//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// iterative function to gather full children at the beginning of the list of the parent 
void gather_full_ite(int debug, FILE* fbug, dyncotree *dync, int x, int iter_debut_check, supinfo_edit * info) {

  int node;
  int temp,i;
  int nb_full;
  int is_full;

  int * queue;
  int head, tail;

  //debug
  // for no-warning at compil
  if ((debug==1)&&(x>=iter_debut_check)) fprintf(fbug,"\n");

  if( (queue=(int *)malloc((dync->nt)*sizeof(int))) == NULL )
    report_error("gather_full_ite: malloc() error");

  queue[0]=dync->root;
  head=0;
  tail=1;

  while (head!=tail) {

    node=queue[head];
        
    // gather full children at the beginnning of the list of children of node
    nb_full=0;
    for (i=0;i<info->nb_child_cforced[node];i++) {
      is_full=1;
      if (! is_leaf(dync->children[node][i],dync)) {
        if (info->nb_leaves_touched[dync->children[node][i]] < dync->nb_leaves[dync->children[node][i]]) is_full=0;
      }
      
      if (is_full==1) {
        temp = dync->children[node][nb_full];        
        dync->children[node][nb_full] = dync->children[node][i];
        dync->children[node][i] = temp;
        dync->pos_in_childpar[dync->children[node][nb_full]]=nb_full;
        dync->pos_in_childpar[dync->children[node][i]]=i;
        nb_full++;
      }
    }
    
    // enqueue non-full and non-hollow children that are not leaves
    for (i=dync->nb_child[node]-info->nb_child_nf[node];i<info->nb_child_nh[node];i++) {
      if (! is_leaf(dync->children[node][i],dync)) {
        queue[tail]=dync->children[node][i];
        tail++;
      }
    }

    head++;

  }

  if (queue!=NULL) free(queue);

}




//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void assign_supinfo_edit (FILE* fdync, FILE* fsupinfo, int consistency, int debug, FILE* fbug, dyncotree *dync, sgraph *g, int x, int iter_debut_check, supinfo_edit * info, int modif_method) {

  int *queue;  // a queue
  int head,tail;  // head and tail of the queue
  int comp_forced;  // boolean to determine whether the current node is completion forced
  int del_forced;  // boolean to determine whether the current node is deletion forced
  int nblt;  // temporary variable for number of leaves touched
  int i;
  //int k;

  // for no warning at compil
  if ((consistency==1)) {
    fprintf(fdync,"\n");
    fprintf(fsupinfo,"\n");
  }

  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  // first bottom-up search of the tree, gathers nh children at the beginning of children list
  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  
  if( (queue=(int *)malloc((dync->nt+dync->nl)*sizeof(int))) == NULL )
    report_error("assign_supinfo_edit: malloc() error");
  head=0;
  for (i=0;i<g->sdegrees[x];i++) queue[i] = g->slinks[x][i]+dync->n; // because positions of leaves are shifted by +dync->n between graph and cotree 
  tail=i;


  while (head!=tail) {

    if (queue[head] != dync->root) {

      // enqueue
      if (info->nb_child_nh[dync->parent[queue[head]]] == 0) {
        queue[tail]=dync->parent[queue[head]];
        tail++;

        //debug
        /*if (debug==1) {
          if (x==114653) {fprintf(fbug,"Tail: %d, contenu de tail-1: %d\n",tail,queue[tail-1]); fflush(fbug);}
        }*/
        
      }

      dync->children[dync->parent[queue[head]]][dync->pos_in_childpar[queue[head]]] = dync->children[dync->parent[queue[head]]][info->nb_child_nh[dync->parent[queue[head]]]];

      dync->children[dync->parent[queue[head]]][info->nb_child_nh[dync->parent[queue[head]]]] = queue[head];

      dync->pos_in_childpar[dync->children[dync->parent[queue[head]]][dync->pos_in_childpar[queue[head]]]]=dync->pos_in_childpar[queue[head]];

      dync->pos_in_childpar[queue[head]]=info->nb_child_nh[dync->parent[queue[head]]];

      (info->nb_child_nh[dync->parent[queue[head]]])++;

    }

    head++;

  }

    
  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  // second bottom-up search of the tree
  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  head=0;
  for (i=0;i<g->sdegrees[x];i++) queue[i] = g->slinks[x][i]+dync->n; // because positions of leaves are shifted by +n between graph and cotree 
  tail=i;

  //fprintf(stderr,"Head: %d, contenu: %d\n",head,queue[head]); fflush(stderr);
  //fprintf(stderr,"Tail: %d, contenu de tail-1: %d\n",tail,queue[tail-1]); fflush(stderr);

  while (head!=tail) {
    if (queue[head] != dync->root) {

      info->nb_child_info[dync->parent[queue[head]]] ++;

      if ( info->nb_child_nh[dync->parent[queue[head]]] == info->nb_child_info[dync->parent[queue[head]]] ) {
        queue[tail]=dync->parent[queue[head]];
        tail++;
        //fprintf(stderr,"Tail: %d, contenu de tail-1: %d\n",tail,queue[tail-1]); fflush(stderr);
      }

      if (info->nb_child_info[dync->parent[queue[head]]] == 1) {
  
        info->nb_child_dforced[dync->parent[queue[head]]] = dync->nb_child[dync->parent[queue[head]]] - info->nb_child_nh[dync->parent[queue[head]]];
        info->nb_child_nf[dync->parent[queue[head]]] = dync->nb_child[dync->parent[queue[head]]] - info->nb_child_nh[dync->parent[queue[head]]];
               
      }

      ////////////////////////////////////////////////////////////////////////////
      if (modif_method==0) {

        // test whether head is completion forced, in the positive puts it at the beginning of children list
        comp_forced=0;
        if (is_leaf(queue[head],dync)) comp_forced=1;
        else {
          if ( ((dync->label[queue[head]]==1)&&(info->nb_child_cforced[queue[head]]==dync->nb_child[queue[head]])) || ((dync->label[queue[head]]==0)&&(info->nb_child_nh[queue[head]]==dync->nb_child[queue[head]])) ) comp_forced=1;
        }

        if (comp_forced==1) {
          dync->children[dync->parent[queue[head]]][dync->pos_in_childpar[queue[head]]] = dync->children[dync->parent[queue[head]]][info->nb_child_cforced[dync->parent[queue[head]]]];

          dync->children[dync->parent[queue[head]]][info->nb_child_cforced[dync->parent[queue[head]]]] = queue[head];
         
          dync->pos_in_childpar[dync->children[dync->parent[queue[head]]][dync->pos_in_childpar[queue[head]]]]=dync->pos_in_childpar[queue[head]];
                   
          dync->pos_in_childpar[queue[head]]=info->nb_child_cforced[dync->parent[queue[head]]];

          info->nb_child_cforced[dync->parent[queue[head]]] ++;
        }
      }
      
      ////////////////////////////////////////////////////////////////////////////
      // test whether head is deletion forced, in the positive puts it at the beginning of the range of the list containing deletion forced. This always includes hollow nodes, which form an interval at the end of the children list
      del_forced=0;
      if (!is_leaf(queue[head],dync)) {
      
        if ( ((dync->label[queue[head]]==1) && (info->nb_child_nf[queue[head]]==dync->nb_child[queue[head]])) || ((dync->label[queue[head]]==0) && (info->nb_child_dforced[queue[head]]==dync->nb_child[queue[head]])) ) del_forced=1;
      }
           
      if (del_forced==1) {          
        dync->children[dync->parent[queue[head]]][dync->pos_in_childpar[queue[head]]] = dync->children[dync->parent[queue[head]]][dync->nb_child[dync->parent[queue[head]]]-info->nb_child_dforced[dync->parent[queue[head]]]-1];
              
        dync->children[dync->parent[queue[head]]][dync->nb_child[dync->parent[queue[head]]]-info->nb_child_dforced[dync->parent[queue[head]]]-1] = queue[head];
       
        dync->pos_in_childpar[dync->children[dync->parent[queue[head]]][dync->pos_in_childpar[queue[head]]]]=dync->pos_in_childpar[queue[head]];
                
        dync->pos_in_childpar[queue[head]]=dync->nb_child[dync->parent[queue[head]]]-info->nb_child_dforced[dync->parent[queue[head]]]-1;

        info->nb_child_dforced[dync->parent[queue[head]]] ++;
      }
      

      ////////////////////////////////////////////////////////////////////////////
      if ((modif_method==1)  || (modif_method==2)) {
    
        // test whether head is completion forced, in the positive puts it at the beginning of children list
        comp_forced=0;
        if (is_leaf(queue[head],dync)) comp_forced=1;
        else {
          if ( ((dync->label[queue[head]]==1)&&(info->nb_child_cforced[queue[head]]==dync->nb_child[queue[head]])) || ((dync->label[queue[head]]==0)&&(info->nb_child_nh[queue[head]]==dync->nb_child[queue[head]])) ) comp_forced=1;
        }

        if (comp_forced==1) {
      
          dync->children[dync->parent[queue[head]]][dync->pos_in_childpar[queue[head]]] = dync->children[dync->parent[queue[head]]][info->nb_child_cforced[dync->parent[queue[head]]]];
    
          dync->children[dync->parent[queue[head]]][info->nb_child_cforced[dync->parent[queue[head]]]] = queue[head];

          dync->pos_in_childpar[dync->children[dync->parent[queue[head]]][dync->pos_in_childpar[queue[head]]]]=dync->pos_in_childpar[queue[head]];
                
          dync->pos_in_childpar[queue[head]]=info->nb_child_cforced[dync->parent[queue[head]]];
          info->nb_child_cforced[dync->parent[queue[head]]] ++;
        }

      }


      if (!is_leaf(queue[head],dync)) {  // leaves that we encounter in the search are always full
      
        if (info->nb_leaves_touched[queue[head]] < dync->nb_leaves[queue[head]])
          info->nb_child_nf[dync->parent[queue[head]]] ++;
      }

      if (is_leaf(queue[head],dync)) nblt=1; else nblt=info->nb_leaves_touched[queue[head]];      
      info->nb_leaves_touched[dync->parent[queue[head]]] += nblt;

    }

    head++;
    //fprintf(stderr,"Head: %d, contenu: %d\n",head,queue[head]); fflush(stderr);

  }



  gather_full_ite(debug, fbug, dync, x, iter_debut_check, info);


  if (queue!=NULL) free(queue);

}

////////////////////////////////////////////////////////////////////////
////////// CLEAR ADDITIONAL INFO PREVIOUSLY ASSIGNED FOR INSERTION OF X IN THE GENERAL EDITION ALGORITHM
//----------------------------------------------------------------------
// IN  : dync: the dynamic cotree
// IN/OUT : info : the supinfo to be cleared
// OUT :
// RETURN : 
//----------------------------------------------------------------------
// PREREQUISITE : the root is not a leaf
////////////////////////////////////////////////////////////////////////
// IMPORTANT NOTE: TO KNOW IF A NODE IS FORCED, CHECK WHETHER ITS POSITION IN THE CHILDREN OF ITS PARENT IS LESS THAN THE NUMBER OF FORCED NODE OF ITS PARENT, SAME FOR NON HOLLOW : PB for the root...

//debug
void clear_supinfo_edit(int debug, FILE * fbug, int x, supinfo_edit * info, dyncotree * dync) {


  int nb,i;

  int * queue;
  int head, tail;
  int node;

  // for no warning at compil
  if ((debug==1)&&(x>=2000000000)) fprintf(fbug,"\n");


  if( (queue=(int *)malloc((dync->n)*sizeof(int))) == NULL )
    report_error("gather_full_ite: malloc() error");

  queue[0]=dync->root;
  head=0;
  tail=1;

  while (head!=tail) {

    node=queue[head];

    nb = info->nb_child_nh[node];
    info->nb_child_nh[node]=0;
    info->nb_child_nf[node]=0;
    info->nb_child_cforced[node]=0;
    info->nb_child_dforced[node]=0;
    info->nb_leaves_touched[node]=0;
    info->nb_child_info[node]=0;

    for (i=0;i<nb;i++) {
      //debug
      if (! is_leaf(dync->children[node][i],dync)) {
        queue[tail]=dync->children[node][i];
        tail++;
      }
    }

    head++;

  }

  if (queue!=NULL) free(queue);

}



////////////////////////////////////////////////////////////////////////
/////////////   FREE SPACE OCCUPIED BY SUPINFO   ///////////////////////
//----------------------------------------------------------------------
// IN  :
// IN/OUT : info : the supinfo to be freed
// OUT :
// RETURN : 
//----------------------------------------------------------------------
// PREREQUISITE :
////////////////////////////////////////////////////////////////////////

void free_supinfo_edit(supinfo_edit * info) {

  if ((info)!=NULL) {
   
    if ((info->nb_child_nh)!=NULL)
      free(info->nb_child_nh);
    if ((info->nb_child_nf)!=NULL)
      free(info->nb_child_nf);
    if ((info->nb_child_cforced)!=NULL)
      free(info->nb_child_cforced);
    if ((info->nb_child_dforced)!=NULL)
      free(info->nb_child_dforced);
    if ((info->nb_leaves_touched)!=NULL)
      free(info->nb_leaves_touched);
    if ((info->nb_child_info)!=NULL)
      free(info->nb_child_info);

    free(info);

  }

}




////////////////////////////////////////////////////////////////////////
////////// COMPLEMENT BOTH THE COTREE AND THE INFORMATION ASSOCIATED TO ITS NODES (RELATIVELY TO THE COMPLEMENTED NEIGHBOURHOOD OF THE INCOMING VERTEX)
//----------------------------------------------------------------------
// IN  :
// IN/OUT : dync, info
// OUT :
// RETURN : 
//----------------------------------------------------------------------
// PREREQUISITE : the root is not a leaf
////////////////////////////////////////////////////////////////////////
//


//void complement_cot_info(int sens, dyncotree* dync, supinfo_edit* info) {
void complement_cot_info(dyncotree* dync, supinfo_edit* info) {


  int temp,i;
  

  int * queue;
  int head, tail;
  int node;

  if( (queue=(int *)malloc((dync->nt)*sizeof(int))) == NULL )
    report_error("gather_full_ite: malloc() error");

  queue[0]=dync->root;
  head=0;
  tail=1;

  while (head!=tail) {

    node=queue[head];


    dync->label[node] = 1-dync->label[node];


    temp = info->nb_child_nh[node];
    info->nb_child_nh[node]=info->nb_child_nf[node];
    info->nb_child_nf[node]=temp;
    
    temp=info->nb_child_cforced[node];
    info->nb_child_cforced[node]=info->nb_child_dforced[node];
    info->nb_child_dforced[node]=temp;

    info->nb_leaves_touched[node]=dync->nb_leaves[node]-info->nb_leaves_touched[node];

    for (i=0;i<dync->nb_child[node]/2;i++) {
      temp=dync->children[node][i];
      dync->children[node][i]=dync->children[node][dync->nb_child[node]-i-1];
      dync->children[node][dync->nb_child[node]-i-1]=temp;

      dync->pos_in_childpar[dync->children[node][i]]=i;
      dync->pos_in_childpar[dync->children[node][dync->nb_child[node]-i-1]]=dync->nb_child[node]-i-1;
    }

    // for formerly hollow children, became full after complement
    for (i=0;i<dync->nb_child[node]-info->nb_child_nf[node];i++) {
      if (! is_leaf(dync->children[node][i],dync)) {
        info->nb_leaves_touched[dync->children[node][i]]=dync->nb_leaves[dync->children[node][i]];
        dync->label[dync->children[node][i]] = 1-dync->label[dync->children[node][i]];
      }
    }

    // for formerly full children, became hollow after complement
    for (i=info->nb_child_nh[node];i<dync->nb_child[node];i++) {
      if (! is_leaf(dync->children[node][i],dync)) {
        info->nb_leaves_touched[dync->children[node][i]]=0;
        dync->label[dync->children[node][i]] = 1-dync->label[dync->children[node][i]];
      }
    }


    // for non-full and non-hollow children
    for (i=dync->nb_child[node]-info->nb_child_nf[node];i<info->nb_child_nh[node];i++) {
      if (! is_leaf(dync->children[node][i],dync)) {
        queue[tail]=dync->children[node][i];
        tail++;
      }
    }

    head++;

  }
  
  if (queue!=NULL) free(queue);

}





///////////////////////////// UTILITY FUNCTION ////////////////////////


int cost_completion(int node, dyncotree *dync, supinfo_edit *info) {
    if (is_leaf(node,dync)) {if (dync->pos_in_childpar[node] < info->nb_child_nh[dync->parent[node]]) return 0; else return 1;}
    else return (dync->nb_leaves[node]-info->nb_leaves_touched[node]);
  }


/////////////////////////////////////////////////////////////////////////////////////
// LIST ALL MINIMUM INSERTION NODES OF A DYNAMIC COTREE WITH A SUPINFO
// IN : 
// OUT : 
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE : 
/////////////////////////////////////////////////////////////////////////////////////

void list_minimum_insertion_nodes (dyncotree *dync, supinfo_edit *info, int *list_min, int *nb_min, int *min_cost) {
  //prerequisite: the root is not hollow

  int local_cost;
  int i;

  int * queue;
  int * queue_cost;
  int head, tail;
  int node;
  int cost_above;




  if (info->nb_child_nh[dync->root]==0) {
    *min_cost=0; list_min[0]=dync->root; *nb_min=1;
  }

  else if (is_cforced(dync->root, dync, info)) {
    *min_cost=dync->nl-info->nb_leaves_touched[dync->root]; list_min[0]=dync->root; *nb_min=1;
  }

  else { // ensures that the root is non-forced and non-hollow
    *min_cost=(dync->nl-info->nb_leaves_touched[dync->root])+1;
    //rec_list_min(dync->root, 0); // start the search only if the root is non-forced

    if( (queue=(int *)malloc((dync->nt)*sizeof(int))) == NULL )
      report_error("gather_full_ite: malloc() error");
    if( (queue_cost=(int *)malloc((dync->nt)*sizeof(int))) == NULL )
      report_error("gather_full_ite: malloc() error");

    queue[0]=dync->root;
    queue_cost[0]=0;
    head=0;
    tail=1;

    while (head!=tail) {
  
      node=queue[head];
      cost_above=queue_cost[head];

      // when it is a leaf: do nothing! Because the insertion node is never a leaf.


      if (dync->label[node]==1) {
        if (info->nb_child_nh[node]<dync->nb_child[node]) {  // ensures that nb of hollow children is >0
          local_cost=0;
          for (i=0;i<info->nb_child_nh[node];i++) local_cost += cost_completion(dync->children[node][i], dync, info);
          if (local_cost+cost_above < *min_cost) {*min_cost=local_cost+cost_above; *nb_min=1; list_min[0]=node;}
          else if (local_cost+cost_above==*min_cost) {list_min[*nb_min]=node; (*nb_min)++;}
        }

        for (i=info->nb_child_cforced[node];i<info->nb_child_nh[node];i++) {  // search only non-forced children that are non-hollow
          //if (! is_leaf(dync->children[node][i],dync)) { // security that should be unuseful from the conditions above
            queue[tail]=dync->children[node][i]; 
            queue_cost[tail]=cost_above + dync->nb_leaves[node] - info->nb_leaves_touched[node] - dync->nb_leaves[dync->children[node][i]] + info->nb_leaves_touched[dync->children[node][i]];
            tail++;
          //}
        }
      }

      if (dync->label[node]==0) {
        if ( (info->nb_child_nh[node]>1) || ((info->nb_child_nh[node]==1) && (info->nb_child_cforced[node]==1)) )  {
          local_cost=0;
          for (i=0;i<info->nb_child_nh[node];i++) local_cost += cost_completion(dync->children[node][i], dync, info);
          if (local_cost+cost_above < *min_cost) {*min_cost=local_cost+cost_above; *nb_min=1; list_min[0]=node;}
          else if (local_cost+cost_above==*min_cost) {list_min[*nb_min]=node; (*nb_min)++;}
        }
        else if ((info->nb_child_nh[node]==1) && (info->nb_child_cforced[node]==0)) { // search only the unique non-hollow child, which is non-forced
          //if (! is_leaf(dync->children[node][i],dync)) { // security that should be unuseful from the conditions above
            queue[tail]=dync->children[node][0];
            queue_cost[tail]=cost_above; 
            tail++;
          //}
        }
      }

      head++;

    }

    if (queue!=NULL) free(queue);
    if (queue_cost!=NULL) free(queue_cost); 
   
  }

}





/////////////////////////////////////////////////////////////////////////////////////
// LIST ALL MINIMUM EDITIONS OF A DYNAMIC COTREE WITH A SUPINFO
// IN : 
// OUT : 
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE : 
/////////////////////////////////////////////////////////////////////////////////////


/////////////////////////// UTILITY FUNCTIONS //////////////////////////////////////

int is_fillable (int node, dyncotree *dync, supinfo_edit *info) {
  return ((dync->nb_leaves[node]-info->nb_leaves_touched[node]) <= info->nb_leaves_touched[node]);
}


int is_emptiable (int node, dyncotree *dync, supinfo_edit *info) {
  return ((dync->nb_leaves[node]-info->nb_leaves_touched[node]) >= info->nb_leaves_touched[node]);
}


int cost_edition(int node, dyncotree *dync, supinfo_edit *info) {
  if (is_leaf(node,dync)) return 0;
  else if (is_fillable(node, dync, info))  return (dync->nb_leaves[node]-info->nb_leaves_touched[node]);
  else return info->nb_leaves_touched[node];
}


/// BUG : y a un problème dans l'affectation initiale de nb_min_edit...
//debug
void list_minimum_editions (int debug, int x, FILE * fbug, dyncotree *dync, supinfo_edit *info, int *list_min, int * list_nb_filled, int * list_nb_emptied, int *nb_min_node, unsigned long *nb_min_edit, int *min_cost) {
  //prerequisite: the root is not hollow

  // for no warning at compil
  if ((debug==1)&&(x>=2000000000)) fprintf(fbug,"\n");


  int i,temp;
  int nb_filled, nb_emptied;

  int local_cost;
  unsigned long local_nb_edit;
  int cost_dive=0; // value ot important, just to avoid warnings

  int * queue;
  int * queue_cost;
  int head, tail;
  int node;
  int cost_above;


 // BODY OF "list_minimum_editions"
  if (info->nb_child_nh[dync->root]==0) {
    *min_cost=0; list_min[0]=dync->root; *nb_min_node=1; *nb_min_edit=1; list_nb_filled[0]=0; list_nb_emptied[0]=dync->nb_child[dync->root];
  }

  else if (info->nb_child_nf[dync->root]==0) {
    *min_cost=0; list_min[0]=dync->root; *nb_min_node=1; *nb_min_edit=1; list_nb_filled[0]=dync->nb_child[dync->root]; list_nb_emptied[0]=0;
  }

  else { // ensures that the root is mixed
    *min_cost=(info->nb_leaves_touched[dync->root])+1;
    
    if( (queue=(int *)malloc((dync->nt)*sizeof(int))) == NULL )
      report_error("gather_full_ite: malloc() error");
    if( (queue_cost=(int *)malloc((dync->nt)*sizeof(int))) == NULL )
      report_error("gather_full_ite: malloc() error");

    queue[0]=dync->root;
    queue_cost[0]=0;
    head=0;
    tail=1;

    while (head!=tail) {
  
      node=queue[head];
      cost_above=queue_cost[head];

    // when it is a leaf: do nothing! Because the insertion node is never a leaf.
    //if (!is_leaf(node,dync)) {
    // anyway, node is guaranteed not to be a leaf at the moment we enqueue.

      nb_filled=dync->nb_child[node]-info->nb_child_nf[node];
      for (i=dync->nb_child[node]-info->nb_child_nf[node]; i<info->nb_child_nh[node]; i++) {
        if (is_fillable(dync->children[node][i], dync, info) && !is_emptiable(dync->children[node][i], dync, info)) {
          temp = dync->children[node][nb_filled];
          dync->children[node][nb_filled] = dync->children[node][i];
          dync->children[node][i] = temp;

          dync->pos_in_childpar[dync->children[node][nb_filled]]=nb_filled;
          dync->pos_in_childpar[dync->children[node][i]]=i;
          
          nb_filled++;
        }
      }

      nb_emptied=dync->nb_child[node]-info->nb_child_nh[node];
      for (i=info->nb_child_nh[node]-1; i>=nb_filled; i--) {
        if (is_emptiable(dync->children[node][i], dync, info) && !is_fillable(dync->children[node][i], dync, info)) {
          temp = dync->children[node][dync->nb_child[node]-nb_emptied-1];
          dync->children[node][dync->nb_child[node]-nb_emptied-1] = dync->children[node][i];
          dync->children[node][i] = temp;

          dync->pos_in_childpar[dync->children[node][dync->nb_child[node]-nb_emptied-1]]=dync->nb_child[node]-nb_emptied-1;
          dync->pos_in_childpar[dync->children[node][i]]=i;

          nb_emptied++;
        }
      }


      // if the minimum cost local edition is indeed settled at "node", consider it
      if ((node==dync->root) || ((nb_filled<dync->nb_child[node]) && (nb_emptied<dync->nb_child[node]))) {

        local_cost=0;
        for (i=dync->nb_child[node]-info->nb_child_nf[node]; i<info->nb_child_nh[node]; i++) {
          local_cost += cost_edition(dync->children[node][i], dync, info);
        }

        local_nb_edit=1;

        if ((nb_filled+nb_emptied)<dync->nb_child[node]) {
          for(i=nb_filled; i<dync->nb_child[node]-nb_emptied; i++) {
            local_nb_edit *= 2;
          }
          if (node!=dync->root){
            if (nb_filled==0) local_nb_edit--;
            if (nb_emptied==0) local_nb_edit--;
          }
        }

        if (local_cost+cost_above < *min_cost) {
          *min_cost=local_cost+cost_above;
          *nb_min_node=1;
          *nb_min_edit=local_nb_edit;
          list_min[0]=node;
          list_nb_filled[0]=nb_filled;
          list_nb_emptied[0]=nb_emptied;
        }

        else if (local_cost+cost_above==*min_cost) {
          list_min[*nb_min_node]=node;
          list_nb_filled[*nb_min_node]=nb_filled;
          list_nb_emptied[*nb_min_node]=nb_emptied;
          (*nb_min_node)++;
          *nb_min_edit += local_nb_edit;
        }

      }


      // dive into all children of "node" that may improve the minimum cost
      for(i=dync->nb_child[node]-info->nb_child_nf[node]; i<info->nb_child_nh[node]; i++) {  // search only non-full children that are non-hollow

        if (dync->label[node]==0) {
          cost_dive=cost_above + info->nb_leaves_touched[node] - info->nb_leaves_touched[dync->children[node][i]];
        }
        else if (dync->label[node]==1) {
          cost_dive=cost_above + (dync->nb_leaves[node]-info->nb_leaves_touched[node]) - (dync->nb_leaves[dync->children[node][i]]-info->nb_leaves_touched[dync->children[node][i]]);
        }
        
        if ((cost_dive <= *min_cost) && (!is_leaf(dync->children[node][i],dync))) {
          queue[tail]=dync->children[node][i];
          queue_cost[tail]=cost_dive;
          tail++;
        }

      }

      head++;

    } //end while

    if (queue!=NULL) free(queue);
    if (queue_cost!=NULL) free(queue_cost); 

  }  //end else

} // end procedure "list_minimum_editions"




/////////////////////////////////////////////////////////////////////////////////////
// PRINT TO A FILE THE LIST OF EDITS AT ONE INCREMENTAL STEP
// IN : list_min_node, list_nb_filled, list_nb_emptied, nb_min_node, nb_min_edit
// OUT : c_node, nb_child_tobefilled
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE : (j'ai l'impression que ça marche dans tous les cas) the insertion node has both non-hollow children and hollow children
/////////////////////////////////////////////////////////////////////////////////////



void choose_min_edition(dyncotree * dync, int * list_min_node, int * list_nb_filled, int * list_nb_emptied, int nb_min_node, unsigned long nb_min_edit, int * c_node, int * nb_child_tobefilled) {
  if ((nb_min_node==0) || (list_min_node==NULL) || (list_nb_filled==NULL) || (list_nb_emptied==NULL))
	report_error("choose_min_edition: empty list.");
// || (nb_min_edit==0) : withdraw cause not used
  // ususeful, only for no warning:
  if (nb_min_edit==0) nb_min_edit=0;

  int temp;
  int i;
  int * res_tirage=NULL;
  int valid_tirage;
  int nb_pos, nb_neg;
  int c_index;
  int nb_tbf;

  c_index=rand_imp(nb_min_node); // randomly choose an insertion node

  *c_node=list_min_node[c_index];
  *nb_child_tobefilled=list_nb_filled[c_index];

  if (dync->nb_child[*c_node] > list_nb_filled[c_index]+list_nb_emptied[c_index]) {

    if ( (res_tirage=(int *)malloc((dync->nb_child[*c_node])*sizeof(int))) == NULL )
      report_error("choose_min_edition: malloc() error");
  
    if (dync->nb_child[*c_node]==(list_nb_filled[c_index]+1)) {res_tirage[list_nb_filled[c_index]]=0; nb_pos=0; nb_neg=1;}

    else if (dync->nb_child[*c_node]==(list_nb_emptied[c_index]+1)) {res_tirage[list_nb_emptied[c_index]]=1; nb_pos=1; nb_neg=0;}

    else {
    valid_tirage=0;
    while (valid_tirage==0) {
      nb_pos=0;
      nb_neg=0;
      for (i=list_nb_filled[c_index]; i<dync->nb_child[*c_node]-list_nb_emptied[c_index]; i++) {

        res_tirage[i]=rand_imp(2);
        
        if (res_tirage[i]==0) nb_neg++; else nb_pos++;
      }
      if ((*c_node!=dync->root) && (((list_nb_emptied[c_index]+nb_neg)==0) || ((list_nb_filled[c_index]+nb_pos)==0) )) valid_tirage=0;
      else valid_tirage=1;
    }
    }

    *nb_child_tobefilled += nb_pos;

    nb_tbf=list_nb_filled[c_index];
    for (i=list_nb_filled[c_index]; i<dync->nb_child[*c_node]-list_nb_emptied[c_index]; i++) {
      if (res_tirage[i]==1) {
        temp = dync->children[*c_node][nb_tbf];
        dync->children[*c_node][nb_tbf] = dync->children[*c_node][i];
        dync->children[*c_node][i] = temp;

        dync->pos_in_childpar[dync->children[*c_node][nb_tbf]]=nb_tbf;
        dync->pos_in_childpar[dync->children[*c_node][i]]=i;

        nb_tbf++;
      }
    }


    if (res_tirage!=NULL) free(res_tirage);

  }

}




/////////////////////////////////////////////////////////////////////////////////////
// COMPUTE THE NUMBER OF ADDS AND DELS AT ONE INCREMENTAL STEP
// IN : dync,info,insert_node, nb_child_tobefilled
// OUT : nb_add, nb_del
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE : (j'ai l'impression que ça marche dans tous les cas) the insertion node has both non-hollow children and hollow children
/////////////////////////////////////////////////////////////////////////////////////


void compute_del_add(dyncotree* dync, supinfo_edit* info, int insert_node, int nb_child_tobefilled, int * nb_add, int * nb_del) {

  int i;
  int node, old_node;
  
  *nb_add=0;
  *nb_del=0;

  node=insert_node;

  // edits in children of the insertion node 
  for (i=dync->nb_child[node]-info->nb_child_nf[node]; i < nb_child_tobefilled; i++) {
    *nb_add += dync->nb_leaves[dync->children[node][i]]-info->nb_leaves_touched[dync->children[node][i]];
  }

  for (i=nb_child_tobefilled; i < info->nb_child_nh[node]; i++) {
    *nb_del += info->nb_leaves_touched[dync->children[node][i]];
  }


  // edits pending from ancestors of the insertion node
  while (node!=dync->root) {

    old_node=node;
    node=dync->parent[node];

    if (dync->label[node]==1) {
      for (i=0;i<dync->nb_child[node];i++) {
        if (dync->children[node][i] != old_node) {
          if (is_leaf(dync->children[node][i],dync)) {
            if (dync->pos_in_childpar[dync->children[node][i]] >= info->nb_child_nh[dync->parent[dync->children[node][i]]]) (*nb_add)++;
          }
          else {
            *nb_add += dync->nb_leaves[dync->children[node][i]]-info->nb_leaves_touched[dync->children[node][i]];
          }
        }
      }
    }

    if (dync->label[node]==0) {
      for (i=0;i<dync->nb_child[node];i++) {
        if (dync->children[node][i] != old_node) {
          if (is_leaf(dync->children[node][i],dync)) {
            if (dync->pos_in_childpar[dync->children[node][i]] < info->nb_child_nh[dync->parent[dync->children[node][i]]]) (*nb_del)++;
          }
          else {
            *nb_del += info->nb_leaves_touched[dync->children[node][i]];
          }
        }
      }
    }

  }

}





/////////////////////////////////////////////////////////////////////////////////////
// PRINT TO A FILE THE LIST OF EDITS AT ONE INCREMENTAL STEP
// IN : dync,node,info,x
// OUT : 
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE : (j'ai l'impression que ça marche dans tous les cas) the insertion node has both non-hollow children and hollow children
/////////////////////////////////////////////////////////////////////////////////////


void print_edits(FILE* f, dyncotree* dync, int node, int nb_child_tobefilled, supinfo_edit* info, sgraph* g, int x, int * nb_add, int * nb_del, int output_modifs) {


  void print_all(int u) {
  // prerequisite : node is not a leaf
    int i;
 

    if (is_leaf(u,dync)) {if (output_modifs==1) fprintf(f,"%d %d\n",g->permu[x],g->permu[u-dync->n]);}
    else {
      for (i=0;i<dync->nb_child[u];i++) {
        print_all(dync->children[u][i]);
      }
    }
  }


  void print_added(int u) {
  // prerequisite : node is not a leaf
    int i;

    if (is_leaf(u,dync)) {
      if (dync->pos_in_childpar[u] >= info->nb_child_nh[dync->parent[u]]) if (output_modifs==1) fprintf(f,"%d %d\n",g->permu[x],g->permu[u-dync->n]);
    }
    else {
      for (i=0;i<dync->nb_child[u];i++) {
        if (is_leaf(dync->children[u][i],dync)) print_added(dync->children[u][i]);
        else {
          if (info->nb_leaves_touched[dync->children[u][i]]==0) print_all(dync->children[u][i]);
          else if (info->nb_leaves_touched[dync->children[u][i]] < dync->nb_leaves[dync->children[u][i]]) print_added(dync->children[u][i]);
        }
      }
    }
  }


    void print_deleted(int u) { 
  // prerequisite : node is not a leaf
    int i;

    if (is_leaf(u,dync)) {
      if (dync->pos_in_childpar[u] < info->nb_child_nh[dync->parent[u]]) if (output_modifs==1) fprintf(f,"%d %d\n",g->permu[x],g->permu[u-dync->n]);
    }
    else {
      for (i=0;i<dync->nb_child[u];i++) {
        if (is_leaf(dync->children[u][i],dync)) print_deleted(dync->children[u][i]);
        else {
          if (info->nb_leaves_touched[dync->children[u][i]]==dync->nb_leaves[dync->children[u][i]]) print_all(dync->children[u][i]);
          else if (info->nb_leaves_touched[dync->children[u][i]] < dync->nb_leaves[dync->children[u][i]]) print_deleted(dync->children[u][i]);
        }
      }
    }
  }



  
  int i;
  int old_node;
  *nb_add=0;
  *nb_del=0;

  // edits in children of the insertion node 
  for (i=dync->nb_child[node]-info->nb_child_nf[node]; i < nb_child_tobefilled; i++) {
    print_added(dync->children[node][i]);
    *nb_add += dync->nb_leaves[dync->children[node][i]]-info->nb_leaves_touched[dync->children[node][i]];
  }

  for (i=nb_child_tobefilled; i < info->nb_child_nh[node]; i++) {
    print_deleted(dync->children[node][i]);
    *nb_del += info->nb_leaves_touched[dync->children[node][i]];
  }


  // edits pending from ancestors of the insertion node
  while (node!=dync->root) {

    old_node=node;
    node=dync->parent[node];

    if (dync->label[node]==1) {
      for (i=0;i<dync->nb_child[node];i++) {
        if (dync->children[node][i] != old_node) {
          if (is_leaf(dync->children[node][i],dync)) {
            print_added(dync->children[node][i]);
            if (dync->pos_in_childpar[dync->children[node][i]] >= info->nb_child_nh[dync->parent[dync->children[node][i]]]) (*nb_add)++;
          }
          else {
            if (info->nb_leaves_touched[dync->children[node][i]]==0) {
              print_all(dync->children[node][i]);
              *nb_add += dync->nb_leaves[dync->children[node][i]];
            }
            else if (info->nb_leaves_touched[dync->children[node][i]] < dync->nb_leaves[dync->children[node][i]]) {
              print_added(dync->children[node][i]);
              *nb_add += dync->nb_leaves[dync->children[node][i]]-info->nb_leaves_touched[dync->children[node][i]];
            }
          }
        }
      }
    }

    if (dync->label[node]==0) {
      for (i=0;i<dync->nb_child[node];i++) {
        if (dync->children[node][i] != old_node) {
          if (is_leaf(dync->children[node][i],dync)) {
            print_deleted(dync->children[node][i]);
            if (dync->pos_in_childpar[dync->children[node][i]] < info->nb_child_nh[dync->parent[dync->children[node][i]]]) (*nb_del)++;
          }
          else {
            if (info->nb_leaves_touched[dync->children[node][i]]==dync->nb_leaves[dync->children[node][i]]) {
              print_all(dync->children[node][i]);
              *nb_del += dync->nb_leaves[dync->children[node][i]];
            }
            else if (info->nb_leaves_touched[dync->children[node][i]] >0) {
              print_deleted(dync->children[node][i]);
              *nb_del += info->nb_leaves_touched[dync->children[node][i]];
            }
          }
        }
      }
    }

  }

  fflush(f);

}






/////////////////////////////////////////////////////////////////////////////////////
// PRINT TO A FILE THE LIST OF FILL EDGES AT ONE INCREMENTAL STEP
// IN : dync,node,info,x
// OUT : 
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE : (j'ai l'impression que ça marche dans tous les cas) the insertion node has both non-hollow children and hollow children
/////////////////////////////////////////////////////////////////////////////////////


void print_added_edges(FILE* f, dyncotree* dync, int node, supinfo_edit* info, sgraph* g, int x) {


  void print_all_hollow(int u) {
  // prerequisite : node is not a leaf
    int i;
 

    if (is_leaf(u,dync)) fprintf(f,"%d %d\n",g->permu[x],g->permu[u-dync->n]);
    else {
      for (i=0;i<dync->nb_child[u];i++) {
        print_all_hollow(dync->children[u][i]);
      }
    }
  }


  void print_all_mixed(int u) {
  // prerequisite : node is not a leaf
    int i;

    if (is_leaf(u,dync)) {
      if (dync->pos_in_childpar[u] >= info->nb_child_nh[dync->parent[u]]) fprintf(f,"%d %d\n",g->permu[x],g->permu[u-dync->n]);
    }
    else {
      for (i=0;i<dync->nb_child[u];i++) {
        if (is_leaf(dync->children[u][i],dync)) print_all_mixed(dync->children[u][i]);
        else {
          if (info->nb_leaves_touched[dync->children[u][i]]==0) print_all_hollow(dync->children[u][i]);
          else if (info->nb_leaves_touched[dync->children[u][i]] < dync->nb_leaves[dync->children[u][i]]) print_all_mixed(dync->children[u][i]);
        }
      }
    }
  }

  
  int i;
  int old_node;

  for (i=0;i < info->nb_child_nh[node];i++) {
    if (info->nb_leaves_touched[dync->children[node][i]] < dync->nb_leaves[dync->children[node][i]]) print_all_mixed(dync->children[node][i]);
  }


  while (node!=dync->root) {

    old_node=node;
    node=dync->parent[node];
    if (dync->label[node]==1) {
      for (i=0;i<dync->nb_child[node];i++) {
        if (dync->children[node][i] != old_node) {
          if (is_leaf(dync->children[node][i],dync)) print_all_mixed(dync->children[node][i]);
          else {
            if (info->nb_leaves_touched[dync->children[node][i]]==0) print_all_hollow(dync->children[node][i]);
            else if (info->nb_leaves_touched[dync->children[node][i]] < dync->nb_leaves[dync->children[node][i]]) print_all_mixed(dync->children[node][i]);
          }
        } 
      }
    }
  }

  fflush(f);

}






/////////////////////////////////////////////////////////////////////////////////////
// UPDATE THE DYNCOTREE UNDER THE INSERTION OF ONE VERTEX
// IN : insnode: the chosen minimum insertion node, x: identifiant of the leaves to be inserted at this incremental step
// IN/OUT : dync: the current dyncotree to be updated 
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE : insnode is not a leaf and has >0 non-hollow children and >0 hollow children
/////////////////////////////////////////////////////////////////////////////////////

//debug
void update_under_insert(int debug, FILE * fbug, int x, dyncotree* dync, int insnode, int nb_tobefilled) {
  int* temp_children;
  int new_x;
  int u_x, u_nh;
  int nb_leaves_nh;
  int nb_h;
  int uniq_node;
  int i;
  //int j;
  int p;

  // for no warning at compil
  if ((debug==1)&&(x>=2000000000)) fprintf(fbug,"\n");


  new_x=dync->n + dync->nl;
  //dync->ident[new_x]=x;
  (dync->nl)++;


  if ( (insnode==dync->root) && ( (nb_tobefilled==0) || (nb_tobefilled==dync->nb_child[dync->root]) ) ) {



    if ( ( (nb_tobefilled==0) && (dync->label[dync->root]==0) ) || ( (nb_tobefilled==dync->nb_child[dync->root]) && (dync->label[dync->root]==1) ) ) {
      int * temp_children;
      if ( (temp_children=(int *)malloc((dync->nb_child[dync->root]+1)*sizeof(int))) == NULL )
        report_error("main: malloc() error");
      for (i=0;i<dync->nb_child[dync->root];i++)
        temp_children[i]=dync->children[dync->root][i];
      temp_children[i]=new_x;
      free(dync->children[dync->root]);
      copy_time += dync->nb_child[dync->root];
      tab_expansion ++;
      dync->children[dync->root]=temp_children;
      dync->nb_child[dync->root]++;
      dync->parent[new_x]=dync->root;
      dync->pos_in_childpar[new_x]=dync->nb_child[dync->root]-1;
      dync->nb_leaves[dync->root]++;
    }

    else {  //
      int new_root=dync->nt;
      dync->nt++;
      dync->label[new_root]= 1-dync->label[dync->root]; // the label of the new_root is the complement of the one of the old root
      dync->parent[new_root]=-1;
      dync->pos_in_childpar[new_root]=-1;
      dync->nb_child[new_root]=2;
      dync->nb_leaves[new_root]=dync->nb_leaves[dync->root]+1;  // we count the contribution of x separately, later
      if ( (dync->children[new_root]=(int *)malloc(2*sizeof(int))) == NULL )
        report_error("main: malloc() error");

      dync->children[new_root][0]=dync->root;
      dync->parent[dync->root]=new_root;
      dync->pos_in_childpar[dync->root]=0;
      dync->children[new_root][1]=new_x;
      dync->parent[new_x]=new_root;
      dync->pos_in_childpar[new_x]=1;
        
      dync->root=new_root;
    }

  }


  else {

    if (dync->label[insnode] == 1) {


      if (nb_tobefilled==(dync->nb_child[insnode]-1)) {


        uniq_node=dync->children[insnode][dync->nb_child[insnode]-1];

        if (is_leaf(uniq_node, dync)) {

          u_x=dync->nt;
          dync->nt++;
          dync->label[u_x]=0;
          dync->parent[u_x]=insnode;
          dync->children[insnode][dync->pos_in_childpar[uniq_node]]=u_x;
          dync->pos_in_childpar[u_x]=dync->pos_in_childpar[uniq_node];
          if ( (dync->children[u_x]=(int *)malloc(2*sizeof(int))) == NULL )
            report_error("update_under_insert: malloc() error");
          dync->children[u_x][0]=uniq_node;
          dync->parent[uniq_node]=u_x;
          dync->pos_in_childpar[uniq_node]=0;
          dync->children[u_x][1]=new_x;
          dync->parent[new_x]=u_x;
          dync->pos_in_childpar[new_x]=1;
          dync->nb_child[u_x]=2;
          dync->nb_leaves[u_x]=1;  // we count the contribution of x separately, later
        }

        else {


          if ( (temp_children=(int *)malloc((dync->nb_child[uniq_node]+1)*sizeof(int))) == NULL )
            report_error("update_under_insert: malloc() error");
          for (i=0;i<dync->nb_child[uniq_node];i++)
            temp_children[i]=dync->children[uniq_node][i];
          temp_children[i]=new_x;
          free(dync->children[uniq_node]);
          copy_time += dync->nb_child[uniq_node];
          tab_expansion ++;
          dync->children[uniq_node]=temp_children;
          dync->nb_child[uniq_node]++;
          dync->parent[new_x]=uniq_node;
          dync->pos_in_childpar[new_x]=dync->nb_child[uniq_node]-1;
        }  
      }

      else {


        u_x=dync->nt;
        u_nh=dync->nt+1;
        //dync->ident[u_x]=dync->n+dync->nt;
        //dync->ident[u_nh]=dync->n+dync->nt+1;
        dync->nt += 2;


        dync->label[u_nh]=1;
        if ( (dync->children[u_nh]=(int *)malloc((nb_tobefilled+1)*sizeof(int))) == NULL )
          report_error("update_under_insert: malloc() error");
        dync->children[u_nh][0]=u_x;
        for (i=0;i<nb_tobefilled;i++) {
          dync->children[u_nh][i+1]=dync->children[insnode][i];
          dync->parent[dync->children[insnode][i]]=u_nh;
          dync->pos_in_childpar[dync->children[insnode][i]]=i+1;
        }
        dync->nb_child[u_nh]=nb_tobefilled+1;
        dync->nb_leaves[u_nh]=dync->nb_leaves[insnode];  // we count the contribution of x separately, later
        dync->parent[u_nh]=dync->parent[insnode];
        dync->pos_in_childpar[u_nh]=dync->pos_in_childpar[insnode];
        if (insnode != dync->root) {
          dync->children[dync->parent[insnode]][dync->pos_in_childpar[insnode]]=u_nh;
        }
        else {
          dync->root=u_nh;
        }

        dync->label[u_x]=0;
        if ( (dync->children[u_x]=(int *)malloc(2*sizeof(int))) == NULL )
          report_error("update_under_insert: malloc() error");
        dync->children[u_x][0]=insnode;
        dync->children[u_x][1]=new_x;
        dync->parent[new_x]=u_x;
        dync->pos_in_childpar[new_x]=1;
        dync->nb_child[u_x]=2;
        nb_leaves_nh=0;
        for (i=0;i<nb_tobefilled;i++) {
          if (is_leaf(dync->children[insnode][i],dync)) nb_leaves_nh++;
          else nb_leaves_nh += dync->nb_leaves[dync->children[insnode][i]];
        }
        dync->nb_leaves[u_x]=dync->nb_leaves[insnode]-nb_leaves_nh;  // we count the contribution of x separately, later
        dync->parent[u_x]=u_nh;
        dync->pos_in_childpar[u_x]=0;

        if (nb_tobefilled < dync->nb_child[insnode]-nb_tobefilled) {
          for (i=0;i<nb_tobefilled;i++) {
            dync->children[insnode][i]=dync->children[insnode][dync->nb_child[insnode]-1-i];
            dync->pos_in_childpar[dync->children[insnode][i]]=i;
          }
        }
        else {
          for (i=nb_tobefilled;i<dync->nb_child[insnode];i++) {
            dync->children[insnode][i-nb_tobefilled]=dync->children[insnode][i];
            dync->pos_in_childpar[dync->children[insnode][i-nb_tobefilled]]=i-nb_tobefilled;
          }          
        }

        dync->nb_child[insnode]=dync->nb_child[insnode]-nb_tobefilled; // the list of children is truncated but the space is not freed...
        lost_space += nb_tobefilled;
        tab_truncated ++;
        dync->nb_leaves[insnode]=dync->nb_leaves[u_x];  // we count the contribution of x separately, later
        dync->parent[insnode]=u_x;
        dync->pos_in_childpar[insnode]=0;


      }

    }



    if (dync->label[insnode]==0) {


      if (nb_tobefilled==1) {


        uniq_node=dync->children[insnode][0];

        if (is_leaf(uniq_node, dync)) {

          u_x=dync->nt;
          dync->nt++;
          dync->label[u_x]=1;
          dync->parent[u_x]=insnode;

          dync->children[insnode][dync->pos_in_childpar[uniq_node]]=u_x;
          dync->pos_in_childpar[u_x]=dync->pos_in_childpar[uniq_node];

          if ( ( (dync->children[u_x]) = (int *)malloc(2*sizeof(int)) ) == NULL )
            report_error("update_under_insert: malloc() error");
          dync->children[u_x][0]=uniq_node;

          dync->parent[uniq_node]=u_x;
          dync->pos_in_childpar[uniq_node]=0;

          dync->children[u_x][1]=new_x;
          dync->parent[new_x]=u_x;
          dync->pos_in_childpar[new_x]=1;

          dync->nb_child[u_x]=2;
          dync->nb_leaves[u_x]=1;  // we count the contribution of x separately, later

        }

        else {



          if ( (temp_children=(int *)malloc((dync->nb_child[uniq_node]+1)*sizeof(int))) == NULL )
            report_error("update_under_insert: malloc() error");
          for (i=0;i<dync->nb_child[uniq_node];i++)
            temp_children[i]=dync->children[uniq_node][i];
          temp_children[i]=new_x;
          free(dync->children[uniq_node]);
          copy_time += dync->nb_child[uniq_node];
          tab_expansion ++;
          dync->children[uniq_node]=temp_children;
          dync->nb_child[uniq_node]++;
          dync->parent[new_x]=uniq_node;
          dync->pos_in_childpar[new_x]=dync->nb_child[uniq_node]-1;
        }
      }

    // A CHANGER:
    // il faudrait rajouter une capacite en plus du nb_child et ne pas faire de nouveau tableau si on a pas encore atteint la capacité.
    // il faudrait aussi compter le nombre d'extensions qu'on fait, pour voir si on les gère différemment.

      else {



        u_x=dync->nt;
        u_nh=dync->nt+1;
        //dync->ident[u_x]=dync->n+dync->nt;
        //dync->ident[u_nh]=dync->n+dync->nt+1;
        dync->nt += 2;

        dync->label[u_nh]=0;
        if ( (dync->children[u_nh]=(int *)malloc((nb_tobefilled)*sizeof(int))) == NULL )
          report_error("update_under_insert: malloc() error");
        for (i=0;i<nb_tobefilled;i++) {
          dync->children[u_nh][i]=dync->children[insnode][i];
          dync->parent[dync->children[insnode][i]]=u_nh;
          dync->pos_in_childpar[dync->children[insnode][i]]=i;
        }
        dync->nb_child[u_nh]=nb_tobefilled;
        nb_leaves_nh=0;
        for (i=0;i<nb_tobefilled;i++) {
          if (is_leaf(dync->children[insnode][i],dync)) nb_leaves_nh++;
          else nb_leaves_nh += dync->nb_leaves[dync->children[insnode][i]];
        }
        dync->nb_leaves[u_nh]=nb_leaves_nh;  // we count the contribution of x separately, later
        dync->parent[u_nh]=u_x;
        dync->pos_in_childpar[u_nh]=0;



        dync->label[u_x]=1;
        if ( (dync->children[u_x]=(int *)malloc(2*sizeof(int))) == NULL )
          report_error("update_under_insert: malloc() error");
        dync->children[u_x][0]=u_nh;
        dync->children[u_x][1]=new_x;
        dync->parent[new_x]=u_x;
        dync->pos_in_childpar[new_x]=1;
        dync->nb_child[u_x]=2;
        dync->nb_leaves[u_x]=dync->nb_leaves[u_nh];  // we count the contribution of x separately, later
        dync->parent[u_x]=insnode;
        dync->pos_in_childpar[u_x]=0;
      
        nb_h=dync->nb_child[insnode]-nb_tobefilled;

        if (nb_tobefilled < dync->nb_child[insnode]-nb_tobefilled) {
          for (i=0;i<nb_tobefilled;i++) {
            dync->children[insnode][i]=dync->children[insnode][dync->nb_child[insnode]-1-i];
            dync->pos_in_childpar[dync->children[insnode][i]]=i;
          }
        }
        else {
          for (i=nb_tobefilled;i<dync->nb_child[insnode];i++) {
            dync->children[insnode][i-nb_tobefilled]=dync->children[insnode][i];
            dync->pos_in_childpar[dync->children[insnode][i-nb_tobefilled]]=i-nb_tobefilled;
          }          
        }

        dync->children[insnode][nb_h]=dync->children[insnode][0];
        dync->pos_in_childpar[dync->children[insnode][nb_h]]=nb_h;
        dync->children[insnode][0]=u_x;
        dync->nb_child[insnode]=1+nb_h; // the list of children is truncated but the space is not freed...
        lost_space += nb_tobefilled-1;
        tab_truncated ++;
      // the number of leaves of insnode is unchanged, as we count the contribution of x separately, later
      // the parent of insnode is unchanged as well as the position of insnode in the children of its parent


      }

    }


    // ADD THE CONTRIBUTION OF X TO NB_LEAVES, X MUST NOT HAVE BEEN COUNTED BEFORE 
    p=dync->parent[new_x];
    dync->nb_leaves[p]++;
    while (p != dync->root) {
      p=dync->parent[p];
    (  dync->nb_leaves[p])++;
    }

  }

}






/////////////////////////////////////////////////////////////////////////////////////
// PRINT A DYNCOTREE TO A FILE
// IN : dync
// OUT : 
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE : 
/////////////////////////////////////////////////////////////////////////////////////

void print_dyncotree_to_file (dyncotree *dync, FILE *f) {

  int local_ident(int position) {
    if (position < 0) return position;
    else{
      if (position<dync->n) return (position+dync->n);
      else return (position-dync->n);
      }
  }

  int i,j;

  fprintf(f,"total nb of vertices: %d\n",dync->n);
  fflush(f);
  fprintf(f,"current nb of leaves: %d\n",dync->nl);
  fflush(f);
  fprintf(f,"current nb of internal nodes: %d\n",dync->nt);
  fflush(f);
  fprintf(f,"root: %d\n",local_ident(dync->root));
  fflush(f);
  fprintf(f,"label of the root: %d\n",dync->label[dync->root]);
  fflush(f);

  fprintf(f,"internal nodes (ident,label,nb_child,nb_leaves):\n");
  for (i=0;i<dync->nt;i++) fprintf(f,"%d %d %d %d\n",local_ident(i),dync->label[i],dync->nb_child[i],dync->nb_leaves[i]);
  fprintf(f,"\n");
  fflush(f);

  fprintf(f,"list of leaves:\n");
  for (i=0;i<dync->nl;i++) fprintf(f,"%d ",local_ident(i+dync->n));
  fprintf(f,"\n");
  fflush(f);

  fprintf(f,"triples (ident,parent,pos_in_childpar):\n");
  for (i=0;i<dync->nl;i++) fprintf(f,"%d %d %d\n",local_ident(i+dync->n),local_ident(dync->parent[i+dync->n]),dync->pos_in_childpar[i+dync->n]);
  for (i=0;i<dync->nt;i++) fprintf(f,"%d %d %d\n",local_ident(i),local_ident(dync->parent[i]),dync->pos_in_childpar[i]);
  fprintf(f,"\n");
  fflush(f);

  fprintf(f,"list of edges of the tree (parent,child):\n");
  for (i=0;i<dync->nt;i++) {
    for (j=0;j<dync->nb_child[i];j++) fprintf(f,"%d %d\n",local_ident(i),local_ident(dync->children[i][j]));
  }
  fprintf(f,"\n");
  fflush(f);

}





////////////////////////////////////////////////////////////////////////
////////// WRITE A DYNAMIC COTREE TO A FILE
//----------------------------------------------------------------------
// IN  : 
// OUT : 
// RETURN : 
//----------------------------------------------------------------------
// PREREQUISITE : 
////////////////////////////////////////////////////////////////////////

void write_dyncotree_to_file(dyncotree* dync, sgraph* g, FILE* f){
  char line[MAX_LINE_LENGTH];  // containing one line of output
  char *out_unit;              // the output is written to file by units contining several lines
  int length_out_unit;
  int node, i, neigh;
  int j, cur, length;

  int nbdigits=0;
  int quot=dync->nt+dync->nl;
  while (quot!=0) {
    quot=quot/2;
    nbdigits++;
  }
  length_out_unit=1+(2*nbdigits+2)*(dync->nt+dync->nl-1);  // chaque ligne contient 2 entiers entre 0 et nt+nl, un espace et un retour chariot. Il y au plus nt+nl-1 lignes (1 par fils) et il faut 1 charactère pour la fin de chaîne

  fprintf(f,"%d\n",dync->nt+dync->nl);
  fprintf(f,"%d\n",dync->label[dync->root]);


// IMPORTANT NOTE : It seems that when line is too long, it does not help to use it and even slow down. So this should be changed. It is probably strcat that scan all out_unit. Then it should be replaced by a direct access to the array of char.

  if( (out_unit=(char *)malloc(length_out_unit*sizeof(char))) == NULL )
    report_error("write_dyncotree_to_file: malloc() error");
//  out_unit[0]='\0';
  cur=0;
  for (node=0;node<dync->nl;node++) {
      sprintf(line,"%d %d\n",node,0);
      length=strlen(line);
      for (j=0; j<length; j++)
        out_unit[cur+j]=line[j];
      cur+=length;


  }
  for (node=0;node<dync->nt;node++) {
      sprintf(line,"%d %d\n",node+dync->nl,dync->nb_child[node]);
      length=strlen(line);
      for (j=0; j<length; j++)
        out_unit[cur+j]=line[j];
      cur+=length;

  }

  out_unit[cur]='\0';



  fprintf(f,"%s",out_unit);
  free(out_unit);


  for (node=0;node<dync->nt;node++) {
      if( (out_unit=(char *)malloc(length_out_unit*sizeof(char))) == NULL )
        report_error("write_dyncotree_to_file: malloc() error");
      //out_unit[0]='\0';
      cur=0;
      for (i=0;i<dync->nb_child[node];i++) {
        neigh=dync->children[node][i];
        if (is_leaf(neigh,dync)) sprintf(line,"%d %d\n",node+dync->nl,g->permu[neigh-dync->n]);
        else sprintf(line,"%d %d\n",node+dync->nl,neigh+dync->nl);
        length=strlen(line);
        for (j=0; j<length; j++)
          out_unit[cur+j]=line[j];
        cur+=length;
      }
      out_unit[cur]='\0';
      fprintf(f,"%s",out_unit);


      free(out_unit);
  }

}




////////////////////////////////////////////////////////////////////////
////////// FREE MEMORY FROM A DYNAMIC COTREE
//----------------------------------------------------------------------
// IN  : 
// OUT : 
// RETURN : 
//----------------------------------------------------------------------
// PREREQUISITE : 
////////////////////////////////////////////////////////////////////////

void free_dyncot (dyncotree** pdync){
  int i;

  if ((*pdync)!=NULL) {

    if (((*pdync)->children)!=NULL) {
      for (i=0;i<((*pdync)->nt);i++) {
	if (((*pdync)->children[i])!=NULL) free(((*pdync)->children[i]));
      }
      free((*pdync)->children);
    }

    if (((*pdync)->label)!=NULL)
      free((*pdync)->label);
    if (((*pdync)->nb_child)!=NULL)
      free((*pdync)->nb_child);
    if (((*pdync)->nb_leaves)!=NULL)
      free((*pdync)->nb_leaves);

    if (((*pdync)->parent)!=NULL)
      free((*pdync)->parent);
    if (((*pdync)->pos_in_childpar)!=NULL)
      free((*pdync)->pos_in_childpar);

    free(*pdync);
    (*pdync)=NULL;
  }
}





/******** COTREE MANAGEMENT functions - end *********/