/*
	getmap.c	1995-07-02
	ColorMap.m	1995-12-18
		by T.Ogihara (ogihara@seg.kobe-u.ac.jp)

	Checks number of color used in the image.
	Reduces color by median cut algorithm (MCA) of Paul Heckbert.
	This code refers to "ppmquant" of Jef Poskanzer, but, in
	many cases, this program could generate more beautiful image.
*/


#import  "ColorMap.h"
#import  <stdio.h>
#import  <stdlib.h>
#import  <string.h>
#import  <appkit/color.h>
#import  <appkit/Control.h>
#import  "common.h"
#import  "getpixel.h"

#define  EnoughMemory	1

#if EnoughMemory
# define  COLORSTEPS		65536	/* = 0x10000 */
# define  MAXColors		62000	/* < COLORSTEPS */
# define  ColorHash(r,g,b)	( ((r)<<8) | (g) )	/* Hash KEY */
# define  ColorHnew(x)		(((x) + 5987) & 0xffff)
  typedef int indexint;
#else
# define  COLORSTEPS		32768	/* = 32 ^ 3 = 0x8000 */
# define  MAXColors		30000	/* < COLORSTEPS */
# define  ColorHash(r,g,b)	( ((r)<<7) | ((g) & 0x7f) )	/* Hash KEY */
# define  ColorHnew(x)		(((x) + 5987) & 0x7fff)
  typedef short indexint;
#endif

typedef struct {
	int 	count;
	unsigned char red, green, blue;
	unsigned char palidx;	/* index for palette */
} tabcell;

typedef struct {
    int index, colors;
    int sum;
} element;

/* quick sort */
static int q_red(int);
static int q_green(int);
static int q_blue(int);
static int q_colors(int);
static int q_count(int);
static int q_palette(int);
static void inssort(int, indexint *, int (*)(int));
static void quicksort(int, indexint *, int (*)(int));

static int hashIndex(int, int, int);
static void SortMaxElement(int, int);
static void makepalette(element *, int, BOOL);


@implementation ColorMap

static tabcell  *hashtab;
static indexint *pindex;
static paltype  *pal;
static int	colornum;	/* Number of colors used in the image */
static int	totalnum;
static BOOL	hasalpha;


int mapping(int r, int g, int b)
{
	return hashtab[hashIndex(r,g,b)].palidx;
}


- init
{
	hashtab = NULL;
	pindex = NULL;
	pal = NULL;
	return self;
}

- allocFullColor
{
	hashtab = (tabcell *)calloc(COLORSTEPS, sizeof(tabcell));
	pindex = (indexint *)calloc(COLORSTEPS, sizeof(indexint));
	pal = (paltype *)calloc(FIXcount, sizeof(paltype));
	if (!hashtab || !pindex || !pal)
		return nil;
	return self;
}

- allocPalColor
{
	hashtab = (tabcell *)calloc(COLORSTEPS, sizeof(tabcell));
	if (!hashtab)
		return nil;
	return self;
}

- free
{
	if (hashtab) free((void *)hashtab);
	if (pindex) free((void *)pindex);
	if (pal) free((void *)pal);
	[super free];
	return nil;
}

- init_regColor
{
	int i;

	for (i = 0; i < COLORSTEPS; i++)
		pindex[i] = i;
	bzero((void *)hashtab, sizeof(tabcell)*COLORSTEPS);
	colornum = 0;
	totalnum = 0;
	hasalpha = NO;
	return self;
}

- (int)getAllColor:(unsigned char **)map limit:(int)limit alpha:(BOOL *)alpha
	/* 使われている色数を返す。
	   limit は色数の上限で、alpha は色数として考慮しない。
	   limit=0 の時は MAXColors を上限とする。
	   色数が多すぎて数えられない、あるいはもう数える必要がない
	   場合は COLORSTEPS が返され、変数 colornum は０にセットされる。 */
{
	int r, g, b, a;
	int maxclr = MAXColors - 1;

	if (limit > 0) maxclr = limit;
	[self init_regColor];
	resetPixel(map, 0);
	while (getPixel(&r, &g, &b, &a) >= 0) {
		if (a != AlphaTransp) {
			(void)hashIndex(r,g,b);
			if (colornum > maxclr)
				break;	/* Too many color */
		}else hasalpha = YES;
	}
	*alpha = hasalpha;
	if (colornum > maxclr) { /* Too many color */
		colornum = 0;
		return COLORSTEPS;
	}
	return colornum;
}

- (int)getAllColor:(unsigned char **)map limit:(int)limit
	/* 使われている色数を返す。
	   上のメソッドと同じだが、alpha があったら１色（白）として
	   考慮する。alpha値を使わない形式へ変更する場合に使う。 */
{
	BOOL alpha;
	int cnum;
	int maxclr = MAXColors - 1;

	if (limit > 0) maxclr = limit;
	cnum = [self getAllColor:map limit:maxclr alpha:&alpha];
	if (cnum > maxclr)	/* Too many color */
		return COLORSTEPS;
	if (alpha) {
		(void)hashIndex(255, 255, 255);	/* for transparent */
		if ((cnum = colornum) > maxclr) {  /* Too many color */
			colornum = 0;
			return COLORSTEPS;
		}
	}
	return cnum;
}


- (int)regColorToMap: (int)red : (int)green : (int)blue
	/* getAllColor: のように使われている色数を数えるが、１ピクセル
	   ごとに呼び出す。
	   色数が多すぎて数えられない場合は -1 が返され、変数 colornum は
	   ０にセットされる。 */
{
	(void)hashIndex(red, green, blue);
	totalnum++;
	if (colornum >= MAXColors) {
		colornum = 0;
		return -1;
	}
	return colornum;
}

- (int)regPalColorWithAlpha:(BOOL)alpha
	/* パレットの中の色を調べ、ハッシュ表に登録しておく。 */
{
	int r, g, b, idx;
	BOOL hasWhite = NO;

	colornum = 0;
	hasalpha = NO;
	for (idx = 0; getPalPixel(&r, &g, &b) >= 0; idx++) {
		hashtab[hashIndex(r,g,b)].palidx = idx;
		if (!hasWhite && r == 255 && g == 255 && b == 255)
			hasWhite = YES;
	}
	if (!alpha && !hasWhite) {
		if (idx >= FIXcount)
			return (FIXcount + 1);	/* no room */
		hashtab[hashIndex(255,255,255)].palidx = idx++;
	}
	return idx;	/* return number of colors */
}


- (paltype *)getNormalmap:(int *)cnum
	/* getAllColor: の後で使い、パレットを返す。
	   使われている色が 256色以内であること。 */
{
	unsigned char *p;
	tabcell *t;
	int i, x, num;

	quicksort(COLORSTEPS, pindex, q_colors);
	for (i = 0, num = 0; i < COLORSTEPS && num < FIXcount; i++) {
		if (hashtab[x = pindex[i]].count == 0) continue;
		t = &hashtab[x];
		p = pal[num];
		p[RED]   = t->red;
		p[GREEN] = t->green;
		p[BLUE]  = t->blue;
		t->palidx = num++;
	}
	*cnum = num;
	return pal;
}


- (paltype *)getReducedMap:(int *)cnum alpha:(BOOL)alpha
	/* Median Cut Algorithm */
{
	int i, w;
	element elm[FIXcount];
	int ncolors, elmptr, curelm;
	int indx, clrs, sm;
	int halfsum, lowersum;

	ncolors = *cnum;
	if (ncolors < 2 || ncolors > FIXcount)
		ncolors = FIXcount;
	if (alpha) ncolors--; 
	quicksort(COLORSTEPS, pindex, q_count);
	for (i = 0; i < COLORSTEPS; i++)
		if (hashtab[pindex[i]].count) break;
	elm[0].index = i;
	elm[0].colors = COLORSTEPS - i;
	elm[0].sum = totalnum;
	elmptr = 1;
    
	while (elmptr < ncolors) {
		/* Find largest element */
		curelm = -1;
		w = 2;	/* should be divided */
		for (i = 0; i < elmptr; i++) {
			if (elm[i].colors >= w)
				w = elm[curelm = i].colors;
		}
		if (curelm < 0)
			break;	/* all color was found */
		indx = elm[curelm].index;
		clrs = elm[curelm].colors;
		sm = elm[curelm].sum;
		SortMaxElement(indx, clrs);

		/* Find the median */
		w = clrs - 1;
		lowersum = 0;
		halfsum = sm / 2;
		for (i = 0; i < w && lowersum < halfsum; i++)
			lowersum += hashtab[pindex[indx + i]].count;

		/* Divide the box */
		elm[curelm].colors = i;
		elm[curelm].sum = lowersum;
		elm[elmptr].index = indx + i;
		elm[elmptr].colors = clrs - i;
		elm[elmptr].sum = sm - lowersum;
		++elmptr;
	}

	makepalette(elm, elmptr, alpha);
	*cnum = elmptr;
	return pal;
}

- (paltype *)getPalette
{
	paltype *p = pal;
	pal = NULL;
	return p;
}

@end


static int hashIndex(int r, int g, int b)
{
	tabcell *tp;
	int x = ColorHash(r,g,b);

	tp = &hashtab[x];
	while (tp->count > 0
	    && (tp->red != r || tp->green != g || tp->blue != b))
		tp = &hashtab[x = ColorHnew(x)];
	if (tp->count == 0) {
		tp->red = r;
		tp->green = g;
		tp->blue = b;
		colornum++;
	}
	tp->count++;
	return x;
}

static void SortMaxElement(int indx, int clrs)
{
	int i, j, end;
	unsigned short min[3], max[3], val[3];
	float bright[3];
	tabcell *t;

	/* Find the minimum and maximum of each component */
	for (i = 0; i < 3; i++)
		min[i] = 255, max[i] = 0;
	end = indx + clrs;
	for (i = indx; i < end; i++) {
		t = &hashtab[pindex[i]];
		if (t->count == 0)
			continue;
		val[RED]   = t->red;
		val[GREEN] = t->green;
		val[BLUE]  = t->blue;
		for (j = 0; j < 3; j++) {
			if (min[j] > val[j]) min[j] = val[j];
			if (max[j] < val[j]) max[j] = val[j];
		}
	}
	/* calculate brightness */
	bright[RED] = (max[RED] - min[RED]) * 0.299;
	bright[GREEN] = (max[GREEN] - min[GREEN]) * 0.587;
	bright[BLUE] = (max[BLUE] - min[BLUE]) * 0.114;
	if ( bright[RED] >= bright[GREEN] && bright[RED] >= bright[BLUE] )
		quicksort(clrs, &pindex[indx], q_red);
	else if ( bright[GREEN] >= bright[BLUE] )
		quicksort(clrs, &pindex[indx], q_green);
	else
		quicksort(clrs, &pindex[indx], q_blue);
}

static void makepalette(element *elm, int cellnum, BOOL alpha)
{
	int indx, clrs, i, ex, best;
	long r, g, b, w, sum;
	unsigned char *p;
	tabcell *t;

	for (ex = 0; ex < cellnum; ex++) {
		indx = elm[ex].index;
		clrs = elm[ex].colors;
		r = g = b = 0, sum = 0;
		p = pal[ex];

		w = indx + clrs;
		for (i = indx; i < w; i++) {
			int c = (t = &hashtab[pindex[i]])->count;
			r += t->red * c;
			g += t->green * c;
			b += t->blue * c;
			sum += c;
		}
		p[RED]   = ((r /= sum) < 256) ? r : 255;
		p[GREEN] = ((g /= sum) < 256) ? g : 255;
		p[BLUE]  = ((b /= sum) < 256) ? b : 255;
	}
	/* Values of pindex[] are not used any more.
	   Sort the palette. */
	for (i = 0; i < cellnum; i++)
		pindex[i] = i;
	quicksort(cellnum, pindex, q_palette);
	for (ex = 0; ex < cellnum; ex++) {
		unsigned char *q;
		int x, y;
		x = pindex[ex];
		if (ex == x) continue;
		for (y = ex+1; y < cellnum; y++)
			if (pindex[y] == ex) break;
		p = pal[x];
		q = pal[ex];
		for (i = 0; i < 3; i++)
			r = p[i], p[i] = q[i], q[i] = r;
		pindex[ex] = ex;
		pindex[y] = x;
	}
	if (alpha /* && cellnum < FIXcount */) {
		p = pal[cellnum];
		for (i = 0; i < 3; i++)
			p[i] = 255;
	}
	
	for (i = 0; i < COLORSTEPS; i++) {
		if (hashtab[i].count == 0) continue;
		t = &hashtab[i];
		r = t->red;
		g = t->green;
		b = t->blue;
		w = 4 * 256 * 256;
		best = 0;
		for (ex = 0; ex < cellnum; ex++) {
			long rr, gg, bb;
			p = pal[ex];
			rr = r - p[RED];
			gg = g - p[GREEN];
			bb = b - p[BLUE];
			if ((sum = rr*rr + gg*gg + bb*bb) < w)
				w = sum, best = ex;
		}
		t->palidx = best;
	}
}

/* ----------------------------------------------------------------
	QUICK SORT by Haruhiko Okumura
	奥村晴彦「Ｃ言語による最新アルゴリズム事典」（技術評論社）
	modified by T. Ogihara
----------------------------------------------------------------- */

static int q_red(int x) { return hashtab[x].red; }
static int q_green(int x) { return hashtab[x].green; }
static int q_blue(int x) { return hashtab[x].blue; }
static int q_count(int x) { return hashtab[x].count; }
static int q_colors(int x) {
	tabcell *t = &hashtab[x];
	return (t->count)
		? ((t->red << 16) | (t->green << 8) | t->blue) : 0;
}
static int q_palette(int x) {
	unsigned char *p = pal[x];
	return ((p[RED] << 16) | (p[GREEN] << 8) | p[BLUE]);
}

static void inssort(int n, indexint *a, int (*qval)(int))
{
	int i, j, val;
	indexint x;

	for (i = 1; i < n; i++) {
		val = qval(x = a[i]);
		for (j = i - 1; j >= 0 && qval(a[j]) > val; j--)
			a[j + 1] = a[j];
		a[j + 1] = x;
	}
}

#define QS_THRESHOLD	10
#define QS_STACKSIZE	32	/* たかだか int のビット数程度 */

static void quicksort(int n, indexint *ar, int (*qval)(int))
{
	int i, j, left, right, p;
	int leftstack[QS_STACKSIZE], rightstack[QS_STACKSIZE];
	indexint t;
	int x;

	left = 0;  right = n - 1;  p = 0;
	for ( ; ; ) {
		if (right - left <= QS_THRESHOLD) {
			if (p == 0) break;
			p--;
			left = leftstack[p];
			right = rightstack[p];
		}
		x = qval(ar[(left + right) / 2]);
		i = left;  j = right;
		for ( ; ; ) {
			while (qval(ar[i]) < x) i++;
			while (x < qval(ar[j])) j--;
			if (i >= j) break;
			t = ar[i];  ar[i] = ar[j];  ar[j] = t;
			i++;  j--;
		}
		if (i - left > right - j) {
			if (i - left > QS_THRESHOLD) {
				leftstack[p] = left;
				rightstack[p] = i - 1;
				p++;
			}
			left = j + 1;
		} else {
			if (right - j > QS_THRESHOLD) {
				leftstack[p] = j + 1;
				rightstack[p] = right;
				p++;
			}
			right = i - 1;
		}
	}
	inssort(n, ar, qval);
}
