#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

struct student 
{ 
    string first_name;
    string last_name;
    int SSN;
    double GPA;
    student *next; 
};


void print_student(student a_student)
{
    cout << a_student.last_name << ", ";
    cout << a_student.first_name << "  SSN:";
    cout << setw(10) << a_student.SSN << endl;
}


void print_class(student * a_class)
{
    if (a_class == NULL) return;
    print_student(*a_class);
    print_class(a_class->next);
}


student * find(student * a_class, int SSN)
{
    if (a_class == NULL) return NULL;
    if (a_class->SSN == SSN) return a_class;
    return find(a_class->next, SSN);
}


student * add_head(student * a_class, student a_student)
{
    student * new_student;
    new_student = new student;
    *new_student = a_student;
    new_student->next = a_class;
    return new_student;
}


void attach(student * a_class, student a_student)
{
    if (a_class == NULL) return;
    student * new_student;
    new_student = new student;
    *new_student = a_student;
    
    while (a_class->next != NULL)
        a_class = a_class->next;
    a_class->next = new_student;    
}





student * insert(student * a_class, student a_student)
{
    student * new_student;
    new_student = new student;
    *new_student = a_student;
    if (a_class == NULL) return new_student;
    if (a_class->SSN >= new_student->SSN) 
    {
        new_student->next = a_class;
        return new_student;
    }
    else
    {
        delete new_student;  // Don't forget this;
        a_class->next = insert(a_class->next, a_student);
    }
    return a_class; 
}


student * remove(student * a_class, int SSN)
{
    if (a_class == NULL) return NULL;
    student *next;
    if (a_class->SSN == SSN) 
    {
        next = a_class->next;
        delete a_class; // Don't forget this;
        return next;
    }
    a_class->next = remove(a_class->next, SSN);
    return a_class; 
}


student * nonrec_remove(student * a_class, int SSN)
{
    if (a_class == NULL) return NULL;
    student *pre, *current, *next;
    pre = current = a_class;
    if (current->SSN == SSN) 
    {
        next = current->next;
        delete current; // Don't forget this;
        return next;
    }
    else
        current = current->next;
    while (current != NULL)
    {
        if (current->SSN == SSN)
        {
            pre->next = current->next;
            delete current;
            return a_class;
        }
        pre = current;
        current = current->next;
    }
    return a_class; 
}




void main()
{
    int i;
    student s;
    student *c1=NULL, *c2=NULL, *c3=NULL;

    for (i=0; i<15; i++)
    {
        s.SSN = 100000000+(rand()%100000*1000)+i;
        s.last_name = "Lastname";
        s.first_name = "Firstname";
        c1 = add_head(c1,s);
    }
    cout << "Class 1:\n";
    print_class(c1);

    c2 = new student;
    c2->first_name=c2->last_name="Head";
    c2->SSN = 100000000+(rand()%100000*1000)+0;
    c2->next = NULL;  // Be aware of this;
    s.next = NULL; // Be aware of this
    for (i=1; i<15; i++)
    {
        s.SSN = 100000000+(rand()%100000*1000)+i;
        s.last_name = "Lastname";
        s.first_name = "Firstname";
        attach(c2,s);
    }
    cout << "\n\nClass 2:\n";
    print_class(c2);
 
    for (i=0; i<15; i++)
    {
        s.SSN = 100000000+(rand()%100000*1000)+i;
        s.last_name = "Lastname";
        s.first_name = "Firstname";
        c3 = insert(c3,s);
    }
    cout << "\n\nClass 3:\n";
    print_class(c3);

    while (true)
    {
        cout << "\nInput a SSN to remove:";
        cin >> i;
        if (i==0) break;
        c3 = nonrec_remove(c3,i);
        cout << "\n\nClass 3:\n";
        print_class(c3);
    }
}