//
//	Implement Sorted Lists with lisked lists
//	p.217
//

#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();
	}
	// 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();

	// delete 11?
	me.DeleteItem(11);

	me.Print();

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

	return 0;	

}