#ifndef _LINKLIST_
#define _LINKLIST_
	#include <string>  // both
	#include <iostream>  // both
	#include <stdio.h>  // linux
	#include <stdlib.h> // linux
//	#include <sys\timeb.h> // windows
	#include <sys/timeb.h> // linux
#endif

using namespace std;

// forward declare
class LinkList;

// Our Abstract Class ListNode
class ListNode {

public:  //constructor/destructor

	ListNode() { return; };
	~ListNode() { return; };

protected:

	ListNode *Link;

public:  //functions

// pure virtual function(s)
	virtual ListNode* CopyNode() =0;
	virtual int operator-(ListNode *lnNode1)=0;

// other virtual, get/set methods
	virtual void SetData(int nData) {};
	virtual char* GetNodeType() { return  "UNSPECIFIED"; }
	virtual int GetData() { return -1; }
	virtual char* GetString() { return NULL; }

// so that everyone can access our protected data meeber
	friend LinkList;
	friend ostream& operator<<(ostream& s, LinkList* lList);

// to be implemented for next week's project:
//virtual void SetKey(){};//allows field selection for Value();


};

class IntegerListNode : public ListNode {

public: //constructor/destructor
	IntegerListNode(int nData) { Data = nData; Link = NULL; };
	~IntegerListNode()  { return; };

private:
	int Data;

public: //functions
	char* GetNodeType() { return "INTEGER_LIST_NODE"; }
	ListNode* CopyNode();
	int operator-(ListNode * lnNode);

// get/set values
	int GetData() { return Data; };
	void SetData(int nData);
	char* GetString(char* Buffer);
	friend ostream& operator<<(ostream& s, ListNode* lNode)
	{
		s << lNode->GetData();
		return s;
	}
};

// In my implementation of LinkList, Index is 0 to Count
// Anything less than zero (as a parameter) or more than 
// count is an indication to the program to leave Current
// where it is.

class LinkList {
public:
	LinkList() {
		 // create empty head node
		Head = NULL;
		Current = Tail = &Head;
		Index = 0;
		Count = 0;
		return;
	};
	~LinkList();

private:
	ListNode *Head;
	ListNode **Current;
	ListNode **Tail;
	int Count;
	int Index;

public:

	void SetPosition(int nPos = 0); //SetPosition
	void InsertNode(ListNode* lNode, int nPos = -1); //Insert
	LinkList* CopyList();  //Copy
	ListNode*  DeleteNode(int nPos = -1); //Delete or Remove
	void AppendList(LinkList* lList); //Append
	LinkList* Split(); //Split

	friend ostream& operator<<(ostream& s, LinkList* lList)
	{
		lList->Current = &(lList->Head);
		int nTemp = lList->GetIndex();
		lList->Index = 0;
		while (lList->Index < lList->Count) {
			if (nTemp == lList->Index)
				s << " | ";

			s << (*lList->Current)->GetData();
			lList->Current = &(*lList->Current)->Link;
			

			if (lList->Index != lList->Count - 1)
				s << ", ";

			lList->Index++;
		}
		s << "\n";
		
		lList->SetPosition(nTemp);

		return s;
	}

// GET and [] do the same exact thing, except overloaded operator cannot
// have default parameters!!!
	ListNode* operator[](int nPos) {
		if ( (nPos >= 0) && (nPos <= Count) )
			SetPosition(nPos);
		return (*Current);
	}

	ListNode* Get(int nPos=-1)
	{
		if ( (nPos >= 0) && (nPos <= Count) )
			SetPosition(nPos);
		return (*Current);
	}

	bool operator=(ListNode* ln) { (*Current)->SetData(ln->GetData()); } 

	// utility functions
	int GetIndex() { return Index; }
	int GetCount() { return Count; }
	void PrintList();
	void AppendNode(ListNode *lNode);	// Appends a single node to the end of the list  

	// Find -- overloaded -- value it returns is index or -1
	int Find(int nVar);

	// returns position of first node whose difference from target
	// matches sign (+1 == +,0 == equal,-1 == -) or -1 if not found. 
	int  Find(ListNode& lTargetNode,int nSign);

	bool Next();							// advances current (if possible), returns t/f
	ListNode * Iterate();					// moves current and returns ptr
	bool IsEmpty() { return (Count==0); }	// returns true if empty
	bool IsEnd() {
		if ( (Count==Index) || ((*Current) == NULL) || ((Head) == NULL))
			return true;
		else
			return false;
	}	// returns true if empty
	bool IsTail(ListNode* lNode) { return (Tail == &(lNode->Link)); }

};


void MergeSort(LinkList *lList);
void Merge(LinkList* lListIn);


class Timer
{
private:
	timeb t1;
	timeb t2;
public:
	Timer()
	{
		ftime ( &t1 );
		ftime ( &t2 );
	}

	void GetTime()
	{
		ftime ( &t2 );
		int time_in_ms = 0;
		if (t1.millitm < t2.millitm) {
			time_in_ms = t2.millitm - t1.millitm; 
		} else {
			time_in_ms = 1000 + t2.millitm - t1.millitm;
		}
		int time_in_seconds = t2.time - t1.time;
		printf( "time to complete= %d seconds %d milliseconds\n", time_in_seconds , time_in_ms );
		t1 = t2;
	}
};