#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;
int o = 0;
double s_t, e_t;

struct Node
{
    int number;
    Node*next;
    Node*back;
};

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

// Добавить ячейку
void addNode(List *L){
    Node *temp = new Node;
    temp->number = rand()%10;
    temp->next = NULL;
    if(L->head != NULL){                           // Если список не пуст
        temp->back = L->tail;
        L->tail->next = temp;
        L->tail = temp;
    } else {                                        // Если пустой
        temp->back = NULL;
        L->head = L->tail = temp;
    }
}

void insertNode(List *L){
    int n;
    cout << "\nВведите номер для новой ячейки: ";
    cin >> n;
    while(n<0 || n>L->count)
    {
        cout<<"\nТакой ячейки нет. Введите номер ячейки заново: ";
        cin>> n;
    }
    s_t = clock();
    Node*temp=new Node;
    temp->number=rand()%10;
    if(n == 0){
        // вставка в начало
        L->head->back=temp;
        temp->next=L->head;
        L->head=temp;
    } else if(n == L->count){
        // вставка в конец
        addNode(L);
    } else {
        // вставка в серидину
        Node*random=L->head;
        for(int i=0; i<n-1; i++)
        {
            random=random->next;
        }
        random->next->back=temp;
        temp->back=random;
        temp->next = random->next;
        random->next=temp;
    }
    L->count++;
    temp = L->head;
    for(int i = 0; i < L->count; i++){
        cout << temp->number << " ";
        temp = temp->next;
    }
    cout << endl;
}

void createList(List *L){
    L->head = NULL;
    L->tail = NULL;
    int n;
    cout << "Введите длину двусвязного списка: ";
    cin >> n;
    while(n < 1){
        cout << "Введите заново: ";
        cin >> n;
    }
    L->count = n;
    for(int i = 0; i < n; i++){
        addNode(L);
    }
    Node *temp = L->head;
    for(int i = 0; i < n; i++){
        cout << temp->number << " ";
        temp = temp->next;
    }
}

void deleteNode(List *L){
    int n;
    cout << endl;
    do{
        cout << "Какую ячейку удалим?) Номер: ";
        cin>>n;
    } while(n < 0 || n > L->count);
    s_t = clock();
    if((n == 0) && (L->head->next)){               // Если удаляется Ячейка под номером 1, но помимо его есть еще и другие
        Node *temp = L->head;                      // Указываем на начало списка
        L->head=L->head->next;                    // Сдвигаем начало на пункт номер 2
        L->count--;
        Node *temp3 = L->head;
        for(int i = 0; i < n; i++){
            cout << temp3->number << " ";
            temp3 = temp3->next;
        }
        return;                                     // Выходим из функции
    } else if((n == 0) && (L->head=L->tail)){      // Если удаляется Ячейка под номером 1, при условии что в списке только он
        L->head->next = NULL;                      // Обнуляем элементы
        L->head = NULL;
        L->count--;
        Node *temp3 = L->head;
        for(int i = 0; i < n; i++){
            cout << temp3->number << " ";
            temp3 = temp3->next;
        }
        return;
    }
    if(n == L->count-1){                              // Если удаляют Ячейку из конца списка
        Node *temp = L->tail;                    // Смещаем указатель последнего элемента на тот, который стоял перед ним
        L->tail = L->tail->back;                    // Обнуляем крайний УДАЛЕННЫЙ элемент
        L->tail->next = NULL;
        L->count--;
        Node *temp3 = L->head;
        for(int i = 0; i < n; i++){
            cout << temp3->number << " ";
            temp3 = temp3->next;
        }
        return;
    }
    Node *temp = L->head, *temp2;
    for(int i = 0; i < n; i++){ // Добираемся до нужного элемента
        temp = temp->next;
    }
    temp2 = temp;                                   // Временно запоминаем адресс удаляемого элемента
    temp2->back->next = temp->next;
    temp2->next->back = temp->back;
    L->count--;
    Node *temp3 = L->head;
    for(int i = 0; i < L->count; i++){
        cout << temp3->number << " ";
        temp3 = temp3->next;
    }
}

void findNode(List *L){
    int n;
    cout << endl;
    cout << "Какую ячейку выведем?:) Номер: ";
    cin >> n;
    while(n < 0 || n > L->count){
        cout << "Ошибка. Введите заново: ";
        cin >> n;
    }
    s_t = clock();
    Node *temp = L->head;
    for(int i = 0; i < n; i++){
        temp = temp->next;
    }
    cout << "Значение ячейки " << n << " равно " << temp->number << endl;
}

//Вставка
void mVstavka(int *A, int n) //x-номер, р- значение
{
    int x,*B;
    cout<<endl;
    cout<<"ВСТАВКА"<<endl;
    for(int i=0; i<n; i++)
    { cout<<A[i]<<" ";
    }
    cout<<"\nВведите номер для новой ячейки: ";
    cin>> x;
    while(x<0 || x>n)
    {cout<<"\nТакой ячейки нет. Введите номер ячейки заново: ";
    cin>> x;
    }
    s_t = clock();
    B=new int [n+1];
    int m=0;
    for(int i=0; i<n+1; i++)
    {
        if (i==x){
        B[i]=rand()%10;
        continue;
        }
        B[i]=A[m];
        m++;
    }
    delete[]A;
    A=new int [n+1];
    for(int i=0; i<n+1; i++)
    {
    A[i]=B[i];
    cout<<A[i]<<" ";
    }
    o++;
};

//Удаление
void mDelete (int *A, int n)
{
    int x, *B;
    cout<<endl<<endl;
    cout<<"УДАЛЕНИЕ"<<endl;
    for(int i=0; i<n; i++)
    { cout<<A[i]<<" ";
    }
    cout<<"\nВведите номер ячейки, которую хотите удалить: ";
    cin>> x;
    while(x<0 || x>=n)
    {cout<<"\nТакой ячейки нет. Введите номер ячейки заново: ";
    cin>> x;
    }
    s_t = clock();
    B=new int[n-1];
    int c = 0;
    for (int i=0; i<n; i++)
    {
        if(i == x) continue;
        B[c] = A[i];
        c++;
    }
    delete[]A;
    A = new int[n-1];
    for (int i=0; i<n-1; i++)
    {
        A[i] = B[i];
        cout << A[i] << " ";
    }
    delete[]B;
    o--;
}

//Получение значения
void mNumber(int *A, int n)
{
    int x;
    cout<<endl<<endl;
    cout<<"ПОЛУЧЕНИЕ ЗНАЧЕНИЯ"<<endl;
    cout<<"Введите номер ячейки: ";
    cin>>x;
    while(x<0 || x>n){
    cout<<"Неправильный номер ячейки. Введите новый: ";
    cin>>x;
    }
    s_t = clock();
    cout<<"Значение ячейки "<< x<<" Равно "<< A[x]<< endl;
};


void main()
{
    setlocale(LC_ALL, "Russian");
    int t, *A;
    bool m = 1;
    List *L = new List;
    int type = 0; // 1 - массив, 2 - список
    cout << "Привет с:\n";
    do{
        do{
            cout << "\nВыберите структуру данных:\n1. Динамический массив\n2. Двусвязный список\n0. Выход\n--> ";
            cin >> t;
        } while(t<0 || t > 2);
        if(t == 0){
            m = 0;
            return;
        }
        type = t;
        if(type == 1){
            cout<<"Введите длину динамического массива: ";
            cin>>o;
        }
        A=new int[o];
        if(type == 1){
            for(int i=0; i<o; i++)
            {
                A[i]= rand()%10;
            }
        } else if(type == 2){
            L = new List;
            createList(L);
        }
        do{
            cout << "\nВыберите операцию:\n1. Вставка\n2. Удаление\n3. Получение элемента\n0. Выход\n--> ";
            cin >> t;
        } while(t<0 || t > 3);
        if(t == 0) m = 0;
        switch(t){
            case 1:{
                if(type == 1) mVstavka(A, o), e_t = clock();
                else if(type == 2) insertNode(L), e_t = clock();
                break;
            }
             case 2:{
                if(type == 1)mDelete(A, o), e_t = clock();
                else if(type == 2) deleteNode(L), e_t = clock();
                break;
            }
            case 3:{
                if(type == 1) mNumber(A, o), e_t = clock();
                else if(type == 2) findNode(L), e_t = clock();
                break;
            }
        }

        cout << endl << (e_t-s_t) << "мс." << endl;
    }while(m);
    system("pause");
}