#include <iostream>

using namespace std;

template <typename Tip>
class Iterator;

//Prva verzija klase Niz je bila preko vektora, pa je zbog toga ova klasa izmjenjena u odnosu na onu koju sam poslala kao Pripremu za tutorijal 2
//Također, neke metode u svim klasama su izmjenjene na osnovu gresaka koje sam uvidjela nakon autotestova, vecina gresaka je bila vezana za pristup izvan opsega, pa su mjenjane samo vrijednosti koje vraca niz ili lista
template<typename Tip>
class Niz
{
    int dimenzija;
    Tip* niz;
    int trenutno;//trenutni broj elemenata stavljenih u niz
    int pok; //index elementa na koji trenutno pokazuje

public:
    Niz() :dimenzija(0), trenutno(0), pok(0)
    {

        niz=new Tip[0];
    }

    virtual ~Niz()
    {
        delete[] niz;
        pok=0;
        trenutno=0;
    }

    Niz(const Niz &n)
    {

        dimenzija=n.dimenzija;
        niz=new Tip[n.dimenzija];
        for (int i=0; i<dimenzija; i++)
        {
            niz[i]=n.niz[i];
        }
    }


    Niz &operator=(const Niz &n)
    {
        delete[] niz;
        pok=0;
        trenutno=0;

        dimenzija=n.dimenzija;
        niz=new Tip[n.dimenzija];
        for (int i=0; i<dimenzija; i++)
        {
            niz[i]=n.niz[i];
        }


        return *this;
    }


    virtual int brojElemenata()
    {
        return trenutno;
    }

    virtual Tip trenutni()
    {
        return niz[trenutno-1];
    }

    virtual bool prethodni()
    {
        if (trenutno==0) throw "Nema elemenata u nizu.";
        else if (trenutno==1) return false;
        else
        {
            pok--;
            return true;
        }
    }

    virtual bool sljedeci()
    {
        if (trenutno==0) throw "Nema elemenata u nizu.";
        else if (trenutno==dimenzija) return false;
        else
        {
            pok++;
            return true;

        }

    }

    virtual void pocetak()
    {
        pok=0;
    }

    virtual void kraj()
    {
        pok=dimenzija;
    }

    virtual void dodajIspred( const Tip &element)
    {

        if (trenutno==0)
        {
            niz[0]=element;
            trenutno++;
            pok=0;

        }
        else
        {
            Tip *niz1=new Tip[trenutno+1];
            for (int i=0; i<pok; i++)
            {
                niz1[i]=niz[i];
            }
            niz1[pok]=element;
            for (int j=pok+1; j<trenutno; j++)
            {
                niz1[j]=niz[j];
            }
            niz=niz1;
            pok++;
            trenutno++;
        }
    }


    virtual void dodajIza(const Tip &element)
    {




        if (trenutno==0)
        {
            niz[trenutno-1]=element;
            trenutno++;
            pok=0;
        }

        else
        {

            Tip *niz1=new Tip[trenutno+1];

            for (int i=0; i<=pok; i++)
            {

                niz1[i]=niz[i];

            }
            niz1[pok]=element;

            for (int j=pok+1; j<trenutno; j++)
            {
                niz1[j]=niz[j];
            }
            niz=niz1;
            pok++;
            trenutno++;
        }
    }


    virtual void obrisi()
    {
        if (trenutno==0) throw "Niz je prazan.";

        Tip *niz1=new Tip[trenutno];
        for (int i=0; i<pok; i++)
        {
            niz1[i]=niz[i];
        }
        for (int j=pok+1; j<trenutno; j++)
        {
            niz1[j]=niz[j];
        }

        if (pok==trenutno-1) pok--;
        else pok++;
        trenutno--;
        niz=niz1;


    }


    virtual Tip operator [] (int n) const
    {
        if (n<0) throw "Ne postoji taj clan niza.";
        return niz[n-1];
    }

    friend class Iterator<Tip>;
};



// obzirom da smo dobili neke upute vezane za implementacije pojedinih metoda klase Lista, doslo je do nekih izmjena u metodama, obzirom da je nacin na koji sam implementirala metode za pripremu za tutorijal bio pogresan.
template<typename Tip>
class Lista: public Niz<Tip>
{

    struct Cvor //izmjena naziva struktura iz Clan u Cvor i Clan* veza u Cvor* _sljedeci, zbog prilagodjavanja imena i funkcije koju obavlja Cvor sljedeci, cisto radi lakse orjentacije
    {
        Tip element;
        Cvor *_sljedeci;
    };
    Cvor* p; //pocetni
    Cvor* tr; //trenutni
    Cvor *poslj;// posljednji
    int br; // ukupan broj cvorova


public:
    Lista() :p(0), tr(0), poslj(0), br(0) {} //atributi su bili implementirani unutar zagrada, pa sam ih prebacila u konstruktorsku inicijalizacijsku listu

    ~Lista()
    {

        Cvor *novi(p);
        while (novi->_sljedeci!=0)
        {
            novi=novi->_sljedeci;
            delete p;
            p=novi;
        }
        delete novi;
        p=tr=poslj=0;
    }

    Lista(Lista &a)
    {
        br=a.br;
        p= new Cvor(*p);
        Cvor *temp(a.p);
        Cvor *temp1(p);
        while (temp!=0)
        {
            if (temp==a.tr) tr=temp1;
            temp1->_sljedeci=new Cvor(*temp);
            temp1=temp1->_sljedeci;
            temp=temp->_sljedeci;
        }
    }

    Lista &operator=(Lista &a)
    {
        Cvor *temp=p;
        while (temp->_sljedeci!=0)
        {
            temp=temp->_sljedeci;
            delete p;
            p=temp;
        }
        delete temp;
        p=tr=poslj=0;

        br=a.br;
        p=new Cvor(*p);
        temp=a.p;
        Cvor *temp1(p);
        while (temp!=0)
        {
            if (temp==a.tr) tr=temp1;
            temp1->_sljedeci=new Cvor(temp);
            temp1=temp1->_sljedeci;
            temp=temp->_sljedeci;
        }
        return *this;
    }

    int brojElemenata()
    {
        return br;
    }

    Tip trenutni() const
    {
        if (br==0) throw "Lista  je prazna.";
        return tr->element;
    }

    bool prethodni()
    {
        if (br==0) return false;
        Cvor *novi=p;
        while (novi->_sljedeci!=tr)
        {
            novi=novi->_sljedeci;
        }
        tr=novi;
        return true;
    }


    bool sljedeci()
    {
        if (tr==poslj) return false;
        tr=tr->_sljedeci;
        return true;
    }

    void pocetak()
    {
        tr=p;
    }

    void kraj()
    {

        tr=poslj; //Obzirom da sam naknadno dodala varijablu posljednji, promjenila sam i ovu metodu u odnosu kakvu sam je poslala kao pripremu za tutorijal 2.
    }

    void obrisi()
    {
        if (tr==p)
        {
            p=p->_sljedeci;
            delete tr;

            br--;
            tr=p;

        }
        else
        {
            Cvor *temp=p;
            while (temp->_sljedeci!=tr)
            {
                temp=temp->_sljedeci;
            }
            temp->_sljedeci=tr->_sljedeci;
            delete tr;
            br--;
            tr=temp;


        }
    }


    void dodajIza(const Tip &el)
    {
        Cvor* novi=new Cvor;
        novi->element=el;
        novi->_sljedeci=0;
        if (br==0)
        {
            poslj=tr=novi;
        }
        else
        {
            novi->_sljedeci=tr->_sljedeci;
            tr->_sljedeci=novi;
        }
        br++;
    }

    void dodajIspred(const Tip &el)
    {
        if (br==0)
        {
            p=new Cvor;
            p->element=el;
            p->_sljedeci=0;
            tr=p;
            br++;
            return;
        }

        if (tr==p)
        {
            Cvor* novi=new Cvor;
            novi->_sljedeci=p;
            novi->element=el;
            p=novi;
            br++;
            return;
        }
        prethodni();
        dodajIza(el);
        sljedeci();
        sljedeci();
    }

    Tip &operator [](int n)
    {
        if (n<0 || n>br) throw "Ne postoji taj clan niza.";
        Cvor* temp(p);
        for (int i=0; i<n; i++)
        {
            temp=temp->_sljedeci;
        }
        return temp->element;
    }

    friend class Iterator<Tip>;
};



template <typename Tip>
class Iterator
{
    const Niz<Tip> *niz;
    const Lista<Tip> *lista;
    int trenutniNiz;
    typename Lista<Tip>::Cvor *trenutniLista;

public:

    Iterator(const Niz<Tip> &n) : niz(n), lista(0), trenutniNiz(0), trenutniLista(0) {}

    Iterator(const Lista<Tip> &l) : lista(l), trenutniLista(l.p), niz(0), trenutniNiz(0) {}

    Tip trenutni()
    {
        if (niz==0 && lista==0 && trenutniLista==0) throw "Niz je prazan.";
        else if (niz==0 && lista==0 && trenutniNiz==0) throw "Lista je prazna.";
        else if (niz!=0) return niz->_niz[trenutniNiz];
        else return trenutniLista->element;
    }

    Tip prethodni()
    {
        typename Lista<Tip>::Cvor *novi(trenutniLista);
        if (niz==0 && lista==0 && trenutniLista==0) throw "Niz je prazan.";
        else if (niz==0 && lista==0 && trenutniNiz==0) throw "Lista je prazna.";
        else if (niz!=0)
        {
            trenutniNiz--;
            return niz->_niz[trenutniNiz];
        }
        else
        {
            while (novi->_sljedeci!=trenutniLista)
            {
                novi=novi->_sljedeci;
            }
            return trenutniLista->element;


        }
    }

    Tip sljedeci()
    {
        if (niz==0 && lista==0 && trenutniLista==0) throw "Niz je prazan.";
        else if (niz==0 && lista==0 && trenutniNiz==0) throw "Lista je prazna.";
        else if (niz!=0)
        {
            trenutniNiz++;
            return niz->_niz[trenutniNiz];
        }
        else
        {
            trenutniLista=trenutniLista->_sljedeci;
            return trenutniLista->element;
        }
    }

    Tip pocetak()
    {
        if (niz==0 && lista==0 && trenutniLista==0) throw "Niz je prazan.";
        else if (niz==0 && lista==0 && trenutniNiz==0) throw "Lista je prazna.";
        else if (niz!=0)
        {
            trenutniNiz=0;
            return niz->_niz[trenutniNiz];
        }
        else
        {
            trenutniLista=trenutniLista.p;
            return trenutniLista->element;
        }
    }

    Tip kraj()
    {
        if (niz==0 && lista==0 && trenutniLista==0) throw "Niz je prazan.";
        else if (niz==0 && lista==0 && trenutniNiz==0) throw "Lista je prazna.";
        else if (niz!=0)
        {
            int a(0);
            for (int i=0; i<niz.brojElemenata(); i++)
                a++;

            trenutniNiz=a;
            return niz->_niz[trenutniNiz];
        }
        else
        {
            trenutniLista=trenutniLista.poslj;
            return trenutniLista->element;
        }
    }

};



template<typename Tip>
class DvostrukaLista: public Niz<Tip>
{
    struct Cvor
    {
        Tip element;
        Cvor* _sljedeci;
        Cvor* _prethodni;

    };

    Cvor* _pocetak; //pokazivac na pocetni cvor
    Cvor* _kraj; //pokazivac na krajnji cvor
    Cvor* tekuci; //pokazivac na prethodnika tekuceg
    int brojEl;
public:
    DvostrukaLista() : tekuci(0), _pocetak(0), _kraj(0),  brojEl(0) {}

    ~DvostrukaLista()
    {
        while (_pocetak!=0)
        {
            tekuci=_pocetak;
            _pocetak=_pocetak->_sljedeci;
            delete tekuci;
        }

        _kraj=0;
        tekuci=0;
    }

    DvostrukaLista(DvostrukaLista &a)
    {
        brojEl=a.brojEl;
        _pocetak= new Cvor(*_pocetak);
        Cvor *temp(a._pocetak);
        Cvor *temp1(_pocetak);
        while (temp!=0)
        {
            if (temp==a.tekuci) tekuci=temp1;
            temp1->_sljedeci=new Cvor(temp);
            temp1=temp1->_sljedeci;
            temp=temp->_sljedeci;
        }
    }

    DvostrukaLista &operator=(DvostrukaLista &a)
    {
        while (_pocetak!=0)
        {
            tekuci=_pocetak;
            _pocetak=_pocetak->_sljedeci;
            delete tekuci;
        }

        _kraj=0;
        tekuci=0;

        brojEl=a.brojEl;
        _pocetak= new Cvor(*_pocetak);
        Cvor *temp(a._pocetak);
        Cvor *temp1(_pocetak);
        while (temp!=0)
        {
            if (temp==a.tekuci) tekuci=temp1;
            temp1->_sljedeci=new Cvor(temp);
            temp1=temp1->_sljedeci;
            temp=temp->_sljedeci;
        }


        return *this;
    }

    int brojElemenata()
    {
        return brojEl;
    }

    Tip trenutni() const
    {
        if (brojEl==0) throw "Niz je prazan.";
        return tekuci->element;
    }

    bool prethodni()
    {
        if (brojEl==0) return false;
        if (tekuci!=_pocetak)
        {
            tekuci=tekuci->_prethodni;
            return true;
        }
    }


    bool sljedeci()
    {
        if (tekuci==_kraj) return false;
        if (brojEl==0) return false;
        if (tekuci!=_kraj)
        {
            tekuci=tekuci->_sljedeci;
            return true;
        }
    }

    void pocetak()
    {
        tekuci=_pocetak;
    }

    void kraj()
    {

        tekuci=_kraj;
    }

    void obrisi()
    {
        if (tekuci==_pocetak)
        {
            _pocetak=_pocetak->_sljedeci;
            delete tekuci;
            tekuci=_pocetak;
            brojEl--;
        }
        else
        {
            Cvor *temp=_pocetak;
            while (temp->_sljedeci!=tekuci)
            {
                temp=temp->_sljedeci;
            }
            temp->_sljedeci=tekuci->_sljedeci;
            delete tekuci;
            tekuci=temp;
            brojEl--;
        }
    }


    void dodajIza(const Tip &el)
    {
        Cvor* novi=new Cvor;
        novi->element=el;
        novi->_sljedeci=0;
        if (brojEl==0)
        {
            _kraj=tekuci=novi;
        }
        else
        {
            novi->_sljedeci=tekuci->_sljedeci;
            tekuci->_sljedeci=novi;
        }
        brojEl++;
    }

    void dodajIspred(const Tip &el)
    {
        Cvor* novi=new Cvor;
        novi->element=el;
        novi->_sljedeci=0;
        if (brojEl==0)
        {
            _kraj=tekuci=novi;
        }
        else
        {
            novi->_sljedeci=tekuci->_prethodni;
            tekuci->_sljedeci=novi;
        }
        brojEl++;

    }

    Tip &operator[](int n)
    {
        if (n<0 ) throw "Ne postoji taj clan niza.";
        Cvor* temp(pocetak);
        for (int i=0; i<n; i++)
        {
            temp=temp->_sljedeci;
        }
        return temp->element;
    }
};



template<typename Tip_>
Tip_ dajMaksimum(const Niz<Tip_>& n)
{
    int index(0);
    if (int(n.trenutni())==0) throw "Niz je prazan.";
    else
    {
        int max=n[0];

        for (int i=0; i<int(n.brojElemenata()); i++)
        {

            if (n[i]>max) max=n[i];
            index=i;
        }
    }

    return n[index];

}

template<typename Tip>
Tip dajMaksimum( Lista<Tip> &n)
{

    Tip max=0;
    for (int i=1; i<n.brojElemenata(); i++)
    {

        if (max<n.trenutni()) max=n.trenutni();
    }

    return max;
}


template<typename Tip>
Tip dajMaksimum( DvostrukaLista<Tip> &dl)

{
    Tip max=dl.trenutni();
    for (int i=1; i<dl.brojElemenata(); i++)
    {
        if (dl.trenutni()>max) max=dl.trenutni();

    }

    return max;
}

int main()
{

    try
    {
        Niz<int>* niz;
        niz = new Niz<int>;

        niz->dodajIza(2);
        niz->dodajIspred(3);
        niz->dodajIza(5);
        for (int i(1); i<3; i++)
            cout << (*niz)[i] << " ";
        delete niz;

        Lista<int> *lista;
        lista=new Lista<int>;
        lista->dodajIspred(2);
        lista->dodajIza(3);
        cout<<(*lista)[1];

    }

    catch (const char tekst[])
    {
        cout<<tekst;
    }
    catch (...)
    {
        cout << "\nGreska u programu";
    }

    return 0;
}