/*
To programma pairnei ws orismata:
ton arithmo twn dosolhpsiwn N
ton arithmo twn praksewn ana dosolhpsia M
ton arithmo twn antikeimenwn O
ton bathmo polyplexias k
Dhladh to programma trexei ws ekhs:
./a.out N M O k

Gia na ginei compile xrhsimopoioyme to flag -lm, dhladh:
gcc -lm schedule.c
*/

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

typedef struct transaction
{
        int *objects;
        int *action;
}transaction;

typedef struct schedule
{
        int trans1;
        int *acts;
}schedule;
typedef struct node
{
        int tn;
        int ac;
        struct node *next;
}node;

int round(float x)
{
if((ceil(x)-x)>=0.5)
	return(floor(x));
else
return(ceil(x));
}


int Uniform(int a, int b)
{
float r;
r=drand48();
r=a+(b-a)*r;
return(round(r));
}

int actions(void)
{
        float u;
        u=drand48();
        if(u<=0.8)
                return(0);
        else
                return(1);
}

int object(int O)
{
   float u;
   int i;
   float s,j;
   u=drand48();
   s=O;
   for(i=1;i<=O;i++)
   {
        j=i;
        if(u<j/s)
                return(i-1);
   }
}
int **adjacent,N,**c;

main(int argc, char *argv[])
{
        int M,O,k,i,j,u,flag,*counter,*count,l;
        transaction *trans;
        float w,y;
        int x;
        node **top,*new,*temp,*current,*prev;
        schedule *sch;

        if(argc!=5)
        {
                printf("Wrong number of arguments\n");
                printf("Usage: a.out N M O k\n");
                exit(0);
        }
        N=atoi(argv[1]);
        M=atoi(argv[2]);
        O=atoi(argv[3]);
        k=atoi(argv[4]);
        srand48(time(NULL));
      trans=(transaction *)malloc(N*sizeof(transaction));
      counter=(int *)malloc(N*sizeof(int));
        for(i=0;i<N;i++)
        {
                trans[i].objects=(int *)malloc(M*sizeof(int));
                trans[i].action=(int *)malloc(M*sizeof(int));
                for(j=0;j<M;j++)
                {
                   trans[i].objects[j]=object(O);
                   trans[i].action[j]=actions();
                }
        }
        w=M;
        y=k;
        x=ceil(w/y);
        sch=(schedule *)malloc((N*x)*sizeof(schedule));
        for(i=0;i<N*x;i++)
           sch[i].acts=(int*)malloc(k*sizeof(int));
        for(i=0;i<N;i++)
                counter[i]=0;
        i=0;
       while(i<N*x)
        {
                u=Uniform(0,N-1);
                if(counter[u]<x)
                {
                        sch[i].trans1=u;
                        for(j=k*counter[u];j<k*counter[u]+k;j++)
                                if((counter[u]*k+j-(k*counter[u]))<M)
                                        sch[i].acts[j-k*counter[u]]=j+k*counter[u];
                        counter[u]++;
                        i++;
                }
        }
        for(i=0;i<N;i++)
                counter[i]=0;
        for(i=0;i<N*x;i++)
        {
                fprintf(stderr,"T%i:",sch[i].trans1+1);
                for(j=k*counter[sch[i].trans1];j<k*counter[sch[i].trans1]+k;j++)
                {
                        if((counter[sch[i].trans1]*k+j-(k*counter[sch[i].trans1]))<M)
                        {
                                if(trans[sch[i].trans1].action[j]==0)
                                        fprintf(stderr,"R(");
                                else
                                        fprintf(stderr,"W(");
                                fprintf(stderr,"%i)",trans[sch[i].trans1].objects[j]+1);
                        }
                }
                counter[sch[i].trans1]++;
        }
        printf("\n");
        if(k==M)
        {
                printf("\nThe schedule is serial\n");
                return;
        }
        else
        {
                flag=0;
                for(i=0;i<N;i=i+x)
                {
                        for(j=0;j<x;j++)
                        {
                                if(sch[i].trans1!=sch[i+j].trans1)
                                {
                                        flag=1;
                                        break;
                                }
                        }
                        if(flag==1)
                                break;
                }
                if(flag==0)
                {
                        printf("\nThe schedule is serial\n");
                        return;
                }
        }
        adjacent=(int **)malloc(N*sizeof(int));
        for(i=0;i<N;i++)
                adjacent[i]=(int *)malloc(N*sizeof(int));
       for(i=0;i<N;i++)
              for(j=0;j<N;j++)
                       adjacent[i][j]=0;
      c=(int **)malloc(N*sizeof(int));
        for(i=0;i<N;i++)
               c[i]=(int *)malloc(N*sizeof(int));
       for(i=0;i<N;i++)
              for(j=0;j<N;j++)
                       c[i][j]=0;
        top=(node **)malloc(O*sizeof(node));
        for(i=0;i<O;i++)
                top[i]=NULL;
         for(i=0;i<N;i++)
                counter[i]=0;
        for(i=0;i<N*x;i++)
        {
                for(j=k*counter[sch[i].trans1];j<k*counter[sch[i].trans1]+k;j++)
                {
                        if((counter[sch[i].trans1]*k+j-(k*counter[sch[i].trans1]))<M)
                        {
                                new=(node *)malloc(sizeof(node));
                                new->next=NULL;
                                new->tn=sch[i].trans1;
                                new->ac=trans[sch[i].trans1].action[j];
                                if(top[trans[sch[i].trans1].objects[j]]==NULL)
                                            top[trans[sch[i].trans1].objects[j]]=new;
                                else
                                {
                                        temp=top[trans[sch[i].trans1].objects[j]];
                                        while(temp->next!=NULL)
                                                temp=temp->next;
                                        temp->next=new;
                                }
                        }
                }
                counter[sch[i].trans1]++;
        }

         for(i=0;i<O;i++)
         {
                current=top[i];
                while(current!=NULL)
                {
                        temp=current->next;
                        while(temp!=NULL)
                        {
                                if(current->tn!=temp->tn)
                                        if((current->ac==1)||(temp->ac==1))
                                        {
                                                adjacent[current->tn][temp->tn]=1;
                                                c[current->tn][temp->tn]=1;
                                        }
                                temp=temp->next;
                        }
                        current=current->next;
                }
         }
         printf("\n");
         for(l=1;l<N;l++)
                for(i=0;i<N;i++)
                         for(j=0;j<N;j++)
                                for(k=0;k<N;k++)
                                         c[i][j]=c[i][j]+c[i][k]*adjacent[k][j];
        for(i=0;i<N;i++)
                if(c[i][i]!=0)
                {
                        printf("The schedule is not conflict serializable\n");
                       exit(0);
                }
         printf("This schedule is conflict-serializable\n");
      }