//CIS 610-251: Link Lists
//Assignment # 4 Question 4
//Object:Concat 2 lists, reverse a list, delete nth element, insert after nth.

#include<iostream.h>

//link list node type
class llNode
{
public:
	int value;
	llNode * nxtNode;
};

//link list defined
class lList
{
private:
	llNode * head;
public:
	lList(); 
	~lList();
	void Insert(int);
	bool InsertAfter(int, int);
	bool Delete(int);
	bool Concat(lList*);
	void Reverse(void);
	int getall();

};


//create head and put NULL values in it.
lList::lList()
{
	head = new llNode; 
	head->nxtNode=NULL;
	head->value=NULL;
}

//Destroy/free list/memory
lList::~lList()
{
	delete head;
} 


//Insert to the tail of link list
void lList::Insert(int InsertInt)
{
	llNode * ptr=head; 

	while(ptr->nxtNode)  //go all the way to NULL-pointing/last node
		ptr=ptr->nxtNode; 

	ptr->nxtNode=new llNode; 
	ptr=ptr->nxtNode; // temporary pointer holds new value's Insertress
	ptr->value=InsertInt; // Insert a value to new value
	ptr->nxtNode=NULL; //make next value of new value point to NULL
}

//join two lists together.
bool lList::Concat(lList * ll)
{
	llNode * ptr=head;
	while(ptr->nxtNode) ptr=ptr->nxtNode;
	ptr->nxtNode=ll->head->nxtNode;
	return true;
}

//print all values in the link list.
int lList::getall()
{
	llNode * ptr=head; //ptr gets the head value
		while (ptr=(ptr->nxtNode)) //while ptr points to not NULL value
			cout << ptr->value << "\n";

	return NULL;
}




//reverse the list
void lList::Reverse(void)
{
	lList l2;
	llNode * ptr=head;
	l2.Insert(ptr->nxtNode->value);
	ptr=ptr->nxtNode;
	while(ptr=ptr->nxtNode)
	{
		llNode * temp=new llNode;  //temp node
		temp->nxtNode=l2.head->nxtNode; //temp node now points to first node of l2
		temp->value=ptr->value;   //temp gets the value of origianl list node
		l2.head->nxtNode=temp;    //l2's head is the new temp node.
	}

	head->nxtNode=l2.head->nxtNode;//point the original head to reversed nodes.
}


//inserts insInt Integer after interger 'after' in list
bool lList::InsertAfter(int insInt, int after)
{
	llNode * ptr=head,*temp=NULL;
	int current= -1 ;
	while (ptr->nxtNode && ++current<after) ptr=ptr->nxtNode;
	if (ptr)
	{
	temp=ptr->nxtNode; //temp ptr holds address of next node
	ptr->nxtNode=new llNode;  //current value gets new nxtNode address
	ptr->nxtNode->nxtNode=temp; //new value's nxtNode gets the address of temp
	ptr->nxtNode->value=insInt; //new value gets value to be inserted
	return true;
	}
	return false;
}

//delete nth node.
bool lList::Delete(int nth)
{
	if (nth>0)
	{
	llNode * ptr=head,*temp=NULL;
	int current= 0 ;
	while (ptr->nxtNode && ++current<nth) ptr=ptr->nxtNode;
	if (ptr->nxtNode)
	{
		temp=ptr->nxtNode->nxtNode; //temp ptr holds address of next to next node
		delete(ptr->nxtNode);
		ptr->nxtNode=temp; //node points to the previous next to next node.
		return true;
	}
	}
	return false;
}





//------- Program's main flow starts ---------------------------
main()
{

	lList myList,l2;
	int i=9;
//insert values in mylist
	while(i!=-1)
	{
		cout << "\nEnter Int to insert into List,(exit=-1)";
		cin >> i;
		if (i!=-1) myList.Insert(i);
	}
	
	cout << "\nYour List:\n";
	myList.getall();
//another list
	cout << "\nList 2 contains 1,2,3,4,5";
	l2.Insert(1);
	l2.Insert(2);
	l2.Insert(3);
	l2.Insert(4);
	l2.Insert(5);
    cout << "\n L2 Concatenated to your list=\n";	
//Concat two lists
	myList.Concat(&l2);
	myList.getall();
//Reverse the list
	cout << "\nReverse of list is=\n";
	myList.Reverse();
//Print the list
	myList.getall();

	return 0;
}