for debugging

#include <iostream>
#include <array>
#include <string>
#include <queue>
//#include "Huffman.h"

using namespace std;

typedef char byte;

struct list {
    int repeat;
    char symb;
    string code;
    list* left;
    list* right;

    list():
    repeat(0),
    symb(0),
    code(""),
    left( nullptr ),
    right( nullptr )
    {}

    list( const list& root );

};

list::list(const list &root) :
    repeat( root.repeat ),
    symb( 0 ),
    code( "" ),
    left( root.left ),
    right( root.right)
    {}


bool operator <( const list& first, const list& second ){
    return first.repeat > second.repeat;
}

void init_arr( array<list*, 256>& ASCII ) {
    for( int i = 0; i < 256; i++ ) {
        ASCII[i] = new list();
        ASCII[i]->symb = (char)(i);
    }
}
void generateCode( list*& root ) {
    if( root == nullptr ) {
        return;
    }
    if( root->left != nullptr ) {
        root->left->code = root->code + '0';
    }
    if( root->right != nullptr ) {
        root->right->code = root->code + '1';
    }

    generateCode(root->left);
    generateCode(root->right);
}

void translate( list* root, vector<list*>& shedule ) {

    if( root->right == nullptr && root->left == nullptr ) {
        shedule.push_back(root);
        return;
    } else {
        translate(root->left, shedule);
        translate(root->right, shedule);
    }

}

string find_code( vector<list*> shed, char p ) {
    int i = 0;
    while( shed[i]->symb != p ) {
        i++;
    }
    return shed[i]->code;
}

string into_bin ( char p ) {
    string binary;
    int p_num = (int)p;
    int i = 0;

    while( p_num > 0 ) {
        p_num /= 2;
        i++;
    }
    p_num = (int)p;
    i--;
    for( ; i >= 0; --i) {
        if( 0 == ((p_num>>i)&(0x1)) ) {
            binary += '0';
        } else {
            binary += '1';
        }
    }

    return binary;

}

void crypt_tree( vector<list*>& shedule, string& crypt ) {

    for( int i = 0; i < shedule.size(); i++ ) {
        crypt += into_bin(shedule[i]->symb);
        crypt += ' ';
        crypt += shedule[i]->code;
        crypt += ' ';
    }

}

void deletetree( list* tree ) {
    if( tree == nullptr ) {
        return;
    }
    deletetree(tree->left);
    deletetree(tree->right);
    delete tree;
}

bool read( byte& value ) {
    value = getchar_unlocked();

    if( value != EOF ) {
        return true;
    } else {
        return false;
    }
}

void Encode( string& input, string& output ) {
    //      byte value;
    //    string input;
    //    string output;
    array<list*, 256> ASCII;
    vector<list*> shedule;
    priority_queue<list*> queue;

    init_arr( ASCII );

    //    while( read(value) ) {
    //        input += value;
    //        ASCII[(int)value].repeat++;
    //    }

    for( int i = 0; i < input.length(); i++ ) {
        ASCII[(int)input[i]]->repeat++;
    }

    for( int i = 0; i < 256; i++ ) {
        if( ASCII[i]->repeat != 0 ) {
            queue.push(ASCII[i]);
        }
    }

    while( queue.size() >= 2) {
        list* tmp1 = queue.top();
        queue.pop();
        list* tmp2 = queue.top();
        queue.pop();

        list* newtmp = new list();
        newtmp->left = tmp1;
        newtmp->right = tmp2;
        newtmp->repeat = tmp1->repeat + tmp2->repeat;
        queue.push(newtmp);
    }

    list* root = queue.top();
    queue.pop();

    root->left->code = '0';
    root->right->code = '1';
    generateCode(root->right);
    generateCode(root->left);
    translate( root, shedule );

    crypt_tree(shedule, output);

    for( int i = 0; i < input.length(); i++ ) {
        output += find_code(shedule, input[i]);
    }

    //    for( int i = 0; i < output.length(); i++ ) {
    //        compressed.Write(output[i]);
    //    }

    deletetree(root);
}

list* decode_tree ( string output, int& position ) {
    list* root = new list();
    list* tmp = root;
    int symb_num = 0;
    int j = 0;
    int i = 0;

    while( i < output.length() ) {
        for(; output[i] != ' '; i++ ) {
            j++;
            symb_num = symb_num*2 + (output[i] - '0' )*2;
            if( symb_num > 256 ) {
                position = i - j + 1;
                return root;
            }
        }
        symb_num /= 2;
        j = 0;
        i++;
        while( output[i] != ' ') {
            if( output[i] == '1' ) {
                if( tmp->right == nullptr) {
                    tmp->right = new list;
                    tmp->right->code = tmp->code + '1';
                    tmp = tmp->right;
                    i++;
                } else {
                    tmp = tmp->right;
                    i++;
                }
            } else {
                if( tmp->left == nullptr ) {
                    tmp->left = new list;
                    tmp->left->code = tmp->code + '0';
                    tmp = tmp->left;
                    i++;
                } else {
                    tmp = tmp->left;
                    i++;
                }
            }
        }
        tmp->symb = (char)symb_num;
        tmp = root;
        i++;
        symb_num = 0;
    }
    return root;
}

void Decode( string& output, string& input ) {
    int position = 0;
    //    byte value;
    //    while( compressed.Read(value) ) {
    //        output += value;
    //    }

    list* root = decode_tree( output, position );
    list* tmp = root;

    for( int i = position; i < output.length(); i++ ) {
        if( output[i] == '0' ) {
            if( tmp->left == nullptr ) {
                //                original.Write(tmp->symb);
                input += tmp->symb;
                tmp = root;
            }
            tmp = tmp->left;
        } else {
            if( tmp->right == nullptr) {
                //                original.Write(tmp->symb);
                input += tmp->symb;
                tmp = root;
            }
            tmp = tmp->right;
        }
    }
    deletetree(root);
}

int main(){
    string input;
    string output;
    string tmp;
    byte value;

    while( read(value) ) {
        input += value;
    }

    Encode(input, output);
    cout << output<<endl;

    Decode(output, tmp);
    cout<<tmp;
}