#include <iostream>


using namespace std;


class ListNotValid {};
class AccessToTheEmptyList {};
class OutOfRange {};


template <class T>
class List
{
	private:
	struct Node
	{
	    T info;
	    Node* next;
	    Node* prev;
	};
	Node *head,
	     *tail;


	public:

	List()
	{
		head = NULL;
		tail = NULL;
	}



	int size()
	{
		int count = 0;
		Node* p = head;
		while(p != NULL)
		{
			count++;
			p = p->next;
		}
		return count;
	}



	void push_front(T info)
	{
	      Node* add = new Node;
	      add->next = NULL;
	      add->prev = NULL;
	      add->info = info;


	      if (head == NULL)
	      {
	          head = add;
	          tail = add;
	  	  }
	      else
	      {
	          add->next = (head);
	          (head)->prev = add;
	          (head) = add;
	      }


	}


	void push_back(T info)
	{

	      if (head == NULL)
	      {

	          push_front(info);
	  	  }
	      else
	      {
	      	(tail)->next = new Node;
	        (tail)->next->prev = tail;
	        tail = (tail)->next;
	        (tail)->next = NULL;
	  	  }

	      (tail)->info = info;

	}





	void printAll()
	{


	    if (head==NULL)
	      {
	          cout << "Spisok pust";
	          return;
	  	  }


	    Node* p = head;

	    while (p != NULL)
	    {
	        cout << p->info << " ";
	        p = p->next;
	    }
	    cout << endl;
	}


	void printReverseAll()
	{
	      if (tail==NULL)
	      {
	          cout << "Spisok pust";
	          return;
	  	  }


	      Node* p = tail;
	      while (p != NULL)
	      {

	          cout << p->info << ' ';
	          p = p -> prev;

	      }
	      cout <<endl;
	}


	void erase(int position)
	{

		if(head == NULL) return;

		Node* p = head;
		int cnt = 0;

		while((p != NULL) && (cnt != position))
		{
			p = p->next;
			cnt++;
		}

		if(p == NULL)
		{
			cout<<"del elem not found"<<endl;
			return;
		}

		if(p == head)
		{

				head = p->next;

				if (head != NULL)
				{
					(head)->prev = NULL;
				}
				else
				{
					tail = NULL;
				}
				delete p;
		}
		else if (p == tail)
	    {
				tail=(tail)->prev;

				if (tail != NULL)
				{
				 	(tail)->next = NULL;
				}
				else
				{
				 head = NULL;
				}

				delete p;
		}
		else
		{
	              Node* tmpi = head;

	              while (tmpi->next != p)
	              {
	                  tmpi = tmpi->next;
	          	  }

	              tmpi->next = p->next;

	              if (p->next != NULL)
	              {
	                  p->next->prev = tmpi;
	          	  }
	              delete p;
		}


	}

	T operator[](int i)
	{
		if(i<0)
		{
			throw OutOfRange();
		}

		if(head == NULL)
		{
			throw OutOfRange();

		}
		int count = 0;
		Node* p = head;
		while((p != NULL) && (i != count))
		{

			count++;
			p = p->next;
		}

		if(p == NULL)
		{
			throw OutOfRange();
			return NULL;
		}
		return p->info;
	}


	T front()
	{
		if(head == NULL)
		{
			//cout <<"no front element"<<endl;

			throw AccessToTheEmptyList();


		}
		return head->info;
	}

	T back()
	{
		if(tail == NULL)
		{
			throw AccessToTheEmptyList();

		}
		return tail->info;
	}


	void clear()
	{
		while(size() != 0)
		{
			erase(0);
		}
	}

	void add(List<T>& list2)
	{
		for(int i = 0;i<list2.size();i++)
		{
			push_back(list2[i]);
		}

	}


};




int main()

try {

	List<int> l;

	for (int i = 0; i < 10; i++)
	{
		l.push_back(i);
	}

	cout << "Numbers from 0 to 9: ";
	l.printAll();
	cout << "Numbers from 9 to 0: ";
	l.printReverseAll();

	cout << "Numbers from 0 to 9: ";
	for (int i = 0; i < l.size(); i++)
	{//l.size() - count of elements in list
		cout << l[i] << " ";
	}
	cout << endl;

	l.erase(9);//
	l.erase(0);

	cout << "Numbers from 1 to 8: ";
	l.printAll();
	cout << "Numbers from 8 to 1: ";
	l.printReverseAll();

	l.erase(2);
	l.erase(2);
	l.erase(2);

	cout << "List after erasing third element three times: ";
	l.printAll();

	cout << "First element: " << l.front() << endl;//1
	cout << "Last element: " << l.back() << endl;//8

	l.clear();

	try
	{
		cout << l.front() << endl;//throw AccessToTheEmptyList();
	}
	catch (AccessToTheEmptyList)
	{
		cout << "Exception test #1 passed." << endl;
	}

	try
	{
		cout << l.back() << endl;//throw AccessToTheEmptyList();
	}
	catch (AccessToTheEmptyList)
	{
		cout << "Exception test #2 passed." << endl;
	}

	try
	{
		cout << l[5] << endl;//throw OutOfRange();
	}
	catch (OutOfRange)
	{
		cout << "Exception test #3 passed." << endl;
	}

	try
	{
		cout << l[-1] << endl;//throw OutOfRange();
	}
	catch (OutOfRange)
	{
		cout << "Exception test #4 passed." << endl;
	}

	l.push_front(10);
	try
	{
		cout << l[1] << endl;//throw OutOfRange();
	}
	catch (OutOfRange) {
		cout << "Exception test #5 passed." << endl;
	}

	for (int i = 0; i < 9; i++)
	{
		l.push_front(9-i);
	}

	try
	{
		cout << l[10] << endl;//throw OutOfRange();
	}
	catch (OutOfRange)
	{
		cout << "Exception test #6 passed." << endl;
	}

	cout << "Numbers from 1 to 10: ";
	l.printAll();
	l.clear();

	l.push_back(1); l.push_back(2); l.push_back(3);

	List<int> l2;
	l2.push_back(-1); l2.push_back(-2); l2.push_back(-3);

	l.add(l2);

	l.printAll();
	l.printReverseAll();

	l2.add(l);
	l.add(l2);
	l2.clear();

	l.add(l2);

	l.printAll();
	l.printReverseAll();

	cin.get();
	return 0;
}
catch (OutOfRange) {
	cout << "Testing fail by \"OutOfRange\"\n";
	cin.get();
}
catch (AccessToTheEmptyList) {
	cout << "Testing fail by \"AccessToTheEmptyList\"\n";
	cin.get();
}
catch (ListNotValid) {
	cout << "Testing fail by \"ListNotValid\"\n";
	cin.get();
}