// CS2310 Exercise 22
// Chapter 18
//
// Name ________________________ SSN ____________________
//
// Chapter 18 p1051 - 10
// Write a recursive value-returning function that
// searches a dynamic linked list for the integer 
// value key. If the value is in the list, the
// function should return a pointer to the node
// where it was found. If the value is not in the
// list, the function should return NULL.
//
//  IMPLEMENTATION FILE  DYNAMIC-LINKED SORTED LIST
//  ( slist2.cpp )

#include <iostream>
#include "slist2.h"

using namespace std;

bool SortedList2::IsEmpty ( ) const {
	return (head == NULL);
}

void SortedList2::Print ( ) const {
	NodePtr ptr = head;

	cout << "The elements in the list is:" << endl;
	while (ptr != NULL) {
		printf("%6d", ptr->item);
		ptr = ptr->link;
	}
	cout << endl;
}

void SortedList2::InsertTop ( /* in */  ItemType  item ) {
	NodePtr  location;

	location = new  NodeType;
	location->item = item;
	location->link = head;
	head = location;
}

void SortedList2::DeleteTop ( /* out */ ItemType& item) {
	NodePtr  tempPtr;
	
	item = head->item;
	tempPtr = head;
	head = head->link;
	delete  tempPtr;
}

void  SortedList2 :: Delete ( /* in */  ItemType  item ) 
// Pre:       list is not empty && list elements in ascending 
//			  order
//	      &&  item == component member of some list node
// Post:	  item == element of some list node @ entry
//        &&  node containing first occurrence of item is no 
//			  longer in linked list   &&  list elements in 
//			  ascending order.
{   NodePtr   delPtr ;
	NodePtr   currPtr ;	
	//  Is item in first node? 		    
	if ( item == head->item )
	{	delPtr = head ;		// If so, delete first node	
		head = head->link ;
	} 				
    else {			// search for item in rest of list
		currPtr = head ;
		while ( currPtr->link->item  !=  item )
			currPtr = currPtr->link ;
		delPtr = currPtr->link ;
		currPtr->link = currPtr->link->link ;
	}
	delete  delPtr ;
}
	
SortedList2::SortedList2 ( ) {
	// Constructor
	// Post:	  head == NULL
	head = NULL;
}

SortedList2::~SortedList2 ( )
	// Destructor
	// Post:  All linked nodes deallocated 
{
	ItemType  temp ;
					// keep deleting top node
	while  ( !IsEmpty() )
		DeleteTop ( temp );
}

NodePtr SortedList2::PointerToKey( /* in */ NodePtr headp,
								   /* in */ int     key  )
{
	// Write the recursive solution to
	// search the dynamic linked list for the 
	// integer value key. If the value is in the 
	// list, the function should return a pointer 
	// to the node where it was found. If the 
	// value is not in the list, the function 
	// should return NULL. 

	// The base case should be headp==NULL, the 
	// function should return NULL

	// In the general case, key should be compared
	// to the item field of the node pointed-to
	// by headp, if they are equal, return headp;
	// otherwise, place a recursive call using
	// headp->link as the first parameter.
}

bool SortedList2::IsPresent(/* in */ int key) {
	return PointerToKey(head, key) != NULL;
}

int main() {
	SortedList2 slist;
	int i;

	for (i=0; i<5; i++) 
		slist.InsertTop(i);
	slist.Print();
	if (slist.IsPresent(3))
		cout << "3 is present in the list" << endl << endl;
	else
		cout << "3 is not present in the list" << endl << endl;

	slist.Delete(3);
	slist.Print();
	if (slist.IsPresent(3))
		cout << "3 is present in the list" << endl << endl;
	else
		cout << "3 is not present in the list" << endl << endl;

	for (i=0; i<3; i++) 
		slist.InsertTop(i+3);
	slist.Print();
	if (slist.IsPresent(3))
		cout << "3 is present in the list" << endl << endl;
	else
		cout << "3 is not present in the list" << endl << endl;

	slist.Delete(3);
	slist.Print();
	if (slist.IsPresent(3))
		cout << "3 is present in the list" << endl << endl;
	else
		cout << "3 is not present in the list" << endl << endl;

	return 0;
}