#include <iostream>
#include "ilist.cpp"

using namespace std;

template<class T> class node : public inode<T> {
private:
    T value;
    inode<T>* prev;
    inode<T>* next;
public:
    node(inode<T>* prev=NULL, inode<T>* next=NULL)
        : inode<T>(), prev(prev), next(next) {  }
    node(T t, inode<T>* prev=NULL, inode<T>* next=NULL)
        : inode<T>(),prev(prev), next(next), value (t) {  }
    ~node() {}

    T get_val() {
        return value;
    }
    void set_val(T t) {
        value = t;
    }
    inode<T>* get_prev() {
        return prev;
    }
    inode<T>* get_next() {
        return next;
    }
    bool has_next() {
        return NULL != next;
    }
    bool has_prev() {
        return NULL != prev;
    }
    void set_prev(inode<T>* prev) {
        this->prev = prev;
    }
    void set_next(inode<T>* next) {
        this->next = next;
    }
};

template <class T> class list2 : public ilist<T> {
protected:
    inode<T>* HEAD;
    inode<T>* TAIL;
    inode<T>* it_el;
public:
    list2() : HEAD(NULL), TAIL(NULL), it_el(NULL) {}
    ~list2() {}
    void push_front(T t) {
        append(t, 0);
    }
    void push_back(T t) {
        append(t, -1);
    }
    void insert(T t, int i) {
        append(t, i);
    }
    void append(T t, int i) {
        reset();
        if (-1 == i) { //na koniec
            next();
            if (NULL == it_el) {
                TAIL = HEAD = new node<T>(t);
                return;
            }
            TAIL->set_next(new node<T>(t));
            TAIL->get_next()->set_prev(TAIL);
            TAIL = TAIL->get_next();
            return;
        }
        if (0 == i) { //na poczatek
            if (NULL == HEAD) {
                it_el = TAIL = HEAD = new node<T>(t);
            } else {
                inode<T>* HEAD = this->HEAD;
                (this->HEAD = new node<T>(t))->set_next(HEAD);
                HEAD->set_prev(this->HEAD);
            }
            return;
        }
        if (NULL == HEAD) {
            it_el = TAIL = HEAD = new node<T>(t);
            return;
        }

        for (int _i=0; _i < i; _i++)
            next();
        inode<T>* buff = it_el->get_next();
        it_el->set_next(new node<T>(t));
        it_el->get_next()->set_next(buff);
        if (buff)
            buff->set_prev(it_el->get_next());
        it_el->get_next()->set_prev(it_el);
        return;
    }

    /** resetuje iteracje */
    void reset() {
        it_el = NULL;
    }

    T get_val(int idx) { //indeksowane od zera
        if (NULL == HEAD) {
            cout << "BLAD!";
            return (T)NULL;
        }
        if (0 == idx)
            return it_el->get_val();
        it_el=HEAD;
        for (int i = 0; i<idx; i++)
            next();
        return it_el->get_val();
    }

    bool next() {
        if (NULL == it_el && NULL == HEAD) //brak elementow
            return false;
        if (NULL == it_el) { // iteracja po resecie
            it_el = HEAD;
            return true;
        }
        if (!it_el->has_next()) // istnieje nastepnik
            return false;
        return it_el=it_el->get_next(); // ustawienie nastepnika
    }
    void print() {
        reset();
        cout << '[';
        if (next())
            cout << it_el->get_val();
        while(next())
            cout << ", " << it_el->get_val();
        cout << ']' << endl;
    }
    void remove_front() {
        reset();
        inode<T>* HEAD = this->HEAD;
        this->HEAD = HEAD->get_next();
        this->HEAD->set_prev(NULL);
        HEAD->set_next(NULL);
        remove(HEAD);
    }
    void remove_back() {
        if (NULL == HEAD)
            return;
        if (!HEAD->has_next()) {
            remove(HEAD);
            HEAD = TAIL = NULL;
            return;
        }
        inode<T>* TAIL = this->TAIL;
        (this->TAIL = this->TAIL->get_prev())->set_next(NULL);
        TAIL->set_prev(NULL);
        remove(TAIL);

    }
    void remove(inode<T>* t) {
        if (t->has_next())
            remove(t->get_next());
        delete t;
    }
};