//////////////////////////////////////////////////////////////////////
//   Computing bit-vector encodings of TREE hierarchies
//          with Caseau's and CHNR's method
//   
// Input: file name of a tree hierarchy under the .inh format
// Ouput: sizes of the bit-vector encodings produced by these methods
//////////////////////////////////////////////////////////////////////

#include <iostream.h>
#include <fstream.h>
#include <string.h>

#define N 2000  // the maximum number of nodes in the hierarchy

int max(int a, int b) {
  if (a>b) return(a);
  else return(b);
}
 
int min(int a, int b) {
    if (a>b) return(b);
    else return(a);
  }

// Weight functions for the degree of a node

int poids_caseau(int degre) {  // Weight function for Caseau's method
   return(degre);
}

int poids_chnr(int degre) { // Weight function for CHNR's method
  int x=1; // number of bits
  int l=1; // maximal width of an antichain that can be encoded with x bits

  while (l<degre) {
    l=((x+1)*l)/((x/2)+1);
    x++;
  }
  return(x);
}

// Index of the minimum of the n first elements of the array t

int lemin1(int n, int t[N]) {
     int i,imin=0;
 
     for (i=1; i<n; i++) if (t[i]<t[imin]) imin=i;
     return(imin);
   } 

// Index of the second minimum of the n first elements of the arry t

int lemin2(int n, int t[N], int imin1) {
     int i,imin=(imin1+1)%n;
 
     for (i=0; i<n; i++) if ((t[i]<t[imin]) && (i!=imin1)) imin=i;
     return(imin);
   }
 
// Index of the node s in the array t which lists all the nodes
// of the hierarchy

int index(char t[N][80], char s[80], int nb) {
     int i;
 
     for (i=1; i<=nb; i++) if (strcmp(t[i],s)==0) return(i);
     cout<<"\n"<<s<<" is not in this array";
     return(0);
   }
 
// Recursive function which computes the weights for nodes

int code_caseau(int noeud, int fils[N], int frere[N]) {  // Caseau's method
     int poids[N];
     int nb_fils=0;
     int degre; 
     int i;
     int imin1,imin2;
 
     if (fils[noeud]==0) return(0);
     i=fils[noeud];
     poids[nb_fils]=code_caseau(i,fils,frere);
     nb_fils++;
     while (frere[i]) {
       i=frere[i];
       poids[nb_fils]=code_caseau(i,fils,frere);
       nb_fils++;
     }

     if (nb_fils==1) return(poids[0]+1);

     degre=nb_fils;
     while (nb_fils>1) {
       imin1=lemin1(nb_fils,poids);
       imin2=lemin2(nb_fils,poids,imin1);
       poids[min(imin1,imin2)]=max(poids[imin1],poids[imin2]); 
       poids[max(imin1,imin2)]=poids[nb_fils-1]; 
       nb_fils--;
     }
     // cout<<"\nnode "<<noeud<<", weight="<<poids[0]; 
    return(poids[0]+poids_caseau(degre));
  }

int code_chnr(int noeud, int fils[N], int frere[N]) {  // CHNR's method
     int poids[N];
     int nb_fils=0;
     int degre; 
     int i;
     int imin1,imin2;
 
     if (fils[noeud]==0) return(0);
     i=fils[noeud];
     poids[nb_fils]=code_chnr(i,fils,frere);
     nb_fils++;
     while (frere[i]) {
       i=frere[i];
       poids[nb_fils]=code_chnr(i,fils,frere);
       nb_fils++;
     }

     if (nb_fils==1) return(poids[0]+1);

     degre=nb_fils;
     while (nb_fils>1) {
       imin1=lemin1(nb_fils,poids);
       imin2=lemin2(nb_fils,poids,imin1);
       poids[min(imin1,imin2)]=max(poids[imin1],poids[imin2]); 
       poids[max(imin1,imin2)]=poids[nb_fils-1]; 
       nb_fils--;
     }
     // cout<<"\nnode "<<noeud<<", weight="<<poids[0]; 
    return(poids[0]+poids_chnr(degre));
  }

// MAIN

void main(int nb,char **arg) {
    ifstream fin;
    ofstream fout;
    char s1[80],s2[80],s3[80],s4[80];
  int i,j,k,l;
  int nb_sommets;
  int bits_caseau,bits_chnr;

  if (nb!=2) {
    cout<<"One argument please\n";
    exit(-1);
  }

  fin.open(arg[1]);
  if (!fin.is_open()) { 
    cout<<"Can't open file "<<arg[1]<<"\n";
    exit(-1);
  }

  // Construction of the list of the nodes of the hierarchy
  char nom[N][80];

  nb_sommets=0;
  while (!fin.eof()) {
    fin>>s1;
    if (!fin.eof()) {
      fin>>s2>>s3>>s4;
      for (i=1; i<=nb_sommets; i++) if (strcmp(s2,nom[i])==0) break;
      if (i==nb_sommets+1) {nb_sommets++; strcpy(nom[nb_sommets],s2); }
      for (i=1; i<=nb_sommets; i++) if (strcmp(s4,nom[i])==0) break;
      if (i==nb_sommets+1) {nb_sommets++; strcpy(nom[nb_sommets],s4); }
    }  
  }

  // List the nodes
  // for (i=1;i<=nb_sommets;i++) cout<<"\n node "<<i<<" is "<<nom[i];

  // Storage of the tree 
  int fils[N]; // fils[i] is the index of the last son of i and is equal to 0 if i has no son
  int frere[N];  // frere[i] est the index of the left brother of i and is equal to 0 if i has no brother
  int a1pere[N]; // a1pere[i] is equal to 1 if i has a father and 0 otherwise (used to locate the root node)
  int racine; // index of the root node

  for (i=1; i<=nb_sommets; i++) { fils[i]=0; frere[i]=0; a1pere[i]=0; }

  fin.close();
  fin.open(arg[1]);
  while (!fin.eof()) {
    fin>>s1;
    if (!fin.eof()) {
      fin>>s2>>s3>>s4;
      if (strcmp(s2,s4)) {
        i=index(nom,s2,nb_sommets); j=index(nom,s4,nb_sommets);
        frere[j]=fils[i];
        fils[i]=j;
        a1pere[j]=1;
      }
    }
  }

  i=1;
  while (a1pere[i]) i++;
  racine=i;
   
  // Encoding     

    bits_caseau=code_caseau(racine,fils,frere);
    bits_chnr=code_chnr(racine,fils,frere);
    cout<<"\nSize of the bit-vector encodings for "<<arg[1]<<" , produced by:";
    cout<<"\nCaseau's method = "<<bits_caseau<<" bits";
    cout<<"\nCHNR's method = "<<bits_chnr<<" bits";
    cout<<"\n"; 

  fin.close();
}