/* Authors: */
/* Giannhs Stagakhs */
/* Basilikh Stamati */
/* Euanthia Tripolith */

/* Tropopoiisi:
 * Lillis Kostas A.M. 606
 */

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

#define MAXN 10

int counter=1,flag2=0;
int conflict_table[MAXN][MAXN], my_c_table[MAXN][MAXN];
char choice;

/*
 * Domi po kratao ta statistika stoixeia.
 */
typedef struct statistics
{
   int N;
   int M;
   int O;
   int k;
   int m;
   float seiriaka_nr;
   float seiriop_nr;
   float xronop_nr;
   int run_nr;
   struct statistics *next;
}stat;
stat *total_stat_head, *total_stat_tail;

/* Domh pou xrhsimopoieitai gia th dhmiourgia antikeimenwn, panw sta opoia efarmozontai
   oi energeies twn dosolhpsiwn. Kathe antikeimeno perilamvanei ws pedio to onoma tou. */
typedef struct obj{
   char object[20];
   int RTS;                     /*Xronosimo anagnosis antikeimenou - Lillis Kostas*/
   int WTS;                     /*Xronosimo eggrafis antikeimenou - Lillis Kostas*/
}obj;

/* Domh pou xrhsimopoieitai gia th dhmiourgia listas energeiwn gia kathe
   dosolhpsia. Kathe komvos-energeia exei ws pedia to id ths dosolhpsias,
   ean einai energeia egrafhs h anagnwshs, to onoma toy antikeimenou sto
   opoio efarmozetai h energeia kai ena deikth pros epomenh energeia. */  
typedef struct action {
   char R_W;
   obj *ob;                     /*Deiktis stin energeia pou ginetai i energeia*/
   int TID;
   int TS;	                   /*Xronosimo dosolipsias stin opoia anikei i energeia - Lillis Kostas*/
   struct action  *next_action;
}action;

/* Domh pou xrhsimopoieitai gia th dhmiourgia dosolhpsiwn. Perilamvanei ws pedia
   to id ths dosolhpsias, ena deikth sth prwth energeia ths dosolhpsias kai ena
   deutero deikth pou deixnei sth teleutaia energeia ths dosolhpsias. */
typedef struct trans{
   int TID;
   int TS;	                   /*Xronosimo dosolipsias - Lillis Kostas*/
   action *first_action;
   action *help_action;
}trans;

/*                    Lillis Kostas
 * Sunartisi pou epistrefei enan tuxaio arithmo
 * metaxi low kai high.
 */

int RandomInteger(int low, int high)
{
   int k;
   double d;
   d = (double) rand() / ((double) RAND_MAX + 1);
   k = (int) (d * (high - low + 1));
   return (low + k);
}

void *Calloc (size_t nobj , size_t size)
{
   int *general;

   if ( (general = (int *)calloc(nobj , size)) == NULL )
   {
      perror("calloc: ");
      exit (1);
   }

      return general;
}

/* Synarthsh dhmiourgias toy telikou xronoprogrammatos */

trans *create_schedule(trans *transactions,int num_trans,int k,int M) {
   trans *new;
   action *new_action=NULL,*help_act=NULL,*help2=NULL;
   int COUNT=0,temp,T_num,i,TS = 1;

  /* Desmeush mhnmhs kai arxikopoihsh twn pediwn gia to xronoprogramma */
   new=(trans *)Calloc(1,sizeof(trans));
 
   new->TID=-1;
   new->first_action=NULL;
   new->help_action=NULL;
   help_act= new->first_action; 
   
   /* Enhmerwsh tou xronoprogrammatos me tis energeies twn dosolhpsiwn ews otou
      oles oi energeies na perilamvanontai sto xronoprogramma. Arxika ginetai tuxaia
      epilogh ths dosolhpsias. Sth sunexeia dhmiourgountai sto xronoprogramma k h 
      ligoteres energeies, ean h epilegmenh dosolhpsia den exei k energeies h oi 
      energeies pou apomenoun gia na xrhsimopoihthoun apo authn einai ligoteres apo k. 
      Gia kathe mia energeia pou eisagoume sto xronoprogramma ginetai antigrafh twn pediwn ths 
      antistoixhs energeias apo thn epilegmenh dosolhpsia kai eisagetai sth lista twn
      energeiwn tou xronoprogrammatos. */
   /*
    *                       Lillis Kostas
	* Ektos apo ta parapano, dinetai se kathe dosolipsia kai stis energeies
	* tis to katallilo xronosimo. Auto tha xrisimeusei gia ton elegxo an
	* to xronoprogramma mporei na paraxthei me ton algorithmo diataxis
	* xronosimaton.
	*/
      
   while(COUNT!=M*num_trans) {
      temp=RandomInteger(0,99);
      T_num=temp%num_trans;
      for(i=0;i<k;i++){
         new_action=(action *)Calloc(1,sizeof(action));
		 help2=transactions[T_num].help_action;

		 if(transactions[T_num].TS == 0)          /* Tropopoiisi - Lillis Kostas*/
		 {
             transactions[T_num].TS = TS;
			 TS++;
		 }
              
         if(transactions[T_num].help_action!=NULL) {
		    help2->TS = transactions[T_num].TS;    /* Tropopoiisi - Lillis Kostas*/
            transactions[T_num].help_action=transactions[T_num].help_action->next_action;
            COUNT++;
         }
         else break;
             
         new_action->R_W=help2->R_W;
         new_action->TID=help2->TID;
		 new_action->ob = help2->ob;              /* Tropopoiisi - Lillis Kostas*/
		 new_action->TS=help2->TS;                /* Tropopoiisi - Lillis Kostas*/

         if(help_act==NULL) {
            help_act=new_action;
            new->first_action=new_action;
         }
         else {
            help_act->next_action=new_action;
            help_act=new_action;
         }
      }
   }   
   return(new);
}

/* Synarthsh enhmerwshs-eisagwghs onomasias twn antikeimenwn */

void create_object(FILE *input, obj *matrix_o,int num_objects) {

   int i;
   
   for(i=0;i<num_objects;i++)
   {
      fscanf(input,"%s",matrix_o[i].object);    
      matrix_o[i].RTS=0;
      matrix_o[i].WTS=0;
   }
 }

/* H sunarthsh auth epilegei tuxaia to onoma enos antikeimenou. */
/* Lillis Kostas - epistrefei deikti sto antikeimeno*/

obj *find_object(obj *matrix_o,int num_objects) {
   int temp;

   temp=RandomInteger(0,99);
   return(&matrix_o[temp%num_objects]);           /* Tropopoiisi - Lillis Kostas*/
}

/* Synarthsh dhmiourgias twn transactions */
/* Arxika sth dosolhpsia dinetai ena akeraio id. H prwth dosolhpsia exei to id 1, h deuterh
   to id 2 k.o.k. Sth sunexeia gia th dosolhpsia dhmiourgeitai to plhthos twn energeiwn. Gia
   kathe mia energeia enhmerwnontai ta antistoixa pedia ths. Sugkekrimena, to onoma tou 
   antikeimenou sto opoio tha efarmostei h energeia vrisketai mesw ths epistrefomenhs timhs ths
   sunarthshs find_object. Sthn energeia eisagoume kai to id ths dosolhpsias sthn opoia anhkei
   kai ean einai energeia eggrafhs h anagnwshs. Telos, eisagoume thn energeia sth lista twn
   antistoixwn energeiwn ths dosolhpsias.*/

/*                        Lillis Kostas
 * Edo prosthesa to orisma m to opoio leei poses fores pio syxnes einai oi
 * praxeis anagnosis apo aytes eggrafis.
 */

void create_transaction(trans *new_trans,int trans_num,int action_num,obj *matrix_o,int num_objects, int m) {
   action *new,*help;
   int i, percent = (int)(((float)m/(m+1))*100);
  

   new_trans->TID=counter; 
   new_trans->TS=0;                          /*Tropopoiisi - Lillis Kostas*/
   help=new_trans->first_action;
  
   for(i=0;i<action_num;i++) {
      new=(action *)Calloc(1,sizeof(action));
      new->ob = find_object(matrix_o,num_objects);          /* Tropopoiisi - Lillis Kostas*/
      new->TID=counter;
      if(RandomInteger(0,99)<=percent)
         new->R_W='R';
      else 
         new->R_W='W';

      if(help==NULL) {
         new_trans->first_action=new;
         help=new;
      }
      else { 
         help->next_action=new;
         help=new;          
      }
   }
   new_trans->help_action=new_trans->first_action;
}     

/* Synarthsh ektypwshs twn transactions */									  

void  print_transaction(trans *transactions, int N, int M)
{
   int i,j;
   action *current;
 
 
   for(i=0;i<N;i++)
   {
      printf("\n--->TRANSACTION  %i [TS(T%i) = %d]\n\n",(transactions+i)->TID,(transactions+i)->TID,(transactions+i)->TS); 
      current=(transactions+i)->first_action;
      for(j=0;j<M;j++)
      {
         printf("ACTION %c(%s) T%i \n",current->R_W, current->ob->object,current->TID);  /* Tropopoiisi - Lillis Kostas*/
         current=current->next_action;
      }
   }

}


/* Synarthsh ektypwshs tou xronoprogrammatos */

void print_schedule(trans *sched,int N, int M)
{
   action *start;
   int i;
  
   printf("\n------To teliko xronoprogramma einai------\n");
  
   start=sched->first_action;
     
   for(i=0;i<M*N;i++)
   {
	   printf("ACTION %c(%s) T%i \n",start->R_W,start->ob->object,start->TID);  /* Tropopoiisi - Lillis Kostas*/
       start=start->next_action;
   }
  
}

/* Dhmiourgia tou pinaka geitniashs gia to grafo plohghshs */
void check_conflict(int N, int M, trans *sched)
{ 
   int i,j;
   action *pointer1, *pointer2;
 
  /* Arxika exoume duo deiktes pou o prwtos deixnei sth prwth energeia tou
     xronoprogrammatos kai o allos sthn amesws epomenh energeia.*/
    
   pointer1=sched->first_action;
   pointer2=pointer1->next_action;
 
 /* Gia kathe mia energeia tou xronoprogrammatos elegxoume-sugkrinoume oles 
    tis metepeita energeies tou scheduler. Se kathe sugkrish metaxu duo
    energeiwn, ean oi energeies antistoixoun se diaforetikes dosolhpsies,
    efarmozontai sto idio antikeimeno kai mia apo autes einai gia egrafh
    sto antikeimeno, tote exoyme sugkroush kai enhmerwnoume thn katallhlh
    thesh tou pinaka geitniashs me 1. Gia paradeigma ean h i dosolhpsia
    sugkrouetai me th dosolhpsia j, tote h thesh (i,j) tou pinaka 
    enhmerwnetai me 1. Sto telos ths sunarthshs oles oi "sugkrouomenes" dosolhpsies
    tha uparxoun sto pinaka conflict_table. */
    
   for(j=0;j<N*M && pointer2!=NULL;j++)
   {
      for(i=j+1;i<N*M;i++)
      {
         if(pointer1->TID!=pointer2->TID) /*exoume duo diaforetikes dosolipsies*/
         {
           if(pointer1->ob == pointer2->ob) /*an einai sto idio dedomeno*/
           {
             /*elegxw ti eidos praksi exw*/
             if(pointer1->R_W=='R' && pointer2->R_W=='R') /*Den exw conflict*/
             {
               pointer2=pointer2->next_action;
             }
             else /*exw conflict*/
             {
               conflict_table[pointer1->TID][pointer2->TID]=1;   
               pointer2=pointer2->next_action;
             }
           }
           else
           {
             pointer2=pointer2->next_action;
           }
         }
         else
         {
           pointer2=pointer2->next_action;
         }
      } /*end of second for*/
 
      pointer1=pointer1->next_action;
      pointer2=pointer1->next_action;
   }  /*end of for*/
}

/* H sunarthsh auth elegxei ean to xronoprogramma einai seiriopoihsimo
   h oxi. Sugekrimena otan kaleitai kathe fora auth h sunarthsh ginetai
   elegxos, me thn voitheia tou conflict table, na entopistei ean uparxei
   kuklos metaxu twn dosolhspiwn. Kalwntas th sugekrimenh sunarthsh, ginetai
   elegxos se kathe komvo-dosolhspia ean to indegree tou einai 0. Se auth thn 
   periptwsh diagrafoume oles tis "akmes" apo ton upo exetash komvo-dosolhpsia
   pros tis upoloipes dosolhpsies. Afou ektelestei h sugekrimenh sunarthsh gia
   to plhthos twn dosolhspiwn, telika entopizetai ean uparxei kuklos h oxi kai
   epomenws ean to xronoprogramma einai seiriopoihsimo h oxi.  */
   
int check(int N)
{
   int i,j, l,zero=0,help=0;
   j=1;
   while(j<=N)
   {
      for(i=1;i<=N;i++)
      {
	     if(conflict_table[i][j]==0)
		 zero++;
      }
      if(zero==N)
      {	
	     for(l=1;l<=N;l++)
	     {
	        conflict_table[j][l]=0;
	     }
	     help++;
	     zero=0;
	     j++;
      }
      else
      {
	     j++;
	     zero=0;
      }
   }
   return(help);
}

/*                    Lillis Kostas
 * I routina aytielegxei an to xronoprogramma einai seiriako.
 * Etsi metraei poses enallages ginontai metaxi ton dosolipsion.
 * An oi enallages einai N to xronoprogramma einai seiriako
 * diaforetika oxi.
 */

int check_serial(trans *sched,int N, int M)
{
   action *start;
   int i, count = 0, check = -1;
  
   start=sched->first_action;
     
   for(i=0;i<M*N;i++)
   {
       if (start->TID != check)
	   {
           check = start->TID;
           count++;
       }
       start=start->next_action; 
   }
  
   printf ("\nTo xronoprogramma%seinai seiriako.\n\n",(count == N)?" ":" den ");

   return ((count == N)?1:0);
}

/*                    Lillis Kostas
 * I routina auti tuponei ena seiriako xronoprogramma
 * isodinamo me to seiriopoiisimo arxiko xronoprograma.
 * Auto to kanei bazontas se kaoia seira tis dosolipseies
 * sumfona me poses alles proigountai autis.
 */

void find_serial(int N)
{
   int i,j,my_tot[MAXN],count = 0,max ,pos;

   for(i=1;i<=MAXN;i++)
      my_tot[i] = 0;

   for(i=1;i<=N;i++)
       for(j=1;j<=N;j++)
           if(my_c_table[i][j] == 1)
           {
              my_tot[i]++;
              my_tot[j]--;
           }
	
   printf("\nTo isodynamo siriako xronoprogramma einai: ");
   while(count < N)
   {
       max = -(MAXN+1);
       for(i=1;i<=N;i++)
           if(max < my_tot[i])
           {
              max = my_tot[i];
              pos = i;
           }
       printf("%sT%d",(count == 0)?"":"->",pos);
       my_tot[pos] = -(MAXN);
       count++;
   }
   printf("\n");
}


/*                     Lillis Kostas
 * I routina auti elegxei an to xronoprogramma mporei na paraxthei
 * me ton algorithmo diataxis xronosimaton.
 */

int check_time_scedual(trans *sched,int N, int M)
{
   action *start;
   int i, ok = 1;

   start=sched->first_action;
     
   for(i=0;i<M*N;i++)
   {
       if(start->R_W == 'R')
       {
          if(start->TS < start->ob->WTS)
          {
             printf("\nACTION %c(%s): TS(T%i) = %d ",start->R_W,start->ob->object,start->TID,start->TS);
             printf("< WTS(%s) = %d\n",start->ob->object, start->ob->WTS);
             ok=-1;
             break;
          }
          else
             start->ob->RTS = (start->ob->RTS > start->TS)?start->ob->RTS:start->TS;
       }
       else
       {
          if(start->TS < start->ob->RTS)
          {
             printf("\nACTION %c(%s): TS(T%i) = %d ",start->R_W,start->ob->object,start->TID,start->TS);
             printf("< WTS(%s) = %d\n",start->ob->object, start->ob->WTS);
             ok = -1;
             break;
          }
          else if(start->TS < start->ob->WTS)
             continue;
          else
             start->ob->WTS = start->TS;
       }
       start=start->next_action; 
   }
   printf("\nTo xronoprogramma%smporei na paraxthei ",(ok == 1)?" ":" den ");
   printf("me ton algorithmo diataxis xronosimaton\n");

   return((ok == 1)?1:0);
}

/*                    Lillis Kostas
 * I routina auti krataei ta statistika diladi:
 * posa xronoprogrammata einai seiriaka, posa 
 * seiropoiisima, posa mporoun na paraxthoun me
 * ton algorithmo diataxis xronosimaton kai ton
 * arithmo ton ekteleseon.
 */

void get_stat(int N, int M, int O, int k, int m, int seiriako, int seirop, int xronop, int repeat_nr)
{
   stat *new_stat;

   if (total_stat_head == NULL)
   {
      new_stat = (stat *)Calloc(1,sizeof(stat));
      new_stat->N = N;
      new_stat->M = M;
      new_stat->O = O;
      new_stat->k = k;
      new_stat->m = m;
      new_stat->seiriaka_nr = (float)seiriako;
      new_stat->seiriop_nr = (float)seirop;
      new_stat->xronop_nr = (float)xronop;
      new_stat->run_nr = repeat_nr;
      new_stat->next = NULL;

      total_stat_head = new_stat;
      total_stat_tail = new_stat;
   }
   else
   {
      if (N==total_stat_tail->N && M==total_stat_tail->M &&
          O==total_stat_tail->O && k==total_stat_tail->k &&
          m==total_stat_tail->m)
      {
         total_stat_tail->seiriaka_nr+=(float)seiriako;
         total_stat_tail->seiriop_nr+=(float)seirop;
         total_stat_tail->xronop_nr+=(float)xronop;
      }
      else
      {
         new_stat = (stat *)Calloc(1,sizeof(stat));
         new_stat->N = N;
         new_stat->M = M;
         new_stat->O = O;
         new_stat->k = k;
         new_stat->m = m;
         new_stat->seiriaka_nr = (float)seiriako;
         new_stat->seiriop_nr = (float)seirop;
         new_stat->xronop_nr = (float)xronop;
         new_stat->run_nr = repeat_nr;
         new_stat->next = NULL;

         total_stat_tail->next = new_stat;
         total_stat_tail = new_stat;
      }
   }

}

/*                    Lillis Kostas
 * I routina auti meta to telos tis ektelesis upologizei
 * ta pososta ton statistikon.
 */

void create_percentage(void)
{
   stat *tmp_stat = total_stat_head;

   while(tmp_stat != NULL)
   {
       tmp_stat->seiriaka_nr = (tmp_stat->seiriaka_nr * 100)/tmp_stat->run_nr;
       tmp_stat->seiriop_nr = (tmp_stat->seiriop_nr * 100)/tmp_stat->run_nr;
       tmp_stat->xronop_nr = (tmp_stat->xronop_nr * 100)/tmp_stat->run_nr;

       tmp_stat = tmp_stat->next;
   }
}

/*                    Lillis Kostas
 * I routina auti arxikopoiei se 0 tous xronous eggrafis
 * kai diabasmatos ton antikeimenon gia tin epomeni epanalipsi.
 */

void reset_object_time(obj *matrix_o,int num_objects) 
{
   int i;
   
   for(i=0;i<num_objects;i++)
   {
       matrix_o[i].RTS=0;
       matrix_o[i].WTS=0;
   }
 }

/*                    Lillis Kostas
 * I routina auti eleutheronei ti mnimi pou kratoun oi domes.
 */

void free_mem(trans *transactions, trans *sched, int N, int M)
{
   int i,j;
   action *act, *tmp_act;

   for(i=0;i<N;i++)
   {
       act = (transactions+i)->first_action;
       for(j=0;i<M;i++)
       {
           tmp_act = act;
           act = act->next_action;
           free(tmp_act);
       }
   }
   free(transactions); 

   act = sched->first_action;
   for(i=0;i<M*N;i++)
   {
       tmp_act = act;
       act = act->next_action;
       free(tmp_act);
   }
   free(sched);
}

int main(int argc , char **argv)
{
   int m,help=0, seirop, seiriako, xronop, repeat_nr;
   int O,N,M,k,i,j,flag=0,flag1=0,k1=1,z;
   trans *transactions,*sched;
   obj *matrix_o;
   FILE *stats, *input;

   if (argc<3)
   {
      printf ("Usage: a.out <filename> <number of runs with same parameters>\n");
      exit(1);
   }
   ++argv;

   input = fopen(*argv,"r");

   ++argv;
   repeat_nr = atoi(*argv);
  
   while((fscanf(input,"%i %i %i %i %i",&N,&M,&O,&k,&m))!=EOF)
   {
       matrix_o=(obj *)Calloc(O,sizeof(obj));
       create_object(input,matrix_o,O);

       for(z=0;z<repeat_nr;z++)
       {
           counter=1;
        /* Desmeush mhnmhs gia tis dosolhpsies kai gia ta antikeimena. */
  
           transactions=(trans *)Calloc(N,sizeof(trans));

			/* Arxikopoihsh tou pinaka sugkrousewn. */
   
           for(i=0;i<=N;i++)
           {
               for(j=0;j<=N;j++)
                   conflict_table[i][j]=0;
           }
  
           for(i=0;i<N;i++)   
               create_transaction((transactions+i),N,M,matrix_o,O,m),counter++;
 
           sched=create_schedule(transactions,N,k,M);

           print_transaction(transactions,N,M);
  
           print_schedule(sched,N,M);
   
           seiriako = check_serial(sched,N,M);                /* Tropopoiisi - Lillis Kostas*/

           check_conflict(N,M,sched);
 
           for(i=1;i<=N;i++)
           {
               for(j=1;j<=N;j++)
               {
                   printf(" %i ",conflict_table[i][j]); 
                   my_c_table[i][j] = conflict_table[i][j];   /* Tropopoiisi - Lillis Kostas*/
               }
               printf("\n"); 
           }   

           for(i=0;i<N;i++)
               help=check(N);

           if(help==N)
           {
              printf("\nO grafos den exei kyklo ara to xronoprogramma einai seiriopoihsimo.\n");
              seirop = 1;            /* Tropopoiisi - Lillis Kostas*/
              find_serial(N);        /* Tropopoiisi - Lillis Kostas*/
           }
           else
           {
              printf("\nYparxei kyklos sto grafo ara to xronoprogramma den einai seiriopoihsimo.\n");
              seirop = 0;             /* Tropopoiisi - Lillis Kostas*/
           }
	
           xronop = check_time_scedual(sched,N,M);          /* Tropopoiisi - Lillis Kostas*/
 
           printf("\n"); 

           get_stat(N, M, O, k, m, seiriako, seirop, xronop,repeat_nr); /* Tropopoiisi - Lillis Kostas*/

           reset_object_time(matrix_o,O);                              /* Tropopoiisi - Lillis Kostas*/
           free_mem(transactions, sched, N, M);                        /* Tropopoiisi - Lillis Kostas*/
        }
		free(matrix_o);                          /* Tropopoiisi - Lillis Kostas*/
   }

   create_percentage();                         /* Tropopoiisi - Lillis Kostas*/
   stats = fopen("statistics","w");             /* Tropopoiisi - Lillis Kostas*/
   /*fprintf(stats,"N\tM\tO\tk\tm     seiriaka seriop xronop nr_of_runs\n");
   fprintf(stats,"-----------------------------------------------------------------------\n");*/
   while (total_stat_head != NULL)              /* Tropopoiisi - Lillis Kostas*/
   {
       fprintf(stats,"%d\t%d\t", total_stat_head->N, total_stat_head->M);
       fprintf(stats,"%d\t%d\t", total_stat_head->O, total_stat_head->k);  
       fprintf(stats,"%d\t%3.2f\t", total_stat_head->m, total_stat_head->seiriaka_nr);  
       fprintf(stats,"%3.2f\t%3.2f\t", total_stat_head->seiriop_nr, total_stat_head->xronop_nr);  
       fprintf(stats,"%d\n",total_stat_head->run_nr);

       total_stat_head = total_stat_head->next;
   }
   fclose(stats);
   fclose(input);
   return 0;
}