//CIS 610-251: Link Lists
//Assignment # 4 Question 6
//Object:LIST operations:add element,delete every other element,combine ...
//...two sorted lists to one ordered list, insert an element after the nth element 

#include<iostream.h>
#include "stack.h"


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

//link list defined
class lList
{
private:
	llNode * head;
	unsigned totNode;
public:
	lList(); 
	~lList();
	void Insert(int);
	bool InsertAfter(int, int);
	bool Delete(int);
	void DeleteEveryOther(void);
	void Join2Lists(lList*);
	int getall();
	int getTotNode();
};


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

//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 address
	ptr->value=InsertInt; // Insert a value to new value
	ptr->nxtNode=NULL; //make next value of new value point to NULL
	totNode++;
}


//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;
}


//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;
	totNode++;
	}
	return false;
}

void lList::DeleteEveryOther(void)
{
	
	llNode * ptr=head->nxtNode,*temp;
	
	if(totNode%2) //odd
	{

		while(1)
		{
		if (ptr->nxtNode==NULL) break;
		temp=ptr->nxtNode->nxtNode;
		delete ptr->nxtNode;
		totNode--;
		ptr->nxtNode=temp;
		ptr=ptr->nxtNode;
		}
	}
	else //even
	{
		while(1)
		{
		if (ptr->nxtNode->nxtNode==NULL) {ptr->nxtNode=NULL;totNode--;break;}
		temp=ptr->nxtNode->nxtNode;
		delete ptr->nxtNode;
		totNode--;
		ptr->nxtNode=temp;
		ptr=ptr->nxtNode;
		}
	}
	
}

void lList::Join2Lists(lList* l2)
{

	Stack s1,s2,s3;int i=0;
	llNode * ptr2=head;
//add all values of this object to stack s1
	while(ptr2=ptr2->nxtNode) 
		s1.push(ptr2->value);
//add all values of l2 to stack s2
	ptr2=l2->head;
	while(ptr2=ptr2->nxtNode) 
		s2.push(ptr2->value);
//compare s1 and s2 values. Greater values is stored to s3.
	while( (!s1.isEmpty()) && (!s2.isEmpty()) )
	{
		if (s1.StackTop() > s2.StackTop()) s3.push(s1.pop()); 
		else s3.push(s2.pop());
	}
	
//any remaining items in s1 or s2 are pushed to s3.	
	while(!s1.isEmpty()) s3.push(s1.pop());
	while(!s2.isEmpty()) s3.push(s2.pop());

//replace current values in this object to new values from s3
	ptr2=head;
	while(ptr2=ptr2->nxtNode) 
	{
		ptr2->value=s3.pop();		
	}
//if still values remain in s3 insert them to this object.
	while(!s3.isEmpty()) Insert(s3.pop());
		
}


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



	lList l,l2;
	int i=9;
	l.Insert(1);
	l.Insert(2);
	l.Insert(3);
		l.Insert(4);
		l.Insert(5);
		l.Insert(6);
	cout << "\nYour List:\n";
	l.getall();
//l.DeleteEveryOther();
	
	l2.Insert(1);
	l2.Insert(2);
	l2.Insert(50);
	l2.Insert(60);
	l2.Insert(70);
	l2.Insert(90);

	cout << "l2 is";
	l2.getall();

	l.Join2Lists(&l2);
	cout << "Joined";

	l.getall();
	
	return 0;
}