/*(28) Разработать систему «Линейный список» для работы с линейными односвязными списками. Написать следующие функции:
Инициализация списка
Добавление элемента:
В начало списка
В конец списка
Удаление элемента списка
Вставка элемента в упорядоченный список
Печать списка
Создание списка
Проверка списка на пустоту
Для проверки работы всех функций создать меню выбора функции.
ЛЕК_13 (11.05.16):
(29) Дан линейный односвязный список. Написать программу, которая меняет порядок элементов на обратный без использования второго списка.*/

#include <stdio.h>
#include <iostream>
using namespace std;
struct Node
{
    int d;
    Node *next;
    Node *prev;
};
Node *first(int d)//Инициализация списка
{
    Node *pv = new Node;
    pv->d = d; pv->next = NULL; pv->prev = NULL;
    return pv;
}
void add_end(Node **pend, int d)//Добавление в конец списка
{
    Node *pv = new Node;
    pv->d = d; pv->next = NULL; pv->prev = *pend;
    (*pend)->next = pv;
    *pend = pv;
}
void add_beg(Node **pbeg, int d)//Добавление в начало списка
{
    Node *pv = new Node;
    pv->d = d; pv->next = *pbeg; pv->prev = NULL;
    (*pbeg)->prev = pv;
    *pbeg = pv;
}
Node *find(Node *const pbeg, int d)//Поиск элемента по ключу
{
    Node *pv = pbeg;
    while (pv)
    {
        if (pv->d == d)break;
        pv = pv->next;
    }
    return pv;
}
bool remove(Node **pbeg, Node **pend, int key)//Удаление элемента
{
    if (Node *pkey = find(*pbeg, key))
    {
        if (pkey == *pbeg)
        {
            *pbeg = (*pbeg)->next;
            (*pbeg)->prev = NULL;
        }
        else
            if (pkey == *pend)
            {
                *pend = (*pend)->prev;
                (*pend)->next = NULL;
            }
            else
            {
                (pkey->prev)->next = pkey->next;
                (pkey->next)->prev = pkey->prev;
            }
        delete pkey;
        return true;
    }
    return false;
}
Node *insert(Node *const pbeg, Node **pend, int key, int d)//Вставка элемента в список
{
    if (Node *pkey = find(pbeg, key))
    {
        Node *pv = new Node;
        pv->d = d;
        pv->next = pkey->next;
        pv->prev = pkey;
        pkey->next = pv;
        if (pkey != *pend) (pv->next)->prev = pv;
        else *pend = pv;
        return pv;
    }
    return 0;
}
void insert_list(Node *pbeg,Node *pend, int key)//Вставка в упорядоченный список
{
    Node *pv = pbeg;
    while (pv)
    {
        if (pv->d > key)
        {
            pv = pv->prev;
            break;
        }
        if(pv->next!=NULL)pv = pv->next;
        else break;
    }
    if (pv == pend)add_end(&pend, key);
    else
    {
        Node *new_list = new Node;
        new_list->d = key;
        new_list->prev = pv;
        new_list->next = pv -> next;
        pv->next = new_list;
        (new_list->next)->prev = new_list;
    }
}
void Node_print(Node **pbeg)//Печать списка
{
    Node *pv = *pbeg;
    while (pv)
    {
        cout << pv->d << ' ';
        pv = pv->next;
    }
}
bool check(Node **pbeg)//Проверка списка на пустоту
{
    if (pbeg != NULL)return true;
    else false;
}
Node *create()//Создание и заполнение списка
{
    int n;
    int a;
    cout << "Enter number of elements:\n";
    scanf("%d", &n);
    cout << "Enter element number 1:\n";
    scanf("%d", &a);
    Node *pbeg = first(a);
    Node *pend = pbeg;
    for (int i = 1; i < n; i++)
    {
        cout << "Enter element number ";
        cout <<i;
        cout << ":\n";
        scanf("%d", &a);
        add_end(&pend, a);
    }
    return pbeg;
}
Node *revers(Node **pbeg,Node **pend)//Переворот списка
{
    Node *temp;
    Node *pv = *pbeg;
    while (pv != *pend)
    {
        temp = pv->next;
        pv->next = pv->prev;
        pv->prev = temp;
        pv = temp;
    }
    temp = (*pbeg)->next;
    (*pbeg)->next = NULL;
    (*pbeg)->prev = temp;
    temp = (*pend)->prev;
    (*pend)->prev = NULL;
    (*pend)->next = temp;
    return *pend;
}
int main()
{
    Node *default = first(1);
    Node *pend = default;
    int a = 0;
    int d = 0;
    bool test = true;
    for (int i = 2; i < 10; i++)
    {
        add_end(&pend, i*2);
    }
    int c = 0;
    printf("Menu:\n");
    printf("Enter digit to run function:\n");
    printf("0 - Printing standart List\n");
    printf("1 - List inicialization\n");
    printf("2 - Add to end of List\n");
    printf("3 - Add to begin of List\n");
    printf("4 - Delete element\n");
    printf("5 - Insert element to List\n");
    printf("6 - List creating\n");
    printf("7 - Check is List empty or not\n");
    printf("8 - Turn List\n\n");
    printf("9 - Exit\n");
    while (test)
    {
        scanf("%d", &c);
        switch (c)
        {
        case 0://Печать стандартного списка
        {Node_print(&default); break; }
        case 1://Инициализация списка
        {
            printf("Enter first element:\n");
            scanf("%d", &a);
            Node *one = first(a);
            Node_print(&one);
            break;
        }
        case 2://Добавление в конец
        {
            printf("Enter element:\n");
            scanf("%d", &a);
            add_end(&pend, a);
            Node_print(&default);
            break;
        }
        case 3://В начало
        {
            printf("Enter element:\n");
            scanf("%d", &a);
            add_beg(&default, a);
            Node_print(&default);
            break;
        }
        case 4://Удаление
        {
            printf("Enter element:\n");
            scanf("%d", &a);
            if (remove(&default, &pend, a) == false)
            {
                printf("Element is not found.\n");
            }
            else Node_print(&default);
            break;
        }
        case 5://Вставка
        {
            printf("Enter element to insert:\n");
            scanf("%d", &a);
            insert_list(default,pend, a);
            Node_print(&default);
            break;
        }
        case 6://Создание списка
        {
            Node *pv = create();
            Node_print(&pv);
            break;
        }
        case 7://Проверка на пустоту
        {
            if (check(&default) != false)printf("List is not empty.\n");
            else ("List is empty.\n");
            break;
        }
        case 8:
        {
            default = revers(&default, &pend);
            Node_print(&default);
            break;
        }
        case 9:
        {
            test = false;
            break;
        }
        }
    }
}