#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

template<typename E>

class DLinkedList {

private:
	class DNode{
	public:
		E elem;
		DNode* prev;
		DNode* next;
	};

	DNode* header;
	DNode* trailer;

	int numberOfElements;
public:
	DLinkedList(){

		header = new DNode();
		trailer = new DNode();

		header->next = trailer;
		trailer->prev = header;

		numberOfElements = 0;
	}

	virtual ~DLinkedList() {
	
		while (!empty()) 
			pop_front();
		delete header;
		delete trailer;
	}

	bool empty() const {
		return (numberOfElements == 0);

	}

	int size() const {
		return numberOfElements;
	}

	const E& front() const {
		return header->next->elem;
	}

	const E& back() const {
		return trailer->prev->elem;
	}

	void push_front(const E& e) {
		insert(header->next, e);
	}

	void push_back(const E& e) {
		insert(trailer, e);
	}

	void pop_front() {
		erase(header->next);
	}

	void pop_back() {
		erase(trailer->prev);
	}

protected:
	void insert(DNode* v,  const E& e) {
		DNode* u = new DNode();
		u->elem = e;
		u->next = v;
		u->prev = v->prev;
		v->prev->next = u;
		v->prev = u;

		numberOfElements++;
	}

	void erase(DNode* v) {
		v->prev->next = v->next;
		v->next->prev = v->prev;
		delete v;
		numberOfElements--;
	}

public:
	class Iterator {
	private:
		DNode* current;
		Iterator(DNode* u): current(u) {}
	public:
		E& operator*() {
			return current->elem;
		}
		Iterator& operator++(){
			current = current->next;
			return *this;
		}

		Iterator& operator--(){
			current = current->prev;
			return *this;
		}

		bool operator==(const Iterator& it) const {
			return current == it.current;
		}

		bool operator!=(const Iterator& it) const{
			return current != it.current;
		}

		friend class DLinkedList;
	};

	Iterator begin() const {
		return Iterator(header->next);
	}

	Iterator end() const {
		return Iterator(trailer);
	}

	void insert(const Iterator& it, const E& e){
		DNode* v = new DNode();
		DNode* w = it.current;
		DNode* u = w->prev;
		v->elem = e;
		v->next = w;
		v->prev = u;

		w->prev = v;
		u->next = v;
		numberOfElements++;
		
	}

	void erase(const Iterator& it){
		DNode* v = it.current;
		DNode* w = v->next;
		DNode* u = v->prev;
		u->next = w;
		w->prev = u;
		delete v;
		numberOfElements--;
	}
};

int main() {

	DLinkedList<string> list;

	list.push_front("ATH");
	list.push_front("THE");
	list.push_front("IOA");
	list.push_front("PAT");

	DLinkedList<string>::Iterator it = list.begin();

	while(it != list.end()) {
		cout<< *it << " ";
		++it;
	}

	cout<< endl;

	it = list.begin();
	++++it;
	list.insert(it,"CHA");

	it = list.begin();

	while (it != list.end()) {
		cout<< *it <<" ";
		++it;
	}
	cout<< endl;

	return 0;
}