tahmids_tree

/*  TAHMID RAHMAN
    DAMIAN FOREVER
     MATH LOVER
    NEVER GIVE UP
*/
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define pb push_back
#define fi first
#define se second
#define in insert
#define mp make_pair
#define GCD(a,b) __gcd(a,b);
#define endl "\n"
#define FRU freopen("out.txt","w",stdout)
#define FRO freopen("in.txt","r",stdin)
#define INFLL 9223372036854775807
#define debug 0
#define MAXN   100001
#define ar array
#define lb lower_bound
#define ub upper_bound
const int mxN=2e5;
const int MOD=1e9+7;
template<typename ForwardIterator, typename T>
ForwardIterator first_less_than (ForwardIterator first, ForwardIterator last, T value)
{auto it = std::lower_bound (first, last, value);
return (it == first ? last : --it);}
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
    return (a.second < b.second);
}
#define debugxx(v) {for(auto x:v){cout<<x.fi<<" "<<x.se<<endl;}cout<<endl;}
#define debugx(v){for(auto y:v) {cout<<y<<" ";}cout<<endl;}


map<char,string>priff_codes;


struct parent
{
    char ch;
    double freq;

    parent *left;
    parent *right;

};



string genarate_id(string s)
{
    string id="MYIDIS";
    map<char,string>m;
    m['0']="ZERO",m['1']="ONE",m['2']="TWO",m['3']="THREE",m['4']="FOUR",
    m['5']="FIVE",m['6']="SIX",m['7']="SEVEN",m['8']="EIGHT",m['9']="NINE";
    ll i;

    for(i=s.size()-4;i<s.size();i++)
    {
        id+=m[s[i]];
    }

    return id;

}


void traverse(struct parent *memo,string s)
{

    if(memo->left==NULL&&memo->right==NULL)
    {
        //leaf node
        priff_codes[memo->ch]=s;
        return ;

    }

    //not a leaf node


    //left_subtree <--
    if(memo->left)
        traverse(memo->left,s+'0');


    //right_subtree -->
    if(memo->right)
        traverse(memo->right,s+'1');


}


bool sort_compo(struct parent *num1,struct parent *num2)
{
    if(num1->freq<num2->freq)
        return true;
    else
        return false;
}


void priffix_code(string s)
{
    deque<struct parent*>nodes;

    map<char,ll>f;

    ll i;

    for(i=0;i<s.size();i++)
    {
        f[s[i]]++;
    }


    for(auto x:f)
    {
        struct parent *temp=new struct parent;
        temp->ch=x.fi;
        temp->freq=x.se*1.00/s.size()*1.00;
        temp->left=NULL;
        temp->right=NULL;
        nodes.push_back(temp);
    }



    sort(nodes.begin(),nodes.end(),sort_compo);

    /*for(i=0;i<nodes.size();i++)
    {
        cout<<nodes[i]->ch<<" "<<nodes[i]->freq<<endl;
    }

    cout<<endl;*/


    while(nodes.size()!=1)
    {

        struct parent *temp1=new struct parent;
        temp1->freq=nodes[0]->freq+nodes[1]->freq;
        temp1->ch=max(nodes[0]->ch,nodes[1]->ch);
        temp1->left=nodes[1];
        temp1->right=nodes[0];

        nodes.pop_front();
        nodes.pop_front();

        nodes.push_back(temp1);

        sort(nodes.begin(),nodes.end(),sort_compo);

    }


    traverse(nodes[0],"");


}





int main()
{

    string stu_id;
    cout<<"Step #1."<<"  "<<"Enter Student ID: ";
    cin>>stu_id;
    string id=genarate_id(stu_id);
    priffix_code(id);
    cout<<"Step #2."<<"  "<<"Generated String: "<<id<<endl;
    cout<<"Step #3."<<"  "<<"Prefix Codes (GENERATED USING HUFFMAN CODING):"<<endl;
    set<char>st;

    for(ll i=0;i<id.size();i++)
    {
        if(!st.count(id[i])){
        cout<<"          "<<id[i]<<" :"<<"   "<<priff_codes[id[i]]<<endl;
        st.in(id[i]);
        }
    }

}