I\'m working in C++ and the project im\'m working on involves a heap. Below is w
ID: 3602928 • Letter: I
Question
I'm working in C++ and the project im'm working on involves a heap.
Below is what the assignment have to do. Below that is what code I have already. Where i'm stuck is i don't know how store the input from the file correctly. I don't know what data structure to use. I don't want you to finish this for me, I just need help getting passed menu item number 2. How do I store the input, right now i have each stored individually, but how do i keep them together so i can put on the heap where they are linked?
Problem: Write a menu-driven C++ program to implement operations on a heap and binary file I/O.
Inputs:
1. Initial input file is stored in an external text file named as cs316p2.dat.
Each line in the file contains a record with the following format:
FirstName LastName ID GPA
Where FirstName and LastName are strings of at most 20 characters, ID is an integer, and GPA is a float.
2. Interactive inputs: (1)
(2) (3) (4)
(5) (6) (7) (8)
your program should start with the following menu.
(1)Read data from external text file.
/* Prompt the user to enter an external input file name or use default file name. */
(2) Build a max heap in terms of ID or LastName. /* prompt for selection */
(3)Add a new record to max heap. /* prompt for entering new record */
(4)Delete a record from the max heap.
/* Prompt for ID or LastName*/
(5)Print sorted list from max heap in ascending order based on ID or LastName.
(6)Save a sorted list to external binary file named as 316p2.rec.
(7) Load the binary file and print the list by one record per line.
(8) Quit.
Outputs: print all warning or error messages to screen.
Testing: create your testing data file.
Other Requirements:
Define and implement a heap ADT. Your program should be fail-safe.
main.cpp
#include "heap.hpp"
#include
#include
#include
using std::cout;
using std::cin;
using std::endl;
// declaring functions
int menu();
void readFile();
void buildMaxHeap();
void buildMaxHeapLastName();
void buildMaxHeapID();
void addRecord();
void deleteRecord();
void printHeap();
int main(){
// a start label to goto so when they pick a task, they can continue to choose other options until they break
start:
while(true)
{
int option = menu();
switch(option){
case 1 :
readFile();
cout << "You've read in the file ";
goto start;
case 2 :
buildMaxHeap();
cout << "You've built the max heap! ";
goto start;
case 3 :
addRecord();
cout << "You've added a new record to the max heap ";
goto start;
case 4 :
deleteRecord();
cout << "You've deleted a record from the heap ";
goto start;
case 5 :
printHeap();
cout << " You've printed the sorted heap ";
goto start;
case 6 :
cout << " ";
goto start;
case 7 :
cout << " ";
goto start;
default :
break;
}
break;
}
return 0;
}
void buildMaxHeap()
{
start:
cout << "Do you want to build heap on (1)LastName or (2)ID? ";
int option;
cin >> option;
if(option == 1)
{
cout<< "Congrats, you choose LastName ";
buildMaxHeapLastName();
}
else if(option == 2)
{
cout<< "you choose ID ";
buildMaxHeapID();
}
else
{goto start;}
}
void buildMaxHeapLastName()
{
std::ofstream infile;
infile.open ("cs316p2.dat");
//Check for Error
if (infile.fail())
{
std::cerr << "Error Opening File" << endl;
exit(1);
}
std::string line, firstName, lastName;
int ID;
float GPA;
while(!infile.eof(std::getline(cin, line, " "))
{
infile >> firstName >> LastName >> ID >> GPA;
push(LastName);
}
infile.close();
}
void buildMaxHeapID()
{
std::ofstream infile;
infile.open ("cs316p2.dat");
//Check for Error
if (infile.fail())
{
std::cerr << "Error Opening File" << endl;
exit(1);
}
std::string line, firstName, lastName;
int ID;
float GPA;
while(!infile.eof(std::getline(cin, line, " "))
{
infile >> firstName >> LastName >> ID >> GPA;
push(ID);
}
infile.close();
}
//uses default name, not allowing user to enter
void readFile()
{
std::ofstream infile;
infile.open ("cs316p2.dat");
//Check for Error
if (infile.fail())
{
std::cerr << "Error Opening File" << endl;
exit(1);
}
infile.close();
}
int menu()
{
cout << "Please choose one of the following ";
cout << "(1) Read data from external text file. ";
cout << "(2) Build a max heap in terms of ID or LastName. ";
cout << "(3) Add a new record to max heap.. ";
cout << "(4) Delete a record from the max heap. ";
cout << "(5) Print sorted list from max heap in ascending order based on ID or LastName. ";
cout << "(6) Save a sorted list to external binary file named as 316p2.rec. ";
cout << "(7) Load the binary file and print the list by one record per line. ";
cout << "(8) Quit ";
// get what number they entered, not worried about anything else
int option;
cin.ignore();
cin >> option;
return option;
}
heap.hpp
#include
#include
using std::vector;
using std::cout;
using std::out_of_range;
using std::swap;
class Heap
{
private:
// vector to store heap elements
vector A;
// return Parent of A[i]
// don't call this function if it is already a root node
int Parent(int i)
{
return (i - 1) / 2;
}
// return left child of A[i]
int Left(int i)
{
return (2 * i + 1);
}
// return right child of A[i]
int Right(int i)
{
return (2 * i + 2);
}
// Recursive Heapify-down algorithm
// the node at index i and its two direct children
// violates the heap property
void heapify_down(int i)
{
// get left and right child of node at index i
int left = Left(i);
int right = Right(i);
int largest = i;
// compare A[i] with its left and right child
// and find largest value
if (left < size() && A[left] > A[i])
largest = left;
if (right < size() && A[right] > A[largest])
largest = right;
// swap with child having greater value and
// call heapify-down on the child
if (largest != i) {
swap(A[i], A[largest]);
heapify_down(largest);
}
}
// Recursive Heapify-up algorithm
void heapify_up(int i)
{
// check if node at index i and its Parent violates
// the heap property
if (i && A[Parent(i)] < A[i])
{
// swap the two if heap property is violated
swap(A[i], A[Parent(i)]);
// call Heapify-up on the Parent
heapify_up(Parent(i));
}
}
public:
// return size of the heap
unsigned int size()
{
return A.size();
}
// function to check if heap is empty or not
bool empty()
{
return size() == 0;
}
// insert key into the heap
void push(int key)
{
// insert the new element to the end of the vector
A.push_back(key);
// get element index and call heapify-up procedure
int index = size() - 1;
heapify_up(index);
}
// function to remove element with highest priority (present at root)
void pop()
{
try {
// if heap has no elements, throw an exception
if (size() == 0)
throw out_of_range("Vector::at() : "
"index is out of range(Heap underflow)");
// replace the root of the heap with the last element
// of the vector
A[0] = A.back();
A.pop_back();
// call heapify-down on root node
heapify_down(0);
}
// catch and print the exception
catch (const out_of_range& oor) {
cout << " " << oor.what();
}
}
// function to return element with highest priority (present at root)
int top()
{
try {
// if heap has no elements, throw an exception
if (size() == 0)
throw out_of_range("Vector::at() : "
"index is out of range(Heap underflow)");
// else return the top (first) element
return A.at(0); // or return A[0];
}
// catch and print the exception
catch (const out_of_range& oor) {
cout << " " << oor.what();
}
}
};
Explanation / Answer
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
//# include <bits/stdc++.h>
using namespace std;
/*int stoi(string str)
{
stringstream ss(str);
int N;
ss<<str;
ss>>N;
return N;
}*/
struct maxHeap
{
vector<string> maxHeapVect;
int size_of_heap;
bool build_by_id;
bool build_by_name;
maxHeap()
{
size_of_heap = 0;
}
int parent(int i)
{
return (i-1)/2;
}
int left(int i)
{
return (2*i)+1;
}
int right(int i)
{
return (2*i)+2;
}
void insertKey(string s)
{
maxHeapVect.push_back(s);
int i = size() - 1;
max_heapify(i);
}
void buildHeap(vector<string> fileVect)
{
for(int i = 0; i < fileVect.size(); i++)
{
insertKey(fileVect[i]);
}
}
int size()
{
return maxHeapVect.size();
}
void swap(string& s1, string& s2)
{
string temp = s2;
s2 = s1;
s1 = temp;
}
string grab_lname(string element)
{
string lname;
int spaceCounter = 0;
for(int j = 0; j < element.size(); j++)
{
if(isspace(element[j]))
{
spaceCounter++;
}
if(spaceCounter == 2)
{
break;
}
if(isalpha(element[j]) && spaceCounter == 1)
{
lname += element[j];
}
}
return lname;
}
void print_in_order()
{
for(int i = 0; i < size(); i++)
{
cout << maxHeapVect[i] << endl;
}
}
void delete_by_id(string s)
{
for(int i = 0; i < size(); i++)
{
cout << convert_for_ID(maxHeapVect[i]);
if(stoi(s) == convert_for_ID(maxHeapVect[i]))
{
maxHeapVect.erase(remove(maxHeapVect.begin(), maxHeapVect.end(), maxHeapVect[i]), maxHeapVect.end());
}
}
}
void delete_by_lname(string s)
{
for(int i = 0; i < size(); i++)
{
if(s == grab_lname(maxHeapVect[i]))
{
cout << "found match" << endl;
maxHeapVect.erase(remove(maxHeapVect.begin(), maxHeapVect.end(), maxHeapVect[i]), maxHeapVect.end());
}
}
}
void max_heapify(int i)
{
if(build_by_id)
{
if (i && convert_for_ID(maxHeapVect[parent(i)]) < convert_for_ID(maxHeapVect[i]))
{
swap(maxHeapVect[i], maxHeapVect[parent(i)]);
max_heapify(parent(i));
}
}
else if(build_by_name)
{
if (i && convert_for_lname(maxHeapVect[parent(i)]) < convert_for_lname(maxHeapVect[i]))
{
swap(maxHeapVect[i], maxHeapVect[parent(i)]);
max_heapify(parent(i));
}
}
}
int convert_for_ID(string element)
{
string idS;
int id;
int spaceCounter = 0;
for(int j = 0; j < element.size(); j++)
{
if(isspace(element[j]))
{
spaceCounter++;
}
if(isdigit(element[j]))
{
idS+=element[j];
}
if(spaceCounter == 3)
{
break;
}
}
id = stoi(idS);
return id;
}
char convert_for_lname(string element)
{
char lname;
bool hit_first_space = false;
for(int j = 0; j < element.size(); j++)
{
if(isspace(element[j]))
{
hit_first_space = true;
}
if(isalpha(element[j]) && hit_first_space)
{
lname = tolower(element[j]);
break;
}
}
return lname;
}
};
vector<string> readExternal();
maxHeap build_Heap(vector<string>);
void addRecord(maxHeap&);
void deleteRecord(maxHeap&);
void printSortedList(maxHeap);
void saveSortedList(maxHeap);
void loadAndPrintFile();
void clearBinaryFile();
int main()
{
int selection;
bool running = true;
vector<string> fileVect;
vector<string> heaped_vect;
maxHeap m_heap;
while(running)
{
cout << "Please follow steps 1-9 in order" << endl;
cout << "Select one of the following options and hit enter:" << endl;
cout << "(1) Read data from an external file" << endl;
cout << "(2) Build max heap in terms of ID or LastName" << endl;
cout << "(3) Add record to max heap" << endl;
cout << "(4) Delete Record from max heap" << endl;
cout << "(5) Print sorted list from max heap in ascending order based on ID or last name" << endl;
cout << "(6) Save sorted list in external file" << endl;
cout << "(7) Load binary file and print records one line at a time" << endl;
cout << "(8) Clear Binary" << endl;
cout << "(9) Exit program" << endl;
cin >> selection;
cin.ignore(1000, ' ');
switch (selection)
{
case 1:
fileVect = readExternal();
break;
case 2:
m_heap = build_Heap(fileVect);
m_heap.print_in_order();
break;
case 3:
addRecord(m_heap);
m_heap.print_in_order();
break;
case 4:
deleteRecord(m_heap);
m_heap.print_in_order();
break;
case 5:
printSortedList(m_heap);
break;
case 6:
saveSortedList(m_heap);
break;
case 7:
loadAndPrintFile();
break;
case 8:
clearBinaryFile();
break;
case 9:
running = false;
return 0;
break;
default:
cout << "You entered an incorrect character..." << endl;
break;
}
}
return 0;
}
vector<string> readExternal()
{
ifstream inFile;
string fileName;
string fileString;
vector<string> fileVect;
maxHeap m_heap;
cout << "Enter external file name or type 'default' to use default external file:" << endl;
getline(cin, fileName);
cout << "You entered: " << fileName << endl;
if(fileName == "default")
{
inFile.open("cs316p2.dat");
}
else
{
inFile.open(fileName);
}
if(!inFile)
{
cerr << "unable to open " << fileName << endl;
}
while(!inFile.eof())
{
getline(inFile, fileString);
cout << fileString << endl;
fileVect.push_back(fileString);
}
inFile.close();
return fileVect;
}
maxHeap build_Heap(vector<string> fileVect)
{
maxHeap m_heap;
string choice;
cout << "Type 'id' for heap built by id, or 'lastname' for heap built by last name:" << endl;
getline(cin, choice);
if(choice == "id")
{
m_heap.build_by_id = true;
m_heap.build_by_name = false;
cout << "You selected ID" << endl;
}
else if(choice == "lastname")
{
m_heap.build_by_id = false;
m_heap.build_by_name = true;
}
else
{
cout << "you entered an incorrect string..";
exit(0);
}
m_heap.buildHeap(fileVect);
return m_heap;
}
void addRecord(maxHeap& m_heap)
{
string newRecord;
cout << "Please enter the new record in correct format: Firstname Lastname id(integer) gpa(float)" << endl;
getline(cin, newRecord);
cout << endl;
m_heap.insertKey(newRecord);
}
void deleteRecord(maxHeap& m_heap)
{
string recordToDelete;
cout << "Please enter the ID or last name of the record being deleted:" << endl;
getline(cin, recordToDelete);
if(isdigit(recordToDelete[0]))
{
m_heap.delete_by_id(recordToDelete);
}
else if(isalpha(recordToDelete[0]))
{
m_heap.delete_by_lname(recordToDelete);
}
else
{
cout << "You inputed an incorrect string..";
}
}
void printSortedList(maxHeap m_heap)
{
m_heap.print_in_order();
}
void saveSortedList(maxHeap m_heap)
{
fstream myFile("316p2.rec", ios::out | ios::binary);
myFile.write((char*)&m_heap, sizeof(maxHeap));
myFile.close();
}
void loadAndPrintFile()
{
ifstream myFile;
maxHeap* readHeap = new maxHeap[10];
myFile.open("316p2.rec", ios::in | ios::binary);
myFile.read((char*)readHeap, sizeof(maxHeap) * 10);
for(int i = 0; i < readHeap->size(); i++)
{
cout << readHeap->maxHeapVect[i] << endl;
}
myFile.close();
}
void clearBinaryFile()
{
ofstream myFile;
myFile.open("316p2.rec", ofstream::out | ofstream::trunc);
myFile.close();
}
///Maxheap.h
#ifndef MAX_HEAP_H_INCLUDED
#define MAX_HEAP_H_INCLUDED
#endif // MAX_HEAP_H_INCLUDED