Microsoft Word - assign6v2.doc CPSC 350: Data Structures Assignment 6, Version 1.2 Building a Database with Binary Search Trees Due: XXXXXXXXXX, 11:59pm. Overview In this assignment, you will push...

1 answer below »
Building a Database with Binary Search Trees


Microsoft Word - assign6v2.doc CPSC 350: Data Structures Assignment 6, Version 1.2 Building a Database with Binary Search Trees Due: 5-3-2021, 11:59pm. Overview In this assignment, you will push your C++ skills to the limit by implementing a simple database system using binary search trees. Though the final product will be a far cry from an Oracle or MySQL system, your DB will allow the user to insert, delete, and query data. The data itself will be persistent (stored on disk), so that you may process it over several sessions. The DB itself will contain data that would be commonly found in a university’s computer system. In our case, this information consists of student and faculty records. The information for each will be stored in its own tree (or “table” in DB terminology). Though I will provide you with a general outline of the program, many of the implementation details will be up to you. In the same spirit, I will give you a point in the right direction as far as some of the C++ techniques go, but it will also be your responsibility to research the techniques in more detail. Details Tables The tables that store the records in your DB will be binary search trees. The nodes will consist of Student or Faculty objects, depending on the tree. The tree will be sorted on the primary key value of the nodes, which in our case will be faculty and student Ids. Your first job will be to build a BST implementation supporting the usual operations (including delete). This should not be difficult in and of itself. Just be sure to use templates to make your implementation generic, and overload operators as required. Student Records Student records will be stored in a Student class. Student records contain a unique student ID (an integer), a String name field, a string level field (Freshman, Sophomore, etc), a String major field, a double GPA field, and an integer advisor field, which will contain the Faculty ID of their advisor. These are the only fields the class contains. The Student class must overload equality, less than, greater than operators, etc. so that we can compare them to one another. Faculty Records Faculty records are similar to student records and will also require overloaded operators. Faculty records contain an integer Faculty ID, a String name, a String level (lecturer, assistant prof, associate prof, etc), a String department, and a list of integers corresponding to all of the faculty member’s advisees’ ids. These are the only fields the class contains. How the Program Should Work Your program will keep references to both the faculty and student tables in memory. These references are simply BSTree instances. For convenience, we will call them masterFaculty and masterStudent. When the program starts, it should check the current directory for the existence of 2 files “facultyTable” and “studentTable”. These files correspond to the BSTrees containing the faculty and student data. If neither of these files exist, then masterFaculty and masterStudent should be initialized as new, empty trees. If the files do exist, then they should be read into the appropriate variables. (See appendix A) Once the tables have been set up, a menu should be presented to the user to allow them to manipulate the databases. At a minimum the choices should include: 1. Print all students and their information (sorted by ascending id #) 2. Print all faculty and their information (sorted by ascending id #) 3. Find and display student information given the students id 4. Find and display faculty information given the faculty id 5. Given a student’s id, print the name and info of their faculty advisor 6. Given a faculty id, print ALL the names and info of his/her advisees. 7. Add a new student 8. Delete a student given the id 9. Add a new faculty member 10. Delete a faculty member given the id. 11. Change a student’s advisor given the student id and the new faculty id. 12. Remove an advisee from a faculty member given the ids 13. Rollback 14. Exit When a command is selected, you should prompt the user for the required data, and execute the command. If there are any errors, you should inform the user describing what the error is and abort the command. All of the above commands should enforce referential integrity. That is to say, a student can not have an advisor that is not in the faculty table. A faculty member can’t have an advisee in the student table. If a faculty member is deleted, then their advisees must have their advisors changed, etc. Your commands will be responsible for maintaining referential integrity. If a user issues a command that would break referential integrity, you should warn them and abort the command, or execute the command and fix any violations as appropriate. After each command is executed, the menu should be displayed again, and the user allowed to continue. The Rollback command is used if the user realizes they have made a mistake in their data processing. The Rollback command will “undo” the previous action, but only if that action changed the structure of the DB. Your program should allow the user to roll back the last 5 commands that CHANGED the DB. (Commands that simply display data do not count.) This will involve keeping snapshots of the DB before and after commands are issued. The implementation details for this are left up to you. If the user chooses to exit, you should write the faculty and student tables back out to the “facultyTable” and “studentTable” files (see appendix A), clean up, and quit gracefully. Programming Strategy At this point you should realize this is a non-trivial assignment. To successfully complete it, you need to make use of your best OO design and programming skills. Think modularly, sketch out a solution before you start coding, and START EARLY. Sleeping is optional, but not recommended. Requirements -You may work in groups of 2 on this assignment. (HIGHLY Recommended) -All code must be your own -Develop on any platform you wish, but make sure it compiles/runs with g++ within your Linux Docker container Grading As usual, you will be graded on correctness, elegance of solution, and your adherence to the above requirements. Style and comments are also important, so be aware that a well- documented, clean solution will receive more credit than a sloppy solution without comments. Due Date Submit the link to your GitHubs repository via the course website on Canvas by 11:59 pm on 5-3-2021. The README should contain your names, student Ids, and any comments you have to make about your solution (special instructions for running, etc). Appendix A: Object Serialization Serialization involves converting objects into a form such that they can be written out to disk. There are two options for doing this with your binary search trees. 1) Design a standard format for each node in the tree. BSTs are then saved by writing out these nodes to a text or binary file. The BSTs can be restored by starting with an empty tree and inserting nodes corresponding to the nodes from the file. 2) Design a format so the entire tree can be read from/written to a file. This is done most efficiently with binary files.
assign6v2-05sorrrj.pdf
Answered 3 days AfterApr 26, 2021

Answer To: Microsoft Word - assign6v2.doc CPSC 350: Data Structures Assignment 6, Version 1.2 Building a...

Pulkit answered on Apr 30 2021
154 Votes
Assignment-5/BST.h
#include "TreeNode.h"
#include "Student.h"
#include "Faculty.h"
using namespace std;
template
class BST
{
private:
TreeNode *root;
int size;
public:
BST()
{
root = NULL;
size = 0;
}
~BST(){};
void insert(TreeNode *node)
{
//TreeNode *node = new TreeNode(data);
// TREE IS EMPTY
if (root == NULL)
{
root = node;
}
else
{
TreeNode *current = root; // STARTING POINT
TreeNode *parent; // FOR KEEPING TRACK OF WHO THE NEW PARENT WILL BE
while (true)
{
parent = current;
// GOING LEFT
if (node->key < current->key)
{
current = current->left;
// FOUND A LEAF
if (current == NULL)
{
parent->left = node;
break;
}
}
// GOING RIGHT
else
{
current = current->right;
// FOUND A LEAF
if (current == NULL)
{
parent->right = node;
break;
}
}
}
}
size++;
 }
bool isInTree(int k)
{
// EMPTY TREE
if (root == NULL)
{
return false;
}
TreeNode *current = root;
// LOOK FOR NODE
while (current->key != k)
{
// GOING LEFT
if (k < current->key)
{
current = current->left;
}
// GOING RIGHT
else
{
current = current->right;
}
// NODE NOT FOUND
if (current == NULL)
{
return false;
}
}
return true;
}
T* search(int k)
{
if (isInTree(k))
{
TreeNode *current = root;
// LOOK FOR NODE
while (current->key != k)
{
// GOING LEFT
if (k < current->key)
{
current = current->left;
}
// GOING RIGHT
else
{
current = current->right;
}
}
return current->data;
}
else
{
return NULL;
}
}
TreeNode* getSuccessor(TreeNode *n)
{
TreeNode *successorParent = n;
TreeNode *successor = n;
TreeNode *current = n->right;
while (current != NULL)
{
successorParent = successor;
successor = current;
current = current->left;
}
if (successor != n->right)
{
successorParent->left = successor->right;
successor->right = n->right;
}
return successor;
}
bool deleteNode(int k)
{
// EMPTY TREE
if (root == NULL)
{
return false;
}
TreeNode *parent = root;
TreeNode *current = root;
bool isLeft = true;
// LOOK FOR NODE TO DELETE
while (current->key != k)
{
parent = current;
// GOING LEFT
if (k < current->key)
{
isLeft = true;
current = current->left;
}
// GOING RIGHT
else
{
isLeft = false;
current = current->right;
}
// NODE NOT FOUND
if (current == NULL)
{
return false;
}
}
// IF WE GET HERE, WE FOUND NODE TO BE DELETED;
// NOW WE CHECK OUR CASES
// NO CHILDREN
if (current->left == NULL && current->right == NULL)
{
// DELETING THE ROOT
if (current == root)
{
root = NULL;
}
else if (isLeft)
{
parent->left = NULL;
}
else
{
parent->right = NULL;
}
}
// ONE CHILD, LEFT CHILD
else if (current->right == NULL)
{
if (current == root)
{
root = current->left;
}
else if (isLeft)
{
parent->left = current->left;
}
else
{
parent->right = current->left;
}
}
// ONE CHILD, RIGHT CHILD
else if (current->right == NULL)
{
if (current == root)
{
root = current->right;
}
else if (isLeft)
{
parent->left = current->right;
}
else
{
parent->right = current->right;
}
}
// TWO CHILDREN
else
{
TreeNode *successor = getSuccessor(current);
if (current == root)
{
root = successor;
}
else if (isLeft)
{
parent->left = successor;
}
else
{
parent->right = successor;
}
// LINK SUCCESSOR TO CURRENT'S LEFT CHILD
successor->left = current->left;
}
size--;
return true;
}
void print(TreeNode *node)
{
if (node == NULL)
{
return;
}
print(node->left);
cout << node->data << " | ";
print(node->right);
}
void printTree()
{
print(root);
}
TreeNode* getRoot()
{
return root;
}
int getSize()
{
return size;
}
bool isEmpty()
{
return (size == 0);
}
};
Assignment-5/DLL.h
#include
#include "ListNode.h"
using namespace std;
template
class DLL
{
    public:
        ListNode *front;
        ListNode *back;
        unsigned int size;
        DLL()
        {
            size = 0;
            front = NULL;
            back = NULL;
        }
        ~DLL()
        {
            delete front;
            delete back;
        }
        void insertBack(T d)
        {
            ListNode *node = new ListNode(d);
            // IF LIST IS EMPTY
            if (size == 0)
            {
                front = node;
            }
            else
            {
                back->next = node;
                node->prev = back;
            }
            back = node;
            ++size;
        }
        T removeFront()
        {
         if (!isEmpty())
         {
                ListNode *oldFront = front;
             T oldData = oldFront->data;
             // IF THERE IS ONLY ONE ELEMENT
                if (front->next == NULL)
                {
             front = NULL;
             back = NULL;
                }
             // MORE THAN ONE ELEMENT
                else
                {
                    front->next->prev = NULL;
             front = front->next;
                }
                delete oldFront;
                size--;
                return oldData;
         }
            else
            {
                return T();
            }
        }
        void removeAt(int pos)
        {
            int index = 0;
            ListNode *current = front;
            ListNode *previous = front;
            while (index != pos)
            {
                previous = current;
                current = current->next;
                ++index;
            }
            // WE FOUND WHAT NEEDS TO BE DELETED
            previous->next = current->next;
            current->next->prev = previous;
            current->next = NULL;
            current->prev = NULL;
            size--;
            delete current;
        }
        T getFront()
        {
            return front->data;
        }
        void printList()
        {
            if (front != NULL)
            {
                ListNode *current = front;
                while (true)
                {
                    if (current == NULL)
                    {
                        break;
                    }
                    cout << current->data << ", ";
                    current = current->next;
                }
            }
            else
            {
                cout << "None";
            }
        }
        unsigned int getSize()
        {
            return size;
        }
bool isEmpty()
        {
         return (size == 0);
        }
};
Assignment-5/Faculty.cpp
#include "Faculty.h"
using namespace std;
Faculty::Faculty(){};
Faculty::Faculty(int i, string n, string l, string d)
{
id = i;
name = n;
level = l;
department = d;
adviseeIDArray = new int[4];
numAdvisees = 0;
maxArraySize = 4;
for (int i = 0; i < 4; ++i)
{
adviseeIDArray[i] = -1;
}
}
Faculty::~Faculty()
{
delete [] adviseeIDArray;
};
void Faculty::printFaculty()
{
cout << "Faculty ID: " << id << " | Name: " << name << " | Level: " << level << " | Dept: " << department << "\nAdvisee IDs: ";
printAdvisees();
cout << endl;
}
void Faculty::printAdvisees()
{
if (numAdvisees == 0)
{
cout << "No Advisees";
}
// GO THROUGH ADVISEE LIST AND PRINT ID OF ALL
else
{
for (int i = 0; i < maxArraySize; ++i)
{
if (adviseeIDArray[i] != -1)
{
cout << adviseeIDArray[i];
if (i < numAdvisees - 1)
{
cout << ", ";
}
}
}
}
cout << endl;
}
void Faculty::addAdvisee(int aid)
{
// IF ARRAY IS FULL, DOUBLE IN SIZE AND ADD ADVISEE
if (numAdvisees == maxArraySize)
{
        int *temp1 = new int[numAdvisees];
// MAKE TEMP ARRAY OF SAME SIZE AS CURRENT ARRAY
        for (int i = 0; i < numAdvisees; ++i)
        {
            temp1[i] = adviseeIDArray[i];
        }
// DOUBLES SIZE OF ARRAY
        adviseeIDArray = new int[numAdvisees * 2];
maxArraySize = numAdvisees * 2;
// REPOPULATE FIRST HALF WITH OLD VALUES
        for (int i = 0; i < numAdvisees; ++i)
        {
            adviseeIDArray[i] = temp1[i];
        }
// POPULATE SECOND HALF WITH 'OPEN' STATUS
for (int i = numAdvisees; i < numAdvisees * 2; ++i)
{
adviseeIDArray[i] = -1;
}
adviseeIDArray[++numAdvisees] = aid;
    }
// IF ARRAY NOT FULL, ADD ADVISEE IN FIRST OPEN POSITION
else
{
int f = 0;
// CHECK IF STUDENT IS ALREADY BEING ADVISED BY THIS FACULTY MEMBER
for (int i = 0; i < maxArraySize; ++i)
{
if (adviseeIDArray[i] == aid)
{
f = maxArraySize;
}
}
// IF NOT, ADD THEM
while (f < maxArraySize)
{
if (adviseeIDArray[f] == -1)
{
adviseeIDArray[f] = aid;
++numAdvisees;
break;
}
++f;
}
}
}
bool Faculty::removeAdvisee(int adviseeID)
{
bool deleted = false;
// GO THROUGH ADVISEE LIST; IF FOUND DELETE
for (int i = 0; i < maxArraySize; ++i)
{
if (adviseeIDArray[i] == adviseeID)
{
adviseeIDArray[i] = -1;
--numAdvisees;
deleted = true;
}
}
if (!deleted)
{
cout << "\nAdvisee not found." << endl;
}
return deleted;
}
int Faculty::getMaxArraySize()
{
return maxArraySize;
}
string Faculty::getDepartment()
{
return department;
}
int Faculty::getNumAdvisees()
{
return numAdvisees;
}
Assignment-5/Faculty.h
#include
#include
#include "DLL.h"
#include "Person.h"
using namespace std;
class Faculty : public Person
{
public:
string department;
unsigned int numAdvisees;
unsigned int maxArraySize;
int *adviseeIDArray;
Faculty();
Faculty(int i, string n, string l, string d);
~Faculty();
void printFaculty();
void printAdvisees();
void addAdvisee(int aid);
bool removeAdvisee(int adviseeID);
int getMaxArraySize();
string getDepartment();
int getNumAdvisees();
};
Assignment-5/facultyTable.txt
2
--
4321
Rene German
Professor
CPSC
2
1234
5678
--
765
Stacy
Dr
Business
1
12345
Assignment-5/GenStack.h
/* Generic Stack Class */
template
class GenStack
{
    public:
        GenStack();
        GenStack(int maxSize);
        ~GenStack();
        void push(T data);
        T pop();
        T peek();
        int isFull();
        int isEmpty();
        int top;
        int max;
        T *myArray;
};
template
GenStack::GenStack(){};
template
GenStack::GenStack(int maxSize)
{
    myArray = new T[maxSize];
    max = maxSize;
    top = -1;
}
template
GenStack::~GenStack()
{
    delete myArray;
}
template
void GenStack::push(T data)
{
    // IF FULL, DOUBLE SIZE
    if (top == max - 1)
    {
        T *temp1 = new T[max];
        for (int i = 0; i < max; ++i)
        {
            temp1[i] = myArray[i];
        }
        myArray = new T[max * 2];
        for (int i = 0; i < max; ++i)
        {
            myArray[i] = temp1[i];
        }
        max *= 2;
    }
    myArray[++top] = data;
}
template
T GenStack::pop()
{
    if (top != -1)
    {
        return myArray[top--];
    }
    else
    {
        return 0;
    }
}
template
T GenStack::peek()
{
    return myArray[top];
}
template
int GenStack::isFull()
{
    return (top == max-1);
}
template
int GenStack::isEmpty()
{
    return (top == -1);
}
Assignment-5/ListNode.h
#include
using namespace std;
template
class ListNode
{
    public:
        T data;
ListNode *next;
ListNode *prev;
        ListNode(){};
        ListNode(T d)
        {
            data = d;
            next = NULL;
            prev = NULL;
        }
        ~ListNode()
        {
            if (next != NULL)
            {
                next = NULL;
                prev = NULL;
                delete next;
                delete prev;
            }
        }
};
Assignment-5/main.cpp
#include "Processor.h"
using namespace std;
int main (int argc, char** argv)
{
Processor p1;
Menu menu;
p1.readFromFile();
menu.welcome();
p1.run();
p1.writeToFile();
return 0;
}
Assignment-5/Makefile
#this Makefile goes in the src directory
#change this to the correct assignment #
EXECUTABLE := assignment5
# the source files to be built
SOURCES := *.cpp
#stuff you don't need to worry about
INCLUDES := -I ../include
EXT := out
CC := g++
all:
    $(CC) $(INCLUDES) $(SOURCES) -o $(EXECUTABLE).$(EXT)
realclean:
    find . -type f -name "*.o" -exec rm '{}' \;
    find . -type f -name “*.out” -exec rm '{}' \;
# this line required by make - don't delete
Assignment-5/Menu.cpp
#include "Menu.h"
using namespace std;
Menu::Menu(){};
Menu::~Menu(){};
void Menu::welcome()
{
cout << "\nStudent & Faculty Records Database\n----------------------------------\n";
displayMenu();
}
void Menu::displayMenu()
{
cout << "\n1. Print all students and their information" << endl;
cout << "2. Print all faculty and their information" << endl;
cout << "3. Find and display student information" << endl;
cout << "4. Find and display faculty information" << endl;
cout << "5. Get faculty advisor of student" << endl;
cout << "6. Get advisees of a faculty member" << endl;
cout << "7. Add a new student" << endl;
cout << "8. Delete a student" << endl;
cout << "9. Add a new faculty member" << endl;
cout << "10. Delete a faculty member" << endl;
cout << "11. Change a student’s advisor" << endl;
cout << "12. Remove an advisee from a faculty member" << endl;
cout << "13. Rollback" << endl;
cout << "14. Exit" <<...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Have files?