//
// File: gradelnklist.cpp
// Grade Link List - a form of listing grades, adding grades, deleting grades,
// counting grades, and averaging grades 
// September 2008 
// CS 311
// Justin McCreary
// Professor: Mrs. Ames
// Implementation file for ordered grade list in an array
//
// Contents: C++ source code for dynamic memory
// allocation implementation of a list of grades.  Each node in the 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())
       cout << "\nThere are no grades\n\n"; //displays if gradelist is empty
   else
   {   //Displays the list of grades and occurence count for that grade
       cout << "\nGrades    Num of Each \n\n";
       while (tmp != NULL)
       {
          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 replace a node
    
   if( !IsEmpty())
   {
      while (curr != NULL && curr->grade < delgrade)  // find place to insert
      {
         prev = curr;
         curr = curr->next; 
      }

      if (curr != NULL && curr->grade == delgrade)    // grade already here ...
        curr->count--;                                // ... simply dec. count
      if (curr -> count == 0)
      {
	if ( prev == NULL ) //delete at the beginning
	{
		head = curr -> next;
		delete curr;
	}
	else //delete in middle or at end
	{
		tmp = curr -> next;
		delete curr;
		prev -> next = tmp;
	}
      }
   }
}

// -------------------------------------------------------------------
// 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; //for sum of grades
  float avg = 0; //for average
  float countgrades = 0; //for number of grades

  if (!IsEmpty())
  {	
	  while (curr != NULL)
	  {     //sums up grades
		sumgrades = sumgrades + (curr -> grade * curr -> count);
		//counts the num of grades in total
		countgrades = countgrades + curr -> count;
		curr = curr -> next;
	  }	
	  avg = sumgrades/countgrades; //calculates average
  }
	
  return (avg); //returns average
}

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

void GradeList::DropLowestGrade()
{
   NodeType* tmp; //temp ptr for replacing a node 

   if(!IsEmpty())
   {
  	tmp = head;
  
  	tmp -> count--; //reduces occurence by one
	
        if (tmp -> count == 0) // if count now equals zero...
  	{		       // ...closes spot on the list 
  	  tmp = tmp -> next;
	  delete head;
	  head = tmp;
  	} 
   }
}
     
// -------------------------------------------------------------------
// 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
  
  int occur = 0;

  if(!IsEmpty())
  {	//keep  looking until proper grade is found
	while(curr != NULL && curr -> grade < grade)
	{
		curr = curr -> next;
	}
	if ( curr -> grade == grade )
		occur = curr -> count; //receives num of occurrences
  }

  return (occur); //returns num of occurrences
}