zip.cpp

#include <bits/stdc++.h>
#define ln '\n'
#define loop(i,a,b) for(int i = a; i <= b; i++)
#define pb push_back
using namespace std;
ifstream fin("file.txt", ios::binary);
ofstream fout("file.myzip", ios::binary);

uint8_t curr = 0;
int bitCount = 0;
char c;
unordered_map<char, string> ans;

class Node{
public:
    char val;
    int data;
    Node *left, *right;
    Node(char x, int y){
        val = x;
        data = y;
        left = nullptr;
        right = nullptr;
    }
};

class Compare{
public:
    bool operator() (Node* a, Node* b){
        return a->data > b->data;
    }
};

void preorder(Node* root, string curr){
    if(root == nullptr)return;
    if(root->left == nullptr && root->right == nullptr){
        ans[root->val] = curr;
        return;
    }
    preorder(root->left, curr + '0');
    preorder(root->right, curr + '1');
}

void huffmanCoding(vector<pair<char, int>> freq){
    int n = freq.size();

    priority_queue<Node*, vector<Node*>, Compare>pq;
    for(int i = 0; i < n; i++){
        Node *tmp = new Node(freq[i].first, freq[i].second);
        pq.push(tmp);
    }

    while(pq.size() >= 2){
        Node *l = pq.top();
        pq.pop();

        Node *r = pq.top();
        pq.pop();

        Node *x = new Node('x', l->data + r->data);
        x->left = l;
        x->right = r;

        pq.push(x);
    }

    preorder(pq.top(), "");
}

unordered_map<char, int> mp;
vector<pair<char, int>> freq;

int main(){
    auto writeBit = [&](int bit){
        curr = (curr << 1) | bit;
        bitCount++;
        if(bitCount == 8){
            fout.put(curr);
            curr = 0;
            bitCount = 0;
        }
    };

    while(fin.get(c)){
        mp[c]++;
    }
    fin.clear();
    fin.seekg(0, ios::beg);

    uint8_t nr = mp.size();
    for(int i = 7; i >= 0; i--){
        writeBit((nr >> i) & 1);
    }

    for(auto i : mp){
        freq.pb({i.first, i.second});
    }

    huffmanCoding(freq);

    uint8_t x;
    for(auto i : mp){
        x = i.first;
        for(int j = 7; j >= 0; j--){
            writeBit((x >> j) & 1);
        }

        x = ans[i.first].size();
        for(int j = 7; j >= 0; j--){
            writeBit((x >> j) & 1);
        }

        for(auto b : ans[i.first])writeBit(b - '0');
        int nr = (8 - x % 8) % 8;
        for(int j = 0; j < nr; j++)writeBit(0);

    }

    while(fin.get(c)){
        string code = ans[c];
        for(char b : code){
            writeBit(b - '0');
        }
    }

    if(bitCount > 0){
        curr <<= (8 - bitCount);
        fout.put(curr);
    }

    return 0;
}