#include <iostream>

using namespace std;

struct Item {
    Item* next;
    int data;

    Item(int value) // конструктор, для создания нового элемента
    {
        data = value;
        next = this;
    }
};
typedef Item* List;

List initEmptyList(); // инициализация пустого списка;
List purgeList(List); // уничтожение списка с освобождением памяти;
List addToHead(List, int); //добавление узла в голову списка;
List addToTail(List, int); // добавление узла в хвост списка;
List deleteFromHead(List); // удаление узла из головы списка;
List deleteFromTail(List); // удаление узла из хвоста списка;
void drawList (List); // выдача текущего списка на экран.

List firstSecondSwap(List); // Обмен первого узла и второго
List removeFromPosition(List, int); // Удаление узла в указанной позиции

List initEmptyList()
{
    return nullptr; // nullptr - указатель на NULL
    //если указатель на элемент списка равен nullptr, значит список пуст
    // if (tail == nullptr) - проверка на пустоту
}


List addToHead(List tail, int value)
{
    if (tail == nullptr) return new Item(value); // список пуст, значит просто создаём элемент

    List p = new Item(value);
    p->next = tail->next; // новый элемент указывает на голову
    // Список циклический, поэтому любое tail->next - это начало списка
    tail->next = p; // хвост указывает на новый элемент

    return tail;
}

List addToTail(List tail, int value)
{
    // Добавляем в голову, и идём один раз вперёд
    // Добавление в голову и в хвост осущетсвляется на одинаковые позиции в списке
    // Между головой и хвостом
    // Разница только в том, что при добавлении в голову, ты возвращаешь исходный указатель
    // А при добавлении в хвост, следующий
    tail = addToHead(tail,value);
    tail = tail->next;
    return tail;
}

List deleteFromHead(List tail)
{
    if (tail == nullptr) return nullptr; // Список пустой, нечего удалять

    if (tail->next == tail) // Список из одного элемента
    {
        delete tail;
        return nullptr;
    }

    List tmp = tail->next; // сохраняем голову, делаем так, чтобы хвост указывал на следующий элемент
    tail->next = tmp->next;

    // Голова теперь не принадлежит списку, её можно вычищать из памяти
    delete tmp;

    return tail;
}


List deleteFromTail(List tail)
{
    if (tail == nullptr) return nullptr;

    if (tail->next == tail)
    {
        delete tail;
        return nullptr;
    }

    // Верхние два ифа как и в удалении с головы

    List tmp = tail;
    while(tmp->next != tail) tmp = tmp->next; // идём до предпоследнего элемента

    tmp = deleteFromHead(tmp); // удаляем следующий за предпоследним элемент, теперь он - хвост списка

    return tmp; // возвращаем обновленный хвост
}

List purgeList(List tail)
{
    while (tail != nullptr) tail = deleteFromHead(tail); // пока список не пустой, удаляем с головы

    return nullptr;
}

List firstSecondSwap(List tail)
{
    // тут 3 частных случая, вынес их в отдельные ифы
    if (tail == nullptr)  // список пустой, нечего удалять
    {
        drawList(tail);
        return nullptr;
    }

    if (tail->next == tail)// список из одного элемента, второго не существует
    {
        cout << "\nSecond element doesn't exist\n";
        return tail;
    }

    if (tail->next->next == tail) // Список из двух элементов, просто делаем сдвиг
    {
        return tail->next;
    }

    // сохраняем первый и второй элементы
    List tmp1 = tail->next; // первый элемент, или же хвост
    List tmp2 = tmp1->next; // второй элемент

    // меняем порядок указателей
    tmp1->next = tmp2->next; // первый указывает на третий
    tmp2->next = tmp1; // второй указывает на первый
    tail->next = tmp2; // хвост указывает на обновлённую голову, тоесть второй элемент

    return tail;
}

List removeFromPosition(List tail,int position)
{
    if (tail == nullptr) // список пустой, удалять нечего
    {
        drawList(tail);
        return nullptr;
    }

    if (position < 0) // позиция меньше нуля, выводим ошибку
    {
        cout << "\nNegative position\n";
        return tail;
    }

    int size = 0;
    List tmp = tail;
    do
    {
        size++;
        tmp = tmp->next;
    } while (tmp != tail); // считаем размер списка

    if (position >= size) // слишком большая позиция
    {
        cout << "\nNo position\n";
        return tail;
    }

    // Индексация как в массивах
    // тип у тебя список из четырех элементов и индексы: 0 1 2 3
    if (position == 0) tail = deleteFromHead(tail); // нулевая позиция, удаляем с головы
    else if (position == size-1) tail = deleteFromTail(tail); // последняя позиция, удаляем с хвоста
    else
    {
        int counter = 0;
        while (counter < position) // нам нужно добраться до элемента, который указывает на нужный нам
        // если нужно удалить,допустим, третий, то мы добираемся до второго и уничтожаем следующий после него
        {
            tmp = tmp->next;
            counter++;
        }
        tmp = deleteFromHead(tmp);
    }

    return tail;
}
void drawList (List tail)
{
    if (tail == nullptr)
    {
        cout << "List has no elements...\n";
        return;
    }

    List tmp = tail->next;

    do
    {
        cout << tmp->data << ' ';
        tmp = tmp->next;
    } while (tmp != tail->next);

    return;
}

void commands()
{
    cout << "1) add number to list tail\n";
    cout << "2) add number to list head\n";
    cout << "3) delete list tail\n";
    cout << "4) delete list head\n";
    cout << "5) show list\n";
    cout << "6) delete list\n";
    cout << "7) remove value from position\n";
    cout << "8) swap first and second\n";
    cout << "9) command list\n";
    cout << "0) exit\n";

    return;
}

int main()
{
    List tail;
    bool init = false;
    commands();

    int command;
    do
    {
        cout << "Write your command: ";
        cin >> command;
        if (!init && command != 10)
        {
            cout << "СПИСОК НЕ ИНИЦИАЛИЗИРОВАН\n";
            continue;
        }
        switch (command)
        {
            int tmp;


            case 1:
                cout << "Enter your number: ";
                cin >> tmp;

                tail = addToTail(tail,tmp);
                break;
            case 2:
                cout << "Enter your number: ";
                cin >> tmp;

                tail = addToHead(tail,tmp);
                break;

            case 3:
                tail = deleteFromTail(tail);
                break;
            case 4:
                tail = deleteFromHead(tail);
                break;

            case 5:
                cout << "\n" << "List: ";
                drawList(tail);
                break;

            case 6:
                tail = purgeList(tail);
                break;

            case 7:
                int position;
                cout << "Enter your position: ";
                cin >> position;

                tail = removeFromPosition(tail,position);
                break;

            case 8:
                tail = firstSecondSwap(tail);
                break;

            case 9:
                commands();
                break;
            case 10:
                tail = initEmptyList();
                init = true;
                break;
            default:
                break;
        }
    } while (command != 0);

    tail = purgeList(tail);
}