lab5.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Student {
public:
    string fName_, sName_;
    int id_, grade_;

    Student(string fName, string sName, int id, int grade){
        fName_ = fName;
        sName_ = sName;
        id_ = id;
        grade_ = grade;
    }

    int Compare(string fName, string sName){
        // tiebreak on second names first, but if they're equal consider first names.
        int comp = sName_.compare(sName);

        if (comp != 0) return comp;
        return fName_.compare(fName);
    }

    int Compare(Student *s2){
        return Compare(s2->fName_, s2->sName_);
    }

    void Print(){
        cout << "Name: " << sName_ << ", " << fName_ << endl <<
                "ID: " << id_ << endl <<
                "Final Grade: " << grade_ << endl <<
                "-----" << endl;
    }
};

class LLNode {
public:
    Student *data;
    LLNode *next;
    LLNode(Student *st) { 
        data = st;
        next = NULL;
    }
};

class LinkedList {
private:
    LLNode *head_;
    LLNode *tail_;
public:
    LinkedList() {
        head_ = tail_ = NULL;
    }

    void Add(Student *st){
        LLNode *node = new LLNode(st);

        // first node in list
        if (!head_) {
            head_ = tail_ = node;
            return;
        }

        LLNode *ptr = head_;
        LLNode *prev = NULL;

        while(ptr && st->Compare(ptr->data) >= 0) {
            prev = ptr;
            ptr = ptr->next;
        }

        // first node
        if (!prev) {
            node->next = head_;
            head_ = node;
            return;
        }
        // if it's the last node, update tail var.
        if (!ptr) tail_ = node;

        // insert at this loc.
        node->next = prev->next;
        prev->next = node;
    }

    Student* FindStudent(string fName, string lName){
        LLNode *ptr = head_;
        int c = 0;

        while (ptr){
            c++;
            int comp = ptr->data->Compare(fName, lName);
            if (comp == 0){
                break;
            }
            else if (comp > 0) {
                ptr = NULL;
                break;
            }

            ptr = ptr->next;
        }

        cout << "Number of comparisons made: " << c << endl;
        if (ptr) {
            cout << "Student found..." << endl;
            ptr->data->Print();
            return ptr->data;
        }
        else {
            cout << "No matching student found." << endl;
            return NULL;
        }

    }
    void Print(){
        LLNode *ptr = head_;
        while (ptr){
            ptr->data->Print();
            ptr = ptr->next;
        }
    }
};

class TreeNode {
private:
    Student *FindStudent(string fName, string lName, int i){

        int comp = data_->Compare(fName, lName);
        if (comp == 0) {
            // print stuff..
            cout << "Number of comparisons made: " << i << endl;
            cout << "Student found..." << endl;
            data_->Print();
            return data_;
        }

        TreeNode *t = (comp > 0 ? left_ : right_);
        if (t)
            return t->FindStudent(fName, lName, i+1);
        else {
            cout << "Number of comparisons made: " << i << endl;
            cout << "Student not in tree." << endl;
        }
    }
public:
    Student *data_;
    TreeNode *left_;
    TreeNode *right_;

    TreeNode(Student *stu){
        data_ = stu;
    }

    void Add(Student *stu){
        TreeNode **ptr = (data_->Compare(stu) > 0) ? &left_ : &right_;

        if (*ptr) (*ptr)->Add(stu);
        else *ptr = new TreeNode(stu);
    }

    Student *FindStudent(string fName, string lName){
        return FindStudent(fName, lName, 0);
    }
};


int main(){
    int NUM_STU = 10000;
    vector<Student*> students;

    string fName, lName;
    int id, grade;

    for (int i = 0; i < NUM_STU; i++){
        cin >> lName >> fName >> id >> grade;
        students.push_back(new Student(fName, lName, id, grade));
    }

    cout << endl;
    cout << "---------- LINKED LIST RESULTS ----------" << endl;

    LinkedList *s_ll = new LinkedList();
    for (Student* s : students){
        s_ll->Add(s);
    }

    s_ll->FindStudent("Abraham", "CRONIN");
    s_ll->FindStudent("Collin", "BREE");
    s_ll->FindStudent("Etienne", "HOLOHAN");
    s_ll->FindStudent("", "AAAA");
    s_ll->FindStudent("", "ZZZZ");

    cout << endl;
    cout << "---------- BINARY TREE RESULTS ----------" << endl;

    TreeNode *s_bst = new TreeNode(students[0]);
    for (int i = 1; i < NUM_STU; i++){
        s_bst->Add(students[i]);
    }

    s_bst->FindStudent("Abraham", "CRONIN");
    s_bst->FindStudent("Collin", "BREE");
    s_bst->FindStudent("Etienne", "HOLOHAN");
    s_bst->FindStudent("", "AAAA");
    s_bst->FindStudent("", "ZZZZ");

    cout << endl;
}