#include <iostream>
#include <string>
#include <fstream>

using namespace std;

class moj_wezel
{
public:
    moj_wezel *left, *right;
    char znak;
};

moj_wezel *utworz_drzewo()
{
    string plik;
    cout << "Podaj nazwe pliku ze schematem kodowania: ";
    cin >> plik;
    ifstream in(plik);
    int ilosc_znakow;
    char zn;
    string kod;
    in >> ilosc_znakow;

    moj_wezel *korzen, *w;
    korzen = new moj_wezel;
    korzen -> left = NULL;
    korzen -> right = NULL;
    for(int i = 0; i < ilosc_znakow; i++)
    {
        in >> zn >> kod;
        w = korzen;
        for(int j=0; j <  (int) kod.length(); j++)
        {
            if( kod[j] == '0')
            {
                if( !(w -> left))
                {
                    w -> left = new moj_wezel;
                    w -> left -> left = NULL;
                    w -> left  -> right = NULL;
                }
                w = w -> left;
            }
            else
            {
                if( !(w -> right))
                {
                    w -> right = new moj_wezel;
                    w -> right -> left = NULL;
                    w -> right  -> right = NULL;
                }
                w = w -> right;
            }
        }
        w -> znak = zn;
    }

    return korzen;

}

void usun_drzewo(moj_wezel *w)
{
    if( w )
    {
        usun_drzewo( w -> left );
        usun_drzewo( w -> right );
        delete w;
    }
    return;
}

void odkoduj(moj_wezel *korzen)
{
    string plik;
    cout << "Prosze podac nazwe pliku z zakodowanym tekstem: ";
    cin >> plik;
    ifstream in(plik);
    string kod;
    in >> kod;
    moj_wezel *w = korzen;
    for(int i = 0; i <  (int) kod.length(); i++)
    {
        if(kod[i] == '0') w = w -> left;
        else w = w -> right;
        if( !w -> left )
        {
            cout << w -> znak;
            w = korzen;
        }
    }
    cout << endl;
}

bool koduj_znak(ofstream &out, char zn, moj_wezel *w, string kod)
{
    if ( ! w -> left )
        if (zn != w -> znak)
            return false;
        else
        {
            out << kod;
            return true;
        }
    else return koduj_znak(out, zn, w -> left, kod + "0") || koduj_znak(out, zn, w -> right, kod + "1");
}


int main()
{
    moj_wezel *korzen;
    korzen = utworz_drzewo();
    odkoduj( korzen );
    cout << "Podaj nazwe pliku z tekstem: ";
    string plik;
    cin >> plik;
    ifstream in(plik);
    cout << "Podaj nazwe pliku do wpisania kodu: ";
    cin >> plik;
    ofstream out(plik);
    string tekst;
    in >> tekst;
    for(int i = 0; i < (int) tekst.length(); i++)
        koduj_znak(out, tekst[i], korzen, "");

    usun_drzewo(korzen);



    return 0;
}