/**************************************************************************************************/
/*                                                                                                */
/*  Name:  DarC KonQuesT                                                                          */
/*  Program:  #3                                                                                  */
/*  Date:  2005.3.2                                                                               */
/*  Purpose:                                                                                      */
/*  File provided by book that allows us to create an *ordered* linked list by inheriting from    */
/*  linkedListType.h                                                                              */
/*                                                                                                */
/*                                                                                                */
/**************************************************************************************************/
#ifndef H_orderedListType
#define H_orderedListType

#include <iostream>

#include "linkedListType.h"

template<class Type>
class orderedLinkedListType: public linkedListType<Type>
{
public:
    void search(const Type& item); 
		//Outputs "Item is found in the list" if searchItem is in 
		//the list; otherwise, outputs "Item is not in the list"
    void insertNode(const Type& newItem);
		//newItem is inserted in the list
		//Post: first points to the new list and the 
		//   newItem is inserted at the proper place in the list
    void deleteNode(const Type& deleteItem);
		//If found, the node containing the deleteItem is deleted
		//from the list
		//Post: first points to the first node of the
		//   new list
    void printListReverse() const;
		//This function prints the list in the reverse order
		//Because the original list is in ascending order, the
		//elements will be printed in descending order


private:
    void reversePrint(nodeType<Type> *current) const;
		//This function is called by the public member
		//function to print the list in the reverse order
};


template<class Type>
void orderedLinkedListType<Type>::search(const Type& item)
{
	bool found;
	nodeType<Type> *current; //pointer to traverse the list
	
	found = false;		//initialize found to false
	current = first;	//start the search at the first node

	if(first == NULL)
       cout<<"Cannot search an empty list."<<endl;
	else
	{
   		while(current != NULL && !found)
			if(current->info >= item)
				found = true;
			else
				current = current->link;
			
		if(current == NULL)         //item is not in the list
			cout<<"Item is not in the list"<<endl;		
     	else        
  			if(current->info == item) //test for equality
 				cout<<"Item is found in the list"<<endl;
  			else
 				cout<<"Item is not in the list"<<endl;
	}//end else
}//end search

template<class Type>
void orderedLinkedListType<Type>::insertNode(const Type& newitem)
{
	nodeType<Type> *current;		//pointer to traverse the list
	nodeType<Type> *trailCurrent;	//pointer just before current
	nodeType<Type> *newNode;		//pointer to create a node

	bool  found;

	newNode = new nodeType<Type>;	//create the node
	newNode->info = newitem;		//store newitem in the node
	newNode->link = NULL;			//set the link field of the node
									//to NULL

	if(first == NULL)  //Case 1		
		first = newNode;
	else
	{
		current = first;
		found = false;

		while(current != NULL && !found) //search the list
			if(current->info >= newitem)
				found = true;
     		else
			{
				trailCurrent = current;
				current = current->link;
			}
		  
		if(current == first)  	//Case 2
		{
			newNode->link = first;
			first = newNode;
		}
		else				//Case 3
		{
			trailCurrent->link = newNode;
			newNode->link = current;
		}
	}//end else
}//end insertNode

template<class Type>
void orderedLinkedListType<Type>::deleteNode(const Type& deleteItem)
{
	nodeType<Type> *current; //pointer to traverse the list
	nodeType<Type> *trailCurrent; //pointer just before current
	bool found;

	if(first == NULL) //Case 1
		cout<<"Cannot delete from an empty list."<<endl;
	else
	{
		current = first;
		found = false;

		while(current != NULL && !found)  //search the list
			if(current->info >= deleteItem)
				found = true;
			else
			{
				trailCurrent = current;
				current = current->link;
			}
		
		if(current == NULL)   //Case 4
			cout<<"Item to be deleted is not in the list."<<endl;
		else
 			if(current->info == deleteItem) //item to be deleted is 
											//in the list
			{
  				if(first == current) 		//Case 2
				{
					first = first->link;
					delete current;
				}
				else     				//Case 3
				{
					trailCurrent->link = current->link;
					delete current;
				}
			}
			else  					//Case 4
				cout<<"Item to be deleted is not in the list."<<endl;
	}
} // end deleteNode


template<class Type>
void orderedLinkedListType<Type>::reversePrint
							(nodeType<Type> *current) const
{
	if(current != NULL)
	{
		reversePrint(current->link);	//print the tail
		cout<<current->info<<" ";		//print the node
	}
}

template<class Type>
void orderedLinkedListType<Type>::printListReverse() const
{
	reversePrint(first);
	cout<<endl;
} 

#endif