//
// File: studgradelnklist.cpp.  
// Contents: C++ source code for dynamic memory allocation 
// implementation of a linked list of grades.  Each node in the 
// linked list contains a grade and the occurrence count for that 
// grade. The grades are stored in ascending order.
//

#include "gradelnklist.h"
#include <iostream>
#include <iomanip>
using namespace std;

// ---------- general list members first ----------

// --------------------------------------------------------------------
// GradeList constructor -  initializes a list to empty
// --------------------------------------------------------------------
// Accepts:  nothing
// Returns:  nothing
// --------------------------------------------------------------------

GradeList::GradeList()
{
head = NULL;
}

// --------------------------------------------------------------------
// GradeList destructor - deletes all nodes in list
// --------------------------------------------------------------------
// Accepts:  nothing
// Returns:  nothing
// --------------------------------------------------------------------

GradeList::~GradeList()
{
NodeType* tmp;    // temp ptr for deleting nodes

while (head != NULL)    // destroy nodes one by one
{
    tmp = head;
    head = head->next;
    delete tmp;
}
}

// --------------------------------------------------------------------
// IsEmpty - test for empty list
// --------------------------------------------------------------------
// Accepts:  nothing
// Returns:  true if the list is empty, false otherwise.
// --------------------------------------------------------------------

bool GradeList::IsEmpty(void)
{
return (head == NULL);
}

// --------------------------------------------------------------------
// IsFull - test for full list
// --------------------------------------------------------------------
// Accepts:  nothing
// Returns:  false always, because, within the bounds of memory size,
//           the list never fills!
// --------------------------------------------------------------------

bool GradeList::IsFull()
{
return false;
}

// -------------------------------------------------------------------
// Display - prints the grades in the list, one grade per line
// -------------------------------------------------------------------
// Accepts:  nothing
// Returns:  nothing
// -------------------------------------------------------------------

void GradeList::Display()
{
    NodeType* tmp = head;   // temp ptr for traversing list

    if (IsEmpty())	    // If the list is empty, display message.
    	cout << "\nThere are no grades\n\n";
    else		    // If not, print headings...
    {
    	cout << "\nGrades    Num of Each \n\n";
    	while (tmp != NULL)	// and grades with counts.
    	{
            cout << setw(4) << tmp->grade << setw(14) << tmp->count << "\n";
            tmp = tmp->next;
    	}
    }
}

// -------------------------------------------------------------------
// Function to insert a new grade into the list in ascending order
// -------------------------------------------------------------------
// Accepts:  the new grade
// Returns:  nothing
// -------------------------------------------------------------------

void GradeList::InsertGrade(int newgrade)
{
NodeType* curr = head;   // temp ptr for traversing list
NodeType* prev = NULL;   // temp ptr for traversing list
NodeType* tmp;           // temp ptr to create new node

while (curr != NULL && curr->grade < newgrade)  // find place to insert
{
    prev = curr;
    curr = curr->next;
}

if (curr != NULL && curr->grade == newgrade)    // grade already here ...
    curr->count++;                              // ... simply inc. count
else
    if (prev == NULL)    // empty list or insert at beginning
    {
        tmp = new NodeType;
        tmp->grade = newgrade;
	tmp->count = 1;
	tmp->next = head;
	head = tmp;
    }
    else                 // insert in middle or at end
    {
	tmp = new NodeType;
	tmp->grade = newgrade;
	tmp->count = 1;
	tmp->next = curr;
        prev->next = tmp;
    }
}

// -------------------------------------------------------------------
// Function to delete the indicated grade from the list
// -------------------------------------------------------------------
// Accepts:  grade to delete
// Returns:  nothing
// -------------------------------------------------------------------

void GradeList::DeleteGrade(int delgrade)
{
    NodeType* curr = head;   // temp ptr for traversing list
    NodeType* prev = NULL;   // temp ptr for traversing list
    NodeType* tmp;           // temp ptr to create new node
    
    while (curr != NULL && curr->grade < delgrade)  // find grade to delete
    {
        prev = curr;
        curr = curr->next; 
    }
        
    if (IsEmpty())		// If your list is empty, display a message
    {				//   saying so.
	cout << "\n\nYour list is empty so a grade cannot be deleted.\n\n";
    }
    else if(curr != NULL && curr->grade == delgrade)    // grade is found...
    {
	if(curr->count >= 2)			// and count > 1, 
	    curr->count--;                      //    ... simply dec. count
	else					// Else, you'll need to delete
	{					//    the grade entirely.
	    if(prev == NULL)			// If you're at the beginning
	    {					//    of the list then...
		head = curr->next;		//    change head & delete.
		delete curr;
	    }
	    else				// If you're in the middle or
	    {					//   at the end, assign tmp
		tmp = curr; 			//   and delete curr and
     		tmp = tmp-> next;		//   reconnect to prev.
		delete curr;
	    	prev->next = tmp;
	    }            
	}
    }
    else					// If grade not found
    {						//   display a message.
        cout << "\n\nThis grade cannot be deleted because it does not ";
	cout << "exist in the set.\n\n";
    } 
}

// -------------------------------------------------------------------
// Function to calculate the average of the grades in the list
// -------------------------------------------------------------------
// Accepts:  nothing
// Returns:  the average (0 if list is empty)
// -------------------------------------------------------------------

float GradeList::CalculateAvg()
{
    NodeType* curr = head;   // temp ptr for traversing list

    float sumgrades = 0,     // temp floats for calculating average
	sumcount = 0,
	average = 0;

    // So long as the list is not empty, calculate the average.
    if(!IsEmpty())    
    {	while (curr != NULL)  // while you are still in the list...
    	{
	    sumgrades += curr->grade*curr->count;   // sum the grades
    	    sumcount += curr->count;		// sum the counts
        
            curr = curr->next; 			// move to the next
						//   node.
    	}
	
	average = sumgrades/sumcount;		// calculate the average

	return average;				// return the average
    }

    else			// If your list is empty, display a 
    {				//   message saying so.
	cout << "\n\nYour list is empty, an average could not be ";
	cout << "calculated.\n\n";

	return 0;
    }

}

// -------------------------------------------------------------------
// DropLowestGrade - drops the lowest grade in the list, does nothing
//                   if list is empty
// -------------------------------------------------------------------
// Accepts:  nothing
// Returns:  nothing
// -------------------------------------------------------------------

void GradeList::DropLowestGrade()
{
    NodeType* curr = head;   // temp ptr for traversing list
            
    if(head != NULL)	// So long as the list isn't empty,
    {				//   delete the first.
	if(curr->count > 1)	// If there is more than one of the
	{			//   lowest grade, decrease the count.
	    curr->count--;
	}
	else			// If there's only one of the lowest
	{			//   grade, delete it entirely.
      	    head = curr->next;
            delete curr;
	}
    }
    else			// If the first is empty, display a
    {				//   message saying so.
	cout << "\n\nYou list is empty, so a lowest grade cannot be ";
	cout << "dropped.\n\n";
    }

}
     
// -------------------------------------------------------------------
// HowManyofGrade -  returns how many times this grade is in the list
// -------------------------------------------------------------------
// Accepts:  the grade to look for
// Returns:  the number of times the grade is in the list
// -------------------------------------------------------------------

int GradeList::HowManyofGrade (int grade)
{
    NodeType* curr = head;   // temp ptr for traversing list
            
    while (curr != NULL && curr->grade < grade)  // find desired grade
    {
        curr = curr->next;  
    }
           
    if(IsEmpty())	 	// If your list is empty, display
    {				//   a message saying so.
	cout << "\n\nYour list is empty, so the number of any grade ";
	cout << "cannot be found.\n\n";
	return 0;
    }  
    else if(curr != NULL && curr->grade == grade)    // If grade is found
    {   					     //   return count.
        return curr->count;
    }
    else			// If your grade is not found in the
    {				//   list, display a message saying so.
	cout << "\n\nYour grade was not found in the list.\n\n";
	
	return 0;
    }

}