/*******************************
 * Subset Enumeration Algorithmic 
 * Framework and its illustration in 
 * finding TSP. (vamsi(dat]krishnak[dat)geemaildatcam)
 ******************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<math.h>
#include "List.h"
unsigned int **GRAPH;
unsigned int subset_count=0;
//#define VERBOSE_MODE 1
void EnumSubSetsBFS(unsigned int n);

void CreateGraph(unsigned int *n){
	unsigned int i,j;
	printf("Enter the Graph Size\n");
	scanf("%u",n);
	if(*n>32){
		fprintf(stderr,"TODO: The Bitset currently supports only 32 bits\n");
		exit(1);
	}
	printf("Enter the weighted graph\n");
	GRAPH = (unsigned int **) malloc(sizeof(unsigned int *)*(*n));
	for(i=0;i<*n;i++){
		GRAPH[i] = (unsigned int *) malloc(sizeof(unsigned int)*(*n));
		for(j=0;j<*n;j++){
			scanf("%u",&(GRAPH[i][j]));
		}
	}
}

int main(){
	/*Create the Graph*/
	unsigned int n;
	CreateGraph(&n);
	EnumSubSetsBFS(n);

}
/*Returns the new tail of the list*/
inline List* ListAppend(List **tail,void *_data){
	List *new_node = (List *)malloc(sizeof(new_node)*1);
	assert(new_node);
	if(!(*tail)){
		(*tail) = new_node;
		(*tail)->_data = _data;
		(*tail)->next = NULL;
		return *tail;
	}
	new_node->_data = _data;
	new_node->next = NULL;
	(*tail)->next = new_node;
	return new_node;
}
typedef struct _subset_{
	/*if i^th bit is set then subset has i^th
	 *element*/
	unsigned int ebits;
	unsigned int max; /*Maximum element in the subset*/
	unsigned int size; /*Size of subset*/
	/*Pointer to the sub-problem */
	void *sub_problem;
}SubSet;
/*Enumerate the Subset using BFS, n is 
 *the set size [1,2...n] */
void EnumSubSetsBFS(unsigned int n){
	unsigned int check_sub_set,k,i,j;
	unsigned int current_level = 0;
	List *bfs_list = NULL;
	List *tail = NULL; List *free_node,*ptr;
	SubSet *sub_set,*new_sub_set;
	SubSet *one_sets = NULL;

	one_sets = (SubSet *)malloc(sizeof(SubSet)*n); 
	assert(one_sets);
	/*Add the 1-subsets*/
	for(i=1;i<n;i++){
		one_sets[i].ebits = 0; one_sets[i].ebits |= (1<<i);
		one_sets[i].max = i; one_sets[i].size = 1;
		/****SUBPROBLEM SPECIFIC*****/
		one_sets[i].sub_problem = (float *)malloc(sizeof(float)*n);
		for(j=1;j<n;j++){
			if(i==j){ continue; }
			/* TSP({i},j) */
			((float *)one_sets[i].sub_problem)[j] = GRAPH[0][i]+GRAPH[i][j];
			printf("S({%u},%u) = %f\n",i+1,j+1,((float *)one_sets[i].sub_problem)[j]);
		}
		/*****************************/
		if(!tail){
			ListAppend(&bfs_list,(void *)&(one_sets[i]));
			tail = bfs_list;
			continue;
		}
		tail = ListAppend(&tail,(void *)&(one_sets[i]));
	}
	/*Now do the BFS*/
	while(bfs_list){
		sub_set = (SubSet *)bfs_list->_data; 
		free_node = bfs_list;
		bfs_list=bfs_list->next;
		subset_count++;
		assert(sub_set->max < n);
		for(i=((sub_set->max)+1);i<n;i++){
			new_sub_set = (SubSet *) malloc(sizeof(SubSet)*1);
			new_sub_set->size = (sub_set->size)+1;
			new_sub_set->max = i;
			new_sub_set->ebits = (sub_set->ebits | (1<<i));
			
			
			
			/*****<begin>**SUBPROBLEM SPECIFIC******/
			/* S(X,j) = min_k {S(X-k,k) + d[k][j]}*/
			ptr = free_node;
			float current_min = HUGE_VAL;
			float *new_sub_problem;
			float *sub_problem; float local_min;
			unsigned int k1,jstart,jend;
			List *ptr_prev;
			
			new_sub_set->sub_problem = (float *) malloc(sizeof(float)*n);
			new_sub_problem = (float *)new_sub_set->sub_problem;

			if(new_sub_set->size == n-1){
				jstart = 0; jend = 1;
			}else{
				jstart = 1; jend = n;
			}

			for(j=jstart;j<jend;j++){
				ptr = free_node;
				current_min = HUGE_VAL;
				if(new_sub_set->ebits & (1<<j)){
					/*Avoid computation of redundant subproblems like
					 *S({....,x_i,x_j,x_k,....},x_i) */
					new_sub_problem[j]=HUGE_VAL;
					continue;
				}

				for(k=1;k<=new_sub_set->size;k++){
					do{
						check_sub_set = ((SubSet *)ptr->_data)->ebits; 
						check_sub_set ^= new_sub_set->ebits; 
						k1 = (int)log2(check_sub_set);
						ptr_prev = ptr;
						ptr=ptr->next;
					}while(check_sub_set & (check_sub_set-1));
					sub_problem = (float *)((SubSet *)ptr_prev->_data)->sub_problem;
					local_min = sub_problem[k1] + GRAPH[k1][j];

					if(local_min < current_min){
						current_min = local_min; 
						new_sub_problem[j] = current_min;
					}

				}
			}
			/*Print Solution to the Subproblem */
			unsigned int i1,istart,iend;
			unsigned int j1;
			
			for(i1=jstart;i1<jend;i1++){
				check_sub_set = new_sub_set->ebits;
				if(check_sub_set & (1<<i1)){ continue; }
				printf("S(%u,{ ",i1+1);
				/*Get the elements back*/
				for(j1=0;j1<n;j1++){
					if(check_sub_set & (1<<j1)){
						printf(" %u ",j1+1);
					}
				}
				printf("})=%f\n",((float *)(new_sub_set->sub_problem))[i1]);
			}
			/**********<END>***SUBPROBLEM SPECIFIC*************/


			tail = ListAppend(&tail,(void *)new_sub_set);
		}
		if(!(sub_set >= one_sets && sub_set <= &(one_sets[n-1]))){
			free(sub_set->sub_problem);
			free(sub_set); 
		}
		free(free_node);
	}
	for(i=0;i<n;i++){
		free(one_sets[i].sub_problem);
	}
	free(one_sets);
	printf("SubsetCount=%u\n",subset_count);
}