#include <iostream>
#include <stdexcept>
#include <utility>

using namespace std;

template <typename T>
class Dek {
    T **niz;
    int i1, i2, kapacitet;

    void InicijalizirajPrazan();
    void Realociraj();
    void OslobodiMemoriju();
    void Zamijeni(Dek &drugi) noexcept;

public:
    Dek() {
        InicijalizirajPrazan();
    }

    template <typename Iterator>
    Dek(Iterator pocetak, Iterator iza_kraja) : Dek() {
        try {
            while (pocetak != iza_kraja) {
                DodajNaKraj(*pocetak);
                ++pocetak;
            }
        } catch (...) {
            OslobodiMemoriju();
            throw;
        }
    }

    Dek(const Dek &drugi);
    Dek(Dek &&drugi) noexcept;

    Dek &operator=(const Dek &drugi);
    Dek &operator=(Dek &&drugi) noexcept;

    ~Dek() {
        OslobodiMemoriju();
    }

    void DodajNaKraj(const T &element);
    void DodajNaPocetak(const T &element);

    int DajVelicinu() const {
        return i2 - i1;
    }

    T &operator[](int indeks);
    const T &operator[](int indeks) const;
};

template <typename T>
void Dek<T>::InicijalizirajPrazan() {
    kapacitet = 10;
    i1 = i2 = 5;
    niz = new T *[kapacitet]{};
}

template <typename T>
void Dek<T>::Realociraj() {
    if (kapacitet == 0) {
        delete[] niz;
        InicijalizirajPrazan();
        return;
    }

    int velicina = i2 - i1;
    int novi_kapacitet = kapacitet + kapacitet / 2;

    if (novi_kapacitet <= kapacitet)
        novi_kapacitet = kapacitet + 1;

    T **novi_niz = new T *[novi_kapacitet]{};

    int slobodno = novi_kapacitet - velicina;
    int novi_i1 = slobodno / 3;
    int novi_i2 = novi_i1 + velicina;

    for (int i = 0; i < velicina; i++)
        novi_niz[novi_i1 + i] = niz[i1 + i];

    delete[] niz;

    niz = novi_niz;
    kapacitet = novi_kapacitet;
    i1 = novi_i1;
    i2 = novi_i2;
}

template <typename T>
void Dek<T>::OslobodiMemoriju() {
    if (niz != nullptr) {
        for (int i = i1; i < i2; i++)
            delete niz[i];

        delete[] niz;
    }

    niz = nullptr;
    i1 = i2 = 0;
    kapacitet = 0;
}

template <typename T>
void Dek<T>::Zamijeni(Dek &drugi) noexcept {
    swap(niz, drugi.niz);
    swap(kapacitet, drugi.kapacitet);
    swap(i1, drugi.i1);
    swap(i2, drugi.i2);
}

template <typename T>
Dek<T>::Dek(const Dek &drugi)
    : niz(drugi.kapacitet == 0
              ? nullptr
              : new T *[drugi.kapacitet]{}),
      i1(drugi.i1),
      i2(drugi.i2),
      kapacitet(drugi.kapacitet) {

    int i = i1;

    try {
        for (; i < i2; i++)
            niz[i] = new T(*drugi.niz[i]);
    } catch (...) {
        for (int j = i1; j < i; j++)
            delete niz[j];

        delete[] niz;
        throw;
    }
}

template <typename T>
Dek<T>::Dek(Dek &&drugi) noexcept
    : niz(drugi.niz),
      i1(drugi.i1),
      i2(drugi.i2),
      kapacitet(drugi.kapacitet) {

    drugi.niz = nullptr;
    drugi.i1 = 0;
    drugi.i2 = 0;
    drugi.kapacitet = 0;
}

template <typename T>
Dek<T> &Dek<T>::operator=(const Dek &drugi) {
    if (this != &drugi) {
        Dek kopija(drugi);
        Zamijeni(kopija);
    }

    return *this;
}

template <typename T>
Dek<T> &Dek<T>::operator=(Dek &&drugi) noexcept {
    if (this != &drugi) {
        OslobodiMemoriju();

        niz = drugi.niz;
        kapacitet = drugi.kapacitet;
        i1 = drugi.i1;
        i2 = drugi.i2;

        drugi.niz = nullptr;
        drugi.i1 = 0;
        drugi.i2 = 0;
        drugi.kapacitet = 0;
    }

    return *this;
}

template <typename T>
void Dek<T>::DodajNaKraj(const T &element) {
    if (i2 == kapacitet)
        Realociraj();

    niz[i2] = new T(element);
    i2++;
}

template <typename T>
void Dek<T>::DodajNaPocetak(const T &element) {
    if (i1 == 0)
        Realociraj();

    T *novi_element = new T(element);

    i1--;
    niz[i1] = novi_element;
}

template <typename T>
T &Dek<T>::operator[](int indeks) {
    if (indeks < 0 || indeks >= DajVelicinu())
        throw range_error("Neispravan indeks");

    return *niz[i1 + indeks];
}

template <typename T>
const T &Dek<T>::operator[](int indeks) const {
    if (indeks < 0 || indeks >= DajVelicinu())
        throw range_error("Neispravan indeks");

    return *niz[i1 + indeks];
}

int main() {
    Dek<int> d;

    d.DodajNaKraj(20);
    d.DodajNaPocetak(10);
    d.DodajNaKraj(30);

    for (int i = 0; i < d.DajVelicinu(); i++)
        cout << d[i] << " ";

    return 0;
}