Huffman.cpp

#include "Huffman.h"
#include <queue>
#include <vector>
#include <stdexcept>

// ─── Min-heap comparator ─────────────────────────────────────────
struct Compare {
    bool operator()(Node* a, Node* b) { return a->freq > b->freq; }
};

Huffman::Huffman() : root_(nullptr) {}

Huffman::~Huffman() { freeTree(root_); }

void Huffman::freeTree(Node* node) {
    if (!node) return;
    freeTree(node->left);
    freeTree(node->right);
    delete node;
}

// ─── Build tree + generate codes ────────────────────────────────
void Huffman::build(const std::string& text) {
    if (text.empty()) throw std::runtime_error("Input text is empty.");

    // Count frequencies
    std::unordered_map<unsigned char, int> freq;
    for (unsigned char c : text) freq[c]++;

    // Edge case: single unique character
    if (freq.size() == 1) {
        unsigned char c = freq.begin()->first;
        Node* leaf = new Node(c, freq[c]);
        root_ = new Node('\0', freq[c]);
        root_->left = leaf;
        codes_[c] = "0";
        return;
    }

    // Build min-heap
    std::priority_queue<Node*, std::vector<Node*>, Compare> pq;
    for (auto& [ch, f] : freq)
        pq.push(new Node(ch, f));

    // Merge until one root
    while (pq.size() > 1) {
        Node* l = pq.top(); pq.pop();
        Node* r = pq.top(); pq.pop();
        Node* parent = new Node('\0', l->freq + r->freq);
        parent->left  = l;
        parent->right = r;
        pq.push(parent);
    }

    root_ = pq.top();
    codes_.clear();
    generateCodes(root_, "");
}

void Huffman::generateCodes(Node* node, const std::string& code) {
    if (!node) return;
    if (!node->left && !node->right) {   // leaf
        codes_[node->ch] = code;
        return;
    }
    generateCodes(node->left,  code + "0");
    generateCodes(node->right, code + "1");
}

// ─── Encode text → bit string ────────────────────────────────────
std::string Huffman::encode(const std::string& text) const {
    std::string bits;
    bits.reserve(text.size() * 4);
    for (unsigned char c : text) {
        auto it = codes_.find(c);
        if (it == codes_.end())
            throw std::runtime_error("Character not in Huffman table.");
        bits += it->second;
    }
    return bits;
}

// ─── Decode bit string → text ────────────────────────────────────
std::string Huffman::decode(const std::string& bits) const {
    if (!root_) throw std::runtime_error("Tree not built.");
    std::string result;
    Node* cur = root_;
    for (char bit : bits) {
        cur = (bit == '0') ? cur->left : cur->right;
        if (!cur) throw std::runtime_error("Invalid bit stream.");
        if (!cur->left && !cur->right) {   // leaf
            result += (char)cur->ch;
            cur = root_;
        }
    }
    return result;
}

// ─── Tree serialization ──────────────────────────────────────────
// Format: 1 byte type ('L'=leaf, 'I'=internal), then for leaf: 1 byte char value
void Huffman::serializeNode(Node* node, std::string& out) const {
    if (!node->left && !node->right) {   // leaf
        out += 'L';
        out += (char)node->ch;
    } else {
        out += 'I';
        serializeNode(node->left,  out);
        serializeNode(node->right, out);
    }
}

std::string Huffman::serializeTree() const {
    if (!root_) throw std::runtime_error("Tree not built.");
    std::string out;
    serializeNode(root_, out);
    return out;
}

Node* Huffman::deserializeNode(const std::string& data, size_t& pos) {
    if (pos >= data.size()) throw std::runtime_error("Corrupt tree data.");
    char type = data[pos++];
    if (type == 'L') {
        if (pos >= data.size()) throw std::runtime_error("Corrupt leaf data.");
        unsigned char ch = (unsigned char)data[pos++];
        return new Node(ch, 0);
    } else {
        Node* node  = new Node('\0', 0);
        node->left  = deserializeNode(data, pos);
        node->right = deserializeNode(data, pos);
        return node;
    }
}

void Huffman::deserializeTree(const std::string& data, size_t& pos) {
    freeTree(root_);
    root_ = deserializeNode(data, pos);
    codes_.clear();
    generateCodes(root_, "");
}