#include <stdio.h>

template<typename T>
class List {
public:
	struct Node {
		Node* next;
		Node* prev;
		T info;
	};
	class Iterator {
	private:
		Node* current;
	public:
		explicit Iterator(Node* c) {
			current = c;
		}
		T& operator*() const {
			return current->info;
		}
		T* operator->() const {
			return &current->info;
		}
		void operator++() {
			current = current->next;
		}
		void operator--() {
			current = current->prev;
		}
		bool isValid() const {
			return current != nullptr;
		}
		bool operator==(Iterator that) const {
			return current == that.current;
		}
		bool operator!=(Iterator that) const {
			return current != that.current;
		}
	};
private:
	Node dummy;
	
public:
	List() {
		dummy.next = &dummy;
		dummy.prev = &dummy;
	}
	
	void add(T val) {
		Node* added = new Node;
		added->info = val;
		if(dummy.prev != &dummy) {
			added->next = &dummy;
			added->prev = dummy.prev;
			dummy.prev->next = added;
		} else {
			added->next = &dummy;
			added->prev = &dummy;
			dummy.next = added;
		}
		dummy.prev = added;
	}
	bool isEmpty() const {
		return dummy.next == &dummy;
	}
	Iterator begin() {
		return Iterator(dummy.next);
	}
	Iterator end() {
		return Iterator(&dummy);
	}
};

int main()
{
	List<int> list;
	list.add(42);
	list.add(12);
	list.add(10);

	for(List<int>::Iterator it=list.begin() ; it!=list.end() ; ++it) {
		*it = *it * 10;
	}

	printf("Begin list\n");
	for(List<int>::Iterator it=list.begin() ; it!=list.end() ; ++it) {
		printf("  %d\n", *it);
	}
	printf("End list\n");
	
	int count = 0;
	for(List<int>::Iterator i=list.begin() ; i!=list.end() ; ++i) {
		for(List<int>::Iterator j=list.begin() ; j != i ; ++j) {
			if(*j>*i){
				++count;
			}
		}
	}
	printf("Inversions : %d\n", count);

	printf("Reverse list begins\n");
	
	List<int>::Iterator it=list.end();
	while(it!=list.begin()) {
		--it;
		printf("  %d\n", *it);
	}
	printf("Reverse list ends\n");
	
}