#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define max(a,b)((a)>(b)?(a):(b))
//#define taille 51
     int i,j,m,n,nombre,diag,I;

    int etape,processeur_libre,deb,pas;
    float temps_courant, alpha1,lst;

    float alpha,temps_seq,efficacite;
	double opt;
    int sortie;
    float seqreal,seqparal,tampon;
    typedef int Matrice [150][150];
    typedef int rempduree[150][150];

struct Processeur
{
    struct Processeur *suiv;
    struct Processeur *pred;
    int ligne,colonne;
    float temps;
};typedef struct Processeur Processeur;

  Processeur *tetepr,*finpr,*pp,*qp,*p1;

struct Tache
{
    struct Tache *suiv;
    int ligne,colonne;
    double chemin;
};typedef struct Tache Tache;
Tache *teteex,*pt,*qt;

struct Coefficient
{
    struct Coefficient *suiv;
    int ligne,colonne;
};typedef struct Coefficient Coefficient;

Coefficient *teteat;

void lire(FILE * aLire, Matrice mat,int taille)
 {
		  int i, j ;
		  for (i = 1; i < taille; i++)
            {
			  for (j =1 ; j < taille; j++)
               fscanf(aLire, "%d", & mat[i] [j]);
			   fscanf(aLire, "\n");
		    }
}


void remplir_matrice_duree(rempduree red,Matrice m,int taille)
{
    int i,j,C[150];
    int nb;
    printf("matrice donnee\n");
    for (i = 1 ; i <taille; i++)
    {
       for (j = 1;j<taille; j++)

           printf("%5.2d", m[i][j]);
           printf("\n");
    }
    for(i=1;i<taille;i++)
    { j=1;
     while ((m[i][j]==0)&(j<=i))
      {
	   j++;
      }
       C[i]=j;
    }
    for(i=1;i<taille;i++)
    {
        printf("%d\n",C[i]);
    }
  for(j=1;j<taille;j++)
   {
    for(i=j;i<taille;i++)
     if(C[i]<=j)
       {
           if (i>j)
           {
            nb=4*(j-max(C[i],C[j]))+2;
            red[i][j]=nb;
           }
           else
            {
            if (i==j)
            nb=4*(j-C[j]);
            red[j][j]=nb;

            }
       }
    }
    for (i = 1 ; i <taille; i++)
    {
       for (j = 1;j<taille; j++)

           printf("%5.2d", red[i][j]);
           printf("\n");
    }

}

int duree (int i, int j, rempduree red)
{
    int a;

    if(i>j)
    {
     a=red[i][j];
    }
    else
    if (i==j)
    {
     a=red[j][j];
    }
    return a;
}



double ch(int i,int j)
{
    double a;
   a=2*n-i-j+1;
    return(a);
}


void place(struct Processeur *pp0)
{
    Processeur *pp1,*pp2;
    int fin;
    if(tetepr==NULL)
    {
        tetepr=pp0;
        finpr=pp0;
        pp0->suiv=NULL;
        pp0->pred=NULL;
    }
    else
    {
        if((tetepr->temps)<=(pp0->temps))
        {
            pp0->suiv=tetepr;
            tetepr->pred=pp0;
            tetepr=pp0;
            pp0->pred=NULL;
        }
        else
        {
            pp1=tetepr;
            pp2=tetepr->suiv;
            fin=0;
            while(!fin)
            {
                if(pp2==NULL)
                {
                    pp1->suiv=pp0;
                    finpr=pp0;
                    fin=1;
					pp0->pred=pp1;
					pp0->suiv=pp2;
                }
                else
                {
                    if((pp0->temps)>=(pp2->temps))
                    {
                        pp1->suiv=pp0;
                        pp0->suiv=pp2;
                        pp0->pred=pp1;
                        pp2->pred=pp0;
                        fin=1;
                    }
                    else
                    {
                        pp1=pp2;
                        pp2=pp2->suiv;
                    }
                }
            }
        }
    }
}


void affectation(rempduree red)
{
    Tache *qp;
    Processeur *pp;
    //rempduree red;
    processeur_libre=processeur_libre-1;
    pp=(Processeur *)malloc(sizeof(Processeur));
    pp->ligne=teteex->ligne;
    pp->colonne=teteex->colonne;
    pp->temps=temps_courant+duree(pp->ligne,pp->colonne,red);
    temps_seq=temps_seq+duree(pp->ligne,pp->colonne,red);
    place(pp);
    qp=teteex;
    teteex=teteex->suiv;
    qp->suiv=NULL;
    free(qp);
}



void miseex(int i1,int j1)
{
    Tache *p1,*p2,*pt;
    int fin;
    pt=(Tache *)malloc(sizeof(Tache));
    pt->ligne=i1;
    pt->colonne=j1;
    pt->chemin=ch(i1,j1);
    if(teteex==NULL)
    {
        teteex=pt;
        teteex->suiv=NULL;
    }
    else
    {
        if((teteex->chemin)<=(pt->chemin))
        {
            pt->suiv=teteex;
            teteex=pt;
        }
        else
        {
           p1=teteex;
		   p2=teteex->suiv;
		   fin=0;
           while(!fin)
           {
              if(p2==NULL)
              {
                  p1->suiv=pt;
                  pt->suiv=NULL;
                  fin=1;
              }
              else
              {
                 if((pt->chemin)>=(p2->chemin))
                 {
                    p1->suiv=pt;
                    pt->suiv=p2;
                    fin=1;
                 }
                 else
                 {
                     p1=p2;
                     p2=p2->suiv;
                 }
              }
           }
        }
    }

}




void miseat(int i2,int j2)
{
    Coefficient *p;
    p=(Coefficient *)malloc(sizeof(Coefficient));
    p->ligne=i2;
    p->colonne=j2;
    p->suiv=teteat;
    teteat=p;
}


void libea(int jj)
{
    Coefficient *p,*q;
    p=teteat;
    teteat=NULL;
    while(p!=NULL)
    {
        if(p->colonne==jj)
        {
            miseex(p->ligne,jj);
            q=p;
            p=p->suiv;
            q->suiv=NULL;
            free(q);
        }
        else
        {
            q=p->suiv;
            p->suiv=teteat;
            teteat=p;
            p=q;
        }
    }
}
void libeat(int ii, int jj)
{
    Coefficient *p,*q;
    p=teteat;
    teteat=NULL;
    while(p!=NULL)
    {
        if( p->ligne==ii && p->colonne==jj)
        {
            miseex(ii,jj);
            q=p;
            p=p->suiv;
            q->suiv=NULL;
            free(q);
        }
        else
        {
            q=p->suiv;
            p->suiv=teteat;
            teteat=p;
            p=q;
        }
    }
}


int main(void)
{
    Matrice A;
	//int  m, n;
	rempduree redtab;
	int p,n;
	int h;
	int g=0;
	int tab[500][500];
	int taille=51;

    printf("Entrer le valeur de nombre=");
	scanf("%d",&nombre);
	printf("entrer le n \n");
	scanf("%d",&n);

	FILE * aLire = fopen("C:\\Users\\DeLL\\Documents\\project c\\cc-ancien-avec2n\\test.txt", "r") ;
	 if(aLire == NULL)
    {
       printf("Le fichier n'existe pas");
    }
	 else

	 {
            lire (aLire, A,taille);
            remplir_matrice_duree(redtab,A,taille);
            printf("duree de la tache est %d\n",duree(6,4,redtab));

	 }
	   teteat=NULL;
	   teteex=NULL;

         for (i =1;i <taille; i++)
           {
           for (j = 1;j<taille; j++)
              if(redtab [i][j]!=0)
               {
                if(redtab[j][j]==0 && redtab[i][j-1]==0)
                  {
                    miseex(i,j);
                    diag=j;
                    printf("valeur de red[%d][%d]=%d\n",i,j,redtab[i][j]);

                  }
               }
            }

            temps_seq=0;

            temps_courant=0;


            processeur_libre=nombre;
            for(i=1;i<=nombre;i++)
            {
                affectation(redtab);
            }
            printf("le nombre de processeur est fini \n");

            sortie=0;
			printf("le temps courant est %f\n",temps_courant);
            while((!sortie)&&(tetepr!=NULL))
            {
                printf("debut= pas de tetepr\n");
                i=finpr->ligne;
                j=finpr->colonne;
                tab[0][g]=i;
                printf("valeur tab[1][%d]=%d\n",g,tab[0][g]);
                tab[1][g]=j;
                printf("valeur tab[2][%d]=%d\n",g,tab[1][g]);
                g++;
				printf("i=%d  j=%d\n",i,j);
                temps_courant=finpr->temps;
				printf("%f\n",temps_courant);
                p1=finpr;
                finpr=finpr->pred;
                if (finpr==NULL) tetepr=NULL;
				else finpr->suiv=NULL;

                p1->suiv=NULL;
                p1->pred=NULL;
                free(p1);
                if(j<i-1)

                    if(duree(j+1,j+1,redtab)!=0)
                    {
                        h=0;
                        printf("valeur de h est %d\n",h);
                        printf("valeur de tab[%d][%d]=%d\n",0,h,tab[0][h]);
                        printf("valeur de i est %d et j est %d\n",i,j);
                            while( h<g && (tab[0][h]!=j+1 || tab[1][h]!=j+1))
                            {
                                h++;

                            }

                            if(h<g && (tab[0][h]==j+1 || tab[1][h]==j+1 ))
                            {
                                printf("trouvé\n");
                                printf("libeat(%d)\n",j+1);
                                libea(j+1);
                            }
                            else
                            {
                                printf("hhhhhhhhhh\n");
                                printf("non trouvé\n");
                                printf("miseat(%d,%d)\n",i,j+1);
                                miseat(i,j+1);

                            }
                            printf("salut\n");
                    }

                  else miseex(i,j+1);

                else
				 if(j==i-1)

                    if(i!=n)
                    {
                     miseex(i,i);
                     printf("miseex(%d,%d)\n",i,i);
                    }

                    else
					{
						sortie=1;
						printf("miseex(%d,%d)=\n",i,i);
						miseex(i,i);
					}
                else
                {
                    for(p=j+1;p<taille;p++)
                    {

                        if(redtab[p][j]!=0 && redtab[p][j-1]==0)
                        {

                            printf("miseex (%d,%d)\n",p,j);
                            miseex(p,j);

                        }

                        else if (redtab[p][j]!=0 && redtab[p][j-1]!=0)
                        {
                            printf("salut\n");
                            printf("valeur de p trouvé est %d \n",p);

                            h=0;

                            while(h<g && (tab[0][h]!=p || tab[1][h]!=j-1))
                            {
                                h++;

                            }

                            if(h<g && (tab[0][h]==p || tab[1][h]==j-1 ))
                            {
                                printf("trouvé\n");
                                printf("libeat(%d,%d)\n",p,j);
                                libeat(p,j);
                            }
                            else
                            {
                                printf("non trouvé\n");
                                printf("miseat(%d,%d)\n",p,j);
                                miseat(p,j);

                            }

                        }
                    }

                }
                printf(" a atteint proceseur libre\n");
                processeur_libre=processeur_libre+1;
                //if(true)
                printf("valeur processeur libre=%d\n",processeur_libre);
                    while((processeur_libre>0)&&(teteex!=NULL))
                     {
                       printf(" dans while\n");
                      affectation(redtab);
                     }
            }

			i=finpr->ligne;
            j=finpr->colonne;
            tab[0][g]=i;
            printf("valeur tab[0][%d]=%d\n",g,tab[0][g]);
            tab[1][g]=j;
            printf("valeur tab[1][%d]=%d\n",g,tab[1][g]);

return 0;
}