#pragma once

#include <iostream>
using namespace std;

template <class type>
struct node
{
	type value;
	node* next, * previous;
	node(type v, node* n = 0, node* p = 0)
	{
		value = v;
		next = n;
		previous = p;
	}
};

template <class type>
class list
{
	node <type>* head;
public:
	list()
	{
		head = 0;
	}
	bool empty()const
	{
		return (head == 0);
	}
	int size()const
	{
		int count = 0;
		for (node <type>* temp = head; temp != 0; temp = temp->next)
			count++;
		return count;
	}
	void print_forward()const
	{
		for (node <type>* temp = head; temp != 0; temp = temp->next)
			cout << temp->value << " ";
		cout << "\n";
	}
	void print_backward()const
	{
		if (!empty())
		{
			node <type>* temp = head;
			while (temp->next != 0)
				temp = temp->next;
			while (temp->previous != 0)
			{
				cout << temp->value << " ";
				temp = temp->previous;
			}
			cout << temp->value << endl;
		}
	}
	void push_front(type element)
	{
		if (empty())
			head = new node<type>(element);
		else
			head = head->previous = new node<type>(element, head);
	}
	void push_back(type element)
	{
		if (empty())
			head = new node<type>(element);
		else
		{
			node <type>* temp = head;
			while (temp->next != 0)
				temp = temp->next;
			temp->next = new node<type>(element, 0, temp);
		}
	}
	void insert(type element, int position)
	{
		if (position < 1 || position > size() + 1)
			cout << "Position is out of range when inserting an element in the list." << endl;
		else if (position == 1)
			push_front(element);
		else if (position == size() + 1)
			push_back(element);
		else
		{
			node <type>* temp = head;
			for (int count = 1; count < position - 1; count++)
				temp = temp->next;
			temp->next = temp->next->previous = new node<type>(element, temp->next, temp);
		}
	}
	void pop_front()
	{
		if (empty())
			cout << "You can't delete an element in an empty list." << endl;
		else if (size() == 1)
		{
			delete head;
			head = 0;
		}
		else
		{
			head = head->next;
			delete head->previous;
			head->previous = 0;
		}
	}
	void pop_back()
	{
		if (empty())
			cout << "You can't delete an element in an empty list." << endl;
		else if (size() == 1)
		{
			delete head;
			head = 0;
		}
		else
		{
			node <type>* temp = head;
			while (temp->next != 0)
				temp = temp->next;
			temp->previous->next = 0;
			delete temp;
		}
	}
	void erase_position(int position)
	{
		if (empty())
			cout << "You can't delete an element in an empty list." << endl;
		else if (position < 1 || position > size())
			cout << "The position is out of range when deleting an element in the list." << endl;
		else if (position == 1)
			pop_front();
		else if (position == size())
			pop_back();
		else
		{
			node <type>* temp = head;
			for (int count = 1; count < position; count++)
				temp = temp->next;
			temp->next->previous = temp->previous;
			temp->previous->next = temp->next;
			delete temp;
		}
	}
	bool search(type element)const
	{
		for (node <type>* temp = head; temp != 0; temp = temp->next)
		{
			if (temp->value == element)
				return true;
		}
		return false;
	}
	int find_position(type element)const
	{
		int count = 1;
		for (node <type>* temp = head; temp != 0; temp = temp->next)
		{
			if (temp->value == element)
				return count;
			count++;
		}
		return 0;
	}
	node <type>* find_iterator(type element)const
	{
		for (node <type>* temp = head; temp != 0; temp = temp->next)
		{
			if (temp->value == element)
				return temp;
		}
		return 0;
	}
	void erase(type element)
	{
		if (empty())
			cout << "You can't erase an element in an empty list." << endl;
		else if (search(element) == 0)
			cout << "The element is not found in the list." << endl;
		else
			erase_position(find_position(element));
	}
	~list()
	{
		while (!empty())
			pop_front();
	}
	void operator=(list <type>& otherList)
	{
		while (!empty())
			pop_back();
		if (!otherList.empty())
		{
			node <type>* temp1, * temp2 = otherList.head;
			temp1 = head = new node<type>(temp2->value);
			while (temp2->next != 0)
			{
				temp2 = temp2->next;
				temp1->next = new node<type>(temp2->value, 0, temp1);
				temp1 = temp1->next;
			}
		}
		else
			head = 0;
	}
	list(list <type>& otherList)
	{
		if (!otherList.empty())
		{
			node <type>* temp1, * temp2 = otherList.head;
			temp1 = head = new node<type>(temp2->value);
			while (temp2->next != 0)
			{
				temp2 = temp2->next;
				temp1->next = new node<type>(temp2->value, 0, temp1);
				temp1 = temp1->next;
			}
		}
		else
			head = 0;
	}
};