#include<iostream>
using namespace std;
typedef int type;
struct node
{
	type data;
	node* past;
	node* next;
};
typedef node* position;
class doublelinkedlist {
	node* head;
	node* tail;
	int count;
public:
	void makenull()
	{
		head = new node;
		
		tail = head= NULL;
		count = 0;
	}
	doublelinkedlist()
	{
		makenull();
	}

	int getLength()
	{
		return count;
	}

	position first()
	{
		return head;
	}

	position end() {
		return tail;
	}
	position locate(type value)
	{
		node* temp = head;
		int i = 0;
		while (temp->next!=NULL&&temp!=NULL)
		{
			if (temp->next->data == value)
			{
				cout <<"node number" << i +1<< "this position exist in previous node this =" << endl;
				return temp;
			}
			i++;
			temp = temp->next;
		}
		return NULL;
	}


	position previous(position item)
	{
		if (item == NULL ||item == head)
		{
			cout << "out range";
			return NULL;
		}
		else
		return (item->past);
	}
	position next(position item)
	{
		if (item == NULL || item->next == NULL)//item==tail
		{
			cout << "out range";
			return NULL;
		}
		
		else
		return item->next;
	}


	void additem(position item, type value) {
		position temp = new node;
		temp->data = value;
		temp->next = temp->past = NULL;

		if (head == NULL) 
			head = tail = temp;
		
		else if (item == NULL) {  
			cout << "Item does not exist!" << endl;
			return;
		}
		else if (item == tail) {  
			tail->next = temp;
			temp->past = tail;
			tail = temp;
		}
		else {  
			temp->next = item->next;
			temp->past = item;
			item->next->past = temp;
			item->next = temp;
		}

		count++;
	}

	type retirve(position item) {
		if (item == NULL) {
			cout << "Item unavailable" << endl;
			return -1;
		}
		return item->data;
	}

	void deleted(position item) {
		if (item == NULL) {
			cout << "Item unavailable" << endl;
			return;
		}
		else if (item == head) { 
			head = head->next;
			head->past = NULL;
		}
		else if (item == tail) {  
			tail = tail->past;
			tail->next = NULL;
		}
		else {  
			item->past->next = item->next;
			item->next->past = item->past;
		}

		delete item;
		count--;
	}

	void print()
	{
		position temp = head;
		while (temp != NULL) {
			cout << temp->data << " <-> ";
			temp = temp->next;
		}
		cout << "NULL" << endl;
	}

};

	


typedef doublelinkedlist dll;
void purge(dll  &l1)//مبتحذفش اول عنصر
{
	position temp =l1.first();
	position temp2 , nexttemp2;
		while (temp!=NULL)
		{
			temp2 =l1.next(temp);
			while(temp2 != NULL)
			{
				nexttemp2 = l1.next(temp2);
				if (temp->data == temp2->data)
				{
					
					l1.deleted(temp2);
					
				}
				temp2 = nexttemp2;
			}
			temp = l1.next(temp);
		}
		cout << "after purge" << endl;
		l1.print();
		
}

void reserved(dll& l1)
{

	dll l2;
	position temp = l1.end();
	type value;
	while (temp !=NULL)
	{
		value = l1.retirve(temp);
		l2.additem(l2.end(), value);// temp->data); 
		
		temp = l1.previous(temp);

	}
	cout << "\nbefore reserve" << endl;
	l1.print();
	l1 = l2;
	cout << "\nafter reserve" << endl;
	l1.print();
}




int main()
{
	doublelinkedlist l1;
	l1.additem(l1.first(), 40);
	l1.additem(l1.first(), 30);
	l1.additem(l1.first(), 10);
	l1.additem(l1.first(), 20);
	l1.additem(l1.first(), 30);
	l1.additem(l1.first(), 20);
	l1.additem(l1.first(), 15);
	l1.additem(l1.end(), 42);
	l1.additem(l1.end(), 50);
	l1.additem(l1.end(), 50);
	l1.additem(l1.end(), 65);
	l1.additem(l1.end(), 40);
	l1.additem(l1.end(), 50);
	l1.print();
	reserved(l1);
	//l1.deleted(l1.first());
	
	purge(l1);
	l1.print();
	cout << endl;
	//reserved(l1);
	purge(l1);
	cout<<l1.locate(30)->data << endl;
	cout << l1.retirve(l1.first()) << endl;
	cout << l1.retirve(l1.end())<< endl;  
	//cout << l1.next(l1.end())->data<<endl;	//  error
	//cout << l1.previous(l1.first())->data;	 //  error
	cout << l1.next(l1.first())->data << endl;
	cout << l1.previous(l1.end())->data;
	
	l1.print();
	l1.deleted(l1.first());
	l1.print();
	l1.deleted(l1.end());
	l1.print();
	cout << "hallo";
	return 0;
}