//Syed Rais Ahmad
//Assignment # 5 Quest 7
//Doubly Circular List.add,intersection of eleme in 2 lists, move node(p) forward n positions

#include<iostream.h>

//A node in a doubly list

class dlistItem 
{
public:
	int item;
	dlistItem * left;
	dlistItem * right;

};


//circular Doubly List
class dList
{
private:
	dlistItem * head;
	int total;
public:
	dList(); 
	~dList() {delete head;}; 
	bool Add(int);
	int Get(int);
	int Delete();
	bool IsEmpty();
	bool In(int);
	void PrintAll();
	int GetTotal();
	void Move(int,int);
};


//create rear and put NULL values in it.
dList::dList()
{
	head = new dlistItem;
	head->left=head->right=NULL;//Empty cList
	total=0;
}


//print all values stored in list
void dList::PrintAll()
{
	if (!IsEmpty())
	{
		dlistItem * ptr=head;
		while((ptr=ptr->right)!=head) cout << ptr->item << '\n';
	
	}
}

//return the nth node value in list
int dList::Get(int n)
{
	if (!IsEmpty())
	{
		dlistItem * ptr=head;int i=0;
		while((ptr=ptr->right)!=head && ++i<n); 
		if (i==n) return ptr->item;
		else return -1;
	}
	return -1;
}


//Insert an int to a doubly List
bool dList::Add(int newVal)
{

	dlistItem * ptr=new dlistItem;
	ptr->item=newVal;
	total++;
	if (IsEmpty())
	{
		head->right=head->left=ptr;
		ptr->right=ptr->left=head;
	}
	else
	{
		head->left->right=ptr;
		ptr->left=head->left;
		ptr->right=head;
		head->left=ptr;
	}
	
		return true;
}


//if n is present in list return true
bool dList::In(int n)
{
	if (IsEmpty()) return false;
	dlistItem * ptr=head;
	while((ptr=ptr->right)!=head) {if (ptr->item==n) return true;}

	return false;
}

//return total nodes in list
int dList::GetTotal()
{
	return total;
}

//is cList Empty
bool dList::IsEmpty()
{
	return (head->right)? false : true;
}

//move node(p) forward n positions
void dList::Move(int p,int n)
{
	if ((p+n)<=total)
	{
		dlistItem *pptr,*nptr,*ptr=head;
		int i=0,j=0;
//get to the pth node
		while(++i<=p) ptr=ptr->right;
//pth-1's right is now pth's right
		ptr->left->right=ptr->right;
		ptr->right->left=ptr->left;
		pptr=ptr;
		
		
		while(++j<=n) ptr=ptr->right;
		nptr=ptr;
//insert the pth element
		nptr->left->right=pptr;
		pptr->left=nptr->left;
		nptr->left=ptr;
		pptr->right=nptr;

		
	}
}


//------- Program's main flow starts ---------------------------

main()
{
dList d1,d2,d3;
int i=1;

for(;i<11;i++) d1.Add(i);

d2.Add(23);
d2.Add(3);
d2.Add(9);
d2.Add(1);

cout << "List 1 has elements 1 - 10. List 2 has elements 1,9,3,23.\n";
int t1,t2,temp;
t1=d1.GetTotal();
t2=d2.GetTotal();

for(i=1;i<=t1;i++) 
{
	temp=d1.Get(i);
	if (d2.In(temp)) d3.Add(temp);
}

cout << "\nIntersection of two lists is:\n";
d3.PrintAll();

cout << "\nIn List 1 third element is moved forward 4 places\n";
d1.Move(3,4);

cout << '\n';
d1.PrintAll();
	
	return 0;

}