#include <iostream>
#include <stdlib.h>

using namespace std;


struct nodetype
{	int data;
	nodetype * next;
	nodetype ( int, nodetype *);
};

nodetype::nodetype(int n, nodetype * link)
: data(n), next(link)
{}

class linklist
{	public:
	  linklist ();
	  void insert( int insertvalue);
	  void print ( ) const;
	  void fill (int numOfInts );
	  linklist (const linklist & original);
	  void deletenode( int deletevalue);
	  //void destroy( );
	  //~linklist();
	private:
		nodetype * front;
		nodetype * rear;
};
void checkparameter (linklist copy);
int menu();

int main()
{

linklist list;
int choice, num;
	do
	{	system("cls");
		choice = menu( );
		switch(choice)
		{	case 1: cout<<"Enter integer to insert:";
			cin>>num;
			list.insert(num); break;
			case 2: list.print(); break;
			case 3: cout<<"How many random integers?";
					cin>>num;
					list.fill(num); break;
			case 4: {linklist copy (list);
					cout<<"copy: ";
					copy.print();
					}break;
			case 5:	cout<<"Enter the number to delete:";
					cin>>num;
					list.deletenode(num); break;
		//	case 6: list.destroy(); break;
			case 7:	checkparameter(list); break; 
			case 9: break;
			default: cout<<"Invalid choice\n";
				cin.ignore(); cin.ignore();
		}
	} while (choice != 9);


return 0;
}
void checkparameter (linklist copy)
{  //pre: copy is a valid circular linked list (could be empty)
  //post: copy is modified and printed and then erased by operating system

	copy.insert(33);
	copy.insert(55);
	cout<<"copy:";
	copy.print();
}

int menu( )
{
int choice;
system("cls");
cout<<"	LAB 4 MENU"<<endl;
cout<<" 1 Insert a number into the ordered circular list"<<endl;
cout<<" 2 Print the ordered circular list"<<endl;
cout<<" 3 Insert random integers into the ordered circular list"<<endl;
cout<<" 4 Test the copy constructor of the ordered circular list"<<endl;
cout<<" 5 Delete a number from the ordered circular list"<<endl;
cout<<" 6 Destroy the ordered circular list"<<endl;
cout<<" 7 Pass the list as value parameter & check"<<endl;
cout<<" 9 Quit"<<endl;
cin>>choice;
return choice;
}

linklist::linklist()
{
front = NULL;
rear = NULL;
}

void linklist::fill(int numOfInts)
{ 
  int i;
  nodetype *tempnode;
	for ( i = 0; i<numOfInts; i++)
	{ int rnum = rand();
	  rnum = rnum % 100;
	   nodetype *newnode = new nodetype(rnum,NULL);
		if( front == NULL && rear == NULL)
		{
			front = rear = newnode;
			rear->next = front;
		}
		else if(rnum<front->data)
		{
			newnode->next = front;
			front = newnode;
			rear->next = newnode;
		}

		else if(rnum>rear->data)
		{
			newnode->next = front;
			rear->next = newnode;
			rear = newnode;
		}

		else
		{
			tempnode = front;

				while ( tempnode->next != rear && tempnode->next->data < rnum)
				{
					tempnode = tempnode->next;
				}
				
			newnode->next = tempnode->next;
			tempnode->next = newnode;
		}
	}
cin.ignore();
}


void linklist::print() const
{
	nodetype *traverse = front;
	while( traverse != rear)
	{
		cout<<traverse->data<<" ";
		traverse = traverse->next;
	}
	cout<<traverse->data;
		
	cin.ignore();
	cin.ignore();
}

void linklist::insert( int insertvalue )
{
   nodetype *tempnode;

	    nodetype *newnode = new nodetype(insertvalue,NULL);
		if( front == NULL && rear == NULL)
		{
			front = rear = newnode;
			rear->next = front;
			return;
		}
		else if(insertvalue<front->data)
		{
			newnode->next = front;
			front = newnode;
			rear->next = newnode;
			return;
		}

		else if(insertvalue>rear->data)
		{
			newnode->next = front;
			rear->next = newnode;
			rear = newnode;
			return;
		}

		else
		{
			tempnode = front;

				while ( tempnode->next != rear && tempnode->next->data < insertvalue)
				{
						
					tempnode = tempnode->next;
				
				}
				newnode->next = tempnode->next;
				tempnode->next = newnode;
				return;
		}

  cin.ignore();

}

void linklist::deletenode( int deletevalue)
{
  nodetype *garbage;
  nodetype *tempnode = front;
  while (tempnode != rear)
  {

	if (deletevalue == front->data)
	{
			cout<<"bihia"<<endl;
		garbage = front;
		front = front->next;
		delete garbage;
		return;

	}
	if (deletevalue == rear->data)
	{
			
		garbage = rear;
		tempnode = front;
		while (tempnode->next != rear)
		{
			tempnode = tempnode->next;
		}

		rear = tempnode;	
		rear->next = front;

		delete garbage;
		return;

	}
	else
		while( tempnode->next != rear)
		{
			if (deletevalue == tempnode->next->data)
			{
				garbage = tempnode->next;
				tempnode->next = tempnode->next->next;
				delete garbage;
				return;
			}
			
		}
  cout<< "Not in list.  Please press enter to continue...";
  cin.ignore();
  cin.ignore();
  return;

  }
}

linklist::linklist (const linklist & original)
{
	front = original.front;
	rear = original.rear;
	nodetype *copy = new nodetype(front->data,NULL);
	nodetype *traverse = front;
	front = copy;

	while(traverse != original.rear)
	{
		traverse = traverse->next;
		copy->next = new nodetype(traverse->data,NULL);
		copy = copy->next;

	}
rear = copy;
	
}