//
//	Implement Sorted Lists with lisked lists
//	 Deal with copy structures, p.360
//

#include <iostream>

using namespace std;

// p.218
struct NodeType
{	int info;
	NodeType* next;
};

class SortedType
{
	NodeType* listData;
	int length;
	NodeType* currentPos;
public:
	SortedType()
	{	length = 0;
		listData = NULL;
	}
	~SortedType()
	{
		MakeEmpty();
	}
	// deeep copy, p.367
	void operator=(SortedType& other)
	{
		// 1. empty for other
		if (other.listData == NULL)	listData = NULL;
		// 2. one node
/*		else if (other.listData->next == NULL)
		{
			listData = new NodeType;
			listData->info = other.listData->info;
			listData->next = NULL;
		} 
*/
		else	// general
		{
			NodeType* temp_o = other.listData;;
			NodeType* temp = new NodeType;
			temp->info = other.listData->info;
			listData = temp;

			// move temp_o
			temp_o = temp_o->next;	// for one, IS NULL

			while(temp_o != NULL )
			{
				temp->next = new NodeType;
				// move temp to the new
				temp = temp->next;
				// copy info?
				temp->info = temp_o->info;
				// move temp_o
				temp_o = temp_o->next;
			}
			temp->next = NULL;
		}
	}
	// p.219
	void InsertItem(int item)
	{
		NodeType *newNode, *preLoc, *location;
		bool moreToSearch;
		location = listData;	// first node
		preLoc = NULL;
		moreToSearch = (location != NULL);
		while( moreToSearch )
		{	if( item > location->info )
			{
				preLoc = location;
				location = location->next;
				moreToSearch = (location!=NULL);
			}
			else 
				moreToSearch = false;
		}	
		newNode = new NodeType;
		newNode->info = item;		
		// insert
		// as the first first node
		if(preLoc == NULL)
		{	newNode->next = listData;
			listData = newNode;
		}
		else
		{
			newNode->next = location;
			preLoc->next = newNode;
		}
		length ++;
	}
	void MakeEmpty()	// p.218
	{	NodeType* tempPtr;
		while( listData != NULL )
		{	tempPtr = listData; // points to the head
			listData = listData->next;	// move head forward
			delete tempPtr;
		}
		length = 0;
	}
	// p.220
	void DeleteItem(int item)
	{	NodeType* location = listData;	// will point the node infront
		NodeType* tempLocation;		// wil point to THE node to be deleted

		if( item == listData->info)	// match the first node
		{
			tempLocation = location;
			listData = listData->next;	// move the head forward
		}
		else
		{
			while(item != location->next->info)
				location = location->next;
			// if match, delete location->next
			tempLocation = location->next;	// temp points THE node
			// move forward location->next
			location->next = location->next->next;
		}
		delete 	tempLocation;
		length --;
	}	
	void Print() const
	{	NodeType* temp = listData;
		while( temp!= NULL )
		{	cout << temp->info << " ";
			temp = temp->next;
		}
		cout << "\n";
	}
};
		
int main()
{
	SortedType me;
	// 2, 11, 71
	me.InsertItem(11);
	me.InsertItem(71);
	me.InsertItem(2);
	me.Print();

	// code to make 2, 11, 12, 71?
	me.InsertItem(12);

	// check
	me.Print();

	SortedType you;

	//you = me;	// shalow copy - alias name
	you = me;

	you.DeleteItem(11);
	cout << "\n\nHere is YOU: ";
	you.Print();	// 2, 12, 71

	cout << "\n\nThis is me - (with you be deleted): ";
	me.Print();	// 2. 11, 12, 71




	cout << "\n\nDone.\n\n";

	return 0;	

}