#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <signal.h>
#include <time.h>
#include <string.h>

typedef unsigned char          byte1;
typedef unsigned short int     byte2;
typedef unsigned int           byte4;
typedef unsigned long long int byte8;

byte1 *t, *ttmp, *ttmptmp;
byte2 *k;
byte2 *c;
byte1 *cc;
byte1 *ties;

int
rnd( int min, int max )
{
	return min + rand() % (max - min);
}

void
fnsh( int sig )
{
	printf("Seconds running: %ld\n", clock() / CLOCKS_PER_SEC);
	free(t); free(ttmp); free(k); free(c); free(cc); free(ties); exit(0);
}

int
main( int argc, char** argv )
{
	int i, j, nf, done, steps, mcc, numpeople, minfriend, maxfriend, numstates;
	int diff, tp, seed;
	float satpercnt;

	numpeople = 40000;
	minfriend = 1;
	maxfriend = 11;
	numstates = 3;
	satpercnt = 0.99;
	seed = -1;

	for( i = 1; i < argc; i++ )
		if(		   !strcmp(argv[i], "-c") ||
				   !strcmp(argv[i], "--node-count")) {
			sscanf(argv[++i], " %d", &numpeople);
		} else if( !strcmp(argv[i], "-n") ||
				   !strcmp(argv[i], "--min-connections") ) {
			sscanf(argv[++i], " %d", &minfriend);
		} else if( !strcmp(argv[i], "-x") ||
				   !strcmp(argv[i], "--max-connections") ) {
			sscanf(argv[++i], " %d", &maxfriend);
			maxfriend++;
		} else if( !strcmp(argv[i], "-s") ||
				   !strcmp(argv[i], "--state-count") ) {
			sscanf(argv[++i], " %d", &numstates);
		} else if( !strcmp(argv[i], "-p") ||
				   !strcmp(argv[i], "--satisfaction") ) {
			sscanf(argv[++i], " %f", &satpercnt);
		} else if( !strcmp(argv[i], "-h") ||
				   !strcmp(argv[i], "--help") ) {
			printf(
"Usage: %s [OPTION]...\n"
"I don't want to explain what this does. Read the source.\n"
"  -h, --help                 this mess\n"
"  -r, --rand-seed            use this random seed instead of the time\n"
"  -c, --node-count           total number of nodes\n"
"  -n, --min-connections      minimum number of connections for each node\n"
"  -x, --max-connections      maximum number of connections for each node\n"
"  -s, --state-count          number of states\n"
"  -p, --satisfaction         blah blah\n", argv[0]);
			exit(0);
		} else if( !strcmp(argv[i], "-r") ||
				   !strcmp(argv[i], "--rand-seed") ) {
			sscanf(argv[++i], " %d", &seed);
		} else {
			fprintf(stderr, "Invalid option: %s\nRun %s -h", argv[i], argv[0]);
			exit(1);
		}

	t    = (byte1*) malloc(sizeof(byte1) * numpeople);
	ttmp = (byte1*) malloc(sizeof(byte1) * numpeople);
	k    = (byte2*) malloc(sizeof(byte2) * numpeople * maxfriend);
	c    = (byte2*) malloc(sizeof(byte2) * numstates);
	cc   = (byte1*) malloc(sizeof(byte1) * numstates);
	ties = (byte1*) malloc(sizeof(byte1) * numstates);
	srand(seed > 0 ? seed : time(NULL));
	signal(SIGINT, fnsh);

	// initialize simulation
	diff = done = steps = 0;
	for( i = 0; i < numstates; i++ ) c[i] = 0;
	for( i = 0; i < numpeople; i++ ) {
		t[i] = rnd(0, numstates);
		c[t[i]]++;
		nf = rnd(minfriend, maxfriend);
		for( j = 0; j < maxfriend; j++ )
			k[i * maxfriend + j] = j < nf ? rnd(0, numpeople): 0xFFFF;
	}

	// run simulation
	while( !done ) {
		for( i = 0; i < numstates; i++ ) printf("%6d ", c[i]);
		printf("| %6d | %d\n", steps, diff);
		diff = 0;
		for( i = 0; i < numstates; i++ ) c[i] = 0;
		for( i = 0; i < numpeople; i++ ) {
			for( j = 0; j < numstates; j++ ) cc[j] = 0;
			j = -1;
			while( k[i * maxfriend + ++j] != 0xFFFF )
				cc[t[k[i * maxfriend + j]]]++;
			mcc = tp = ttmp[i] = 0;
			for( j = 0; j < numstates; j++ ) if( cc[j] > mcc ) mcc = cc[j];
			for( j = 0; j < numstates; j++ ) if( cc[j] == mcc ) ties[tp++] = j;
			ttmp[i] = ties[rnd(0, tp)];
			c[ttmp[i]]++;
			if( ttmp[i] != t[i] ) diff++;
		}
		ttmptmp = ttmp;
		ttmp = t;
		t = ttmptmp;

		for( i = 0; i < numstates && !done; i++ )
			if( ((float) c[i]) >= ((float) satpercnt) * ((float) numpeople) )
				done++;
		steps++;
	}
	
	for( i = 0; i < numstates; i++ ) printf("%6d ", c[i]);
	printf("| %6d | %d\n", steps, diff);

	fnsh(0);
	
	return 0;
}