/******************************************************
// Name: 
//
// Filename: Linksort.template
//
//
// MEMBER FUNCTIONS
//
// void printList(node<T> *head_ptr);
// Postcondition: prints the list of nodes
//
// void setData(T newData);
// Precondition: nodes are set as null
// Postcondition: nodes now contain retrieved data
//
// void setLink(node<T> *newLink);
// Postcondition: The node now contains the specified new link
//
// void sort_list(node*& head_ptr);
// Precondition: head_ptr is a head pointer of
// a linked list of items, and these items can be
// compared with a less-than operator.
// Postcondition: head_ptr points to the head
// of a linked list with exactly the same entries
// (including repetitions if any), but the entries
// in this list are sorted from smallest to 
// largest. The orginal linked list is no longer
// available.
******************************************************/
template <class T>
void node<T> :: printList(node<T> *head_ptr)
{
   cout << endl;

   while (head_ptr != NULL)
   {
      cout << head_ptr -> data << "   ";
      head_ptr = head_ptr -> next;
   }

   cout << endl;
}

template <class T>
T node<T> :: getData()
{
   return data;
}

template <class T>
void node<T> :: setData(T newData)
{
   data = newData;
}

template <class T>
node<T>* node<T> :: getLink()
{
   return next;
}

template <class T>
void node<T> :: setLink(node<T> *newLink)
{
   next = newLink;
}

template <class T>
void node<T> :: sort_list(node <T>*& head_ptr)
{
   // Sorts a linked list of integers(or any data type)

   // The original list is traversed to find the node with the largest integer
   // It is then deleted from the list.
   // To facilitate deletion of the node we keep track of each node's predecessor
   // and upon encountering a node containing a larger integer its predecessor is
   // recorded.

   node<T> *prevNodePtr,*currentNodePtr,*bigIntNodePtr,*bigIntNodePredecessorPtr;

   // Points to the new sorted list
   node<T> *newListHeadPtr = NULL;

   // Biggest integer found so far
   T bigInt;

   // Repeat till the original list contains nodes
   while (head_ptr != NULL)
   {
	// Assume that the first node contains the largest integer
	bigIntNodePtr = head_ptr;
	bigInt = head_ptr -> getData();

	// Make the successor of head node as the current node
	currentNodePtr = head_ptr -> getLink();

	// Make head node as current node's predecessor
	prevNodePtr = head_ptr;

	// Check for nodes with still large integers
	while (currentNodePtr != NULL)
	{
	   // Have we found a node with a larger integer ?
	   // Then save its pointer and its predecessor's
	   // to facilitate deletion
	   if (bigInt < currentNodePtr -> getData())
	   {
		bigIntNodePtr = currentNodePtr;
		bigInt = currentNodePtr -> getData();
		bigIntNodePredecessorPtr = prevNodePtr;
	   }

	   // Make the current node as the previous node
	   prevNodePtr = currentNodePtr;

	   // Move to next node
	   currentNodePtr = currentNodePtr -> getLink();
	}

	// Special care is to be taken if the head node has
	// the biggest integer
	// Just modify head_ptr to point to the next node
	if (bigIntNodePtr == head_ptr)
	{
	   head_ptr = head_ptr -> getLink();
	}
	// Remove the node from the original list
	// by rearranging pointers
	else
	{
	   bigIntNodePredecessorPtr -> setLink(bigIntNodePtr -> getLink());
	}

	// Add the removed node to the new list
	bigIntNodePtr -> setLink(newListHeadPtr);
	newListHeadPtr = bigIntNodePtr;
   }

   // Finally modify head_ptr to point to the new list
   head_ptr = newListHeadPtr;

}