/*
 * Huffman.h
 *
 *
 */

#ifndef HUFFMAN_H_
#define HUFFMAN_H_
#include <iterator> // std::forward_iterator_tag
#include <cstddef>  // std::ptrdiff_t

template<typename T, typename E>

class Huffman {
public:
	typename T::iterator beginSeq; ///< iteratore che punta al primo elemento della sequenza T
	typename T::iterator endSeq; ///< iteratore che punta all'ultimo elemento della sequenza T
	E elementi[]; ///< sequenza di elementi ordinata per frequenza
	int frequenza[]; ///< frequenza di ogni singolo elemento
	int dimSeq; ///< dimensione della sequenza T
	int dimHuffman; ///< dimensione della sequenza T senza ripetizioni

private:
	void calcolafrequenza()	{
		int i = 0, j = 0;
		while(beginSeq != endSeq) {
			j = i - 1;
			while(j >= 0)	{
				if (*beginSeq == elementi[j]) {
					frequenza[j]++;
					j = -2;
				}else j--;
			}
			if (j == -1)	{
				elementi[i] = *beginSeq;
				frequenza[i] = 1;
				i++;
			}
			dimSeq++;
			beginSeq++;
		}
		dimHuffman = i;
		E temp;
		int freqtemp;
		for(int k = 0; k < dimHuffman; k++)	{
			for(int t = k; t < dimHuffman; t++)	{
				if (frequenza[t] > frequenza[k])	{
					temp = elementi[k];
					freqtemp = frequenza[k];
					elementi[k] = elementi[t];
					frequenza[k] = frequenza[t];
					elementi[t] = temp;
					frequenza[t] = freqtemp;
				}
			}
		}
	}


public:
	/**
	 * Costruttore di default
	 */
	Huffman()	{
		beginSeq = 0;
		endSeq = 0;
		dimSeq = 0;
		dimHuffman = 0;
	}

	/**
	 * Costruttore secondario
	 * @param beginSeq iteratore che punta al primo elemento della sequenza
	 * @param endSeq iteratore che punta all'ultimo elemento della sequenza
	 */
	Huffman(typename T::iterator beginSeq, typename T::iterator endSeq)	{
		this->beginSeq = beginSeq;
		this->endSeq = endSeq;
		dimSeq = 0;
		dimHuffman = 0;
		calcolafrequenza();
	}

};


#endif /* HUFFMAN_H_ */