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

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){
			//no chnaging the following lineup!!!!
			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("Athens");
	list.push_front("Thessaloniki");
	list.push_front("Ioannina");
	list.push_front("Patra");

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

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

	cout << endl;

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

	it = list.begin();

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