template <typename TElement>
struct Node {
    TElement field;
    Node *next;
    Node *prev;
};

template <typename TElement>
class ListSequence: public Sequence <TElement> { // <--- ПОДКЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ С двусвязным СПИСКОМ
    Node<TElement> *First, *Last;
public:
    ListSequence();
    ~ListSequence();
    void Append(TElement item);
    void Prepend(TElement item);
    TElement GetFirst();
    TElement GetLast();
    void InsertAt(int index, TElement item);
    TElement Get(int index);
    void Remove(TElement item);
    ListSequence<TElement> GetSubsequence(int startIndex, int endIndex);
    void PrintAll ();
};

template <typename TElement>
ListSequence<TElement>:: ListSequence() : Sequence<TElement>() {
    First = NULL;
    Last = NULL;
}

template <typename TElement>
ListSequence<TElement>:: ~ListSequence(){
    while (First) {
        Last = First->next;
        delete First;
        First = Last;
    }
}

template <typename TElement>
TElement ListSequence<TElement>:: GetFirst() {
    if(First == NULL) {
        throw ExceptionOutOfBounds(0);
    }
    return First->field;
}

template <typename TElement>
TElement ListSequence<TElement>:: GetLast() {
    if (Last == NULL) {
        throw ExceptionOutOfBounds(0);
    }
    return Last->field;
}

template <typename TElement>
void ListSequence<TElement>:: Append(TElement item) {
    Node<TElement> *temp = new Node<TElement>;
    temp->next = NULL;
    temp->field = item;
    if(this->length != 0){
        temp->prev = Last;
        Last->next = temp;
        Last = temp;
        this->length++;
    }
    else {
        temp->prev = NULL;
        First = temp;
        Last = temp;
        this->length++;
        this->isEmpty = false;
    }
}

template <typename TElement>
void ListSequence<TElement>:: Prepend(TElement item) {
    Node<TElement> *temp = new Node<TElement>;
    temp->prev = NULL;
    temp->field = item;
    if(this->length != 0) {
        temp->next=First;
        First->prev=temp;
        First=temp;
        this->length++;
    }
    else {
        temp->next=NULL;
        First=temp;
        Last=temp;
        this->length++;
        this->isEmpty = false;
    }
}

template <typename TElement>
void ListSequence<TElement>:: InsertAt(int index, TElement item) {
    if(index < 0 || index > this->length) {
        throw ExceptionOutOfBounds(index);
    }
    if(this->isEmpty == true) this->isEmpty = false;
    if(index == 0) Prepend(item);
    else if(index == this->length - 1) Append(item);
    else {
        this->length++;
        Node<TElement> *temp=new Node<TElement>;
        temp->field = item;
        temp->next = First->next;
        temp->prev = First;
        while(index-2) {
            temp->prev = temp->prev->next;
            temp->next = temp->next->next;
            index --;
        }
        temp->prev->next = temp;
        temp->next->prev = temp;
    }
}

template <typename TElement>
TElement ListSequence<TElement>:: Get(int index) {
    if (index < 0 || index > this->length - 1) {
        throw ExceptionOutOfBounds(index);
    }
    if(index == 0) return GetFirst();
    if(index == this->length - 1) return GetLast();
    else {
        Node<TElement> *temp = new Node<TElement>;
        temp->next = First->next;
        while(index - 1) {
            temp->next = temp->next->next;
            index --;
        }
        return temp->next->field;
    }
}

template <typename TElement>
void ListSequence<TElement>:: Remove(TElement item) {
    int k = 0;
    while(k < this->length - 1) {
        Node<TElement> *temp = new Node<TElement>;
        int index = k;
        temp->next = First;
        while(temp->next->field != item && index < this->length - 1) {
            temp->next = temp->next->next;
            index ++;
            k ++;
        }
        if(temp->next->field == item) {
            temp = temp->next;
            if(temp->prev != 0) temp->prev->next = temp->next;
            else First = temp->next;
            if(temp->next != 0) temp->next->prev = temp->prev;
            else Last = temp->prev;
            if (this->length == 0) this->isEmpty = false;
            this->length--;
            delete temp;
        }
    }
}

template <typename TElement>
ListSequence<TElement> ListSequence<TElement>:: GetSubsequence(int startIndex, int endIndex) {
    if (startIndex < 0 || startIndex > this->length + 1) {
        throw ExceptionOutOfBounds(startIndex);
    }
    if (endIndex < 0 || endIndex >= this->length + 1) {
        throw ExceptionOutOfBounds(endIndex);
    }
    if (endIndex - startIndex < 0) {
        throw ExceptionOutOfBounds(endIndex - startIndex);
    }
    ListSequence<TElement> Subsequence;
    Node<TElement> *temp = new Node<TElement>;
    temp = First;
    for (int i = 0; i < startIndex; i ++) temp = temp->next;
    for (int i = startIndex - 1; i < endIndex; i++) {
        Subsequence.Append(temp->field);
        temp = temp->next;
    }
    return Subsequence;
}

template <typename TElement>
void ListSequence<TElement>:: PrintAll() {
    Node<TElement> *temp = new Node<TElement>;
    temp = First;
    cout << "Последовательность: " ;
    while (temp) {
        cout << temp->field << " ";
        temp = temp->next;
    }
    cout << endl;
}