#include <iostream>
#include <exception>
using namespace std;

class ListException : public exception {
    const char* why;
public:
        ListException(const char* reason) : why(reason) {}
        virtual const char* what() const throw() {
        return why;
        };
    };

template<typename T>
class list {
    struct element {
        T data;
        element *prev;

        element(T x, element *elem) : data(x), prev(elem) {};
    };

    int length;
    element *top;
public:

    list():length(0), top(nullptr){}
    void print() {
        cout << endl;
        element* temp = top;
        while (temp != nullptr) {
            cout << temp->data << '\t';
            temp = temp->prev;
        }
    }

    bool empty() {
        return length;
    }

    void push_front(T x) {
        insert(x, 0);
    }

    void pop_front() {
        if(length > 0)
        {
            int templength = length;
            element *temptop = top;
            if (length > 0) {
                while (templength != 2) {
                    temptop = temptop->prev;
                    templength--;
                }
            }
            delete temptop -> prev;
            temptop->prev = nullptr;
            length--;
        }
    }
    void insert(int i, T x) {
        if (i + 1 == length)
            push_back(x);
        if ((length >= i + 1) && i >= 0) {
            int templength = length;
            element *temp = new element(top->data, top);
            top = temp;
            temp = top;
            temp = temp->prev;
            while (templength != i + 1) {
                temp->data = temp->prev->data;
                temp = temp->prev;
                templength--;
            }
            temp->data = x;
            length++;
        }
    }

    T back() {
        return top->data;
    }

    T front() {
        if (length > 0)
        {
            int templength = length;
            element *temptop = top;
            if (length > 0) {
                while (templength != 1) {
                    temptop = temptop->prev;
                    templength--;
                }
            }
            T res = temptop->data;
            return res;
        }
        else throw ListException("zero length");
    }

    void pop_back() {
        element *temptop = top;
        top = top -> prev;
        delete temptop;
        length--;
    }

    void push_back(T x) {
        element *temp = new element(x, top);
        top = temp;
        length++;
    }

    void clear() {
        while(length != 0)
        {
            pop_back();
        }
    }

    void resize(int i, T value) {
        if (i > length) {
            while (i != length) {
                push_back(value);
            }
        }
    }

    void resize(int i) {
        if (i < length)
        {
            while (length != i) {
                pop_back();
            }
        } else
        {
            while (length != i)
                push_back(0);
        }
    }

    int size() {
        return length;
    }

    void remove(T value) {
        int templength = length;
        element *temptop = new element (0, top);
        element *dop = temptop;
        while (templength != 0) {
            if (temptop->prev->data == value) {
                element *bum = temptop ->prev;
                temptop->prev = temptop->prev->prev;
                delete bum;
                length--;
            } else
                temptop = temptop->prev;
            templength--;
        }
        delete dop;
    }

    T &operator[](int i) {
        element *cursor = top;

        for (int j = length - 1; i < j; j--) {
            cursor = cursor->prev;
        }

        return cursor->data;
    }

     void swap(element *f, element *s) {
        int l = 0;
        if (s == top)
        {
            l = 1;
        }
        if (s->prev == f) {
            if (s->prev != top){
                s->prev = f->prev;
                f->prev = s->prev->prev;
                s->prev->prev = f;
                if (l == 1)
                    top ->prev = s ->prev;
            } else
            {
                s = top-> prev;
                top ->prev = s ->prev;
                s ->prev = top;
                top = s;
            }
        }
        else {
                element *fdop = f->prev;
                element *sdop = s->prev;
                element *prfdop = fdop->prev;
                s->prev = fdop;
                fdop->prev = sdop->prev;
                f->prev = sdop;
                sdop->prev = prfdop;
        }
    }

    void sort() {
        for (int i = 0; i < length; i++)
        {
            element *temptop = search(i);
            for (int j = i - 1; j >= 0; j--)
            {
                if (temptop ->prev -> prev ->data > temptop ->prev ->data)
                {
                    swap(temptop -> prev, temptop);
                }
                if ((j == length -2) && (i == length - 1))
                    temptop -> prev = top;
                temptop = temptop ->prev;
            }
        }
    }
    element *search(int i){
        element *temptop = new element(0, top);
        for (int templength = length; templength > i + 1; templength--)
        {
            temptop = temptop ->prev;
        }
        return temptop ;
    }
    struct Iterator {
    private:
        element *previt;
    public:
        Iterator(element *l) : previt(l) {};

        T operator*() {
            return previt->data;
        }

        Iterator &operator--() {
            return *(new Iterator(previt = previt-> prev ));
        }

        bool operator==(const Iterator &temp) {
            return previt == temp.previt;
        }

        bool operator!=(const Iterator &temp) {
            return previt != temp.previt;
        }
    };

    Iterator &end() {
        return *(new Iterator(top));
    }

    Iterator &begin() {
        return *(new Iterator(nullptr));
    }

    ~list() {
        clear();
    }
};


int main() {
    list<int> a;
    a.remove(4);
    a.push_back(4);
    a.push_back(100);
    a.resize (5);
    a.pop_front();
    cout << endl;
    a.sort();
    list<int>::Iterator z = a.end();
    while (z!= a.begin()) {
        cout << *z << " ";
        --z;
    }
    return 0;
}