package charactermanaj.graphics.filters;

/**
 * 伺か用のPNG256インデックスカラー用に使う「予定」の減色アルゴリズム.以下URLより借用。
 * http://himitsu.jpn.ph/yomimono/java/genshoku/rtreducecolor.html
 * 
 * @author ukei CQuantizer (c) 1996-1997 Jeff Prosise
 * 
 * 31/08/2003 Davide Pizzolato - www.xdp.it
 * 
 * パレット最適化を行うクラス。 Jeff Prosise氏のCQuantizerからの移植。
 * Javaの命名規則と違うのは元のソースがC++なため。
 */

public class ColorQuantizer {
	protected static class RGBQUAD {
		public int rgbBlue;
		public int rgbGreen;
		public int rgbRed;
		public int rgbReserved;
	}

	protected static class NODE {
		public boolean bIsLeaf; // TRUE if node has no children
		public int nPixelCount; // Number of pixels represented by this leaf
		public int nRedSum; // Sum of red components
		public int nGreenSum; // Sum of green components
		public int nBlueSum; // Sum of blue components
		public int nAlphaSum; // Sum of alpha components
		public NODE[] pChild; // Pointers to child nodes
		public NODE pNext; // Pointer to next reducible node

		NODE() {
			pChild = new NODE[8];
		}
	}

	// Cのダブルポインタの代用
	protected static class NodePointer {
		public NodePointer(NODE v) {
			value = v;
		}

		public NODE value;
	}

	protected static class IntPointer {
		public IntPointer(int v) {
			value = v;
		}

		public int value;
	}

	NODE m_pTree;
	int m_nLeafCount;
	NODE[] m_pReducibleNodes;
	int m_nMaxColors;
	int m_nOutputMaxColors;
	int m_nColorBits;

	public ColorQuantizer(int nMaxColors, int nColorBits) {
		m_pReducibleNodes = new NODE[9];

		m_nColorBits = nColorBits < 8 ? nColorBits : 8;

		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;
	}

	public void finalize() {
		if (m_pTree != null) {
			NodePointer pm_pTree = new NodePointer(m_pTree);
			DeleteTree(pm_pTree);
			m_pTree = pm_pTree.value;
		}
	}

	/**
	 * 
	 * @param pbBits
	 *            A31-24 R23-16 G15-8 B7-0の32ビットが１要素の配列
	 * @param pal
	 *            ARGB各8ビットのパレット配列
	 * @param biWidth
	 * @param biHeight
	 * @param biBitCount
	 * @param biClrUsed
	 * @return
	 */
	public boolean ProcessImage(int[] pbBits, int[] pal, int biWidth,
			int biHeight, int biBitCount, long biClrUsed) {
		int r, g, b, a;
		int i, j, arypos = 0;

		int effwdt = ((((biBitCount * biWidth) + 31) / 32) * 4);

//		int nPad = effwdt - (((biWidth * biBitCount) + 7) / 8);

		switch (biBitCount) {

		case 1: // 1-bit DIB
		case 4: // 4-bit DIB
		case 8: // 8-bit DIB
			for (i = 0; i < biHeight; i++) {
				for (j = 0; j < biWidth; j++) {
					int idx = GetPixelIndex(j, i, biBitCount, effwdt, pbBits);
					b = pal[idx] & 0xFF;
					g = (pal[idx] >> 8) & 0xFF;
					r = (pal[idx] >> 16) & 0xFF;
					a = (pal[idx] >> 24) & 0xFF;

					IntPointer pm_nLeafCount = new IntPointer(m_nLeafCount);
					NodePointer pm_pTree = new NodePointer(m_pTree);
					AddColor(pm_pTree, r, g, b, a, m_nColorBits, 0,
							pm_nLeafCount, m_pReducibleNodes);
					m_pTree = pm_pTree.value;
					m_nLeafCount = pm_nLeafCount.value;

					while (m_nLeafCount > m_nMaxColors) {
						pm_nLeafCount.value = m_nLeafCount;
						ReduceTree(m_nColorBits, pm_nLeafCount,
								m_pReducibleNodes);
						m_nLeafCount = pm_nLeafCount.value;
					}
				}
			}

			break;
		case 24: // 24-bit DIB
		case 32:
			for (i = 0; i < biHeight; i++) {
				for (j = 0; j < biWidth; j++) {
					b = pbBits[arypos] & 0xFF;
					g = (pbBits[arypos] >> 8) & 0xFF;
					r = (pbBits[arypos] >> 16) & 0xFF;
					if (biBitCount == 32)
						a = (pbBits[arypos] >> 24) & 0xFF;
					else
						a = 255;
					arypos++;

					IntPointer pm_nLeafCount = new IntPointer(m_nLeafCount);
					NodePointer pm_pTree = new NodePointer(m_pTree);
					AddColor(pm_pTree, r, g, b, a, m_nColorBits, 0,
							pm_nLeafCount, m_pReducibleNodes);
					m_pTree = pm_pTree.value;
					m_nLeafCount = pm_nLeafCount.value;

					while (m_nLeafCount > m_nMaxColors) {
						pm_nLeafCount.value = m_nLeafCount;
						ReduceTree(m_nColorBits, pm_nLeafCount,
								m_pReducibleNodes);
						m_nLeafCount = pm_nLeafCount.value;
					}
				}
				// オリジナルのソースはパディングを行うが、
				// ここでは横幅のバイト数とメモリ上のバイト数を同じとして扱うので
				// パディングを行わない
				// arypos += nPad;
			}
			break;

		default: // Unrecognized color format
			return false;
		}
		return true;
	}

	/**
	 * 色の追加
	 * 
	 * @param ppNode
	 * @param r
	 * @param g
	 * @param b
	 * @param a
	 * @param nColorBits
	 * @param nLevel
	 * @param pLeafCount
	 * @param pReducibleNodes
	 * @return
	 */
	void AddColor(NodePointer ppNode, int r, int g, int b, int a,
			int nColorBits, int nLevel, IntPointer pLeafCount,
			NODE[] pReducibleNodes) {
		short[] mask = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };

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

		// Update color information if it's a leaf node.
		if (ppNode.value.bIsLeaf) {
			ppNode.value.nPixelCount++;
			ppNode.value.nRedSum += r;
			ppNode.value.nGreenSum += g;
			ppNode.value.nBlueSum += b;
			ppNode.value.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);

			NodePointer ppChildNode = new NodePointer(
					ppNode.value.pChild[nIndex]);
			AddColor(ppChildNode, r, g, b, a, nColorBits, nLevel + 1,
					pLeafCount, pReducibleNodes);
			ppNode.value.pChild[nIndex] = ppChildNode.value;
		}
	}

	NODE CreateNode(int nLevel, int nColorBits, IntPointer pLeafCount,
			NODE[] pReducibleNodes) {
		NODE pNode = new NODE();

		pNode.bIsLeaf = (nLevel == nColorBits) ? true : false;
		if (pNode.bIsLeaf)
			pLeafCount.value++;
		else {
			pNode.pNext = pReducibleNodes[nLevel];
			pReducibleNodes[nLevel] = pNode;
		}
		return pNode;
	}

	void ReduceTree(int nColorBits, IntPointer 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;

		int nRedSum = 0;
		int nGreenSum = 0;
		int nBlueSum = 0;
		int nAlphaSum = 0;
		int 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.value -= (nChildren - 1);
	}

	void DeleteTree(NodePointer ppNode) {
		/*
		 * for (int i=0; i<8; i++) { if ((*ppNode)->pChild[i] != null)
		 * DeleteTree (&((*ppNode)->pChild[i])); } free(*ppNode);ppNode = null;
		 */
		ppNode.value = null;
	}

	void GetPaletteColors(NODE pTree, RGBQUAD[] prgb, IntPointer pIndex,
			int[] pSum) {
		if (pTree != null) {
			if (pTree.bIsLeaf) {
				prgb[pIndex.value].rgbRed = (short) ((pTree.nRedSum) / (pTree.nPixelCount));
				prgb[pIndex.value].rgbGreen = (short) ((pTree.nGreenSum) / (pTree.nPixelCount));
				prgb[pIndex.value].rgbBlue = (short) ((pTree.nBlueSum) / (pTree.nPixelCount));
				prgb[pIndex.value].rgbReserved = (short) ((pTree.nAlphaSum) / (pTree.nPixelCount));
				if (pSum != null)
					pSum[pIndex.value] = pTree.nPixelCount;
				pIndex.value++;
			} else {
				for (int i = 0; i < 8; i++) {
					if (pTree.pChild[i] != null)
						GetPaletteColors(pTree.pChild[i], prgb, pIndex, pSum);
				}
			}
		}
	}

	int GetColorCount() {
		return m_nLeafCount;
	}

	public void SetColorTable(byte[] pr, byte[] pg, byte[] pb) {
		int nIndex = 0;
		if (m_nOutputMaxColors < 16) {
			int col;
			int[] nSum = new int[16];
			RGBQUAD[] tmppal = new RGBQUAD[16];
			for (col = 0; col < tmppal.length; col++)
				tmppal[col] = new RGBQUAD();

			IntPointer pnIndex = new IntPointer(nIndex);
			GetPaletteColors(m_pTree, tmppal, pnIndex, nSum);
			nIndex = pnIndex.value;

			if (m_nLeafCount > m_nOutputMaxColors) {
				int 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].rgbRed * nSum[k];
						ng += tmppal[k].rgbGreen * nSum[k];
						nb += tmppal[k].rgbBlue * nSum[k];
						na += tmppal[k].rgbReserved * nSum[k];
						ns += nSum[k];
					}
					col = nr / ns;
					pr[j] = (byte) (col < 128 ? col : 254 - col); // 2の補数
					col = ng / ns;
					pg[j] = (byte) (col < 128 ? col : 254 - col);
					col = nb / ns;
					pb[j] = (byte) (col < 128 ? col : 254 - col);
				}
			} else {
				int j;
				for (j = 0; j < m_nLeafCount; j++) {
					pr[j] = (byte) tmppal[j].rgbRed;
					pg[j] = (byte) tmppal[j].rgbGreen;
					pb[j] = (byte) tmppal[j].rgbBlue;
				}
				// memcpy(prgb,tmppal,m_nLeafCount * sizeof(RGBQUAD));
			}
		} else {
			IntPointer pnIndex = new IntPointer(nIndex);
			RGBQUAD[] tmppal = new RGBQUAD[pr.length];
			for (int col = 0; col < tmppal.length; col++)
				tmppal[col] = new RGBQUAD();
			GetPaletteColors(m_pTree, tmppal, pnIndex, null);
			nIndex = pnIndex.value;

			for (int j = 0; j < m_nLeafCount; j++) {
				pr[j] = (byte) tmppal[j].rgbRed;
				pg[j] = (byte) tmppal[j].rgbGreen;
				pb[j] = (byte) tmppal[j].rgbBlue;
			}
		}
	}

	int GetPixelIndex(int x, int y, int nbit, int effwdt, int[] pimage) {
		if (nbit == 8) {
			return pimage[y * effwdt + x];
		} else {
			int pos;
			int iDst = pimage[y * effwdt + (x * nbit >> 3)];
			if (nbit == 4) {
				pos = (int) (4 * (1 - x % 2));
				iDst &= (0x0F << pos);
				return (iDst >> pos);
			} else if (nbit == 1) {
				pos = (int) (7 - x % 8);
				iDst &= (0x01 << pos);
				return (iDst >> pos);
			}
		}
		return 0;
	}

}
