#include "dkdata.h"

static color_t *Brute_FindClosestRGB(colorList_t *clist, color_t *cur, float *dist)
{
	color_t *p;
	color_t *found = NULL;
	float sq2 = 9999999.0;
	float sq1;

	for (p = clist->colorHead; p != NULL; p = p->n)
	{
		// don't include ourselves
		if (p == cur) continue;

		// don't reduce permenant nodes
		if (p->flags & CF_Perm) continue;

		// find least square
		sq1 = ( ((p->r - cur->r) * (p->r - cur->r)) +
			    ((p->g - cur->g) * (p->g - cur->g)) +
				((p->b - cur->b) * (p->b - cur->b)) );

		if (sq1 < sq2)
		{
			sq2   = sq1;
			found = p;
		}
	}

	*dist  = sq2;
	return(found);
}


static void Brute_FindClosest(colorList_t *clist, color_t **p, color_t **q)
{
	color_t *cur, *close;
	float dist;

	// ok get distances between all points
	for (cur = clist->colorHead; cur != NULL; cur = cur->n)
	{
		// don't reduce perm nodes
		if (cur->flags & CF_Perm) 
		{
			cur->close = NULL;
			continue;
		}

		// find closest point to me, get dist too
		cur->close = Brute_FindClosestRGB(clist, cur, &dist);
		cur->dist  = dist;
	}

	dist  = 9999999.0;
	close = NULL;

	// find two points with least distance
	for (cur = clist->colorHead; cur != NULL; cur = cur->n)
	{
		// skip null nodes
		if (!cur->close) continue;

		if (cur->dist < dist)
		{
			dist  = cur->dist;
			close = cur;
		}
	}

	// if close is NULL we have probs
	if (close == NULL)
	{
		Error("Brute_FindClosest failed.");
	}

	// ok we now have the two closest points in rgb space
	// verify it
	*p = close;
	*q = close->close;

	if ((*p)->dist != (*q)->dist)
	{
		Error("Closest points dont have same distance.");
	}
}



static void Brute_AverageRGB(color_t *p, color_t *q)
{
	float r1, g1, b1;
	float r2, g2, b2;
	float r3, g3, b3;
	float count;

	// if p is a perm color then don't touch it
	// if (p->flags & CF_Perm) return;

	if ((p->flags & CF_Perm) || (p->flags & CF_Perm))
	{
		Error("Brute_AverageRGB: Perm node found.");
	}

	r1 = p->r * p->count;
	g1 = p->g * p->count;
	b1 = p->b * p->count;

    r2 = q->r * q->count;
	g2 = q->g * q->count;
	b2 = q->b * q->count;

	// now add in new color
	r3 = r1 + r2;
	g3 = g1 + g2;
	b3 = b1 + b2;

	count = p->count + q->count;

	// save new averaged values
	p->r = r3 / count;
	p->g = g3 / count;
	p->b = b3 / count;

	p->count = count;
}


void Brute_Reduce(colorList_t *clist, int colorGoal)
{
	color_t *p, *q;

    while (clist->colorCount > colorGoal)
	{
		// find the two closest rgb values
		// ignore perm nodes
		Brute_FindClosest(clist, &p, &q);

		// ok merge these two colors together, put result in p
		Brute_AverageRGB(p, q);

		// printf("avg: (%f %f %f)\n", brute[i].r, brute[i].g, brute[i].b);

		// delete q from list
		Color_DelNode(clist, q, 1);

/*
		if (Sys_CheckParm("-v"))
		{
		    printf("Brute: Color count: %d\n", clist->colorCount);
		}
		else
*/
		{
			if ((clist->colorCount % 100) == 0)
			{
				printf("Reduced to %d colors.\n", clist->colorCount);
			}
		}
	}
}
