sami_huffman

#include <bits/stdc++.h>
using namespace std;

map<char, string> prefixCodes;

struct root {
    double frequency;
    char maxVal;
    struct root* left;
    struct root* right;
};

bool rootComp(struct root* r1, struct root* r2){
    /*   My bad sorting M < I in exam script  (*_ _)人 */
    if(r1->maxVal == 'M' && r2->maxVal == 'I') return true;

    if(r1->frequency == r2->frequency) return r1->maxVal < r2->maxVal;
    return r1->frequency < r2->frequency;
}

void dfs(struct root *cur, string pCode){
    if(!cur->left && !cur->right){
        prefixCodes[cur->maxVal] = pCode;
        return;
    }
    if(cur->left) dfs(cur->left, pCode + "0");
    if(cur->right) dfs(cur->right, pCode + "1");
}

string generateString(string id) {
    stringstream ss;
    ss<<"MYIDIS";
    char digWord[10][6] =
    {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
    for(int i = id.size() - 4; i < id.size(); i++) {
        ss<<digWord[id[i]-'0'];
    }
    return ss.str();
}

void generatePrefixCodes(string str) {
    map<char, double> frequency;
    vector<struct root*> roots;
    for(auto c : str){
        if(frequency.count(c)) frequency[c] += 1;
        else frequency[c] = 1;
    }
    for(auto p : frequency){
        struct root* newRoot = new struct root;
        newRoot->frequency = p.second / str.size();
        newRoot->maxVal = p.first;
        newRoot->left = nullptr;
        newRoot->right = nullptr;
        roots.push_back(newRoot);
    }

    sort(roots.begin(), roots.end(), rootComp);

    while(roots.size() > 1){
        struct root* newRoot = new struct root;
        newRoot->frequency = roots[0]->frequency + roots[1]->frequency;
        newRoot->maxVal = max(roots[0]->maxVal, roots[1]->maxVal);

        if(rootComp(roots[0], roots[1])){
            newRoot->left = roots[1];
            newRoot->right = roots[0];
        }
        else{
            newRoot->left = roots[0];
            newRoot->right = roots[1];
        }
        roots.push_back(newRoot);
        roots.erase(roots.begin());
        roots.erase(roots.begin());
        sort(roots.begin(), roots.end(), rootComp);
    }
    dfs(roots[0], "");
}

int main() {
    string id, str;
    cout<<"Enter Student ID : ";
    cin>>id;
    str = generateString(id);
    cout<<"Generated String: "<<str<<"\n";
    generatePrefixCodes(str);
    cout<<"Prefix Codes (Generated Using Huffman Coding):\n";
    for(auto p : prefixCodes){
        cout<<p.first<<" : "<<p.second<<"\n";
    }
}