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

#include "subset.h"
#include "input.h"
#include "output.h"


//Declaration of all functions
bool borrelSubsetCanAttend(int t,Subset* borrelSubset,int* b,int* s,Obligation *obligations,int n,Subset* whenObligation);
bool borrelIterate(int t,int m,int* b,int* s);
bool obligationoverlap(int t, Subset* whenObligation,int n,Obligation* obligations,bool* borrelAtTime);
bool borrelSubsetCanAttend(int t,Subset* borrelSubset,int* b,int* s,Obligation *obligations,int n,Subset* whenObligation);
bool borrelIterate(int t,int m,int* b,int* s);
Output borrel(Input* in);


void main(){
	Input in = parser();
	double start,end;
	start = (double)clock()/(double)CLOCKS_PER_SEC;
	if(!isFeasible(&in)){
		printf("The given input is infeasible\n");
		return;
	}
	Output out = borrel(&in);
	end = (double)clock()/(double)CLOCKS_PER_SEC;
	printOutput(&in,&out);
	double time_taken = (double)(end - start);
	printf("The algorithm took %f seconds.\n", time_taken);
}


//Check if there is an overlap in the schedule
bool obligationoverlap(int t, Subset* whenObligation,int n,Obligation* obligations,bool* borrelAtTime){
	bool obligationAtTime[t];
	for(int i=0;i<t;i++)obligationAtTime[i]=false;
	for(int i=0;i<n;i++){
		for(int j=obligations[i].r;j<=obligations[i].d;j++){
			if(whenObligation[i].elem[j-obligations[i].r]){
				if(obligationAtTime[j]||borrelAtTime[j])return true;
				obligationAtTime[j]=true;
			}
		}
	}
	return false;
}
//Checks if the current borrel subset is feasible.
bool borrelSubsetCanAttend(int t,Subset* borrelSubset,int* b,int* s,Obligation *obligations,int n,Subset* whenObligation){
	bool borrelAtTime[t];
	for(int i=0;i<t;i++)borrelAtTime[i]=false;
	for(int h=0;h<borrelSubset->n;h++)
		if(borrelSubset->elem[h])
			for(int i=s[h];i<b[h]+s[h];i++)
				if(borrelAtTime[i])return false;
				else borrelAtTime[i] = true;

	for(int i=0;i<n;i++){
		int leftover=0;
		for(int j=obligations[i].r;j<=obligations[i].d;j++)
			leftover+=!borrelAtTime[j];
		if(leftover<obligations[i].p)return false;
	}

	for(int i=0;i<n;i++){
		whenObligation[i].n = obligations[i].d-obligations[i].r+1;
		whenObligation[i].size = obligations[i].p;
		subsetInitSize(whenObligation+i,obligations[i].p,obligations[i].d-obligations[i].r+1);
	}
	while(obligationoverlap(t,whenObligation,n,obligations,borrelAtTime)){
		bool endOfIteration = true;
		for(int i=0;i<n;i++){
			if(fixedSizeSubsetIterate(whenObligation+i)){
				endOfIteration=false;
				break;
			}else{
				subsetInitSize(whenObligation+i,whenObligation[i].size,whenObligation[i].n);
			}
		}
		if(endOfIteration)return false;
	}
	return true;
}

bool borrelIterate(int t,int m,int* b,int* s){
	for(int h=0;h<m;h++){
		s[h]++;
		if(s[h]+b[h]<=t)
			return true;
		else
			s[h]=0;
	}
	return false;
}


int updateAttendance(Output* out){
	Input* in = out->in;
	out->maxTotAtt =0;

	for(int i=0;i<in->n;i++){
		Subset borrelSubs;
		subsetInit(&borrelSubs,in->m);
		int maxAttendanceForStudent = 0;
		do{
			Subset whenObligationTmp[in->nI[i]];
			for(int j=0;j<in->nI[i];j++){
				subsetInit(whenObligationTmp+j, in->I[i][j].d-in->I[i][j].r+1);
			}
			
			if(!borrelSubsetCanAttend(in->t,&(borrelSubs),in->b,out->s,in->I[i],in->nI[i],whenObligationTmp))
				continue;
			if(borrelSubs.size>maxAttendanceForStudent){
				maxAttendanceForStudent = borrelSubs.size;
				for(int j=0;j<in->nI[i];j++){
					out->obl[i][j] = whenObligationTmp[j];
				}
				
			}
		}while(subsetIterate(&(borrelSubs)));
		out->maxTotAtt+=maxAttendanceForStudent;
	}
}

Output borrel(Input* in){
	Output out = initOutput(in);
	Output ret = initOutput(in);
	do{
		updateAttendance(&out);
		if(ret.maxTotAtt<out.maxTotAtt){
			copyOutput(&out,&ret);
		}
	}while(borrelIterate(in->t,in->m,in->b,out.s));
	return ret;
}