Хаффман.cpp

#include <iostream>
#include <list>
#include <map>
#include <string>
using namespace std;
class Node {
    public:
    char Symbol;
    int Frequency;
    Node *Right, *Left;

    list<bool> Traverse(char symbol, list<bool> &data) {
        // Leaf
        if (Right == NULL && Left == NULL)
            return (symbol == this->Symbol) ? (data) : list<bool>();
        else {
            list<bool> left;
            list<bool> right;

            if (Left != NULL) {
                list<bool> leftPath(data);
                leftPath.push_back(false);
                left = Left->Traverse(symbol, leftPath);
            }

            if (Right != NULL) {
                list<bool> rightPath(data);
                rightPath.push_back(true);
                right = Right->Traverse(symbol, rightPath);
            }

            if (!left.empty())
                return left;
            else 
                return right;
        }
    }
};

class MyComp{
    public:
bool operator()(const Node* l, const Node* r) const { 
    return l->Frequency < r->Frequency; 
    }
};

class HuffmanTree {
    list<Node*> nodes;
    Node* Root;
    map<char, int> Frequencies;
public:
    void Build(string source){
        for (size_t i = 0; i < source.length(); i++){
            if (Frequencies.find(source[i]) == Frequencies.end()) 
                Frequencies.insert(std::pair<char,int>(source[i], 0));
            Frequencies[source[i]]++;
        }

        for ( map<char,int>::iterator symbol = Frequencies.begin(); symbol!= Frequencies.end(); ++symbol ) {
            Node* temp = new Node();
            temp->Symbol = symbol->first;
            temp->Frequency = symbol->second;
            nodes.push_back(temp);
        }

        while (nodes.size() > 1) {
            nodes.sort(MyComp());
            if (nodes.size() >= 2){
                Node* parent = new Node();
                parent->Symbol = '*';
                parent->Left= nodes.front();
                nodes.pop_front();
                parent->Right = nodes.front();
                nodes.pop_front();
                nodes.push_back(parent);
            }
            this->Root = nodes.front();
        }
    }

    list<bool> Encode(string source) {
        list<bool> encodedSource;
        for (size_t i = 0; i < source.length(); i++) {
            list<bool> buffer;
            list<bool> encodedSymbol(this->Root->Traverse(source[i],buffer));
            while(!encodedSymbol.empty()){
                encodedSource.push_back(encodedSymbol.front());
                encodedSymbol.pop_front();
            }
        }

        return encodedSource;
    }

    string Decode(list<bool> &bits) {
        Node* current = this->Root;
        string decoded = "";
        bool bit;
        while(!bits.empty()){
            bit=bits.front();
            //cout<<bit<<endl;
            if (bit) {
                if (current->Right != NULL)
                    current = current->Right;
            }
            else {
                if(current->Left != NULL)
                    current = current->Left;
            }

            if (IsLeaf(current)) {
                decoded += current->Symbol;
                current = this->Root;
            }
            bits.pop_front();
        }
        return decoded;
    }

    bool IsLeaf(Node* node) {
        return (node->Left == NULL && node->Right == NULL);
    }

};

int main(){
    char input[255];
    cin.getline(input,255);
    HuffmanTree* huffmanTree = new HuffmanTree();

    // Build the Huffman tree
    huffmanTree->Build(input);

    // Encode
    list<bool> encoded = huffmanTree->Encode(input);

    cout<<"Encoded: ";
    for (list<bool>::iterator i = encoded.begin(); i!=encoded.end(); ++i){
        cout<< int(*i);
    }
    cout<<endl;
    // Decode
    string decoded = huffmanTree->Decode(encoded);

    cout<<"Decoded: " + decoded<<endl;
}