//DoubleList.h
#pragma once
#ifndef DOUBLELIST_H
#define DOUBLELIST_H
#include <iostream>
using namespace std;

// структура узел
template<typename TYPE> struct Node
{
    TYPE x;     // информационное поле узла
    Node* next; // указатели на структуру
    Node* prev; // указатели на структуру
};

// класс двунаправленный список
template<typename TYPE> class DoubleList
{
private:
    Node<TYPE>* head; // указатель на начало списка
    Node<TYPE>* tail; // указатели на конец списка
public:
    //конструктор/деструктор
    DoubleList();         // конструктор
    ~DoubleList();        // деструктор

    //методы
    void addTail(TYPE y); // добавление элемента в конец списка
    void addHead(TYPE y); // добавление элемента в начало списка
    void showFromBegin(ofstream& dout); // вывод списка с начала
    void showFromEnd(ofstream& dout);   // вывод списка с конца
    void getHead();       // вывод головы
    void getTail();       // вывод хвоста
    void delNum(int n);   // удаление элемента по номеру
    int size();           // размер списка
    int findNum(int n);   // вернуть элемент, расположенный на n месте сверху
};

//конструктор
template <typename TYPE> DoubleList<TYPE>::DoubleList()
    : head(NULL), tail(NULL) {}
//деструктор
template<typename TYPE> DoubleList<TYPE>::~DoubleList()
{
    while (head != NULL) {            // пока список не пуст
        tail = head->next;            // последний элемент равен следующему за головой
        delete head;                  // удаление головы
        head = tail;                  // первым становится последний
    }
}
//добавление элемента в конец списка
template<typename TYPE> void DoubleList<TYPE>::addTail(TYPE y)
{
    Node<TYPE>* temp = new Node<TYPE>;      // выделение памяти для нового элемента
    temp->next = NULL;                // за этим элементом нет других
    temp->x = y;
    if (head != NULL) {               // пока список не пуст
        temp->prev = tail;            // следующий за temp элемент будет хвостом
        tail->next = temp;            // элемент следующий за хвостом temp
        tail = temp;                  // temp равен хвосту
    }
    else {
        temp->prev = NULL;            // перед элементом пусто
        head = tail = temp;           // голова равна хвосту и равна temp
    }
}
//добавление элемента в начало списка
template<typename TYPE> void DoubleList<TYPE>::addHead(TYPE y)
{
    Node<TYPE>* temp = new Node<TYPE>;
    temp->x = y;
    if (temp != NULL) {
        temp->next = head;
        head = temp;
    }
    else {
        head = tail = temp;
    }
}
//вывод списка с начала
template<typename TYPE> void DoubleList<TYPE>::showFromBegin(ofstream& dout)
{
    Node<TYPE>* temp = head;          // temp равен началу списка
    while (temp != NULL) {            // пока список не пуст
        dout << temp->x << " " << endl;
        temp = temp->next;            // перемещение на следующий
    }
}
//вывод списка с конца
template<typename TYPE> void DoubleList<TYPE>::showFromEnd(ofstream& dout)
{
    Node<TYPE>* temp = tail;          // temp равен концу  списка
    while (temp != NULL) {            // пока элементы есть
        dout << temp->x << " " << endl;
        temp = temp->prev;            // перемещение на предыдущий
    }
}
//вывод головы
template<typename TYPE> void DoubleList<TYPE>::getHead()
{
    if (head != NULL) {
        cout << head->x << endl;
    }
}
//вывод хвоста
template<typename TYPE> void DoubleList<TYPE>::getTail()
{
    if (tail != NULL) {
        cout << tail->x << endl;
    }
}
//удаление элемента по номеру
template<typename TYPE> void DoubleList<TYPE>::delNum(int n) {
    Node<TYPE>* temp = head;
    if (temp != NULL && n <= size()) {
        for (int i = 0; i < n; i++) {
            temp = temp->next;
        }
        if (temp == head) {
            head = temp->next;
        }
        else {
            temp->prev->next = temp->next;
        }
        delete temp;
    }
}
//размер списка
template<typename TYPE> int DoubleList<TYPE>::size() {
    Node<TYPE>* temp = head;
    int counter = 0;
    while (temp != NULL) {
        temp = temp->next;
        counter++;
    }
    return counter;
}
// вернуть элемент, расположенный на n месте сверху
template<typename TYPE> int DoubleList<TYPE>::findNum(int n) {
    Node<TYPE>* temp = head;
    while (temp != NULL && n <= size()) {
        for (int i = 0; i < n; i++) {
            temp = temp->next;
        }
        return temp->x;
    }
}
#endif