#include <iostream>
#include <cmath>
#include <stdexcept>
using namespace std;

template<typename Tip>
struct Cvor {
    Tip element;
    Cvor *prethodni;
    Cvor *veza;
    Cvor() = default;
    Cvor(Tip element, Cvor *p, Cvor *q)
    {
        this->element=element;
        prethodni=p;
        veza=q;
    }
};

template<typename Tip>
class Iterator;

template<typename Tip>
class Lista
{
public:
    Lista() {};
    virtual int brojElemenata() const=0;
    virtual Tip &trenutni() = 0;
    virtual Tip trenutni() const = 0;
    virtual bool prethodni() = 0;
    virtual bool sljedeci() = 0;
    virtual void pocetak() = 0;
    virtual void kraj() = 0;
    virtual void obrisi() = 0;
    virtual void dodajIspred(const Tip &el) = 0;
    virtual void dodajIza(const Tip &el) = 0;
    virtual Tip &operator [](int i) = 0;
    virtual Tip operator[](int i) const = 0;
    virtual ~Lista() {}
};

template<typename Tip>
class DvostrukaLista:public Lista<Tip>
{
    Cvor<Tip> *pocetni;
    Cvor<Tip> *krajnji;
    Cvor<Tip> *tekuci;
    int brojelemenata;
    int pozicijaTekuceg;

    void Dealociraj()
    {
        tekuci=nullptr;
        while(pocetni!=krajnji) {
            Cvor<Tip> *p=pocetni;
            pocetni=pocetni->veza;
            delete p;
            p=nullptr;
        }
        delete krajnji;
        krajnji=nullptr;
    }
public:
    DvostrukaLista()
    {
        pocetni=nullptr;
        krajnji=nullptr;
        tekuci=nullptr;
        brojelemenata=0;
        pozicijaTekuceg=0;
    }
    DvostrukaLista(const DvostrukaLista<Tip> &lista)
    {
        brojelemenata=lista.brojElemenata();
        pozicijaTekuceg=lista.pozicijaTekuceg;
        Cvor<Tip> *p=lista.pocetni;
        pocetni = new Cvor<Tip>(p->element, nullptr, nullptr);
        Cvor<Tip> *poc=pocetni;
        krajnji=poc;
        tekuci=poc;
        p=p->veza;
        while(p!=nullptr) {
            poc->veza=new Cvor<Tip>(p->element, poc, nullptr);
            poc=poc->veza;
            krajnji=poc;
            if(p==lista.tekuci) tekuci=poc;
            p=p->veza;
        }
    }
    int brojElemenata() const
    {
        return brojelemenata;
    }
    Tip &trenutni()
    {
        if(brojelemenata==0) throw std::domain_error("Prazna lista");
        return tekuci->element;
    }
    Tip trenutni() const
    {
        if(brojelemenata==0) throw std::domain_error("Prazna lista");
        return tekuci->element;
    }
    bool prethodni()
    {
        if(brojelemenata==0) throw std::domain_error("Prazna lista");
        if(tekuci==pocetni) return false;
        tekuci=tekuci->prethodni;
        pozicijaTekuceg--;
        return true;
    }
    bool sljedeci()
    {
        if(brojelemenata==0) throw std::domain_error("Prazna lista");
        if(tekuci==krajnji) return false;
        tekuci=tekuci->veza;
        pozicijaTekuceg++;
        return true;
    }
    void pocetak()
    {
        tekuci=pocetni;
        pozicijaTekuceg=0;
    }
    void kraj()
    {
        tekuci=krajnji;
        pozicijaTekuceg=brojelemenata-1;
    }
    void dodajIza(const Tip &el)
    {
        Cvor<Tip> *p = new Cvor<Tip>();
        p->element = el;
        if(brojelemenata == 0) {
            p->prethodni = nullptr;
            p->veza = nullptr;
            tekuci=p;
            pocetni=p;
            krajnji=p;
            brojelemenata=1;
            pozicijaTekuceg=0;
        } else {
            p->prethodni=tekuci;
            p->veza=tekuci->veza;
            tekuci->veza=p;
            if(p->veza == nullptr) krajnji=p;
            else p->veza->prethodni=p;
            brojelemenata++;
        }
    }
    void dodajIspred(const Tip &el)
    {
        Cvor<Tip> *p= new Cvor<Tip>();
        p->element=el;
        if(brojelemenata==0) {
            p->prethodni=nullptr;
            p->veza=nullptr;
            tekuci=p;
            pocetni=p;
            krajnji=p;
            brojelemenata=1;
            pozicijaTekuceg=0;
        } else {
            p->prethodni=tekuci->prethodni;
            p->veza = tekuci;
            tekuci->prethodni = p;
            if(p->prethodni == nullptr) pocetni=p;
            else p->prethodni->veza=p;
            brojelemenata++;
            pozicijaTekuceg++;
        }
    }
    void obrisi()
    {
        if(pocetni==krajnji) {
            delete pocetni;
            pocetni=nullptr;
            tekuci=nullptr;
            krajnji=nullptr;
            pozicijaTekuceg=0;
        } else if(tekuci==krajnji) {
            tekuci=tekuci->prethodni;
            tekuci->veza=nullptr;
            delete krajnji;
            krajnji=tekuci;
            tekuci->veza=nullptr;
            pozicijaTekuceg--;
        } else if(tekuci==pocetni) {
            tekuci=tekuci->veza;
            tekuci->prethodni=nullptr;
            delete pocetni;
            pocetni=tekuci;
            tekuci->prethodni=nullptr;
            pozicijaTekuceg=0;
        } else {
            Cvor<Tip> *p= tekuci->veza;
            tekuci->prethodni->veza=p;
            p->prethodni=tekuci->prethodni;
            delete tekuci;
            tekuci=p;
        }
        brojelemenata--;
    }
    Tip operator [] (int i) const
    {
        int razlika1, razlika2, razlika3;
        razlika1=i;
        razlika2=brojelemenata-1-i;
        razlika3=abs(pozicijaTekuceg-i);
        if(razlika1<=razlika2 && razlika1<=razlika3) {
            Cvor<Tip> *p=pocetni;
            for(int j=0; j<i; j++) p=p->veza;
            return p->element;
        } else if(razlika3<razlika1 && razlika3<razlika2) {
            int razlika = pozicijaTekuceg-i;
            if(razlika>=0) {
                Cvor<Tip> *p=tekuci;
                for(int j=0; j<razlika3; j++) p=p->veza;
                return p->element;
            } else if(razlika<0) {
                Cvor<Tip> *p=tekuci;
                for(int j=0; j<razlika2; j++) p = p->prethodni;
                return p->element;
            }
        } else {
            Cvor<Tip> *p=krajnji;
            for(int j=0; j<abs(razlika2); j++) p=p->prethodni;
            return p->element;
        }
    }

    Tip &operator [](int i)
    {
        int razlika1, razlika2, razlika3;
        razlika1=i;
        razlika2=abs(brojelemenata-1-i);
        razlika3=abs(pozicijaTekuceg-i);
        if(razlika1<=razlika2 && razlika1<=razlika3) {
            Cvor<Tip> *p=pocetni;
            for(int j=0; j<i; j++) p=p->veza;
            return p->element;
        } else if(razlika3<razlika1 && razlika3<razlika2) {
            int razlika=pozicijaTekuceg-i;
            if(razlika>=0) {
                Cvor<Tip> *p=tekuci;
                for(int j=0; j<razlika3; j++) p= p->veza;
                return p->element;
            } else if(razlika<0) {
                Cvor<Tip> *p=tekuci;
                for(int j=0; j<razlika2; j++) p=p->prethodni;
                return p->element;
            }
        } else {
            Cvor<Tip> *p=krajnji;
            for(int j=0; j<abs(razlika2); j++) p=p->prethodni;
            return p->element;
        }

    }
    ~DvostrukaLista()
    {
        Dealociraj();
    }
    DvostrukaLista &operator= (const DvostrukaLista<Tip> &lista)
    {
        if(this!=&lista) {
            Dealociraj();
            brojelemenata=lista.brojelemenata;
            pozicijaTekuceg=lista.pozicijaTekuceg;
            Cvor<Tip> *p=lista.pocetni;
            pocetni=new Cvor<Tip>(p->element, nullptr, nullptr);
            Cvor<Tip> *poc=pocetni;
            krajnji=poc;
            tekuci=poc;
            p=p->veza;
            while(p!=nullptr) {
                poc->veza=new Cvor<Tip>(p->element, poc, nullptr);
                poc=poc->veza;
                krajnji=poc;
                if(p==lista.tekuci) tekuci=poc;
                p=p->veza;
            }
        }
        return *this;
    }
    friend class Iterator<Tip>;
};

template<typename Tip>
class Iterator
{
    const DvostrukaLista<Tip> *lista;
    Cvor<Tip> *trenutniLista;
public:
    Iterator(const DvostrukaLista<Tip> &l)
    {
        lista=&l;
        trenutniLista=l.pocetni;
    }
    Tip trenutni()
    {
        return trenutniLista->element;
    }
    bool prethodni()
    {
        if(lista->brojelemenata==0) throw std::domain_error("Prazna lista");
        if(lista->tekuci==lista->pocetni) return false;
        trenutniLista=trenutniLista->prethodni;
        return true;
    }
    bool sljedeci()
    {
        if(lista->brojElemenata()==0) throw std::domain_error("Prazna lista");
        if(lista->tekuci == lista->pocetni) return false;
        trenutniLista=trenutniLista->veza;
        return true;
    }
    void pocetak()
    {
        trenutniLista=lista->pocetni;
    }
    void kraj()
    {
        trenutniLista=lista->krajnji;
    }
};

template<typename Tip>
Tip dajMaksimum(const Lista<Tip> &n)
{
    const DvostrukaLista<Tip> *l=(DvostrukaLista<Tip>*)(&n);
    Iterator<Tip> iter(*l);
    iter.pocetak();
    Tip max = iter.trenutni();
    for(int **0; i<n.brojElemenata(); i++) {
        if(iter.trenutni()>max) max=iter.trenutni();
        iter.sljedeci();
    }
    return max;
}

template <typename Tip>
bool testbrojElemanata(const DvostrukaLista<Tip> &lista, int velicina_liste)
{
    if(velicina_liste==lista.brojElemenata()) return true;
    return false;
}

template <typename Tip>
bool testtrenutni(const DvostrukaLista<Tip> &lista, Tip element)
{
    if(element==lista.trenutni()) return true;
    return false;
}

template<typename Tip>
bool testprethodni(DvostrukaLista<Tip> &lista, Tip prethodni)
{
    lista.prethodni();
    if(prethodni==lista.trenutni()) return true;
    return false;
}

template<typename Tip>
bool testsljedeci(DvostrukaLista<Tip> &lista, Tip sljedeci)
{
    lista.sljedeci();
    if(sljedeci==lista.trenutni()) return true;
    return false;
}

template<typename Tip>
bool testpocetak(DvostrukaLista<Tip> &lista, Tip pocetak)
{
    lista.pocetak();
    if(pocetak==lista.trenutni()) return true;
    return false;
}

template<typename Tip>
bool testkraj(DvostrukaLista<Tip> &lista, Tip kraj)
{
    lista.kraj();
    if(kraj==lista.trenutni()) return true;
    return false;
}

template<typename Tip>
bool testOperatorZagrade(const DvostrukaLista<Tip> &lista, int i, Tip element)
{
    if(lista[i]==element) return true;
    return false;
}

template<typename Tip>
bool testOperatorJednako(const DvostrukaLista<Tip> &lista)
{
    DvostrukaLista<Tip> nova;
    nova=lista;
    if(lista.brojElemenata()!=nova.brojElemenata())return false;
    for(int **0; i<lista.brojElemenata(); i++) {
        if(lista[i]!=nova[i]) return false;
    }
    if(lista.trenutni() != nova.trenutni()) return false;
    return true;
}

template<typename Tip>
bool testObrisi(DvostrukaLista<Tip> &lista, int brojelemenata, Tip tekuci)
{
    lista.obrisi();
    if(lista.brojElemenata()!=brojelemenata) return false;
    if(lista.trenutni()!=tekuci) return false;
    return true;
}


int main()
{
    DvostrukaLista<int> lista;
    for(int **0; i<7; i++) lista.dodajIza(i);
    if(testbrojElemanata(lista, 7)) std::cout << "Test funkcije brojElemenata: Uspjesan" << std::endl;
    else std::cout << "Test funkcije brojElemenata: Neuspjesan" << std::endl;
    if(testtrenutni(lista, 0)) std::cout << "Test funkcije trenutni: Uspjesan" << std::endl;
    else std::cout << "Test funkcije trenutni: Neuspjesan" << std::endl;
    if(testsljedeci(lista, 6)) std::cout << "Test funkcije sljedeci: Uspjesan" << std::endl;
    else std::cout << "Test funkcije sljedeci: Neuspjesan" << std::endl;
    if(testprethodni(lista, 0)) std::cout << "Test funkcije prethodni: Uspjesan" << std::endl;
    else std::cout << "Test funkcije prethodni: Neuspjesan" << std::endl;
    if(testpocetak(lista, 0)) std::cout << "Test funkcije pocetak: Uspjesan" << std::endl;
    else std::cout << "Test funkcije pocetak: Neuspjesan" << std::endl;
    if(testkraj(lista, 1)) std::cout << "Test funkcije kraj: Uspjesan" << std::endl;
    else std::cout << "Test funkcije kraj: Neuspjesan" << std::endl;
    if(testOperatorZagrade(lista, 3, 4)) std::cout << "Test funkcije operator []: Uspjesan" << std::endl;
    else std::cout << "Test funkcije operator []: Neuspjesa" << std::endl;
    if(testOperatorJednako(lista)) std::cout << "Test funkcije operator =: Uspjesan" << std::endl;
    else std::cout << "Test funkcije operator =: Neuspjesan" << std::endl;
    if(testObrisi(lista, 6, 2)) std::cout << "Test funkcije obrisi: Uspjesan" << std::endl;
    else std::cout << "Test funkcije obrisi: Neuspjesan" << std::endl;
    DvostrukaLista<int> nova(lista);
    nova.dodajIspred(16);
    nova.dodajIspred(22);
    if(nova[5]==16 && nova[6]==22) std::cout << "Test funkcije dodajIspred: Uspjesan" << std::endl;
    else std::cout << "Test funkcije doadjIspred: Neuspjesan" << std::endl;
    return 0;
}