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

using namespace std;

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

int utworz_liste( moj_wezel *&root, string s )
{
    int  temp_ilosc;
    char temp_znak;
    moj_wezel *temp;
    bool posortowana;

    root = NULL;
    for( int i = 0; i < s.length(); i++ )
    {
        temp = root;
        while( temp && ( temp -> znak != s[i] ) ) temp = temp -> next;
        if( !temp )
        {
            temp = new moj_wezel;
            temp -> next  = root;
            temp -> left  = NULL;
            temp -> right = NULL;
            temp -> znak = s[i];
            temp -> ilosc = 0;
            root = temp;
        }
    temp -> ilosc++;
    }
    do
    {
        posortowana = true;
        temp = root;
        while( temp -> next )
        {
            if( temp -> ilosc > temp -> next -> ilosc )
            {
                temp_znak = temp -> znak;
                temp -> znak = temp -> next -> znak;
                temp -> next -> znak = temp_znak;
                temp_ilosc = temp -> ilosc;
                temp -> ilosc = temp -> next -> ilosc;
                temp -> next -> ilosc = temp_ilosc;
                posortowana = false;
            }
            temp = temp -> next;
        }
    } while( !posortowana );
    int dlug = 0;
    temp = root;
    while( temp )
    {
        temp = temp -> next;
        dlug++;
    }
    return dlug;
}

void pokaz_liste(moj_wezel *root)
{
    moj_wezel *temp = root;
    while( temp )
    {
        cout << temp -> znak << " " << temp -> ilosc << endl;
        temp = temp -> next;
    }
    cout << endl << endl;

}

void utworz_drzewo(moj_wezel *&root)
{
    moj_wezel *temp, *tempr, *wezel_1, *wezel_2;

    while( true )
    {
        wezel_1 = root;
        wezel_2 = wezel_1 -> next;  //dwa pierwsze z listy

        if( !wezel_2 ) break;

        root = wezel_2 -> next;
        temp = new moj_wezel;
        temp -> left = wezel_1;
        temp -> right = wezel_2;
        temp -> ilosc = wezel_1 -> ilosc + wezel_2 -> ilosc;


        if( !root || ( temp -> ilosc <= root -> ilosc ) )
        {
            temp -> next = root;
            root = temp;
            continue;
        }

        tempr = root;

        while( tempr -> next && ( temp -> ilosc > tempr -> next -> ilosc ) ) tempr = tempr -> next;

        temp -> next = tempr -> next;
        tempr -> next = temp;
    }
}

void pokaz_drzewo(moj_wezel *temp, string kod )
{
    if( !temp -> left )
    {
        cout << temp -> znak << " " << kod << endl;
    }
    else
    {
        pokaz_drzewo(temp -> left, kod + "0");
        pokaz_drzewo(temp -> right, kod + "1");
    }
}

bool koduj_znak( ofstream &out, char zn, moj_wezel *w, string kod )
{
    if( !w -> left )
    {
        if( zn != w -> znak ) return false;     //doszliœmy do liœcia, ale to nie ten
        else
        {
            out << kod;    //doszliœmy do liœcia,  kod jest kompletny
            return true;
        }
    }
    else return koduj_znak( out, zn, w -> left, kod + "0" ) || koduj_znak( out, zn, w -> right, kod + "1" );
}

void koduj(ofstream &out, moj_wezel *root, string tekst )
{

    for(int i = 0; i < tekst.length( ); i++ )
        koduj_znak(out, tekst[i], root, "" );
}

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



int main( )
{
    moj_wezel *root;
    cout << "Podaj nazwe pliku zawierajacego tekst do zakodowania: ";
    string plik;
    cin >> plik;
    ifstream in(plik);
    cout << "Podaj nazwe pliku do wpisania kodu: ";
    cin >> plik;
    ofstream out(plik);
    string tekst;
    in >> tekst;
    int ilosc_znakow;
    ilosc_znakow = utworz_liste(root, tekst);
    cout << "Posortowana lista: " << endl;
    pokaz_liste(root);
    utworz_drzewo(root);
    cout << "Tabela kodow: " << endl;
    cout << ilosc_znakow << endl;
    pokaz_drzewo(root, "" );
    koduj(out, root, tekst);

    usun_drzewo(root);

    cout << endl << endl;

    return 0;
}