C++ Assignment, Please help me break the following program into class. Also, ple
ID: 3847262 • Letter: C
Question
C++ Assignment, Please help me break the following program into class. Also, please post the output
Write a program for a police department that has collected a database of information on various suspects for a given crime. (Luckily for you, the department is only investigating one crime at a time.) Each suspect has a set of attributes, such as shifty eyes, a limp, or a parrot on his shoulder. The maximum number of such attributes for any suspect is not known. Your program accepts commands to manipulate the database in order to narrow down the list of suspects, in the hope of pinpointing the villain.
Input
The retained criminal information, generated by the previous execution of this program, is input from file "Criminal.mf" at the beginning of each execution of the program.
The user inputs commands from the keyboard, in the format shown below. Names and attributes are strings of no more than 20 characters. The program should not be case sensitive (e.g., 'JOE' and 'Joe' are the same name). To simplify the processing, you can assume that names are unique; that is, no two criminals use the same professional handle. The commands are discussed in detail in the Command Processing instructions below.
Output
Responses to user commands are to be written to the screen, as described in the Command Processing instructions below.
Echo print each command and show the results of any PRINT commands in a file called "Criminal.trn". You may determine the format of the information in this file; it should be labeled and formatted clearly. A hard copy of this file is turned in with your program for grading.
If any new suspects were added (see ADD command), file "Criminal.mf" must be rewritten to contain the updated collection of criminal information.
Command Processing
New suspects can be added to the collection of criminal information using the ADD command. An inquiry consists of a set of commands with respect to a single crime, at the end of which the crime is assumed to be solved. An inquiry must be completed within the execution of the program; it cannot be "saved" to finish on a subsequent execution. After an inquiry is complete, a new inquiry (the investigation of another crime) can begin. Each new inquiry starts over with the entire collection of suspects.
Command
Processing
ADD
Add a suspect to the Suspects data structure. Prompt the user for the suspect's name and a list of attributes. ADD commands can be issued only before an inquiry begins.
INQUIRY
Prompt user for code name of this inquiry. Once the inquiry has begun, do not allow the user to issue the ADD command until this inquiry is complete.
TIP
Prompt user for the tip information (a particular attribute). Process the tip, reducing the set of current suspects by deleting suspects who do not match the attribute mentioned in the tip. If there is only one suspect left in the set of active suspects, print out a message indicating that the crime is solved. Be sure to include the suspect's name and inquiry code name. This terminates the current inquiry.
CHECK
Prompt the user for a suspect's name. Check the set of active suspects to see if this name is there; print out an appropriate response.
Print the set of active suspects (those who have not yet been eliminated).
QUIT
If any new suspects have been added during this execution of the program, rewrite the "Criminal.mf" file. Be careful about how you go about saving the records; the traversal order affects the shape of the tree that is built on the next execution of the program. Terminate the program.
Sample Input
(Some of the labels shown in the sample input are not typed in by the user, but are only printed for clarity. For this example, the "Criminal.mf" file is empty and all the potential suspects are added by command.)
ADD Name: Quickdraw McGraw
Attributes: has a Texas accent
has a body guard
is computer literate
ADD Name: Twingun Morgan
Attributes: has a New York accent
has red hair
smokes cigars
ADD Name: Jackda Ripper
Attributes: has a body guard
bites his fingernails
carries a knife
is computer literate
ADD Name: Annie Getcher Gunn
Attributes: has a New York accent
has red hair
eats Fritos
smokes cigars
ADD Name: Slowdrawl Raul
Attributes: has a Texas accent
carries a knife
is computer literate
eats Fritos
ADD Name: Sloan de Uptake
Attributes: has a body guard
has red hair
bites his fingernails
is computer literate
INQUIRY Code Name: Bang Bang
TIP Tip Info: has a New York accent
CHECK Quickdraw McGraw
TIP Tip Info: has red hair
CHECK Annie Getcher Gunn
TIP Tip Info: eats Fritos
INQUIRY Code Name: Holdup
TIP Tip Info: has a Texas accent
CHECK Slowdrawl Raul
CHECK Sloan de Uptake
TIP Tip Info: is computer literate
INQUIRY Code Name: Tough Stuff
TIP Tip Info: bites his fingernails
CHECK Twingun Morgan
TIP Tip Info: has a body guard
CHECK Slowdrawl Raul
TIP Tip Info: is computer literate
QUIT
Data Structures
There is no upper bound to the number of suspects or number of attributes for a given suspect. You cannot use an array-based list to store the suspects or the attributes for a given suspect.
The CHECK operation must be very efficient, because suspects are continually being pulled off the street for questioning and we must decide whether to let them go or ruthlessly interrogate them. Using a simple linked list to store the suspects is not sufficient. You must use a binary search tree. Suspects must be actually deleted from the structure when they are eliminated by TIP information. Because you destroy the list of suspects, as suspects are eliminated by TIP information, each inquiry should work on a copy of the original tree.
TIP is executed much less often than CHECK and hence can be less efficient. It is acceptable if processing a TIP command requires searching the whole data structure of (active) suspects. Thus, a list of attributes can be stored with each suspect. You do not have to link all the suspects with the same attributes together. (This could potentially make for a much faster TIP operation.) You may do this if you want, but it complicates things.
Deliverables
Your design and CRC cards for any classes
A listing of any test driver necessary to check classes
A listing of the test plan for any class as input to the driver
A listing of the source code
A listing of the test plan as input to the program
A listing of the output from the test run
Here is the Program, which is not in empty project of Visual Studio. I want the program in empty project, using ofstream, ifstream and without fout.
#include "stdafx.h"
#include
#include
#include
#include
#include
#define Input "Criminal.mf"
#define Output "Criminal.trn"
#define INF 1000000000
#define II pair,string>
using namespace std;
// using binary search tree to store suspects
typedef struct Element{
int key;
string name;
list attributes; // List attributes of suspect
Element *leftChild;
Element *rightChild;
} Node;
ofstream Fin(Input);
ofstream Fout(Output);
class BinarySearchTree{
private:
Node *Tree = NULL;
public: void AddToTree(list attributeSet, string ten);
void RemoveFromTree(string info);
void TravelBinaryTree(Node *root, string info);
void ClearTree(Node *root);
void PrintSuspect(Node *root);
void PrintSuspectName(Node *root, string name);
void printSuspectInfo(string name);
void init();
void print();
void Clear();
string getSuspect();
int getNum();
int num; // number suspects
};
BinarySearchTree inquiry;
list< II > store;
bool Found1;
void printCommands() {
printf("%-15s%-21s% ", "Command", "Processing");
printf("%-15s%-21s% ", "ADD", "Add a suspect to the Suspects data structure.");
printf("%-15s%-21s% ", "INQUIRY", "Prompt user for code name of this inquiry.");
printf("%-15s%-21s% ", "TIP", "Prompt user for the tip information (a particular attribute).");
printf("%-15s%-21s% ", "CHECK", "Prompt the user for a suspect's name.");
printf("%-15s%-21s% ", "PRINT", "Print the set of active suspects.");
printf("%-15s%-21s% ", "QUIT", "Stop processing.");
cout << endl;
}
int getKey(list attributeSet){
int u;
list::iterator run;
string att;
u = INF;
for (run = attributeSet.begin(); run != attributeSet.end(); run++){
att = *run;
if (att.length() < u)
u = att.length();
}
return u;
}
void BinarySearchTree::init(){
Tree = NULL;
}
int BinarySearchTree::getNum(){
return num;
}
string BinarySearchTree::getSuspect(){
return Tree->name;
}
string converttoupper(string source){
for (int i = 0; i < source.length(); i++)
source[i] = toupper(source[i]);
return source;
}
void BinarySearchTree::PrintSuspectName(Node *root, string name){
list tmp;
list::iterator run;
if (root == NULL) return;
string NAME = converttoupper(name);
if (converttoupper(root->name) == NAME){
Found1 = true;
cout << name << " (";
Fout << name << " (";
tmp = root->attributes;
int n = root->attributes.size();
int i = 0;
for (run = tmp.begin(); run != tmp.end(); run++){
cout << *run;
Fout << *run;
i++;
if (i < n) {
cout << ", ";
Fout << ", ";
}
}
cout << endl;
Fout << endl;
return;
}
PrintSuspectName(root->leftChild, name);
PrintSuspectName(root->rightChild, name);
}
void BinarySearchTree::printSuspectInfo(string name){
PrintSuspectName(Tree, name);
}
void BinarySearchTree::AddToTree(list attributeSet, string ten){
Node *tmp, *parent, *v;
int k;
num++;
k = getKey(attributeSet);
v = new Node;
v->leftChild = NULL;
v->rightChild = NULL;
v->attributes = attributeSet;
v->name = ten;
tmp = Tree;
parent = NULL;
if (Tree == NULL)
Tree = v;
else {
while (tmp != NULL){
parent = tmp;
if (k < tmp->key)
tmp = tmp->leftChild;
else
tmp = tmp->rightChild;
}
if (parent != NULL) {
if (parent->key > k)
parent->leftChild = v; // insert data in left subtree
else
parent->rightChild = v; // insert data in right subtree
}
}
}
void BinarySearchTree::TravelBinaryTree(Node *source, string info){
list tmp;
list::iterator run;
bool found;
found = false;
if (source == NULL) return;
tmp = source->attributes;
for (run = tmp.begin(); run != tmp.end(); run++)
if (converttoupper(*run) == converttoupper(info)){
found = true;
break;
}
if (found) store.push_back(II(tmp, source->name));
TravelBinaryTree(source->leftChild, info);
TravelBinaryTree(source->rightChild, info);
}
void BinarySearchTree::ClearTree(Node *root){
if (root != NULL){
ClearTree(root->leftChild);
ClearTree(root->rightChild);
delete root;
}
}
void BinarySearchTree::Clear(){
ClearTree(Tree);
Tree = NULL;
}
void BinarySearchTree::RemoveFromTree(string info){
list::iterator run;
store.clear();
TravelBinaryTree(Tree, info);
ClearTree(Tree);
Tree = NULL;
num = 0;
for (run = store.begin(); run != store.end(); run++){
AddToTree(run->first, run->second);
}
}
bool iskeyWord(string token){
string s = converttoupper(token);
if (s == "ADD" || s == "INQUIRY" || s == "TIP" || s == "CHECK" || s == "PRINT" || s == "QUIT") return true;
return false;
}
string skipBlank(string str){
string s;
bool blank;
s = "";
blank = false;
for (int i = 0; i < str.length(); i++)
if (str[i] != ' '){
s += str[i];
blank = false;
}
else {
if (!blank) s += str[i];
blank = true;
}
return s;
}
void BinarySearchTree::PrintSuspect(Node *root){
list::iterator run;
if (root == NULL) return;
cout << root->name << " (";
Fout << root->name << " (";
int n = root->attributes.size();
int i = 0;
for (run = (root->attributes).begin(); run != (root->attributes).end(); run++){
cout << *run;
Fout << *run;
i++;
if (i < n) {
cout << ", ";
Fout << ", ";
}
}
cout << ")" << endl;
Fout << ")" << endl;
PrintSuspect(root->leftChild);
PrintSuspect(root->rightChild);
}
void BinarySearchTree::print(){
cout << " List of suspects:" << endl;
Fout << " List of suspects:" << endl;
PrintSuspect(Tree);
}
void processing(){
string strLine, token, order, attr, name, codeName, TIPinfo;
list ListAttr;
inquiry.init();
getline(cin, strLine);
istringstream read(strLine);
read >> order;
while (true){
if (converttoupper(order) == "ADD"){
ListAttr.clear();
cout << " Name:" << endl;
getline(cin, name);
Fin << "Suspect's name: " << name << endl;
Fin << " Attributes:" << endl;
cout << " Attributes:" << endl;
while (true){
getline(cin, strLine);
istringstream read(strLine);
read >> token;
if (iskeyWord(token)){
order = token;
inquiry.AddToTree(ListAttr, name);
break;
}
else {
attr = skipBlank(strLine);
Fin << strLine << endl;
ListAttr.push_back(attr);
}
}
}
else
if (converttoupper(order) == "INQUIRY"){
cout << " Code Name:" << endl;
getline(cin, codeName);
getline(cin, strLine);
istringstream read(strLine);
read >> order;
}
else
if (converttoupper(order) == "TIP"){
cout << " Tip info:" << endl;
getline(cin, strLine);
TIPinfo = skipBlank(strLine);
inquiry.RemoveFromTree(TIPinfo);
Fout << "Tip info: " << TIPinfo << endl;
if (inquiry.getNum() == 1){
cout << " Crime has found. That is suspect " << inquiry.getSuspect() << endl;
cout << " Inquiry code name: " << codeName << endl;
Fout << " Crime has found. That is suspect " << inquiry.getSuspect() << endl;
Fout << " Inquiry code name: " << codeName << endl;
inquiry.Clear();
}
getline(cin, strLine);
istringstream read(strLine);
read >> order;
}
else
if (converttoupper(order) == "CHECK"){
cout << " Name:" << endl;
getline(cin, name);
Fout << "Check " << name << endl;
Found1 = false;
inquiry.printSuspectInfo(name);
if (!Found1){
cout << "Suspect " << name << " has been released" << endl;
Fout << "Suspect " << name << " has been released" << endl;
}
getline(cin, strLine);
istringstream read(strLine);
read >> order;
}
else
if (converttoupper(order) == "PRINT"){
inquiry.print();
getline(cin, strLine);
istringstream read(strLine);
read >> order;
}
else
if (converttoupper(order) == "QUIT") return;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
printCommands();
processing();
Fin.close();
Fout.close();
system("pause");
return 0;
}
Command
Processing
ADD
Add a suspect to the Suspects data structure. Prompt the user for the suspect's name and a list of attributes. ADD commands can be issued only before an inquiry begins.
INQUIRY
Prompt user for code name of this inquiry. Once the inquiry has begun, do not allow the user to issue the ADD command until this inquiry is complete.
TIP
Prompt user for the tip information (a particular attribute). Process the tip, reducing the set of current suspects by deleting suspects who do not match the attribute mentioned in the tip. If there is only one suspect left in the set of active suspects, print out a message indicating that the crime is solved. Be sure to include the suspect's name and inquiry code name. This terminates the current inquiry.
CHECK
Prompt the user for a suspect's name. Check the set of active suspects to see if this name is there; print out an appropriate response.
Print the set of active suspects (those who have not yet been eliminated).
QUIT
If any new suspects have been added during this execution of the program, rewrite the "Criminal.mf" file. Be careful about how you go about saving the records; the traversal order affects the shape of the tree that is built on the next execution of the program. Terminate the program.
Explanation / Answer
main.cpp
#include "Suspect.h"
#include "SuspectTree.h"
#include "Tee.h"
#include "TeeIn.h"
#include <fstream>
#include <iostream>
#include <string>
#include <Windows.h>
using namespace std;
// echo print to screen and file
ofstream printLog("Criminal.trn");
Tee coutEcho(std::cout, printLog);
SuspectTree criminals;
SuspectTree currentCriminals;
string code;
void readCriminalList();
string menu();
string inquiryMenu();
void inquiryMenuHelper();
void add();
void inquiry();
void tip();
void check();
void print();
void cinEcho(string&);
void appendNewAdd(Suspect);
bool iequals(const string&, const string&);
int main()
{
readCriminalList();
string menuSelection;
do
{
menuSelection = menu();
if (menuSelection == "ADD" || menuSelection == "add" || menuSelection == "Add")
add();
else if (menuSelection == "INQUIRY" || menuSelection == "inquiry" || menuSelection == "Inquiry")
inquiry();
else if (menuSelection == "QUIT" || menuSelection == "quit" || menuSelection == "Quit")
coutEcho << " ";
else
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (12));
coutEcho << " Invalid menu option. Please try again. ";
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (7));
}
} while (menuSelection != "QUIT" && menuSelection != "quit");
system("pause");
return 0;
}
void readCriminalList()
{
string str;
fstream criminalList;
criminalList.open("criminals.mf", std::ofstream::in);
// CRIMINAL LIST IS IN THE FOLLOWING FORMAT:
// NAME, TIP, TIP, TIP, ..., #,
if (criminalList)
{
do
{
Suspect *newCriminal = new Suspect();
getline(criminalList, str, ',');
newCriminal->setName(str);
getline(criminalList, str, ' ');
getline(criminalList, str, ',');
while (str != "#")
{
newCriminal->attributes.appendNode(str);
getline(criminalList, str, ' ');
getline(criminalList, str, ',');
}
newCriminal->attributes.appendNode(str);
Suspect addPerson;
addPerson.copy(newCriminal);
criminals.putItem(addPerson);
getline(criminalList, str, ' ');
} while (!criminalList.eof());
}
criminalList.close();
}
// MAIN MENU - CALLED -AT BEGINNING OF PROGRAM
// -AFTER A NEW CRIMINAL IS ADDED
// -AFTER AN INQUIRY IS FINISHED
string menu()
{
string selection;
coutEcho << "************************************************** ";
coutEcho << "Menu - Please choose one of the following commands ";
coutEcho << " ADD INQUIRY QUIT ";
coutEcho << "Type in your command: ";
cinEcho(selection);
return selection;
}
// INQUIRY MENU - WILL CONTINUE TO CALL UNTIL INQUIRY IS SOLVED (ONLY ONE SUSPECT LEFT)
string inquiryMenu()
{
string selection;
coutEcho << " *** " << code << " *** ";
coutEcho << " TIP CHECK PRINT ";
coutEcho << "Type in your command: ";
cinEcho(selection);
return selection;
}
// ADDS NEW CRIMINAL TO CRIMINAL LIST AND FORMATTED TO FILE CORRECTLY
void add()
{
// create new suspect
Suspect *person = new Suspect();
string str;
// get suspects name
coutEcho << " What is the suspect's name: ";
cinEcho(str);
person->setName(str);
// get suspects attributes
coutEcho << " Enter " << str << "'s attributes. Enter 0 when finished. ";
do
{
coutEcho << "- ";
cinEcho(str);
if (str != "0")
person->attributes.appendNode(str);
} while (str != "0");
// add suspect to list
Suspect addPerson;
addPerson.copy(person);
criminals.putItem(addPerson);
appendNewAdd(addPerson);
coutEcho << " ";
}
// INITIAL INQUIRY CALL - CREATES NEW INQUIRY
void inquiry()
{
coutEcho << " *** New Inquiry *** ";
coutEcho << " Type new inquiry code name: ";
cinEcho(code);
currentCriminals = criminals;
inquiryMenuHelper();
}
// INQUIRY HELPER FUNCTION KEEPS GETTING CALLED UNTIL INQUIRY IS SOLVED
void inquiryMenuHelper()
{
string str = inquiryMenu();
if (str == "TIP" || str == "tip" || str == "Tip")
tip();
else if (str == "CHECK" || str == "check" || str == "Check")
check();
else if (str == "PRINT" || str == "print" || str == "Print")
print();
else
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (12));
coutEcho << " Invalid menu option. Try again. ";
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (7));
inquiryMenuHelper();
}
}
// TIP PROMPTS USER TO ENTER AN ATTRIBUTE - ATTRIBUTE IS CHECKED WITH
// ALL ATTRIBUTES IN ALL SUSPECTS TO ELIMINATE SUSPECTS WHO DO NOT MATCH
void tip()
{
Suspect checkPerson;
// get tip info
string tip, suspectTip = "";
coutEcho << " Enter the tip info: ";
cinEcho(tip);
currentCriminals.fillStack();
// get first person in stack
checkPerson = currentCriminals.getNextItem();
// while next person is not "null"
bool match = false;
while (checkPerson.getName() != "")
{
// while there is no match and not at the end of the attribute list
while (!match && suspectTip != "#")
{
suspectTip = checkPerson.attributes.getNextItem();
if (iequals(suspectTip, tip))
match = true;
}
if (!match)
currentCriminals.deleteItem(checkPerson);
// check next person, reset suspectTip and match
checkPerson = currentCriminals.getNextItem();
suspectTip = "";
match = false;
}
if (currentCriminals.getLength() > 1)
inquiryMenuHelper();
else if (currentCriminals.getLength() == 1)
{
currentCriminals.fillStack();
coutEcho << code << " Case has been solved. ";
coutEcho << "The only suspect left is " << currentCriminals.getNextItem().getName();
coutEcho << " Book 'Em Danno ";
}
else
{
coutEcho << "There are no suspects that match all given tips. ";
}
}
// CHECK USES A BINARY SEARCH FUNCTION TO SEE IF A CERTAIN CRIMINAL IS STILL A SUSPECT ON THIS INQUIRY
void check()
{
string str;
bool found = false;
coutEcho << " Enter name: ";
cinEcho(str);
currentCriminals.getItem(str, found);
coutEcho << " ";
if (!found)
coutEcho << str << " is not a suspect for this case. ";
else
coutEcho << str << " is still a suspect. ";
inquiryMenuHelper();
}
// PRINTS ALL CURRENT SUSPECTS FOR THIS INQUIRY
void print()
{
Suspect person;
currentCriminals.fillStack();
person = currentCriminals.getNextItem();
coutEcho << " " << code << " Current Suspects: ";
while (person.getName() != "")
{
coutEcho << " " << person.getName() << " ";
person = currentCriminals.getNextItem();
}
coutEcho << " ";
inquiryMenuHelper();
}
// USED IN PLACE OF ALL CIN CALLS TO ENABLE ECHO PRINTING TO PRINT LOG
void cinEcho(string &input)
{
getline(cin, input);
printLog << input;
}
// USED TO ADD NEW SUSPECT TO CLIENT LIST WITH PROPER FORMATTING
void appendNewAdd(Suspect newPerson)
{
fstream criminalList;
string str;
criminalList.open("criminals.mf", std::fstream::app);
criminalList << " ";
criminalList << newPerson.getName();
criminalList << ", ";
str = newPerson.attributes.getNextItem();
while (str != "#")
{
criminalList << str;
criminalList << ", ";
str = newPerson.attributes.getNextItem();
}
criminalList << str;
criminalList << ", ";
criminalList.close();
}
bool iequals(const string& a, const string& b)
{
unsigned int sz = a.size();
if (b.size() != sz)
return false;
for (unsigned int i = 0; i < sz; ++i)
if (tolower(a[i]) != tolower(b[i]))
return false;
return true;
}
LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
using namespace std;
template <class T>
class LinkedList
{
private:
struct ListNode
{
T value;
struct ListNode *next;
};
ListNode *head;
ListNode *currentPos;
public:
LinkedList();
// ~LinkedList(); // destructor crashed the program - have no clue why, any suggestions?
void appendNode(T);
void insertNode(T);
void deleteNode(T);
void displayList() const;
int searchList(T) const;
T getNextItem();
};
/********* constructor ***********/
template <class T>
LinkedList<T>::LinkedList()
{
head = nullptr;
currentPos = head;
}
/********* append ***********/
template <class T>
void LinkedList<T>::appendNode(T num)
{
ListNode *newNode;
ListNode *nodePtr;
newNode = new ListNode;
newNode->value = num;
newNode->next = nullptr;
if (!head)
head = newNode;
else
{
nodePtr = head;
while (nodePtr->next)
nodePtr = nodePtr->next;
nodePtr->next = newNode;
}
}
/********* insert ***********/
template <class T>
void LinkedList<T>::insertNode(T num)
{
ListNode *newNode;
ListNode *nodePtr;
ListNode *previousNode = nullptr;
newNode = new ListNode;
newNode->value = num;
if (!head)
{
head = newNode;
newNode->next = nullptr;
}
else
{
nodePtr = head;
previousNode = nullptr;
while (nodePtr != nullptr && nodePtr->value < num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
if (previousNode == nullptr)
{
head = newNode;
newNode->next = nodePtr;
}
else
{
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
}
/********* delete ***********/
template <class T>
void LinkedList<T>::deleteNode(T num)
{
ListNode *nodePtr;
ListNode *previousNode = nullptr;
if (!head)
return;
if (head->value == num)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
nodePtr = head;
while (nodePtr != nullptr && nodePtr->value != num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
if (nodePtr)
{
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
}
/********* display ***********/
template <class T>
void LinkedList<T>::displayList() const
{
ListNode *nodePtr;
nodePtr = head;
while (nodePtr)
{
cout << "nodePtr->value" << endl;
nodePtr = nodePtr->next;
}
cout << endl;
}
/********* search ***********/
template <class T>
int LinkedList<T>::searchList(T num) const
{
int index = 0;
ListNode *nodePtr;
nodePtr = head;
while (nodePtr)
{
if (nodePtr->value == num)
return index;
else
{
nodePtr = nodePtr->next;
index++;
}
}
index = -1;
return index;
}
template <class T>
T LinkedList<T>::getNextItem()
{
string done = "#";
if (currentPos == NULL)
currentPos = head;
else
currentPos = currentPos->next;
if (currentPos != NULL)
return currentPos->value;
else
return done;
}
#endif
Stack.h
#ifndef STACK_H
#define STACK_H
#include <iostream>
using namespace std;
template <class T>
class Stack
{
private:
struct StackNode
{
T value;
StackNode *next;
};
StackNode *top;
public:
Stack();
~Stack();
void push(T);
bool pop(T &);
bool get(T &);
bool isEmpty();
};
/************** constructor ***************/
template <class T>
Stack<T>::Stack()
{
top = nullptr;
}
/************** destructor ***************/
template <class T>
Stack<T>::~Stack()
{
StackNode *nodePtr,
*nextNode;
nodePtr = top;
while (nodePtr != nullptr)
{
nextNode = nodePtr->next;
delete nodePtr;
nodePtr = nextNode;
}
}
/************** push ***************/
template <class T>
void Stack<T>::push(T item)
{
StackNode *newNode = nullptr;
newNode = new StackNode;
newNode->value = item;
if (isEmpty())
{
top = newNode;
newNode->next = nullptr;
}
else
{
newNode->next = top;
top = newNode;
}
}
/************** pop ***************/
template <class T>
bool Stack<T>::pop(T &item)
{
bool status;
StackNode *temp = nullptr;
if (isEmpty())
status = false;
else
{
item = top->value;
temp = top->next;
delete top;
top = temp;
status = true;
}
return status;
}
template <class T>
bool Stack<T>::get(T &item)
{
bool status;
StackNode *temp = nullptr;
if (isEmpty())
status = false;
else
{
item = top->value;
temp = top->next;
top = temp;
status = true;
}
return status;
}
/************** is empty ***************/
template <class T>
bool Stack<T>::isEmpty()
{
bool status;
if (!top)
status = true;
else
status = false;
return status;
}
#endif
Suspect.cpp
#include "Suspect.h"
Suspect::Suspect()
{ name = ""; }
Suspect::Suspect(string n)
{ name = n; }
Suspect::~Suspect()
{
}
void Suspect::setName(string n)
{ name = n; }
string Suspect::getName() const
{ return name; }
// used to transform a pointer object into an object
void Suspect::copy(Suspect *ptr)
{
setName(ptr->getName());
attributes = ptr->attributes;
}
Suspect.h
#pragma once
#ifndef SUSPECT_H
#define SUSPECT_H
#include "LinkedList.h"
#include <string>
using namespace std;
class Suspect
{
private:
string name;
public:
LinkedList<string> attributes;
Suspect();
Suspect(string);
~Suspect();
void setName(string);
string getName() const;
void copy(Suspect*);
};
#endif
SuspectTree.cpp
#include "SuspectTree.h"
SuspectTree::SuspectTree()
{
root = NULL;
}
SuspectTree::~SuspectTree()
{
destroy(root);
}
void SuspectTree::destroy(TreeNode*& tree)
{
if (tree != NULL)
{
destroy(tree->left);
destroy(tree->right);
delete tree;
}
}
SuspectTree::SuspectTree(const SuspectTree &original)
{
copyTree(root, original.root);
}
void SuspectTree::operator=(const SuspectTree& original)
{
if (&original == this)
return;
destroy(root);
copyTree(root, original.root);
}
void SuspectTree::copyTree(TreeNode*& copy, const TreeNode* original)
{
if (original == NULL)
copy = NULL;
else
{
copy = new TreeNode;
copy->info = original->info;
copyTree(copy->left, original->left);
copyTree(copy->right, original->right);
}
}
bool SuspectTree::isEmpty() const
{
return root == NULL;
}
bool SuspectTree::isFull() const
{
TreeNode* location;
try
{
location = new TreeNode;
delete location;
return false;
}
catch (std::bad_alloc exception)
{
return true;
}
}
void SuspectTree::putItem(Suspect person)
{
insert(root, person);
}
void SuspectTree::insert(TreeNode*& tree, Suspect person)
{
if (tree == NULL)
{
tree = new TreeNode;
tree->right = NULL;
tree->left = NULL;
tree->info = person;
position = root;
}
else if (person.getName() < tree->info.getName())
insert(tree->left, person);
else
insert(tree->right, person);
}
void SuspectTree::deleteItem(Suspect person)
{
makeDeletion(root, person);
}
void SuspectTree::makeDeletion(TreeNode*& tree, Suspect person)
{
if (person.getName() < tree->info.getName())
makeDeletion(tree->left, person);
else if (person.getName() > tree->info.getName())
makeDeletion(tree->right, person);
else
deleteNode(tree);
}
void SuspectTree::deleteNode(TreeNode*& tree)
{
Suspect person;
TreeNode* tempPtr;
tempPtr = tree;
if (tree->left == NULL)
{
tree = tree->right;
delete tempPtr;
}
else if (tree->right == NULL)
{
tree = tree->left;
delete tempPtr;
}
else
{
getPredecessor(tree->left, person);
tree->info = person;
makeDeletion(tree->left, person);
}
}
void SuspectTree::getPredecessor(TreeNode* tree, Suspect& person)
{
while (tree->right != NULL)
tree = tree->right;
person = tree->info;
}
int SuspectTree::getLength()
{
return countNodes(root);
}
int SuspectTree::countNodes(TreeNode* tree)
{
if (tree == NULL)
return 0;
else
return countNodes(tree->left) + countNodes(tree->right) + 1;
}
Suspect SuspectTree::getItem(Suspect person, bool& found)
{
retrieve(root, person, found);
return person;
}
void SuspectTree::retrieve(TreeNode* tree, Suspect &person, bool &found)
{
string currentName;
string personName = person.getName();
if (tree != NULL)
currentName = tree->info.getName();
else
currentName = "";
bool same = true;
unsigned int size = personName.size();
if (size != currentName.size())
same = false;
else
{
for (unsigned int i = 0; i < size; ++i)
{
if (tolower(personName[i]) != tolower(currentName[i]))
{
same = false;
}
}
if (same)
{
person = tree->info;
found = true;
}
}
if (!found)
{
if (tree == NULL)
found = false;
else if (personName < currentName)
retrieve(tree->left, person, found);
else if (personName > currentName)
retrieve(tree->right, person, found);
}
}
Suspect SuspectTree::getNextItem()
{
Suspect rtn;
suspectStack.get(rtn);
return rtn;
}
void SuspectTree::fillStack()
{
fillStackHelper(root);
}
void SuspectTree::fillStackHelper(TreeNode* current)
{
if (current != NULL)
{
fillStackHelper(current->left);
suspectStack.push(current->info);
fillStackHelper(current->right);
}
}
void SuspectTree::deleteSuspect()
{
Suspect s;
suspectStack.pop(s);
}
Tee.h
#ifndef TEE_H
#define TEE_H
#include <ostream>
class Tee
{
std::ostream &first, &second;
template<typename T> friend Tee& operator<< (Tee&, T);
public:
Tee(std::ostream &f, std::ostream &s) : first(f), second(s) {}
};
template <typename T>
Tee& operator<< (Tee &t, T val)
{
t.first << val;
t.second << val;
return t;
}
#endif
TeeIn.h
#ifndef TEEIN_H
#define TEEIN_H
#include <ostream>
class TeeIn
{
std::istream &first;
std::ostream &second;
template<typename T> friend Tee& operator>> (Tee&, T);
public:
TeeIn(std::istream &f, std::ostream &s) : first(f), second(s) {}
};
template <typename T>
Tee& operator>> (Tee &t, T val)
{
t.first >> val;
t.second << val;
return t;
}
#endif
SuspectTree.h
#ifndef SUSPECTTREE
#define SUSPECTTREE
#include "Suspect.h"
#include "Stack.h"
class SuspectTree
{
private:
struct TreeNode
{
Suspect info;
TreeNode *left;
TreeNode *right;
};
TreeNode *root;
TreeNode *position;
Stack<Suspect> suspectStack;
// helper functions
void destroy(TreeNode*&);
void copyTree(TreeNode*&, const TreeNode*);
int countNodes(TreeNode*);
void retrieve(TreeNode*, Suspect&, bool&);
void insert(TreeNode*&, Suspect);
void deleteNode(TreeNode*&);
void makeDeletion(TreeNode*&, Suspect);
void getPredecessor(TreeNode*, Suspect&);
void fillStackHelper(TreeNode*);
public:
SuspectTree();
~SuspectTree();
SuspectTree(const SuspectTree &);
void operator=(const SuspectTree &);
bool isEmpty() const;
bool isFull() const;
void putItem(Suspect);
void deleteItem(Suspect);
void makeEmpty();
int getLength();
Suspect getItem(Suspect, bool&);
Suspect getNextItem();
void fillStack();
void deleteSuspect();
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.