#include <iostream>
#include <ctime>
using namespace std;

struct Node
{
	int data = 0;
	Node *prev, *next;
	Node() :prev(NULL), next(NULL) {};
};
class List {

	int length = 0;

	Node *head, *tail, *cur;
public:
	List() : head(NULL), tail(NULL), cur(NULL) {};
	~List();
	Node* creat_node(int value);
	void add_begin(int data);
	void add_last(int data);
	void insert(int data, int index);
	void pop_begin();
	void pop_end();
	//void del(int index);
	int get(int index);
	void show();
	int Count();
};

List::~List() {
	while (head) {
		tail = head->next;
		delete head;
		head = tail;
	}
}

Node* List::creat_node(int value) {
	length++;
	Node*temp = new Node();
	temp->data = value;
	temp->next = NULL;
	temp->prev = NULL;
	return temp;
}

void List::add_begin(int data) {
	Node *temp = new Node;
	temp = creat_node(data);
	if (head == tail && head == NULL) {
		head = tail = temp;
		head->next = tail->next = NULL;
		head->prev = tail->prev = NULL;
	}
	else
	{
		temp->next = head;
		head->prev = temp;
		head = temp;
		head->prev = tail;
		tail->next = head;
	}
}

void List::add_last(int data) {
	Node *temp = new Node;
	temp = creat_node(data);
	if (head == tail && head == NULL) {
		head = tail = temp;
		head->next = tail->next = NULL;
		head->prev = tail->prev = NULL;
	}
	else
	{
		tail->next = temp;
		temp->prev = tail;
		tail = temp;
		head->prev = tail;
		tail->next = head;
	}
}

void List::insert(int data, int index)
{
	Node *temp, *help, *ptr;
	temp = creat_node(data);
	if (head == tail && head == NULL)
	{
		if (index == 1) {
			head = tail = NULL;
			head->next = tail->next = NULL;
			head->prev = tail->prev = NULL;
		}
		else
		{
			cout << "Position out of range" << endl;
			length--;
			return;
		}
	}
	else
	{
		if (length < index)
		{
			cout << "Position out of range" << endl;
			length--;
			return;
		}
		else if (index == 0) {
			temp->next = head;
			head->prev = temp;
			head = temp;
			head->prev = tail;
			tail->next = head;
			return;
		}
		else if (index == length-1) {
			tail->next = temp;
			temp->prev = tail;
			tail = temp;
			head->prev = tail;
			tail->next = head;
			return;
		}
		else
		{
			help = head;
			for (int i = 0; i < length; i++)
			{
				ptr = help;
				help = help->next;
				if (i == index - 1) {
					ptr->next = temp;
					temp->prev = ptr;
					temp->next = help;
					help->prev = temp;
					cout << "Element inserted" << endl;
					break;
				}

			}
		}
	}
}

void List::pop_begin() {
	Node *temp = head;
	Node *help = new Node;
	if (length > 0)
	{
		if (tail->prev == NULL)
		{
			head = NULL;
			tail = NULL;
			cur = NULL;
		}
		else
		{
			head = head->next;
			head->prev = tail;
			tail->next = head;
			cur = head;
		}
	}
	else
	{
		cout << "List is empty " << endl;
		return;
	}
	cout << "Delete element: " << temp->data << endl;
	delete temp;
	length--;
}

void List::pop_end()
{
	Node *temp = tail;
	if (length > 0)
	{
		if (tail->prev == NULL)
		{
			head = NULL;
			tail = NULL;
			cur = NULL;
		}
		else
		{
			tail = tail->prev;
			tail->next = head;
			head->prev = tail;
			cur = tail;
		}
	}
	else
	{
		cout << "List is empty " << endl;
		return;
	}
	cout << "Delete element: " << temp->data << endl;
	delete temp;
	length--;
}




int List::get(int index) {
	Node *temp = head;
	for (int i = 0; i < index; i++) {
		if (temp != tail)
		{
			temp = temp->next;
		}
		else
			temp = head;
		}
	return temp->data;
}

int List::Count(){
	return length;
}

void List::show() {
	Node *temp = head;
	for (int i = 0; i < length - 1; i++)
	{
		cout << temp->data << endl;
		temp = temp->next;
	}
	cout << temp->data << endl;
}

int main() {

	List a;
	while (1)
	{
		int choice = 0;
		cout << "Operations on Doubly Circular linked list" << endl;
		cout << "1.Insert at Beginning" << endl;
		cout << "2.Insert at Last" << endl;
		cout << "3.Insert at Position" << endl;
		cout << "4.Delete at begin" << endl;
		cout << "5.Delete at end" << endl;
		cout << "6.Show list" << endl;
		cout << "7.Show length list" << endl;
		cout << "8.Element of index" << endl;
		cout << "Enter your choice : ";
		cin >> choice;
		switch (choice)
		{
		case 1:
		{
			int n;
			cout << "Enter number element(begin) : ";
			cin >> n;
			for (int i = 0; i < n; i++)
			{
				int data;
				cin >> data;
				a.add_begin(data);
			}
			break;
		}
		case 2:
		{
			int n;
			cout << "Enter number element(last) : ";
			cin >> n;
			for (int i = 0; i < n; i++)
			{
				int data;
				cin >> data;
				a.add_last(data);
			}
			break;
		}
		case 3:
		{
			int data, index;
			cout << "Insert element : ";
			cin >> data;
			cout << "Position : ";
			cin >> index;
			a.insert(data, index);
			break;
		}
		case 4: {
			a.pop_begin();
			break;
		}
		case 5: {
			a.pop_end();
			break;
		}
		case 6:
			a.show();
			break;
		case 7:
			a.Count();
			break;
		case 8:
		{
			int index;
			cout << "Get element : ";
			cin >> index;
			cout << a.get(index) << endl;
			break;
		}
		case 9:
			exit(1);
		default:
			cout << "Wrong choice" << endl;
		}
	}
	system("pause");
	return 0;
}