# include <iostream>
using namespace std;
#include<assert.h>

struct Node
{
	int info;
	Node* link;
};

class LinkedList
{
	protected:
     	Node *first;
    	Node *last;
    	int count;
	public:
       LinkedList();
       void insertbeg(int newItem);
       const LinkedList& operator=(const LinkedList&) ;
       void copyList(const LinkedList& otherList) ;
       void print() ;
       void insertend(int newItem);
       void deleteNode(int deleteItem);
       void buildListForward();
       int front() const;
       ~LinkedList();
       void traverse_and_print();
       void destroyList();
};

const LinkedList& LinkedList:: operator= (const LinkedList& otherList)
{
   if (this != &otherList) //avoid self-copy
   {
       copyList(otherList) ;
    }//end else
   return * this;
}

void LinkedList :: copyList(const LinkedList& otherList)
{
	Node  *newNode = new Node; //pointer to create a node
	Node *current; //pointer to traverse the list
	if (first != NULL) //if the list is nonempty, make it empty
		destroyList() ;
	if (otherList. first == NULL) //otherList is empty
	{
		first = NULL;
		last = NULL;
		count = 0;
	}else
	{
		//first copy the first node
		current = otherList. first; //current points to the list to be copied
		count = otherList. count;//copy the first node
		first = new Node; //create the node
		first->info = current->info; //copy the info
		first->link = NULL; //set the link field of the node to NULL
		last = first; //make last point to the first node

		//copy the remaining list
		current = current->link; //make current point to the next node
        while (current != NULL)
        {
        	newNode = new Node; //create a node
        	newNode->info = current->info; //copy the info
        	newNode->link = NULL; //set the link of newNode to NULL
        	last->link = newNode; //attach newNode after last
        	last = newNode; //make last point to the actual last node
        	current = current->link; //make current point to the next node
        }//end while
	}//end else
}//end copyList




LinkedList::LinkedList()
{
       first = last = NULL;
       count = 0;
}

void LinkedList::destroyList()
{
	Node * temp;
    while (first != NULL)
    {
    	temp = first; //set temp to the current node
    	first = first->link; //advance first to the next node
    	delete temp; //deallocate the memory occupied by temp
    }
	last = NULL; //initialize last to NULL; first has already been set to NULL by the while loop
	count = 0;

}

LinkedList::~LinkedList()
{
	destroyList();
}

int LinkedList :: front() const
{

return first->info; //return the info of the first node
}//end


void LinkedList::print()
{
	Node * current; //pointer to traverse the list
	current = first; //set current point to the first node
	while (current != NULL) //while more data to print
	{
	cout << current->info << " ";
	current = current->link;
	}
}


/*
int linkedListType :: length()
{
   return count;
}
*/

void LinkedList :: insertbeg(int newitem)
{

  Node *newNode = new Node;
  if (first == NULL)
  {
     newNode->info = newitem;
     newNode->link = NULL;
     first = newNode;
     last = newNode;
  }
}

void LinkedList :: insertend(int newitem)
{
  Node *newNode = new Node;
  newNode->info = newitem;
  newNode->link = NULL;
  last->link = newNode;
  last = newNode;
}

void LinkedList :: buildListForward()
{
	int num;
	cout << "Enter a list of integers ending with -999. "<< endl;
	cin >> num;
	first = NULL;
	while (num != -999)
	{
		Node *newNode = new Node;
		newNode->info = num;
		newNode->link = NULL;
		if (first == NULL)
		{
			first = newNode;
			last = newNode;
		}else
		{
			last->link = newNode;
			last = newNode;
		}
		cin >> num;
	}

}
///////////////////////////////////////////////////////////////

class orderedLinkedList: public LinkedList
{
public:
	bool search(const int& searchItem) const; // have code

	void insert(const int& newItem) ;

	void insertFirst(const int& newItem) ; // have code

	void insertLast(const int& newItem) ; //have code

	void deleteNode(const int& deleteItem) ; // have code

	orderedLinkedList& mergeLists(orderedLinkedList &list1, orderedLinkedList &list2) ;
	void print1();
	void MoveNode(struct node** destRef, struct node** sourceRef);

};

void MoveNode(struct Node** destRef, struct Node** sourceRef)
{
  /* the front source node  */
  struct Node* newNode = *sourceRef;
  assert(newNode != NULL);

  /* Advance the source pointer */
  *sourceRef = newNode->link;

  /* Link the old dest off the new node */
  newNode->link = *destRef;

  /* Move dest to point to the new node */
  *destRef = newNode;
}

void orderedLinkedList::print1()
{
	Node * current; //pointer to traverse the list
	current = first; //set current point to the first node
	while (current != NULL) //while more data to print
	{
	cout << current->info << " ";
	current = current->link;
	}
}


bool orderedLinkedList::search(const int& searchItem) const
{
	bool found = false;
	Node * current; //pointer to traverse the list
	current = first; //start the search at the first node
	while (current != NULL && found == false)
	{
		if (current->info >= searchItem)
			found = true;
		else
			current = current->link;
	}
	if (found)
		found = (current->info == searchItem) ; //test for equality
	return found;
}//end search


orderedLinkedList& orderedLinkedList:: mergeLists(orderedLinkedList &list1,orderedLinkedList &list2 )
{
	Node  * dummy = new Node; //pointer to create a node
    Node *tail;
    tail = dummy;

	dummy->link = NULL;
	while(1)
	{
		if (list1 == NULL)
	    {
	    /* if either list runs out, use the other list */
			tail->link = list2;
	        break;
	    }
	    else if (list2 == NULL)
	    {
	    	tail->link = list1;
	    	break;
	    }

		if (list1->info <= list2->info)
	    {
	       MoveNode(&(tail->link), &list1);
	    }
	    else
	    {
	       MoveNode(&(tail->link), &list2);
	    }
	    tail = tail->link;
	 }
	 return(dummy->link);
}


void orderedLinkedList :: insert(const int& newItem)
{
	Node * current; //pointer to traverse the list
	Node * trailCurrent; //pointer just before current
	Node * newNode; //pointer to create a node
	bool found;
	newNode = new Node; //create the node
	newNode->info = newItem; //store newItem in the node
	newNode->link = NULL; //set the link field of the node to NULL
	if (first == NULL) //Case 1
	{
		first = newNode;
		last = newNode;
		count++;
	}else
	{
		current = first;
		found = false;
		while (current != NULL && ! found) //search the list
		{
			if (current->info >= newItem)
				found = true;
			else
			{
				trailCurrent = current;
				current = current->link;
			}
	    }
		if (current == first) //Case 2
		{
			newNode->link = first;
			first = newNode;
			count++;
		} else //Case 3
		{
			trailCurrent->link = newNode;
			newNode->link = current;
			if (current == NULL)
			{
				last = newNode;
			}
			count++;
		}
	} //end else
}//end insert