// CS2310 Exercise 17
//
// Name ________________________ SSN ________________
// 
// Chapter 16 p960 - 4
// The aim of this project is to excise the usage of 
// class SortedList2 developed in textbook Chapter 16 
// and adding new functions to it.
//
// To the SortedList2 class, add a Boolean member 
// function named Equal that compares two class objects 
// and returns true if the two lists they represent are 
// identical;
//
//  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::Equal(const SortedList2& otherList) {
	// Precondition: otherList is assigned.
	// Postcondition:
	//		Compare the list pointed to by head and the
	//		list pointed to by the head member of
	//		otherList. Return true if the two lists are
	//		equally long and the contents of the lists
	//		are exactly the same; false, otherwise.

	// Write the implementation here.
	// Hint: consider how to use Find function.
}

int main() {
	SortedList2 slist1, slist2;
	ItemType item;
	int i;

	// Construct slist1
	for (i=0; i<5; i++) 
		slist1.InsertTop(i);
	cout << "The content of slist1:" << endl;
	slist1.Print();

	// Construct slist2
	for (i=0; i<5; i++) 
		slist2.InsertTop(i);
	cout << "The content of slist2:" << endl;
	slist2.Print();

	// Compare slist1 and slist2
	if (slist1.Equal(slist2))
		cout << "slist1 and slist2 are equal to each other" << endl << endl;
	else
		cout << " slist1 and slist2 are NOT equal to each other " << endl << endl;

	// Change slist1
	slist1.Delete(3);
	cout << "The content of slist1:" << endl;
	slist1.Print();
	cout << "The content of slist2:" << endl;
	slist2.Print();

	// Compare slist1 and slist2
	if (slist1.Equal(slist2))
		cout << " slist1 and slist2 are equal to each other " << endl << endl;
	else
		cout << " slist1 and slist2 are NOT equal to each other " << endl << endl;

	// Change slist2
	slist2.Delete(3);	
	cout << "The content of slist1:" << endl;
	slist1.Print();
	cout << "The content of slist2:" << endl;
	slist2.Print();

	// Compare slist1 and slist2
	if (slist1.Equal(slist2))
		cout << "slist1 and slist2 are equal to each other" << endl << endl;
	else
		cout << " slist1 and slist2 are NOT equal to each other " << endl << endl;

	return 0;
}