debughuf67

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include "Huffman.h"
#include <assert.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( vector<list*>& ASCII ) {
    for( int i = 0; i < 256; i++ ) {
        ASCII[i] = new list();
        ASCII[i]->symb = (unsigned char)(i);
        ASCII[i]->repeat = 0;
    }
}

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 = (unsigned 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;
}



void Encode( IInputStream& original, IOutputStream& compressed ) {
    byte value = 0;
    string input = "";
    string output = "";
    vector<list*> ASCII(256);
    vector<list*> shedule;
    priority_queue<list*> queue;

    init_arr( ASCII );

    while( original.Read(value) ) {
        int uval = value + 128;
        input += uval;
        ASCII[uval]->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] - 128);
    }

    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 >= 512 ) {
                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( IInputStream& compressed, IOutputStream& original ) {
    string output= "";
    int position = 0;
    byte value = 0;

    while( compressed.Read(value) ) {
        int uval = value + 128;
        output += uval;
    }


    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 - 128);
                tmp = root;
            }
            tmp = tmp->left;
        } else {
            if( tmp->right == nullptr ) {
                original.Write(tmp->symb - 128);
                tmp = root;
            }
            tmp = tmp->right;
        }

    }

    deletetree(root);

}