#include <iostream>

using namespace std;

/*
     ________
    |  Data  |
    |________|
    | *next  |
    |________|
*/

struct Data
{
    int data;
    Data *next;
    
    Data(int);                  //  Data(int val)
    ~Data();
    void print();
};
//  konstruktor
Data :: Data(int val)
{
    data = val;
    next = NULL;
    //  Ponizej jest rysunek jak wyglada lista
    //  - element i wskaznik na kolejny element
    //  - na koncu wskaznik na pusty element
}

Data :: ~Data()
{
    cout << "Deleted ";
    print();
    cout << endl;
}

void Data :: print()
{
    cout << " (" << data << ") ";
}

/*
         ________      ________      ________          ________      ________
        |  Data  |  ->|  Data  |  ->|  Data  |        |  Data  |  ->|  NULL  |
  List: |________| /  |________| /  |________|   ...  |________| /  |________|
        | *next  |/   | *next  |/   | *next  |        | *next  |/   |        |
        |________|    |________|    |________|        |________|    |________|
          first         ->next        ->next     ...    ->next        ->next
                                        ^
                                        |
                                first->next->next
*/

struct List
{
    //  pierwszy element listy
    Data *first;
    
    List();
    List(int);                  //  List(int val)
    ~List();
    void push(int);             //  push(int val)
    int pop();
    void replace(int, int);     //  replace(int pos, int val)
    void insert(int, int);      //  insert(int pos, int val);
    void erase(int);            //  erase(int pos);
    void print();
    int size();
    void sort();
};

//  konstruktor tworzy pierwszy blok jako pusty
List :: List()
{
    cout << "New empty list" << endl;
    first = NULL;
}

//  konstruktor tworzy pierwszy element
//  kontruktor elementu tworzy wskaznik na kolejny pusty blok
List :: List(int val)
{
    cout << "New initialised list" << endl;
    first = new Data(val);
}

//  destruktor usuwa wszystkie elementy z listy
List :: ~List()
{
    cout << "List has been deleted" << endl;
    Data *temp = first;
    //  Windows:
    Data *next = first->next;
    
    //  chodzimy po liscie
    //  Linux:
    //  while (temp)
    //  Windows:
    while (temp->next)
    {
        //  usuwamy obecny
        delete temp;
        //  temp wskazuje na nastepny
        //  Linux:
        //  temp = temp->next;
        //  Windows:
        temp = next;
        next = next->next;
    }
    
    //  pozostanie nam ostatni element do usuniecia
    delete temp;
}

//  wstawiamy nowy element na koncu listy,
//  pusty blok staje sie nowym elementem
void List :: push(int val)
{
    cout << "Pushed data into list (" << val << ")" << endl;
    //  tworzy nowy element
    Data *data = new Data(val);
    
    if (first == NULL)
    {
        /*
            Gdy lista nie zawiera elementow
                 ________
                |  NULL  |
          List: |________|
                |        |
                |________|
                 push(val)
            Wstawiamy elment jako pierwszy
                 ________      ________
                |  Data  |  ->| NULL   |
          List: |__(val)_| /  |________|
                | *next  |/   |        |
                |________|    |________|
        */
        
        first = data;
    }
    else
    {
        /*
            Gdy lista zawiera elementy, obchodzimy ja do konca i tam
            wstawiamy nowy element
                 ________      ________      ________
                |  Data  |  ->|  Data  |  ->|  NULL  |
          List: |________| /  |________| /  |________|
                | *next  |/   | *next  |/   |        |
                |________|    |________|    |________|
                                             push(val)
            Wstawiamy element na koniec
                 ________      ________      ________      ________
                |  Data  |  ->|  Data  |  ->|  Data  |  ->|  NULL  |
          List: |________| /  |________| /  |__(val)_| /  |________|
                | *next  |/   | *next  |/   | *next  |/   |        |
                |________|    |________|    |________|    |________|
        */
        //  zaczynamy od pierwszego elementu
        Data *temp = first;
        
        //  chodzimy po liscie tak dlugo, az aktualny element
        //  nie wskazuje na pusty blok
        while (temp->next)
        {
            temp = temp->next;
        }
        
        //  jak znajdzie taki blok to go uzupelnia
        temp->next = data;
        temp->next->next = NULL;
    }
}

//  Sciaga ostatni element z listy zastepujac go pustym blokiem
int List :: pop()
{
    /*
             ________      ________      ________      ________
            |  Data  |  ->|  Data  |  ->|  Data  |  ->|  NULL  |
      List: |________| /  |________| /  |__(val)_| /  |________|
            | *next  |/   | *next  |/   | *next  |/   |        |
            |________|    |________|    |________|    |________|
                                           pop()
        Sciagamy ostatni
             ________      ________      ________
            |  Data  |  ->|  Data  |  ->|  NULL  |
      List: |________| /  |________| /  |________|
            | *next  |/   | *next  |/   |        |
            |________|    |________|    |________|
    */
    int ret_val;
    
    if (first == NULL)
    {
        //  Jezeli lista pusta to error
        cout << "Empty list! Cannot pop." << endl;
        ret_val = 0;
    }
    else if (!first->next)
    {
        //  Jezeli lista 1-elementowa to usuwamy i zerujemy
        ret_val = first->data;
        delete first->next;
        
        first = NULL;
    }
    else
    {
        //  Jezeli lista >1-elementowa
        //  poprzednik ostatniego
        Data *prev = first;
        //  ostatni
        Data *data = first->next;
        
        //  chodzimy po liscie tak dlugo, az ostatni element
        //  nie wskazuje na pusty blok
        while (data->next)
        {
            prev = prev->next;
            data = data->next;
        }
        
        //  zwracamy dane z ostatniego
        ret_val = data->data;
        //  usuwamy ostatni
        delete data;
        //  poprzednik wskazuje na pusty blok
        prev->next = NULL;
    }
    
    cout << "Popped data from list (" << ret_val << ")" << endl;
    
    return ret_val;
}

void List :: replace(int pos, int val)
{
    if (pos < 1 or pos > size())
    {
        cout << "Index out of range!" << endl;
        return;
    }
    else
    {
        cout << "Data at pos " << pos << " has been replaced by " << val << endl;
        int i = 1;
        
        Data *temp = first;
        
        while (i != pos)
        {
            i++;
            temp = temp->next;
        }
        
        temp->data = val;
    }
}

void List :: insert(int pos, int val)
{
    //  nowy element
    Data *data = new Data(val);
    if (pos < 1)
    {
        cout << "Index out of range!" << endl;
        return;
    }
    else if(!first)
    {
        cout << "Inserted " << val << " at pos " << pos << endl;
        //  gdy lista pusta wstawiamy nowy element jako pierwszy
        first = data;
    }
    else
    {
        cout << "Inserted " << val << " at pos " << pos << endl;
        int i = 1;
        
        if (!first)
        {
            //  Jezeli lista pusta
            first = data;
        }
        else
        {
            //  Jezeli lista zawiera elementy
            //  poprzednik
            Data *prev = first;
            //  nastepnik
            Data *next = first->next;
            
            if (pos == 1)
            {
                first = data;
                data->next = prev;
            }
            else
            {
                while (i != pos)
                {
                    i++;
                    prev = prev->next;
                    next = next->next;
                }
                
                //  poprzednik wskazuje na nowy element
                prev->next = data;
                //  nowy element wskazuje na nastepnik;
                data->next = next;
            }
        }
    }
}

void List :: erase(int pos)
{
    if (pos < 1 or pos > size())
    {
        cout << "Index out of range!" << endl;
        return;
    }
    else
    {
        cout << "Erased data from pos " << pos << endl;
        int i = 1;
        Data *temp = first;
        
        if (pos == 1)
        {
            //  Jezeli usuwamy pierwszy element
            delete first;
            //  pierwszy staje sie nastepnym
            first = temp->next;
        }
        else
        {
            //  chodzimy po liscie
            while (temp)
            {
                if ((i + 1) == pos)
                {
                    //  Jezeli kolejny ma byc usuniety
                    //  zapisujemy sobie kolejny po usuwanym
                    Data *temp2 = temp->next->next;
                    
                    //  usuwamy
                    delete temp->next;
                    //  obecny wskazuje na kolejny po usuwanym
                    temp->next = temp2;
                    
                    break;
                }
                
                temp = temp->next;
                i++;
            }
        }
    }
}

void List :: print()
{
    cout << "HEAD";
    
    Data *temp = first;
    
    while (temp)
    {
        cout << "->";
        temp->print();
        temp = temp->next;
    }
    
    cout << endl;
}

int List :: size()
{
    int size = 0;
    
    Data *temp = first;
    
    while (temp)
    {
        size++;
        temp = temp->next;
    }
    
    return size;
}

void List :: sort()
{
    if (!first or !first->next)
    {
        return;
    }
    else
    {
        Data *prev = first;
        for (int i = 0; i < size(); i++)
        {
            Data *next = prev->next;
            int temp;
            
            for (int j = i; j < size() - 1; j++)
            {
                if (prev->data > next->data)
                {
                    temp = prev->data;
                    prev->data = next->data;
                    next->data = temp;
                }
                
                next = next->next;
            }
            
            prev = prev->next;
        }
    }
}

int main()
{
    List *lista = new List();
    
    lista->print();
    
    lista->insert(1, -5);
    lista->print();
    
    lista->push(-1);
    lista->push(2);
    lista->push(-2);
    lista->print();
    
    lista->sort();
    lista->print();
    
    lista->pop();
    lista->print();
    
    lista->replace(0, 4);
    lista->replace(1, 4);
    lista->print();
    
    lista->insert(1, 6);
    lista->print();
    
    lista->erase(6);
    lista->erase(3);
    lista->print();
    
    delete lista;
    
    return 0;
}