/*--------------------------------------------------------------------------------
F|permut|max(Ci)  Utemezesi fedadat megoldasa véletlenszerűen kereső algoritmus alkalmazásával.
Az előző gyakorlaton megírt program bővítése 
szakaszosan rendelkezésre álló gépek terhelésére szolgáló algortimussal.

A Load_STET_to_Cal függvény a cut paraméter értékétől függően
a megadott terhelést [st, et]  
but==0 érték esetén: 
	az adott gép azon rendelkezésre állási intervallumára helyezi, 
	amelyiken megszakitás nelkul elfér.
cut==1 érték esetén:
	megszakitásokkal akár több darabban helyezi el
	az adott gép rendelkezésre állási időintervallumain.
 --------------------------------------------------------------------------------*/


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

typedef struct{
                long id,
                     * SetT,
                     * ProcT,
                     * OptT,
                     * StartT,
                     * EndT;
              }T_JOB;

typedef struct{
                long ST; //start
                long ET;  //end
                }T_TW;  //time window

typedef struct{
                int id;
                int NCal;
                T_TW* Cal;
                }T_M;  //machine

long simulation(int* S, T_JOB* job, int n, int m, long ref_T, T_M* M, int cut);
void job_print(int* Sch, T_JOB* job, int n, int m);
void sim_data_print(int* Sch, T_JOB* job, int n, int m);
void Johnson_ald(int* Sch, T_JOB* job, int n, int x, int y );

void copy(int* s, int* d, int n);
void neigbour( int* S_inic, int* S, int n);
void random_search(int* S, T_JOB* job, int n, int m, int STEP, int LOOP, T_M* M, int cut);
void mach_print(int m, T_M* M);
int Load_STET_to_Cal(long *st, long *et, long last, int j, T_M* M, int cut);
int Load_STET_to_Cal_do_cut(long *st, long *et, long last, int j, T_M* M, int cut);



int main(int argc, char* argv[])
{
 T_JOB* job;
 int n; //jobok darabszama
 int m; //gepek szama
 int i; //job futoindex
 int j; //gepek futoindex
 int * Sch; //utemterv
 int *r;  //rendezes Johnson alg. elott
 int x, y; //elso masodik Johnson
 long Cmax; //maximalis befejezesi ido
 long Cbest; //kereses soran legjobb celfv ertek
 int *Sch_best; //kereses soran talalt legjobb megoldas
 T_M* M;  //gepek halmaza
 int c;  //szamlalo
 int cut; //felhasznalo dontese

 //virtualis adatbazis lekerdeze
 randomize();
 printf("\n Kerem a jobok szamat:");
 scanf("%d", &n); //n erteket kap bill-rol

 printf("\n Kerem a gepek szamat:");
 scanf("%d", &m); //m erteket kap bill-rol
 printf("\n Munkak a gepeken megszakithato (i/n)?:");
 if (getch() == 'i' )
  cut = 1;
 else
  cut = 0;

 randomize();

 M = (T_M*) calloc( m, sizeof(T_M));
 for (j=0; j<m; j++)
 {
   M[j].id = j;
   M[j].NCal = 1 + random(10);
   M[j].Cal = (T_TW*) calloc(M[j].NCal, sizeof(T_TW) );
   for (c=0; c<M[j].NCal; c++)
   {
    if (c==0)
     {
       M[j].Cal[c].ST = random(50);
     }
    else
     {
       M[j].Cal[c].ST = M[j].Cal[c-1].ET + 10 + random(50);
     }
    M[j].Cal[c].ET = M[j].Cal[c].ST + 10 + random (100);
   }
 }

 mach_print(m, M);

 /*
 {
  long st, et;
  int r;
  do
  {
   printf("\n Mach_id = ");
   scanf("%d", &j);
   printf("\n st = ");
   scanf("%ld", &st);
   printf("\n et = ");
   scanf("%ld", &et);
   r = Load_STET_to_Cal(&st, &et, 0, j, M, 0);
   printf("\n r=%d: %ld-%ld", r, st, et);

   printf("\n Uj teszt?");
  }
  while (getch()=='i');

 }

 getch();
 */
 job = (T_JOB*) calloc(n, sizeof(T_JOB) );
 for (i=0; i<n; i++)
 {
  job[i].id = i;
  job[i].SetT = (long*) calloc(m, sizeof(long));
  job[i].ProcT = (long*) calloc(m, sizeof(long));
  job[i].OptT = (long*) calloc(m, sizeof(long));
  job[i].StartT = (long*) calloc(m, sizeof(long));
  job[i].EndT = (long*) calloc(m, sizeof(long));

  for (j=0; j<m; j++)
    {
     job[i].SetT[j] = random (10) + 10;
     job[i].ProcT[j] = random (100) + 10;
     job[i].OptT[j] = job[i].SetT[j] + job[i].ProcT[j];
     }
  }

  Sch = (int*) calloc(n, sizeof(int));
  for (i=0; i<n; i++)
    Sch[i]=i;

  Sch_best = (int*) calloc(n, sizeof(int));

  //CDS
  for (j=0; j<m-1; j++) //0-1  1-2 ...(m-1)-m
  {
   Johnson_ald(Sch, job, n, j, j+1 );
   Cmax = simulation(Sch, job, n, m, 0, M, cut);
   //printf("\n %d. megoldas: \n \t Cmax=%ld",j, Cmax);

   if (j==0)
     {
      Cbest = Cmax;
       for(i=0; i<n; i++)
          Sch_best[i]=Sch[i];

     }
   else
     {
      if ( Cbest > Cmax )
       {
         Cbest = Cmax;
         for(i=0; i<n; i++)
            Sch_best[i]=Sch[i];

       }
     }
  }
  for(i=0; i<n; i++)
     Sch[i]=Sch_best[i];
  //kiindulasi adatok
  //job_print(Sch, job, n, m);
  //szimulacio
  Cmax = simulation(Sch, job, n, m, 0, M, cut);
  printf("\n \n \t CDS heurisztika eredmenye: Cmax=%ld", Cmax);
  //eredmeny
  //sim_data_print(Sch, job, n, m);

    //random kereses
  random_search(Sch, job, n, m, 100, 500, M, cut);
  Cmax = simulation(Sch, job, n, m, 0, M, cut);
  printf("\n \n \t Kereses eredmenye: Cmax=%ld", Cmax);


 for (i=0; i<n; i++)
  {
   free( job[i].SetT );
   free( job[i].ProcT );
   free( job[i].OptT );
   free( job[i].StartT );
   free( job[i].EndT );
  }
  free( job );
  free( Sch );
  free( Sch_best );

  //gep felszab
 for (j=0; j<m; j++)
   free ( M[j].Cal );
 free( M );


 getch();
 return 1;
}

void random_search(int* S, T_JOB* job, int n, int m, int STEP, int LOOP, T_M* M, int cut)
{
 int step, loop;
 long g, g_best, g_n_best;
 int* S_best;
 int* S_n_best;
 int* S_inic;

 S_best = (int*) calloc(n, sizeof(int));
 S_n_best = (int*) calloc(n, sizeof(int));
 S_inic = (int*) calloc(n, sizeof(int));

 copy( S, S_inic, n); //kezdo
 g = simulation(S_inic, job, n, m, 0, M, cut);
 copy( S_inic, S_best, n ); //legjobb
 g_best = g;

 for (step=0; step<STEP; step++)
 {
   for (loop=0; loop<LOOP; loop++)
   {
   //kepezzunk szomszedot
   neigbour( S_inic, S, n);
   g = simulation(S, job, n, m, 0, M, cut);
   //printf("\n %d. megoldas: \n \t Cmax=%ld",j, Cmax);

   if (loop==0)
     {
      g_n_best = g;
      copy(S, S_n_best, n);
     }
   else
      if ( g_n_best > g )
       {
         g_n_best = g;
         copy(S, S_n_best, n);
       }
   }//loop
   copy( S_n_best, S_inic, n);

   if (g_best > g_n_best)
   {
    g_best = g_n_best;
    copy( S_n_best, S_best, n);
   }
  } //step

    copy(S_best, S, n);

 free( S_best);
 free( S_n_best);
 free( S_inic);
}

void neigbour( int* S_inic, int* S, int n)
{
 int d;
 int temp;
 copy(S_inic, S, n);
 d = random(n);
 if ( d==0 )
   {
     temp = S[n-1];
     S[n-1] = S[d];
     S[d] = temp;
   }
 else
   {
     temp = S[d-1];
     S[d-1] = S[d];
     S[d] = temp;

   }
}


void copy(int* s, int* d, int n)
{
  int i;
  for (i=0; i<n; i++)
    d[i]=s[i];
}


long simulation(int* S, T_JOB* job, int n, int m, long ref_T, T_M* M, int cut)
{ //n munka m gepen sch sorrendben
  int i, j;

  for ( i=0; i<n; i++ )
   for ( j= 0; j<m; j++ )
   {
    if ( i == 0 )
    {
      if ( j == 0 )
      {
       job[S[i]].StartT[j] = ref_T;
      }
      else
      { //kezdo munka nem kezdo gepen
        job[S[i]].StartT[j] = job[S[i]].EndT[j-1];
      }
    }
    else //nem kezdo munka
    {
      if (m==0)
      { //kezdo gep
         job[S[i]].StartT[j] = job[S[i-1]].EndT[j];
      }
      else
      { //nem kezdo gep               //elozo gepen          //elozo munka
         job[S[i]].StartT[j] = max( job[S[i]].EndT[j-1] , job[S[i-1]].EndT[j] );

      }
    }//if i
    job[S[i]].EndT[j] = job[S[i]].StartT[j]
                           + job[S[i]].OptT[j];
    Load_STET_to_Cal( &job[S[i]].StartT[j], &job[S[i]].EndT[j], 0, j, M, cut);

   }//for
  return job[S[n-1]].EndT[m-1];
}

void mach_print(int m, T_M* M)
{
 int j;
 for (j=0; j<m; j++)
 {
   int c;
   printf("\n %d_Mach /%d/", j, M[j].NCal);
   for (c=0; c<M[j].NCal; c++)
    printf("\n \t %d_cal: %ld-%ld", c, M[j].Cal[c].ST, M[j].Cal[c].ET);

  }

}

void job_print(int* Sch, T_JOB* job, int n, int m)
{
 int i, j;
 printf("\n Idoadatok:\n");
 for (j=0; j<m; j++)
  {
   printf("\n %d_Operacio:", j);

   for (i=0; i<n; i++ )
   {
    printf("\n \t jobid=%d \t %ld", Sch[i], job[Sch[i]].OptT[j]);
   }
  }
}

void sim_data_print(int* Sch, T_JOB* job, int n, int m)
{
 int i, j;
 printf("\n Idoadatok:\n");
 for (j=0; j<m; j++)
  {
   printf("\n %d_Operacio:", j);

   for (i=0; i<n; i++ )
   {
    printf("\n \t %d \t %ld \t %ld \t %ld", Sch[i], job[Sch[i]].OptT[j], job[Sch[i]].StartT[j], job[Sch[i]].EndT[j]);
   }
  }
}

void Johnson_ald(int* Sch, T_JOB* job, int n, int x, int y )
{
 int i, j, temp;
 int b, l;
 long ti, tj;
 int *r = (int *) calloc(n, sizeof(int));
 for (i=0; i<n; i++)
   r[i] = Sch[i];

 for (i=0; i<n-1; i++)
   for (j=i+1; j<n; j++ )
   {
    ti = min( job[r[i]].OptT[x], job[r[i]].OptT[y] );
    tj = min( job[r[j]].OptT[x], job[r[j]].OptT[y] );
    if ( ti > tj)
     {
      temp = r[i];
      r[i] = r[j];
      r[j] = temp;
     }

   }

   b=0;
   l=n-1;  //korrekcio!!!!

   for(i=0; i<n; i++)
    if ( job[r[i]].OptT[x] < job[r[i]].OptT[y])
     {
      Sch[b]=r[i];
      b++;
     }
    else
    {
     Sch[l]=r[i];
     l--;
    }


 free(r);
}

int Load_STET_to_Cal(long *st, long *et, long last, int j, T_M* M, int cut)
{
 //nem szakithato meg a munka
 long size;
 long newst, newet;
 int n, c, found;

 if (cut == 1 ) return Load_STET_to_Cal_do_cut(st, et, last, j, M, cut);


 size = *et-*st; //hossz
 newst = max ( last, *st);
 newet = newst + size;

 found = -1;
 n = M[j].NCal;
 c = 0;
 while( c < n )
 {
  if (  newst < M[j].Cal[c].ET  )
  {
      newst = max( newst, M[j].Cal[c].ST );
      newet = newst + size;
      if ( newet <= M[j].Cal[c].ET)
      {
        found = c;
        break;
      }
      else
      {
        c++;
        if ( c >= n)
        {
         break;
        }
        newst = M[j].Cal[c].ST;
        newet = newst + size;
        continue;
      }
  }
  c++;
 }

 *st = newst;
 *et = newet;
 return found;
 }

int Load_STET_to_Cal_do_cut(long *st, long *et, long last, int j, T_M* M, int cut)
{
 //nem szakithato meg a munka
 long size;
 long newst, newet;
 long fps = -1; //first part start
 int n, c, found;
 size = *et-*st; //hossz
 newst = max ( last, *st);
 newet = newst + size;

 found = -1;
 n = M[j].NCal;
 c = 0;
 while( c < n )
 {
  if (  newst < M[j].Cal[c].ET  )
  {
      newst = max( newst, M[j].Cal[c].ST );
      newet = newst + size;
      if ( newet <= M[j].Cal[c].ET)
      {
        found = c;
        if ( fps == -1) fps = newst;
        break;
      }
      else
      {
        c++;
        if ( c >= n)
        {
         break;
        }
        size -= newet-M[j].Cal[c-1].ET;

        newst = M[j].Cal[c].ST;
        newet = newst + size;
        continue;
      }
  }
  c++;
 }

 *st = fps;
 *et = newet;
 return found;
 }