huffman-new

#include <iostream>
#include <string>
#include <map>
#include <list>
#include <algorithm>
#include <set>

using namespace std;
typedef std::pair <char, unsigned> Element;

class Node {
public:
    char c;
    size_t freq;
    Node *left;
    Node *right;
    Node(){}
    Node(char c_, size_t freq_) :c(c_), freq(freq_), left(nullptr), right(nullptr) {}

};
struct Comparator {

    bool operator()( const Node *left, const Node *right ) const {
        return left->freq < right->freq;
    }
};
class  Huffman
{
public:

    std::map <char, unsigned> mapFreq;
    std::list <Node*> lstFreq;
    std::map <char, std::vector<bool> > mapHuffman;
    Node* root;

     Huffman(const std::string inputStr)  {

         for (auto some : inputStr) {
             mapFreq[some]++;
         }
         root = new Node();
     }

     unsigned getLetterNumber() const {
         return mapFreq.size();
     }

     void createVectorMap(Node* node, std::vector <bool> &sHuffman) {

         if ((node->left == nullptr) && (node->right == nullptr)) {
             mapHuffman[node->c] = sHuffman;
          }
         else
         {
             if (node->left != nullptr)  {
                 std::vector <bool> sHuffmanL=sHuffman;
                 sHuffmanL.push_back(true);
                 createVectorMap(node->left, sHuffmanL);
             }
             if (node->right != nullptr) {
                 std::vector <bool> sHuffmanR=sHuffman;
                 sHuffmanR.push_back(false);
                 createVectorMap(node->right, sHuffmanR);
             }

         }
     }

     void solve() {
         for (auto const& some : mapFreq) {
          //  Node* node = new Node(some.first, some.second);
            lstFreq.push_back(new Node({some.first, some.second}));
         }
        lstFreq.sort(Comparator());
        for (auto const some : lstFreq) {
         //  Node* node = new Node(some.first, some.second);
           std::cout << some->c << some->freq << ", ";
        }

        // создаем дерево
         while (lstFreq.size() >1) {
            lstFreq.sort(Comparator());

            std::cout << lstFreq.size();
            Node *leftNode = lstFreq.front();

            lstFreq.pop_front();

            Node *rightNode = lstFreq.front();

            lstFreq.pop_front();

            Node *newNode  = new Node();
            newNode->freq = leftNode->freq + rightNode->freq;
            newNode->left = leftNode;
            newNode->right = rightNode;

            lstFreq.push_front(newNode);

         }

         root = lstFreq.front();
         root->left = lstFreq.front()->left;
         root->right = lstFreq.front()->right;
         lstFreq.pop_front();

         std::vector <bool> v1;
         //v1.push_back(false);
         createVectorMap(root, v1);

     }



     void print(Node* node) {

         if ((node->left == nullptr) && (node->right == nullptr)) {
              std::cout << "("<< node->c <<")"<< " : " <<node->freq << endl;
         }
         else
         {
             if (node->left != nullptr)  {
                 std::cout << "l";
                 print(node->left);
             }
             if (node->right != nullptr) {
                 std::cout << "r";
                 print(node->right);
             }

         }

        }

     void print() {
         print(root);
     }

     void printHuffmanTable() {
         for (auto some : mapHuffman ){
             std::cout << some.first << ": ";
             for ( auto somebit : some.second ) {
                std::cout << (somebit) ?  "1" : "0";
             }
             std::cout << endl;
         }
     }
};

int main()
{
    std::string inputStr;
    std::getline (std::cin, inputStr);
    Huffman huffman(inputStr);
    huffman.solve();
    huffman.print();
    huffman.printHuffmanTable();




    return 0;
}