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

#define EDGE_MISSING 0xFFFFFFFF
#define MAX_DIM 32

#define printpath(...)

float p=0.02;
unsigned len_prematch, dim;
unsigned **adj_matrix;
unsigned hop_count = 0, pos[MAX_DIM];	
int ham_dist;

unsigned  bitset(unsigned int num);
void find_prepath(unsigned source, unsigned dest);
unsigned  prematch(unsigned source, unsigned dest);
void print_bitpattern(unsigned dec);
void find_randpath(unsigned source, unsigned dest);
unsigned* greedy_pos(unsigned source,unsigned  dest);
int hamming_dist(unsigned source,unsigned  dest);

int main()
{
	unsigned int i, j, tmp, vertices;
	unsigned int source, dest;
	//printf("Enter Dim of Cube :");
	//scanf("%d ", &dim);
	dim = 9;
	vertices = (1 << dim);

	adj_matrix = (unsigned**)malloc(vertices*sizeof(unsigned *));

	for(i=0;i<vertices;i++)
		adj_matrix[i] = (unsigned*) malloc(dim * sizeof(unsigned));

	tmp = 0x1;
	//printf("\t\tAdjacency Matrix\t\t\n\n");
	//printf("Vertex\t--------------Neighbours-----------------\n");
	for(i=0;i<vertices;i++)
	{
		//printf("\n%d", i);
		
		for(j=0 ;j<dim; j++)
		{
			adj_matrix[i][j] = i ^ (tmp << j);
			//printf("\t%d", adj_matrix[i][j]);
		}
	}
	printf("\n");

	while(p<0.26)
	{
		for(i=0;i<1000;i++)
		{
			//printf("\nEnter source and destination: ");
			scanf("%d %d", &source, &dest);
			printf("\t\t%d %d\n", source, dest);
			//fflush(NULL);
			/*
			   printf("\nbit pattern of source ");
			   print_bitpattern(source);
			   printf("\nbit pattern of dest ");
			   print_bitpattern(dest);
			   */

			srand(time(NULL));
			//pos = greedy_pos(source, dest);
			//find_randpath(source, dest);
			ham_dist = hamming_dist(source, dest);
			find_prepath(source, dest);
		}
		p+=0.02;
		//sleep(1);
	}

	return 0;
}

/* function to find the neighbours in greedy path */
unsigned* greedy_pos(unsigned source,unsigned  dest)
{
	unsigned result;

	int i, count=0;

	for(i=0; i < MAX_DIM; i ++)
		pos[i] = EDGE_MISSING;

	result = source ^ dest;

	for(i=0;i<MAX_DIM;i++)
	{
		if((result & 0x1))
			pos[count++] = i;
		result >>= 1;

	}

	return pos;
}

int hamming_dist(unsigned source,unsigned  dest)
{
	unsigned result;

	int i, count=0;

	result = source ^ dest;

	for(i=0;i<MAX_DIM;i++)
	{
		if((result & 0x1))
			count++;
		result >>= 1;

	}

	return count;
}

void find_randpath(unsigned source, unsigned dest)
{
	int neigh_count=0, i, random;
	if(source == dest)
	{
		printpath("%d\n",dest);
		printf("\nno of hops = %d\n", hop_count);
		hop_count = 0;
		return;
	}

	for(i=0; i < dim; i++)
		if(adj_matrix[source][i] != EDGE_MISSING) neigh_count++;

	random = (int) (neigh_count * (rand() / (RAND_MAX + 1.0)));

	hop_count++;
	printpath("%d->", source);
	find_randpath(adj_matrix[source][random], dest);

	return;
}

void print_bitpattern(unsigned dec)
{
	int n,i=0,a[MAX_DIM], pad;
	do
	{
		a[i]=dec%2;
		dec=dec/2;
		i++;
	}while(dec!=0);
	pad = dim - i;

	for(n=0;n<pad;n++) printf("0");
	for(n=i-1;n>=0;n--)
		printf("%d",a[n]);

}

void find_prepath(unsigned source, unsigned dest)
{
	unsigned i;

	int random, neigh_count=0;
	unsigned *temp, *pos;

	if(source == dest) 
	{
		printpath("%d\n", dest);
		//hop_count++;
		printf("%f %f\n", p, (float)hop_count/ham_dist);
		hop_count = 0;
		return;
	}

	random = (int) (100.0 * rand() /(RAND_MAX + 1.0));

	if(random < 100*p)
	{
		temp = (unsigned *)malloc(dim*sizeof(unsigned));
		for(i=0; i < dim; i++)
		{
			if(adj_matrix[source][i] != EDGE_MISSING)
			{
				neigh_count++;
				temp[neigh_count] = adj_matrix[source][i];
			}
		}

		random = (int) (neigh_count * (rand() / (RAND_MAX + 1.0)));

		hop_count++;
		printpath("%d->", source);
		find_prepath(temp[random], dest);
		free(temp);
		return;

	}
	else
	{
		pos = greedy_pos(source, dest);

		for(i=0;pos[i] != EDGE_MISSING;i++)
		{
			if(adj_matrix[source][pos[i]] != EDGE_MISSING)
			{
				hop_count++;
				printpath("%d->", source);
				find_prepath(adj_matrix[source][pos[i]], dest);
				return;
			}
		}
		temp = (unsigned *)malloc(dim*sizeof(unsigned));
		for(i=0; i < dim; i++)
		{
			if(adj_matrix[source][i] != EDGE_MISSING)
			{
				neigh_count++;
				temp[neigh_count] = adj_matrix[source][i];
			}
		}

		random = (int) (neigh_count * (rand() / (RAND_MAX + 1.0)));

		hop_count++;
		printpath("%d->", source);
		find_prepath(temp[random], dest);
		free(temp);
		return;
	}

	/* Prefix based routing 
	   if(adj_matrix[source][len_prematch] != EDGE_MISSING) 
	   {
	   hop_count++;
	   find_prepath(adj_matrix[source][len_prematch], dest);
	   return;
	   }
	   */

}

unsigned  prematch(unsigned source, unsigned dest)
{
	unsigned num_zero=0, i;
	unsigned result;

	result = source ^ dest;
	result <<= MAX_DIM-dim;

	for(i=0;i<dim;i++)
	{
		/* printf("\nresult bit pattern ");
		   print_bitpattern(result);
		   printf("\n");
		   */
		if(!(result & 0x80000000))
		{
			num_zero++;
		}
		else return num_zero;
		result <<= 1;
	}

	return num_zero;
}

unsigned bitset(unsigned int num)
{
	unsigned count=0, i;

	for(i=0;i<dim;i++)
	{
		if(num & 0x1) count ++;
		num >>= 1;
	}

	return count;
}