/*
 * Copyright (C) 2004-2012 Geometer Plus <contact@geometerplus.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */

#include <algorithm>

#include "HuffmanDecoder.h"

HuffmanDecoder::HuffmanDecoder() : myMaxBitsNumber(0) {
}

void HuffmanDecoder::reset() {
	CodeLengths.clear();
}

bool HuffmanDecoder::buildTable() {
	myMaxBitsNumber = 0;
	for (unsigned short symbol = 0; symbol < CodeLengths.size(); symbol++) {
		myMaxBitsNumber = std::max(CodeLengths[symbol], myMaxBitsNumber);
	}
	if (myMaxBitsNumber > 16) {
		return false;
	}

	unsigned int tableSize = 1 << myMaxBitsNumber;
	mySymbols.clear();
	mySymbols.reserve(tableSize);

	for (unsigned char i = 1; i <= myMaxBitsNumber; ++i) {
		for (unsigned short symbol = 0; symbol < CodeLengths.size(); symbol++) {
			if (CodeLengths[symbol] == i) {
				mySymbols.insert(mySymbols.end(), 1 << (myMaxBitsNumber - i), symbol);
				if (mySymbols.size() > tableSize) {
					return false;
				}
			}
		}
	}

	if (mySymbols.size() < tableSize) {
		mySymbols.insert(mySymbols.end(), tableSize - mySymbols.size(), 0);
	}

	return true;
}