#include "LinkList.H"

bool DEBUG = false;

/************** START LinkList CLASS **************************/

LinkList* LinkList::CopyList()
{
	LinkList * Temp = new LinkList();
	Current = &Head;
	Index = 0;

//
// 1a. NewNode returns a node with CurrentLink ptr pointing to a 
// new node with link value set to null and the address of Link
//
// 1b. Set Current to ptr to value of null in the node
// 
// 1c. Loop
//
	while (*Current)
	{
		// newNode- makes a copy of the data in the current 
		// node without any pointers- it is a virtual function
		// it will generate the correct type of node in the
		// constructor.
		*(Temp->Current) = (*Current)->CopyNode();
		// () forces evaluation without dereferencing
		// -> happens first
		// * dereference happens next
		Current = &(*Current)->Link;
		Temp->Current = &(*Temp->Current)->Link;
	}
	Temp->Count = Count;
	Temp->Tail = Temp->Current;
	Current = &Head;
	Temp->Current = &Temp->Head;
	Temp->Index = 0;
	return Temp;
}

void LinkList::InsertNode(ListNode *lNode, int nPos)
{
// If List is Empty, Current = &Head, or *Current = Head
	lNode->Link = *Current;
	*Current = lNode;
	
	if ( (nPos > -1) && (nPos < Count) )
		SetPosition(nPos);

	// need to update tail if the insert happens at the end
	if ( Current == Tail )
		Tail = &lNode->Link;

	Index++;
	Count++;
}

// Add A Node to The Tail!!!
void LinkList::AppendNode(ListNode *lNode)
{
	*Tail = &(*lNode);
	Tail = &lNode->Link;
	Count++;
	SetPosition(Count);
}

ListNode* LinkList::DeleteNode(int nPos)
{
// make sure we aren't at the end of the list, in which
// case there is nothing to delete
	if ( (nPos > -1) && (nPos < Count) )
		SetPosition(nPos);

	if (*Current)
	{
		ListNode* Deleted = *Current;

// reset tail
		if ( Current == Tail )
		{
			Head = NULL;
			Current = Tail = &Head; 
			Count = Index = 0;
		} else {
			ListNode** Temp = &(*Current)->Link;
			*Current = *Temp;
		}
		Count--;

// reset tail again-- i'm am absolutely sure there is a 
// more elegant way to do this, but this works!
		if (Count == 0)
		{
			Head = NULL;
			Current = Tail = &Head;
			Index= 0;
		}

		return Deleted;
	} else
		return NULL;
}

void LinkList::AppendList(LinkList* lList)
{
	// Set the internal ptr in our tail (which points to the
	// last element in the list) to the head of the list that 
	// was passed in

	(*Tail) = &(*lList->Head);  // implied: *Current = *Tail;

	Count += lList->Count - 1; // set new count- index is fine where it is

	// Make sure that the new list isn't a null list- otherwise
	// tail will give us a circular reference
	if (lList->Head)
		Tail = lList->Tail;

	lList->Head = NULL; // set head of old list to NULL- it is now empty
	// cleanup will be done by the calling program
	lList->Current = lList->Tail = &lList->Head; 
	lList->Count = lList->Index = 0;
}

LinkList* LinkList::Split()
{
	LinkList *Temp = new LinkList();
	Temp->Head = *Current;

	// if Current is not an empty list, then set Tail to something other
	// than null
	if (Temp->Head)
		Temp->Tail = Tail;
	
	Tail = Current;
	*Tail = NULL;
	Temp->Count = Count - Index;
	Count = Index;
	return Temp;
}

void LinkList::SetPosition(int nPos)
{
	// if out of bounds, set to end of the list
	if (nPos < 0) nPos = Count;

	if (nPos >= Count) {
		Current = Tail;
		Index = Count;
		return;
	}
	if (nPos < Index) {
		Current = &Head;
		Index = 0;
	}
	while (Index < nPos) {
		Current = &(*Current)->Link;
		Index++;
	}
}

// LinkList::Find -- this is the version of find that looks for 
// integers (doesn't require a node to do find)

int LinkList::Find(int nVar)
{
// if out of bounds, set to end of the list
	int nodeVal = nVar - 1;

// set to start of list
	Current = &Head;
	int nTemp = GetIndex();
	Index = 0;

	nodeVal = (*Current)->GetData();
	while ( (Index < Count) && (nodeVal != nVar)) {
		Current = &(*Current)->Link;
		Index++;
	}

	// return list back to start state
	SetPosition(nTemp);

	if (nodeVal == nVar)
		return Index;
	else
		return -1;
}


// LinkList::Find -- this version returns position of first node whose 
// difference from target matches sign (+1 == +,0,-1 == -) or -1 if not found.
// This can be used to do some level of sorting

int LinkList::Find(ListNode& lTargetNode, int nSign)
{
// go to start of list
	Current = &Head;
	int nTemp = GetIndex(); // save start place
	Index = 0;
	int bFlag = false;

	if ( (nSign > 1) || (nSign < -1) )
		return -1;

	int nodeVal = lTargetNode.GetData();
	while (*Current) {
		int nTestVal = nodeVal - (*Current)->GetData();
		if ( ( (nSign == 1) && (nTestVal < 0) ) ||
			( (nSign == 0) && (nTestVal == 0) ) ||
			( (nSign == -1) && (nTestVal > 0) ) )
		{
			bFlag = true;
			break;
		}
		Current = &(*Current)->Link;
		Index++;
	}

// we don't set them back to start state in
// this case because they spent so much time
// just trying to find this!  And if the place 
// wasn't found, and they are using this information
// to decide where to append, then the end is where
// they should be anyhow.
	if (bFlag)
		return Index;  
	else
		return -1;
}


void LinkList::PrintList()
{
	Current = &Head;
	int nTemp = GetIndex();
	Index = 0;
	cout << "(";
	while ( (Index < Count) && (*Current) ) {

		if (nTemp == Index)
			cout << " | ";

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


		if (Index != Count - 1)
			cout << ", ";

		Index++;
	}
	cout << ")\n";

	SetPosition(nTemp);
}

// LinkList::Next() -- moves current and returns t/f
bool LinkList::Next()
{
	if (*Current)
	{
		(*Current) = (*Current)->Link;
		Index++;
		return true;
	} else
		return false;
}


// LinkList::Next() -- moves current and returns ptr to list node
ListNode* LinkList::Iterate()
{
	ListNode *lnTemp = NULL;
	if ( (*Current) && (Index < Count) )
	{
		lnTemp = (*Current);
		(*Current) = (*Current)->Link;
		Index++;
	} 

	return lnTemp;
}

LinkList::~LinkList()
{
	SetPosition(0);
	ListNode* Temp;
	while( (*Current != NULL) && (Count > 0) )
	{
		Count--;
		Temp = (*Current)->Link;
		delete *Current;
		*Current = Temp;
	}
}

/************** END LinkList CLASS ****************************/


/************ START IntegerListNode LIST CLASS ****************/

ListNode* IntegerListNode::CopyNode()
{
	// What Current points to 
	IntegerListNode* Temp = new IntegerListNode(Data);
	return Temp;
}

void IntegerListNode::SetData(int nData)
{
	Data = nData;
}

char* IntegerListNode::GetString(char* Buffer)
{
//   itoa(Data,Buffer,10);
   return Buffer;
}

int IntegerListNode::operator-(ListNode * lnNode)
{
	int nData = lnNode->GetData();
	return Data - nData;
}

/************ END IntegerListNode LIST CLASS *******************/

// moves current and returns ptr


// MergeSort (or actually merge) splits the entire sequence into two halves; it 
// then applies itself to these two subsequences, and finally merges the resulting, 
// sorted subsequences into 1
void MergeSort (LinkList* lListIn)
{
	if (lListIn->GetCount() <= 0) // if listlength 0, bail
		return;

	lListIn->SetPosition(0); // Start from the top
	Merge(lListIn);
	
}

void Merge(LinkList* lListIn)
{
	int nCount = lListIn->GetCount();
	int n1, n2;
	if (nCount == 1)
		return;

//	lTemp1 will get 1/2 the items from lListIn, and
//  lTemp2 the other 1/2 the items
	LinkList *lTemp1 = new LinkList();
	LinkList *lTemp2 = new LinkList();
	ListNode *lnNode = NULL; 

	while( nCount > 0 )
	{
		lnNode = lListIn->DeleteNode(0);
		if ( lnNode != NULL )
			lTemp1->AppendNode(lnNode);

		lnNode = lListIn->DeleteNode(0);
		if ( lnNode != NULL )
			lTemp2->AppendNode(lnNode);

		nCount = lListIn->GetCount();
	}
// same as: return merge(mergesort(lTemp1), Mergesort(lTemp2));
	int nCount1 = lTemp1->GetCount();

	if (DEBUG)
		cout << "count 1:" << nCount1 << "\n";  // DEBUG

// if the left list is larger than 1, subdivide and conquer
	if ( nCount1 > 1 )
		Merge(lTemp1);

	int nCount2 = lTemp2->GetCount();

	if (DEBUG)
		cout << "count 2:" << nCount2 << "\n";  // DEBUG

// if the right list is larger than 1, subdivide and conquer
	if ( nCount2 > 1 )
		Merge(lTemp2);

// ok, we are done subdividing for now- time to merge!
// start from the smallest numbers and move toward the end
	lTemp1->SetPosition(0);
	lTemp2->SetPosition(0);

// Loop until both lists are at their ends- I created a nice 
// function that is a catch all for all the probable end 
// conditions - usually this just means Current = Index.
	while( (lTemp1->IsEnd() == false) || (lTemp2->IsEnd() == false) )
	{
		int myVal = 0;
		if (lTemp1->IsEnd())  // left list is exhausted
			myVal = 0; 
		else if (lTemp2->IsEnd()) // right list is exhausted
			myVal = -1;
		else // both lists are full- may the smallest value win!
		{
			// this way is nice and easy to debug- so that's
			// the way it needs to be for now.
			n1 = lTemp1->Get()->GetData();
			n2 = lTemp2->Get()->GetData();
			myVal = n1 - n2;
		}

		if ( myVal < 0)
		{
			lnNode = lTemp1->DeleteNode();

			if (DEBUG)
				n1 = lnNode->GetData();
			
			if (lnNode) { lListIn->AppendNode(lnNode); }
		}
		else if (myVal >=0)
		{
			lnNode = lTemp2->DeleteNode();

			if (DEBUG)
				n2 = lnNode->GetData();

			if (lnNode) { lListIn->AppendNode(lnNode); }
		}

	}
	if (DEBUG)
		lListIn->PrintList();  // DEBUG

	delete lTemp1;
	delete lTemp2;
}

void main()
{

	int i;
	cout << "\n\nend first tests\n\n";

	cout << "start My code "<< endl;
	LinkList  A,*B;
	A.InsertNode(new IntegerListNode(100));
	A.InsertNode(new IntegerListNode(102),-2);
	A.InsertNode(new IntegerListNode(101),1);
	A.InsertNode(new IntegerListNode(103),8);
	A.AppendNode(new IntegerListNode(104));

	cout << "List A after inserting 100-103 "<< &A <<endl;
	B = A.CopyList();
	cout << "List B, a copy of A " << B <<endl;

// this results in garbage
	B->InsertNode(new IntegerListNode(5));
        cout << "B after inserting 5 " << B<< endl;
        A.AppendList(B);
        cout << "A after appending B " << &A << endl;
        cout << "B after the append " << B << endl;
        ListNode* x;
        x = A.DeleteNode(4);
        cout << "A after removing the " << x << " " << &A <<endl;
        delete x;
        B=A.Split();
        cout << "A and B after Split" << &A << B <<endl;
        cout << "Contents of A printed using [subscripting]";
        for (i =0;i<A.GetCount(); i++)
              cout << A[i] << ' ';

	cout << "\n\nend prof doering basic tests\n\n";

	cout << "\nstart additional basic tests\n\n";

/****************** TOM'S TESTS *********************************/
	LinkList *lList = new LinkList();
	LinkList *lList2 = new LinkList();
	LinkList *lList3;
	ListNode *nNode, *nNode2;
	Timer* myTimer = new Timer();

// TEST 1: Create a Whole Bunch of Nodes and add to List
// using InsertNode().  Then, do some test InsertNodes, 
// using SetPosition to do inserts in different parts of the list
	for (i = 100; i < 115; i++)
	{
		nNode = new IntegerListNode(i);
		lList->InsertNode(nNode);
	}
	for (i = 200; i < 215; i++)
	{
		nNode = new IntegerListNode(i);
		lList2->InsertNode(nNode);
	}
	// set node at beginning of list
	nNode = new IntegerListNode(1000);
	lList->InsertNode(nNode, 0);

	// set node at middle of list
	nNode = new IntegerListNode(2000);
	lList->InsertNode(nNode,6);

	// set node at end of list
	nNode = new IntegerListNode(3000);
	lList->InsertNode(nNode, 12);

	cout << "TEST 1: Show List With Random Inserts \n";
	lList->PrintList(); // show results of TEST 1
	 
	// TEST 2: try to delete end of the list
	nNode = lList->DeleteNode();
	if (nNode == NULL)
	{
		// didn't work, so delete middle of the list
		nNode = lList->DeleteNode(12);
	}
	cout << "TEST 2: Show Results of DeleteNode\n";
	lList->PrintList(); // show results of TEST 2

	// TEST3: CopyNode, Insert Node
	nNode2 = nNode->CopyNode();
	lList->InsertNode(nNode2);

	cout << "TEST 3: Copy Deleted Node and Re-Insert It\n";
	lList->PrintList(); // show results of TEST 3


	// TESTS 4-6: List Operations

	// TEST 4: LinkList::CopyList
	lList3 = lList->CopyList();
	cout << "TEST 4: Copied List- Show Copy\n";
	lList3->PrintList();

	// TEST 5: LinkList::AppendList
	cout << "TEST 5 a: Show List to Append\n";
	lList2->PrintList();
	lList->AppendList(lList2);
	cout << "TEST 5: Show Appended List\n";
	lList->PrintList();

	// TEST 6: LinkList::Split
	lList->SetPosition(6);
	lList3 = lList->Split();
	cout << "TEST 6 a: Test Split- Split 1st Half\n";
	lList3->PrintList();
	cout << "TEST 6 b: Test Split- Split 2nd Half\n";
	lList->PrintList();

	// TEST 7: Alternative PrintList using Operator Overloading
	cout << "TEST 7: Does << Work to Print List?\n";
	cout <<lList;

	// TEST 8: [] get node by index
	cout << "TEST 8: Test [] to Get Reference to Node and Print Data\n";
	ListNode* nNode5 = (*lList)[3];
	cout << nNode5->GetData();

	cout << "\n\nend additional basic tests\n\n";

	cout << "\n\nstart prof doering mergesort/find tests\n\n";

	int n;
	do {
		delete B;
		B = new LinkList;
		cout << "\nEnter the list size to sort: ";

        cin >> n;

		myTimer->GetTime();
		if (n<100){
			cout << "Performing reverse insertion sorting on "<<n<<" random numbers" <<endl;
			for (int i=0 ; i<n ; i++){
				int r=rand();
				x=new IntegerListNode(r);
				B->InsertNode(x,B->Find(*x,-1));
			}
			cout << "B after reverse insertion sorting on "<<n<<" random numbers" <<endl;
			cout << B <<endl;
        } else {
			cout << "Performing mergesort on "<<n<<" random numbers" <<endl;
			for (int i=0 ; i<n ; i++){
				int r=rand();
				x=new IntegerListNode(r);
				B->InsertNode(x);
			}
			MergeSort(B);
			if (n<1000){
				cout << "B after a MergeSort " << B ;
				cout<< endl;
			}
		}
		myTimer->GetTime();
     } while (n > 0);

}