/*
	Zlib – библиотека сжатия данных общего назначения. Версия 1.1.0
	Это изменённая объектно-ориентированная версия библиотеки, полностью
	совместимая с оригинальной библиотекой.
	
	Copyright © 1995–2005 Jean-loup Gailly и Mark Adler
	Copyright © 2000–2011 ymnk, JCraft, Inc.
	Copyright © 2016, 2019 Малик Разработчик
	
	Эта библиотека поставляется «как есть», без каких-либо явных или
	подразумеваемых гарантий. Ни при каких обстоятельствах авторы не
	несут какой-либо ответственности в случае потери данных вследствие
	использования данной библиотеки.
	
	Разрешается всем использовать эту библиотеку для любых целей, в том
	числе и для коммерческих приложений, а также изменять её и
	распространять свободно при соблюдении следующих условий:
	
		1. Оригинал библиотеки не должен быть искажён; вы не должны
	заявлять, что именно вы написали оригинальную библиотеку. Если вы
	используете эту библиотеку в своём программном продукте, то ссылка
	на авторов библиотеки была бы желательна, но это не является
	обязательным требованием.
	
		2. Изменённые версии исходных текстов должны быть отчётливо
	маркированы и не должны выдаваться за оригинал библиотеки.
	
		3. Эти замечания не могут быть удалены либо изменены при
	каком-либо варианте распространения исходных текстов.
*/


package malik.emulator.compression.zlib;

final class Tree extends Zlib
{
	private static final int MAX_BITS = 15;
	private static final int LITERALS = 256;
	private static final int LENGTH_CODES = 29;
	private static final int L_CODES = LITERALS + 1 + LENGTH_CODES;
	private static final int HEAP_SIZE = 2 * L_CODES + 1;

	private static void genCodes(int[] tree, int maxCode, int[] blCount)
	{
		int[] nextCode = new int[MAX_BITS + 1];
		int code = 0;
		int bits;
		int n;
		for(bits = 1; bits <= MAX_BITS; bits++)
		{
			nextCode[bits] = code = (short) ((code + blCount[bits - 1]) << 1);
		}
		for(n = 0; n <= maxCode; n++)
		{
			int len = tree[n * 2 + 1];
			if(len == 0)
			{
				continue;
			}
			tree[n * 2] = (short) (biReverse(nextCode[len]++, len));
		}
	}

	private static int biReverse(int code, int len)
	{
		int res = 0;
		do
		{
			res |= code & 1;
			code >>>= 1;
			res <<= 1;
		} while(--len > 0);
		return res >>> 1;
	}


	public int maxCode;
	public int[] dynTree;
	public StaticTree statDesc;

	Tree()
	{
	}

	public void buildTree(Deflate s)
	{
		int elems = statDesc.elems;
		int n;
		int m;
		int maxCodeLocal = -1;
		int node;
		int[] tree = dynTree;
		int[] stree = statDesc.staticTree;
		s.heapLen = 0;
		s.heapMax = HEAP_SIZE;
		for(n = 0; n < elems; n++)
		{
			if(tree[n * 2] != 0)
			{
				s.heap[++s.heapLen] = maxCodeLocal = n;
				s.depth[n] = 0;
			} else
			{
				tree[n * 2 + 1] = 0;
			}
		}
		while(s.heapLen < 2)
		{
			node = s.heap[++s.heapLen] = (maxCodeLocal < 2 ? ++maxCodeLocal : 0);
			tree[node * 2] = 1;
			s.depth[node] = 0;
			s.optLen--;
			if(stree != null)
			{
				s.staticLen -= stree[node * 2 + 1];
			}
		}
		this.maxCode = maxCodeLocal;
		for(n = s.heapLen / 2; n >= 1; n--)
		{
			s.pqDownHeap(tree, n);
		}
		node = elems;
		do
		{
			n = s.heap[1];
			s.heap[1] = s.heap[s.heapLen--];
			s.pqDownHeap(tree, 1);
			m = s.heap[1];
			s.heap[--s.heapMax] = n;
			s.heap[--s.heapMax] = m;
			tree[node * 2] = (short) (tree[n * 2] + tree[m * 2]);
			s.depth[node] = (byte) (Math.max(s.depth[n], s.depth[m]) + 1);
			tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node;
			s.heap[1] = node++;
			s.pqDownHeap(tree, 1);
		} while(s.heapLen >= 2);
		s.heap[--s.heapMax] = s.heap[1];
		genBitlen(s);
		genCodes(tree, maxCodeLocal, s.blCount);
	}

	private void genBitlen(Deflate s)
	{
		int f;
		int base = statDesc.extraBase;
		int maxLength = statDesc.maxLength;
		int h;
		int n;
		int m;
		int bits;
		int xbits;
		int overflow = 0;
		int[] tree = dynTree;
		int[] stree = statDesc.staticTree;
		int[] extra = statDesc.extraBits;
		for(bits = 0; bits <= MAX_BITS; bits++)
		{
			s.blCount[bits] = 0;
		}
		tree[s.heap[s.heapMax] * 2 + 1] = 0;
		for(h = s.heapMax + 1; h < HEAP_SIZE; h++)
		{
			n = s.heap[h];
			bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
			if(bits > maxLength)
			{
				bits = maxLength;
				overflow++;
			}
			tree[n * 2 + 1] = (short) bits;
			if(n > maxCode)
			{
				continue;
			}
			s.blCount[bits]++;
			xbits = 0;
			if(n >= base)
			{
				xbits = extra[n - base];
			}
			f = tree[n * 2];
			s.optLen += f * (bits + xbits);
			if(stree != null)
			{
				s.staticLen += f * (stree[n * 2 + 1] + xbits);
			}
		}
		if(overflow == 0)
		{
			return;
		}
		do
		{
			bits = maxLength - 1;
			while(s.blCount[bits] == 0)
			{
				bits--;
			}
			s.blCount[bits]--;
			s.blCount[bits + 1] += 2;
			s.blCount[maxLength]--;
			overflow -= 2;
		} while(overflow > 0);
		for(bits = maxLength; bits != 0; bits--)
		{
			n = s.blCount[bits];
			while(n != 0)
			{
				m = s.heap[--h];
				if(m > maxCode)
				{
					continue;
				}
				if(tree[m * 2 + 1] != bits)
				{
					s.optLen += (((long) bits) - (long) tree[m * 2 + 1]) * (long) tree[m * 2];
					tree[m * 2 + 1] = (short) bits;
				}
				n--;
			}
		}
	}
}
