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

struct TMaillon
{
 char Bit;
 struct TMaillon *Suivant;
};

struct TMaillon *NbBin1=NULL,*NbBin2=NULL,*ListeOR=NULL,
                *ListeAND=NULL,*Liste1par2=NULL,*ListeSomme=NULL;

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Creer une liste à partir d'une chaine de caracteres
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

struct TMaillon *ListeBiniare(char s[])
{
    struct TMaillon *T=NULL,*P;
    int i=strlen(s)-1; //On commence de la fin de la chaine pour mettre le poids fort au début de la liste

    while(i>=0)
    {
     P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
     P->Bit=s[i];
     P->Suivant=T;    //Insertion au début
     T=P;
     i=i-1;
    }
    //Enlever les zeros au début de la liste
    while(T!=NULL && T->Bit=='0')
    {
        P=T;
        T=T->Suivant;
        free(P);
    }
    return T;
};

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Afficher une liste
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

void Affciher(struct TMaillon *T)
{
    printf("Liste -->");
    while(T!=NULL)
    {
      printf("|%c|-->",T->Bit);
      T=T->Suivant;
    }
    printf("Nil\n\n");
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Liberer une liste
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

void Liberer(struct TMaillon **T)
{
    struct TMaillon *P,*Q=*T;
    while(Q!=NULL)
    {
     P=Q;
     Q=Q->Suivant;
     free(P);
    }
    *T=NULL;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Calculer la fonction OR entre les deux nombres
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

void CalculerOR()
{
  struct TMaillon *LongListe=NbBin1,*CourtListe=NbBin2,*P,*Q;
  int i,L1=0,L2=0,k;
  //1. Calculer les longueurs des deux listes
  P=NbBin1;
  while(P!=NULL)
  {
     L1=L1+1;
     P=P->Suivant;
  }
  P=NbBin2;
  while(P!=NULL)
  {
     L2=L2+1;
     P=P->Suivant;
  }
  //Determiner la liste longue et la liste courte
  if(L1>L2)
  {
      LongListe=NbBin1;
      CourtListe=NbBin2;
  }
  else
  {
      LongListe=NbBin2;
      CourtListe=NbBin1;
      k=L1;
      L1=L2;
      L2=k;
  }
  // Creer les maillons du début de la liste longue
  for(i=0;i<(L1-L2);i++)
  {
      P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
      P->Suivant=NULL;
      P->Bit=LongListe->Bit;
      LongListe=LongListe->Suivant;
      if(ListeOR==NULL)
      {
         ListeOR=P;
      }
      else
      {
       Q->Suivant=P;
      }
     Q=P;
  }
  //creer les maillons des bits de correspondance
  for(i=0;i<L2;i++)
  {
      P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
      P->Suivant=NULL;
      if(LongListe->Bit=='1' || CourtListe->Bit=='1')
      {
         P->Bit='1'; // un des deux bits =1
      }
      else
      {
         P->Bit='0';
      }
      LongListe=LongListe->Suivant;
      CourtListe=CourtListe->Suivant;
      if(ListeOR==NULL)
      {
         ListeOR=P;
      }
      else
      {
       Q->Suivant=P;
      }
     Q=P;
  }

}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Calculer la fonction AND entre les deux nombres
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

void CalculerAND()
{
  struct TMaillon *LongListe=NbBin1,*CourtListe=NbBin2,*P,*Q;
  int i,L1=0,L2=0,k;
  //1. Calculer les longueurs des deux listes
  P=NbBin1;
  while(P!=NULL)
  {
     L1=L1+1;
     P=P->Suivant;
  }
  P=NbBin2;
  while(P!=NULL)
  {
     L2=L2+1;
     P=P->Suivant;
  }
  //Determiner la liste longue et la liste courte
  if(L1>L2)
  {
      LongListe=NbBin1;
      CourtListe=NbBin2;
  }
  else
  {
      LongListe=NbBin2;
      CourtListe=NbBin1;
      k=L1;
      L1=L2;
      L2=k;
  }
  // Sauter les premiers bits de la liste longue parceque les bits correspondants de la liste courte = 0
  for(i=0;i<(L1-L2);i++)
  {
      LongListe=LongListe->Suivant;
  }
  while(LongListe!=NULL && (LongListe->Bit=='0' || CourtListe->Bit=='0'))
  {
   LongListe=LongListe->Suivant;
   CourtListe=CourtListe->Suivant;
  }
  //creer les maillons des bits de correspondance
  while(LongListe!=NULL)
  {
      P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
      P->Suivant=NULL;
      if(LongListe->Bit=='1' && CourtListe->Bit=='1')
      {
         P->Bit='1'; // les deux bits =1
      }
      else
      {
         P->Bit='0';
      }
      LongListe=LongListe->Suivant;
      CourtListe=CourtListe->Suivant;
      if(ListeAND==NULL)
      {
         ListeAND=P;
      }
      else
      {
       Q->Suivant=P;
      }
     Q=P;
  }

}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Multiplier la premiere liste par 2
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

void Multip2()
{
 struct TMaillon *P1=NbBin1,*P,*Q;
 while(P1!=NULL)
 {
  P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
  P->Bit=P1->Bit;
  P->Suivant=NULL;
  if(Liste1par2==NULL)
  {
    Liste1par2=P;
  }
  else
  {
    Q->Suivant=P;
  }
  Q=P;
  P1=P1->Suivant;
 }
 if(Liste1par2!=NULL)
 {
  P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
  P->Bit='0'; //Ajouter un 0 à la fin
  P->Suivant=NULL;
  Q->Suivant=P;
 }

}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Calculer la somme des deux nombres
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

void CalculerSomme()
{
 struct TMaillon *P1=NbBin1,*P2=NbBin2,*NbBin1Inv=NULL,
                  *NbBin2Inv=NULL,*P,*Q;
 char Reste='0';
 //Creer les deux listes inversees
 while(P1!=NULL)
 {
   P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
   P->Bit=P1->Bit;
   P->Suivant=NbBin1Inv;
   NbBin1Inv=P;
   P1=P1->Suivant;
 }
 while(P2!=NULL)
 {
   P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
   P->Bit=P2->Bit;
   P->Suivant=NbBin2Inv;
   NbBin2Inv=P;
   P2=P2->Suivant;
 }

 P1=NbBin1Inv;
 P2=NbBin2Inv;

 // Calculer la somme des bites en correspondnace

 while(P1!=NULL && P2!=NULL)
 {
  P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
  P->Suivant=NULL;
  if((P1->Bit=='1' && P2->Bit=='1') || (P1->Bit=='0' && P2->Bit=='0'))
  {
      P->Bit=Reste;
      Reste=P1->Bit;
  }
  else
  if(Reste=='0')
  {
      P->Bit='1';
      Reste='0';
  }
  else
  {
      P->Bit='0';
      Reste='1';
  }
  if(ListeSomme==NULL)
  {
    ListeSomme=P;
  }
  else
  {
    Q->Suivant=P;
  }
  Q=P;
  P1=P1->Suivant;
  P2=P2->Suivant;
 }
 if(P1==NULL) {P1=P2;}

 // Calculer la somme du reste de la liste longue

 while(P1!=NULL)
 {
  P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
  P->Suivant=NULL;
  if((P1->Bit=='1' && Reste=='1') || (P1->Bit=='0' && Reste=='0'))
  {P->Bit='0';}
  else {P->Bit='1';
        Reste='0';}
   if(ListeSomme==NULL)
  {
    ListeSomme=P;
  }
  else
  {
    Q->Suivant=P;
  }
  Q=P;
  P1=P1->Suivant;
 }
 if(Reste=='1')
 {
  P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
  P->Bit='1';
  P->Suivant=NULL;
  Q->Suivant=P;
  }
 // Inverser la liste somme
 P=NULL;
 while(ListeSomme!=NULL)
 {
   P1=ListeSomme;
   ListeSomme=ListeSomme->Suivant;
   P1->Suivant=P;
   P=P1;
 }
 ListeSomme=P;

 Liberer(&NbBin1Inv);
 Liberer(&NbBin2Inv);
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Programme principal
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

int main()
{

    char chaine[255];
    int Choix=0;

    while(Choix!=9)
    {
        printf("============================================= \n");
        printf("==============TP Listes binaires=============\n");
        printf("=============================================\n");
        printf("[1] Lire la premiere liste\n");
        printf("[2] Afficher la premiere liste\n");
        printf("[3] Lire la deuxième liste\n");
        printf("[4] Afficher la deuxième liste\n");
        printf("[5] Calculer le OR \n");
        printf("[6] Calculer le AND\n");
        printf("[7] Multiplier la première liste par 2\n");
        printf("[8] Calculer la somme des deux listes\n");
        printf("[9] Quitter\n");
        printf("=============================================\n");
        printf("Donner votre choix:");
        scanf("%d",&Choix);
        switch (Choix)
        {
            case 1:
                printf("********************************************* \n");
                printf("-------- Creation de la premiere liste ------- \n");
                printf("--------------- Donner la liste: ------------- \n");
                printf("--------------------------------------------- \n");
                scanf("%s",chaine);
                printf("--------------------------------------------- \n");
                Liberer(&NbBin1);
                NbBin1= ListeBiniare(chaine);
                printf("------------ Nouvelle liste cree ------------ \n");
                printf("********************************************* \n");
                break;
            case 2:
                printf("********************************************* \n");
                printf("-------- Contenu de la premiere liste ------- \n");
                printf("--------------------------------------------- \n");
                Affciher(NbBin1);
                printf("********************************************* \n");
                break;
            case 3:
                printf("********************************************* \n");
                printf("-------- Creation de la deuxieme liste ------- \n");
                printf("--------------- Donner la liste: ------------- \n");
                printf("--------------------------------------------- \n");
                scanf("%s",chaine);
                printf("--------------------------------------------- \n");
                Liberer(&NbBin2);
                NbBin2= ListeBiniare(chaine);
                printf("------------ Nouvelle liste cree ------------ \n");
                printf("********************************************* \n");
                break;
            case 4:
                printf("********************************************* \n");
                printf("-------- Contenu de la deuxieme liste ------- \n");
                printf("--------------------------------------------- \n");
                Affciher(NbBin2);
                printf("********************************************* \n");
                break;
            case 5:
                printf("********************************************* \n");
                printf("-------- Calcul du OR entre les deux nombes ------- \n");
                printf("--------------------------------------------- \n");
                CalculerOR();
                printf("------------ OR Calcule, Resultat: ------------ \n");
                Affciher(ListeOR);
                printf("********************************************* \n");
                Liberer(&ListeOR);
                break;
            case 6:
                printf("********************************************* \n");
                printf("-------- Calcul du AND entre les deux nombes ------- \n");
                printf("--------------------------------------------- \n");
                CalculerAND();
                printf("------------ AND Calcule, Resultat: ------------ \n");
                Affciher(ListeAND);
                printf("********************************************* \n");
                Liberer(&ListeAND);
                break;
            case 7:
                printf("********************************************* \n");
                printf("----- Multiplier la premiere liste par 2 ---- \n");
                printf("--------------------------------------------- \n");
                Multip2();
                printf("------------ AND Calcule, Resultat: ------------ \n");
                Affciher(Liste1par2);
                printf("********************************************* \n");
                Liberer(&Liste1par2);
                break;
            case 8:
                printf("********************************************* \n");
                printf("-------------- Calculer la somme ------------ \n");
                printf("--------------------------------------------- \n");
                CalculerSomme();
                printf("------------ Somme Calcule, Resultat: ------------ \n");
                Affciher(ListeSomme);
                printf("********************************************* \n");
                Liberer(&ListeSomme);
                break;
           }

    }

    return 0;
}