#include<iostream>
#include<cstdlib>
#include<ctime>

struct Node
{
    int key;
    struct Node *prev;
    struct Node *next;
};

struct List
{
    struct Node *head;
    struct Node *tail;
};

void ListInit(struct List &L)
{
    L.head = nullptr;
    L.tail = nullptr;
}

bool ListIsEmpty(struct List L)
{
    return (L.head == nullptr && L.tail == nullptr);
}

Node *ListSearch(struct List L,int k)
{
    Node *x = L.head;
    while(x != nullptr && x->key != k)
        x = x->next;
    return x;
}

void ListInsert(struct List &L,int k)
{
    Node *x = new Node;
    x->key = k;
    x->next = L.head;
    if(L.head != nullptr)
        L.head->prev = x;
    L.head = x;
    x->prev = nullptr;
    if(x->next == nullptr)
        L.tail = x;
}

void ListDelete(struct List &L,int k)
{
    Node *x = ListSearch(L,k);
    if(x != nullptr)
    {
        if(x->next == nullptr)
            L.tail = x->prev;
        if(x->prev != nullptr)
            x->prev->next = x->next;
        else
            L.head = x->next;
        if(x->next != nullptr)
            x->next->prev = x->prev;
        delete x;
    }
}

void ListDispayForward(struct List L)
{
    int counter = 0;
    struct Node *p = L.head;
    while(p != nullptr)
    {
        std::cout<<p->key<<" -> ";
        p = p->next;
        counter++;
    }
    std::cout<<"NULL \n";
    std::cout<<"Liczba wezlow listy : "<< counter <<'\n';
}

void ListDispayBackward(struct List L)
{
    int counter = 0;
    struct Node *p = L.tail;
    while(p != nullptr)
    {
        std::cout<<p->key<<" -> ";
        p = p->prev;
        counter++;
    }
    std::cout<<"NULL \n";
    std::cout<<"Liczba wezlow listy : "<< counter <<'\n';
}


void ListSplit(struct List L, struct List &L1,struct List &L2)
{
    struct Node *p,*q;
    //Wyszukiwanie srodkowego wezła
    //Iterujemy wskaźniki z obu stron i gdy się spotkaja to oznacza ze znaleźlismy węzeł
    //Pętla while sprawdza dwa warunki dla list o parzystej i nieparzystej liczbie węzłów
    p = L.head;
    q = L.tail;
    while(p != q && p->next != q)
    {
        p = p->next;
        q = q->prev;
    }
    //Po znalezieniu węzła rozdzielamy listę za znalezionym węzłem
    if(p == nullptr && p->next == nullptr)
    {
        L1.head = L.head;
        L1.tail = L.tail;
        L2.head = nullptr;
        L2.tail = nullptr;
    }
    else
    {
        q = p->next;
        p->next = nullptr;
        q->prev = nullptr;
        L1.head = L.head;
        L1.tail = p;
        L2.head = q;
        L2.tail = L.tail;
    }
}

void ListMerge(struct List &L, struct List L1,struct List L2)
{
    struct Node *curr;
    //Sprawdzamy czy któraś z list jest pusta i zwracamy tę niepustą
    if(ListIsEmpty(L1))
        L.head = L2.head;
    else if(ListIsEmpty(L2))
        L.head = L1.head;
    else
    {
        // Ustawiamy głowę dla listy wynikowej

        if(L2.head->key < L1.head->key)
        {
            L.head = L2.head;
            L.tail = L2.head;
            L2.head = L2.head->next;
        }
        else
        {
            L.head = L1.head;
            L.tail = L1.tail;
            L1.head = L1.head->next;
        }
        curr = L.head;
        L.head->prev = nullptr;
        // Iterujemy wskaźniki dopóki nie osiągniemy końca co najmniej jednej z list
        // dołączając do listy wynikowej węzeł o mniejszym lub równym kluczu
        while(L1.head != nullptr && L2.head != nullptr)
        {
            if(L2.head->key < L1.head->key)
            {
                curr->next = L2.head;
                L2.head->prev = curr;
                L2.head = L2.head->next;
            }
            else
            {
                curr->next = L1.head;
                L1.head->prev = curr;
                L1.head = L1.head->next;
            }
            curr = curr->next;
        }
        //Dołączenie reszty listy do listy wynikowej
        if(L1.head != nullptr)
        {
            curr->next = L1.head;
            L1.head->prev = curr;
            L.tail = L1.tail;
        }
        else
        {
            curr->next = L2.head;
            L2.head->prev  = curr;
            L.tail = L2.tail;
        }
    }
}

void ListMergeSort(struct List &L)
{
    struct List h1,h2;
    if(L.head != nullptr && L.head->next != nullptr)
    {
        ListSplit(L,h1,h2);
        ListMergeSort(h1);
        ListMergeSort(h2);
        ListMerge(L,h1,h2);
    }
}

int main()
{
    int k,n,m,p;
    List L;
    ListInit(L);
    srand(time(nullptr));
        std::cout<<"Ile liczb wylosowac \n";
        std::cin>>n;
        std::cout<<"Podaj gorny zakres przedzialu dla losowanych liczb \n";
        std::cin>>m;
        for(k = 1;k <= n;k++)
            ListInsert(L,rand()%m);
        std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        ListMergeSort(L);
        std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        while(!ListIsEmpty(L))
            ListDelete(L,L.head->key);
        //system("PAUSE");
    return 0;
}