//#include <windows.h>

//#include <>

#include "quantize.h"
/////////////////////////////////////////////////////////////////////////////
CQuantizer::CQuantizer (uint nMaxColors, uint nColorBits)
{
//	m_nColorBits = nColorBits < 8 ? nColorBits : 8;
	m_nColorBits = nColorBits;

	m_pTree	= NULL;
	m_nLeafCount = 0;
	for	(int i=0; i<=(int) m_nColorBits; i++)
		m_pReducibleNodes[i] = NULL;
	m_nMaxColors = m_nOutputMaxColors = nMaxColors;
//	if (m_nMaxColors<16) m_nMaxColors=16;
}
/////////////////////////////////////////////////////////////////////////////
CQuantizer::~CQuantizer	()
{
	if (m_pTree	!= NULL)
		DeleteTree (&m_pTree);
}
/////////////////////////////////////////////////////////////////////////////
//BOOL CQuantizer::ProcessImage (HANDLE hImage)
bool CQuantizer::ProcessImage (QImage &theImage)
{
	BYTE r,	g, b, a;
	int  i, j;
	QRgb rgb;

printf ("CQuantizer::ProcessImage depth<%d>\n", theImage.depth());
	for	(i=0; i<theImage.height(); i++) {
		for	(j=0; j<theImage.width(); j++)	{

			rgb = theImage.pixel (j, i);
			b = qBlue (rgb);
			g = qGreen(rgb);
			r = qRed(rgb);
			a = qAlpha(rgb);

			AddColor (&m_pTree, r, g, b, a, m_nColorBits, 0, &m_nLeafCount, m_pReducibleNodes);
			while (m_nLeafCount > m_nMaxColors)
				ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
		}
	}

	return TRUE;

}
/////////////////////////////////////////////////////////////////////////////
void CQuantizer::AddColor (NODE** ppNode, BYTE r, BYTE g, BYTE b, BYTE a,
	uint nColorBits, uint nLevel, uint *pLeafCount, NODE** pReducibleNodes)
{
	static BYTE	mask[8]	= {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};

	// If the node doesn't exist, create it.
	if (*ppNode	== NULL)
		*ppNode	= (NODE*)CreateNode (nLevel, nColorBits, pLeafCount, pReducibleNodes);

	// Update color	information	if it's	a leaf node.
	if ((*ppNode)->bIsLeaf)	{
		(*ppNode)->nPixelCount++;
		(*ppNode)->nRedSum   += r;
		(*ppNode)->nGreenSum += g;
		(*ppNode)->nBlueSum  += b;
		(*ppNode)->nAlphaSum += a;
	} else {	// Recurse a level deeper if the node is not a leaf.
		int	shift =	7 -	nLevel;
		int	nIndex =(((r & mask[nLevel]) >> shift) << 2) |
				 (((g & mask[nLevel]) >>	shift) << 1) |
				 (( b & mask[nLevel]) >> shift);
		AddColor (&((*ppNode)->pChild[nIndex]), r, g, b, a, nColorBits, nLevel + 1, pLeafCount, pReducibleNodes);
	}
}
/////////////////////////////////////////////////////////////////////////////
void* CQuantizer::CreateNode (uint nLevel, uint	nColorBits,	uint* pLeafCount,
	NODE** pReducibleNodes)
{
	NODE* pNode = (NODE*)calloc(1,sizeof(NODE));

	if (pNode== NULL) return NULL;

	pNode->bIsLeaf = (nLevel ==	nColorBits)	? TRUE : FALSE;
	if (pNode->bIsLeaf) (*pLeafCount)++;
	else {
		pNode->pNext = pReducibleNodes[nLevel];
		pReducibleNodes[nLevel]	= pNode;
	}
	return pNode;
}
/////////////////////////////////////////////////////////////////////////////
void CQuantizer::ReduceTree (uint nColorBits, uint *pLeafCount, NODE** pReducibleNodes)
{
	int i;
	// Find	the	deepest	level containing at	least one reducible	node.
	for	(i=nColorBits -	1; (i>0) &&	(pReducibleNodes[i]	== NULL); i--);

	// Reduce the node most	recently added to the list at level	i.
	NODE* pNode	= pReducibleNodes[i];
	pReducibleNodes[i] = pNode->pNext;

	uint nRedSum = 0;
	uint nGreenSum = 0;
	uint nBlueSum =	0;
	uint nAlphaSum = 0;
	uint nChildren = 0;

	for	(i=0; i<8; i++)	{
		if (pNode->pChild[i] !=	NULL) {
			nRedSum	+= pNode->pChild[i]->nRedSum;
			nGreenSum += pNode->pChild[i]->nGreenSum;
			nBlueSum +=	pNode->pChild[i]->nBlueSum;
			nAlphaSum += pNode->pChild[i]->nAlphaSum;
			pNode->nPixelCount += pNode->pChild[i]->nPixelCount;
			free(pNode->pChild[i]);
			pNode->pChild[i] = NULL;
			nChildren++;
		}
	}

	pNode->bIsLeaf = TRUE;
	pNode->nRedSum = nRedSum;
	pNode->nGreenSum = nGreenSum;
	pNode->nBlueSum	= nBlueSum;
	pNode->nAlphaSum	= nAlphaSum;
	*pLeafCount	-= (nChildren -	1);
}
/////////////////////////////////////////////////////////////////////////////
void CQuantizer::DeleteTree	(NODE**	ppNode)
{
	for	(int i=0; i<8; i++)	{
		if ((*ppNode)->pChild[i] !=	NULL) DeleteTree (&((*ppNode)->pChild[i]));
	}
	free(*ppNode);
	*ppNode	= NULL;
}
/////////////////////////////////////////////////////////////////////////////
//void CQuantizer::GetPaletteColors (NODE* pTree,	RGBQUAD* prgb, uint* pIndex, uint* pSum)
void CQuantizer::GetPaletteColors (NODE* pTree,	QColor* prgb, uint* pIndex, uint* pSum)
{
	int iRed, iGreen, iBlue, iAlpha;
	if (pTree){
		if (pTree->bIsLeaf)	{
			iRed   = (BYTE)((pTree->nRedSum)/(pTree->nPixelCount));
			iGreen = (BYTE)((pTree->nGreenSum)/(pTree->nPixelCount));
			iBlue  = (BYTE)((pTree->nBlueSum)/(pTree->nPixelCount));
			iAlpha = (BYTE)((pTree->nAlphaSum)/(pTree->nPixelCount));
			prgb[*pIndex].setRgb(iRed, iGreen, iBlue);
			if (pSum) pSum[*pIndex] = pTree->nPixelCount;
			(*pIndex)++;
		} else {
			for	(int i=0; i<8; i++)	{
				if (pTree->pChild[i] !=	NULL)
					GetPaletteColors (pTree->pChild[i],	prgb, pIndex, pSum);
			}
		}
	}
}
/////////////////////////////////////////////////////////////////////////////
uint CQuantizer::GetColorCount ()
{
	return m_nLeafCount;
}
/////////////////////////////////////////////////////////////////////////////
//void CQuantizer::SetColorTable (RGBQUAD* prgb)
void CQuantizer::SetColorTable (QColor* prgb)
{
	int iRed, iGreen, iBlue, iAlpha;
	uint t, nIndex = 0;
	if (m_nOutputMaxColors<16){
		uint nSum[16];
//		RGBQUAD tmppal[16];
		QColor tmppal[16];
		GetPaletteColors (m_pTree, tmppal, &nIndex, nSum);
		if (m_nLeafCount>m_nOutputMaxColors) {
			uint j,k,nr,ng,nb,na,ns,a,b;
			for (j=0;j<m_nOutputMaxColors;j++){
				a=(j*m_nLeafCount)/m_nOutputMaxColors;
				b=((j+1)*m_nLeafCount)/m_nOutputMaxColors;
				nr=ng=nb=na=ns=0;
				for (k=a;k<b;k++){
					nr+=tmppal[k].red  () * nSum[k];
					ng+=tmppal[k].green() * nSum[k];
					nb+=tmppal[k].blue () * nSum[k];
//					na+=tmppal[k].rgbReserved * nSum[k];
					ns+= nSum[k];
				}
				iRed = nr/ns;
				iGreen = ng/ns;
				iBlue = nb/ns;
//				prgb[j].rgbReserved = na/ns;
				prgb[j].setRgb(iRed, iGreen, iBlue);
			}
		} else {
//			memcpy(prgb,tmppal,m_nLeafCount * sizeof(RGBQUAD));
			for (t=0;t<m_nLeafCount;t++)
				prgb[t] = tmppal[t];
		}
	} else {
		GetPaletteColors (m_pTree, prgb, &nIndex, 0);
	}
}
/////////////////////////////////////////////////////////////////////////////
BYTE CQuantizer::GetPixelIndex(long x, long y, int nbit, long effwdt, BYTE *pimage)
{
	if (nbit==8){
		return pimage[y*effwdt + x];
	} else {
		BYTE pos;
		BYTE iDst= pimage[y*effwdt + (x*nbit >> 3)];
		if (nbit==4){
			pos = (BYTE)(4*(1-x%2));
			iDst &= (0x0F<<pos);
			return (iDst >> pos);
		} else if (nbit==1){
			pos = (BYTE)(7-x%8);
			iDst &= (0x01<<pos);
			return (iDst >> pos);
		}
	}
	return 0;
}