#include <iostream>
#include <string>

//--------------------------------------------------------------------------
// Data Definition
// ---------------
//  A date is a structure consisting of
//      - day as number
//      - month as number
//      - year as number
//--------------------------------------------------------------------------
struct Date
{
    int day;
    int month;
    int year;
};

//--------------
// Data Example
//--------------
Date date_1 = {  3, 4, 1900 };
Date date_2 = {  2, 7, 1945 };
Date date_3 = { 12, 4, 1996 };
Date date_4 = {  9, 5, 2000 };

//--------------
// Code Pattern
//--------------
// ... F(Date d)
// {
//     ... d.day ...
//     ... d.month ...
//     ... d.year ...
// }

//--------------------------------------------------------------------------
// Data Definition
// ---------------
// A student record (SR) is a structure consisting of
//      - student id as number
//      - student first name as string
//      - student last name as string
//      - student Phone number as number
//      - student birthday as Date
//--------------------------------------------------------------------------
struct StudentRecord
{
    int             id;
    std::string     firstName;
    std::string     lastName;
    int             Phone;
    Date            birthday;
};

//--------------
// Data Example
//--------------
StudentRecord student_1 = { 123456, "Tom", "Cruise",  345463474, { 10, 9, 1960 } };
StudentRecord student_2 = { 322344, "Brad", "Pitt",   523452345, {  3, 5, 1967 } };
StudentRecord student_3 = { 547824, "Val", "Klimmer", 136564566, { 25, 7, 1965 } };

//--------------
// Code Pattern
//--------------
// ... G(StudentRecord r)
// {
//     ... r.id ...
//     ... r.lastName ...
//     ... r.firstName ...
//     ... r.Phone ...
//     ... F(r.birthday) ...
// }

//--------------------------------------------------------------------------
// Data Definition
// ---------------
// A list of student records is either
//      - an empty list
//  or a structure consisting of
//      - first as StudentRecord
//      - last as ListOfStudentRecord
//--------------------------------------------------------------------------
struct ListOfStudentRecord
{
    StudentRecord           first;
    ListOfStudentRecord     *rest;
};

//--------------
// Data Example
//--------------
ListOfStudentRecord *empty = 0;
ListOfStudentRecord list_1 = { student_1, empty };
ListOfStudentRecord list_2 = { student_2, &list_1 };
ListOfStudentRecord list_3 = { student_3, &list_2 };

//--------------
// Code Pattern
//--------------
// ... H(ListOfStudentRecord * L)
// {
//      if (L == 0)
//      {
//          ...
//      }
//      else
//      {
//          ... G(L->first) ...
//          ... H(L->rest) ...
//      }
// }

//--------------------------------------------------------------------------
// Prototypes
//--------------------------------------------------------------------------
bool isLeapYear(Date d);
int nDay(Date d);
int leapDay(Date d);
bool older(Date d1, Date d2);
int findOldestHelper(ListOfStudentRecord * L, StudentRecord r);
int findOldest(ListOfStudentRecord * L);
std::string findFirstPhoneHelper(ListOfStudentRecord * L, StudentRecord r);
std::string findFirstPhone(ListOfStudentRecord * L);

//--------------------------------------------------------------------------
// main
//--------------------------------------------------------------------------
int main()
{
    std::cout << "isLeapYear(date_1) == " << std::boolalpha << isLeapYear(date_1) << "\n";
    std::cout << "isLeapYear(date_2) == " << std::boolalpha << isLeapYear(date_2) << "\n";
    std::cout << "isLeapYear(date_3) == " << std::boolalpha << isLeapYear(date_3) << "\n";
    std::cout << "isLeapYear(date_4) == " << std::boolalpha << isLeapYear(date_4) << "\n";

    std::cout << "leapDay(date_1) == " << leapDay(date_1) << "\n";
    std::cout << "leapDay(date_2) == " << leapDay(date_2) << "\n";
    std::cout << "leapDay(date_3) == " << leapDay(date_3) << "\n";
    std::cout << "leapDay(date_4) == " << leapDay(date_4) << "\n";

    std::cout << "nDay(date_1) == " << nDay(date_1) << "\n";
    std::cout << "nDay(date_2) == " << nDay(date_2) << "\n";
    std::cout << "nDay(date_3) == " << nDay(date_3) << "\n";
    std::cout << "nDay(date_4) == " << nDay(date_4) << "\n";

    std::cout << "older(date_1, date_2) == " << std::boolalpha << older(date_1, date_2) << "\n";
    std::cout << "older(date_1, date_3) == " << std::boolalpha << older(date_1, date_3) << "\n";
    std::cout << "older(date_2, date_3) == " << std::boolalpha << older(date_2, date_3) << "\n";

    std::cout << "findOldestHelper(empty, student_2) == " << findOldestHelper(empty, student_2) << "\n";
    std::cout << "findOldestHelper(list_1, student_2) == " << findOldestHelper(&list_1, student_2) << "\n";
    std::cout << "findOldestHelper(list_2, student_2) == " << findOldestHelper(&list_2, student_2) << "\n";
    std::cout << "findOldestHelper(list_3, student_2) == " << findOldestHelper(&list_3, student_2) << "\n";

    std::cout << "findOldest(empty) == " << findOldest(empty) << "\n";
    std::cout << "findOldest(&list_1) == " << findOldest(&list_1) << "\n";
    std::cout << "findOldest(&list_2) == " << findOldest(&list_2) << "\n";
    std::cout << "findOldest(&list_3) == " << findOldest(&list_3) << "\n";

    std::cout << "findFirstPhoneHelper(empty, student_2) == " << findFirstPhoneHelper(empty, student_2) << "\n";
    std::cout << "findFirstPhoneHelper(&list_1, student_2) == " << findFirstPhoneHelper(&list_1, student_2) << "\n";
    std::cout << "findFirstPhoneHelper(&list_2, student_2) == " << findFirstPhoneHelper(&list_2, student_2) << "\n";
    std::cout << "findFirstPhoneHelper(&list_3, student_2) == " << findFirstPhoneHelper(&list_3, student_2) << "\n";

    std::cout << "findFirstPhone(empty) == " << findFirstPhone(empty) << "\n";
    std::cout << "findFirstPhone(&list_1) == " << findFirstPhone(&list_1) << "\n";
    std::cout << "findFirstPhone(&list_2) == " << findFirstPhone(&list_2) << "\n";
    std::cout << "findFirstPhone(&list_3) == " << findFirstPhone(&list_3) << "\n";

    return 0;
}

//--------------------------------------------------------------------------
// @description check whether a year is a leap year
// @param d a date
// @return true if d is a leap year, false otherwise
// @contract isLeapYear : Date -> boolean
// @example isLeapYear(date_1) == false
// @example isLeapYear(date_2) == false
// @example isLeapYear(date_3) == true
// @example isLeapYear(date_4) == true
//--------------------------------------------------------------------------
bool isLeapYear(Date d)
{
    return (d.year % 400 == 0) ||
            ((d.year % 100 != 0) && (d.year % 4 == 0));
}

//--------------------------------------------------------------------------
// @description calculate the leap day
// @param d a date
// @return 1 if d is a leap year, 0 otherwise
// @contract leapDay : Date -> int
// @example leapDay(date_1) == 0
// @example leapDay(date_2) == 0
// @example leapDay(date_3) == 1
// @example leapDay(date_4) == 1
//--------------------------------------------------------------------------
int leapDay(Date d)
{
    if (isLeapYear(d))
        return 1;
    else
        return 0;
}

//--------------------------------------------------------------------------
// @description calculate the number of days since the new year
// @param d a date
// @return the number of days since the new year
// @contract nDay : Date -> number
// @example nDay(date_1) == 31 + 28 + 31 + 3 == 93
// @example nDay(date_2) == 31 + 28 + 31 + 30 + 31 + 31 + 2 = 184
// @example nDay(date_3) == 31 + 29 + 31 + 12 == 103
// @example nDay(date_4) == 31 + 29 + 31 + 30 + 9 == 130
//--------------------------------------------------------------------------
int nDay(Date d)
{
    if (d.month == 1)
        return d.day;
    else if (d.month == 2)
        return 31 + d.day;
    else if (d.month == 3)
        return 31 + 28 + d.day + leapDay(d);
    else if (d.month == 4)
        return 31 + 28 + 31 + d.day + leapDay(d);
    else if (d.month == 5)
        return 31 + 28 + 31 + 30 + d.day + leapDay(d);
    else if (d.month == 6)
        return 31 + 28 + 31 + 30 + 31 + d.day + leapDay(d);
    else if (d.month == 7)
        return 31 + 28 + 31 + 30 + 31 + 31 + d.day + leapDay(d);
    else if (d.month == 8)
        return 31 + 28 + 31 + 30 + 31 + 31 + 31 + d.day + leapDay(d);
    else if (d.month == 9)
        return 31 + 28 + 31 + 30 + 31 + 31 + 31 + 31 + d.day + leapDay(d);
    else if (d.month == 10)
        return 31 + 28 + 31 + 30 + 31 + 31 + 31 + 31 + 30 + d.day + leapDay(d);
    else if (d.month == 11)
        return 31 + 28 + 31 + 30 + 31 + 31 + 31 + 31 + 30 + 31 + d.day + leapDay(d);
    else
        return 31 + 28 + 31 + 30 + 31 + 31 + 31 + 31 + 30 + 31 + 30 + d.day + leapDay(d);
}

//--------------------------------------------------------------------------
// @description determine whether the first date is prior to the second date
// @param d1 the first date
// @param d2 the second date
// @contract older : Date Date -> boolean
// @return true if d1 < d2, false otherwise
// @example older(date_1, date_2) == true
// @example older(date_1, date_3) == true
// @example older(date_2, date_3) == false
//--------------------------------------------------------------------------
bool older(Date d1, Date d2)
{
    return (d1.year < d2.year) ||
           (d1.year == d2.year && nDay(d1) < nDay(d2));
}

//--------------------------------------------------------------------------
// @description find the id of the oldest student
// @param L a list of student records
// @param r the record of the oldest student so far
// @return the id of the oldest student
// @contract findOldestHelper : ListOfStudentRecord StudentRecord -> number
// @example findOldestHelper(empty, student_2) == 322344
// @example findOldestHelper(&list_1, student_2) == 123456
// @example findOldestHelper(&list_2, student_2) == 123456
// @example findOldestHelper(&list_3, student_2) == 123456
//--------------------------------------------------------------------------
int findOldestHelper(ListOfStudentRecord * L, StudentRecord r)
{
    if (L == 0)
    {
        return r.id;
    }
    else
    {
        if ( older(r.birthday, L->first.birthday) )
        {
            return findOldestHelper(L->rest, r);
        }
        else
        {
            return findOldestHelper(L->rest, L->first);
        }
    }
}

//--------------------------------------------------------------------------
// @description find the id of the oldest student
// @param L a list of student records
// @return 0 if the list is empty, otherwise the id of the oldest student
// @contract findOldest : ListOfStudentRecord -> number
// @example findOldest(empty) == 0
// @example findOldest(&list_1) == 123456
// @example findOldest(&list_2) == 123456
// @example findOldest(&list_3) == 123456
//--------------------------------------------------------------------------
int findOldest(ListOfStudentRecord * L)
{
    if (L == 0)
    {
        return 0;
    }
    else
    {
        return findOldestHelper(L->rest, L->first);
    }
}

//--------------------------------------------------------------------------
// @description find the last name of the student with the smallest Phone
//              number
// @param L a list of student records
// @param r a student record with the smallest Phone number so far
// @return "" if L is empty, otherwise, the last name of the student with
//         the smallest Phone number
// @contract findFirstPhoneHelper : ListOfStudentRecord -> string
// @example findFirstPhoneHelper(empty, student_2) == "Pitt"
// @example findFirstPhoneHelper(&list_1, student_2) == "Cruise"
// @example findFirstPhoneHelper(&list_2, student_2) == "Cruise"
// @example findFirstPhoneHelper(&list_3, student_2) == "Klimmer"
//--------------------------------------------------------------------------
std::string findFirstPhoneHelper(ListOfStudentRecord * L, StudentRecord r)
{
    if (L == 0)
    {
        return r.lastName;
    }
    else
    {
        if (L->first.Phone < r.Phone)
        {
            return findFirstPhoneHelper(L->rest, L->first);
        }
        else
        {
            return findFirstPhoneHelper(L->rest, r);
        }
    }
}

//--------------------------------------------------------------------------
// @description find the last name of the student with the smallest Phone
//              number
// @param L a list of student records
// @return "" if L is empty, otherwise, the last name of the student with
//         the smallest Phone number
// @contract findFirstPhone : ListOfStudentRecord -> string
// @example findFirstPhone(empty) == ""
// @example findFirstPhone(&list_1) == "Cruise"
// @example findFirstPhone(&list_2) == "Cruise"
// @example findFirstPhone(&list_3) == "Klimmer"
//--------------------------------------------------------------------------
std::string findFirstPhone(ListOfStudentRecord * L)
{
    if (L == 0)
    {
        return "";
    }
    else
    {
        return findFirstPhoneHelper(L->rest, L->first);
    }
}