/* Deutero sunolo askisewn - meros b*/
/* 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;
 
typedef struct action {
  char R_W;
  char ch[20];
  int TID;
  struct action  *next_action;
}action;

typedef struct trans{
  int TID;
  action *first_action;
  action *help_action;
}trans;

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;


  new=(trans *)malloc(sizeof(trans));
 
   new->TID=-1;
   new->first_action=NULL;
   new->help_action=NULL;
   help_act= new->first_action; 
   
   
   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 dhmiiourgias 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);    
 }



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

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;
  }
  
 }

void check_conflict(int N, int M, trans *sched)
{ 
 int i,j,e,v;
 action *pointer1, *pointer2;
 
 pointer1=sched->first_action;
 pointer2=pointer1->next_action;
 
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*/
 
}

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)
  {
   transactions=(trans *)malloc(N*sizeof(trans));
   matrix_o=(obj *)malloc(O*sizeof(obj));

  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);
}
}