#include <string>
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

int frecv[256];
class Iterator;

class NodA {
private:
	NodA * st;
	NodA *dr;
	char e;
public:
	friend class AB;
	NodA(char c, NodA* st, NodA* dr) : e{ c }, st{ st }, dr{ dr } {}

	char getCaracter() {
		return e;
	}
	NodA* getDr() {
		return dr;
	}
	NodA* getSt() {
		return st;
	}
};

queue< string> q;



class AB {
private:
	NodA * rad;
public:
	friend class Iterator;



	AB() {
		rad = NULL;
	}


	NodA* getRad() {
		return rad;
	}

	void creeazaArb(NodA *dr, NodA *st, char e) {
		rad->dr = dr;
		rad->st = st;
		rad->e = e;
	}

	void creeazaFrunza(char e) {
		this->rad = new NodA(e, NULL, NULL);
	}

	void creeazaAB(const AB& st, char e, const AB& dr) {
		//distrug vechiul arbore
		distruge(this->rad);
		//creez radacina
		this->rad = new NodA(e, NULL, NULL);
		//copiez subarborii
		this->rad->st = copiere(st.rad);
		this->rad->dr = copiere(dr.rad);
	}

	NodA* copiere(NodA* p) const {
		if (p != NULL) {
			//creez radacina
			NodA* pNew = new NodA(p->e, NULL, NULL);
			pNew->st = copiere(p->st);
			pNew->dr = copiere(p->dr);
			return pNew;
		}
		return NULL;
	}

	void distrugeSubarbori(NodA* p) {
		if (p != NULL) {
			distruge(p->st);
			distruge(p->dr);
		}
	}

	void adaugaSubSt(const AB& st) {
		//distrug vechii subarbori ai subarborelui stang
		distrugeSubarbori(this->rad->st);
		//copiez noul subarbore
		this->rad->st = copiere(st.rad);
	}

	void adaugaSubDr(const AB& dr) {
		//distrug vechii subarbori ai subarborelui drept
		distrugeSubarbori(this->rad->dr);
		//copiez noul subarbore
		this->rad->dr = copiere(dr.rad);
	}

	char element() const {
		return this->rad->e;
	}

	AB stang() const {
		AB ab;
		ab.rad = copiere(rad->st);
		return ab;
	}

	AB drept() const {
		AB ab;
		ab.rad = copiere(rad->dr);
		return ab;
	}

	void distruge(NodA* p) {
		if (p != NULL) {
			distruge(p->st);
			distruge(p->dr);
			delete p;
		}
	}

	Iterator iterator();


};

class Iterator {
private:
	AB a;
	NodA* current;
	std::stack<NodA*> st;
public:

	friend class AB;

	explicit Iterator(AB& a) : a{ a } {
		this->current = this->a.getRad();
	}

	bool valid() {
		return this->current != nullptr || !st.empty();
	}

	char element() {
		while (this->current != nullptr) {
			this->st.push(this->current);
			this->current = this->current->getSt();
		}

		auto elem = this->st.top();
		current = st.top();
		st.pop();
		return elem->getCaracter();

	}

	void urmator() {
		this->current = this->current->getDr();
	}

};


inline Iterator AB::iterator() {
	return Iterator(*this);
}

class Nod {
private:
	int prioritate;
	Nod *urm;
	Nod *ant;
	AB ab;
public:
	friend class CoadaPrioritati;
	Nod(int prioritate, AB a) :prioritate{ prioritate }, ab{ a }, urm{ NULL }, ant{ NULL } {}

	AB getArbore() {
		return ab;
	}

	int getPrioritate() {
		return prioritate;
	}
};



class CoadaPrioritati
{
private:
	Nod * prim;
	Nod *ultim;
public:
	CoadaPrioritati() {
		prim = ultim = nullptr;
	}

	void adaugaC(int p, AB a) {
		Nod *nodNou = new Nod(p, a);
		Nod *curent = prim;

		if (curent == nullptr) {
			prim = ultim = nodNou;
		}
		else
		{
			while (curent != nullptr && curent->prioritate <= p) {
				curent = curent->urm;
			}
			if (curent == nullptr) {
				ultim->urm = nodNou;
				ultim = nodNou;
			}
			else if (curent == prim) {
				curent->ant = nodNou;
				nodNou->urm = curent;
				prim = nodNou;
			}
			else {
				curent->ant->urm = nodNou;
				nodNou->ant = curent->ant;
				nodNou->urm = curent;
				curent->ant = nodNou;
			}
		}
	}

	Nod* sterge() {
		Nod* nod = prim;
		prim = prim->urm;
		return  nod;
	}

	size_t dim() {
		Nod* p = prim;
		size_t len = 0;
		while (p != NULL) {
			len++;
			p = p->urm;
		}
		return len;
	}
	bool vida() {
		if (prim = ultim = nullptr)
			return true;
		else
			return false;
	}
	~CoadaPrioritati() {
		Nod *nod = prim;
		while (nod != NULL)
		{
			Nod* p = nod;
			nod = nod->urm;
			delete p;
		}
	}
};

void construireCod(string s, int frecv[]) {
	for (int i = 0; i < 256; i++)
		frecv[i] = 0;
	for (const auto& elem : s) {
		frecv[int(elem)] ++;
	}
}


vector<string> coduri;
vector<char> car;

void stocheazaCod(NodA* rad, string str)
{
	if (rad == NULL)
		return;
	if (rad->getCaracter() != '$') {
		q.push(str);
		coduri.push_back(str);
		car.push_back(rad->getCaracter());
	}
	stocheazaCod(rad->getSt(), str + "0");
	stocheazaCod(rad->getDr(), str + "1");
}
void codificaHuffman(string s, CoadaPrioritati& coada, AB& arb) {
	construireCod(s, frecv);
	for (int i = 0; i<256; i++) {
		if (frecv[i] != 0) {
		//	cout << char(i) << " " << frecv[i] << endl;
			AB a;
			a.creeazaFrunza(char(i));
			coada.adaugaC(frecv[i], a);
		}
	}

	while (coada.dim() != 1) {
		auto left = coada.sterge();
		auto right = coada.sterge();
		auto frecventa = left->getPrioritate() + right->getPrioritate();
		arb.creeazaFrunza('$');
		arb.creeazaAB(left->getArbore(), '$', right->getArbore());
		coada.adaugaC(frecventa, arb);
	}

	//stocheazaCod(coada.sterge()->getArbore().getRad(), "");
}



/*string decodareHuffman(NodA* rad, string s)
{
	string ans = "";
	NodA* curr = rad;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '0')
			curr = curr->getSt();
		else
			curr = curr->getDr();

		// reached leaf node
		if (curr->getSt() == nullptr and curr->getDr() == nullptr)
		{
			ans += curr->getCaracter();
			curr = rad;
		}
	}
	// cout<<ans<<endl;
	return ans + '\0';
}*/


string decodareHuffman(string s)
{
	int ok = 0;
	string ans = "";
	string caracter = "";
	for (int i = 0; i < s.size(); i++) {
		ok = 0;
		for (int j = 0; j < coduri.size(); j++)
			if (caracter == coduri[j]) {
				caracter = "";
				ans += car[j];
				ok = 1;
			}
		if (ok == 0)
			caracter += s[i];
	}
	return ans;
}


int main() {
	CoadaPrioritati coada;
	string str = "rog";
	string codare, decodare;
	AB ab;
	codificaHuffman(str, coada, ab);
	auto nd = coada.sterge();
	stocheazaCod(nd->getArbore().getRad(), "");

	Iterator it = ab.iterator();
	while (it.valid()) {
		auto elem = it.element();
		if (elem != '$') {
			std::cout << elem << "  " << q.front() << endl;
			q.pop();
		}
		it.urmator();
	}
	string a = decodareHuffman("010001011");
	cout << a;
	return 0;
}