#include <string>
#include <iostream>

using namespace std;


template <typename TElement>
class Sequence {                // <--- КЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ
protected:
    int length;
    bool isEmpty;
public:
    Sequence();
    ~Sequence();
    int getLength ();
    bool getIsEmpty ();
    virtual TElement Get (int index) = 0;
    virtual TElement GetFirst() = 0;
    virtual TElement GetLast () = 0;
    // virtual Sequence<TElement> GetSubsequence (int startIndex, int endIndex) = 0;
    virtual void Append (TElement item) = 0;
    virtual void Prepend (TElement item) = 0;
    virtual void InsertAt (int index, TElement item) = 0;
    virtual void Remove (TElement item) = 0;

};
template <typename TElement>
Sequence<TElement>::Sequence() {
    length = 0;
    isEmpty = true;
}

template <typename TElement>
Sequence<TElement>::~Sequence() {

}
template <typename TElement>
int Sequence<TElement>::getLength() {
    return length;
}
template <typename TElement>
bool Sequence<TElement>::getIsEmpty() {
    return isEmpty;
}


template <typename TElement>
class ArraySequence : public Sequence<TElement> {   // <--- ПОДКЛАСС ПОСЛЕДОВАТЕЛЬНОСТЬ С МАССИВАМИ
private:
    TElement *Array;
public:
    ArraySequence();
    ~ArraySequence();
    TElement Get (int index);
    TElement GetFirst();
    TElement GetLast ();
    ArraySequence<TElement> GetSubsequence (int startIndex, int endIndex);
    void Append (TElement item);
    void Prepend (TElement item);
    void InsertAt (int index, TElement item);
    void Remove (TElement item);

    //
    void qwe(TElement *array);
    void print_all ();
};

class ExceptionOutOfBounds : public exception {     // <--- КЛАСС ИСКЛЮЧЕНИЙ выход за границу массива
    int wrongIndex;
public:
    ExceptionOutOfBounds(int index);
    void what() {
        cout << "Индекс " << wrongIndex << " oшибка: выход за границы массива " << endl;
    }
};
ExceptionOutOfBounds:: ExceptionOutOfBounds(int index) {
    wrongIndex = index;
}

template <typename TElement>
ArraySequence<TElement>::ArraySequence() {
    Array = new TElement;
}

template <typename TElement>
ArraySequence<TElement>::~ArraySequence() {
    delete Array;
}

template <typename TElement>
TElement ArraySequence<TElement>:: Get (int index) {
    if (index < 0 || index >= this->length) {
        throw ExceptionOutOfBounds(index);
    }
    return Array[index];

}


template <typename TElement>
TElement ArraySequence<TElement>:: GetFirst () {
    return Array[0];
}

template <typename TElement>
TElement ArraySequence<TElement>:: GetLast() {
    return Array [this->length - 1];
}
template <typename TElement>    // удалить потом
void ArraySequence<TElement>:: qwe(TElement *array) {
    Array = array;
}

template <typename TElement>
void ArraySequence<TElement>:: Append(TElement item) {  // Append. вставить в конец
    if (this->length == 0) {
        this->length ++;
        this->isEmpty = false;
        Array [0] = item;
    }
    else {
        this->length ++;
        TElement *newArray = new TElement [this->length];
        for (int i = 0; i < this->length - 1; i++) {
            newArray[i] = Array [i];
        }
        newArray[this->length - 1] = item;
        Array = newArray;
    }
}

template <typename TElement>
void ArraySequence<TElement>:: Prepend(TElement item) {  // Prepend. вставить в начало
    if (this->length == 0) {
        this->length ++;
        this->isEmpty = false;
        Array [0] = item;
    }
    else {
        this->length ++;
        TElement *newArray = new TElement [this->length];
        for (int i = 1; i < this->length; i++) {
            newArray[i] = Array [i-1];
        }
        newArray[0] = item;
        Array = newArray;
    }
}

template <typename TElement>
void ArraySequence<TElement>:: InsertAt(int index, TElement item) {
    if (index < 0 || index >= this->length) {
        throw ExceptionOutOfBounds(index);
    }
    if (index == 0) {
        this->Prepend(item);
    }
    if (index == this->length) this->Append(item);  // или вообще запретить это?
    else {
        this->length ++;
        TElement *newArray = new TElement [this->length];
        for (int i = 0; i < index; i ++) {
            newArray[i] = Array[i];
        }
        newArray[index] = item;
        for (int i = index + 1; i < this->length; i++) {
            newArray [i] = Array [i-1];
        }
        Array = newArray;
    }
}


template <typename TElement>
void ArraySequence<TElement>:: Remove(TElement item) {
    for (int i = 0; i < this->length; i ++) {
        //cout << Array[i] << " ";
        if (Array[i] == item) {
            this->length --;
            TElement *newArray = new TElement [this->length];
            for (int j = 0; j < i; j ++) {
                newArray[j] = Array [j];
            }
            for (int k = i; k < this->length; k ++) {
                newArray[k] = Array[k+1];
            }
            Array = newArray;
            i --;
        }
    }
}

template <typename TElement>
ArraySequence<TElement> ArraySequence<TElement>:: GetSubsequence(int startIndex, int endIndex) {
    if (startIndex < 0 || startIndex >= this->length) {
        throw ExceptionOutOfBounds(startIndex);
    }
    if (endIndex < 0 || endIndex >= this->length) {
        throw ExceptionOutOfBounds(endIndex);
    }
    ArraySequence<TElement> Subsequence;
    for (int i = startIndex; i <= endIndex; i ++) {
        Subsequence.Append(Array[i]);
    }
    return Subsequence;
}


template <typename TElement>
void ArraySequence<TElement>:: print_all() {
    for (int i = 0; i < this->length; i ++) {
        cout << Array[i] << endl;
    }
}

void TestArraySequence() {
    cout << "--- НАЧАЛО ТЕСТИРОВАНИЯ ---" << endl;
    ArraySequence<int> testArray;

    if (testArray.getLength() == 0) cout << "1 - OK" << endl;
    else cout << "1 - Mistake" << endl;

    testArray.Append(23);

    if (testArray.getLength() == 1) cout << "2 - OK" << endl;
    else cout << "2 - Mistake" << endl;

    if (testArray.GetFirst() == 23) cout << "3 - OK" << endl;
    else cout << "3 - Mistake" << endl;

    if (testArray.GetLast() == 23) cout << "4 - OK" << endl;
    else cout << "4 - Mistake" << endl;

    try {
        if (testArray.Get(0) == 23) cout << "5 - OK" << endl;
        else cout << "5 - Mistake" << endl;
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    try {
        cout << testArray.Get(-1) << endl;
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    try {
        testArray.Get(1);
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    testArray.Append(43);

    if (testArray.getLength() == 2) cout << "6 - OK" << endl;
    else cout << "6 - Mistake" << endl;

    if (testArray.GetFirst() == 23) cout << "7 - OK" << endl;
    else cout << "7 - Mistake" << endl;

    if (testArray.GetLast() == 43) cout << "8 - OK" << endl;
    else cout << "8 - Mistake" << endl;

    try {
        if (testArray.Get(0) == 23) cout << "9 - OK" << endl;
        else cout << "9 - Mistake" << endl;
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    try {
        if (testArray.Get(1) == 43) cout << "10 - OK" << endl;
        else cout << "10 - Mistake" << endl;
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    try {
        testArray.Get(-1);
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    try {
        testArray.Get(2);
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    testArray.Prepend(53);

    if (testArray.getLength() == 3) cout << "11 - OK" << endl;
    else cout << "11 - Mistake" << endl;

    if (testArray.GetFirst() == 53) cout << "12 - OK" << endl;
    else cout << "12 - Mistake" << endl;

    if (testArray.GetLast() == 43) cout << "13 - OK" << endl;
    else cout << "13 - Mistake" << endl;

    try {
        if (testArray.Get(0) == 53) cout << "14 - OK" << endl;
        else cout << "14 - Mistake" << endl;
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    try {
        if (testArray.Get(1) == 23) cout << "15 - OK" << endl;
        else cout << "15 - Mistake" << endl;
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    try {
        testArray.Get(-1);
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    try {
        testArray.Get(3);
    }
    catch (ExceptionOutOfBounds ex){
        ex.what();
    }

    ArraySequence<int> testSubseq = testArray.GetSubsequence(1, 1);

    if (testSubseq.getLength() == 1) cout << "16 - OK" << endl;
    else cout << "16 - Mistake" << endl;

    if (testSubseq.GetFirst() == 23) cout << "17 - OK" << endl;
    else cout << "17 - Mistake" << endl;

    if (testSubseq.GetLast() == 23) cout << "18 - OK" << endl;
    else cout << "18 - Mistake" << endl;

    cout << "--- КОНЕЦ ТЕСТИРОВАНИЯ ---" << endl;

}