//******* List.cpp *****************************************************
//
//  Derek Harter 
//  dharter@online.tamu-commerce.edu
//  Assignment #1 - Linked Lists
//  June 16, 2005
//  KDevelop Integrated Development Environment & gnu g++ compiler
//
//  This impelmentation file implements the member function of the List
//  class.  This class implements and fills
//  out the template of the List ADT given in Nyhoff "ADTs, Data
//  Structures and Problem Solving with C++ 2ed", ch 6.5 p. 296.
//  Basic operations are:
//       empty:   To determine if the list is currently empty or not.
//       traverse: To traverse and display the elements currently
//                 in the list.
//       insert: To add an item into the list.
//       delete: To remove an item from the list. 
//*******************************************************************


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

using namespace std;



// Construct a List (default).
// 
// Precondition: None.
// Postcondition: The List is initialized and initially has no
//    elements.
List::List():first(0), mySize(0)
{
}



// Destruct a List, free up any dynamically allocated memory
//    used by the List object.
//
// Precondition: None.
// Postcondition: All memory used by the List object is 
//    successfully returned to the OS for reuse.
List::~List()
{
	NodePointer ptr = first, next;
	
	while(ptr != NULL)
	{
		next = ptr->next;
		delete ptr;
		ptr = next;
	}

	mySize = 0;
}



// Provides information about the current state of the List,
//    whether or not the List is empty.
//
// Precondition: None.
// Postcondition: Returns boolean value true if the List is 
//     empty (contains no items) false otherwise.
bool List::empty() const
{
	return first == NULL;
	// or return mySize == 0;
}



// Traverse the list displaying all of the items currently in
//    the list on the provided output stream.
//
// Precondition: The ostream out is open.
// Postcondition: The items in the List have been inserted into
//    ostream out.
void List::display(ostream & out) const 
{
	NodePointer ptr = first;

	cout << "List size = " << mySize << ": ";
	while(ptr != NULL)
	{
		out << ptr->data << " ";
		ptr = ptr->next;
	}

	out << endl;
}



// Insert the indicated data item into my List of items.
//
// Precondition: first is pointing to the first Node in
//    my linked List (or is NULL if the list is empty).  
// Postcondition: A new Node is dynamically created and
//    inserted onto the front of my linked List.  The 
//    data item of the new Node contains the value that
//    was asked to be inserted.  mySize is updated by 1
//    to indicate the new size of the list after item
//    was inserted.
void List::insert(ElementType data)
{
	NodePointer newptr;

	newptr = new Node;
	newptr->data = data;
	newptr->next = first;
	
	first = newptr;

	mySize++;
}



// Delete the indicated data element from my List
//
// Precondition: first is pointing to the first Node in
//    my linked List (or is NULL if the list is empty).
// Postcondition: If a Node is found containing the
//    indicated data item, it will be removed from my
//    linked list and its memory will be freed.  mySize
//    is decremented by 1 for each item that is deleted
//    from my List.
void List::erase(ElementType data)
{

	// First make sure we are not trying to attempt erase on an already empty list
	if (first == NULL)
	{
		cerr << "*** List is empty ***" << endl;
		return;
	}

	// we need to search for the data item to be deleted
	// we are only going to find the first instance and delete, any other instances of data
	// in the list will still remain.
	NodePointer ptr = first;
	NodePointer prevPtr = NULL;

	while (ptr->data != data)
	{
		prevPtr = ptr;
		ptr = ptr->next;
	}

	// at this point either we found the item to delete, or we didn't find anything
	if (ptr == NULL)
	{
		cerr << "*** List does not contain element " << data << ", cannot delete ***" << endl;
		return;
	}

	// At this point we know we have found an item to delete.  There are 2 cases, either the
	// item is the first item in the list, or the item is somewhere in the middle of the list.
	if (ptr == first)
	{
		first = ptr->next;
	}
	else  
	{
		prevPtr->next = ptr->next;
	}
	// free up the memory that was just erased
	delete ptr;

	// update the size of my list
	mySize--;
}



// Overload the << operator for the List class.
//
// Precondition: The ostream out is open and aList is a valid list.
// Postcondition: The items in the List have been inserted into
//    ostream out.
ostream& operator<<(ostream& out, const List& aList)
{
	aList.display(out);
	return out;
}