#include <iostream>
using namespace::std;

enum { kIsSmaller, kIsLarger, kIsSame } ;

class Data
{
public:
	Data(int val):myValue(val) {}
	~Data() {}
	int Compare(const Data &);
	void Show() { cout << myValue << endl; }
private:
	int myValue;
};

int Data::Compare(const Data & theOtherData)
{
	if (myValue < theOtherData.myValue)
		return kIsSmaller;
	if (myValue > theOtherData.myValue)
		return kIsLarger;
	else 
		return kIsSame;
}

class Node;
class HeadNode;
class TailNode;
class InternalNode;

class Node
{
public:
	Node() {}
	virtual ~Node() {}
	virtual Node * Insert(Data * theData)=0;
	virtual void Show()= 0;
private:
};

class InternalNode: public Node
{
public:
	InternalNode(Data * theData, Node * next);
	~InternalNode() { delete myNext; delete myData; }
	virtual Node * Insert(Data * theData);
	virtual void Show() { myData->Show(); myNext->Show(); }

private:
	Data * myData;
	Node * myNext;
};

InternalNode::InternalNode(Data * theData, Node * next):
myData(theData),myNext(next)
{
}

Node * InternalNode::Insert(Data * theData)
{
	int result = myData->Compare(*theData);

	switch(result)
	{
	case kIsSame:
	case kIsLarger:
		{
			InternalNode * dataNode = new InternalNode(theData, this);
			return dataNode;
		}

	case kIsSmaller:
		myNext = myNext->Insert(theData);
		return this;
	}
	return this;
}

class TailNode : public Node
{
public:
	TailNode() {}
	~TailNode() {}
	virtual Node * Insert(Data * theData);
	virtual void Show() {}

private:
};

Node * TailNode::Insert(Data * theData)
{
	InternalNode * dataNode = new InternalNode(theData, this);
	return dataNode;
}

class HeadNode : public Node
{
public:
	HeadNode();
	~HeadNode() { delete myNext; }
    virtual Node * Insert(Data * theData);
	virtual void Show() { myNext->Show(); }
private:
	Node * myNext;
};

HeadNode::HeadNode()
{
	myNext = new TailNode;
}

Node * HeadNode::Insert(Data * theData)
{
	myNext = myNext->Insert(theData);
	return this;
}

class LinkedList
{
public:
	LinkedList();
	~LinkedList() { delete myHead; }
	void Insert(Data * theData);
	void ShowAll() { myHead->Show(); }
private:
	HeadNode * myHead;
};

LinkedList::LinkedList()
{
	myHead = new HeadNode;
}

void LinkedList::Insert(Data * pData)
{
	myHead->Insert(pData);
}

int main()
{
	Data * pData;
	int val;
	LinkedList ll;

	for (;;)
	{
		cout << "What value? (0 to stop): ";
		cin >> val;
		if (!val)
			break;
		pData = new Data(val);
		ll.Insert(pData);
	}

	ll.ShowAll();
	system("Pause");
	return 0;
}