#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

#define g 3
#define Nil 0xFFFFFFFFLU


typedef struct{
  unsigned int G[g];      // Les fils
  unsigned int R;         // Redirection
  unsigned int S;         // Relation
  unsigned int T : 31;    // Profondeur
  unsigned int w : 1;     // Flag de passage
} Cellule;

const unsigned int Nmax=10000000;
Cellule * M;

unsigned int p;  // Première cellule vide

unsigned int c;  // Curseur
unsigned int b;  // Curseur précédent
int d;           // Direction précédente

unsigned int K;  // Profondeur de l'échelon

unsigned int N;  // Nombre de noeuds connus
unsigned int D;  // Nombre de direction non explorées
unsigned int T;  // Profondeur du graphe

unsigned int min(unsigned int x, unsigned int y);
void InitMem();                    // Initialisation
unsigned int Malloc();             // Alloue une cellule
void Free(unsigned int x);         // Libère une cellule
void garbage_collection(unsigned int r); // Nettoyage de la mémoire
unsigned int creer();		   // Alloue une cellule et l'initialise
unsigned int red(unsigned int x);  // Aspect 1 (redirection)
void dep(int x);                   // Déplace le curseur 0 selon la direction x
void chemin(unsigned char *L);     // Déplace le curseur selon le chemin *L
void equation(unsigned int x, unsigned char *L1, unsigned char *L2); // Applique l'équation à x
void equations(unsigned int x, int N, unsigned char *L1,...); // Applique les équations à x
void theorie(unsigned int x);      // Applique la théorie à x
void aff(unsigned int h);          // Affiche l'arbre de racine h
void ppp(unsigned int h);          // Parcourt l'arbre de racine h


unsigned int min(unsigned int x, unsigned int y){if (x<y) return x; else return y;}
void InitMem(){
  M = malloc(sizeof(Cellule[Nmax]));
  for(p=0;p<Nmax-1;p++) M[p].G[0] = p+1;
  M[Nmax-1].G[0]=Nil;
  p=0;
}
unsigned int Malloc(){
  unsigned int x=M[p].G[0];
  unsigned int y=p;
  if (x==Nil){printf("Out of memory!"); exit(-1);}
  else {p=x;return y;}
}
void Free(unsigned int x){
  M[x].G[0]=p;
  p=x;
}
void garbage_collection(unsigned int r){
  void graphe1(unsigned int r){
  
  }
  void list1(){
  
  }
  void libere_grille(){
  
  }
  void graphe0(unsigned int r){
  
  }
  void list0(){
  
  }
}
unsigned int creer(){
  unsigned int x=Malloc(); 
  int i;
  for(i=0;i<g;i++) M[x].G[i] = Nil;
  M[x].R=x;
  M[x].S=Nil; 
  M[x].T=0x7FFFFFFF;
  M[x].w=0;
  return x;
}
unsigned int red(unsigned int x){        // Aspect 1
  unsigned int y=x;
  while(M[x].R!=x) x=M[x].R;
  while(M[y].R!=y) y=x;
  return x;
}
void dep(int x){
  unsigned int y=M[c].G[x];
  if (y==Nil){
    y=creer();
    M[c].G[x]=y;
    b=c;
    d=x;
    c=y;
    M[y].T = M[b].T+1;              // Aspect 2
  }
  else {
  b=c;
  d=x;
  c=red(y);
  M[b].G[d]=c;
  M[c].T = min(M[c].T, M[b].T+1);  // Aspect 2
 }
} 
void chemin(unsigned char *L){
  unsigned char *K = L;
  while (*K != 0){
    if (*K!='1') dep(*K - 'a');
    K++;
  }
}
void equation(unsigned int x, unsigned char *L1, unsigned char *L2){
  unsigned int c0,b0; int d0;
  c=x;b=Nil;d=-1;
  chemin(L1);
  c0=c;b0=b;d0=d;
  c=x;b=Nil;d=-1;
  chemin(L2);
  if (c>c0) {M[c].R=c0; if (d!=-1) M[b].G[d]=c0;}
  if (c<c0) {M[c0].R=c; if (d0!=-1) M[b0].G[d0]=c;}
}
void equations(unsigned int x, int N, unsigned char *L1,...){
  unsigned int c0,b0; int d0;
  unsigned char *L2;
  int i;
  va_list L;
  va_start(L,L1);	
  c=x;b=Nil;d=-1;
  chemin(L1);
  c0=c;b0=b;d0=d;
  va_start(L,L1);

  for(i=1;i<N;i++){
    L2 = va_arg(L,unsigned char*);
    c=x;b=Nil;d=-1;
    chemin(L2);
    if (d==-1) {
      printf("***Erreur: equation: L'argument 1 doit être en premier\n");
      exit(-1);
    }
    if (c>c0) {M[c].R=c0; if (d!=-1) M[b].G[d]=c0;}
    if (c<c0) {M[c0].R=c; c0=c; if (d0!=-1) M[b0].G[d0]=c;}
  }
}
void affR(unsigned int h){
  unsigned int N=0,D=0,T=0,x;  

void aff1(unsigned int h){ // Affiche l'arbre de racine r en marquant le passage
  int i;
  //printf("%u",h);
  if (M[h].w!=1){ 
    N++;
    if (M[h].T>T) T=M[h].T;
    M[h].w=1; // Marque le passage.

      i=0; while(i<g && M[h].G[i]==Nil) i++; 
      if (i<g) {
        //printf("(");
        for(i=0;i<g-1;i++)
          if (M[h].G[i]==Nil){/*printf(".,")*/;D++;}
          else {
            x=red(M[h].G[i]);
            M[h].G[i]=x;
            M[x].T = min(M[x].T, M[h].T+1);  // Aspect 2
            aff1(x);
            //printf(",");
          }
        if (M[h].G[g-1]==Nil){/*printf(".)")*/;D++;}
        else {
          x=red(M[h].G[g-1]);
          M[h].G[g-1]=x;
          M[x].T = min(M[x].T, M[h].T+1);  // Aspect 2
          aff1(x);
          //printf(")");
        }
      }
      else D+=g;

  }
}
void aff0(unsigned int h){  // Démarque le passage
  int i;
  if (M[h].w==1){ 
    M[h].w=0;  // Démarque de passage.
    for(i=0;i<g;i++) if (M[h].G[i]!=Nil) aff0(M[h].G[i]);
  }
}

  aff1(h);
  aff0(h);
  printf("<%u|%u|%u>\n",N,D,T);
}

void aff(unsigned int h){
  unsigned int N=0,D=0,T=0;  
  void aff1(unsigned int h){
    int i;
    printf("%u",h);
    if (M[h].w!=1){ 
      N++;
      if (M[h].T>T) T=M[h].T;
      M[h].w=1; // Marque le passage.
        i=0; while(i<g && M[h].G[i]==Nil) i++; 
        if (i<g) {
          printf("(");
          for(i=0;i<g-1;i++)
            if (M[h].G[i]==Nil){printf(".,");D++;}
            else {
              aff1(M[h].G[i]);
              printf(",");
            }
          if (M[h].G[g-1]==Nil){printf(".)");D++;}
          else {
            aff1(M[h].G[g-1]);
            printf(")");
          }
        }
        else D+=g;
    }
  }
  void aff0(unsigned int h){
    int i;
    if (M[h].w==1){ 
      M[h].w=0; // Démarque de passage.
      for(i=0;i<g;i++) if (M[h].G[i]!=Nil) aff0(M[h].G[i]);
    }
  }

  aff1(h);
  aff0(h);
  printf("<%u|%u|%u>\n",N,D,T);
}
void affNDT(unsigned int h){
  unsigned int N=0,D=0,T=0;  
  void aff1(unsigned int h){
    int i;
    if (M[h].w!=1){ 
      N++;
      if (M[h].T>T) T=M[h].T;
      M[h].w=1;
      for(i=0;i<g;i++)
        if (M[h].G[i]==Nil)D++;else aff1(M[h].G[i]);
    }
  }
  void aff0(unsigned int h){
    int i;
    if (M[h].w==1){
      M[h].w=0; 
      for(i=0;i<g;i++) if (M[h].G[i]!=Nil) aff0(M[h].G[i]);
    }
  }

  aff1(h);
  aff0(h);
  printf("<%u|%u|%u>\n",N,D,T);
}

void ppp(unsigned int h){
void ppp1(unsigned int h){    // Parcourt l'arbre de racine h
  int i;
  if (M[h].w!=1){ 

    M[h].w=1;      // Marque le passage.
    theorie(h);

    if (M[h].T<K) for(i=0;i<g;i++) if (M[h].G[i]!=Nil) ppp1(M[h].G[i]);
  }
}
void ppp0(unsigned int h){   // Démarque le passage
  int i;
  if (M[h].w==1){ 
    M[h].w=0; // Démarque de passage.
    for(i=0;i<g;i++) if (M[h].G[i]!=Nil) ppp0(M[h].G[i]);
  }
}
ppp1(h);
ppp0(h);
}

void theorie(unsigned int x){
  equation(x,"acac","cba");
  equation(x,"bccb","abab");
  equations(x,4,"1","aaa","bbb","ccc");
}

/*void theorie(unsigned int x){
  equation(x,"ab","ba");
  //equations(x,3,"1","aaaaaa","bb");
}*/

int main(){
  InitMem();                 // Crée la grille
  unsigned int r=creer();    // Crée un noeud
  M[r].T=0;                  // Fixe la profondeur du noeud r à zéro, donc définie r comme la racine.
  
 for(K=0;K<10;K++){ppp(r);affR(r);affNDT(r);} 
  
  return 0;
}