#include <iostream>
#include <fstream>
#include <string>
using namespace std;


struct cell
{
    char symbol;
    size_t amount;

    cell* next;

    cell(char symbol) : symbol(symbol), next(nullptr)
    {
        amount = 1;
    }
    cell(char symbol, size_t amount) : symbol(symbol), amount(amount),next(nullptr)
    {
    }
};

class queue
{
private:
    cell* first;
    cell* last;
    size_t size;
public:
    queue() : first(nullptr), last(nullptr), size(0) {};
    bool isEmpty() { return size == 0; }

    void push(char symbol);
    void push(cell put);
    cell pop();
    void sortByAmount();

    friend void print(const queue my);
    friend void fillFromFile(queue& my, const char* fileName);
};

void print(queue my)
{
    if(my.isEmpty())
    {
        cout << "Queue is empty" << endl;
        return;
    }


    size_t counter = 1;
    cell* it = my.first;
    while(it!= nullptr)
    {
        cout << counter++ << ") Symbol = " << it->symbol << " | Amount = " << it->amount << endl;
        it = it->next;
    }
};

void fillFromFile(queue& my, const char* fileName)
{
    ifstream input(fileName);
    if (!input.is_open())
    {
        cout << "File is not open" << endl;
        return;
    }

    string text;
    while (!input.eof())
    {
        string tmp;
        getline(input, tmp);
        text += tmp;
    }

    for (size_t i = 0; i < text.size(); i++)
        if(text[i] != ' ')
            my.push(text[i]);

    input.close();
}


int main()
{
    queue a;
    fillFromFile(a, "file.txt");
    cout << "Before adding" << endl;
    print(a);

    a.sortByAmount();
    cout << "After adding" << endl;
    print(a);


    return 0;
}



void
queue::push(char symbol)
{

    if(isEmpty())
    {
        cell* newCell = new cell(symbol);
        first = last = newCell;
        size++;
        return;
    }

    cell* it = first;
    while (it != nullptr)
    {
        if (it->symbol == symbol)
        {
            it->amount++;
            return;
        }
        it = it->next;
    }

    cell* newCell = new cell(symbol);
    last->next = newCell;
    last = newCell;
    size++;

}

void
queue::push(cell put)
{

    if (isEmpty())
    {
        cell* newCell = new cell(put.symbol,put.amount);
        first = last = newCell;
        size++;
        return;
    }

    cell* it = first;
    while (it != nullptr)
    {
        if (it->symbol == put.symbol)
        {
            it->amount += put.amount;
            return;
        }
        it = it->next;
    }
    cell* newCell = new cell(put.symbol,put.amount);
    last->next = newCell;
    last = newCell;
    size++;

}

cell
queue::pop()
{
    if(isEmpty())
    {
        cout << "Error: Queue is empty " << endl;
        return '-';
    }

    if(first != last)
    {
        cell toReturn = *first;
        cell* toDelete = first;

        first = first->next;
        delete toDelete;
        size--;
        return toReturn;
    }
    else
    {
        cell toReturn = *first;
        delete first;
        first = last = nullptr;
        size--;
        return toReturn;
    }
}

void queue::sortByAmount()
{
    queue temp;

    while (!isEmpty())
    {
        cell min = *first;

        for(size_t i = 1; i < size; i++)
        {
            cell toCheck = pop();
            if (toCheck.amount < min.amount)
                min = toCheck;
            push(toCheck);
        }

        while(true)
        {
            cell toCheck = pop();
            if(toCheck.amount == min.amount && toCheck.symbol == min.symbol)
            {
                break;
            }
            push(toCheck);
        }

        temp.push(min);
    }

    while (!temp.isEmpty())
        push(temp.pop());
}