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

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


//Declaration of all functions
bool borrelIterate(Output* out);
bool obligationoverlap(int t, Subset* whenObligation,int n,Obligation* obligations,bool* borrelAtTime);
bool borrelSubsetCanAttend(Output* out,Subset* borrelSubset,Subset* whenObligation,int i);
Output borrel(Input* in);
double calcValue(Subset* borrelSubs,double** matrix,int n,int m);
Output test(Input* in);
int updateAttendance(Output* out);


void main(){
	Input in = parser();
	if(!isFeasible(&in)){
		printf("The given input is infeasible\n");
		return;
	}
	Output out = borrel(&in);
	printOutput(&in,&out);
	freeOutput(&out);
}

Output test(Input* in){
	Output r = initOutput(in);
	r.s[0] = 1;
	r.s[1] = 2;
	updateAttendance(&r);
	return r;
}

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;
}
bool borrelSubsetCanAttend(Output* out,Subset* borrelSubset,Subset* whenObligation,int i){
	Input* in = out->in;
	bool borrelAtTime[in->t];
	for(int j=0;j<in->t;j++)borrelAtTime[j]=false;
	for(int h=0;h<borrelSubset->n;h++)
		if(borrelSubset->elem[h])
			for(int j=out->s[h];j<in->b[h]+out->s[h];j++)
				if(borrelAtTime[j])return false;
				else borrelAtTime[j] = true;

	for(int j=0;j<in->nI[i];j++){
		int leftover=0;
		for(int k=in->I[i][j].r;k<=in->I[i][j].d;k++)
			leftover+=!borrelAtTime[k];
		if(leftover<in->I[i][j].p)return false;
	}

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


bool borrelIterate(Output* out){
	Input* in = out->in;
	for(int h=0;h<in->m;h++){
		out->s[h]++;
		if(out->s[h]+in->b[h]<=in->t)
			return true;
		else
			out->s[h]=0;
	}
	return false;
}

// Input:
// t:	Amount of time slots
// m:	Amount of borrels
// b:	Amount of time slots per borrel
// n:	Amount of students
// I:	List of obligations per student
// nI:	Amount of obligations per student

// Output:
// s:	Time slot that a borrel starts
// att: The set of of borrels that a student can attend
// return==-1: There is no feasible solution
// return>=0: Amount of students that can attend the borrels in the optimum solution

double calcValue(Subset* borrelSubs,double** matrix,int n,int m){
	double value=0;
	for(int k=0;k<m;k++)
	for(int i=0;i<n;i++)
		if(borrelSubs[i].elem[k])
			for(int j=0;j<n;j++)
				value += borrelSubs[j].elem[k]*matrix[i][j];
	return value;
}

void freeListofListofSubsets(Subset** obl, int n, int* nI){
	for(int i=0;i<n;i++){
		for(int j=0;j<nI[i];j++){
			subsetFree(obl[i]+j);
		}
		free(obl[i]);
	}
	free(obl);
}

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

	Subset* borrelSubs=malloc(sizeof(Subset)*in->n);
	for(int i=0;i<in->n;i++)
		subsetInit(borrelSubs+i,in->m);

	bool iterating=true;
	while(iterating){

		Subset** obl = malloc(sizeof(Subset*)*in->n);

		bool validSubsets = true;
		for(int i=0;i<in->n;i++){
			obl[i] = malloc(sizeof(Subset)*in->nI[i]);
			if(!borrelSubsetCanAttend(out,borrelSubs+i,obl[i],i)){
				validSubsets = false;
				break;
			}
		}
		if(validSubsets){
			double value = calcValue(borrelSubs,in->socialMatrix,in->n,in->m);
			if(value>out->maxValue){
				out->obl=obl;
				out->maxValue = value;
			}else
				freeListofListofSubsets(obl,in->n,in->nI);
		}
		
		for(int i=0;i<in->n;i++){
			if(subsetIterate(borrelSubs+i)){
				iterating = true;
				break;
			}
			else{
				subsetInitSize(borrelSubs+i,in->m,in->m);
				iterating =false;
			}
		}
	}
	for(int i=0;i<in->n;i++)
		subsetFree(borrelSubs+i);
	free(borrelSubs);

	//for(int i=0;i<in->n;i++){
	//	subsetInit(borrelSubs+i,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+i,in->b,out->s,in->I[i],in->nI[i],whenObligationTmp))
	//			continue;
	//		if(borrelSubs[i].size>maxAttendanceForStudent){
	//			maxAttendanceForStudent = borrelSubs[i].size;
	//			for(int j=0;j<in->nI[i];j++){
	//				out->obl[i][j] = whenObligationTmp[j];
	//			}
	//			
	//		}
	//	}while(subsetIterate(borrelSubs+i));
	//	out->maxTotAtt+=maxAttendanceForStudent;
	//}
}

Output borrel(Input* in){
	Output out = initOutput(in);
	Output ret = initOutput(in);
	do{
		updateAttendance(&out);
		if(ret.maxValue<out.maxValue){
			copyOutput(&out,&ret);
		}
	}while(borrelIterate(&out));
	return ret;
}