#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 Node *x,struct List L,struct List &L1,struct List &L2)
{
    struct Node *inputHead;
    struct Node *nextX;
    if(x == nullptr || x->next == nullptr)
    {
        L1.head = L.head;
        L1.tail = L.tail;
        L2.head = nullptr;
        L2.tail = nullptr;
    }
    else
    {
        inputHead = L.head;
        nextX = x->next;
        x->next = nullptr;
        nextX->prev = nullptr;
        L1.head = inputHead;
        L1.tail = x;
        L2.head = nextX;
        L2.tail = L.tail;
    }
}


int main()
{
    int k,n,m,p;
    List L,L1,L2;
    Node *x;
    ListInit(L);
    ListInit(L1);
    ListInit(L2);
    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);
        std::cout<<"Podaj element za ktorym chcesz rozdzielic liste \n";
        std::cin>>p;
        x = ListSearch(L,p);
        ListSplit(x,L,L1,L2);
        std::cout<<"Lista L1 \n";
        ListDispayForward(L1);
        ListDispayBackward(L1);
        std::cout<<"Lista L2 \n";
        ListDispayForward(L2);
        ListDispayBackward(L2);
        std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        while(!ListIsEmpty(L1))
           ListDelete(L1,L1.head->key);
        while(!ListIsEmpty(L2))
           ListDelete(L2,L2.head->key);
        std::cout<<"Lista L1 \n";
        ListDispayForward(L1);
        ListDispayBackward(L1);
        std::cout<<"Lista L2 \n";
        ListDispayForward(L2);
        ListDispayBackward(L2);
       std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        system("PAUSE");
    return 0;
}