#include <stdlib.h>

#include "md5.h"

#include "p_local.h"
#include "p_mobj.h"
#include "z_zone.h"

#define NUM_STATS 6

typedef struct
{
	int data[NUM_STATS];
} mobjstats_t;

static mobjstats_t *mobjstats = NULL;
static int num_mobjstats = 0;
static int mobjstats_length = 0;

static void AddMobjStat(mobj_t *mobj)
{
	mobjstats_t *new_mobjstats;
	mobjstats_t *newstat;

	// Need to increase the mobjstats array?

	if ((num_mobjstats + 1) > mobjstats_length)
	{
		if (mobjstats_length == 0)
		{
			mobjstats_length = 128;
		}
		else
		{
			mobjstats_length *= 2;
		}

		new_mobjstats = Z_Malloc(sizeof(*mobjstats) * mobjstats_length,
		                         PU_STATIC, NULL);
		memcpy(new_mobjstats, mobjstats,
		       sizeof(*mobjstats) * num_mobjstats);

		if (mobjstats != NULL)
		{
			Z_Free(mobjstats);
		}

		mobjstats = new_mobjstats;
	}

	// Allocate a new mobjstat

	newstat = &mobjstats[num_mobjstats];
	++num_mobjstats;

	// Copy in appropriate data from the mobj_t

	newstat->data[0] = mobj->x;
	newstat->data[1] = mobj->y;
	newstat->data[2] = mobj->z;
	newstat->data[3] = mobj->angle;
	newstat->data[4] = mobj->type;
	newstat->data[5] = mobj->health;
}

// Compare two mobjstats_t structures for sorting.

static int CmpMobjStats(mobjstats_t *st1, mobjstats_t *st2)
{
	int i;

	for (i=0; i<NUM_STATS; ++i)
	{
		if (st1->data != st2->data)
		{
			return st2->data - st1->data;
		}
	}

	return 0;
}

// Sort the mobjstats array.  Quicksort.

static void SortMobjStats(mobjstats_t *array, int length)
{
	mobjstats_t pivot;
	mobjstats_t tmp;
	int list1_length;
	int i;

	// Anything less than two elements cannot be sorted.

	if (length < 2)
	{
		return;
	}

	// Last in the list is the pivot.

	memcpy(&pivot, &array[length - 1], sizeof(pivot));

	// Build up list1 and list2, stored sequentially after each other.
	// list1 < pivot < list2.

	list1_length = 0;

	for (i=0; i<length-1; ++i)
	{
		if (CmpMobjStats(&array[i], &pivot) < 0) 
		{
			// This item is in the wrong list.  Exchange it
			// into list1.

			memcpy(&tmp, &array[i], sizeof(*array));
			memcpy(&array[i], &array[list1_length], sizeof(*array));
			memcpy(&array[list1_length], &tmp, sizeof(*array));

			++list1_length;
		}
	}

	// Move the pivot into place.
	
	memcpy(&array[length - 1], &array[list1_length], sizeof(*array));
	memcpy(&array[list1_length], &pivot, sizeof(*array));

	// Recursively sort.

	SortMobjStats(array, list1_length);
	SortMobjStats(array + list1_length + 1, length - list1_length - 1);
}

static void BuildMobjStats(void)
{
	thinker_t *th;

	// Build the mobjstats array, with data for all objects.

	num_mobjstats = 0;

	for (th = thinkercap.next; th != &thinkercap; th = th->next)
	{
		// Only care about mobj_ts

		if (th->function.acp1 != (actionf_p1) P_MobjThinker)
		{
			continue;
		}

		AddMobjStat((mobj_t *) th);
	}

	// Sort mobjstats array.

	SortMobjStats(mobjstats, num_mobjstats);
}

// Add all mobjstats array into an MD5 hash.

static void HashMobjStats(md5_context_t *md5)
{
	int i, j;

	for (i=0; i<num_mobjstats; ++i)
	{
		for (j=0; j<NUM_STATS; ++j)
		{
			MD5_UpdateInt32(md5, mobjstats[i].data[j]);
		}
	}
}

static void PrintHash(md5_context_t *md5)
{
	md5_digest_t digest;
	int i;

	MD5_Final(digest, md5);

	for (i=0; i<sizeof(digest); ++i)
	{
		printf("%02x", digest[i]);
	}
	printf("\n");
}

static void HashWorld(void)
{
	md5_context_t md5;

	MD5_Init(&md5);

	// Build the mobjstats array with statistics for every object
	// in the game world
	
	BuildMobjStats();

	// Hash into md5 context

	HashMobjStats(&md5);

	PrintHash(&md5);
}