// CS2310 Excise 16
// Chapter 16
// 
// Name __________________________ SSN ______________________
//
// p960 - 3:
// To the SortedList2 class, add a Boolean 
// member function named IsPresent that searches a
// list for a particular value (passed as an argument)
// and returns true if the value is found.
//
//  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 );
}

bool SortedList2::IsPresent(ItemType item)
	  // PRE: item is a well defined value.
	  // POST: Return true if item is found in the
	  //       list; false, otherwise.
{
	NodePtr ptr = head;
	
	// Write the missing code here: Beginning from head,
	// traverse the link and compare the value of 
	// parameter "item" with the "item" field of each
	// node. Stop the traverse and return true if they 
	// are equal; otherwise, move to the next node.
	// Return false if it reaches the end of the list
	// and has not found "item".

	return ptr != NULL;
}

int main() {
	SortedList2 slist;
	ItemType item;
	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;
}