//////////////////////////////////////////////////////////////////////
//   Computing bit-vector encodings of TREE hierarchies
//          with the dichotomic method
//   
// Input: file name of a tree hierarchy under the .inh format
// Ouput: a file with a list of the nodes with their codes
//////////////////////////////////////////////////////////////////////

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

#define N 2000  // the maximum number of nodes in the hierarchy 
#define NN 4000 // twice N
#define S 200   // the maximum size for the bit-vector encoding

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

// 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 array 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, inserts
// new intermediate nodes and gives colors to the nodes

int code(int noeud, int fils[NN], int frere[NN], char couleur[NN][S],
         int *p_nb) {
     int poids[N],indice[N];
     int nb_fils=0;
     int i,m;
     int imin1,imin2;
 
     if (fils[noeud]==0) return(0);
     
     i=fils[noeud];
     poids[nb_fils]=code(i,fils,frere,couleur,p_nb);
     indice[0]=i;
     nb_fils++;
     while (frere[i]) {
       i=frere[i];
       poids[nb_fils]=code(i,fils,frere,couleur,p_nb);
       indice[nb_fils]=i;
       nb_fils++;
     }

     if (nb_fils==1) {
       couleur[indice[0]][poids[0]+1]=1;
       return(poids[0]+1);
     }       

     while (nb_fils>2) {
       imin1=lemin1(nb_fils,poids);
       imin2=lemin2(nb_fils,poids,imin1);
       
       // insertion of the new node
       *p_nb=*p_nb+1;
       frere[indice[imin1]]=indice[imin2];
       frere[indice[imin2]]=0;
       fils[*p_nb]=indice[imin1];
       
       // updates of the weights and colors
       m=max(poids[imin1],poids[imin2]);
       couleur[indice[imin1]][m+1]=1;
       couleur[indice[imin2]][m+2]=1;
       
       poids[min(imin1,imin2)]=m+2;
       indice[min(imin1,imin2)]=*p_nb;
       
       poids[max(imin1,imin2)]=poids[nb_fils-1];
       indice[max(imin1,imin2)]=indice[nb_fils-1];

       nb_fils--;
    }

    fils[noeud]=indice[1];
    frere[indice[1]]=indice[0];
    frere[indice[0]]=0;

    m=max(poids[0],poids[1]);
    couleur[indice[0]][m+1]=1;
    couleur[indice[1]][m+2]=1;
    return(m+2);
  }


// Propagation of the colors to obtain the complete encoding from the
// reduced encoding

void propagate(int noeud, int fils[NN], int frere[NN], char
               couleur[NN][S], int nb_couleurs) {
    int i,c;
 
    if (fils[noeud]==0) return;
     
    i=fils[noeud];
    for (c=1; c<=nb_couleurs; c++) couleur[i][c]=couleur[i][c] ||
    couleur[noeud][c];
    propagate(i,fils,frere,couleur,nb_couleurs);

    while (frere[i]) {
      i=frere[i];
      for (c=1; c<=nb_couleurs; c++) couleur[i][c]=couleur[i][c] ||
      couleur[noeud][c];
      propagate(i,fils,frere,couleur,nb_couleurs);
    }
}

// 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 nb_courant;
  int bits;

  if (nb!=3) {
    cout<<"2 arguments please: input hierarchy and output file\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[NN]; // fils[i] is the index of the last son of i and is equal to 0 if i has no son
  int frere[NN];  // 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;
   
  // Generation of the reduced code    
  char couleur[NN][S];

  for (i=0; i<NN; i++)
    for (j=0; j<S; j++) couleur[i][j]=0;
  nb_courant=nb_sommets;
  bits=code(racine,fils,frere,couleur,&nb_courant);

  // Generation of the complete code

  propagate(racine,fils,frere,couleur,bits);

  // Writing the encoding 
  
  fout.open(arg[2],ios::out | ios::trunc);
  if (!fout.is_open()) { 
    cout<<"Can't open "<<arg[2]<<"\n";
    exit(-1);
  }

  for (i=1; i<=nb_sommets; i++) {
    fout<<nom[i]<<" ";
    for (j=1;j<=bits;j++) {if (couleur[i][j]==1) fout<<"1"; else
      fout<<"0";}
    fout<<"\n";
  }

  fout.close();

  cout<<"\nThe generated bit-vector encoding for "<<arg[1]<<" has a
 size equal to "<<bits<<" bits and has been stored in "<<arg[2]<<"\n";


  fin.close();
}