#include <iostream>
#include <ctime>
// ZADATAK JE MODIFICIRAN DA BI RADIO SA KONSTANTNIM REFERENCAMA, A I DODAN JE MAIN ZAJEDNO SA BENCHMARK TESTOM

using namespace std;

template<typename T>
class Lista {

    public:

    Lista() {}
    Lista(Lista& rhs) {}
    virtual Lista& operator=(Lista& rhs) {}
    virtual ~Lista() {}

    virtual int brojElemenata() const = 0;
    virtual T trenutni() const = 0;
    virtual T& trenutni() = 0;
    virtual bool prethodni() = 0;
    virtual bool sljedeci() = 0;
    virtual void pocetak() = 0;
    virtual void kraj() = 0;
    virtual void obrisi() = 0;
    virtual bool dodajIspred(const T&) = 0;
    virtual bool dodajIza(const T&) = 0;
    virtual T operator[](int) const = 0;
    virtual T& operator[](int) = 0;

};

template<typename T>
class NizLista : public Lista<T> {

    T** _niz, **_trenutni;// stavljeni dvostruki pokazivaci zbog problema sa konstantnim referencama
    int _brojE, _kapacitet;
    static const int INIT_NUM = 500;// Bilo 30, zakljuceno da je premalo, pa ispravljeno

    public:

    NizLista() : _niz(new T*[INIT_NUM]),
        _kapacitet(INIT_NUM), _trenutni(0), _brojE(0) {}

    NizLista(const NizLista& rhs) {
        _kapacitet = rhs._kapacitet;
        _brojE = rhs._brojE;
        _niz = new T*[_kapacitet];

        for(int i = 0; i < _brojE; i++)
            _niz[i] = new T(*rhs._niz[i]);

        _trenutni = _niz + (rhs._trenutni - rhs._niz);
    }

    virtual ~NizLista() { Unisti(); }


    virtual int brojElemenata() const { return _brojE; }

    virtual T trenutni() const {
        if(_brojE == 0)
            throw "Empty list";
        return **_trenutni;
    }

    virtual T& trenutni() {
        if(_brojE == 0)
            throw "Empty list";

        return **_trenutni;
    }

    virtual bool prethodni();
    virtual bool sljedeci();
    virtual void pocetak();
    virtual void kraj();
    virtual void obrisi();
    virtual bool dodajIspred(const T&);
    virtual bool dodajIza(const T&);
    virtual T operator[](int) const;
    virtual T& operator[](int);

    virtual NizLista& operator=(NizLista& rhs);

    void print() const;

    private:
    void Unisti(); // FUNKCIJA DODATA KAO PRILAGODBA zbog dvostrukog pokazivaca, cisto da se ne kuca petlja u destruktoru
    void prosiriListu();
};

template<typename T>
void NizLista<T>::Unisti(){
    for(int i = 0 ; i<_brojE ; i++) delete _niz[i];
    delete[] _niz;
}

template<typename T>
NizLista<T>& NizLista<T>::operator=(NizLista<T>& rhs) {

    Unisti();
    _kapacitet = rhs._kapacitet;
    _brojE = rhs._brojE;
    _niz = new T*[_kapacitet];

    for(int i = 0; i < _brojE; i++)
        _niz[i] = new T(*rhs._niz[i]);

    _trenutni = _niz + (rhs._trenutni - rhs._niz);

    return *this;
}

template<typename T>
bool NizLista<T>::prethodni() {
    if(_trenutni == _niz || _brojE == 0)
        return false;

    _trenutni--;
    return true;
}

template<typename T>
bool NizLista<T>::sljedeci() {
    if(_trenutni == _niz + (_brojE - 1) || _brojE == 0)
        return false;

    _trenutni++;
    return true;
}

template<typename T>
void NizLista<T>::pocetak() {
    if(_brojE == 0)
        throw "Empty list";

    _trenutni = _niz;
}

template<typename T>
void NizLista<T>::kraj() {
    if(_brojE == 0)
        throw "Empty list";

    _trenutni = _niz + _brojE - 1;
}

template<typename T>
void NizLista<T>::obrisi() {
    if(_brojE == 0)
        throw "Empty list";
    delete *_trenutni;
    if(_trenutni == _niz + _brojE - 1) _trenutni--;

    else
    for(T** i = _trenutni; i < _niz + _brojE - 1; i++)
        *i = *(i+1);

    _brojE--;

}

template<typename T>
bool NizLista<T>::dodajIza(const T& val) {
    if(_brojE == 0) {
        *_niz = new T(val);
        _trenutni = _niz;
        _brojE++;
        return true;
    }

    if(_brojE == _kapacitet)
        prosiriListu();

    for(int i = _brojE; i > _trenutni - _niz + 1; i--)
        _niz[i] = _niz[i - 1];

    *(_trenutni + 1) =new T(val);

    _brojE++;
    return true;
}

template<typename T>
bool NizLista<T>::dodajIspred(const T& val) {
    if(_brojE == 0) {
        *_niz = new T(val);
        _trenutni = _niz;
        _brojE++;
        return true;
    }

    if(_brojE == _kapacitet)
        prosiriListu();

    for(int i = _brojE; i >= _trenutni - _niz + 1; i--)
        _niz[i] = _niz[i - 1];

    *_trenutni = new T(val);
    _trenutni++;
    _brojE++;
    return true;
}

template<typename T>
void NizLista<T>::prosiriListu() {
    _kapacitet *= 2;
    T** noviNiz = new T*[_kapacitet];
    for(int i = 0; i < _brojE; i++)
        noviNiz[i] = _niz[i];
    _trenutni = noviNiz + (_trenutni - _niz);
    delete[] _niz;
    _niz = noviNiz;
}

template<typename T>
T NizLista<T>::operator[](int at) const {
    if(at < 0 || at >= _brojE)
        throw "Index out of range";

    return *_niz[at];
}

template<typename T>
T& NizLista<T>::operator[](int at) {
    if(at < 0 || at >= _brojE)
        throw "Index out of range";

    return *_niz[at];
}

template<typename T>
void NizLista<T>::print() const {
    for(int i = 0; i < _brojE; i++)
        cout << *_niz[i] << " ";

    cout << endl;
}


template<typename T>
class Node {

    public:

    T _val;
    Node* _next;

    Node() {
        _val = 0;
        _next = 0;
    }

    Node(const T& val) {
        _val = val;
        _next = 0;
    }

    static Node* getNode(const T& val) {
        return new Node(val);
    }

};

template<typename T>
class JednostrukaLista : public Lista<T> {

    Node<T> *_first, *_current,
        *_last;
    int _brojE;

    public:

    JednostrukaLista() : _first(0), _current(0),
        _last(0), _brojE(0) {}

    JednostrukaLista(const JednostrukaLista&);
    JednostrukaLista& operator=(const JednostrukaLista&);

    ~JednostrukaLista() { deleteAll(); }

    virtual int brojElemenata() const { return _brojE; }

    virtual T trenutni() const;
    virtual T& trenutni();
    virtual bool prethodni();
    virtual bool sljedeci();
    virtual void pocetak();
    virtual void kraj();
    virtual void obrisi();
    virtual bool dodajIza(const T&);
    virtual bool dodajIspred(const T&);
    virtual T operator[](int) const;
    virtual T& operator[](int);

    virtual void print() const;

    private:

    void deleteAll();
};

template<typename T>
JednostrukaLista<T>::JednostrukaLista(const JednostrukaLista<T>& rhs) {
    _brojE = rhs._brojE;
    _first = Node<T>::getNode(rhs._first->_val);
    Node<T> *j = _first, *i = rhs._first->_next;
    while(true) {
        if(i == rhs._current)
            _current = j;
        j->_next = Node<T>::getNode(i->_val);
        j = j->_next;
        if(i->_next == 0)
            break;
        i = i->_next;
    }

    _last = j;
}

template<typename T>
JednostrukaLista<T>& JednostrukaLista<T>::operator=(const JednostrukaLista<T>& rhs) {

    deleteAll();
    _brojE = rhs._brojE;
    _first = Node<T>::getNode(rhs._first->_val);
    Node<T> *j = _first, *i = rhs._first->_next;
    while(true) {
        if(i == rhs._current)
            _current = j;
        j->_next = Node<T>::getNode(i->_val);
        j = j->_next;
        if(i->_next == 0)
            break;
        i = i->_next;
    }

    _last = j;

    return *this;
}

template<typename T>
T JednostrukaLista<T>::trenutni() const {
    if(_brojE == 0)
        throw "Empty list";

    return _current->_val;
}

template<typename T>
T& JednostrukaLista<T>::trenutni() {
    if(_brojE == 0)
        throw "Empty list";

    return _current->_val;
}

template<typename T>
bool JednostrukaLista<T>::sljedeci() {
    if(_current == _last)
        return false;

    _current = _current->_next;
    return true;
}

template<typename T>
bool JednostrukaLista<T>::prethodni() {
    if(_current == _first)
        return false;

    Node<T>* i;
    for(i = _first; i->_next != _current; i = i->_next);

    _current = i;
    return true;
}

template<typename T>
void JednostrukaLista<T>::pocetak() {
    if(_brojE == 0)
        throw "Empty list";

    _current = _first;
}

template<typename T>
void JednostrukaLista<T>::kraj() {
    if(_brojE == 0)
        throw "Empty list";

    _current = _last;
}

template<typename T>
void JednostrukaLista<T>::obrisi() {
    if(_brojE == 0)
        throw "Empty list";
    else if(_brojE == 1) {
        delete _first;
        _first = 0;
        _current = 0;
        _last = 0;
    } else if(_current == _first) {
        Node<T>* oldCurrent = _current;
        _first->_next = _current->_next;
        _current = _first->_next;
        _first = _current;
        delete oldCurrent;
    } else if(_current == _last) {
        prethodni();
        _last = _current;
        delete _current->_next;
    } else {
        prethodni();
        Node<T>* oldCurrent = _current->_next;
        _current->_next = _current->_next->_next;
        delete oldCurrent;
        _current = _current->_next;
    }

    _brojE--;
}

template<typename T>
bool JednostrukaLista<T>::dodajIza(const T& val) {
    if(_brojE == 0) {
        _first = Node<T>::getNode(val);
        _last = _first;
        _current = _first;
        _brojE++;
        return true;
    }

    bool isLast = (_current == _last);

    Node<T>* oldNext = _current->_next;
    _current->_next = Node<T>::getNode(val);
    _current->_next->_next = oldNext;
    _brojE++;

    if(isLast)
        _last = _current->_next;

    return true;
}

template<typename T>
bool JednostrukaLista<T>::dodajIspred(const T& val) {
    if(_brojE == 0) {
        _first = Node<T>::getNode(val);
        _last = _first;
        _current = _first;
        _brojE++;
        return true;
    }

    if(_first == _current) {
        _first = Node<T>::getNode(val);
        _first->_next = _current;
        _brojE++;
        return true;
    }

    Node<T>* oldCurrent = _current;
    prethodni();
    _current->_next = Node<T>::getNode(val);
    _current->_next->_next = oldCurrent;
    _current = oldCurrent;
    _brojE++;
    return true;
}

template<typename T>
void JednostrukaLista<T>::print() const {
    Node<T>* i = _first;
    while(true) {
        cout << i->_val << " ";
        if(i == _last)
            break;
        i = i->_next;
    }

    cout << endl;
}

template<typename T>
void JednostrukaLista<T>::deleteAll() {
    while(_brojE != 0)
        obrisi();
}

template<typename T>
T JednostrukaLista<T>::operator[](int at) const {
    if(at < 0 || at >= _brojE)
        throw "Index out of range";

    Node<T> *i = _first;
    for(int j = 0; j < at; j++)
        i = i->_next;

    return i->_val;
}

template<typename T>
T& JednostrukaLista<T>::operator[](int at) {
    if(at < 0 || at >= _brojE)
        throw "Index out of range";

    Node<T>* i = _first;
    for(int j = 0; j < at; j++)
        i = i->_next;

    return i->_val;
}

 template<typename T>
 class Node2{

    public:
    Node2* _previous;
    Node2* _next;
    T _value;


    Node2() : _previous(0), _next(0), _value(0) {}
    Node2(const T& value){
        _value = value;
        _previous = 0;
        _next = 0;
    }

    static Node2* GetNode(T value){return new Node2(value);}

 };


 template<typename T>
 class DvostrukaLista : public Lista<T>{

    int _brojE;
    Node2<T> *_head, *_tail, *_current;

    public:

    DvostrukaLista() : _head(0), _tail(0), _current(0), _brojE(0) {}
    DvostrukaLista(const DvostrukaLista&);
    DvostrukaLista& operator=(const DvostrukaLista&);
    ~DvostrukaLista() { Ponisti();}

    //METODE

    int brojElemenata() const { return _brojE;}
    T trenutni() const;
    T& trenutni();
    bool prethodni();
    bool sljedeci();
    void pocetak();
    void kraj();
    void obrisi();
    bool dodajIspred(const T&);
    bool dodajIza(const T&);
    T operator[](int pozicija) const;
    T& operator[](int pozicija);
    void Isprintaj() const;

    private:

    void Ponisti();


 };

 template<typename T>
 T DvostrukaLista<T>::trenutni() const {
    if(_brojE == 0) throw "Lista je prazna";
    return _current -> _value;
 }

 template<typename T>
 T& DvostrukaLista<T>::trenutni(){
    if(_brojE == 0) throw "Lista je prazna";
    return _current->_value;
 }

 template<typename T>
 bool DvostrukaLista<T>::prethodni(){
    if(_brojE == 0) throw "Lista je prazna";
    if(_current == _head) return false;
    _current = _current -> _previous;
    return true;
 }

 template<typename T>
 bool DvostrukaLista<T>::sljedeci(){
    if(_brojE == 0) throw "Lista je prazna";
    if(_current == _tail) return false;
    _current = _current ->_next;
    return true;
 }

 template<typename T>
 void DvostrukaLista<T>::pocetak(){

    if(_brojE == 0) throw "Lista je prazna";
    _current = _head;
 }

template<typename T>
void DvostrukaLista<T>::kraj(){

    if(_brojE == 0) throw "Lista je prazna";
    _current = _tail;
}

template<typename T>
void DvostrukaLista<T>::obrisi(){

    if( _brojE == 0) throw "Lista je prazna";
    if(_brojE == 1){

        Node2<T>* oldCurrent = _current;
        _current = 0;
        _head = 0;
        _tail = 0;
        delete oldCurrent;
        _brojE--;
    }
    else if( _current == _head){

        Node2<T>* oldHead = _head;
        _current = _current->_next;
        _head = _current;
        _head->_previous = 0;
        delete oldHead;
        _brojE--;
    }
    else if(_current == _tail){

        Node2<T>* oldTail = _tail;
        _current = _current -> _previous;
        _tail = _current;
        _tail -> _next = 0;
        delete oldTail;
       _brojE--;
    }
    else {

        Node2<T>* oldCurrent = _current;
        _current->_previous -> _next = oldCurrent -> _next;
        _current -> _next -> _previous = _current ->_previous;
        _current = _current -> _next;
        delete oldCurrent;
        _brojE--;
    }

}

template<typename T>
bool DvostrukaLista<T>::dodajIza(const T& element){

    if(_brojE == 0){

        _head = Node2<T>::GetNode(element);
        _current = _head;
        _tail = _head;
        _brojE++;
        return true;
    }
    else if(_brojE == 1){


        _current -> _next = Node2<T>::GetNode(element);
        _tail = _current ->_next;
        _tail -> _previous = _current;
        _tail->_next = 0;
        _brojE++;
        return true;
    }
    else if(_current == _tail){

        _tail -> _next = Node2<T>::GetNode(element);
        _tail = _tail->_next;
        _tail -> _previous = _current;
        _tail->_next = 0;
        _brojE++;
    }
    else{

        Node2<T>* novi = Node2<T>::GetNode(element);
        Node2<T>* oldNext = _current->_next;
        _current -> _next = novi;
        novi->_next = oldNext;
        oldNext->_previous = novi;
        novi->_previous= _current;

        _brojE++;
        return true;
    }

}

template<typename T>
bool DvostrukaLista<T>::dodajIspred(const T& element){

    if(_brojE == 0){

        _head = Node2<T>::GetNode(element);
        _head->_previous = 0;
        _current = _head;
        _tail = _head;
        _tail->_next = 0;
        _brojE++;
        return true;
    }
    else if(_brojE == 1){


        _current -> _previous = Node2<T>::GetNode(element);
        _head = _current ->_previous;
        _head -> _next = _current;
        _head->_previous = 0;
        _brojE++;
        return true;
    } else if(_current == _head){

        _current -> _previous = Node2<T>::GetNode(element);
        _head = _current->_previous;
        _head->_next = _current;
        _head->_previous = 0;
        _brojE++;
    }
    else{

        Node2<T>* novi = Node2<T>::GetNode(element);

        _current->_previous->_next=novi;
        novi->_previous=_current->_previous;
        novi->_next=_current;
        _current->_previous=novi;
        _brojE++;
        return true;

    }

}

template<typename T>
T DvostrukaLista<T>::operator[](int pozicija) const{
    if(_brojE == 0) throw "Lista je prazna";
    Node2<T>* j = _head;
    for(int i = 0; i < pozicija ; i++) j=j->_next;
    return j->_value;
}

template<typename T>
T& DvostrukaLista<T>::operator[](int pozicija){
    if(_brojE == 0) throw "Lista je prazna";
    Node2<T>* j = _head;
    for(int i = 0; i < pozicija ; i++) j=j->_next;
    return j->_value;
}

template<typename T>
void DvostrukaLista<T>::Isprintaj() const{

    Node2<T>* j = _head;

    for(int i = 0; i < _brojE; i++){ cout << j->_value << " "; j = j->_next;}
    cout << endl;
}

template<typename T>
void DvostrukaLista<T>::Ponisti(){

    while(_brojE != 0) obrisi();

}

template<typename T>
DvostrukaLista<T>::DvostrukaLista(const DvostrukaLista<T>& rhs){

    _brojE = rhs._brojE;
    _head = Node2<T>::GetNode(rhs._head->_value);
    Node2<T> *j = _head, *i = rhs._head->_next, *temporary;
    while(true) {
        j->_next = Node2<T>::GetNode(i->_value);
        if(i == rhs._current)
            _current = j->_next;
        temporary = j;
        j = j->_next;
        j->_previous = temporary;
        if(i->_next == 0) break;
        i = i->_next;
    }

    _tail = j;
    _tail->_next = 0;

    }



template<typename T>
DvostrukaLista<T>& DvostrukaLista<T>::operator=(const DvostrukaLista<T>& rhs){

    Ponisti();
    _brojE = rhs._brojE;
    _head = Node2<T>::GetNode(rhs._head->_value);
    Node2<T> *j = _head, *i = rhs._head->_next, *temporary;
    while(true) {
        j->_next = Node2<T>::GetNode(i->_value);
        if(i == rhs._current)
            _current = j->_next;
        temporary = j;
        j = j->_next;
        j->_previous = temporary;
        if(i->_next == 0) break;
        i = i->_next;
    }

    _tail = j;
    _tail->_next = 0;

    return *this;
}



int main() {
cout << "==========NIZLISTA==========";
for(int i = 0; i<4; i++) cout << endl;
NizLista<int> nizlista;

for(int i = 1; i <= 5 ;i++) {

    nizlista.dodajIza(i);
    nizlista.sljedeci();
}

nizlista.print();
cout << endl;

cout << nizlista.trenutni() << endl;
nizlista.sljedeci();
cout << nizlista.trenutni() << endl;
nizlista.prethodni();
cout << nizlista.trenutni() << endl;
nizlista.pocetak();
cout << nizlista.trenutni() << endl;
nizlista.kraj();
cout << nizlista.trenutni() << endl;
cout << nizlista.brojElemenata() << endl;

nizlista.sljedeci();
nizlista.sljedeci();

nizlista.obrisi();
nizlista.print();

cout << endl << nizlista[2];
cout << endl;

NizLista<int> nizlista2(nizlista);

nizlista2.print();

cout << endl;

NizLista<int> nizlista3 = nizlista2;
nizlista3.print();

cout << "==========DVOSTRUKA LISTA==========";
for(int i = 0; i<4; i++) cout << endl;

DvostrukaLista<int> lista;

for(int i = 1; i <= 5 ;i++) lista.dodajIspred(i);
lista.Isprintaj();
cout<< endl;
cout << lista.trenutni() << endl;
lista.prethodni();
cout << lista.trenutni() << endl;
lista.prethodni();
lista.prethodni();
cout<< lista.trenutni() << endl;
lista.sljedeci();
cout << lista.trenutni() << endl;

lista.pocetak();
cout<< lista.trenutni() << endl;

lista.kraj();
cout << lista.trenutni() << endl;

lista.dodajIspred(8);
lista.Isprintaj();
lista.dodajIza(9);
lista.Isprintaj();
lista.kraj();
lista.obrisi();
lista.Isprintaj();
cout << lista.trenutni();
cout << endl;
DvostrukaLista<int> lista2(lista);
cout << endl;

lista2.Isprintaj();
cout << lista2.trenutni() << endl << endl;
lista2.sljedeci();

cout << lista2.trenutni() << endl;
lista2.prethodni();
cout << lista2.trenutni() << endl;

DvostrukaLista<int> lista3 = lista2;

cout << endl;
lista3.Isprintaj();
cout << endl;


cout << "==========JEDNOSTRUKA LISTA==========";
for(int i = 0; i<4; i++) cout << endl;

JednostrukaLista<int> listax;

for(int i = 1; i <= 5 ;i++) listax.dodajIspred(i);
listax.print();
cout<< endl;
cout << listax.trenutni() << endl;
listax.prethodni();
cout << listax.trenutni() << endl;
listax.prethodni();
listax.prethodni();
cout<< listax.trenutni() << endl;
listax.sljedeci();
cout << listax.trenutni() << endl;

listax.pocetak();
cout<< listax.trenutni() << endl;

listax.kraj();
cout << listax.trenutni() << endl;

listax.dodajIspred(8);
listax.print();
listax.dodajIza(9);
listax.print();
listax.kraj();
listax.obrisi();
listax.print();
cout << listax.trenutni();
cout << endl;
JednostrukaLista<int> lista2x(listax);
cout << endl;

lista2x.print();
cout << lista2x.trenutni() << endl << endl;
lista2x.sljedeci();

cout << lista2x.trenutni() << endl;
lista2x.prethodni();
cout << lista2x.trenutni() << endl;

JednostrukaLista<int> lista3x = lista2x;

cout << endl;
lista3x.print();
cout << endl;

cout << "==========BENCHMARK TESTIRANJE PERFORMANSI==========";
for(int i = 0; i<5; i++) cout << endl;
JednostrukaLista<int> hljeb;
for(int i = 1 ; i<=100000 ; i++){

    hljeb.dodajIza(1);

}

clock_t vrijeme1 = clock();

hljeb.prethodni();

clock_t vrijeme2 = clock();

int ukvrijeme = (vrijeme2 - vrijeme1) / (CLOCKS_PER_SEC / 1000);
cout << "Vrijeme izvrsenja metode prethodni za JEDNOSTRUKU listu je: " << ukvrijeme << " ms." << endl;

DvostrukaLista<int> pogaca;
for(int i = 1 ; i<=1000000 ; i++){

    pogaca.dodajIza(1);

}



clock_t vrijeme12 = clock();

pogaca.prethodni();

clock_t vrijeme21 = clock();

int ukvrijeme1 = (vrijeme21 - vrijeme12) / (CLOCKS_PER_SEC / 1000);
cout << "Vrijeme izvrsenja metode prethodni za DVOSTRUKU listu je: " << ukvrijeme1 << " ms." << endl;




return 0;

}