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

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

#define MAXN 10

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

/* 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;
  char ch[20];
  int TID;
  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;
  action *first_action;
  action *help_action;
}trans;

/* 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];
} obj;

/* 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,*tempo;
   int COUNT=0,temp,T_num,i;

  /* Desmeush mhnmhs kai arxikopoihsh twn pediwn gia to xronoprogramma */
  new=(trans *)malloc(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. */
      
   while(COUNT!=M*num_trans) {
      temp=drand48()*100;
      T_num=temp%num_trans;
      for(i=0;i<k;i++){
            new_action=(action *)malloc(sizeof(action));
            help2=transactions[T_num].help_action;
              
              
            if(transactions[T_num].help_action!=NULL) {
                   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;
            strcpy(new_action->ch,help2->ch);
            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(obj *matrix_o,int num_objects) {


   int i;
   
   printf("\nGive the objects: \n");
   
   for(i=0;i<num_objects;i++)
      scanf("%s",matrix_o[i].object);    
 }


/* H sunarthsh auth epilegei tuxaia to onoma enos antikeimenou. */

char *find_object(obj *matrix_o,int num_objects) {
   int temp;
     temp=drand48()*100;
    return(matrix_o[temp%num_objects].object);
 }

/* 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.*/

void create_transaction(trans *new_trans,int trans_num,int action_num,obj *matrix_o,int num_objects) {
  action *new,*help;
  int i;
  
  

   new_trans->TID=counter; 
   help=new_trans->first_action;
  
   for(i=0;i<action_num;i++) {
      new=(action *)malloc(sizeof(action));
      strcpy(new->ch,find_object(matrix_o,num_objects));
      new->TID=counter;
      if(drand48()<=0.8)   
             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 \n\n",(transactions+i)->TID); 
 current=(transactions+i)->first_action;
 for(j=0;j<M;j++)
 {
  printf("ACTION %c(%s) T%i \n",current->R_W, current->ch,current->TID);
  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->ch,start->TID);  
    start=start->next_action;
  }
  
 }

/* Dhmiourgia tou pinaka geitniashs gia to grafo plohghshs */
void check_conflict(int N, int M, trans *sched)
{ 
 int i,j,e,v;
 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(strcmp(pointer1->ch,pointer2->ch)==0) /*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);
}



main() {
   int trans_num,m,help=0;
   int O,N,M,k,i,j,e,v,flag=0,flag1=0,k1=1;
   trans *transactions,*sched;
   obj *matrix_o;
  
    while(1)
    {
    counter=1;
    printf("\n****PROSOXH****\n");
    printf("\nOI ARITHMOI POU THA DWSETE THA PREPEI NA EINAI THETIKOI!!!\n");
    
    printf("\nDwste ton arithmo twn transactions N: ");
    scanf("%i",&N);
    printf("\nDwste ton arithmo twn actions M: "); 
    scanf("%i",&M);
    printf("\nDwste ton arithmo twn objects O: ");
    scanf("%i",&O);
    printf("\nDwste ton arithmo k: ");
    scanf("%i",&k);

  if(N>0 && M>0 && O>0 && k>0 && k<=M)
  {
  /* Desmeush mhnmhs gia tis dosolhpsies kai gia ta antikeimena. */
  
   transactions=(trans *)malloc(N*sizeof(trans));
   matrix_o=(obj *)malloc(O*sizeof(obj));

   /* Arxikopoihsh tou pinaka sugkrousewn. */
   
  for(i=0;i<=N;i++)
  {
   for(j=0;j<=N;j++)
    conflict_table[i][j]=0;
  }
    
  create_object(matrix_o,O);
  
   for(i=0;i<N;i++)   
       create_transaction((transactions+i),N,M,matrix_o,O),counter++;
    
   print_transaction(transactions,N,M);
 
   sched=create_schedule(transactions,N,k,M);  
  
   print_schedule(sched,N,M);
   
   check_conflict(N,M,sched);
 
 for(i=1;i<=N;i++)
 {
   for(j=1;j<=N;j++)
     printf(" %i ",conflict_table[i][j]); 
    printf("\n"); 
  }   

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

  if(help==N)
	printf("\no grafos den exei kyklo ara to xronoprogramma einai seiriopoihsimo.\n");
  else
   printf("\nyparxei kyklos sto grafo ara to xronoprogramma den einai seiriopoihsimo.\n");

printf("\n"); 
}
else
{
 printf("\nEisagate lanthasmena dedomena. Prospathiste xana.\n");
}

printf("Thelete na termatisei to programma? (y/n)");
scanf("\n%c",&choice);

if(choice=='y')
   exit(0);
}
}