HUFFMAN 2.0

#include <iostream>
#include <array>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

struct list {
    int repeat = 0;
    char symb = NULL;
    string code;
    list* left = nullptr;
    list* right = nullptr;
};


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



void init_arr( array<list, 257>& ASCII ) {
    for( int i = 0; i < 257; i++){
        ASCII[i].repeat = 0;
        ASCII[i].symb =(char)(i+1);
    }
}

bool read( array<list, 257>& ASCII, string& input ) {
    char c = getchar_unlocked();
    if( c != EOF ) {
        input += c;
        ASCII[(int)c - 1].repeat++;
        return true;
    } else {
        return false;
    }
}

void generateCode( list*& root ) {//TO DO
    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) {
    for( int i = 0; i < shed.size(); i++){
        if( shed[i]->symb == p) {
            return shed[i]->code;
        }
    }
    return NULL;
}

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 Encode( array<list, 257>& ASCII, string& input, string& output, list*& out ) {
    vector<list*> shedule;
    priority_queue<list> queue;
    for( int i = 0; i < 257; i++ ) {
        if( ASCII[i].repeat != 0 ) {
        queue.push(ASCII[i]);
        }
    }



    while( queue.size() >= 2) {
    list* tmp1 = new list(queue.top());
    queue.pop();
    list* tmp2 = new list( 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 = new list( queue.top() );
    root->code = '1';
    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]);
    }
    out = 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) {
            list* right = new list;
            tmp->right = right;
            right->code = tmp->code + '1';
            tmp = right;
            i++;
            } else {
                tmp = tmp->right;
                i++;
            }
        } else {
            if( tmp->left == nullptr ) {
            list* left = new list;
            tmp->left = left;
            left->code = tmp->code + '0';
            tmp = left;
            i++;
            } else {
                tmp = tmp->left;
                i++;
            }
        }
    }
    tmp->symb = (char)symb_num;
    tmp = root;
        i++;
        symb_num = 0;
    }
    cout <<" ";
    return root;
}

void Decode( string& output) {
    int position = 0;
    list* root = decode_tree( output, position );
    list* tmp = new list;
    tmp = root;

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

            }
            tmp = tmp->right;
        }
    }
}

int main() {
    string input;
    string output;
    array<list, 257> ASCII;
    init_arr( ASCII );
    list* out = new list;

    while( read(ASCII, input) ) {
    };

    Encode( ASCII, input, output, out );

    cout<<output<<endl;

    Decode(output);

    return 0;

}