#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

#define COUNT 10

struct Node
{
    int value;
    char symbol;

    Node* next, * prev;
    Node* left, * right;

    Node()
    {
        prev = next = left = right = nullptr;
    }

    Node(int value, char symbol, Node* next, Node* prev)
    {
        this->value = value;
        this->symbol = symbol;
        this->next = next;
        this->prev = prev;
        left = right = nullptr;
    };

    Node(int value, char symbol, Node* next, Node* prev, Node* left, Node* right)
        : value(value), symbol(symbol), next(next), prev(prev), left(left), right(right) {};
};

class list
{
private:
    Node* first;
    Node* last;
public:
    list();
    bool isEmpty();

    Node* getFirst();
    bool hasOnlyOne();
    void push(int value, char symbol);
    void push(Node* node);
    Node* pop();
    void sort();
    void print();

};

list::list()
{
    first = last = nullptr;
};



void print(Node* root, int space)
{
    if (root == nullptr)
        return;

    space += COUNT;

    print(root->left, space);

    cout << endl;
    for (int i = COUNT; i < space; i++)
        cout << " ";
    cout << root->value  << " (" << root->symbol  << ")"<< "\n";

    print(root->right, space);
}


bool compareFunction(Node* a, Node* b)
{
    return a->value < b->value;
}

map<char, vector<int>> table;
vector<int> code;

void BuildTable(Node* root);

int main()
{
    vector<int> repeats;// создаем переменную типа x
    string str = "it is my striiiiiiing!!!!!";
    map<char, int> m;
    for (int i = 0; i < str.length(); i++)
    {
    	if(str[i] != ' ')
			m[str[i]]++;
    }

    vector<Node*> toSort;
    list myList;
    for (map<char, int>::iterator it = m.begin(); it != m.end(); ++it)
    {
        myList.push(it->second, it->first);
    }

     while (!myList.hasOnlyOne())
    {
        myList.sort();
        Node* rSon = myList.pop();
        Node* lSon = myList.pop();

        int value = rSon->value + lSon->value;
        char symbol = ' ';


        Node* parent = new Node(value, symbol, nullptr, nullptr, lSon, rSon);

        myList.push(parent);
     }

    Node* root = myList.getFirst();

    BuildTable(root);

    for (auto it : table)
    {
        cout << endl;
        cout << "Symbol = " << it.first << " | Code = ";
        for (size_t i = 0; i < it.second.size(); i++)
            cout << it.second[i];
    }

    cout << endl;
    print(root,0);
    return 0;
}

void BuildTable(Node* root)
{
    if (root->symbol != ' ')
        table[root->symbol] = code;

    if (root->left != NULL)
    {
        code.push_back(0);
        BuildTable(root->left);
    }

    if (root->right != NULL)
    {
        code.push_back(1);
        BuildTable(root->right);
    }

    if (root->left == NULL && root->right == NULL)
       if(root->symbol != ' ')
        table[root->symbol] = code;


	if(!code.empty())
        code.pop_back();
}

bool
list::isEmpty()
{
    return first == nullptr;
}

Node* list::getFirst()
{
    return first;
}

bool
list::hasOnlyOne()
{
    return first == last;
};

void
list::push(int value, char symbol)
{

    if (isEmpty())
    {
        Node* newNode = new Node(value, symbol, nullptr, nullptr);
        first = last = newNode;

    }
    else
    {
        if (first == last)
        {
            Node* newNode = new Node(value, symbol, nullptr, first);
            last = newNode;
            first->next = last;
        }
        else
        {
            Node* newNode = new Node(value, symbol, nullptr, last);
            last->next = newNode;
            last = last->next;
        }

    }

}

void
list::push(Node* node)
{

    if (isEmpty())
    {
        Node* newNode = new Node(node->value, node->symbol, nullptr, nullptr, node->left, node->right);
        first = last = newNode;

    }
    else
    {
        if (first == last)
        {
            Node* newNode = new Node(node->value, node->symbol, nullptr, first, node->left, node->right);
            last = newNode;
            first->next = last;
        }
        else
        {
            Node* newNode = new Node(node->value, node->symbol, nullptr, last, node->left, node->right);
            last->next = newNode;
            last = last->next;
        }

    }
}

Node*
list::pop()
{
    if (isEmpty())
        throw exception("List is empty");

    if (first == last)
    {
        Node* nodeToReturn = new Node(first->value, first->symbol, nullptr, nullptr, last->left, last->right);
        delete first;
        first = last = nullptr;
        return nodeToReturn;
    }

    Node* nodeToReturn = new Node(last->value, last->symbol, nullptr, nullptr, last->left,last->right);
    Node* toDelete = last;
    last = last->prev;
    delete toDelete;

    return nodeToReturn;
}

void
list::sort()
{
    Node* temp = first;
    while (temp->next != nullptr)
    {
        if (temp->value < temp->next->value)
        {
            swap(temp->value, temp->next->value);
            swap(temp->symbol, temp->next->symbol);
            swap(temp->left , temp->next->left);
            swap(temp->right, temp->next->right);
        	temp = temp->next;
            sort();
        }
        else
            temp = temp->next;

    }
}

void list::print()
{
    Node* it = first;

    cout << endl;
    while (it != nullptr)
    {
        cout << it->value << "-[" << it->symbol << "] ";
        it = it->next;
    }
}