#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <fstream>

using namespace std;

class Node {
public:

    int count;
    char sym;
    Node *left = 0;
    Node *right = 0;

    Node(int cnt) {
        count = cnt;
    }

    Node(int cnt, char smb) {
        count = cnt;
        sym = smb;
    }

};

bool isLeaf(Node *node) {
    return node->left == nullptr and node->right == nullptr;
}


vector<bool> code;
map<char, vector<bool> > table;

void MakeCodes(Node *root) {
    if (root->left != nullptr) {
        code.push_back(false);
        MakeCodes(root->left);
    }

    if (root->right != nullptr) {
        code.push_back(true);
        MakeCodes(root->right);
    }

    if (isLeaf(root)) table[root->sym] = code;

    code.pop_back();
}


int main(int argc, char *argv[]) {
////// считываем посимвольно в мапу
    ifstream f("CA.pptx", ios::out | ios::binary);

    map<unsigned char, int> symbols;

    while (!f.eof()) {
        char symbol = f.get();
        symbols[symbol]++;
    }


////// записывам мапу в вектор формируя ноды

    vector<Node *> numbers;

    map<unsigned char, int>::iterator ii;
    for (ii = symbols.begin(); ii != symbols.end(); ii++) {
        cout<<int(ii->first)<<" : "<<ii->second<<endl;
        //Node *p = new Node(i->first,i->second);
        //cout << ii->first << ":" << ii->second << endl;
        numbers.push_back(new Node(ii->second, ii->first));
    }

    while (numbers.size() != 1) {
        int last_element_index = numbers.size() - 1;
        /// создаем новую ноду на основе двух последних
        Node *new_node = new Node(numbers[last_element_index]->count + numbers[last_element_index - 1]->count);
        /// присваиваем этой ноде левого-правого ребенка
        new_node->left = numbers[last_element_index - 1];
        new_node->right = numbers[last_element_index];
        ///выкидываем последний
        numbers.pop_back();
        ///новый ставим на место последнего
        numbers[last_element_index - 1] = new_node;
        ///сортируем по размеру
        for (int i = numbers.size() - 1; i > 0 and numbers[i - 1]->count < numbers[i]->count; i--) {
            swap(numbers[i], numbers[i - 1]);
        }
    }

    Node *root = numbers[0];

////// делаем коды

    MakeCodes(root);

////// записываем сжатую версию файла

    f.clear();
    f.seekg(0);

    ofstream g("output.huff", ios::out | ios::binary);

    int count = 0;
    char buf = 0;
    while (!f.eof()) {
        char c = f.get();
        vector<bool> x = table[c];
        for (int n = 0; n < x.size(); n++) {
            buf = buf | x[n] << (7 - count);
            count++;
            if (count == 8) {
                count = 0;
                g << buf;
                buf = 0;
            }
        }
    }

    f.close();
    g.close();

///// разархивируем

    ifstream F("output.huff", ios::in | ios::binary);
    ofstream file(  "CAposle.pptx", ios::binary);
    //char c = 'a';
    //file.write((char *)c,1);
    setlocale(LC_ALL, "Russian");

    Node *node = root;
    count = 0;
    char byte;
    byte = F.get();
    while (!F.eof()) {
        bool b = (bool (byte & (1 << (7 - count))));
        if (b) node = node->right; else node = node->left;
        if (isLeaf(node)) {
            //cout << node->sym;
            file.write((char *) &node->sym, sizeof(char));
            node = root;
        }
        count++;
        if (count == 8) {
            count = 0;
            byte = F.get();
        }
    }

    F.close();
    file.close();
    return 0;
}