/*----------------------------------------------------------------------
 * split up color space for quantize program
 *----------------------------------------------------------------------
 */

#include <stdio.h>
#include <std.h>
#include "quantize.h"

/* Pick your choice of algorithm: */
/* MIDPOINT_CUT or POPULARITY */
/* (Choose in makefile) */

#ifdef MIDPOINT_CUT

typedef unsigned int color_index_t;

/* My method here is to allocate a clist array big enough for all the
 * possible colors, and then recursively split it.  Since the recursion
 * is depth-first and we're building a LIST, not a TREE of boxes, we can
 * scramble the colors within a parent box because that parent won't be used
 * any more.  We end up with a list of boxes into which all the existing
 * colors are partitioned, as described in Heckbert's paper.
 */
struct Box {
    struct Box *next;
    int rmin, rmax, gmin, gmax, bmin, bmax;
    color_index_t *clist;	/* an array of color indices */
    int clist_len;		/* how many cindexes in the list */
};

static int nboxes, maxboxes;	/* number of boxes so far and max needed */

MakeCmap(hist, cmap, cmaplen)
unsigned int *hist;
cmap_t *cmap;
int cmaplen;
{
    register int i;
    struct Box *box;
    nboxes = 1;
    maxboxes = cmaplen;
    NEW(box, struct Box, 1);
    dbug0("Making color boxes.\n");
    MakeTopBox(box, hist);	/* Make the first (top-level) box */
    while (nboxes < maxboxes)
    	SplitBoxes(box);
    FindColors(box, cmap, cmaplen);
}

MakeTopBox(box, hist)		/* Make the top box from the histogram */
struct Box *box;
color_index_t *hist;
{
    register int i;
    ASSERT(box != NULL);
    ASSERT(hist != NULL);
    
    /* Allocate enough color cells to hold all the colors */
    NEW(box->clist, color_index_t, HIST_SIZE);
    box->clist_len = 0;
    box->next = NULL;
    /* For each possible rgb color */
    for (i = 0; i < HIST_SIZE; i++)
    {
	if (hist[i] > 0)	/* if any pixels are that color, */
	    box->clist[box->clist_len++] = i;
    }
    Compact(box);
    fprintf(stderr,"Top box at 0x%x: %d colors, R (%d -> %d)  G (%d -> %d)  B (%d -> %d)\n",
	    box, box->clist_len,
	    box->rmin, box->rmax, box->gmin, box->gmax, box->bmin, box->bmax);
}

/* Shrink the box limits until it just encloses the points within it. */
Compact(box)
struct Box *box;
{
    register int i;
    ASSERT(box != NULL);
    box->rmin = 256;
    box->gmin = 256;
    box->bmin = 256;	/* Greater than any value */
    box->rmax = -1;
    box->gmax = -1;
    box->bmax = -1;	/* Less than any rgb value */
    for (i = box->clist_len-1; i >= 0; i--)
    {
	int r = (box->clist[i] >> 10) & 0x1f; /* colors associated with 'i' */
	int g = (box->clist[i] >> 5) & 0x1f;
	int b = (box->clist[i]) & 0x1f;
	/* Expand the box until it just fits the colors tightly */
	if (r < box->rmin) box->rmin = r;
	if (g < box->gmin) box->gmin = g;
	if (b < box->bmin) box->bmin = b;
	if (r > box->rmax) box->rmax = r;
	if (g > box->gmax) box->gmax = g;
	if (b > box->bmax) box->bmax = b;
    }
}

/* Split all the boxes once each, stop if we've got enough */
SplitBoxes(box)
struct Box *box;
{
    struct Box *nextbox;
    dbug1("Splitting all the boxes with %d done so far.\n", nboxes);
    while (box != NULL && nboxes < maxboxes)
    {
	nextbox = box->next;
	SplitBox(box);		/* SplitBox changes box->next! */
	box = nextbox;
    }
}

static char longdim;		/* char representing the longest dimension */

int
CompareColors(c1, c2)
color_index_t *c1, *c2;
{
    switch (longdim)
    {
      case 'r':
	return ((*c1 >> 10 & 0x1f) - (*c2 >> 10 & 0x1f));
      case 'g':
	return ((*c1 >> 5 & 0x1f) - (*c2 >> 5 & 0x1f));
      case 'b':
	return ((*c1 & 0x1f) - (*c2 & 0x1f));
      default:
	fprintf(stderr,"Illegal longdim 0x%x in CompareColors.\n", longdim);
	exit(1);
    }
}

/* Divide the box across its longest dimension at its median point
 * This is NOT recursive - we split all the boxes once, then if there's
 * more colors to be assigned we split all of them again, and so on. */
SplitBox(box)
struct Box *box;
{
    struct Box *newbox;		/* the 'other half' of the split box */
    ASSERT(box != NULL);
    if (nboxes > maxboxes) return;
    if (box->clist_len <= 1) return;
    nboxes++;
    if (box->rmax - box->rmin >= box->gmax - box->gmin &&
	box->rmax - box->rmin >= box->bmax - box->bmin)
	longdim = 'r';
    else
    if (box->gmax - box->gmin >= box->rmax - box->rmin &&
	box->gmax - box->gmin >= box->bmax - box->bmin)
	longdim = 'g';
    else
    if (box->bmax - box->bmin >= box->gmax - box->gmin &&
	box->bmax - box->bmin >= box->rmax - box->rmin)
	longdim = 'b';
    else
    {
	fprintf(stderr,"No longest dimension in SplitBox??!\n");
        fprintf(stderr,"This box: R (%d -> %d)  G (%d -> %d)  B (%d -> %d)\n",
	    box->rmin, box->rmax, box->gmin, box->gmax, box->bmin, box->bmax);
	exit(1);
    }
    qsort(box->clist, box->clist_len, sizeof(color_index_t), CompareColors);
    /* Set up the new box and put it after the old box */
    NEW(newbox, struct Box, 1);
    newbox->next = box->next;
    box->next = newbox;
    /* If len is odd, put the extra one in the old box */
    newbox->clist_len = box->clist_len / 2;
    box->clist_len -= newbox->clist_len;
    newbox->clist = box->clist + box->clist_len;
    Compact(box);
    Compact(newbox);
}

/* Find the representative color in each box and put it into cmap. */
FindColors(box, cmap, cmaplen)	/* here box is a list of boxes */
struct Box *box;
cmap_t *cmap;
int cmaplen;
{
    register int r, g, b;
    register int i;
    int cml = 0;
    while (box != NULL)
    {
	r = 0, g = 0, b = 0;
	for (i=0; i < box->clist_len; i++)
	{
	    r += (box->clist[i] >> 10 & 0x1f) << 3;
	    g += (box->clist[i] >> 5 & 0x1f) << 3;
	    b += (box->clist[i] & 0x1f) << 3;
	}
	ASSERT(r/box->clist_len < 256);
	ASSERT(g/box->clist_len < 256);
	ASSERT(b/box->clist_len < 256);
	cmap[cml*3] = r / box->clist_len;
	cmap[cml*3+1] = g / box->clist_len;
	cmap[cml*3+2] = b / box->clist_len;
	box = box->next;
	cml++;
    }
    ASSERT(cmaplen == cml);	/* since there should be 'cmaplen' boxes */
    for (i = 0; i < cmaplen*3; i+=3)
    {
	printf("Cmap[%4d] = %3d, %3d, %3d\n",
	   i/3, cmap[i], cmap[i+1], cmap[i+2]);
    }
}

#endif

#ifdef POPULARITY
static unsigned int *HiSt;

CompareHist(v1, v2)
int *v1, *v2;
{
    return (HiSt[*v2] - HiSt[*v1]);
}

MakeCmap(hist, cmap, cmaplen)
unsigned int *hist;
cmap_t *cmap;
int cmaplen;
{
    register int i;
    unsigned int *hptrs;
    /* This is the popularity algorithm (Boyle & Lippman, Archmac, 1978) */
    /* First we sort the histogram: set up a bunch of pointers and sort them */
    dbug1("Getting %d ints for hptrs...", HIST_SIZE);
/*  NEW(hptrs, unsigned int, HIST_SIZE);*/
    hptrs = (unsigned int *)quant_image;	/* use existing storage temporarily */
    dbug0("initting it...");
    for (i = 0; i < HIST_SIZE; i++) hptrs[i] = i;
    HiSt = hist;
    dbug0("Sorting...");
    qsort (hptrs, HIST_SIZE, sizeof(unsigned int), CompareHist);
    dbug0("making color map...");
    for (i = 0; i < cmaplen; i++)
    {
	cmap[3*i] = hptrs[i] >> 10 << 3;
	cmap[3*i+1] = (hptrs[i] >> 5 & 0x1f) << 3;
	cmap[3*i+2] = (hptrs[i] & 0x1f) << 3;
    }
    dbug0("done.\n");
    dbug1("Max pixels in one bucket: %d.\n", hist[hptrs[0]]);
}
#endif POPULARITY