In C++, this project is to develop a simple database system. The database is to handle multiple records, each composed of several fields. The database will store its information to a file, addition and deletion of records, field modifications, and it will allow users to sort records based on the selected keys, and produce reports (output) according to predefined criteria.

Some definitions:

A database is a collection of information, or data, that you can organize, update, sort, search through, and print as needed. A database does not just hold information; you use a database to organize and analyze information so that you understand its significance.

A database file consists of one or more records. Each record holds all the information about one subject item. In C++, the class data type provides an efficient way to represent and manipulate records.

Each piece of information in a record is called a field. Fields store the data that has been entered or calculated. In C++ parlance, fields are nothing more than the member variables defined for a particular class.

Given the requirements as a rough specification, you are to design the class and implement the database. So you can consider the requirements below as an outcome from a meeting with a client. You are in full control of the choice of data structures (except the main data structure of a Binary Search Tree, more detail below), algorithms, internal file format, and detailed user interface scheme.

You're designing and implementing a database for an address book. Users should be able to browse, search their contacts, by any field (last name, first name, zip code etc.) from the database, and organize their chosen contacts to their liking and print out a report. Each contact information includes followings:

Unique ID number. ID is a 9 digit number (assume person has an ID generated from another system)

First name

Middle name (or initial)

Last name

Company name

Home phone

Office phone

Email

Mobile number

Street address

City

State

Zip code

Country

List of affiliates (such as family members or associates name). Each affiliate has first name, and last name. They may have one individual mobile phone number and one email. This database will not track any other information about affiliates. The total number of affiliates is unknown.

Requirements

Database overall management

Use a text based menu for users to choose available features. Program should have a main menu at the beginning and sub menus depending on the task.

You should allow users to read and write data to a text-based database file. The format of the text-based database file is following:

All information is stored in ASCII text format.

Records are divided by a | character

Each field is distinguished by a new line.

When reading from a data file, your program must test the input file to ensure that data is of valid format (basic error detection).

The database is primarily organized with the ID# as a key. You must use the provided Binary Search Tree (from HW8) for the base data structure. You will have to modify this code to ensure that you have a Binary Search Tree of Nodes, that is sorted by ID. You may have additional Binary Search Trees if that fits into your design. While you can modify the given files, do not use some "other" Binary Search trees that you might find in the book or the internet, since we won't be able to help you if things go wrong (and they will!)

Each component of the overall program should be fairly modular.

Each menu item, for example, should be a separate function. The menu feature should be handled by a separate function and not by main( ).

Program should be fairly fault tolerant of user input (both when the user is entering data, and making menu choices). Provide appropriate user prompts and on-screen directions

Split the program into multiple files based on the roughly categorized functionality.

Data Retrieval and Modification

Users should be able to search records based on the field information in two modes: exact and contains. For example, search contacts by last name "Smith", search contacts with an email domain name that contains "ucdenver", etc. So in the search sub menu, users have to pick the search mode and field. Of course users should type in the search item.

Quite often, searches may generate a relatively big output. Users should be able to search again within the search result (secondary search) or start all over again from scratch (new search).

Since the entire data is structures in a Binary Search Tree tree with the ID# key, any search (except using ID#) should traverse the entire tree.

Users should be able to delete a record. So, in the delete record sub menu, users should be able to search and pick a delete candidate record. After deletion, the Binary Search Tree should follow all Binary Search Tree properties (with regard to sorting order, tree levels etc).

Users should be able to modify fields in a record, with the same condition above.

Users should be able to insert new records. There should be no restriction to the number of records in the database. So, in other words, you should not consider a fixed array for the record data structure.

Users can modify records, so the user should be able to write back to file (overwrite to current file or to a new file name similar to "save as").

Output Generation

Output generation is responsible for the re-organizing the final result to a user's liking by displaying appropriate fields and sorted records. The final output is a report in ASCII-text format.

After a series of data retrieval and modification, finally there is a list of contacts to be an output. Users should be able to further organize the contact and convey them to the output by choosing only the fields they want to print in desired order. So users should be able to pick fields to be finally shown in the output. And users should be able to sort the final output contacts by selecting a field as a key.

Users should be able to perform a secondary sorting with the second sort key (e.g., sort by company name, and then last name).

Output file generation in text file format.

Users should be able to generate a report output in ASCII text format. Note that this output file is different from the database file in ASCII text format.

Keep in mind that an output may not include all fields and records.

Submission Guideline

You need to submit following items (all zipped together):

Source code with reasonable comments

Makefile that works (and is tested) on the csegrid.

A final report that includes:

Summary of provided functions. This should be matched with the requirements

Design document that shows the overall program structures, and the explanation of key algorithms. A description of user interface scheme is required to explain the menu items at top level and items in sub menus and how to navigate through menus. A detailed instruction and sample skeleton is available from Design Document.

Accurate status of the program, what's done, and what's not completely implemented.

Accurate status of testing on the csegrid.

The final report should be in MS Word, or PDF format.

Note: You may use the following Binary Search Tree code. You may not use every function associated with this code and you may need to change it to fit this assignment. Any and all changes should be fully documented. Node.h, BSTree.h, BSTree.cpp Your program should work to this small file, and may but does not have to work with the large database file. databasesmall.txt, databaselarge.txt

Grading Criteria

Submitting a working program that provides all of the required features will result in a maximum grade of 80%.

Documentation explained above will result in 20% of the grade.

Any or all of the following will result in point deductions of up to 5% for each infraction.Poor and/or inconsistent programming style. This includes the following:

Improper use of indentation.

Overuse of global variables.

Failure to keep functions modular and reusable (possibly applicable to other programs).

Insufficient comments.

Insufficient menu prompts

Program is not reasonably( not absolutely) fault tolerant.

Test to ensure that your program cannot be crashed or sent into an infinite loop by a user who is not following directions.

Include a reasonable input file integrity check. Rejecting any non-conforming file is fine. You need to provide a sample database file with at least 50 records.

Partial credit may be awarded.

You may get partial credit for non-working modules (functions) by explaining (in the separate document) where you think the problem lies.

Up to 10% could be lost for each required feature that is not provided.

Given File:Node.h

#ifndef NODE_

#define NODE_

#include

using namespace std;

// A generic tree node class

//Placeholder for a composite data type

class Datatype{

private:

int number;

};

//Binary Tree Node

class Node {

private:

int key;

Datatype data;

Node* left;

Node* right;

Node* parent;

public:

Node() { key=-1; left=nullptr; right=nullptr; parent = nullptr;};

void setKey(int aKey) { key = aKey; };

void setLeft(Node* aLeft) { left = aLeft; };

void setRight(Node* aRight) { right = aRight; };

void setParent(Node* aParent) { parent = aParent; };

int Key() { return key; };

Node* Left() { return left; };

Node* Right() { return right; };

Node* Parent() { return parent; };

};

#endif

Given File: BSTree.h

#ifndef BSTREE_

#define BSTREE_

#include

using namespace std;

#include "Node.h"

// Binary Search Tree class

class BSTree {

private:

Node* root;

void addNode(int key, Node* leaf);

Node* deleteNode(Node* node, int key);

void freeNode(Node* leaf);

public:

BSTree();

~BSTree();

Node* Root() { return root; }

void setRoot(Node * _root) {root = _root;}

void addNode(int key);

Node* findNode(int key, Node* parent);

void printPreorder(Node* node);

void printInorder(Node* node);

void printPostorder(Node* node);

void deleteNode(int key);

Node* min(Node* node);

Node* max(Node* node);

Node* successor(int key, Node* parent);

Node* predecessor(int key, Node* parent);

};

#endif //BST

Given File BSTree.cpp

#include "BSTree.h"

// Constructor

BSTree::BSTree() {

root = nullptr;

}

// Destructor

BSTree::~BSTree() {

if (root !=nullptr)

freeNode(root);

}

// Free the node

void BSTree::freeNode(Node* leaf)

{

if ( this->Root() == leaf)

{

}

else if ( leaf != nullptr )

{

freeNode(leaf->Left());

freeNode(leaf->Right());

delete leaf;

}

}

// Add a node

void BSTree::addNode(int key)

{

// No elements. Add the root

if ( root == nullptr ) {

Node* n = new Node();

n->setKey(key);

root = n;

}

else {

addNode(key, root);

}

}

// Add a node (private)

void BSTree::addNode(int key, Node* leaf) {

if ( key Key() )

{

if ( leaf->Left() != nullptr )

addNode(key, leaf->Left());

else {

Node* n = new Node();

n->setKey(key);

n->setParent(leaf);

leaf->setLeft(n);

}

}

else

{

if ( leaf->Right() != nullptr )

addNode(key, leaf->Right());

else {

Node* n = new Node();

n->setKey(key);

n->setParent(leaf);

leaf->setRight(n);

}

}

}

// Find a node

Node* BSTree::findNode(int key, Node* node)

{

}

// Print the BSTree

void BSTree::printPreorder(Node* node)

{

}

void BSTree::printInorder(Node* node)

{

}

void BSTree::printPostorder(Node* node)

{

if ( node != nullptr)

{

}

}

// Find the node with min key

// Traverse the left sub-BSTree recursively

// till left sub-BSTree is empty to get min

Node* BSTree::min(Node* node)

{

Node* tempNode = node;

if ( node == nullptr )

tempNode = nullptr;

else if ( node->Left() )

{

tempNode = min(node->Left());

}

else

tempNode = node;

return tempNode;

}

// Find the node with max key

// Traverse the right sub-BSTree recursively

// till right sub-BSTree is empty to get max

Node* BSTree::max(Node* node)

{

Node * tempNode = node;

if ( node == nullptr )

tempNode = nullptr;

else if ( node->Right() )

tempNode = max(node->Right());

else

tempNode = node;

return tempNode;

}

// Find successor to a node

// Find the node, get the node with max value

// for the right sub-BSTree to get the successor

Node* BSTree::successor(int key, Node *node)

{

Node *successor = nullptr;

Node *current = root;

if(root == nullptr)

return NULL;

while(current->Key() != key){

/* If node value is greater than the node which are looking for, then go to left sub tree

Also when we move left, update the successor pointer to keep track of lst left turn */

if(current->Key() >key){

successor = current;

current= current->Left();

}

/* Else take right turn and no need to update successor pointer */

else

current = current->Right();

}

/*Once we reached at the node for which inorder successor is to be found, check if it has right sub tree, if yes then find the minimum in that right sub tree and return that node

Else last left turn taken node is already stored in successor pointer and will be returned*/

if(current && current->Right()){

successor = min(current->Right());

}

return successor;

}

// Find predecessor to a node

// Find the node, get the node with max value

// for the left sub-BSTree to get the predecessor

Node* BSTree::predecessor(int key, Node *node)

{

Node* current = findNode(key, node);

if (current == nullptr)

{ return nullptr; }

if (current->Left() !=nullptr)

{

return max(current->Left());

} else

{

Node *tempParent = current->Parent();

while (tempParent !=nullptr) {

if (current == tempParent->Right() ){

break;

}

current = tempParent;

tempParent = current->Parent();

}

return tempParent;

}

}

void BSTree::deleteNode(int key)

{

if (deleteNode(Root(), key) == nullptr)

setRoot(nullptr);

}

//deleteNode (Private)

Node* BSTree::deleteNode(Node* root,int key)

{

/* Given a binary search tree and a key, this function deletes the key

and returns the new root */

if(root == nullptr) return root;

else if(key Key())

root->setLeft( deleteNode(root->Left(),key));

else if(key > root->Key())

root->setRight( deleteNode(root->Right(), key) );

else {

// Case 1: No Child

if(root->Left() == nullptr && root->Right() == nullptr){

delete root;

root = nullptr;

// Case 2: one child

} else if(root->Left() == nullptr){

Node *temp = root;

root = root->Right();

delete temp;

} else if(root->Right() == nullptr){

Node *temp = root;

root = root->Left();

delete temp;

} else{

Node *temp = min(root->Right());

root->setKey(temp->Key() );

root->setRight( deleteNode(root->Right(), temp->Key() ) );

}

}

return root;

}

I can put in the given data.txt files, I just need help for the rest of it. Thank you.