.. highlight:: c++

Chapter 3 Notes
===============

Please read chapter 3 of the textbook.


True Tables for Boolean Expressions
-----------------------------------

boolean expressions are important in C++ because they appear in if-statements
and loops

recall that a boolean expression is an expression that evaluates to either
``true`` or ``false``

here are some examples

::

    true     // evaluates to true

    false    // evaluates to false

    5 == 5   // evaluates to true

    4 == 2   // evaluates to false

    5 != 5   // evaluates to false

    4 != 2   // evaluates to false

    2 <= 3   // evaluates to true

    5 <= 1   // evaluates to false

    true && true   // evaluates to true

    (x < 0) || (x > 1)  // value depends upon x
 
    !(x == y)           // value depends upon x and y

    (a == 0 && b == 0) || (a != 0 && b != 0) // value depends upon a and b

as with regular arithmetic expressions, parentheses can be used to change the
order of evaluation of sub-expressions


Truth Tables
------------

the logical operators ``&&`` (and), ``||`` (or), and ``!`` (not) are often
defined using truth tables

see p. 114 of the textbook


Operator Precedence
-------------------

C++ operators have different levels of precedence

in ``1 + 2 * 3``, ``*`` is evaluated before ``+`` because ``*`` has higher
precedence than ``+``

all C++ operators have a precisely defined precedence level

here are the precedence levels of a few important operators

::

    highest precedence (done first)

                unary operators: + - ++ -- ! 
    binary arithmetic operators: * / % 
    binary arithmetic operators: + - 
              boolean operators: < > <= >= 
              boolean operators: == != 
              boolean operators: && 
              boolean operators: ||

    lowest precedence (done last)

for example, consider the expression ``x + 1 > 2``

``+`` has a higher precedence than ``>``, so ``x + 1`` is evaluated first

then the result of ``x + 1`` is compared to 2

you could re-write the expression equivalently as ``(x + 1) > 2``


Short-Circuit Evaluation
------------------------

C++ uses a common trick to speed up evaluation of some expressions

consider the boolean expression ``true || E``, where ``E`` is some other
boolean expression (although we don't know exactly what it is, or what it
evaluates to)

no matter the value of ``E``, the expression ``true || E`` must be ``true``
because it starts with ``true``

so in this expression C++ does not even bother to evaluate ``E``!

similarly, an expression of the form ``false && E`` is always ``false``, and
so C++ does not evaluate ``E``


Short-Circuit Evaluation
------------------------

in general, when C++ evaluates the expression ``E1 || E2`` it first evaluates
``E1``

if ``E1`` is ``true`` then it stops and returns ``true`` for the entire
expression

otherwise, if ``E1`` is ``false``, then it evaluates ``E2``

similarly, when C++ evaluates the expression ``E1 && E2`` it first evaluates
``E1``

if ``E1`` is ``false`` then it stops and returns ``false`` for the entire
expression

otherwise, if ``E1`` is ``true``, then it evaluates ``E2``


Short-Circuit Evaluation
------------------------

short-circuit evaluation can speed up the evaluation of some boolean
expressions

it also forces the order in which the sub-expressions of boolean expressions
are checked


Integers as Boolean Values
--------------------------

C++ lets you use integers as boolean values

this is how things were traditionally done in C (and C++ inherits almost
everything from C)

the integer 0 is considered to be ``false``, and every other non-0 integer is
considered to be ``true``

so you can write expressions like this

::

    (0 && -6) || 5   // same as (false && true) || true

    !52              // same as !true

however, while this is allowed in C++, it is rarely a good idea to do this

using integers as booleans can be quite confusing

it makes your code harder to understand, which in turn makes your code harder
to debug and modify


Enumeration Types
-----------------

an enumeration type is way to create your own data type

enumeration types are useful when you want a type for a small, finite series
of values

::

    // C++11-style enumerations
    enum class Day { Sun, Mon, Tue, Wed, Thu, Fri, Sat };

    Day today = Day::Mon;  // must put Day:: at start of Day values

C++ also supports older, C-style enumerations, e.g.

::

    enum Direction { NORTH = 0, SOUTH = 1, EAST = 2, WEST = 3 };

C-style enumerations pretty much just give names to integers

in C++11, you should almost always prefer the ``enum class`` enumerations

they are usually clearer, and help catch more errors than C-style enumerations


Enumeration Types
-----------------

the use of ``Day::`` to access the values of ``Day`` seems a bit inconvenient

but it allows different enumeration types to use values with the same name,
e.g.

::

    // enum.cpp

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

    using namespace std;

    // C++11-style enumerations
    enum class Day { sun, mon, tue, wed, thu, fri, sat };

    enum class Solar_obj {sun, moon, earth};

    int main() {
        Day today = Day::sun;  // must put Day:: at start of Day values

        if (today == Day::sun) {
            cout << "Sunday\n";
        } else if (today == Day::mon) {
            cout << "Monday\n";
        } else if (today == Day::tue) {
            cout << "Tuesday\n";
        } else if (today == Day::wed) {
            cout << "Wednesday\n";
        } else if (today == Day::thu) {
            cout << "Thursday\n";
        } else if (today == Day::fri) {
            cout << "Friday\n";
        } else if (today == Day::sat) {
            cout << "Saturday\n";
        }

        // There is no confusion between Day::sun and Solar_obj::sun.
        Solar_obj obj = Solar_obj::sun;  // Must put Solar_obj:: at start 
                                         // of Solar_obj values
        if (obj == Solar_obj::sun) {
            cout << "The Sun\n";
        } else if (obj == Solar_obj::moon) {
            cout << "The Moon\n";
        } else if (obj == Solar_obj::earth) {
            cout << "The Earth\n";
        }
    } // main


Multi-way if-statements
-----------------------

one common use of if-statements is to check the value of a variable

and then to do different things depending upon that value

::

    // simple_arith.cpp

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

    using namespace std;

    int main() {
        while (true) {  // loop forever (infinite loop)
            cout << "eval> ";
            double x, y;
            char op;
            cin >> x >> op >> y;

            if (op == '+') {
                cout << x + y;
            } else if (op == '-') {
                cout << x - y;
            } else if (op == '*') {
                cout << x * y;
            } else if (op == '/') {
                cout << x / y;
            } else {
                cout << "Sorry, I don't know the operator " << op;
            }
            cout << '\n';
        } // while
    }


Multi-way if-statements
-----------------------

if there's only one statement in the body of an if-statement, then the braces
are not required

::

    if (op == '+')
        cout << x + y;
    else if (op == '-')
        cout << x - y;
    else if (op == '*')
        cout << x * y;
    else if (op == '/')
        cout << x / y;
    else
        cout << "Sorry, I don't know the operator " << op;

this is nicer to read

but don't forget to add the braces back in when you add new statements!

::

    if (op == '+')
        cout << x + y;
    else if (op == '-')
        cout << x - y;
    else if (op == '*')
        cout << x * y;
    else if (op == '/')
        cout << x / y;
    else
        cout << "Sorry, I don't know the operator " << op;
        cout << "\nI only know +, -, *, and /\n";

don't be fooled by the indentation!

remember that C++ doesn't care about indentation when it comes to determining
blocks of code

the new ``cout`` statement is **not** part of the ``else`` body

instead, the new ``cout`` statement is the first statement after the entire
if-else-if statement, and so it *always* executed

the correct way to write this is with braces

::

    if (op == '+')
        cout << x + y;
    else if (op == '-')
        cout << x - y;
    else if (op == '*')
        cout << x * y;
    else if (op == '/')
        cout << x / y;
    else {
        cout << "Sorry, I don't know the operator " << op;
        cout << "\nI only know +, -, *, and /\n";
    }

because of this problem, it's usually wise to *always* uses braces even if
they are not necessary

then you have one less problem to worry about in your code!

::

    if (op == '+') {
        cout << x + y;
    } else if (op == '-') {
        cout << x - y;
    } else if (op == '*') {
        cout << x * y;
    } else if (op == '/') {
        cout << x / y;
    } else {
        cout << "Sorry, I don't know the operator " << op;
        cout << "\nI only know +, -, *, and /\n";
    }


The switch Statement
--------------------

the switch can be useful to make decisions based on integers or characters

::

    int main() {
        cout << "eval> ";
        double x, y;
        char op;
        cin >> x >> op >> y;

        switch (op) {
            case '+':
                cout << x + y;
                break;
            case '-':
                cout << x - y;
                break;      
            case '*':
                cout << x * y;
                break;      
            case '/':
                cout << x / y;
                break;
            default:
                cout << "Sorry, I don't know the operator " << op;
        }
        cout << '\n';
    }

notice the use of ``break`` --- that's important!

if you forget ``break`` in a ``switch`` statement, then the flow of control
"falls through" to the next case (!)

``switch`` statements only work with integer types, such as ``int`` and
``char``

we will mostly avoid them in this course

they are sometimes a little more readable than if-statements, and possibly a
little more efficient, but they are less flexible and tend to be more error-
prone


The switch Statement
--------------------

``switch`` statements can be used with enumerated types

::

    enum class Day { sun, mon, tue, wed, thu, fri, sat };

    Day today = Day::sun;
    switch (today) {
        case Day::sun:
            cout << "Sunday\n";
            break;
        case Day::mon:
            cout << "Monday\n";
            break;
        case Day::tue:
            cout << "Tuesday\n";
            break;
        case Day::wed:
            cout << "Wednesday\n";
            break;
        case Day::thu:
            cout << "Thursday\n";
            break;
        case Day::fri:
            cout << "Friday\n";
            break;
        case Day::sat:
            cout << "Saturday\n";
            break;
    }


Loops
-----

as we've seen, loops execute a block of code 0 or more times

we saw some examples of ``while`` loops earlier

C++ also has for-loops and do/while loops

for-loops come in two flavours: regular, and ranged

ranged for-loops are new in C++11, while regular for-loops are essentially a
tidier version of a while-loop

do/while loops are just like while-loops, except the condition is checked at
the bottom instead of the top

we won't use do/while loops much, if at all, in this course


While Loops
-----------

this program prints the square of the numbers from 1 to 10

::

    int main() {
        int i = 1;  // i is the loop index variable
        while (i < 11) {
            cout << i << " * " << i << " = " << i * i << "\n";
            ++i;
        }
        cout << "done\n";
    }

notice that ``i`` is initialized to 1

that's because we decided this program should start at 1

notice that the condition for the loop is ``i < 11``

that's because we want 10 to be the last value of ``i`` that is squared

in other words, as long as ``i`` is less than 11, the loop body should be
repeated

we could have written the condition like this: ``i <= 10``

the statement ``++i`` adds 1 to ``i``

it's called the loop's increment statement

without it you'd have an **infinite loop** that runs forever


While Loops
-----------

while loops typically take this general form

::

    initialization_statement;

    while (condition) {
        statement_1;
        statement_2;
        // ...
        statement_n;

        increment;
    }

the exact details will vary depending upon the purpose of the loop

and somtimes a while-loop will not take this form

but in general, this is a good pattern to follow when writing loops


Increment Operators
-------------------

the expression ``++i`` adds 1 to the variable ``i``

``++`` is called the increment operator

``--`` is called the decrement operator

they are short and convenient and occur all the time in C++ code

you can use them inside expressions, e.g.

::

    int i = 1;
    int a = 5;

    cout << "i = " << i << "\n"
         << "a = " << a << "\n";
    // i = 1
    // a = 5

    a = a + ++i + 2;

    cout << "i = " << i << "\n"
         << "a = " << a << "\n";
    // i = 2
    // a = 9


Increment Operators
-------------------

the expression ``++i`` is called **pre**-increment

that's because ``++i`` first increments ``i``, and then returns the value of
``i``

the expression ``i++`` is called **post**-increment

that's because ``i++`` first increments ``i``, and then returns the value of
``i - 1`` (i.e. the value before the increment)

when used as statements, there's no difference between post-increment and pre-
increment

::

    int i = 0;
    ++i;  // i is now 1
    i++;  // i is now 2


Increment Operators
-------------------

but used in expressions, there are serious problems

often, the results are undefined, e.g.

::

    int i = 0;
    cout << ++i
         << "\n"
         << i
         << "\n";

this does not compile using our (strict) course makefile

the problem is that C++ cannot guarantee what, exactly, the value of ``i``
will be

many C/C++ programmers ignore this problem

but it can be a serious source of hard-to-find bugs

**rule of thumb**: **never** use increment (or decrement) operators **in an
expression**

in this course ambiguous use of increment/decrement operators will usually be
caught by our strict compiler options

this is a good thing that will stop you from writing buggy programs!


For Loops
---------

recall this general while-loop template 

::

    initialization_statement;

    while (condition) {
        statement_1;
        statement_2;
        // ...
        statement_n;

        increment;
    }

this happens frequently enough that C++ provides a special loop for this case

this is called a for-loop

here's the basic template

::

    for(initialization_statement; condition; increment) {
        statement_1;
        statement_2;
        // ...
        statement_n;
    }

this behaves the same way as the above while-loop

but the advantage is that all the loop-control information --- the
initialization condition, and increment --- are in one place at the top of the
loop


For Loops
---------

::

    int main() {
        cout << "How many iterations do you want? ";
        int n = 0;
        cin >> n;

        for(int i = 0; i < n; ++i) {
            cout << " i = " << i << "\n";
        }
        // cout << "i = " << i << "\n";
        cout << "Done!\n";
    }

compare this to an equivalent version using a for-loop

::

    int main() {
        cout << "How many iterations do you want? ";
        int n = 0;
        cin >> n;

        int i = 0;
        while (i < n) {
            cout << " i = " << i << "\n";
            ++i;
        }
        // cout << "i = " << i << "\n";
        cout << "Done!\n";
    }

there is subtle difference here

in the for-loop, the scope of the ``i`` variable is within the loop only

but in the while-loop version, you can access ``i`` after the loop


For Loops
---------

the parts of the for-loop header are optional

::

    cout << "How many iterations do you want? ";
    int n = 0;
    cin >> n;

    int i = 0;
    for(; i < n; ) {
        cout << " i = " << i << "\n";
        ++i;
    }
    cout << "Done!\n";

an idiomatic way to write an infinite loop (a loop that never stops) is this

::

    for(;;) { // infinite loop
        cout << "chugga chugga toot toot!\n";
    }

type ctrl-C to end this!


For Loops
---------

there's often multiple ways to write the same loop

for example, suppose you want to print a count-down from 10 to 1 for a rocket

::

    for(int i = 10; i > 0; --i) {
        cout << "... " << i << "\n";
    }
    cout << "Blast off!!\n";

here's another solution

::

    for(int i = 10; i >= 1; --i) {
        cout << "... " << i << "\n";
    }
    cout << "Blast off!!\n";

or even this

::

    for(int i = 0; i < 10; ++i) {
        cout << "... " << (10 - i) << "\n";
    }
    cout << "Blast off!!\n";

try to use the method that you find clearest and simplest

clear, simple code is almost always better than complicated and tricky code!


For Loops
---------

the condition for a for-loop can be more complex that checking the value of
the loop-control variable

as an example, lets write a program that takes a positive ``int`` as input and
prints all the *factors* of n like this

::

    Please enter a positive integer: 12
    12 = 1 * 12
    12 = 2 * 6
    12 = 3 * 4

an important requirement here is that the left factor must be less than, or
equal to, the right factor

so a line like "12 = 4 * 3" should **not** be printed

::

    // factors.cpp

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

    using namespace std;

    int main() {
        cout << "Please enter a positive integer: ";
        int n;
        cin >> n;
        if (n <= 0) {
            cout << n << "isn't big enough!\n";
        } else {
            for(int factor = 1; factor * factor <= n; ++factor) {
                if (n % factor == 0) { // test if n is a multiple of factor
                    int a = factor;
                    int b = n / factor;
                    cout << n << " = " << a << " * " << b << "\n";
                } // if
            } // for
        } // if
    } // main

notice how we use comments to label all the ``}``\ s at the end of the program

this helps ensure that the close braces are paired correctly with their open
braces

we also can't easily predict how many lines this program will print!

the for-loop condition handles it correctly, though


Example: 2-digit Numbers Divisible by their Digit Sum
-----------------------------------------------------

loops can appear with in loops

this can be quite confusing, so use nested loops with care

for example, suppose you want to solve this mathematical problem

    what are all the 2-digit integers, i.e. 11 to 99, that are divisible by
    the sum of their digits?

one solution to this problem is this

::

    int main() {
        int count = 0;
        for(int a = 1; a < 10; ++a) {
            for(int b = 1; b < 10; ++b) {
                int n = 10 * a + b;
                if (n % (a + b) == 0) {
                    cout << n << " is divisible by the sum of its digits\n";
                    ++count;
                }
            }
        }
        cout << "count = " << count << "\n";
    } // main

this code has a for-loop within a for-loop

the variables ``a`` and ``b`` each range over all possible digits

which we can use to create all numbers 11 to 99

nested loops are tricky in general!


Example: Sum of the Digits of a Positive int
--------------------------------------------

Write a program that prints all the digits of a positive ``int``, along with
their sum. Use only basic C++ operators in your answer. Don't use strings or
any functions from other files (like ``cmath``).

For example, given the int 38722, your programs should print::

     2 
     2 
     7 
     8 
     3
     sum = 22

Sample solution::

    #include <iostream>

    using namespace std;

    int main() {
        cout << "What is n? ";
        int n = 0;
        cin >> n;
        cout << "n=" << n << "\n\n";

        if (n == 0) {
            cout << 0 << "\n";
            cout << "sum = 0\n";
        } else {
            int sum = 0;
            // n = 1234
            while (n > 0) {
                // get the ones digit
                int ones = n % 10;
                
                // print it
                cout << ones << "\n";

                sum += ones;

                // remove ones digit from n
                n = (n - ones) / 10;
            } // while
            cout << "sum = " << sum << "\n";
        } // if
    }


Example: Printing a Triangle of Stars
-------------------------------------

Write a program that reads a positive ``int``, n, from the user, and prints a
triangle of stars, with 1 star in the first two, 2 in the second, and so on.
For example, if n=4, then your program should print this::

        *
        **
        ***
        ****

Sample solution::

    // stars.cpp

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

    using namespace std;

    int main() {
        cout << "How many rows do you want? ";
        int num_rows = 0;
        cin >> num_rows;
        for(int i = 0; i < num_rows; ++i) {
            int num_stars = i + 1;
            for(int j = 0; j < num_stars; ++j) {
                cout << '*';
            }
            cout << "\n";
        }
    } // main


Example: Sum of Numbers Entered by the User
-------------------------------------------

Write a program that prints the sum of ``double``\_s entered by the user. Use
the number -1 to indicate the end of the numbers. For example::

        Please enter some numbers:
        1.2
        -1.2
        3
        0
        4.5
        -1
        sum = 7.5

The -1 is *not* included in the sum.

Sample solution (while loop)::

    #include <iostream>

    using namespace std;

    int main() {
        cout << "Enter some numbers (-1 to end): ";
        double x = 0.0;
        double sum = 0.0;
        while (x != -1) {
            sum += x;
            cin >> x;
        }
        cout << "sum = " << sum << "\n";
    }


Sample solution (for loop)::

    #include <iostream>

    using namespace std;

    int main() {
        cout << "Enter some numbers (-1 to end): ";
        double sum = 0.0;
        for(double x = 0.0; x != -1; cin >> x) {
            sum += x;
        }
        cout << "sum = " << sum << "\n";
    }


Example: All 3-letter Strings
-----------------------------

Write a program that prints all 17,576 3-letter strings consisting of lower-
case letters a to z. The first few strings are::

      aaa
      aab
      aac
      aad
      ...

Sample solution::

    // three_letters.cpp

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

    using namespace std;

    int main() {
        int count = 0;
        for(char a = 'a'; a <= 'z'; ++a) {
            for(char b = 'a'; b <= 'z'; ++b) {
                for(char c = 'a'; c <= 'z'; ++c) {
                    cout << a << b << c << "\n";
                    count++;
                }
            }
        }
        cout << "count = " << count << "\n";
    } // main


Ranged for-loops
----------------

when we get to vectors and arrays, we'll see an alternate form of for-loop
called a ranged for-loop

ranged for-loops are a more convenient way to loop over the data in an array
or vector


What Kind of Loop to Use?
-------------------------

we've seen while loops, do/while loops, and for-loops

do/while loops occasionally have their uses, but you probably just avoid them

the problem with do/while loops is that they test their condition at the
bottom

and that's rarely what you want

and even when you do think you need a do/while loop, you often end up adding
if-statements near the top to make it simulate a regular while-loop!

so a good rule of thumb is: never use do/while loops


What Kind of Loop to Use?
-------------------------

so should you use for-loops or while-loops?

if you can only pick one, use a for-loop

a for-loop does everything a while-loop does, but it is more readable because
all the loop-control information is one place

sometimes, though, a while-loop will result in easier-to-read code

one kind of case is when the increment, or initialization, of the loop is
complex and needs more than one statement


The break Statement
-------------------

we've already seen the ``break`` statement inside of a ``switch``

a ``break`` statement can also be used to make the flow of control immediately
jump out of a loop

::

    int sum = 0;
    int count = 0;
    for (;;) {
        cout << "Please enter a positive integer (0 to quit): ";
        int n = 0;
        cin >> n;
        if (n == 0) {
            break;  // jump out of the loop
        } else if (n < 0) {
            cout << n << " is not a positive integer!\n";
            break;  // jump out of the loop
        } else {
            sum += n;
            ++count;
        }
    }
    cout << "Done!\n";

    double avg = double(sum) / count;
    cout << "You entered " << count << " positive integers.\n";
    cout << "Their sum is " << sum << ".\n";
    cout << "Their average is " << avg << ".\n";

generally, using ``break`` like this is a bad idea

it usually makes loops harder to understand, especially if you have more than
one ``break``

it's better if the only way to get out of a loop is because its condition is
false

that will help you understand what the loop is doing, which aids in debugging


The break Statement
-------------------

here is one alternative that avoids ``break``

::

    int sum = 0;
    int count = 0;
    bool done = false;
    while (!done) {  // while "done is not false" do the following ....
        cout << "Please enter a positive integer (0 to quit): ";
        int n = 0;
        cin >> n;
        if (n == 0) {
            done = true;  // jump out of the loop
        } else if (n < 0) {
            cout << n << " is not a positive integer!\n";
            done = true;  // jump out of the loop
        } else {
            sum += n;
            ++count;
        }
    }
    cout << "Done!\n";

    double avg = double(sum) / count;
    cout << "You entered " << count << " positive integers.\n";
    cout << "Their sum is " << sum << ".\n";
    cout << "Their average is " << avg << ".\n";

this uses a flag variable called ``done``

the idea is to set ``done`` to true when the loop is finished

it's initially ``false`` to ensure the loop iterates at least once

flag variables like ``done`` are a usually technique to remember when writing
loops

they can be useful when a loop has a complex stopping condition that doesn't
easily fit into the loop-condition


Designing Loops
---------------

mastering loops is hard because there are so many ways to write them

but you always need to think about, at least, these three things with any loop

- what is the "setup" for the loop, i.e. what variables does it need and what
  are their initial values

- what work should be done on each iteration of the loop

- when, exactly, does the loop stop

in general, writing loops is one of the more challenging parts of programming

they are hard to visualize, and thus hard to debug

as we continue in this course, we will learn standard patterns for writing
loops