.. highlight:: c++

Chapter 10 Notes
================

Please read chapter 10.1 of the textbook. You do not need to read sections
10.2 and onwards (at least for this course --- classes will be a topic in
later courses).


Structures
----------

in C/C++, a ``struct`` is used to define a collection of (often different)
values

for example

::

    struct Person {
      string name;
      int age;
    };  // note the semi-colon: it's an error to leave it out!

we use it to create variables of type ``Person``

::

    Person p{"Bill", 61};

    cout << p.name << "\n"  // Bill
         << p.age << "\n";  // 61

    p.name = "William";
    p.age++;

    cout << p.name << "\n"  // William
         << p.age << "\n";  // 62

we use the dot-notation to access the members of ``p``


Structures
----------

it's usually best to use the {}-notation to provide initial values to a
structure as we have been doing

however, the {}-notation is new in C++11, and doesn't work in C or older
versions of C++

in that case you can do something like this

::

    Person p;  // p.name and p.age have unknown values

    p.name = "Bill";
    p.age = 61;
    cout << p.name << "\n"  // Bill
         << p.age << "\n";  // 61

in C++11, it is almost always best to use the {}-notation to ensure your
structures have sensible initial values

unknown initial values can be the source of subtle errors!


Passing a Structure to a Function
---------------------------------

you can pass structures to functions

::

    void print1(Person p) {    // p is passed by value;
      cout << p.name << "\n"   // i.e. a copy of p is made
           << p.age << "\n";
    }

    void print2(Person& p) {   // p is passed by reference;
      cout << p.name << "\n"   // i.e. no copy of p is made
           << p.age << "\n";
    }

    void print3(const Person& p) {  // p is passed by constant
      cout << p.name << "\n"        // reference; i.e. no copy is made
           << p.age << "\n";        // and the compiler ensures p is not
    }                               // modified

for ``print``, the best way to pass ``p`` is by constant reference here to
avoid making a copy of the data in ``p``

this avoids making a copy and tells any other programmer that use ``print``
that they don't need to worry about it modifying the ``Person`` struct passed
to it


Examples of Structures: dates
-----------------------------

times and dates are a surprisingly complex topic

here lets look at a simple representation of a date as a struct of integers

::

    struct Date {
      int day;    // starts at 1
      int month;  // starts at 1
      int year;
    };  // don't forget the semi-colon!

a ``Date`` struct is essentially a triple of 3 integers

(8, 11, 2014) is November 8th, 2014

(16, 7, 1969) is July 16th, 1969

not all triples of numbers are valid dates

(31, 4, 2011) is an invalid date: there is no April 31st

(29, 2, 1900) is an invalid date: there was no February 29th in 1900

recognizing *all* valid dates is tricky!



Examples of Structures: dates
-----------------------------

the following programs shows some simple code for processing dates

it includes an incomplete date validity checker (it doesn't handle leap years)

it prints dates in only two different formats (there are many different date
formats!)

::

    // dates.cpp

    #include "cmpt_error.h"
    #include <iostream>
    #include <vector>

    using namespace std;

    struct Date {
      int day;
      int month;
      int year;
    };  // don't forget the semi-colon!

    const vector<string> months = {
      "January", "February", "March", "April",
      "May", "June", "July", "August",
      "September", "October", "November", "December"
    };

    // Returns true if d holds a valid date, and false otherwise.
    // Numbering starts at 1 for both days and months.
    // Does *not* handle leap years!
    bool is_valid(const Date& d) {
      // first check that basic ranges are satisfied
      if (d.day < 1 || d.day > 31) return false;
      if (d.month < 1 || d.month > 12) return false;
      if (d.year < 0) return false;

      // different months have different numbers of days
      // 28 days: feb (leap years are not handled!)
      // 30 days: apr, jun, sep, nov
      // 31 days: all other months
      switch (d.month) {
        case 2:
          return d.day <= 28;
        case 4: case 6: case 9: case 11:
          return d.day <= 30;
        default:
          return true;
      }
    }

    string get_month(const Date& d) {
      if (!is_valid(d)) {
        cmpt::error("invalid date");
      }
      return months[d.month - 1];
    }

    string get_day_ordinal(const Date& d) {
      if (!is_valid(d)) {
        cmpt::error("invalid date");
      }
      if (d.day == 11 || d.day == 12 || d.day == 13) {
        return "th";
      }
      int last_digit = d.day % 10;
      switch (last_digit) {
        case 1: return "st";
        case 2: return "nd";
        case 3: return "rd";
        default: return "th";   
      }
    }

    void print(const Date& d) {
      cout << get_month(d) << " "
           << d.day << get_day_ordinal(d) << ", "
           << d.year;
    }

    void println(const Date& d) {
      print(d);
      cout << "\n";
    }

    void print_raw(const Date& d) {
      cout << "(" 
           << d.day   << ", "
           << d.month << ", "
           << d.year  << ")";
    }

    void println_raw(const Date& d) {
      print_raw(d);
      cout << "\n";
    }

    int main() {
      for(int i = 1; i < 31; ++i) {
        Date d{i, 11, 2014};
        print(d);
        cout << "  ";
        println_raw(d);
      }
    }


Structures within Structures
----------------------------

you can put structures within structures when it makes sense

::

    struct Point {
      double x;
      double y;
    };  // don't forget the semi-colon!


    struct Circle {
      Point center;
      double radius;
    };  // don't forget the semi-colon!


    struct Rectangle {
      Point corner;
      double width;
      double height;
    };  // don't forget the semi-colon!

both circles and rectangles have constraints on the values they can take on

so lets write some checking functions to test that they are valid

::

    bool valid_circle(const Circle& c) {
      return c.radius > 0.0;
    }

    bool valid_rectangle(const Rectangle& r) {
      return r.width > 0.0 && r.height > 0.0;
    }

next, lets write functions to calculate perimeters and areas

::

    // Pre-condition:
    //    c.radius > 0
    // Post-condition:
    //    returns the area of c
    double perimeter(const Circle& c) {
      if (!valid_circle(c)) cmpt::error("invalid circle");
      return 2.0 * 3.1415926 * c.radius;
    }

    // Pre-condition:
    //    c.radius > 0
    // Post-condition:
    //    returns the area of c
    double area(const Circle& c) {
      if (!valid_circle(c)) cmpt::error("invalid circle");
      return 3.1415926 * c.radius * c.radius;
    }


    // Pre-condition:
    //    c.radius > 0
    // Post-condition:
    //    returns the area of c
    double perimeter(const Rectangle& r) {
      if (!valid_rectangle(r)) cmpt::error("invalid rectangle");
      return 2.0 * (r.width + r.height);
    }

    // Pre-condition:
    //    c.radius > 0
    // Post-condition:
    //    returns the area of c
    double area(const Rectangle& r) {
      if (!valid_rectangle(r)) cmpt::error("invalid rectangle");
      return r.width * r.height;
    }

these functions have been written pretty carefully

notice that the documentation (pre-condition and post-condition) and error-
checking is longer than the function itself!

the if-statement at the start of each function does decrease the performance
of the functions

so it's possible in some applications this might cause the functions to run
too slowly

so you could remove the error checks, and run the risk of not catching errors

or, you could re-think how this code is designed and make it object-oriented

we won't do any object-oriented programming in this course, but it is worth
mentioning that, in this example, an object-oriented design could improve the
performance and keep the safety


Sorting with Structs
--------------------

the standard C++ ``sort`` is efficient and flexible

if you want to sort, say, a vector of structs, then you need to write a
comparison function

for example

::

    struct Date {
      int day;   // 1 <= day <= 31
      int month; // 1 <= month <= 12
      int year;  // 0 <= year
    }; 

    // Pre-condition:
    //    a and b are valid dates
    // Post-condition:
    //    returns true if a comes before b
    // Note:
    //    This is not necessarily the fastest way
    //    to compare two dates. The intention is for the
    //    code to be clear an explicit, so that it can
    //    be seen to be correct more easily.
    bool less_than(const Date& a, const Date& b) {
      if (a.year < b.year) return true;
      if (a.year > b.year) return false;
      
      // at this point we know a.year == b.year
      if (a.month < b.month) return true;
      if (a.month > b.month) return false;
      
      // at this point we know a.month == b.month
      if (a.day < b.day) return true;
      if (a.day > b.day) return false;
      
      // at this point we know a.day == b.day
      return false;
    }

    int main() {
      vector<Date> dates = {
        Date{1, 2, 3},
        Date{25, 12, 2014},
        Date{25, 12, 2016},
        Date{2, 9, 2014}
      };

      sort(dates.begin(), dates.end(), less_than);

      for(Date d : dates) {
        println(d); 
      }
    }

the ``println`` function used here is defined above

if you want the dates sorted from most recent to earliest, use ``reverse``

::

    sort(dates.begin(), dates.end(), less_than);
    reverse(dates.begin(), dates.end());


Structs and Pointers
--------------------

::

    struct Assignment {
      string name;        // e.g "Assignment 1"
      string short_name;  // e.g. "a1"
      int out_of;         // > 0
    };

we could use ``Assignment`` with pointers like this

::

    Assignment* a1 = new Assignment;  // a1 points to an Assignment

    (*a1).name = "Assignment 1";
    (*a1).short_name = "a1";
    (*a1).out_of = 10;

    cout << (*a1).name << "\n"
         << (*a1).short_name << "\n"
         << (*a1).out_of << "\n";

    delete a1;

here we create an ``Assignment`` object dynamically

``a1`` has the type "pointer to ``Assignment``"

``*a1`` has the type ``Assignment``

so to access the members of ``*a``, we use dot-notation, e.g. ``(*a).name``

the expression ``*a1.name`` is incorrect because in C++ the ``.`` operator has
higher precedence than the ``*`` operator, and so C++ evaluates ``a1.name``
first

but since ``a1`` is a pointer, it does not have a member called ``name``

so ``*a1.name`` causes an error, and we must use brackets to force ``*a1`` to
be evaluated first


Structs and Pointers
--------------------

pointers to structs are very common in C/C++ programs

the notation ``(*a1).name`` is awkward and hard to read

so C/C++ provide a special ``->`` operator for this case

``a1->name`` is the same as ``(*a1).name``

::

    Assignment* a1 = new Assignment;  // a1 points to an Assignment

    a1->name = "Assignment 1";
    a1->short_name = "a1";
    a1->out_of = 10;

    cout << a1->name << "\n"
         << a1->short_name << "\n"
         << a1->out_of << "\n";

    delete a1;

once you get used to it, the ``->`` is quite readable