Here is what I have so far in my C++ program! I cannot seem to get the Template
ID: 3722227 • Letter: H
Question
Here is what I have so far in my C++ program! I cannot seem to get the Template quickSort Function along with the partition function which both are recursive function to print out the months of birthdays in ascending order regardless of the year. The instruction and files are below. I have worked on them but I need help with the rest. All the files are attached even the main file which I have worked on.
Instructions:
Use the “birthdate.txt” file with the names to read into the Person struct.
Mark,12/21/1992, Jay,9/29/1974, Amy Lynn,3/17/2010, Bill,12/18/1985, Julie,7/10/1980, Debbie,5/21/1976, Paul,1/3/2001, Ian,2/29/1980, Josh,10/31/2003, Karen,8/24,2011.
Create a structure person with string name, and Date birthdate, and Date birthday. For example Marks birthdate is 12/21/1992, but his birthday is 12/21/2016. (this year).
Read in the file and create a Vector of the birthdays from the file.
Add a Template Quicksort to Sort by birthday. (Everyone born in January is listed first regardless of what year they were born, ending with the people born in December.) It is NOT sorted by age.
Print out the list of people with their name and birthday and age.
// source.cpp
#include "Date.cpp"
#include <iostream> // For input and output
#include <vector> // For vector operations
#include <fstream> // For opening, closing, reading, and writing to files
#include <cstdlib> // General utilities library for conversions
#include <iomanip> // For output formatting
using namespace std; // Standard C++ library
struct Person {
// Declare person struct variables
string name;
Date birthDate;
Date birthDay;
};
// QuickSort function prototype or function declaration as template
template<class T>
void quickSort(vector<T> person, int start, int last);
// Partition function prototype or function declaration as template
template<class T>
int partition(vector<T> person, int start, int last);
// Start of main
int main() {
// Struct person vector to hold persons' information
vector<Person> person;
Person p; // Assessor object for person struct
int const PRESENT_YEAR = 2018; // Year to calculate age of person
//p.birthDay = Date().setYear(PRESENT_YEAR); // Set the birthday year
int age = 0; // Age variable for person's age
int yearBorn = 0; // Variable for year born
int count = 0; // Loop counter for records
ifstream inputFile; // File string stream object for reading and
// opening file
string input; // Input string from file
// Try to open input file
inputFile.open("birthdays.txt");
if (!inputFile.is_open()) // Check the input file is open
{
// Display message if file is not open
cout << "Could not open file birthdays.txt." << endl;
return 1; // 1 indicates error
}
// Print read numbers to output
cout << "Reading and printing name, birth date, and birth day. ";
while (!inputFile.eof()) // Check for end of file
{
// Get persons' name and store it in struct data member "name".
std::getline(inputFile, input, ',');
p.name = input;
std::getline(inputFile, input, '');
p.birthDate;
// int month = p.birthDate.getMonth();
person.push_back(p);
count++;
}
inputFile.close();
quickSort(person, 0, count - 1);
system("pause");
return 0; // Return 0 if all good
}// End of main
// QuickSort function definition as template
template<class T>
void quickSort(vector<T> person, int start, int last)
{
// PivotPoint of center point variable
int pivotPoint = 0;
// If start value is less than end value then proceed
if (start < last)
{
// Get the pivot point.
pivotPoint = partition(person, start, last);
// Sort the first sublist.
quickSort(person, start, pivotPoint - 1);
// Sort the second sublist.
quickSort(person, pivotPoint + 1, last);
}
}
// Partition function definition as template
template<class T>
int partition(vector<T> person, int start, int last)
{
// Declare variable for pivotValue, pivotIndex and mid
int pivotValue, pivotIndex, mid;
// Assign the midpoint of the search list to variable mid
mid = (start + last) / 2;
// Call the swap function to swap the starting and midpoint
// list values
swap(person.at(start), person.at(mid));
// Assign the start address of search list to the pivotindex
pivotIndex = start;
// Assign the item in array to variable pivotValue
pivotValue = person.at(start);
// Loop through the array to sort values
for (int scan = start + 1; scan <= last; scan++)
{
// Compare values in search array
if (person.at(scan) < pivotValue)
{
// Increase the pivotIndex variable by 1 and swap array
// values by index positions by calling the swap function
pivotIndex++;
swap(person.at(pivotIndex), person.at(scan));
}
}
// Call the swap function again for the last position value
swap(person.at(start), person.at(pivotIndex));
// return the pivotIndex as the pivotPoint position
return pivotIndex;
}
// birthdays.txt
Mark,12/21/1992
Jay,9/29/1974
Amy Lynn,3/17/2010
Bill,12/18/1985
Julie,7/10/1980
Debbie,5/21/1976
Paul,1/3/2001
Ian,2/29/1980
Josh,10/31/2003
Karen,8/24,2011
// Date.h
#ifndef Date_H
#define Date_H
#include <iostream>
#include <sstream>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;
class Date {
private:
int month, day, year;
int days[13];
public:
//constructors
Date(); //constructor for todays date
Date(int m, int d, int y); //constructor to assign date
Date(string str); //constructor for todays date as "mm/dd/year
Date(int gregorian); //constructor to convert a Gregorian date to Date
Date thanksGiving(int year); // Constructor for Thanks Giving
Date birthDate(int m, int d, int y); // Consructor to assign birthdate
//methods
int getMonth() const; //returns the private variable month
int getDay() const; //returns the private variable day
int getYear() const; //returns the private variable year
string toString() const; //returns the string mm/dd/yyyy
bool leapYear() const; //determines if the year is a leap year
int dayofYear() const; //returns the day of the year: ie 2/1/???? is the 32 day of year
int julian() const;
int weekday() const; //returns 0 for Sunday, 1 for Monday, etc.
int seasons(Date date); // Seasons declaration
void bubbleSort(Date holidays[], string names[], int n); // Bubble sort on holidays array
//overloaded operators
bool operator==(const Date& otherDate); //2 dates are equal if month, day and year are equal
bool operator<(const Date& otherDate); //a date is < another date if it is earlier
bool operator>(const Date& otherDate); //a date is > another date if it is later
Date operator=(const Date& otherDate); //let's you copy one date to another.
Date operator+(int); //Assign new values to the date after adding the number of days
friend ostream& operator << (ostream &output, const Date &d);
friend istream& operator >> (istream &input, Date &d);
// Added overloaded operators
bool operator>=(const Date&); // a date is >= another date is equal of later
bool operator!=(const Date&); // 2 dates are not equal if month, day and year are not equal
bool operator<=(const Date&); // a date is <= another date is equal or earlier
};
bool validDate(int m, int d, int y); //test other date
bool leapYear(int y); //let's you test any year, not just the year for the instance
int julian(int m, int d, int y); //convert any date to Julian
void gregorian(int jd, int &mth, int &d, int &y);
static int days2[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
#endif
// Date.cpp
#include "Date.h"
Date::Date() {
//constructor to assign todays date to date
char data[9]; //holder for the date
_strdate_s(data); //gets the current date mm/dd/yy
string date=data; //copy to a string for parsing
month=stoi(date.substr(0,2)); //gets characters 0 and 1 of date and converts to int
day=stoi(date.substr(3,2)); //gets characters 3 and 4 of date and converts to int
year=stoi(date.substr(6,2))+2000; //gets characters 6 and 7 of date and converts to int
if(leapYear()) days2[2]=29; else days2[2]=28;
for(int m=0;m<13;m++) days[m]=days2[m];
}//constructor for today
static bool validDate(int m, int d, int y) {
bool valid=true; //assume it is valid until found to be invalid
if(y<1000) valid=false;
if(m<1 || m>12) valid=false;
if(leapYear(y)) days2[2]=29; else days2[2]=28;
if(d<1 || d>days2[m]) valid=false;
return valid;
}//validDate
Date::Date(int m, int d, int y) {
//constructor to assign values to month day and year
if(validDate(m,d,y)) {
month=m;
day=d;
year=y;
}
else {
month=day=1;
year=1970; //Unix time starting point
} //not valid: set to default valid date
for(int m=0;m<13;m++) days[m]=days2[m];
} //constructor with assigned values
Date::Date(int julian) {
//Fliegel-Van Flandern algorithm to convert Julian date to Gregorian number month, day, and year
gregorian(julian,month,day,year);
if(leapYear()) days2[2]=29; else days2[2]=28;
for(int m=0;m<13;m++) days[m]=days2[m];
}//Date Julian
Date::Date (string str) { //constructor for todays date as "mm/dd/year
//Parse str by adding one char at a s time to the token until a "/" is encounter.
//When "/" is encountered start the next token
//int p=0;
int count=0;
int num[3];
string token[3];
int len=str.length();
for(int p=0; p<len;p++) {
if(str.substr(p,1)=="/") count++;
else token[count]+=str.substr(p,1);
}//parse str to create array of tokens
bool error=false;
for(int p=0;p<3;p++) {
try {
num[p]=stoi(token[p]);
}//try to convert to int
catch(invalid_argument&) {
num[p]=-1;
error=true;
} //catch
}//each of the 3 tokens
if(!error && validDate(num[0],num[1],num[2])) {
month=num[0];
day=num[1];
year=num[2];
} //no error
else {
month=day=1;
year=1970; //Unix time starting point
} //not valid: set to default valid date
for(int m=0;m<13;m++) days[m]=days2[m];
}//constructor with string such as "10/31/2016"
Date Date::operator=(const Date& otherDate) {
//assigns another instance of the date class to this.
month=otherDate.month;
day=otherDate.day;
year=otherDate.year;
return *this; //allows date1=date=date3;
}//overloaded operator =
Date Date::operator+(int numDays) {
//Adds the number of days to the Julian date.
Date other(month,day,year); //make copy of the date
int jd=other.julian(); //find the Julian date
jd+=numDays; //add the number of days to the Julian date
gregorian(jd,other.month,other.day,other.year); //Convert the Julian date back to Gregorian
if(other.leapYear()) days2[2]=29; else days2[2]=28;
for(int m=0;m<13;m++) other.days[m]=days2[m];
return other;
} //operator +
int Date::dayofYear() const {
//returns the day of the year, ie 2/1/???? is the 32 day of the year
int total=day;
for(int m=1;m<month;m++) total+=days[m];
return total;
}//dayofYear
void gregorian(int julian, int &mth, int &d, int &y) {
//Fliegel-Van Flandern algorithm to convert Julian date to Gregorian month, day, and year
int p,q,r,s,t,u,v;
p = julian + 68569;
q = 4*p/146097;
r = p - (146097*q + 3)/4;
s = 4000*(r+1)/1461001;
t = r - 1461*s/4 + 31;
u = 80*t/2447;
v = u/11;
y = 100*(q-49)+s+v;
mth = u + 2 - 12*v;
d = t - 2447*u/80;
} //Gregorian
int Date::julian() const {
int jd= day-32075+1461*(year+4800+(month-14)/12)/4+
367*(month-2-(month-14)/12*12) /12-3*((year+4900+(month-14)/12)/100)/4;
return jd;
}
bool Date::leapYear() const {
bool leap=false;
if(year%4==0) leap=true;
if(year%100==0 && year%400!=0) leap=false;
return leap;
}//leapYear
bool leapYear(int yr) {
bool leap=false;
if(yr%4==0) leap=true;
if(yr%100==0 && yr%400!=0) leap=false;
return leap;
}//leapYear
int Date::weekday() const {
//returns 0 for Sunday, 1 for Monday, etc.
static int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
int y =year;
y-= month < 3;
return ( y + y/4 - y/100 + y/400 + t[month-1] + day) % 7;
}//weekday
int Date::getMonth() const {
//private variables cannot be accessed directly but require "getter" functions
return month;
}//getMonth
int Date::getDay() const {
return day;
}//
int Date::getYear() const {
return year;
}//getYear
string Date::toString() const {
stringstream oss; //a stream to append the values
oss<<month<<"/"<<day<<"/"<<year;
return oss.str();
}
bool Date::operator==(const Date& otherDate) {
return (month==otherDate.month && day==otherDate.day && year==otherDate.year);
}//operator ==
bool Date::operator<(const Date& otherDate) {
//A date is less than another date if is earlier
bool result=false; //assume false until proven true
if(year<otherDate.year) result=true;
else if(year==otherDate.year && month<otherDate.month) result=true;
else if(year==otherDate.year && month==otherDate.month && day<otherDate.day) result=true;
return result;
}//operator
bool Date::operator>(const Date& otherDate) {
//Convert both dates to Julian and compare the Julian dates
int jd1=julian();
int jd2=otherDate.julian();
return jd1>jd2;
}//operator
ostream& operator << (ostream &output, const Date &d) {
output << d.toString();
return output;
} // operator <<
istream& operator >> (istream &input, Date &d) {
string s;
input >> s;
Date other(s); //create a new Date
d=other; //assign the new Date to d
return input;
} // operator >>
// Added overloaded operators
bool Date::operator>=(const Date& otherDate) {
// Convert dates to Julian and then compare dates
int jd1 = julian();
int jd2 = otherDate.julian();
return jd1 >= jd2;
}// oerator >=
bool Date::operator<=(const Date& otherDate) {
// Convert dates to Julian and then compare dates
int jd1 = julian();
int jd2 = otherDate.julian();
return jd1 <= jd2;
}// operator <=
bool Date::operator!=(const Date& otherDate) {
// Convert dates to Julian and then compare dates
int jd1 = julian();
int jd2 = otherDate.julian();
return jd1 != jd2;
}// operator !=
// Added functions or methods
// Function to retrive Thanks Giving Day for year entered
Date Date::thanksGiving(int year)
{
Date turkeyDay(11, 01, year);
while (turkeyDay.weekday() != 4)
{
turkeyDay = turkeyDay + 1;
}
turkeyDay = turkeyDay + 21;
return turkeyDay;
}
// Seasons function difinition
int seasons(Date date) {
// Declare season objects with season start dates
Date spring("04/20/2018"), summer("06/20/2018"),
fall("09/22/2018"), winter("12/21/2018");
int seas = 0; // Return variable
// Check for season between season start dates
if ((date >= spring) && (date < summer)) {
seas = 0; // set to spring
}
else if ((date >= summer) && (date < fall)) {
seas = 1; // set to summer
}
else if ((date >= fall) && (date < winter)) {
seas = 2; // set to fall
}
else {
seas = 3; // set to winter if no other selected
}
return seas; // Return season
}// End of seasons
// Bubble Sort Function
void bubbleSort(Date holidays[], string names[], int n)
{
// Loop counters
int i, j;
// Iterate from first element to the last element
for (i = 0; i < n - 1; i++)
// Last i elements will move in place
for (j = 0; j < n - i - 1; j++)
// Check to see if first date is greater than next date
if (holidays[j] > holidays[j + 1])
{
// If true swap date positions
Date temp = holidays[j];
holidays[j] = holidays[j + 1];
holidays[j + 1] = temp;
// Keep holiday names and holiday dates ralated by swapping
string tempStr = names[j];
names[j] = names[j + 1];
names[j + 1] = tempStr;
}
}// End of bubble sort
Explanation / Answer
Correct implementation of quicksort and partition funtion is provided below
template<class T>
void quickSort(vector<T>person , int start, int last)
{
if(start<last)
{
int pi = partition(person, start, last);
//sort the elements before and after partition separately
quickSort(person, start, pi-1);
quickSort(person, pi+1, last);
}
}
template<class T>
int partition(vector<T> person, int start, int last)
{
T pivot = person.at(last);
int i = start -1;
for(int j=start; j<last-1; j++)
{
if(person.at(j) <= pivot)
{
i++;
swap( person.at(i) , person.at(j) );
}
}
swap(person.at(i+1) , person.at(last) );
return (i+1);
}