Algo.cpp

#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

struct BinaryTree {
    char value;
    int frequ;
    BinaryTree* left;
    BinaryTree* right;
    
    BinaryTree(char val, int freq) : value(val), frequ(freq), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(BinaryTree* a, BinaryTree* b) {
        return a->frequ > b->frequ;
    }
};

class HuffmanCode {
private:
    string path;
    unordered_map<char, string> code;
    unordered_map<string, char> reverseCode;
    priority_queue<BinaryTree*, vector<BinaryTree*>, Compare> minHeap;

    unordered_map<char, int> frequencyFromText(const string& text) {
        unordered_map<char, int> freq;
        for (char ch : text) freq[ch]++;
        return freq;
    }

    void buildHeap(const unordered_map<char, int>& freq) {
        for (const auto& pair : freq) {
            char ch = pair.first;
            int fr = pair.second;
            minHeap.push(new BinaryTree(ch, fr));
        }
    }

    void buildBinaryTree() {
        while (minHeap.size() > 1) {
            BinaryTree* left = minHeap.top(); minHeap.pop();
            BinaryTree* right = minHeap.top(); minHeap.pop();
            BinaryTree* newNode = new BinaryTree('\0', left->frequ + right->frequ);
            newNode->left = left;
            newNode->right = right;
            minHeap.push(newNode);
        }
    }

    void buildTreeCodeHelper(BinaryTree* root, string currBits) {
        if (!root) return;
        if (root->value) {
            code[root->value] = currBits;
            reverseCode[currBits] = root->value;
            return;
        }
        buildTreeCodeHelper(root->left, currBits + "0");
        buildTreeCodeHelper(root->right, currBits + "1");
    }

    void buildTreeCode() {
        BinaryTree* root = minHeap.top();
        buildTreeCodeHelper(root, "");
    }

    string buildEncodedText(const string& text) {
        string encodedText = "";
        for (char ch : text) encodedText += code[ch];
        return encodedText;
    }

    string buildPaddedText(string encodedText) {
        int paddingValue = 8 - (encodedText.length() % 8);
        encodedText.append(paddingValue, '0');
        bitset<8> paddedInfo(paddingValue);
        return paddedInfo.to_string() + encodedText;
    }

    vector<uint8_t> buildByteArray(const string& paddedText) {
        vector<uint8_t> byteArray;
        for (size_t i = 0; i < paddedText.length(); i += 8) {
            byteArray.push_back(stoi(paddedText.substr(i, 8), nullptr, 2));
        }
        return byteArray;
    }

    string removePadding(const string& text) {
        int extraPadding = stoi(text.substr(0, 8), nullptr, 2);
        return text.substr(8, text.length() - 8 - extraPadding);
    }

    string decompressText(const string& text) {
        string decodedText = "", currBits = "";
        for (char bit : text) {
            currBits += bit;
            if (reverseCode.count(currBits)) {
                decodedText += reverseCode[currBits];
                currBits = "";
            }
        }
        return decodedText;
    }

public:
    HuffmanCode(string filepath) : path(filepath) {}

    string compress() {
        ifstream inputFile(path);
        if (!inputFile) {
            cerr << "Error opening file!" << endl;
            return "";
        }
        string text((istreambuf_iterator<char>(inputFile)), istreambuf_iterator<char>());
        inputFile.close();
        
        unordered_map<char, int> freq = frequencyFromText(text);
        buildHeap(freq);
        buildBinaryTree();
        buildTreeCode();

        string encodedText = buildEncodedText(text);
        string paddedText = buildPaddedText(encodedText);
        vector<uint8_t> byteArray = buildByteArray(paddedText);
        
        string outputPath = path.substr(0, path.find_last_of('.')) + ".bin";
        ofstream outputFile(outputPath, ios::binary);
        outputFile.write(reinterpret_cast<char*>(&byteArray[0]), byteArray.size());
        outputFile.close();

        cout << "Compressed to: " << outputPath << endl;
        return outputPath;
    }

    void decompress(const string& inputPath) {
        ifstream inputFile(inputPath, ios::binary);
        if (!inputFile) {
            cerr << "Error opening file!" << endl;
            return;
        }
        vector<uint8_t> byteArray((istreambuf_iterator<char>(inputFile)), istreambuf_iterator<char>());
        inputFile.close();
        
        string bitString = "";
        for (uint8_t byte : byteArray) {
            bitString += bitset<8>(byte).to_string();
        }

        string actualText = removePadding(bitString);
        string decompressedText = decompressText(actualText);
        
        string outputPath = inputPath.substr(0, inputPath.find_last_of('.')) + "_decompressed.txt";
        ofstream outputFile(outputPath);
        outputFile << decompressedText;
        outputFile.close();

        cout << "Decompressed to: " << outputPath << endl;
    }
};

int main() {
    string path;
    cout << "ENTER THE PATH OF YOUR FILE: ";
    cin >> path;
    HuffmanCode h(path);
    string outputPath = h.compress();
    h.decompress(outputPath);
    return 0;
}