#include <iostream>
#include <list>
#include "BinaryTree.h"
#include "xceptions.h"

using namespace std;


class FreqCrts {
	char caracter;	// não é usado para nós que não são folhas 
	int frequencia;			
public:
	FreqCrts(char c='~', int freq=1) { caracter=c; frequencia=freq; }
	char getChar() { return caracter; } 
	int getFrequencia() { return frequencia; } 
	void incFrequencia() { frequencia++; }
	bool operator < (FreqCrts & fc2) { return frequencia<fc2.frequencia;}
	friend ostream &operator << (ostream &os, FreqCrts &fc1);
};

ostream &operator << (ostream &os, FreqCrts &fc1)
{
	os << fc1.caracter << " : frequencia=" << fc1.frequencia << endl;
	return os;
}

void colocaLista(list<BinaryTree<FreqCrts> > &listArv, BinaryTree<FreqCrts> &novaArv)
{
	list<BinaryTree<FreqCrts> >::iterator it=listArv.begin();
	while(it != listArv.end())
	{
		if (novaArv.getRoot()<it->getRoot()) { // insere ordenadamente
			listArv.insert(it,novaArv);
			return;
		}
		it++;
	}
	listArv.push_back(novaArv);
}

void criaLista(list<BinaryTree<FreqCrts> > &listArv, string &frase)
{
	for (int i=0; i<frase.length(); i++)
	{
		char c1=frase[i];
		list<BinaryTree<FreqCrts> >::iterator it=listArv.begin();
		while(it != listArv.end())
		{
			if (it->getRoot().getChar()==c1) { // caracter c1 ja existe
				BinaryTree<FreqCrts> arv1=*it;
				listArv.erase(it);
				arv1.getRoot().incFrequencia();
				colocaLista(listArv,arv1);
				break;
			}
			it++;
		}
		if ( it==listArv.end() ) {// caracter c1 ainda nao existia
			BinaryTree<FreqCrts> *arv1= new BinaryTree<FreqCrts>(FreqCrts(c1));  
			colocaLista(listArv,*arv1);
		}
	}
}


void codifica(list<BinaryTree<FreqCrts> > &listArv)
{
	while (listArv.size()>1)
	{
		list<BinaryTree<FreqCrts> >::iterator it=listArv.begin();
		BinaryTree<FreqCrts> arvL=*it;
		it=listArv.erase(it);
		BinaryTree<FreqCrts> arvR=*it;
		listArv.erase(it);
		int tFreq=arvL.getRoot().getFrequencia() + arvR.getRoot().getFrequencia();
		BinaryTree<FreqCrts> novaArv(FreqCrts('~',tFreq),arvL,arvR);
		colocaLista(listArv,novaArv);
	}
}


int main()
{
    list<BinaryTree<FreqCrts> > lista;
    string frase="If a woodchuck could chuck wood!";
    criaLista(lista,frase);
    codifica(lista);
    //imprime árvore final em pre-ordem
    BinaryTree<FreqCrts> arv1=lista.front();
    BTItrPre<FreqCrts> it(arv1);
    while (!it.isAtEnd())
    {
    	cout << it.retrieve();
    	it.advance();
    }
    system("PAUSE");
    return 0;
}