хуфман

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

using namespace std;

typedef char byte;

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


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



void init_arr( array<list, 258>& ASCII ) {
    for( int i = 0; i < 256; i++){
        ASCII[i].repeat = 0;
        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)&&( p != '\n') ) {
            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;
}

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

    init_arr( ASCII );

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

    for( int i = 0; i < 256; 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->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) {
                  //  list* right = new list;
                    tmp->right = new list;
                    tmp->right->code = tmp->code + '1';
                    tmp = tmp->right;
                    i++;
                } else {
                    tmp = tmp->right;
                    i++;
                }
            } else {
                if( tmp->left == nullptr ) {
                    //list* left = new list;
                    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 ) {
    int position = 0;
    string output;
    byte value;

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

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