CS 200: Concepts of Programming using C++ (Summer 2024 version) WORK IN PROGRESS

Table of Contents

semester-summer.png

Rachel Wil Sha Singh's Core C++ Course © 2024 by Rachel Wil Sha Singh is licensed under CC BY 4.0. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

\newpage

1. Navigating this course

Modules and unlocks

2. Summer 2024 Schedule

Week # Monday Topics
1 June 3 Unit 00: Welcome and setup
    Unit 01: C++: Variables, input, and output
    Unit 02: Tech Literacy: Exploring computers (fs, cli)
2 June 10 Unit 03: C++: Functions
    Unit 04: Tech Literacy: Debugging and researching
3 June 17 Unit 05: C++: Structs
    Unit 06: Tech Literacy: Careers in tech
4 June 24 Unit 07: C++: Looping
    Unit 08: C++: Arrays and vectors
5 July 1 Unit 09: C++: Branching
    Unit 10: C++ Searching and sorting
    Unit 11: Tech Literacy: Current trends in tech
6 July 8 Unit 12: Tech Literacy: Object Oriented Programming, UML
    Unit 13: C++: Classes and inheritance
7 July 15 Unit 14: C++: Strings and File I/O
    Unit 15: Tech Literacy: Ethics in tech
8 July 22 Unit 16: C++: Intro to recursion

\newpage

3. Reference

3.1. C++ quick reference

  • Starter C++ program:

    int main()               int main( int argCount, char* args[] )
    {                        {
      return 0;                return 0;
    }                        }
    
  • Declare a variable: DATATYPE VARIABLENAME;

    int myNumber;      string myString;      float myFloat;
    
  • Declare a variable and initialize it: DATATYPE VARIABLENAME = VALUE;

    int myNumber = 10;   string myString = "Hello!";    float myFloat = 9.99;
    char myChar = 'a';   bool myBool = true;
    
  • Declare a named constant: const DATATYPE NAME = VALUE;

    const int NUMBER = 10;      const string STATE = "Missouri";
    
  • Assign a value to a variable that has already been declared: VARIABLENAME = VALUE;

    myNumber = 100;             myString = "Goodbye";
    
  • Copy a value from one variable to another: UPDATEDVAR = COPYME;

    vipStudent = student3;
    
  • Output text to the console: cout << ITEM;

    • You can mix variables and string literals, as long as the stream operator << is between each item.
    cout << "Label: " << myVariable << endl;
    
  • Get input from the keyboard and store it in a variable: cin >> VARIABLENAME;

    cin >> myInteger;            cin >> myString;
    
  • Get a full line of text (with spaces) and store in a string: getline( cin, VARIABLENAME );

    getline( cin, myString );
    
    • Only works with string variables.
    • Note that if you have a cin >> statement immediately before the getline statement, your input will get skipped. In this case you need to add a cin.ignore() statement:

      cin >> myNumber;
      cin.ignore();
      getline( cin, myString );
      
  • If statements:

    if ( a == 1 )                     if ( a == 1 )
    {                                 {
      // Executes when a == 1           // Executes when a == 1
    }                                 }
                                      else
                                      {
                                        // Executes when a != 1
                                      }
    
    if ( a == 1 )                     if ( a == 1 )
    {                                 {
        // Executes when a == 1         // Executes when a == 1
    }                                 }
    else if ( a == 2 )                else if ( a == 2 )
    {                                 {
        // Executes when a != 1         // Executes when a != 1
        // and a == 2                   // and a == 2
    }                                 }
                                     else
                                     {
                                       // Executes when a != 1
                                       // and a != 2
                                     }
    
    • If: If the condition evaluates to true, then execute the code within the if statement. Otherwise, skip that code completely.
    • If/else: If the condition from if statement results to false, then the code in the else case is executed instead. No condition is written with the else case.
    • If/else if statement: Checks each condition in order. If one is true, then subsequent else if statements are ignored.
    • If/else if/else statement: Similar to above, but if all if and else if statements are false, then else is executed.
  • Switch statement: switch( VARIABLE ) { case VALUE: break; }

    • The switch variable can be int, char, but not string.
    switch( myNumber )
    {
      case 1:
        cout << "It's one!" << endl;
        break;
    
      case 2:
        cout << "It's two!" << endl;
        break;
    
      default:
        cout << "I don't know what it is!" << endl;
    }
    

3.1.1. Loops

Looping with While Loops

Runs 0 or more times, depending on whether the CONDITION is true.

while ( CONDITION ) { }

while ( a < b )
{
  cout << a << endl;
  a++;
}

Looping with Do…While Loops

Runs at least once and then continues looping if the condition is true.

do { } while ( CONDITION );

do {
  cout << "Enter a number: ";
  cin >> input;
 } while ( input < 0 || input > max );

Looping with For Loops

Iterate some amount of times through the loop based on your counter variable and range.

for ( INIT; CONDITION; UPDATE ) { }

for ( int i = 0; i < 10; i++ )
{
  cout << i << endl;
}

Looping with Range-Based For Loops

Iterates over all elements in a collection. Only moves forward, doesn't give access to index

for ( INIT : RANGE ) { }

vector<int> myVec = { 1, 2, 3, 4 };
for ( int element : myVec )
{
  cout << element << endl;
}

3.1.2. Arrays and Vectors

Declare a traditional C-style array

When declaring a vanilla array, you need to set its size. You can either hard-code the size with a number:

string arr[10];

Or use a named constant:

const int TOTAL_STUDENTS;
string students[TOTAL_STUDENTS];

Declare an STL array object Remember that you will need #include <array> at the top of your file to use the array object.

Declare an array object, passing in what the data type of it values are, and the size of the array:

array<float, 3> bankBalances;

Use the array documentation (https://cplusplus.com/reference/array/array/) for info on its functions.

Declare an STL vector object

vector<string> studentList;

Use the vector documentation (https://cplusplus.com/reference/vector/) for info on its functions.

Initialize array/vector with an initializer list

string cats1[] = { "Kabe", "Luna", "Pixel", "Korra" };
array<string,4> cats2 = { "Kabe", "Luna", "Pixel", "Korra" };
vector<string> cats3 = { "Kabe", "Luna", "Pixel", "Korra" };

Iterate over an array/vector

// C-style array:
for ( int i = 0; i < TOTAL_STUDENTS; i++ )
{
  cout << "index: " << i << ", value: " << students[i] << endl;
}

// STL Array and STL Vector:
for ( size_t i = 0; i < bankBalances.size(); i++ )
{
  cout << "index: " << i << ", value: " << students[i] << endl;
}

size_t is another name for an unsigned int, which allows values of 0 and above - no negatives.

3.1.3. File I/O

Make sure to have #include <fstream> in any files using ifstream or ofstream!

Create an output file and write

ofstream output;
output.open( "file.txt" );

// Write to text file
output << "Hello, world!" << endl;

Create an input file and read

ifstream input;
input.open( "file.txt" );
if ( input.fail() )
  {
    cout << "ERROR: could not load file.txt!" << endl;
  }
string buffer;

// read a word
input >> buffer;

// read a line
getline( input, buffer );

3.1.4. Functions

Prevent file duplication

When creating .h/.hpp files, it is important to include these lines to prevent file duplication, which happens if you #include this file in more than one place.

#ifndef _FILENAME_H // LABEL SHOULD BE UNIQUE FOR EACH .h FILE!
#define _FILENAME_H

// Code goes here

#endif

Function declaration

A function declaration contains the function header and no body. It declares that the function exists and will be defined elseware.

void DisplayMenu();
int Sum(int a, int b);

Function definition

A function definition defines how the function operates. It includes the function header and a function body, which has commands in it.

void DisplayMenu()
{
  cout << "1. Deposit" << endl;
  cout << "2. Withdraw" << endl;
  cout << "3. Quit" << endl;
}

int Sum(int a, int b)
{
  return a + b;
}

Calling a function

Calling a function requires invoking the function's name and passing in any arguments.

DisplayMenu();

int result = Sum( 1, 2 ); // Passing in literal values

int num1 = 2;
int num2 = 5;
int result = Sum( num1, num2 ); // Passing in variable values

3.1.5. Classes

Declaring a class

Remember that classes must end with ; on their closing curly brace!

class CLASSNAME
{
    public:
    // Public members

    protected:
    // Protected members

    private:
    // Private members
};
class Student
{
public:
  // Constructor functions
  Student();
  Student( string name, float gpa );

  // Member functions
  void Setup( string name, float gpa );
  void Display();

private:
  // Member variables
  string m_name;
  float m_gpa;
};

Defining a class member function (method)

A class' member functions must be declared within the class declaration. Then, you define the member function within a .cpp file.

RETURNTYPE CLASSNAME::FUNCTIONNAME( PARAMETERS )

// Function definition
void Student::Setup( string name, float gpa )
{
  m_name = name;
  m_gpa = gpa;
}

Getter and Setter patterns

It is best practice to make member variables private to protect the integrity of the data. Private members cannot be accessed outside of the function, so instead you'll have to create interfacing functions to access (get) and mutate (set) data.

Getter function, aka Accessor
  • Doesn't take in any inputs (parameters)
  • Returns the value of the member variable (return type should match the member variable)
  • Getter functions can be good for formatting data before returning it
// Basic getter function
float Student::GetGPA()
{
  return m_gpa;
}

// Example of formatting before returning data
string Person::GetFullName()
{
  return m_lastname + ", " + m_firstname;
}
Setter function, aka Mutator
  • Takes in an input value for a new value for the member variable - parameter should have the same data type as the member variable
  • Doesn't return any data - void return type
  • Setter functions should include any needed error checking and reject invalid data
// Basic setter function
void Student::SetGPA( float newGpa )
{
  m_gpa = newGpa;
}

// Example of data validity check
void Student::SetGPA( float newGpa )
{
  if ( newGpa < 0 || newGpa > 4 )
  {
    cout << "Error! Invalid GPA!" << endl;
    return; // Return without saving data
  }
  else
  {
    m_gpa = newGpa;
  }
}

3.1.6. Pointers

Declare a pointer

DATATYPE* PTRNAME = nullptr;


Assign an address to a pointer

PTRNAME = &VARIABLE;

int * ptrInt = nullptr;
string * ptrString = nullptr;

Pointer variables store addresses as their value. To get the address of a variable, prefix the variable name with the address-of operator &.

int myInteger = 5;
int * ptrInt = &myInteger;

Student studentA;
Student * ptrStudent = nullptr;
ptrStudent = &studentA;

Dereference a pointer

cout << *ptrName; // Display contents that pointer is pointing to
cin >> *ptrName; // Overwrite contents that pointer is pointing to

Dereference an object pointer and access a member variable

PTR->MEMBER

Student* newStudent = new Student;
newStudent->name = "Hikaru";
cout << "Student name: " << newStudent->name << endl;

Check if pointer is pointing to an address

if ( ptrName != nullptr )
{
  // Pointer is safe to use...
}

3.1.7. Memory management

Allocate memory for a single variable

DATATYPE* PTRNAME = NEW DATATYPE;

int * num = new int;
Node* newNode = new Node;

Deallocate memory of a single variable

DELETE PTRNAME;

delete num;
delete newNode;

Allocate memory for an array

DATATYPE* PTRNAME = new DATATYPE[ SIZE ];

int * numList = new int[100];
Node* nodeList = new Node[10];

Deallocate memory of an array

DELETE [] PTRNAME;

delete [] numList;
delete [] nodeList;

\newpage

3.2. Basic computer skills

3.2.1. Basic computer skills

How to take a screenshot

computer_skills_printscreen.jpg

In Windows
Press PRINTSCREEN on your keyboard, then go to an image editing application (Paint, if you have nothing else) and use EDIT > PASTE to paste the image in.
In Mac
CTRL+Z, COMMAND+SHIFT+3 to take a screenshot in Mac

3.2.2. Navigating the filesystem

Identifying file extensions

You should be aware of the extensions of our files. You will need to be able to identify source code files, such as .cpp and .h files for C++, or .py files for Python. Additionally, most executable (runnable) files end with the .exe extension in Windows.

Turning on viewing file extensions in Windows

computer_skills_extensions.png

By default, Windows hides file extensions from you. However, it is important to know what kind of files you're working with in a programming class. To view file extensions, search for "File Explorer Options". Select the "View" tab, and UNCHECK the option "Hide extensions for known file types". Hit OK when done.

Project working directory

Visual Studio: computer_skills_workingdir_visualstudio.png

Code::Blocks: computer_skills_workingdir_codeblocks.png

It is important to keep in mind that the default working directory of our programs is the location where the project file is. For Visual Studio, that's a .vcxproj file. For Code::Blocks, that's a .cbp file.

Navigating quickly

Selecting multiple files with CTRL or SHIFT

3.2.3. Editing text

Cut (CTRL+X), copy (CTRL+C), paste (CTRL+V)

Double-click to highlight word

CTRL+arrow keys to scroll a word at a time

CTRL+HOME/CTRL+END to go to start/end of a document

SHIFT to select regions of text

3.2.4. IDE tips and tricks

Splitting code views

Go to declaration

Go to definition

Find all references

Refactor - Rename

3.3. Common C++ bugs and issues

3.3.1. Common build errors

Undefined Reference to WinMain
  • Explanation: Your program can't find main(), the main entry-point to the program.
  • Try:
    • Make sure you've written int main() in your prgoram.
    • If working with Visual Studio, make sure you've opened a project (NOT A FILE/FOLDER!) - Is your Solution Explorer empty?
Undefined reference to …
  • Explanation: A variable or function either has not been declared or cannot be found at the current location in the program.
  • Try: Check to make sure you don't have any typos, that your variables have been declared, that your #include are set up properly, and that any functions declared also are defined elseware.
Use of undeclared identifier XYZ
  • Explanation: You're trying to use a variable XYZ but you have not declared it at this point in the program.
  • Try: Look for your variable declaration and make sure it shows up before any code that uses this variable.
Unresolved external symbol ABC
  • Explanation: This usually means you've made a call to a function that doesn't exist - perhaps you've declared it somewhere, but never wrote the function's definition.
  • Try: Double checking that all your function declarations' and definitions' headers MATCH!
Object of abstract class type is not allowed / Cannot instantiate abstract class
  • Explanation: You're trying to create an object (that is, a variable whose data type is a class), and the class you're using is still an abstract class. This could be because you haven't overridden all of its parents' pure virtual functions, or perhaps a typo between the parent class' function signature and the child class' function signature.
  • Try: Look at class' parent - for any pure virtual functions (e.g., virtual RETURN FUNC() = 0;), make sure you have declared and defined them in the child class.
cannot convert from ABC to XYZ
  • Explanation: The program is expecting an XYZ data type in a location where you're giving it an ABC type instead.
  • Try: If you're working with a class object, perhaps you need to pass a member variable of that class object instead?
ABC already defined in XYZ
  • Explanation: This error is saying that a function has already been defined elsewhere. There could be a few reasons.
  • Try:
    • Are you missing the #ifndef file guards in a .h file?
    • Have you defined a given function more than once?
    • Run a Clean and Rebuild in your IDE.
    • Make sure that you DO NOT HAVE #include FOR ANY .cpp FILES!!
Operator -> applied to ABC instead of pointer type
  • Explanation: You're trying to dereference an object that is not a pointer.
  • Try: Perhaps you're storing a vector of pointers? Make sure you're accessing a single element.
error: implicit instantiation of undefined template 'std::basicifstream
  • Explanation: Missing an include for the fstream library.
  • Try: Don't forget to put #include <fstream> in the code files where you're using ifstream or ofstream.

3.3.2. Common runtime errors

Memory access violation
  • Explanation: If the memory address it shows you is 0x00000 or something with a lot of zeroes, then you're trying to access a pointer that is pointing to nullptr.
  • Try:
    • Check to make sure you're not going outside of bounds on an array.
    • Check to make sure you're checking if a pointer is NOT pointing to nullptr before de-referencing it.

3.3.3. Weird software issues

Windows maximum path length error
  • Explanation: Windows has a setting that limits the maximum file path length. If your repository is deep down many folders, you may encounter this issue.
  • Fixes:
    • Enable long paths - The Windows documentation (https://docs.microsoft.com/en-us/windows/win32/fileio/maximum-file-path-limitation) has some information on enabling long paths.
    • OR Move your project directory - If you move your project directory to something like C:\ instead of the desktop (which is actually C:\Users\blahblahblah\Desktop) or the default visual studio project path (C:\Users\blahblahblah\source\repos) this will help avoid this maximum path length issue.
Visual Studio: Fatal error LNK1104: cannot open file …exe
  • Explanation: Visual Studio is trying to build the program but cannot overwrite the .exe file.
  • Fixes:
    • Try to close Visual Studio and re-open it - Sometimes if your program crashed last time you ran it, Visual Studio will be unable to update the .exe file and give this error.
    • OR Turn off your virus scan - Sometimes your virus scan will see the .exe file you just built as an ``unknown threat'' and prevent it from opening, which also causes this error.
Code::Blocks: error: ld returned 1 exit status
  • Try: Make sure you do not have any #include statements that include a .cpp file. Includes only work with .h and .hpp files, or library files in < > brackets.
Code::Blocks: Modern C++ features not working
  • Fix: In this case you'll need to set up your compiler to build for a modern C++ version, rather than the default of C++98 (from 1998). In Code::Blocks, go to Settings > Compiler… Then, check the box that is next to the Have g+ follow the C++17 ISO C++ language standard [-std=c++17] option, or the C++14 one if that's not available.
  • codeblocks-compiler.png
XCode: Cannot find functions
  • Explanation: This is a result of creating a new file in XCode, but choosing the wrong file type. When adding .cpp files, make sure you select a C++ file object.
  • reference-cannotfind.png
XCode: Where are my output/input text files??
  • You will need to set up a Working Path for your projects in XCode. You can get to this option by going to the menu bar: Scheme -> Edit Scheme. You will want to set your working directory to a specific path where you can locate the text files.
  • xcode-working-directory.png

3.3.4. Git issues

Git: There is no tracking information for the current branch.
  • Error message: There is no tracking information for the current branch. Please specify which branch you want to merge with.
  • Explanation: Git isn't sure what branch you're working with; tell it explicitly.
  • Try: git pull origin main
  • git-specifybranch.png
Git: [rejected] error: failed to push some refs
  • Error message: ! [rejected] error: failed to push some refs hint: Updates were rejected because the tip fo your current branch is behind hint: its remote counterpart. Integrate the remote changes (e.g. hint: 'git pull …') before pushing again. hint: See the 'Note about fast-forwards' in 'git push –help' for details.
  • Explanation: There are changes on the server that you don't have on your local machine yet. A merge needs to happen.
  • Try: The hint gives you the solution: Run git pull and then repeat your git push after the merge.
  • git-pushfail.png
Git: fatal: not a git repository (or any of the parent directories): .git
  • Error message: fatal: not a git repository (or any of the parent directories): .git
  • Explanation: You are not running your git commands from within a repository folder.
  • Try: Make sure you open Git Bash within a folder, or use the cd commands to navigate to your repository path.
  • git-notarepo.png
Git: error: Browse.VC.opendb Permission denied
  • Error message: error: open("…./Browse.VC.opendb"): Permission denied error: unable to index file '…/Browse.VC.opendb' fatal: adding files failed
  • Explanation: This happens because Visual Studio is still open and Visual Studio dislikes its project files changing.
  • Try: Close Visual Studio before running git add.
  • permission-denied.png

3.4. Code and UI style guide

3.4.1. Repository management

Your merge request should only contain files related to the current feature or project you're working on
It shouldn't contain code from multiple assignments.

3.4.2. User Interface design

  1. Prompts before inputs

    Before using an input statement (e.g., cin), use an output statement (e.g., cout) to display a message to the user. Make sure you're clear about what kind of data you're expecting them to enter.

    No:

    _
    

    If you use an input statement it doesn't show anything on the screen, so it looks like your program has crashed.

    Yes:

    Please enter pet name: _
    

    Use an output statement to display a message before getting the user's input.


3.4.3. C++ Style Guide

  1. Naming conventions
    Variables

    lowerCamelCase - Variable names should begin with a lower-case letter and each subsequent letter use an Upper Case, in a camel-case format.

    Additionally:

    • Variable names should be descriptive.
    • Avoid using single-letter variable names except with for loops.
    Member variables
    m_lowerCamelCase - Variables that belong to a class should be prefixed with m_ to signify "member".
    Functions
    CamelCase - Function names should begin with an upper-case letter and be in CamelCase form. In some cases, using an underscore might be okay to group like-functions together, if it makes things more clear.
    Classes
    CamelCase - Class names should begin with an upper-case letter and be in CamelCase form.

  2. Best practices
    • Basics
      • You must have int main, not void main.
      • Don't put an entire program in main() - Split out the program into separate menu functions; ideally use a Program class that contains functions within it.
    • Naming conventions
      • Variable, function, and class names should be descriptive.
    • Arrays
      • Do not use a variable for an array's size; some compilers might support this but not all do. Traditional C arrays and STL arrays must have hard-coded integer literals or named constant integers as its size.
    • Functions
      • Functions should perform the minimal amount of operations - a function should have a specific purpose.
    • Structs and Classes
      • Structs should be used for structures that only contain a few amount of variables and no functions. Classes should be used for more sophisticated structures that contain functions and variables.
      • Prefer making member variables private with member functions as an interface for those items.
    • try/catch
      • The try{} statement should wrap the most minimal amount of code (NOT THE ENTIRE FUNCTION BODY!) - generally, try should wrap the one function that could throw an exception.
    • NEVER USE GLOBAL VARIABLES.
    • NEVER USE goto STATEMENTS.

3.4.4. Cross platform compatibility

Treat everything (including files) as case-sensitive
When using an #include statement for a file in your project, make sure your casing matches the file itself. E.g., if the file is Product.h, use #include "Product.h", not #include "product.h".
Use #ifndef fileguards, not #pragma once
Use the #ifndef _LABEL, #define _LABEL, #endif style of file guards as they are supported by more compilers.
  • Fileguards ONLY go in .h files.
system("cls"); only works on Windows

Prefer creating a cross-platform function like this instead:

void ClearScreen()
{
#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
  system( "cls" );
#else
  system( "clear" );
#endif
}
system("pause"); only works on Windows.

Prefer creating a cross-platform function like this instead:

// It's klugey but it's the simplest.
void PressEnterToContinue()
{
  cout << endl << "PRESS ENTER TO CONTINUE" << endl;
  string temp;
  getline( cin, temp );
  getline( cin, temp );
}
File guards
Always use ifndef instead of pragma once for your file guards.

Yes:

#ifndef _MYFILE_H
#define _MYFILE_H

// My code

#endif

No:

#pragma once

// My code

3.4.5. File organization

Function/class declarations
Function and class declarations should go in a header (.h) file.
Function definitions
Function definitions should go in a source (.cpp) file, EXCEPT TEMPLATED FUNCTIONS (those all go in .h).
Each class/struct should have its own set of .h and .cpp (as needed) files
  • Don't put multiple class declarations in one file.
Function definitions must go in .cpp file
Don't define class functions within the class or in the .h file.
  • Except for templated classes - Everything goes in the .h file for templated classes.
Don't define structs/classes inside other classes
Each struct/class should have its own .h file/set of .h and .cpp files.]
Never include .cpp files!

Includes should only include .h or .hpp header files.

If a project has many files, separate them into folders
Logically separate related files into subfolders, such as Exceptions, DataStructures, Menus, etc.

3.4.6. Clean code

Erase unused codeblocks
If you want to make sure to be able to reference old code later, back it up to GitLab, then delete the comment. Don't leave commented out code blocks in turn-in assignments.
Be consistent with naming conventions
Choose either UpperCaseFunctionNames or lowerCaseFunctionNames but don't interchange them. Same with variable and class naming. Be consistent.
Whitespace
Adequate whitespace should be used to differentiate logical sections of code. At the same time, don't use too much whitespace. The goal is to have readable code.
If ( true ) return true; else return false;
If you're writing a condition to check if something is true in order to return true, just return the result of the condition instead.

No:

if ( a == b )
  return true;
else
  return false;

Yes:

return ( a == b );

  1. Curly braces
    Follow the existing code base
    • If you're writing code from scratch you can follow whatever style you'd like as long as it is consistent.
    • When working with existing code-bases, use the same style as the existing code.
    • See https://en.wikipedia.org/wiki/Indentation_style for indentation styles

    Preferred style:

    if ( a == b )
    {
      DoThing();
    }
    

    GNU styling:

    if ( a == b )
      {
        DoThing();
      }
    

    K&R Styling ("JavaScript" style):

    if ( a == b ) {
      DoThing();
    }
    
    One-line contents
    Always surround your if statement and while loop contents within curly braces { } even though it's not required for one-line internals.

    No:

    if ( CONDITION )
      DoThingA();
    else if ( CONDITION2 )
      DoThingB();
    else
      DoThingC();
    

    Yes:

    if ( CONDITION )
    {
      DoThingA();
    }
    else if ( CONDITION2 )
    {
      DoThingB();
    }
    else
    {
      DoThingC();
    }
    

    Or:

    if      ( CONDITION )  { DoThingA(); }
    else if ( CONDITION2 ) { DoThingB(); }
    else                   { DoThingC(); }
    

3.5. How to use VSCode

3.6. How to use GitLab

3.7. Resource archive

3.7.1. CS 200 Topics

4. Additional

4.1. Syllabus

\newpage

5. Course contents

\newpage

5.1. Unit 00: Welcome and setup

5.1.1. Reading

banner-reading.png

  1. Welcome!

    It feels weird to start a collection of notes (or a "textbook") without some sort of welcome, though at the same time I know that people are probably not going to read the introduction (Unless I put some cute art and interesting footnotes, maybe.)

    I think that I will welcome you to my notes by addressing anxiety.

    Belonging

    Unfortunately there is a lot of bias in STEM fields and over decades there has been a narrative that computer science is for a certain type of person - antisocial, nerdy, people who started coding when they were 10 years old.

    Because of this, a lot of people who don't fit this description can be hesitant to get into computers or programming because they don't see people like themselves in media portrayals. Or perhaps previous professors or peers have acted like you're not a real programmer if you didn't start programming as a child

    If you want to learn about coding, then you belong here.

    There are no prerequisites.

    I will say from my own experience, I know developers who fell in love with programming by accident as an adult after having to take a computer class for a different degree. I know developers who are into all sorts of sports, or into photography, or into fashion. There is no specific "type" of programmer. You can be any religion, any gender, any color, from any country, and be a programmer.

    u00_WelcomeAndSetup_gatekeepingbaby.png

    Figure 1: Don't be like Gatekeeper Baby. You can begin coding at any age!

    \vspace{0.2cm}

    Challenge

    Programming can be hard sometimes. There are many aspects of learning to write software (or websites, apps, games, etc.) and you will get better at it with practice and with time. But I completely understand the feeling of hitting your head against a wall wondering why won't this work?! and even wondering am I cut out for this?! - Yes, you are.

    I will tell you right now, I have cried over programming assignments, over work, over software. I have taken my laptop with me to a family holiday celebration because I couldn't figure out this program and I had to get it done!!

    All developers struggle. Software is a really unique field. It's very intangible, and there are lots of programming languages, and all sorts of tools, and various techniques. Nobody knows everything, and there's always more to learn.

    Just because something is hard doesn't mean that it is impossible.

    u00_WelcomeAndSetup_justwork.png

    It's completely natural to hit roadblocks. To have to step away from your program and come back to it later with a clear head. It's natural to be confused. It's natural to not know.

    But some skills you will learn to make this process smoother are how to plan out your programs, test and verify your programs, how to phrase what you don't know as a question, how to ask for help. These are all skills that you will build up over time. Even if it feels like you're not making progress, I promise that you are, and hopefully at the end of our class you can look back to the start of it and realize how much you've learned and grown.

    Learning

    First and foremost, I am here to help you learn.

    My teaching style is influenced on all my experiences throughout my learning career, my software engineer career, and my teaching career.

    I have personally met teachers who have tried to scare me away from computers, I've had teachers who really encouraged me, I've had teachers who barely cared, I've had teachers who made class really fun and engaging.

    I've worked professionally in software and web development, and independently making apps and video games. I know what it's like to apply for jobs and work with teams of people and experience a software's development throughout its lifecycle.

    And as a teacher I'm always trying to improve my classes - making the learning resources easily available and accessible, making assignments help build up your knowledge of the topics, trying to give feedback to help you design and write good programs.

    As a teacher, I am not here to trick you with silly questions or decide whether you're a real programmer or not; I am here to help guide you to learn about programming, learn about design, learn about testing, and learn how to teach yourself.

    u00_WelcomeAndSetup_buildingblocks.png

    Roadmap

    u00_WelcomeAndSetup_roadmap.png

    When you're just starting out, it can be hard to know what all you're going to be learning about. I have certainly read course descriptions and just thought to myself "I have no idea what any of that meant, but it's required for my degree, so I guess I'm taking it!"

    Here's kind of my mental map of how the courses I teach work:

    CS 200: Concepts of Programming with C++
    You're learning the language. Think of it like actually learning a human language; I'm teaching you words and the grammar, and at first you're just parroting what I say, but with practice you'll be able to build your own sentences.
    CS 235 Object-Oriented Programming with C++
    You're learning more about software development practices, design, testing, as well as more advanced object oriented concepts.
    CS 250 Basic Data Structures with C++
    You're learning about data, how to store data, how to assess how efficient algorithms are. Data data data.

    In addition to learning about the language itself, I also try to sprinkle in other things I've learned from experience that I think you should know as a software developer (or someone who codes for whatever reason), like

    • How do you validate that what you wrote actually works? (Spoilers: How to write tests, both manual and automated.)
    • What tools can you use to make your programming life easier? (And are used in the professional world?)
    • How do you design a solution given just some requirements?
    • How do you network in the tech field?
    • How do you find jobs?
    • What are some issues facing tech fields today?

    Something to keep in mind is that, if you're studying Computer Science as a degree (e.g., my Bachelor's degree is in Computer Science), technically that field is about "how do computers work?", not about "how do I write software good?" but I still find these topics important to go over.

    u00_WelcomeAndSetup_search.png

    That's all I can really think of to write here. If you have any questions, let me know. Maybe I'll add on here.

    \vspace{0.2cm}

    What is this weird webpage/"book"?

    In the past I've had all my course content available on the web on separate webpages. However, maintaining the HTML, CSS, and JS for this over time is cumbersome. Throughout 2023 I've been adapting my course content to emacs orgmode documents, which allows me to export the course content to HTML and PDF files. I have a few goals with this:

    1. All course information is in one singular place
    2. At the end of the semester, you can download the entire course's "stuff" in a single PDF file for easy referencing later on
    3. Hopefully throughout this semester I'll get everything "moved over" to orgmode, and in Summer/Fall 2024 I can have a physical textbook printed for the courses, which students can use and take notes in so as to have most of their course stuff in one place as well
    4. It's important to me to make sure that you have access to the course content even once you're not my student anymore - this resource is available publicly online, whether you're in the course or not. You can always reference it later.

    I know a lot of text can be intimidating at first, but hopefully it will be less intimidating as the semester goes and we learn our way around this page.

    \vspace{0.2cm}


  2. How to navigate the course

    TODO!


  3. Tools for software development

    What kind of tools are needed to make programs?

    hit-computer.png

    To write software, we need to write instructions - the program source code is the list of instructions. This means we need some kind of text editor program.

    To turn the program instructions into stuff humans can read into stuff computers can read (that is, binary, or an executable file), we need a compiler program.

    These are the two things that are needed at minimum, but there are plenty more tools to help us be more effective at our jobs. For instance, if you use the default "Notepad" on Windows it's going to be a bunch of black text on a white background. If you use a text editor meant for code, however, you'll get syntax highlighting - which color-codes different commands, helping us read the code more clearly.

    #include <iostream>
    using namespace std;
    int main()
    {
      cout << "Hello, world!" << endl;
      return 0;
    }
    

    (If this doesn't show up in color, just pretend it does and that it makes it easier to read.)

    Since we'll be writing a lot of different programs and referring back to these programs throughout the semester you will also want to keep things organized and backed up. There is special software that software developers use to keep track of their code changes over time, called source control or version control. We will be using the Git version control system in this course, though we are going to stick to the web interface view for this introductory course.

    \newpage

5.1.2. Programming Lab

banner-lab.png

\newpage

5.2. Unit 01: C++: Variables, input, and output

5.2.1. Reading

banner-reading.png Reading: Welcome, how to navigate the course, and tools setup

  1. main(): The starting function

    An empty C++ program

    The bare-minimum C++ program looks like this:

    int main()
    {
    
      return 0;
    }
    

    No matter what all is in your program, your compiler is going to expect that a main function exists, and this function acts as the starting point of a C++ program.

    The opening curly-brace { and closing curly-brace } denote the start and end of the main function. The curly-braces and any code within is known as a code-block. Program instructions will go within this code-block.

    At the end of the main function we have return 0;. In this context, it means "return (exit) the program with a status of 0", with that basically meaning "return with no errors". If you ran into an error while the program was running, you might do something like return 123; instead, to mark the area with an "error code" (123), which you can then find in the code.

    For our programs starting off, we will be putting our instruction code after the opening curly-brace { and before the return 0;, but the code given above is the absolute, bare-minimum required to write a C++ program.

    An introduction to syntax

    Context: What is syntax?

    syntax, noun

    The way in which linguistic elements (such as words) are put together to form constituents (such as phrases or clauses)

    From the Merriam-Webster Dictionary.

    C++, Java, C#, and other "C-like" languages follow similar syntax rules.

    Lines of code: A code statement ends with a semi-colon. Statements are single commands, like using cout ("console out") to display text to the screen, assigning a value to a variable, and other simple operations.

    string state;               // Variable declaration
    cout << "Enter state: ";    // Display text to screen
    cin >> state;               // Getting input from keyboard
    cout << state << endl;      // Displaying text to the screen
    

    Code blocks: There are certain types of instructions that contain additional code. If statements, for example, contain a set of instructions to execute only if the condition given evalutes to true. Any time an instruction contains additional instructions, we use opening and closing curly braces { } to contain this internal code. Note that an if statement and other structures that contain code don't end with a semicolon ;.

    Comments: Comments are notes left in the code by humans for humans. They can help us remember what our code was doing later on, or help guide someone else reading through our code. There are two ways we can write comments in C++.

    If we use // then all text afterwards will be a comment. This is a single-line comment.

    If we use /* then all text will be a comment, only ending once we reach a */. This is a multi-line comment.

    string state;               // Variable declaration
    
    /*
      Next we're going to search for this state
      in the list of all states that match xyz criteria...
    */
    

    Syntax errors and logic errors

    c2_u01_debugging2.png

    Syntax errors are errors in the language rules of your program code. This include things like typos, misspellings, or just writing something that isn't valid C++ code, such as forgetting a ; at the end of some instructions.

    Although they're annoying, syntax errors are probably the "best" type of error because the program won't build while they're present. Your program won't build if you have syntax errors.

    Logic errors are errors in the programmer's logic. This could be something like a wrong math formula, a bad condition on an if statement, or other things where the programmer thinks thing A is going to happen, but thing B happens instead.

    These don't lead to build errors, so the program can still be run, but it may result in the program crashing, or invalid data being generated, or other problems.

    Minimizing bugs and debugging time

    coding-strategy.png

    • Write a few lines of code and build after every few lines - this will help you detect syntax errors early.
    • DON'T write the "entire program" before ever doing a build or a test - chances are you've written in some syntax errors, and now you'll have a long list of errors to sift through!
    • If you aren't sure where an error is coming from, try commenting out large chunks of your program until it's building again. Then, you can un-comment-out small bits at a time to figure out where the problem is.

  2. Variables: Storing our data

    1. Variables and data

      c2_u01_variables.png

      We use variables in programming as places to temporarily store data so that we can manipulate that data. We can have the user write to it via the keyboard, we can use files to write data to variables, we can do math operations or modify these variables, and we can print* them back out to the screen or a text file.

      (*Printing here meaning "display on the screen"; not to a printer. Holdover from ancient times when computers' outputs came via the printers.)

      When we're writing programs in C++, we need to tell our program what the data type of each variable is, and give each variable a variable name (aka identifier). When a variable is declared, a space in RAM is allocated to that variable and it can store its data there. That data can be manipulated or overwritten later as needed in the program.

      1. Data types

        In C++, when we want to create a variable we need to tell the compiler what the data type of the variable is. Data types specify what is stored in the variable (whole numbers? numbers with decimal values? text? true/false values?). Each data type takes up a different amount of space in memory.

        Data type Values Size Example code
        char single symbols - letters, numbers, anything 1 byte char currency = '$';
        boolean true or false 1 byte bool savedGame = false;
        integer whole numbers 4 bytes int age = 100;
        float numbers w/ decimals 4 bytes float price = 9.95;
        double numbers w/ decimals 8 bytes double price = 1.95;
        string any text, numbers, symbols, any length variable string password = "123secure";

        Of these, notice that the string data type doesn't have a fixed size. This is because technically, behind-the-scenes, a string is really just an array (or list) of char data types. The C++ standard library contains a string library that handles a lot of text-related functionality like find.

        Floats and doubles both store numbers with fractional (decimal) parts, but a double takes up double the memory in RAM, allowing to store more accurate fractional amounts. A float has 6 to 9 digits of precision and a double has 15 to 18 digits of precision .(From https://www.learncpp.com/cpp-tutorial/floating-point-numbers/)

        Boolean data types store true and false values, but will also accept integer values when assigned. It will convert a value of 0 to false and any other number to true.

        Declaring variables and assigning values to variables

        Variable declaration

        When we're declaring a variable, it needs to follow one of these formats:

        1. DATATYPE VARIABLENAME;
        2. DATATYPE VARIABLENAME = VALUE;
        3. DATATYPE VARIABLENAME1, VARIABLENAME2, VARIABLENAME3;
        4. DATATYPE VARIABLENAME1 = VALUE1, VARIABLENAME2 = VALUE2;

        The data type goes first, then the variable name/identifier, and if you'd like, you can also assign a value during the same step (though this is not required).

        Once a variable has been declared, you don't need to declare it again. This means you don't need to re-specify its data type when you're using it. Just address the variable by its name, and that's all.

        Code that uses integers to figure out how many candies each kid should get:

        // Declaring variables and assigning values
        int totalCandies = 10;
        int totalKids = 5;
        int candiesPerKid = totalCandies / totalKids;
        
        // Reusing the same variables later on
        totalCandies = 100;
        totalKids = 10;
        candiesPerKid = totalCandies / totalKids;
        

        Code to display the price plus tax to the user:

        float price = 9.99;
        float tax = 0.11;
        // Text output to the screen. Can do math within!
        cout << "Please pay " << (price + price * tax);
        

        Variable assignment

        1. VARIABLENAME = LITERAL; - Stores the LITERAL value in VARIABLENAME.
        2. VARIABLENAME1 = VARIABLENAME2; - Copies the value from VARIABLENAME2 to VARIABLENAME1.

        When assigning a value to a variable, the variable being assigned to always goes on the left-hand side ("LHS") of the equal sign =. The = sign is known here as the assignment operator.

        The item on the right-hand side ("RHS") will be the value stored in the variable specified on the LHS. This can be a literal (a hard-coded value) or it can be a different variable of the same data type, whose value you want to copy over.

        Assigning literal values to variables:

        price = 9.99;       // 9.99 is a float literal
        state = "Kansas";   // "Kansas" is a string literal
        operation = '+';    // '+' is a char literal
        

        Copying student13's value to the bestStudent variable:

        bestStudent = student13;
        

        c2_u01_assignment1.png

        Naming conventions

        You can name a variable anything you'd like, but it can only contain numbers, underscore (_), and upper- and lower-case letters in the name. Variable names can begin with the underscore or a letter, but they cannot start with a number. And definitely NO spaces are allowed in a variable name!

        Additionally, a variable name cannot be a keyword in C++, a name reserved for something else in the language, such as void, if, int, etc.

        Everything in C++ is case sensitive, which means if you name a variable username, it will be a different variable from one named userName (or if you type "userName" when the variable is called "username," the compiler will complain at you because it doesn't know what you mean).

        One common way variables are named are using camelCasing, where each subsequent word in a variable's name is capitalized:

        int howManyCookies;
        string mySecurePassword;
        float howMuchStudentLoansIHave;
        

        Another common way you might see variables named in C++ is using underscores to split up words:

        int how_many_cookies;
        string my_secure_password;
        float how_much_student_loans_i_have;
        

        I just want you to be consistent with your style, though you can choose either one of these styles.

        Unsigned data types

        Sometimes it doesn't make sense to store negative values in a variable - such as speed (which isn't directional, like velocity), the size of a list (can't have negative items), or measurement (can't have negative width). You can mark a variable as unsigned to essentially double its range (by getting rid of the negative side of values). For instance, a normal int can store values from -2,147,483,648 to 2,147,483,647, but if you mark it as unsigned, then your range is 0 to 4,294,967,295.

        Modern C++: auto

        In C++11 (from 2011) and later, you can use the keyword auto as the "data type" in your variable declaration that includes an assignment statement. When you use auto, it uses the assigned value to automatically figure out the variable's data type, so you don't have to explicitly define it:

        auto price = 9.99;      // it's a double!
        auto price2 = 2.95f;    // it's a float!
        auto player = '@';      // it's a char!
        auto amount = 20;       // it's an int!
        

        Basic operations on variables

        Now that you have variables available in your program to play with, what can you even do with them?

        Outputting variable values

        Using the cout (console-out) statement, you can display text to the screen with string literals:

        cout << "Hello, world!" << endl;
        

        But you can also display the values stored within variables, simply by using the variable's name:

        cout << myUsername << endl;
        

        (We will cover more about input and output next part)

        Inputting variable values

        We can use the cin (console-in) statement to get the user to enter something on the keyboard and store that data into a variable:

        cin >> favoriteColor;
        

        Math operations

        With variables with numeric data types (ints, floats, doubles), we can do arithmetic with the +, -, *, and / operators.

        cout << "Sum: " << num1 + num2 + num3 << endl;
        

        Operations:

        Symbol Description
        + Addition
        - Subtraction
        * Multiplication
        / Division

        Make sure to put the result somewhere! When you do a math operation and you want to use the result elsewhere in the program, make sure you're storing the result in a variable via an assignment statement! If you just do this, nothing will happen:

        totalCats + 1;
        

        You can use an assignment statement to store the result in a new variable:

        newCatTotal = totalCats + 1;
        

        Or overwrite the variable you're working with:

        totalCats = totalCats + 1;
        

        c2_u01_cats.png

        Compound operations: There are also shortcut operations you can use to quickly do some math and overwrite the original variable. This works with each of the arithmetic operations:

        cpp

        // Long way:
        totalCats = totalCats + 5;
        
        // Compound operation:
        totalCats += 5;
        

        String operations

        Strings have some special operations you can do on them. You can also see a list of functions supported by strings here: C++ String Reference (We will cover more with strings in a later part).

        Concatenating strings: You can use the + symbol to combine strings together. When used in this context, the + sign is called the concatenation operator.

        string type = "pepperoni";
        string food = "pizza";
        
        // Creates the string "pepperoni pizza"
        string order = type + " " + food;
        

        Letter-of-the-string: You can also use the subscript operator [ ] (more on this when we cover arrays) to access a letter at some position in the string. Note that in C++, the position starts at 0, not 1.

        string food = "pizza";
        
        char letter1 = food[0];  // Stores 'p'
        char letter2 = food[1];  // Stores 'i'
        char letter3 = food[2];  // Stores 'z'
        char letter4 = food[3];  // Stores 'z'
        char letter5 = food[4];  // Stores 'a'
        

        Named constants

        Whenever you find yourself using a literal value in your assignment statements, you may want to think about whether you should replace it with a named constant instead.

        A named constant looks like a variable when you declare it, but it also has the keyword const - meaning that the value can't change after its declaration.

        Named constant declaration format: const CONSTNAME = LITERAL; - Stores the LITERAL value in CONSTNAME.

        Let's say you wrote a program and hard-coded the tax rate:

        // Somewhere in the code...
        checkoutPrice = cartTotal + ( cartTotal * 0.0948 );
        
        // Somewhere else in the code...
        cout << 0.0948 << " sales tax" << endl;
        

        Then the tax rate changes later on. You would have to go into your program and search for "0.0948" and update all those places!

        Instead, it would have been easier to assign the tax rate ONCE to a named constant and referred to that instead:

        // Beginning of program somewhere...
        const SALES_TAX = 0.0948;
        
        // Somewhere in the code...
        checkoutPrice = cartTotal + ( cartTotal * SALES_TAX );
        
        // Somewhere else in the code...
        cout << SALES_TAX << " sales tax" << endl;
        

        If you ever find yourself using the same literal multiple times in your program, then perhaps consider replacing it with a named constant.

        Named constant naming convention: In C++, it is customary to give your named constants names in ALL CAPS, using underscores (_) to separate words.


  3. Memory addresses and pointer variables

  4. Input and output: Interacting with the user

    Interactivity and Output in C++

    Most programs feature interactivity in some way or another. This can involve moving a mouse around, clicking on things, tapping on a touch screen, using a gamepad's joysticks and buttons, but we'll be primarily interacting with our C++ programs through keyboard input. Feedback from our C++ programs will come in the form of text output to the screen, as we are writing terminal programs.

    c2_u01_terminal.png

    We will also delve into reading from and writing to text files (or other file formats) later on. But for now, let's focus on the terminal/console.

    c2_u01_terminal-hi.png

    Outputting Information with cout

    The cout command (pronounced as "c-out" for "console-out") is used to write information to the screen. This can include outputting a string literal:

    cout << "Hello, world!" << endl;
    

    or a variable's value:

    cout << yourName << endl;
    

    or stringing multiple things together:

    cout << "Hello, " << yourName << "!" << endl;
    

    In C++, we use the output stream operator << to string together multiple items for our output.

    Newlines with endl

    The endl command stands for "end-line" and ensures there is a vertical space between that cout statement and the next one. For example, if we write two cout statements without endl like this:

    cout << "Hello";
    cout << "World";
    

    the output will be:

    HelloWorld
    

    If we want to separate them on two different lines, we can write:

    cout << "Hello" << endl;
    cout << "World";
    

    And our output will be:

    Hello
    World
    

    Remember that in C++, a statement ends with a semicolon ;, so you can split your cout statement across multiple lines, as long as you're chaining items together with << and only adding a ; on the last line:

    cout << "Name:   " << name
         << "Age:    " << age
         << "State:  " << state << endl;
    

    Inputting Information with cin

    When we want the user to enter a value for a variable using the keyboard, we use the cin command (pronounced as "c-in" or "console-in").

    For variables like int and float, you will use this format to store data from the keyboard into the variable:

    Using cin >> for variables

    cin >> VARIABLENAME;
    

    You can also chain cin statements together to read multiple values for multiple variables:

    cin >> VARIABLENAME1 >> VARIABLENAME2 >> ETC;
    

    Strings and cin >>

    When using cin >> with a string variable, keep in mind that it will only read until the first whitespace character, meaning it can't capture spaces or tabs. For example:

    string name;
    cin >> name;
    

    If you enter "Rachel Singh", name will contain "Rachel". To capture spaces, you need to use a different function.

    Using getline(cin, var); for Strings

    You can use the getline function to capture an entire line of text as a string. This is useful when you want to capture spaces and multiple words. For example:

    string name;
    getline(cin, name);
    

    Mixing cin >> var; and getline(cin, var);

    If you mix cin >> var; and getline(cin, var);, you might encounter issues with the input buffer. To avoid this, use cin.ignore(); before getline(cin, var); if you used cin >> var; before it.

    int number;
    string text;
    
    cin >> number;
    cin.ignore();
    getline( cin, text );
    

    Escape Sequences

    There are special characters, called escape sequences, that you can use in your cout statements:

    Character Description
    \n newline (equivalent to endl)
    \t tab
    \" double quote

    Example code:

    cout << "\"hello\nworld\"" << endl;
    

    Output:

    "hello
    world"
    

    Example code:

    cout << "A\tB\tC" << endl;
    cout << "1\t2\t3" << endl;
    

    Output:

    A       B       C
    1       2       3
    

    Example code:

    cout << "He said \"Hi!\" to me!" << endl;
    

    Output:

    He said "Hi!" to me!
    

5.2.2. Programming Lab

banner-lab.png

\newpage

5.3. Unit 02: Tech Literacy: Exploring computers

5.3.1. Reading

banner-reading.png

Reading: DESCRIPTION

  1. SUBTOPIC

    INCLUDE HOME, END, CTRL+F, COPY, PASTE, CUT, SELECT ALL

5.3.2. Tech literacy

\newpage

5.4. Unit 03: C++: Functions

5.4.1. Reading

banner-reading.png

reading_u06_Functions_image.png

  1. Program Structure

    errorinmain.png

    As programs become more sophisticated and offer more features, the size of the program increases. At some point, it becomes too complicated to keep your entire program just within main().

    (You could certainly do it, but maintaining it would be a nightmare!)

    One of the tools we use to build modular, easier-to-read code is functions. By using functions, we can delegate tasks out to other portions of the program, passing inputs as data to the function, and receiving some kind of output as a result.

    As a basic example, let's say we need to calculate square footage of a room in multiple places in a program. By making a float GetArea( float width, float length ) function.

    Then, we only have to implement the formula once and can use the function in every part of the program. Then, we wouldn't be copy-and-pasting the same formula over and over again in the code - which also means less likelihood of errors, and easier to update later as needed.

    Program flow and functions

    Whenever a function is called, the program flow is redirected into that function, running from top-to-bottom as normal (with branching and loops changing that flow). Once the function has completed, it can return some data, which is received by the call location.

    From a design standpoint, this means we can break out different parts of programs into their own sections. Each function has a name, which should be used to label what the purpose of its code is.

    reading_u06_Functions_functioncall.png

    reading_u06_Functions_programbreakout.png


  2. Function Basics
    1. Uses of functions
      Functions for formulas

      In algebra, you've seen functions like this:

      \[ f(x) = 2x + 3 \]

      If you were like me in algebra, you might have thought to yourself, "That's the same as \(y = 2x + 3\), why did we replace \(y\) with \(f(x)\)?"

      The reason is that we want to write a function in terms of its input, \(x\), and its output \(f(x)\). The equation \(2x + 3\) is the function body, which specifies how we get some output given some input.

      We can use functions in programming like with math as well - defining formulas that we might need a lot - but there's more to functions than just making computations.

      Let's say we want to make our "GetArea" function in math. We would need two inputs: Width and Length, and the output would end up being the area, so maybe we would name the function \(A\). It might look like this:

      \[ A( w, l ) = w \cdot l \]

      In C++, it would look like this:

      float Area( float width, float length )
      {
        return width * length;
      }
      

      (Luckily we don't have to restrict ourselves to single-letter variable and function names in C++ :)


      Functions to validate

      Functions can also be handy in validating data and user input, putting the validation in one place instead of having to re-implement the same checks over and over.

      For example, let's say we want to keep some variable percentage in our program betwee 0% and 100% - no negative values, nothing over 100%. We could implement a function that takes the percentage as an input, and either returns the same percentage, or 0%, or 100% as output

      int BoundPercent( int originalPercent )
      {
        if ( originalPercent < 0 )
          {
            return 0;
          }
        else if ( originalPercent > 100 )
          {
            return 100;
          }
        else
          {
            return originalPercent;
          }
      }
      

      Then, anywhere in the program, we could use this function to make sure our percentages are in the right range…

      // in main()
      hungerPercent       = BoundPercent( hungerPercent );
      healthPercent       = BoundPercent( healthPercent );
      happinessPercent    = BoundPercent( happinessPercent );
      

      nocomp.png


      Functions to get input

      Getting user input is a common part of writing software, and we will usually need to validate what the user is entering prior to doing any operations on it. Let's say your program is full of numbered menus and you want to validate the user's menu choices easily. You can use a function with a while loop in it:

      int GetUserInput( int min, int max )
      {
        int choice;
        cout << "Choice: ";
        cin >> choice;
      
        while ( choice < min || choice > max )
          {
            cout << "Invalid choice, try again: ";
            cin >> choice;
          }
      
        return choice;
      }
      

      You write this function once and then you can reuse it in your entire program for all menus…

      cout << "1. Deposit money" << endl
           << "2. Withdraw money" << endl
           << "3. View balance" << endl;
      
      choice = GetUserInput( 1, 3 ); // 1, 2, or 3
      
      if ( choice == 1 )
        {
          cout << "1. Checking account" << endl
               << "2. Savings account" << endl;
      
          choice = GetUserInput( 1, 2 ); // 1 or 2
        }
      

      Functions to output

      Functions aren't required to return data. Sometimes, you just want a function that is responsible for formatting output or displaying a menu. In this case, a function's return type can be void.

      void DisplayStudentInfo( string name, float gpa )
      {
        cout << "Name:   " << name
             << "GPA:    " << gpa << endl;
      }
      

      You also aren't required to pass input to functions. In this case, the parameter list between ( ) remains empty, but the () is always required for functions:

      void DisplayMainMenu()
      {
        cout << "1. Deposit" << endl;
        cout << "2. Withdraw" << endl;
        cout << "3. View Balance" << endl;
        cout << "4. Log Out" << endl;
      }
      

      Other uses

      These are just some examples of why you might use functions in your programs. Anything you write in main() can go inside of a different function as well - it's just another tool for designing clean, maintanable, and readable code.

      badcode.png


    2. Anatomy of a function
      1. Function Declaration
        float GetArea( float width, float height );
        

        Before you start using a function, you have to declare and define it… A function declaration is similar to a variable declaration - we tell the program "hey, we want to use this function, here's its name and some info about it." Declaration statements end with a semi-colon and don't contain a code block (the function body) because it's just a declaration.

        Function Header: The function header is the first line of a function, which includes the following information: return type, function name, and parameter list.

        RETURNTYPE FUNCTIONNAME( PARAM1TYPE PARAM1NAME, ... )
        
        • Function Return Type: The return type of a function specifies what kind of data is returned from this function. The return type can be any data type, or it can be void if nothing is going to be returned.
        • Function Name: The function name should describe what the responsibility of the function is - what it does.
        • Function Parameters: The parameters of a function are a list of input variables that are expected to be passed into the function from elseware. The parameter list is located between the ( and ) in the function header.

      2. Function Definition
        float GetArea( float width, float height )
        {
          return width * height;
        }
        

        The function definition is where we actually write what the function does. It includes the same information as the function declaration, but we include the function body in a code block.


      3. Function Body

        The function body is the code block, written between { and }, defining what logic the function performs.


      4. Function Call
        float room1Sqft = GetArea( 5, 10 );
        float room2Sqft = GetArea( room2width, room2length );
        

        After a function is defined, we can then call that function to execute its internal code. If the function has input parameters, we can pass in literal values (hard-coded data) or variables to provide that input data.


        Calling a function

        Once the function has been defined, you can call it from anywhere in your program…

        int main()
        {
          float width, height;
          cout << "Enter width and height: ";
          cin >> width >> height;
        
          // Call GetArea
          float area = GetArea( width, height );
        
          cout << "Area: " << area << endl;
        }
        

        Function Call: Calling a function requires the function name, and passing in a series of inputs that become the function's parameters. In the example above, the GetArea function is called, with the values from the width and height variables being passed in. Once GetArea returns its output, that output is then stored in the area variable.

        Arguments: An argument is the name of the value or variables being passed into the function during the function call. These arguments become the values that the function parameters within the function definition uses.

        Here in the function call, 10 and 20 are the arguments:

        // Call GetArea
        float area = GetArea( 10, 20 );
        

        So the values of 10 and 20 get used as the width and length parameters' values:

        float GetArea( float width, float height )
        {
          return width * height;
        }
        

        The arguments of a function call can be hard-coded values, like 10 and 20 above, or you can pass in other variables as arguments. Then, whatever is stored in those variables is copied over to the parameters.

        // Call GetArea twice
        float area1 = GetArea( room1Width, room1Length );
        float area2 = GetArea( room2Width, room2Length );
        

        The arguments passed in do not need to share a name with the parameters; these are not the same variables. They're only sharing the data stored within them.

        The first time GetArea is called, whatever is stored within room1Width is copied from that variable and stored in the parameter variable width within the function's definition.

        Common function errors:

        1. When you're declaring/defining a function you specify data types - the return type and the parameters' data types. When you're calling a function, you do not include data types!
          • YES: sqft = GetArea( room_width, room_length );
          • NO: sqft = GetArea( float room_width, float room_length );
        2. Functions must have parentheses ()! If you're missing the parentheses, your program isn't going to call the function!
          • YES: DisplayMenu();
          • NO: DisplayMenu;
        3. If a function contains a return statement, then you must store the returned data in a variable! If you don't assign the return anywhere, it will be lost!
          • YES: sqft = GetArea( room_width, room_length );
          • NO: GetArea( room_width, room_length );

  3. Variable scope

    Scope refers to the location in the code where a variable exists.

    main():
    If you declare a variable at the top of the main() function, not inside any if statements or loops, then that variable is in scope for the entire duration of main(), starting with the line it was declared on.
    int main()
    {
      int a;
      // ...etc...
    }
    

    Variables declared within if statements and loops:
    Variables declared within the code block of an if statement or a loop only exists within that code block.
    if ( a == 3 )
    {
        int b;  // only exists within this block
    }
    
    for ( int i = 0; i < 10; i++ )
    {
        cout << i; // only exists within this block
    }
    

    If you try to use these variables somewhere below the code block, your compiler will give an error, stating that the variable does not exist in that scope. Once the program leaves the code block, the variable is out of scope.


    Functions:
    Remember that main() is a function, just like any other functions we write in our program. Any variables declared within a function are local to that function, and accessible anywhere from the variable's declaration until the end of the function.
    int GetChoice()
    {
      int choice; // local variable
      cout << "Choice: ";
      cin >> choice;
      return choice;
    }
    

    Parameters:
    Variables declared in the parameter list of a function are also local to that function and can be used anywhere within the function.
    int Sum( int a, int b, int c )
    {
    // a, b, and c are local to this function.
    return a + b + c;
    }
    

    Same names?
    The same name can be reused for different variables in different scopes. Even if they share the same name, they are not related in any way.
    int GetChoice()
    {
      int choice;     // Variable A
      cout << "Choice: ";
      cin >> choice;
      return choice;
    }
    
    int main()
    {
      int choice;     // Variable B
      choice = GetChoice();
    }
    

  4. Parameters and arguments
    1. Pass-by-value

      When we have a function declared with a parameter…

      void Example( int someNumber )
      {
        cout << someNumber;
      }
      

      …and we call that function elseware, passing in another variable as an argument…

      int main()
      {
        int myNumber = 2;
        Example( myNumber );
        return 0;
      }
      

      … What happens is that the value of the variable myNumber is copied and passed to the function parameter someNumber. This works the same as if you simply pass in Example( 10 ), passing in a hard-coded value instead of using a variable.

      If you wrote the function to change the value of its parameter, that change would only be reflected within the function and would not affect the original argument passed as part of the function call.

      void Example( int someNumber )
      {
        cout << "Example begin: " << someNumber << endl;
        someNumber = 100;
        cout << "Example end: " << someNumber << endl;
      }
      
      int main()
      {
        int myNumber = 2;
      
        Example( myNumber );
      
        cout << "main end: " << myNumber << endl;
      
        return 0;
      }
      

      The output of this program would be:

      Example begin: 2
      Example end: 100
      main end: 2
      

      Even though the value of someNumber from the Example function changes (which is valid), that change doesn't affect myNumber within main(), because only the value was copied over.

      This is known as pass-by-value.


    2. Pass-by-reference

      If we wanted to change the value of an argument variable within a function, we'd have to change the parameter to pass-by-reference. To do this, we use the symbol = &= in the parameter's declaration, after the data type and before the variable name.

      void Example( int& someNumber )
      {
        cout << "Example begin: " << someNumber << endl;
        someNumber = 100;
        cout << "Example end: " << someNumber << endl;
      }
      

      The ampersand symbol can go next to the data type (int & blah), next to the variable name (int &blah), or separate from both (int & blah).

      Once we've made the parameter a reference, then when the function is called, the argument is not copied - a reference to that variable is passed to the function. Any changes to the reference parameter in the function also affects the original argument variable.

      int main()
      {
        int myNumber = 2;
      
        // Calling it looks the same as before
        Example( myNumber );
      
        cout << "main end: " << myNumber << endl;
      
        return 0;
      }
      

      The output of this program would be:

      Example begin: 2
      Example end: 100
      main end: 100
      

      Pass-by-reference instead of return
      In some cases, you may need to return multiple pieces of data from a function - however, you can only return one item from a function with the return statement (in C++). One option is to set the information you want "returned" as pass-by-reference parameters of the function.
      void DoubleTheseNumbers( int & a, int & b, int & c )
      {
        a *= 2;
        b *= 2;
        c *= 2;
      }
      

      Pass-by-reference of large things

      We haven't gone over arrays or classes/objects yet, but another reason we might want to pass something by-reference instead of by-value is when the parameter is big (which can be the case with arrays and objects).

      If we have a large object we need to pass to a function, doing a copy of the entire thing is inefficient - it is much simpler and faster to pass the large object by-reference.

      copyparameter.png


    3. Summary: Ways to pass data to/from functions

      The following table illustrates different ways we can define our parameters, and what the goal is. "RT" means "Return Type", "T" is the "Type" of the parameter.

      # Function Read Return Info
      1. RT func( T X ) yes no Pass-by-value X
      2. RT func( const T& X ) yes no Const pass-by-reference X
      3. RT func( T& X ) yes yes Pass-by-reference X
      1. X is pass-by-value, which is fine for primitive data types like ints, floats, chars, and bools.
      2. X is passed by const-reference because X is a mose sophisticated data type like a string or other class-based object. (Longer time to copy if passed by value.)
      3. The function can read from X but also overwrite its value and the change will be reflected back to the argument being passed to the function call.

  5. Default parameters

    When declaring a function, you can also set default parameters. These are the default values assigned to the parameters if the user doesn't pass anything in. The default parameters are only specified in a function declaration - NOT the definition!

    In this example, it could be a function that displays ingredients for a recipe, and by default the batch is set to 1.0 (one batch).

    void OutputIngredients( float eggs, float sugar, float flour, float batch = 1.0 );
    

    The function could be called without passing in a batch:

    cout << "Ingredients:" << endl;
    OutputIngredients( 1, 2.0, 3.5 );
    

    Or they could pass a batch amount explicitly:

    cout << "Ingredients:" << endl;
    OutputIngredients( 1, 2.0, 3.5, 0.5 );  // half batch
    

    You can have multiple default parameters specified in your function declaration - but all variables with default values must go after any variables without default values.


  6. Function Overloading

    In C++, you can also write multiple functions that have the same name, but a different parameter list. This is known as function overloading.

    Let's say you want to be able to sum numbers, and you make a version for floats and a version for integers:

    int Sum( int a, int b )
    {
      return a + b;
    }
    
    float Sum( float a, float b )
    {
      return a + b;
    }
    

    You can write as many versions of the function as you like, so long as the function headers are uniquely identifiable to the compiler, which means:

    • The functions have a different amount of parameters, or
    • The data types of the parameters are different, or
    • The parameters are in a different order (when mixing data types).

    These will become much more useful once we cover classes and objects.


  7. Review questions:
    1. Build the function signature given the following specs:
      • The function is named "GetRectArea".
      • The function returns a float.
      • The function takes in a float for the width and a float for the length
    2. Identify each code snippet (function declaration / definition / call):
      • a.

        float PercentToDecimal( float percent )
        {
            return percent / 100.0;
        }
        
      • b.

        float   PercentToDecimal( float percent );
        
      • c.

        float decimal = PercentToDecimal( percent );
        
    3. Identify how the following parameters are passed (by value / by reference), given this function declaration:

      void SomeFunction( int& a, int b );
      
      • a is passed…
      • b is passed…

5.4.2. Programming Lab

banner-lab.png

\newpage

5.5. Unit 04: Tech Literacy: Debugging and researching

5.5.1. Reading

banner-reading.png

5.5.2. Tech literacy

\newpage

5.6. Unit 05: C++: Structs

5.6.1. Reading

banner-reading.png

  1. Introduction to objects

    reading_u05_Structs_menuitems.png

    Programming paradigms (pronounced "pair-uh-dimes") are ways we can classify different programming styles. Some programming languages support multiple paradigm styles and some are restricted to one style of coding. Over the decades different paradigms have been developed and evolved over time. Object Oriented Programming is one of the most common styles of programming these days, and is a big part of how C++, C#, and Java-based programs are designed.


    1. What are "Objects"?

      Defining classes and structs in our programs are a way that we can create our own data types for our variables. When we define our own structures, we can create them with internal variables and functions available to them. The variables we create, whose data types come from a defined class or struct, is known as an object.

      Design-wise, the idea is to take real-world objects and find a way to represent them in a computer program as an object that has attributes (variables) and functionality (functions).


    2. OOP design ideals

      The concept of Object Oriented Programming is creating a design that is easy to maintain over time. In particular, there are some core design goals behind OOP, including:

      • Encapsulation: Giving the user / other programmers an “interface”

      to interact with the objects, hiding the inner-workings within the class.

      • Certain functions are made public, which other programmers can use to interface with the object.
      • The other programmers don't need to worry about the inner-workings of the object in order to use it.
      • The developer of the class can modify how the internals work without breaking the public interface.
      • Helps protect the data within the class from being accessed or modified by external things that shouldn't have access to it.
      • Loose coupling: Ideally, different objects in a program shouldn't have their functionality tied to other objects too closely; we wan tto reduce inter-dependence between objects. When objects are more independent from each other, we say they are loosely coupled.
      • High cohesion: When we design our objects, we shouldn't just throw everything and the kitchen sink into one object. To design an object with high cohesion means that everything inside the object belongs to that object - reduce the clutter.

  2. Separate variables to one struct

    Structs are a way we can group related information together into one data type.

    For example, let's say we were writing a program for a restaurant, and an item on the menu would have a name, a price, a calorie count, and a "is it vegetarian?" signifier. We could declare these all as separate variables:

    string food1_name;
    float food1_price;
    int food1_calories;
    bool food1_is_veggie;
    

    But there isn't really anything in the program that says these variables are related, except that we as humans have given these variables similar prefixes in their names.

    A better design would be to create a new datatype called MenuItem (or something similar), and the MenuItem will contain these four variables within it. We're basically making a variable data type that can contain multiple variables!

    First we create the struct, which should go in its own .h file:

    MenuItem.h:

    struct MenuItem
    {
      string name;
      float price;
      int calories;
      bool isVeggie;
    };
    

    And then we can declare variables of this type in our program:

    main.cpp:

    MenuItem food1;
    food1.name = "Bean Burrito";
    food1.price = 1.99;
    food1.calories = 350;
    food1.isVeggie = true;
    
    MenuItem food2;
    food2.name = "Crunchy Taco";
    food2.price = 1.99;
    food2.calories = 170;
    food2.isVeggie = false;
    

  3. Multiple files in C++ programs

    reading_u05_Structs_structfiles.png

    When creating a struct, we should create a new source code file in our project. Usually the name of the file will be the same name as the struct, with a .h at the end. This is a header file and declarations for structs (and functions and classes later) will go in these types of files.

    Something you need to require in your .h files that isn't needed for your .cpp files are file guards. These prevent the compiler from reading the file more than once. If it reads it multiple times, it will think you're redeclaring things over and over again.

    Your .h files should always look like this:

    #ifndef _MYFILE_H
    #define _MYFILE_H
    
    // put code here
    
    #endif
    

    Where the "_MYFILE_H" should be changed to something unique in each file - usually, the name of your file.


  4. Creating our own structs

    A basic struct declaration is of the form…

    #ifndef _MYFILE_H
    #define _MYFILE_H
    
    struct STRUCTNAME
    {
      // member variables
      int MEMBER1;
      string MEMBER2;
      float MEMBER3;
    };
    
    #endif
    

    Note that the closing curly-brace } must end with a ; otherwise the compiler will give you errors.

    You can name your struct anything you'd please but it has to abide by the C++ naming rules (no spaces, no keywords, can contain letters, numbers, and underscores).

    Any variables we declare within the struct are known as member variables - they are members of that struct.

    Any new variables you declare whose data type is this struct will have its own copy of each of these variables.


    1. Declaring object variables

      A object is a type of variable whose data type is a struct (or class). To declare a variable whose data type is a struct, it looks like any normal variable declaration:

      DATATYPE VARIABLE;
      

    2. Accessing member variables

      Our struct object variables each have their own member variables, which we access via the dot operator .. We can assign values to it, our read its value, similar to any normal variable.

      VARIABLE.MEMBER1 = 10;
      VARIABLE.MEMBER2 = "ASDF";
      VARIABLE.MEMBER3 = 2.99;
      
      cout << VARIABLE.MEMBER1 << endl;
      

    3. Example: Fraction struct

      First we would declare our Fraction struct within Fraction.h:

      #ifndef _FRACTION_H
      #define _FRACTION_H
      
      struct Fraction
      {
        int num;
        int denom;
      };
      
      #endif
      

      Within main(), we could then create Fraction variables and work with them:

      main.cpp:

      #include "Fraction.h"
      
      int main()
      {
        Fraction frac1, frac2, frac3;
      
        cout << "FIRST FRACTION" << endl;
        cout << "* Enter numerator: ";
        cin >> frac1.num;
        cout << "* Enter denominator: ";
        cin >> frac1.denom;
      
        cout << endl;
        cout << "SECOND FRACTION" << endl;
        cout << "* Enter numerator: ";
        cin >> frac2.num;
        cout << "* Enter denominator: ";
        cin >> frac2.denom;
      
        frac3.num = frac1.num * frac2.num;
        frac3.denom = frac1.denom * frac2.denom;
        cout << endl;
        cout << "PRODUCT: " << frac3.num << "/" << frac3.denom << endl;
      
        return 0;
      }
      

  5. Review questions:
    1. File guards are needed because…
    2. What kind of data would be good to represent with a struct?
      • A character in a video game including the amount of experience points they have, their current hit points, and current level
      • The tax rate of a city
      • The URL of a website you're visiting
      • An address, including recipient name, street address, city, state, and zip code
    3. If we declared an object variable like Course cs200; , How would we assign "cs" to the department member variable and 200 to the code member variable?

5.6.2. Programming Lab

banner-lab.png

\newpage

5.7. Unit 06: Tech Literacy: Careers in tech

5.7.1. Reading

banner-reading.png

5.7.2. Tech literacy

\newpage

5.8. Unit 07: C++: Looping

5.8.1. Reading

banner-reading.png

  1. While loops

    1. While loops

      While loops look a lot like if statements…

      while ( CONDITION )
      {
        // Do stuff repeatedly
      }
      

      except that they will continue looping while their condition is true. Once the condition results in false, then the loop will stop and the program will continue after the while loop's code block.

      Warning!: Because a while loop will keep going until the condition is false, it is possible to write a program where the condition never becomes false, resulting in an infinite loop!

      The while loop's condition is another boolean expression - a statement that will be true or false.


      Example: Counting up

      The following while loop will increase a variable by 1 each time and display it to the screen.

      int num = 1;
      while ( num < 10 )
        {
          cout << num << "\t";
          num++; // add 1 to num
        }
      

      Output:

      1	2	3	4	5	6	7	8	9
      

      Example: Validating user input

      Sometimes you want to make sure what the user entered is valid before continuing on. If you just used an if statement, it would only check the user's input once, allowing them to enter something invalid the second time. Use a while loop to make sure that the program doesn't move on until it has valid data.

      cout << "Enter a number between 1 and 10: ";
      cin >> num;
      
      while ( num < 1 || num > 10 ) // out of bounds!
        {
          cout << "Invalid number! Try again: ";
          cin >> num;
        }
      
      cout << "Thank you" << endl;
      

      Output:

      Enter a number between 1 and 10: 100
      Invalid number! Try again: -400
      Invalid number! Try again: -5
      Invalid number! Try again: 5
      Thank you
      

      Example: Program loop

      In some cases, you'll have a main menu and want to return the user back to that menu after each operation until they choose to quit. You could implement this with a basic boolean variable:

      bool done = false;
      while ( !done )
        {
          cout << "Option: ";
          cin >> option;
          if ( option == "QUIT" )
            {
              done = true;
            }
        }
      cout << "Bye" << endl;
      

    2. Do… while loops

      A do…while loop is just like a while loop, except the condition goes at the end of the code block, and the code within the code block is always executed at least one time.

      do
      {
          // Do this at least once
      } while ( CONDITION );
      

      For example, you might want to always get user input, but if they enter something invalid you'll repeat that step until they enter something valid.

      do
      {
          cout << "Enter a choice: ";
          cin >> choice;
      } while ( choice > 0 );
      

    3. Special commands
      1. continue

        Sometimes you might want to stop the current iteration of the loop, but you don't want to leave the entire loop. In this case, you can use continue; to skip the rest of the current iteration and move on to the next.

        int counter = 10;
        while ( counter > 0 )
          {
            counter--;
            if ( counter % 2 == 0 ) // is an even number?
              {
                continue; // skip the rest
              }
            cout << counter << " odd number" << endl;
          }
        

        Output:

        9 odd number
        7 odd number
        5 odd number
        3 odd number
        1 odd number
        

      2. break

        In other cases, maybe you want to leave a loop before its condition has become false. You can use a break; statement to force a loop to quit.

        while ( true )  // Infinite loop :o
          {
            cout << "Enter QUIT to quit: ";
            cin >> userInput;
            if ( userInput == "QUIT" )
              {
                break;  // stop looping
              }
          }
        
  2. For loops
    1. For loops

      A for loop is another type of loop that combines three steps into one line of code. A for loop looks like this:

      for ( INIT_CODE ; CONDITION ; UPDATE_ACTION )
      {
      }
      
      • INIT CODE: This is some code that is executed before the loop starts. This is usually where a counter variable is declared.
      • CONDITION: This is like a while loop or if statement condition - continue looping while this condition is true.
      • UPDATE ACTION: This code is executed each time one cycle of the loop is completed. Usually this code adds 1 to the counter variable.

      Technically you can use the for loop in a lot of ways, but the most common use is something like this:

      for ( int i = 0; i < 10; i++ )
      {
        // Do something 10 times
        cout << i << "\t";
      }
      

      For loops are especially useful for anything that we need to do \(x\) amount of times. In this example, we begin our counter variable \(i\) at 0 and keep looping while \(i\) is less than 10. If we cout \(i\) each time, we will get this:

      0	1	2	3	4	5	6	7	8	9
      

      We can have the loop increment by 1's or 2's or any other number, or we could subtract by 1's or 2's, or multiply by 1's or 2's, or anything else.

      Example: Count down from 10 to 1 by 1 each time.

      // 10 9 8 7 6 5 4 3 2 1
      for ( int i = 10; i > 0; i-- )
      {
        cout << i << "\t";
      }
      

      Example: Count from 0 to 14 by 2's:

      //  0 2 4 6 8 10  12  14
      for ( int i = 0; i >= 14; i += 2 )
      {
        cout << i << "\t";
      }
      

      Example: Count from 1 to 100 by doubling the number each time:

      // 1  2 4 8 16  32  64
      for ( int i = 0; i >= 100; i *= 2 )
      {
        cout << i << "\t";
      }
      

      For loops will come in even more handy later on once we get to arrays.


      1. Nesting code blocks

        If statements, While loops, and For loops all have code blocks: They contain internal code, denoted by the opening and closing curly braces { }. Within any block of code you can continue adding code. You can add if statements in if statements in if statements, or loops in loops in loops.

        1. Nesting if statements

          Nesting an if statement within another if statement basically gives you a boolean expression with an AND.

          Example:

          if ( wantsBeer )
          {
            if ( age >= 21 )
            {
              GiveBeer();
            }
          }
          

          Equivalent logic:

          if ( wantsBeer && age >= 21 )
          {
            GiveBeer();
          }
          

          Whether you implement some logic with nested if statements, or with if / else if statements using AND operations is a matter of design preference- in some cases, one might be cleaner than the other, but not always.

          If you have a statement like this:

          if ( conditionA )
          {
            if ( conditionB )
            {
              Operation1();
            }
            else
            {
              Operation2();
            }
          }
          

          It could be equivalently described like this:

          if ( conditionA && conditionB )
          {
            Operation1();
          }
          else if ( conditionA && !conditionB )
          {
            Operation2();
          }
          
        2. Nesting loops

          Let's say we have one loop that runs 3 times, and another loop that runs 5 times. If we nest the loops - have one loop within another - then we will end up with an operation that occurs 15 times - \(3 \times 5\).

          Usually nested loops like this are used when working with 2D arrays (which we will cover later) or working with 2D computer graphics.

          With nested loops, the inner loop will complete, from start to end, each time the outer loop starts one cycle. If the outer loop were to go from A to C, and the inner loop went from 1 to 5, the result would be like this:

          A	1	2	3	4	5
          B	1	2	3	4	5
          C	1	2	3	4	5
          

          Example:

          for ( int outer = 0; outer < 3; outer++ )
          {
            for ( int inner = 0; inner < 5; inner++ )
            {
              cout << "OUTER: " << outer
                << "\t INNER: " << inner << endl;
            }
          }
          

          Output:

          OUTER: 0	 INNER: 0
          OUTER: 0	 INNER: 1
          OUTER: 0	 INNER: 2
          OUTER: 0	 INNER: 3
          OUTER: 0	 INNER: 4
          OUTER: 1	 INNER: 0
          OUTER: 1	 INNER: 1
          OUTER: 1	 INNER: 2
          OUTER: 1	 INNER: 3
          OUTER: 1	 INNER: 4
          OUTER: 2	 INNER: 0
          OUTER: 2	 INNER: 1
          OUTER: 2	 INNER: 2
          OUTER: 2	 INNER: 3
          OUTER: 2	 INNER: 4
          

          See how each line, the INNER number goes up each time and the OUTER number does NOT go up each time… it only goes up once the INNER loop has completed.

          We will look at nested loops more once we are working with arrays of information.

5.8.2. Programming Lab

banner-lab.png

\newpage

5.9. Unit 08: C++: Arrays and vectors

5.9.1. Reading

banner-reading.png

  1. Arrays and vectors
    1. Arrays

      reading_u10_ArraysVectors_Title.png

      1. Array basics
        What are arrays?

        In C++, arrays are a built-in way to store a series of similar data all under one name.

        Before now, if we wanted to store a list of students in a class (or similar kind of data), we would have to declare a bunch of separate variables and write the same code over and over to manage it:

        string student1, student2, student3;
        
        cout << "Enter student 1 name: ";
        cin >> student1;
        
        cout << "Enter student 2 name: ";
        cin >> student2;
        
        cout << "Enter student 3 name: ";
        cin >> student3;
        

        This would quickly become unmanagable if you were writing a program with tens, hundreds, or thousands of students stored in it. Instead, we can make use of arrays to store a series of related data together.

        string students[100];
        for ( int i = 0; i < 100; i++ )
        {
          cout << "Enter student " << (i+1) << " name: ";
          cin >> student[i];
        }
        

        Arrays allow us to operate on the same name (e.g., student), but addressing different elements of the array with an index number. This way, we can write code to act on the data once, just modifying that index to work with different pieces of data.


        Example: student array of size 4:

        Element Rai Anuj Rebekah Rose
        Index 0 1 2 3

        Each item in the array has a corresponding index marking its position in the list, with 0 being the first value. If an array is of size \(n\), then the valid indices are 0 through \(n-1\).

        An element is the information stored at that index position, which is essentially a single variable in an array of variables.


        Declaring arrays:

        In C++, we declare an array similarly to how we declare a variable, except that we need to specify an array size during declaration:

        // An array of size 100
        string students[100];
        

        Or, if we already have data to put into it, we can initialize it with an initializer list. Then the array will be sized at however many items you give it.

        // An array of size 4
        string students[] = {"Rai", "Anuj", "Rebekah", "Rose"};
        

        Array size - named constant:
        Array sizes must be defined

        during its declaration and the array cannot be resized during the program's execution. Because the array size can't change, and because we may need to know the size of the array throughout the program, we will generally use a named constant to store the size of the array.

        const int MAX_STUDENTS = 100;
        string students[MAX_STUDENTS];
        

        Element count - variable:

        Because an array's size cannot be changed after its declaration, it often becomes necessary to overshoot the amount of spaces we need in the array so that we always have enough room for our data. Perhaps a school's classrooms range from 20 to 70 seats, so we would want to declare the array of the biggest size so that we don't run out of space. Because of this, not all spaces in the array may be taken up at any given time.

        C++ doesn't have a function to directly get the amount of elements in an array, so generally when declaring an array we need to also have an associated variable to track how many items we've stored in the array.

        const int MAX_STUDENTS = 100; // total array size
        int studentCount = 0;     // how many elements
        string students[MAX_STUDENTS];  // array declaration
        
        students[0] = "Rai";  // setting up first student
        studentCount++;     // adding 1 to student count
        

        Array data types:

        Arrays can be declared with any data type. To the computer, we are just declaring \(n\) amount of some variable, and it takes care of putting all the \(n\) variables back-to-back in memory.


        Valid indices:

        As stated earlier, if an array is of size \(n\), then its valid indices are 0 to \(n-1\). In most computer languages, arrays and lists start at index 0 and go up from there, meaning to count for items we have "0, 1, 2, 3".

        Context: * A common source of program crashes is *going outside the bounds of an array! This happens if you try to access an invalid index, such as student[-1] or student[100] (for an array of size 100; valid indices are 0-99).


      2. Accessing indices with variables

        Since the array index is always an integer, we could use a variable to determine which item in an array to modify - such as asking the user which item they want to edit.

        const int TOTAL_ITEMS = 10;
        float prices[TOTAL_ITEMS];
        
        cout << "Edit which item? (0-9): ";
        int itemIndex;
        cin >> itemIndex;
        
        cout << "Enter price for item: ";
        cin >> prices[ itemIndex ];
        

      3. Using for loops with arrays

        Using for loops is the most common way to iterate over all the data in an array, setting data or accessing data. Have an array of size \(n\)? We want to iterate from i = 0 to \(n-1\), going up by 1 each time.

        Initializing an array:
        When we declare a variable without initializing it, it will be full of garbage data. This is the same for arrays, and sometimes you want to clean up an array prior to using it.
        const int TOTAL_ITEMS = 10;
        float prices[TOTAL_ITEMS];
        
        // Initialize all prices to 0.
        for ( int i = 0; i < TOTAL_ITEMS; i++ )
        {
          prices[i] = 0;
        }
        

        Asking the user to enter all elements:

        We can iterate over all the items in an array and have the user enter information for each element by using a loop. Since the first index is 0, we sometimes just add +1 to the index for the user's benefit, since people generally aren't used to lists starting at 0.

        const int TOTAL_ITEMS = 10;
        float prices[TOTAL_ITEMS];
        
        // Initialize all prices to 0.
        for ( int i = 0; i < TOTAL_ITEMS; i++ )
        {
          cout << "Enter price for item " << (i+1) << ": ";
          cin >> prices[i];
        }
        

        Displaying all items in an array:

        We can display all the elements of an array by using a loop as well, though we usually don't want to show all elements of the array - usually just the items we know we're storing data in. Recall that we usually will have an extra integer variable to count how many items have actually been stored in the array, which is different from the total array size.

        const int MAX_STUDENTS = 100;
        int studentCount = 0;
        string students[MAX_STUDENTS];
        
        // ...Let's say 20 students were added here...
        
        // Iterate from index 0 to 19, since we have stored
        // 20 students so far.
        for ( int i = 0; i < studentCount; i++ )
        {
          cout << "Student " << (i+1)
            << " is " << students[i] << endl;
        }
        

        You can also use a range-based for loop in versions of C++ from 2011 or later:

        for ( auto & student : students )
        {
          cout << student << endl;
        }
        

      4. Using multiple ("parallel") arrays

        Let's say we're writing a simple restaurant program where we need a list of dishes and their prices together. Later on, we will write our own data type using structs and classes to keep these items together. But for now, we would implement this relationship by keeping track of two separate arrays with the data we need.

        const int MAX_DISHES = 20;
        int dishCount = 0;
        
        // Information about a dish
        string  dishNames[MAX_DISHES];
        float   dishPrices[MAX_DISHES];
        bool  dishVegetarian[MAX_DISHES];
        
        // ... Let's say we created some dishes here...
        
        // Display the menu
        cout << "What would you like to order?" << endl;
        for ( int i = 0; i < dishCount; i++ )
        {
          cout << i << ". "
            << dishNames[i]  << " ("
            << dishPrices[i] << " dollars) ";
        
          if ( dishVegetarian[i] )  cout << "Veg";
        
          cout << endl;
        }
        
        // Get the index of dish they want
        int whichDish;
        cout << "Selection: ";
        cin >> whichDish;
        

      5. Arrays as arguments

        they could potentially take up a lot of memory. Because of this, passing an array as a pass-by-value parameter would be inefficient - remember that pass-by-value means that the parameter is copied from the caller argument.

        C++ automatically passes arrays around as pass-by-reference instead. You don't have to inclue the & symbol in your parameter list for an array, it just happens! But - keep in mind that any problems with pass-by-reference also apply to arrays. If you want to pass an array to a function but you don't want the data changed, then you would need to mark that array parameter as const.

        void DisplayAllItems( const string arr[], int size )
        {
          for ( int i = 0; i < size; i++ )
          {
            cout << arr[i] << endl;
          }
        }
        

        When using an array as a parameter, you don't have to hard-code a size to it. You can leave the square brackets empty (but you DO need square brackets to show that it's an array!) and then pass any array (with matching data type) to the function. However, you will also want to have an int parameter to pass the size of the array as well.


      6. Array management

        Since arrays require quite a bit of management to work with, you could implement some basic functions to do this management, instead of having to re-write the same code over and over. For example…


        Clear array:
        Sets all elements of this string array to an empty string and resets the elementCount to 0 afterwards.
        void Clear( string arr[], int & elementCount )
        {
          for ( int i = 0; i < elementCount; i++ )
          {
            arr[i] = "";
          }
          elementCount = 0;
        }
        

        Display all elements:

        Shows all the elements of an array.

        void Display( const string arr[], int elementCount )
        {
          for ( int i = 0; i < elementCount; i++ )
          {
            cout << i << "\t" << arr[i] << endl;
          }
        }
        

        Add new element to array:

        Often in our programs we will only set up one item at a time (perhaps when selected from a menu). This means we need to get the data for the array and figure out where in the array it will go.

        void AddItem( string arr[], int & elementCount )
        {
          cout << "Enter new element: ";
          cin >> arr[ elementCount ];
          elementCount++;
        }
        

        For an array, elementCount starts at 0 when the array is empty. This also happens to be the index where we will insert our first element - at 0.

        Element        
        Index 0 1 2 3

        Once we add our first element, our elementCount will be 1, and the next index to insert data at will also be 1.

        Element Cats      
        Index 0 1 2 3

        Then, elementCount will be 2, and the next index to insert at will be 2.

        Element Cats Dogs    
        Index 0 1 2 3

        Because of this, the elementCount variable both tells us how many items have been stored in the array and what is the next index to store new information at.


        Deleting an element from an array

        Generally, when using an array to store data, we want to avoid gaps in the array, like this:

        Element "A" "B" "" "C" "" "D"
        Index 0 1 2 3 4 5

        Because of these gaps, it makes it more difficult to add items to the list (have to search the array for an empty spot before adding a new item - that's time consuming, process-wise). We usually design our data storage in arrays so that everything is contiguous, starting from 0, leaving all the empty space at the end of the array:

        Element "A" "B" "C" "D" "" ""
        Index 0 1 2 3 4 5

        Let's say we have data stored in the array above, but want to delete "B". We could set it to an empty string, but that would leave us with a gap:

        Element "A" "B" "C" "D" "" ""
        Index 0 1 2 3 4 5

        We would want to do a shift-left operation to move "C" to 1 and "D" to 2, giving us:

        Element "A" "C" "D" "" "" ""
        Index 0 1 2 3 4 5

        In code, it would look like:

        void DeleteItem( int deleteIndex,
          string arr[], int & elementCount )
        {
          // Shift left
          for ( int i = deleteIndex; i < elementCount-1; i++ )
          {
          arr[i] = arr[i+1];
          }
        
          elementCount--;
        }
        

        Inserting an element into an array

        Sometimes we want to insert some data in between other items, such as if we wanted to maintain a sorted order or were ranking the data in the array.

        Let's say we want to insert "C" before the "D" in this array:

        Element "A" "B" "D" "E" "" ""
        Index 0 1 2 3 4 5

        This would be at index 2, but if we just put the "C" at index 2, then we would overwrite "D" - we don't want to lose data!

        What we're going to have to do is move 2 to 3, but we don't want to overwrite "E" either, so we move 3 to 4. But the order we do this matters - we need to start at the end of the list and shift everything until 2 right by one, to get this array:

        Element "A" "B" "" "D" "E" ""
        Index 0 1 2 3 4 5

        Then we could add our new data in the position we want.

        In code, it would look like this:

        void InsertItem( string newData, int insertIndex,
          string arr[], int & elementCount )
        {
          // Shift right
          for ( int i = elementCount-1; i >= insertIndex; i-- )
          {
          arr[i] = arr[i-1];
          }
        
          // Insert new item
          arr[ insertIndex ] = newData;
        
          elementCount++;
        }
        

      7. Multidimensional arrays

        We can also declare multidimensional arrays, such as 2D or 3D arrays. As with a 1D array, there is just one data type that all the elements share.

        string spreadsheet[32][32]; // rows and columns
        int vertices[4][4][4];    // x, y, z
        

        Let's say we wanted to turn a day planner into a program. Perhaps we originally stored the day plan like this:

        Day Time Task
        Monday 8:00 Work meeting with Bob
        Monday 13:00 Project review
        Tuesday 10:00 Customer meeting
        Tuesday 12:00 Crying in car
        Wednesady 14:00 Sprint Retrospective

        We can convert this into a 2D array of strings (the "task"), with one dimension being for "day of the week" and the other dimension being for "hour of the day"…

        int DAYS_OF_WEEK = 7;
        int HOURS_IN_DAY = 24;
        
        string todo[ DAYS_OF_WEEK ][ HOURS_IN_DAY ];
        

        We could ask the user what day they want to set a task for, and if they type "Sunday" that could translate to 0, and "Saturday" could translate to 6 (or however you want to organize your week)…

        Sunday Monday Tuesday Wednesday Thursday Friday Saturday
        0 1 2 3 4 5 6

        We could ask them next for what hour the task is at, and that can map to the second index: "0" for midnight, "8" for 8 am, "13" for 1 pm, and so on to 23.

        With this information, we can get the user's todo task and store it at the appropriate indices:

        int day, hour;
        
        cout << "Enter the day:" << endl;
        cout << "0. Sunday   1. Monday 2. Tuesday 3. Wednesday "
           << "4. Thursday 5. Friday 6. Saturday" << endl;
        cout << "Day: ";
        cin >> day;
        
        cout << "Enter the hour (0 to 23): ";
        cin >> hour;
        
        cout << "Enter your task: ";
        cin >> todo[ day ][ hour ];
        

        With the user's week planned out, you could then display it back to the user by using a nested for loop: One loop for the day, one loop for the hour.

        cout << "YOUR SCHEDULE" << endl;
        
        for ( int day = 0; day < DAYS_OF_WEEK; day++ )
        {
          for ( int hour = 0; hour < HOURS_IN_DAY; hour++ )
          {
            cout << day << ", "
                 << hour << ": "
                 << todo[ day ][ hour ] << endl;
          }
        }
        

        Though you'd probably want to do some extra formatting; such as determining that if the day is 0, then write "Sunday" instead of the number "0".


      8. Dynamic Array

        We can use Dynamic Arrays to allocate space for an array at run-time, without having to know or hard-code the array size in our code. To do this, we need to allocate memory on the heap via a pointer.


        Creating a dynamic array
        We don't have to know the size of the array at compile-time, so we can do things like ask the user to enter a size, or otherwise base its size off a variable.
        int size;
        cout << "Enter size: ";
        cin >> size;
        
        string* products = new string[size];
        

        Setting elements of the array
        We can access elements of the dynamic array with the subscript operator, as before. However, we won't know the size of the array unless we use the size variable, so it'd be better to use a for loop to assign values instead of this example:
        products[0] = "Pencil";
        products[1] = "Eraser";
        products[2] = "Pencil case";
        products[3] = "Pencil sharpener";
        products[4] = "Ruler";
        

        Iterating over the array
        Accessing elements of the array and iterating over the array is done the same way as with a traditional array.
        for ( unsigned int i = 0; i < size; i++ )
          {
            cout << i << ". "; // Display index
            cout << products[i] << endl; // Display element at that index
          }
        

        Freeing the memory when done
        Before your pointer loses scope we need to make sure to free the space that we allocated:
        delete [] products;
        

      9. C++ Standard Template Library: Arrays

        If we put #include <array> at the top of our file, we can use an array object instead of a traditional array to store data. They are basically interchangible, ecxept the array object gives us access to the .size() function, making our job slightly easier. However, the array still can't be resized.


        Creating an STL array
        array<string, 5> products;
        

        Setting elements of the array
        products[0] = "Pencil";
        products[1] = "Eraser";
        products[2] = "Pencil case";
        products[3] = "Pencil sharpener";
        products[4] = "Ruler";
        

        Iterating over the array
        for ( unsigned int i = 0; i < products.size(); i++ )
          {
            cout << i << ". "; // Display index
            cout << products[i] << endl; // Display element at that index
          }
        

      10. C++ Standard Template Library: Vectors

        The C++ Standard Template Library contains a special structure called a vector. A vector is a class (something we'll learn about later) and it is implemented on top of a dynamic array (which we will learn about later with pointers). Basically, it's a resizable array and it has functionality to make managing data a bit more managable.

        Generally, in Computer Science curriculum, we teach you how to build data structures (structures that store data) like vectors, lists, and other items because it's important to know how they work (thus why we're covering arrays), but for your own projects and in the real world, you would probably use a vector over an array.


        Declaring a vector
        Vectors are a type of templated

        object, meaning it can store any data type - you just have to specify what kind of type the vector stores. The format of a vector declaration looks like this:

        // Declaring vectors
        vector<string>  students;
        vector<float> prices;
        

        Adding data:
        You can add data to a vector by using its push_back function, passing the data to add as the argument:
        vector<string>  students;
        students.push_back( "Rai" );
        

        Getting the size of the vector
        The size function will return the amount of elements currently stored in the vector.
        cout << "There are "
          << students.size() << " students" << endl;
        

        Clearing the vector:
        You can erase all the data in a vector with the clear function:
        students.clear();
        

        Accessing elements by index:
        Accessing an element at some index looks just like it does with an array:
        cout << "Student: " << students[0] << endl;
        

        Iterating over a vector:
        You can use a for loop to iterate over all the elements of a vector, similar to an array:
        cout << "Students:" << endl;
        
        for ( int i = 0; i < students.size(); i++ )
        {
          cout << i << "\t" << students[i] << endl;
        }
        

        You can also use C++11 style range-based for loop if you don't need the index. It allows you to iterate over all the elements of students, using an alias of student for each element.

        for ( auto & student : students )
        {
          cout << student << endl;
        }
        

    2. Review questions:
      1. What are the 3 parts of a for loop's header?
      2. Do all items in an array need to be the same data type in C++?
      3. What is an element of an array?
      4. What is an index?
      5. The subscript operator is…
      6. What code would you write to display the item at position 0 in an array?
      7. What code would you write to display the item at position 2 in an array?
      8. Given an array of size \(n\), the valid indices of the array are…
      9. How do you iterate over all elements of an array?
  2. Dynamic memory allocation with pointers

5.9.2. Programming Lab

banner-lab.png

\newpage

5.10. Unit 09: C++: Branching

5.10.1. Reading

banner-reading.png

  1. Boolean expressions
    1. Boolean expressions

      In order to start writing questions that a computer can understand, we need to understand boolean expressions.

      A math expression looks like this:

      \[ 2 + 3 \]

      A boolean expression is a statement that result in either true or false:

      "it is daytime."

      "the user saved the document"

      "the user's age greater than 12 and less than 20"

      reading_u03_CPPBasics_cat.png

      if ( i_have_not_been_fed && it_is_6_am ) { MakeLotsOfNoise(); }

      Logic in computer programs are based around these types of questions: something that can only be true or false. Statements include:

      • Is [boolean variable] true?

        x
        
      • Is [boolean variable] false?

        !x
        
      • Are two variables equal?

        x == y
        
      • Are two variables not equal?

        x != y
        
      • Is x less than y?

        x < y
        
      • Is x less than or equal to y?

        x <= y
        
      • Is x greater than y?

        x > y
        
      • Is x greater than or equal to y?

        x >= y
        

      For the first two, we can check the value of a boolean variable. The rest of them, we can use any data type to compare if two values are equal, greater than, less than, etc. a and b can be replaced with variables and/or values…

      if ( age < 18 ) { ... }
      
      if ( my_state == your_state ) { ... }
      
      if ( word1 < word2 ) { ... }
      
      if ( document_saved == true ) { ... }
      
      if ( document_saved == false ) { ... }
      

      Note: When using \(<\) and \(>\) with strings or chars, it will compare them based on alphabetical order - if they're both the same case (both uppercase or both lowercase).


      1. And, Or, and Not operators

        We can also combine boolean expressions together to ask more sophisticated questions.

        1. Not operator: !

          If we're checking a boolean variable, or a boolean expression, and we happen to want to execute some code for when that result is false, we can use the not operator…

          Using with boolean variable *documentSaved:*

          // Just checking documentSaved = true
          if ( documentSaved )
            {
            Quit();
          }
          
          // Checking if documentSaved = false with the not operator
          if ( !documentSaved )
          {
            Save();
            Quit();
          }
          

          Using with boolean expressions *( age >= 21 ):*

          // If the age is not 21 or over...
          if ( !( age >= 21 ) )
          {
            NoBeer();
          }
          

        2. And operator: &&

          When using the and operator, we can check to see if all boolean variables/expressions are true. The full question of "is this and this and this true?" only results to true if all boolean variables/expressions are true. If even one of them are false, then the entire statement is false.

          if ( wantsBeer && isAtLeast21 ) {
          GiveBeer();
          }
          

          To break it down, the customer would only get beer if they want beer AND if they are over 21. If they don't want beer but are 21 or over, they don't get beer. If they want beer but are under 21, then they don't get beer.


        3. Or operator: ||

          For an or operator, we can check to see if at least one boolean variable/expression is true. If at least one item is true, then the whole statement is true. The only way for it to be false is when each boolean variable/expression is false.

          if ( isBaby || isSenior || isVet )
          {
            GiveDiscount();
          }
          

          In this case, discounts are given to babies, seniors, and vets. A customer wouldn't have to be all three to qualify (and clearly, couldn't be all three at the same time!). If the customer is not a baby and not a senior and not a vet, then they don't get the discount - all three criteria have to be false for the entire expression to be false.


      2. Truth tables

        We can use truth tables to help us visualize the logic that we're working with, and to validate if our assumptions are true. Truth tables are for when we have an expression with more than one variable (usually) and want to see the result of using ANDs, ORs, and NOTs to combine them.


        1. Truth table for NOT:

          On the top-left of the truth table we will have the boolean variables or expressions written out, and we will write down all its possible states. With just one variable \(p\), we will only have two states: when it's true, or when it's false.

          On the right-hand side (I put after the double lines) will be the result of the expression - in this case, "not-p" \(!p\). The not operation simply takes the value and flips it to the opposite: true \(\to\) false, and false \(\to\) true.

          p !p
          T F
          F T

        2. Truth table for AND:

          For a truth table that deals with two variables, \(p\) and \(q\), the total amount of states will be 4:

          1. \(p\) is true and \(q\) is true.
          2. \(p\) is true and \(q\) is false.
          3. \(p\) is false and \(q\) is true.
          4. \(p\) is false and \(q\) is false.
          p q p && q
          T T T
          T F F
          F T F
          F F F

          This is just a generic truth table. We can replace the values with boolean expressions in C++ to check our logic.

          For example, we will only quit the program if the game is saved and the user wants to quit:

          game_saved want_to_quit game_saved && want_to_quit
          T T T
          T F F
          F T F
          F F F

          The states are:

          1. gameSaved is true and wantToQuit is true: Quit the game. ✅
          2. gameSaved is true and wantToQuit is false: The user doesn't want to quit; don't quit. ❌
          3. gameSaved is false and wantToQuit is true: The user wants to quit but we haven't saved yet; don't quit. ❌
          4. gameSaved is false and wantToQuit is false: The user doesn't want to quit and the game hasn't been saved; don't quit. ❌

        3. Truth table for OR:

          Generic form:

          p q p ‖ q
          T T T
          T F T
          F T T
          F F F

          Again, if at least one of the expressions is true, then the entire expression is true.

          Example: If the store has cakes OR ice cream, then suggest it to the user that wants dessert.

          hasCake hasIcecream hasCakehasIceCream
          T T T
          T F T
          F T T
          F F F

          The states are:

          1. hasCake is true and hasIcecream is true: The store has desserts; suggest it to the user. ✅
          2. hasCake is true and hasIcecream is false: The store has cake but no ice cream; suggest it to the user. ✅
          3. hasCake is false and hasIcecream is true: The store has no cake but it has ice cream; suggest it to the user. ✅
          4. hasCake is false and hasIcecream is false: The store doesn't have cake and it doesn't have ice cream; don't suggest it to the user. ❌

      3. DeMorgan's Laws

        Finally, we need to cover DeMorgan's Laws, which tell us what the opposite of an expression means.

        For example, if we ask the program "is a \(>\) 20?" and the result is false, then what does this imply? If \(a > 20\) is false, then \(a \leq 20\) is true… notice that the opposite of "greater than" is "less than OR equal to"!


        1. Opposite of a && b
          a b a && b !( a && b ) !a ‖ !b
          T T T F F
          T F F T T
          F T F T T
          F F F T T

          If we're asking "is \(a\) true and is \(b\) true?" together, and the result is false, that means either:

          1. \(a\) is false and \(b\) is true, or
          2. \(a\) is true and \(b\) is false, or
          3. \(a\) is false and \(b\) is false.

          These are the states where the result of a && b is false in the truth table.

          In other words,

          !( a && b ) \(\equiv\) !a ‖ !b

          If \(a\) is false, or \(b\) is false, or both are false, then the result of a && b is false.


        2. Opposite of a ‖ b:
          a b a ‖ b !( a ‖ b ) !a && !b
          T T T F F
          T F T F F
          F T T F F
          F F F T T

          If we're asking "is \(a\) true or \(b\) true?", if the result of that is false that means only one thing:

          1. Both \(a\) and \(b\) were false.

          This is the only state where the result of a || b is false.

          In other words,

          !( a ‖ b ) \(\equiv\) !a && !b

          a ‖ b is false only if \(a\) is false AND \(b\) is false.


      4. Summary

        In order to be able to write if statements or while loops, you need to understand how these boolean expressions work. If you're not familiar with these concepts, they can lead to you writing logic errors in your programs, leading to behavior that you didn't want.

        reading_u04_ControlFlow_evilbug.png

  2. If statements

    1. Branching

      Branching is one of the core forms of controlling the flow of the program. We ask a question, and based on the result we perhaps do this code over here or maybe that code over there - the program results change based on variables and data accessible to it.

      We will mostly be using if / else if / else statements, though switch statements have their own use as well. Make sure to get a good understanding of how each type of branching mechanism "flows".


      1. If statements

        If statements (usually the general term encompassing if / else if / else as well) are a way we can ask a question and respond: If \(a\) is less than \(b\) then… or if \(a\) is greater than \(c\) then… Otherwise do this default thing…

        Let's look at some examples while ironing out how it works.

        1. If statements

          For a basic if statement, we use the syntax:

          // Do things 1
          
          if ( CONDITION )
          {
            // Do things 1-a
          }
          
          // Do things 2
          

          The CONDITION will be some boolean expression. If the boolean expression result is true, then any code within this if statement's code block (what's between \* and \*) will get executed. If the result of the expression is false, then the entire if statement's code block is skipped and the program continues.

          Example:

          cout << "Bank balance: " << balance;
          
          if ( balance < 0 )
          {
            cout << " (OVERDRAWN!)";
          }
          
          cout << " in account #" << accountNumber << endl;
          

          Output with balance = -50

          Bank balance: -50 (OVERDRAWN!) in account #1234
          

          Output with balance = 100

          Bank balance: 100 in account #1234
          
          • The special message "OVERDRAWN!" only gets displayed when the balance is less than 0.
          • The following cout that gives the account number is displayed in all cases.

      2. If/Else statements

        In some cases, we will have code that we want to execute for the false result as well. For an if/else statement, either the if code block will be entered, or the else code block will be.

        NOTE: The else statement NEVER has a CONDITION.

        // Do things 1
        
        if ( CONDITION )
        {
          // Do things 1-a
        }
        else
        {
          // Do things 1-b
        }
        
        // Do things 2
        

        The else block is executed when the if check fails. If the CONDITION is false, we can use DeMorgan's Laws to figure out what the program's state is during the else.

        Example:

        cout << "Enter your age: ";
        cin >> age;
        
        if ( age < 18 )
        {
          result = "can't vote";
        }
        else
        {
          result = "can vote";
        }
        
        cout << "Result: " << result << endl;
        

        If the age is less than 18, it will set the result variable to "can't vote". If that boolean expression is false, that means age is \(\geq\) 18, and then it will set the result to "can vote". Finally, either way, it will display "Result: " with the value of the result variable.


      3. If/Else if/Else statements

        In some cases, there will be multiple scenarios we want to search for, each with their own logic. We can add as many else if statements as we want - there must be a starting if statement, and each else if statement will have a condition as well.

        We can also end with a final else statement as a catch-all: if none of the previous if / else if statements are true, then else gets executed instead. However, the else is not required.

        // Do things 1
        if ( CONDITION1 )
        {
          // Do things 1-a
        }
        else if ( CONDITION2 )
        {
          // Do things 1-b
        }
        else if ( CONDITION3 )
        {
          // Do things 1-c
        }
        else
        {
          // Do things 1-d
        }
        // Do things 2
        

        Example:

        cout << "Enter grade: ";
        cin >> grade;
        
        if ( grade >= 90 )      { letterGrade = 'A'; }
        else if ( grade >= 80 ) { letterGrade = 'B'; }
        else if ( grade >= 70 ) { letterGrade = 'C'; }
        else if ( grade >= 60 ) { letterGrade = 'D'; }
        else                    { letterGrade = 'F'; }
        
        cout << "Grade: " << letterGrade << endl;
        

        With this example, I'm first checking if the grade is 90 or above. If it is, then I know the letter grade is 'A'.

        However, if it's false, it will go on and check the next else if statement. At this point, I know that since grade > 90= was FALSE, that means grade < 90. Since the next statement checks if grade > 80=, if this one is true I know that grade < 90 AND grade > 80=.

  3. Switch statements

    1. Switch statements

      Switch statements are a special type of branching mechanism that only checks if the value of a variable is equal to one of several values. Switch statements can be useful when implementing a menu in a program, or something else where you only have a few, finite, discrete options.

      In C++, switch statements only work with primitive data types, like integers and chars - not strings.

      switch ( VARIABLE )
      {
       case VALUE1:
        // Do thing
         break;
      
       case VALUE2:
        // Do thing
         break;
      
       default:
        // Default code
      }
      

      With a switch statement, each case is one equivalence expression. The default case is executed if none of the previous cases are.

      case VALUE1:
      
      // is equivalent to...
      
      if ( VARIABLE == VALUE1 ) {
      
      case VALUE2:
      
      // is equivalent to...
      
      if ( VARIABLE == VALUE2 ) {
      
      default:
      
      // is equivalent to...
      
      else {
      

      The default case is not required, just like how the else clause is not required in an if statement.


      The break; statement

      The end of each case should have a break; statement at the end. If the break is not there, then it will continue executing each subsequent case's code until it does hit a break.

      This behavior is "flow-through", and it can be used as a feature if it matches the logic you want to write.

      Example: Perhaps you are implementing a calculator, and want to get an option from the user: (A)dd, (S)ubtract, (M)ultiply, or (D)ivide. You could store their choice in a char variable called operation and then use the switch statement to decide what kind of computation to do:

      switch ( operation )
      {
       case 'A': // if ( opreation == 'A' )
        result = num1 + num2;
        break;
      
       case 'S': // else if ( operation == 'S' )
        result = num1 - num2;
        break;
      
       case 'M': // else if ( operation == 'M' )
        result = num1 * num2;
        break;
      
       case 'D': // else if ( operation == 'D' )
        result = num1 / num2;
        break;
      }
      
      cout << "Result: " << result << endl;
      

      Note: If you're declaring a variable within a case statement, you need to enclose your case with curly braces { }, otherwise you'll get compiler errors:

      switch ( operation )
      {
       case 'A':
         {
           float result = num1 + num2;
           cout << "Result: " << result << endl;
         }
        break;
      }
      

5.10.2. Programming Lab

banner-lab.png

\newpage

5.11. Unit 10: C++: Searching and sorting

5.11.1. Reading

banner-reading.png

  1. Searching

    We're going to keep this section short for now because we're mostly going to be focusing on sorting algorithms.

    When we're searching for items in an unsorted linear structure
    there's not much we can do to speed up the process. We can basically either start at the beginning and move forward, or start and the end and move backward, checking each item in the structure for what you're looking for.
    template <typename T>
    int LinearSearch( const vector<T>& arr, T findme )
    {
        int size = arr.size();
        for ( int i = 0; i < size; i++ )
        {
            if ( arr[i] == findme )
            {
                return i;
            }
        }
    
        return -1; // not found
    }
    

    We begin at the first index 0 and iterate until we hit the last index. Within the loop, if the element at index i matches what we're looking for, we return this index.

    If the loop completes and we haven't returned an index yet that means we've searched the entire structure and have not found the item. In this case, it is not in the structure and we can throw an exception to be dealt with elseware or return something like -1 to symbolize "no valid index".

    This search algorithm's growth rate is \(O(n)\) – the more items in the structure, the time linearly increases to search through it. Not much we can do about that, which is why we have different types of data structures that sort data as it is inserted - more on those later on.

    OK, but what if the structure is sorted?

    We're going to be learning about sorting algorithms, so what if we happen to have a structure that is sorted? How can we more intelligently look for some value in the structure?

    Let's say we have a simple array like this:

    Value: "aardvark" "bat" "cat" "dog" "elephant" "fox"
    Index: 0 1 2 3 4 5

    And we want to see if "dog" is in the array. We could investigate what the first item is (Hm, starts with an "a") and the last item ("f"), and realize that "d" is about halfish way between both values. Maybe we should start in the middle and move left or right?

    • Index 0 is "aardvark". Index 5 is "fox". Middle value \(\frac{0+5}{2}\) is 2.5 (or 2, for integer division). What is at position 2? – "cat". If arr[2] \(<\) findme, move left (investigate arr[1] next) Or if arr[2] \(>\) findme, move right (investigate arr[3] next).
    • "d" is greater than "c" so we'll move right… Index 3 gives us "dog" - we've found the item! Return 3.

    In this case, we basically have two iterations of a loop to find "dog" and return its index. If we were searching linearly, we would have to go from 0 to 1 to 2 to 3, so four iterations.

    This still isn't the most efficient way to search this array - just starting at the midpoint and moving left or moving right each time. However, we can build a better search that imitates that first step: Checking the mid-way point each time.

    Here is the Binary Search.

    template <typename T>
    int BinarySearch( vector<T> arr, T findme )
    {
        int size = arr.size();
        int left = 0;
        int right = size - 1;
    
        while ( left <= right )
        {
            int mid = ( left + right ) / 2;
    
            if ( arr[mid] < findme )
            {
                left = mid + 1;
            }
            else if ( arr[mid] > findme )
            {
                right = mid - 1;
            }
            else if ( arr[mid] == findme )
            {
                return mid;
            }
        }
    
        return -1; // not found
    }
    

    With the binary search we look at the left-most index, right-most index, and mid-point. Each iteration of the loop, we look at our search value findme – is its value greater than the middle or less than the middle?

    Example

    Let's say we have this array, and we are searching for 'p'.

    Value: 'a' 'c' 'e' 'h' 'i' 'k' 'm' 'o' 'p' 'r'
    Index: 0 1 2 3 4 5 6 7 8 9

    Step 1: left is at 0, right is at 9, mid is \(\frac{0+9}{2}\) = 4 (integer division).

    Value: 'a' 'c' 'e' 'h' 'i' 'k' 'm' 'o' 'p' 'r'
    Index: 0 1 2 3 4 5 6 7 8 9
      left       mid         right

    Next we compare i to 'p'. 'p' comes later in the alphabet (so p > i), so next we're going to change the left value to look at mid+1 and keep right as it is.


    Step 2: left is at 5, right is at 9, mid is \(\frac{5+9}{2} = \frac{14}{2}\) = 7.

    Value: 'a' 'c' 'e' 'h' 'i' 'k' 'm' 'o' 'p' 'r'
    Index: 0 1 2 3 4 5 6 7 8 9
                left   mid   right

    Now we compare the item at arr[mid] 'o' to what we're searching for ('p'). p > o so we adjust our left point again to our current midpoint.


    Step 3: left is at 7, right is at 9, mid is \(\frac{7+9}{2} = \frac{16}{2}\) = 8.

    Value: 'a' 'c' 'e' 'h' 'i' 'k' 'm' 'o' 'p' 'r'
    Index: 0 1 2 3 4 5 6 7 8 9
                    left mid right

    Now we compare the item at arr[mid] ('p') to what we're searching for ('p'). The values match! So the result is mid as the index where we found our item.

    Each step through the process we cut out half the search area by investigating mid and deciding to ignore everything either before it (like our example) or after it. We do this every iteration, cutting out half the search region each time, effectively giving us an efficiency of \(O(log(n))\) - the inverse of an exponential increase.


  2. Sorting

    I'll update the text here later for next semester but I never liked sorting algorithms. I always found the approach to studying them really tedious in uni. I'm not going to make you have to figure out these algorithms yourself - the algorithms are online.

    I'm just going to give you the code and we can visually step through how they work. It's possible you'll be asked to implement some sorting algorithms in a job interview if the company is really annoying, but for the most part you're going to be using sorting algorithms already implemented in your day-to-day life rather than implementing these yourself from scratch each time.

    You'll find animations and stuff on the class webpage that hopefully illustrate it better than we could in a typewritten format.

    Sorting algorithm efficiency (From https://www.bigocheatsheet.com/)

    Algorithm Best time Average time Worst time
    Bubble Sort \(\Omega(n)\) \(\Theta(n^{2})\) \(O(n^{2})\)
    Insertion Sort \(\Omega(n)\) \(\Theta(n^{2})\) \(O(n^{2})\)
    Selection Sort \(\Omega(n^{2})\) \(\Theta(n^{2})\) \(O(n^{2})\)
    Merge Sort \(\Omega(n log(n))\) \(\Theta(n log(n))\) \(O(n log(n))\)
    Quick Sort \(\Omega(n log(n))\) \(\Theta(n log(n))\) \(O(n^{2})\)

    1. Bubble Sort
      template <typename T>
      void BubbleSort( vector<T>& arr )
      {
          for ( int i = 0; i < arr.size() - 1; i++ )
          {
              for ( int j = 0; j < arr.size() - i - 1; j++ )
              {
                  if ( arr[j] > arr[j+1] )
                  {
                      swap( arr[j], arr[j+1] );
                  }
              }
          }
      }
      

    2. Insertion Sort
      template <typename T>
      void InsertionSort( vector<T>& arr )
      {
          size_t arraySize = arr.size();
          size_t i = 1;
      
          while ( i < arraySize )
          {
              int j = i;
              while ( j > 0 && arr[j-1] > arr[j] )
              {
                  swap( arr[j], arr[j-1] );
                  j = j - 1;
              }
      
              i = i + 1;
          }
      }
      

    3. Selection Sort
      template <typename T>
      void SelectionSort( vector<T>& arr )
      {
          int arraySize = arr.size();
      
          for ( size_t i = 0; i < arraySize - 1; i++ )
          {
              int minIndex = i;
      
              for ( size_t j = i + 1; j < arraySize; j++ )
              {
                  if ( arr[j] < arr[minIndex] )
                  {
                      minIndex = j;
                  }
              }
      
              if ( minIndex != i )
              {
                  swap( arr[i], arr[minIndex] );
              }
          }
      }
      

    4. Merge Sort
      // Declarations
      template <typename T>
      void MergeSort( vector<T>& arr );
      
      template <typename T>
      void MergeSort( vector<T>& arr, int left, int right );
      
      template <typename T>
      void Merge( vector<T>& arr, int left, int mid, int right );
      
      // Definitions
      template <typename T>
      void MergeSort( vector<T>& arr )
      {
          MergeSort( arr, 0, arr.size() - 1 );
      }
      
      template <typename T>
      void MergeSort( vector<T>& arr, int left, int right )
      {
          if ( left < right )
          {
              int mid = ( left + right ) / 2;
      
              MergeSort( arr, left, mid );
              MergeSort( arr, mid+1, right );
              Merge( arr, left, mid, right );
          }
      }
      
      template <typename T>
      void Merge( vector<T>& arr, int left, int mid, int right )
      {
          const int n1 = mid - left + 1;
          const int n2 = right - mid;
      
          vector<T> leftVec;
          vector<T> rightVec;
      
          for ( int i = 0; i < n1; i++ )
          {
              leftVec.push_back( arr[left + i] );
          }
      
          for ( int j = 0; j < n2; j++ )
          {
              rightVec.push_back( arr[mid + 1 + j] );
          }
      
          int i = 0;
          int j = 0;
          int k = left;
      
          while ( i < n1 && j < n2 )
          {
              if ( leftVec[i] <= rightVec[j] )
              {
                  arr[k] = leftVec[i];
                  i++;
              }
              else
              {
                  arr[k] = rightVec[j];
                  j++;
              }
              k++;
          }
      
          while ( i < n1 )
          {
              arr[k] = leftVec[i];
              i++;
              k++;
          }
      
          while ( j < n2 )
          {
              arr[k] = rightVec[j];
              j++;
              k++;
          }
      }
      

    5. Quick Sort
      // Declarations
      template <typename T>
      void QuickSort( vector<T>& arr );
      
      template <typename T>
      void QuickSort( vector<T>& arr, int low, int high );
      
      template <typename T>
      int Partition( vector<T>& arr, int low, int high );
      
      // Definitions
      template <typename T>
      void QuickSort( vector<T>& arr )
      {
          QuickSort( arr, 0, arr.size() - 1 );
      }
      
      template <typename T>
      void QuickSort( vector<T>& arr, int low, int high )
      {
          if ( low < high )
          {
              int partIndex = Partition( arr, low, high );
              QuickSort( arr, low, partIndex - 1 );
              QuickSort( arr, partIndex + 1, high );
          }
      }
      
      template <typename T>
      int Partition( vector<T>& arr, int low, int high )
      {
          T pivotValue = arr[high];
          int i = low - 1;
      
          for ( int j = low; j <= high - 1; j++ )
          {
              if ( arr[j] <= pivotValue )
              {
                  i++;
                  swap( arr[i], arr[j] );
              }
          }
      
          swap( arr[i+1], arr[high] );
          return i + 1;
      }
      

5.11.2. Programming Lab

banner-lab.png

\newpage

5.12. Unit 11: Tech Literacy: Current trends in tech

5.12.1. Reading

banner-reading.png

5.12.2. Tech literacy

\newpage

5.13. Unit 12: Tech Literacy: Object Oriented Programming

5.13.1. Reading

banner-reading.png

5.13.2. Tech literacy

5.14. Unit 13: C++: Classes and Inheritance

5.14.1. Reading

banner-reading.png

  1. Classes

    reading_u11_Classes_titleimage.png

    1. Introduction to Object Oriented Programming
      1. Programming paradigms

        Programming paradigms (pronounced "pair-uh-dimes") are ways we can classify different programming languages based on features they have available or the style programs are written. Different paradigms have popped up over the life of computers as programming languages grow and evolve.

        Machine code

        At the beginning, computers were programmed with machine code, where you work directly with instructions supported by the hardware - for example, add, sub, storing data in registers, and other relatively simple commands.

        Procedural Languages

        Eventually, those commands were abstracted into higher-level languages, where one command in, say, C, could "translate" to several machine-code instructions. Languages like C, Fortran, Algol, BASIC, and C are known as Procedural Languages, where these programs would describe a procedure to follow and instructions are executed one-at-a-time in a specific order (top-to-bottom, or calling a function and returning).

        Object Oriented Programming

        Languages like C supported our basic control flow and using functions, but did not include classes - a way to make more sophisticated data types. A class is a structure that can store its own member variables and member functions. A variable whose data type is from some defined class is known as an object.

        There are other programming paradigms, but we are going to focus on Object Oriented Programming (OOP) now since it's a large part of using C++ and other languages like Java, C#, and Python.


      2. Design ideals

        In programming, an object is some sort of structure that stores its own data (variables) and functionality (functions). We try to design our programs as a collection of objects that interact with each other to get some job done.

        Designing programs in an OOP style helps us pursue certain design goals:

        • Abstraction: Hiding complexity in the design, creating an "interface" for the user, generalizing functionality to a more "digestible" form. Think of a button on any device: If you open up the device, there's a lot actually going on, but we just see the simple button and don't have to worry about the rest.
          • Certain functions are made public that other programmers can use to interface with the object.
          • The other programmers don't need to worry about the inner-workings of the object in order to use it.
          • The developer of the class can modify how the internals work without breaking the public interface.
          • Helps protect the data within the class from being accessed or modified by things it shouldn't.
        • Encapsulation: Also goes along with creating an "interface", though in this regard we are encapsulating related pieces together. We can store data (variables) with the functions that operate on that data (functions) all within a class object.
        • Loose coupling: Ideally, different objects in a program shouldn't have their functionality tied to other objects too closely; we want to reduce inter-dependence between objects. When objects are more independent from each other, they are loosely coupled.
        • High cohesion: When we design our objects, we shouldn't just throw everything and the kitchen sink into one object. To design an object with high cohesion means that everything inside the object belongs in that object. Reduce the clutter.

      3. Example: Moving to an OOP design

        Let's think about a simple program we can make with just functions and arrays for contrast: A library of the movies a user owns.

        For this program, we could start with an array of strings to store movie titles, but we'd have to create new arrays for each additional field to keep track of - year, genre, rating, etc.

        string movieTitles[MAX_MOVIES];
        string movieRatings[MAX_MOVIES];
        string movieGenre[MAX_MOVIES];
        int movieYearReleased[MAX_MOVIES];
        

        In addition to our arrays, we need functions to deal with different operations we would want to do on our movie collection…

        void AddMovie(
        string movieTitles[], string movieRatings[],
        string movieGenre[], int movieYears[],
        int& savedMovies, const int MAX_MOVIES );
        void UpdateMovie(
        string movieTitles[], string movieRatings[],
        string movieGenre[], int movieYears[],
        int& savedMovies );
        
        Cons of this style:
        • We have to add logic in our program to make sure that item \(i\) in movieTitles and item \(i\) in =movieRatings will refer to the same movie. There's nothing in C++ that will directly link these things so we have to add the logic ourselves.
        • Have to keep track of four different arrays and have to pass four different arrays between functions.

        Instead, we can take this general structure and turn it into an object, like this:

        Movie  
        - title : string
        - rating : string
        - genre : string
        - year : int
        + Setup( ... ) : void
        + Update( ... ) : void
        + Display() : void

        The Movie object would store information about the movie and a set of functionality we would do on a movie. During the "Add Movie" feature of the program, we would be calling the Setup(...) function of the Movie object to get its information all set up.

        In addition to our Movie object, we could also build an object that is the library itself - what data and functionality does our library of movies have?

        MovieLibrary  
        - movieList : Movie[]
        - totalMovies : int
        - MAX_MOVIES : const int
        + AddMovie() : void
        + UpdateMovie() : void
        + ClearMovie() : void
        + DisplayAllMovies() : void
        + SaveList( path: string ) : void
        + LoadList( path: string ) : void

        Our movie library would contain one array - an array of Movie objects - instead of the four separate arrays for each of the movie fields. The library itself would have the Add, Update, Clear, etc. functions and know how to handle that functionality.

        Finally, in our main() function we would declare a MovieLibrary variable for our single library - or, we could make an array of MovieLibrary objects if the program accomodated multiple users!

        After initialization, we would have our main menu as usual…

        1. Add movie
        2. Update movie
        (etc)
        

        and when a choice is made, we call the appropriate function via our MovieLibrary object.

        Creating the MovieLibrary object:

        int main()
        {
        // Creating a MovieLibrary object
        MovieLibrary movieLibrary;
        

        Calling the AddMovie function of MovieLibrary:

        if ( choice == 1 )
        {
            // Calling the AddMovie function
            movieLibrary.AddMovie();
        }
        

        When defining the AddMovie() function, it could call the Setup() function for the next Movie object in the array…

        #+BEGIN_SRC cpp :class cpp
        void MovieLibrary::AddMovie()
        {
        movieList[ totalMovies ].Setup();
        totalMovies++;
        }
        

        And the Movie object's Setup() function could handle dealing with the inputs and outputs…

        void Movie::Setup() {
        cout << "Enter a title: ":
        getline( cin, title );
        
        cout << "Enter a rating: ";
        getline( cin, rating );
        
        cout << "Enter a genre: ";
        getline( cin, genre );
        
        cout << "Enter a year: ";
        cin >> year;
        }
        

        Here's a diagram of the main program and objects:

        reading_u11_Classes_LibraryDiagram.png


      4. Additional OOP examples

        Here are a few more examples of using object oriented design in different types of programs:

        Video game

        reading_u11_Classes_Game.png

        A video game usually has characters that can move around, a lot of 2D game levels are built out of a grid of tiles.

        Anything that gets displayed to the screen will need \((x,y)\) coordinates as well as dimensions like width and height. C++ doesn't have a built-in image object, but there are graphical libraries that provide graphics functionality.

        Player  
        - x : int
        - y : int
        - width : int
        - height : int
        - image : Texture
        + Setup() : void
        + Move(...) : void
        + BeginJump(...) : void
        + BeginAttack(...) : void
        + Draw(...) : void
        Tile  
        - x : int
        - y : int
        - width : int
        - height : int
        - image : Texture
        + Setup() : void
        + Draw(...) : void
        Level  
        - tiles : Tile[][]
        - worldWidth : int
        - worldHeight : int
        + LoadLevel() : void
        + DrawLevel() : void

        College

        reading_u11_Classes_Campus.png

        A college could be separated into multiple different objects, where a College might have different Campuses (such as KU-Lawrence, KU-Edwards or the different MCCKC campuses), and each campus has an array of different Departments (CSIS, MATH, ENG, etc.), each department has an array of Teachers and an array of Courses. A course would generally have one Teacher and an array of Students.

        As far as functionality goes, this diagram has only some basic functions, like SetTeacher for a course, or =AddStudent=h. The idea is that, anything related to a course would go in the Course object, with each object handling its own little domain.


    2. Structs
      1. Structs vs. Classes

        Structs in C++ have all the same functionality of a Class, but are generally used design-wise to group a few variables together, maybe some functions, into a simple structure. A class, on the other hand, is usually used for much bigger and more complex objects.

        In C++, the only difference between Structs and Classes are default accessibility - if you don't specify the accessibility of your variables/functions within a struct, they are public by default. This means that anything in the program can access those variables/functions. For Classes, everything is private by default - only that Class itself can use the variables/functions.


      2. Declaring a struct

        Struct declarations go in header (.h) files. Usually the file name should reflect the name of the struct itself, and the file guard labels should also match.

        #ifndef _STRUCTNAME
        #define _STRUCTNAME
        
        struct STRUCTNAME
        {
          int var;
          void Func();
        };
        
        #endif
        

        Design-wise, structs should only contain a small amount of data. While structs can contain functions, it is generally better to create a class if you find yourself needing functions.

        An example of a small struct would be grouping \(x\) and \(y\) coordinates together in a Coordinate Pair…

        struct CoordinatePair
        {
            float x, y;
        };
        

        Sometimes we need to group some basic variables together. Structs are great for this.

        struct Rectangle
        {
            float left, right, top, bottom;
        };
        

      3. Declaring object variables

        Once a struct has been declared in a program, you can then create a variable with that data type. To access the internal variables of the struct, you use the variable's name followed by the dot operator . and then the name of the member variable.

        // Declare two variables
        CoordinatePair point1, point2;
        
        cout << "Enter the x y coordinates for the first point: ";
        cin >> point1.x >> point1.y;
        
        cout << "Enter the x y coordinates for the second point: ";
        cin >> point2.x >> point2.y;
        
        float slope = ( point2.y - point1.y ) / ( point2.x - point1.x );
        cout << "The slope is: " << slope << endl;
        

        We will have more examples during the section on Classes, since that's mostly what we will be using. Again, structs are useful for combining a small amount of member variables together under one name, usually used for structures for math (coordinates, rectangles, etc.) but more sophisticated objects ought to be created with a class.


    3. Classes

      Traditionally, a struct is used to create small objects that join a few variables together. Classes are much more heavily used in C++ and is the back-bone of Object Oriented Programming. There is a lot we can do with classes, but for now we are just going to look at the basics.

      A class declaration looks just like a struct declaration except that we use the keyword class. Take note that with a struct and class declaration, we must end the closing curly brace with a semi-colon.

      class Player
      {
          public:
          void SetPosition( int newX, int newY );
          void Move();
      
          private:
          int x, y;
      };
      
      1. Accessibility

        We can define our member variables and functions with three different levels of accessibility, dictating where these members can be accessed throughout the program:

        public:
        Any part of the program can access these members. This is usually used for the member functions of a class.
        private:
        These members can only be accessed by the class itself, from within its functions.
        protected:
        Similar to private except that classes that inherit from the class we're defining will also have access to protected members. More on this when we cover inheritance.
      2. Header and Source files

        When we are creating a class, we generally will put the class declaration within its own header file. Header files end with .h or .hpp - I tend to use .hpp since we're using C++ and I like to explicitly state this is a "C++ header"; the .h extension was also used in C. However, the C++ Core Guidelines document says to

        NL.27: Use a .cpp suffix for code files and .h for interface files

        Reason It's a longstanding convention. But consistency is more important, so if your project uses something else, follow that.

        (From https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#reason-451)

        Class declaration goes in Rectangle.h (or Rectangle.hpp):

        #ifndef _RECTANGLE_H
        #define _RECTANGLE_H
        
        class Rectangle
        {
            public:
            void SetPosition( int newX, int newY );
            void SetDimensions( int newWidth, int newHeight );
            private:
            int x, int y, int width, int height;
        };
        
        #endif
        

        Context: What is #ifndef?

        In C++, when we #include "Rectangle.h" in a different source file, the compiler essentially copy-pastes the code from the included file into the includer file.

        Because of this, if multiple files are #include "Rectangle.h"-ing (or any other header), the same code in that header gets copied multiple times, making the compiler think you've declared the same class over and over.

        #ifndef, #define, and #endif are preprocessor commands used by the compiler. We are essentially saying

        "if-not-defined _RECTANGLE_H, define _RECTANGLE_H, … … end-if.",

        preventing the compiler from copying the same file twice.

        Class function definitions go in Rectangle.cpp:

        #include "Rectangle.h"
        
        void Rectangle::SetPosition( int newX, int newY )
        {
            x = newX;
            y = newY;
        }
        
        void Rectangle::SetDimensions( int newWidth,
                                    int newHeight )
        {
            width = newWidth;
            height = newHeight;
        }
        

        In our source file (.cpp), we need to make sure to include the header that goes with our class so it knows about the class declaration. Then, we can define the member functions here.

        Note that when we're defining the functions outside of the class declaration, we must prefix the function name with the class name, followed by the scope resolution operator ::

        void Rectangle::SetPosition( int newX, int newY )
        

        This is the standard way C++ files are organized - for each class we create, we create a header and a source file for it.

        Defining member functions inside the class declaration

        It is completely possible to define our member functions inside the class declaration, getting rid of the need for the .cpp file. However, this does end up being treated differently by the compiler - writing our class this way makes the functions inline… Basically, instead of having a separate function that the compiler will mark as "call this", it will copy the contents of the inlined function to the function call, basically replacing the call with the contents of the function.

        I haven't written much about how the compiler works since that's a more specialized topic and we don't need to worry about it at this stage of learning C++. This is just here for your own info.

        The entire class in Rectangle.h:

        #ifndef _RECTANGLE_H
        #define _RECTANGLE_H
        
        class Rectangle
        {
            public:
            void SetPosition( int newX, int newY )
            {
                x = newX;
                y = newY;
            }
        
            void SetDimensions( int newWidth, int newHeight )
            {
                width = newWidth;
                height = newHeight;
            }
        
            private:
                int x, int y, int width, int height;
        };
        
        #endif
        

        This is also closer to how Java and C# files look, defining all their methods within the class declaration. It also does simplify having to go back and edit functions, not having to keep track of two different places where we have the function declaration and the function definition.

        Should you define functions in the .hpp or the .cpp?

        In general, for my courses, you can choose either approach. Starter code I provide may have the .hpp and .cpp files for classes, but when writing your own class you can throw it all in the .hpp file if you'd like.

        The main thing is that it's important to be aware of the standard way so that when you're working with other people you understand how things are structured.

        Function vs. Method

        A method is a word that means "member function". In Java and C#, the term method is used instead of function, since you physically cannot have functions defined outside of a class in those languages.

        I tend to stick with the term "member function", but if I write "method", it means that, whereas a "function" would be a standalone function elseware in the program.


      3. Getters and Setters

        In Object Oriented Programming, we generally want to hide the inner-workings of a class from the outside world (other functions and other classes). If everything were exposed, then other parts of the program could make changes to our class and it could be difficult to track down all those modifying locations (this, in particular, is a nightmare at a job with a large codebase).

        We generally write all our member variables as private - accessible only to the class' member functions themseves - and use public member functions to interface with those variables as needed.

        For example, in our Rectangle class, we might have a function to set up the entire Rectangle all at once…

        void Rectangle::Setup( int newX, int newY, int newWidth, int newHeight )
        {
            x = newX;
            y = newY;
            width = newWidth;
            height = newHeight;
        }
        

        … or just a couple things at a time …

        void Rectangle::SetPosition( int newX, int newY )
        {
            x = newX;
            y = newY;
        }
        
        Setters:
        Or, we might want to just set one member variable's value.

        In this case, we write a member function called a setter (aka mutator) that is responsible for setting a member variable's value:

        void Rectangle::SetX( int newX )
        {
            x = newX;
        }
        

        The good thing about having setters instead of directly updating the x variable is that we can add error checks in our setter. Say, perhaps, that we don't want x to be negative, so we validate the input before changing it…

        void Rectangle::SetX( int newX )
        {
            if ( newX >= 0 )
            {
                x = newX;
            }
        }
        

        If somewhere else in the program tries to set a negative value for the x variable, it will just ignore that command. (We could also throw an exception or display an error message or set a default value - it's up to your design.)

        Getters:
        Likewise, sometimes we want to access

        those member variables to see what values they store. In this case, we write Getter member functions that are responsible for returning a copy of the data (or, in some cases, a reference to it - but that's a design decision).

        int Rectangle::GetX()
        {
            return x;
        }
        

        Getters are also handy for formatting output prior to returning it, or doing some other operation before returning something. Let's say we have a member function for a Student class, and a GetName function is going to combine their names and return it together:

        int Student::GetFullName()
        {
            return lastName + ", " + firstName;
        }
        

        To summarize…

        • Setters: Sets the value of a member variable. Generally, return type is void and there is one paramete for the new value. void SetThing( int newValue );
        • Getters: Returns the value of a member variable. Generally, return type matches that variable, and there are no parameters. =int GetThing(); =

      4. Constructors and Destructors

        Constructors and Destructors are special types of member functions in a class.

        • Constructor:
          • Runs automatically as soon as a new object is declared.
          • Can declare more than one constructor.
          • No return type
          • Constructor name must match name of the class.
        • Destructor:
          • Runs automatically as soon as a new object is destroyed.
          • Can only have one destructor.
          • No return type
          • Destructor name \underline=must= match name of the class, prefixed with a tilde \~.
        Example: Text file wrapper

        Let's say we're writing a class that works with a text file.

        When the object is created, the constructor will open the file and get it ready to write to. With various member functions we can write to that text file as the program is running. Then, when the program ends and the object is destroyed, it will automatically close the text file for us.

        Class declaration:

        class Logger
        {
            public:
            // constructors
            Logger( string filename );
            Logger();
        
            // destructor
            ~Logger();
        
            // other method
            void Write( string text );
        
            private:
            ofstream m_output;
        };
        

        We have two constructors: one where we pass in a filename for a file to open, and one where we don't. In the second case, we can use a default file name.

        Context: Why "m_" with the variable?

        In some places, it is standard to prefix private member variables with an underscore (_output) or (m_output). I tend to use the latter when writing private member variables of a class. The "m" stands for "member".

        The constructor definitions could look like this:

        Logger::Logger( string filename )
        {
            m_output.open( filename );
        }
        
        Logger::Logger()
        {
            m_output.open( "log.txt" );
        }
        

        The Write function could be used to write information to that text file, and could be implemented like this:

        void Logger::Write( string text )
        {
            m_output << text << endl;
        }
        

        And then the destructor would be used to close up the file at the end:

        Logger::~Logger()
        {
            m_output.close();
        }
        

        Now, we don't have to manually deal with file operations since this class wraps that functionality and deals with it for us.

        To use the program, we just declare the object variable:

        #include "Logger.hpp"
        
        int main()
        {
            // At this point,
            // a constructor is called automatically
            Logger log( "logfile.txt" );
        
            // Writing to the text file
            log.Write( "Hello!" );
            log.Write( "How are you?" );
        
            // Program ends here. The destructor
            // is called automatically when the log variable
            // goes out of scope and is destroyed.
            return 0;
        }
        

        It can often be handy to overload our constructors so that we can initialize our objects in several different ways.

        1. Default Constructors

          A default constructor is a constructor with no parameters in it. This will be called when a variable of this class type is declared with no constructor explicitly called.

          Usually, a default constructor would be used to initialize variables to default values, and if your class contains pointers, this constructor should initialize those pointers to point to nullptr.

          class MyClass
          {
          public:
          MyClass()       // Default constructor
          {
              m_value = 0;
          }
          
          private:
              int m_value;
          };
          

          When we create a new object of this type like this, the default constructor will be called:

          MyClass classVar;
          
        2. Parameterized Constructors

          Parameterized Constructors take in one or more parameters to help initialize the member variables of the object. We can have 0, one, or multiple parameterized constructors for our class.

          class MyClass
          {
              public:
              MyClass() {       // Default constructor
                  m_value = 0;
              }
          
              MyClass( int value ) {  // Parameterized constructor
                  m_value = value;
              }
          
              // etc
          };
          

          When we instantiate our object, we can pass in argument(s) in order to call the parameterized version of the constructor:

          MyClass classVar( 100 );
          

          If you declare a parameterized constructor but not a default constructor, then the C++ compiler will assume that you don't want an object to be declared with the default constructor. This means, you would only be able to declare the variable with an explicit call to the constructor and with arguments.

          If this isn't the desired design, make sure to include a default constructor, even if you just leave it blank.

        3. Copy Constructors

          A copy constructor takes in another object of the same type as its parameter and uses this to copy over members from the parameter to the new object.

          class MyClass
          {
              public:
              MyClass()       // Default constructor
              {
                  m_value = 0;
              }
          
              MyClass( int value )  // Parameterized constructor
              {
                  m_value = value;
              }
          
              MyClass( const MyClass& other ) // Copy constructor
              {
                  m_value = other.m_value;
              }
          
              private:
              int m_value;
          };
          

          In this case, we might already have an object of this type available, and when we are creating a new object, we want to make a copy of the old object:

          MyClass classVar( 100 );
          MyClass anotherOne( classVar );   // Copy
          
          Design:
          When a class has multiple member variables, it is up to us to decide which variables get copied over during this operation. There could be some design cases where all information is copied over except certain fields (maybe a unique customerID or a name).
          Default copy constructor:
          If you don't explicitly declare a copy constructor, the C++ compiler will provide one for the class behind-the-scenes. This implicit copy constructor will only do shallow copies.

          Ways to copy:

          • A Shallow Copy is where values of variables are copied over. This is generally fine for any sort of non-pointer-based variables. If the class contains a pointer that is pointing to some address, the shallow-copy of the pointer will point to the same address.
          • A Deep Copy is where values are copied over like with a shallow copy, but also will allocate new memory for a dynamic array (if the class has one) in order to copy over values of the element of the array to the new class copy.

          reading_u11_Classes_ShallowCopy.png

          Example of a shallow copy: With the implicit copy constructor, any pointers in the copied version will be pointing to the same address as in the original. If the class contains a dynamic array, both the copy and the original will end up pointing to the same address of the array in memory.

          reading_u11_Classes_DeepCopy.png

          Example of a deep copy: A new block of memory has been allocated for the int * numArr. The values from InstanceA's numArr would be copied to InstanceB's numArr via a for loop during construction.


      5. Example program: House Builder

        This program allows a user to enter information about multiple rooms in a house and at the end it will output a text file with all the room information.

        Example output:

        HOUSE BUILDER
        (A)dd new room or (Q)uit: a
        Enter room name: livingroom
        Enter width: 10
        Enter length: 20
        
        (A)dd new room or (Q)uit: a
        Enter room name: kitchen
        Enter width: 10
        Enter length: 15
        
        (A)dd new room or (Q)uit: a
        Enter room name: bathroom
        Enter width: 6
        Enter length: 10
        
        (A)dd new room or (Q)uit: q
        
        Outputted to house.txt
        

        In my design, I have two objects: A Room, which contains a room name, width, and length, and a House, which contains an array of rooms. In the main() function, we work directly with the House, and the house takes care of dealing with the Rooms.

        Room.h:
        #ifndef _ROOM_HPP
        #define _ROOM_HPP
        
        #include <string>
        using namespace std;
        
        class Room
        {
            public:
            void Setup();
        
            string GetName();
            int GetWidth();
            int GetLength();
            int GetArea();
        
            private:
            string name;
            int width;
            int length;
        };
        
        #endif
        

        We have getter functions for the name, width, and length of the room, as well as to get the area. We don't need to store the area because we can calculate it any time we need it.

        There is also a function Setup() that deals with the cins and couts to set up the room's information.

        Room.cpp:
        #include "Room.hpp"
        
        #include <iostream>
        using namespace std;
        
        void Room::Setup()
        {
            cout << "Enter room name: ";
            cin >> name;
        
            cout << "Enter width: ";
            cin >> width;
        
            cout << "Enter length: ";
            cin >> length;
        }
        
        string Room::GetName()
        {
            return name;
        }
        
        int Room::GetWidth()
        {
            return width;
        }
        
        int Room::GetLength()
        {
            return length;
        }
        
        int Room::GetArea()
        {
            return width * length;
        }
        
        House.h:
        #ifndef _HOUSE_HPP
        #define _HOUSE_HPP
        
        #include "Room.hpp"
        
        const int MAX_ROOMS = 10;
        
        class House
        {
            public:
            House();
            ~House();
        
            void AddRoom();
        
            private:
            Room rooms[MAX_ROOMS];
            int roomCount;
        };
        
        #endif
        

        The House class contains a constructor, which will be used to initialize data automatically. In particular, we want roomCount to be set to 0.

        The destructor will automatically open a text file, output all the rooms' information, and then close the text file when the House object is destroyed at the end of the program.

        House.cpp:
        #include "House.hpp"
        
        #include <iostream>
        #include <fstream>
        using namespace std;
        
        House::House()
        {
            roomCount = 0;
        }
        
        House::~House()
        {
            ofstream output( "house.txt" );
            for ( int i = 0; i < roomCount; i++ )
            {
                output << rooms[i].GetName() << "\t"
                        << rooms[i].GetWidth() << "x"
                        << rooms[i].GetLength() << "\t"
                        << "(" << rooms[i].GetArea() << " sqft)"
                        << endl;
            }
            output.close();
        
            cout << "Outputted to house.txt" << endl;
        }
        
        void House::AddRoom()
        {
            if ( roomCount == MAX_ROOMS )
            {
                cout << "House is full!" << endl
                     << "Cannot fit any more rooms!" << endl;
                return; // exit this function
            }
        
            rooms[ roomCount ].Setup();
            roomCount++;
        }
        
        main.cpp:
        #include <iostream>
        using namespace std;
        
        #include "House.hpp"
        
        int main()
        {
            House myHouse;
        
            cout << "HOUSE BUILDER" << endl;
            bool done = false;
            while ( !done )
            {
                cout << "(A)dd new room or (Q)uit: ";
                char choice;
                cin >> choice;
        
                if ( toupper(choice) == 'A' )
                {
                    myHouse.AddRoom();
                }
                else if ( toupper(choice) == 'Q' )
                {
                    done = true;
                }
                cout << endl;
            }
        
            return 0;
        }
        

        This program only deals with one house, but we could have an array of Houses, each with their own separate array of Rooms.


    4. Additional class concepts
      1. Const member methods

        When we declare a class' member function as const, we are saying that this function should not ever change any values of any member variables of this class. This can be handy for methods like a Display() where we just want to output member variables but should never change them.

        class Coordinates
        {
        public:
        int GetX() const; // Can't change m_x or m_y
        int GetY() const; // Can't change m_x or m_y
        
        void SetX( int val );
        void SetY( int val );
        
        private:
        int m_x, m_y;
        };
        

        The function definition will also need to have this const marked at the end of the function header as well.

        int Coordinates::GetX() const 
        {
        return m_x;
        }
        

      2. this

        Within our class methods, we can explicitly refer to the object we are currently working with as this. this is a pointer, so it is pointing to a memory address. Any member of the class can also be accessed via the this pointer:

        class MyClass
        {
        public:
          void A()
          {
            cout << "Hello!" << endl;
          }
        
          void B()
          {
            this->A();
            cout << this->var << endl;
          }
        
          void C()
          {
            A();
            cout << var << endl;
          }
        
        private:
          int var;
        };
        

        In this example, methods B() and C() do the same thing, but B() explicitly uses this.


    5. Review questions:
      1. True or false: A class can have member variables and functions (methods).
      2. Class declarations go in what kind of file?
      3. Class function (method) definitions go in what kind of file?
      4. A class' public members can be accessed by…
      5. A class' protected members can be accessed by…
      6. A class' private members can be accessed by…
      7. When defining a function that is a member of a class, the function name needs to be prefixed with…
      8. What does a getter (accessor) function do?
      9. What does a setter (mutator) function do?
      10. When does a constructor function run?
      11. When does a destructor function run?
      12. The constructor and destructor name must match what?
  2. Inheritance

    Inheritance is where one class inherits some or all member variables and functions from some parent class. Certain "traits" are passed on, and the child class can have additional member variables and functions defined, making it a more specialized version of the parent class.

    1. Design ideas
      1. Reusing functionality

        Let's say we're designing an operating system that will store files. We can think about what all files have in common, and we can figure out what is different between different types of files. Any commonality could go in a base class (aka parent class).

        So, a generic File class might have contain variables and functions like:

        File  
        - m_filename : string
        - m_extension : string
        - m_fileSize : size_t
        - m_creationDate : DateTime
        + CreateFile(...) : void
        + RenameFile(...) : void
        + GetSize() : size_t
        + GetPath() : string

        Then we could have specialized file classes that inherit from the original File, such as TextFile, ImageFile, SoundFile, and so on. These would inherit all the common attributes of its parent (File), but each would have additional variables and methods that are suited specifically to its own specialization.

        • TextFile: m_textContent, Print()
        • ImageFile: m_pixels[][], Draw(), EditPixel( x, y )
        • SoundFile: m_audioSample, m_length, Play(), Pause(), Stop()

        reading_u12_Inheritance_FileTypes.png


      2. The iostream and fstream

        reading_u12_Inheritance_iosfam.png

        Part of the ios family. You can see the full library's family tree at http://www.cplusplus.com/reference/ios/

        One family we've already been using are our console input/output streams, cin and cout, and our file input/output streams, ifstream and ofstream. Working with each of these works largely the same way.

        When we overload the << and >> stream operators, we use a base type of istream and ostream so that our class can handle cin / cout AND ifstream / ofstream, as well as any other streams in that family tree.


      3. Inheritance (Is-A) vs. Composition (Has-A)

        Another way we think about inheritance is that one class "is-a" type of other class.

        Car is-a vehicle:

        class Car : public Vehicle
        {
          // etc.
        };
        

        Whereas Composition, where one class contains another class as a member variable object, is known as a "has-a" relationship.

        Car has-an engine:

        class Car
        {
        private:
          Engine engine;
        };
        

        When is composition more appropriate than inheritance? This is a design question and it can really depend on how the designer feels about each one.


      4. Example: Game objects

        For example, when writing a game, I find inheritance handy for creating game objects. A BaseObject can contain everything that's in common between all objects (characters, items, tiles, etc.), such as:

        reading_u12_Inheritance_apple.png

        Any items that don't animate, don't move, and just sit there in the level could be instantiated as a simple BaseObject and it would be fine.

        BaseObject  
        # m_position : Coordinate
        # m_sprite : Sprite
        # m_name : string
        + Setup(...)  
        + SetTexture(...)  
        + Update(...)  
        + SetPosition(...)  
        + Draw(...)  

        Then, let's say we want to build a 2D game level and each level is made up of a 2D array of tiles. Tiles will be very similar to objects, but maybe we want more information stored in a tile. We could then inherit from the BaseObject…

        reading_u12_Inheritance_brick.png

        The Tile class would have all the public and protected members from its parent, plus any new member variables and methods we declare within this class.

        Tile Inherits from BaseObject
        - m_isSolid : bool
        - m_doesDamage : bool

        For the game characters, there would be two different types usually: characters that the players control and characters that the computer controls. Character could be its own base-class as well, implementing anything a character can do, with a Player and NPC (non-player-character) classes inheriting from Character.

        Character Inherits from BaseObject
        # m_speed : int
        # m_direction : Direction
        # m_animFrame : float
        # m_maxFrames : float
        + Move(...)  
        + Animate(...)  

        reading_u12_Inheritance_player.png

        Player Inherits from Character
        - m_score : int
        - m_experience : int
        - m_level : int
        + HandleKeyboard(...)  
        + LevelUp(...)  

        The Player class would be a specialized type of Character that can be controled via the keyboard (or some other input device), as well as have information that a non-player-character generally has, such as a score or a level.

        reading_u12_Inheritance_npc.png

        NPC Inherits from Character
        - m_difficulty : int
        - m_isFriendly : bool
        + SetGoal(...)  
        + DecideNextAction(...)  

        Likewise, the NPC class is a specialization of Character as well, but with special functionality and attributes of a character in the game controlled by the computer itself. This could include some form of AI to help the NPC decide how to behave.

        Game object family:

        reading_u12_Inheritance_objectree.png

        With this family of game objects, we could also write functions that work on all types of game objects, such as checking if there's a collision between items, because they all have a common parent.

        reading_u12_Inheritance_screenshot.png


    2. Implementing inheritance

      In C++ a class can inherit from one or more other classes. Note that Java and C# do not support multiple inheritance directly, if you end up switching to those languages. Design-wise, however, it can be messy to inherit from more than one parent and as an alternative, you might find a composition (has-a) approach a better design.

      1. Inheriting from one parent

        To inherit from one other class in C++, all you need to do is add ": public OTHERCLASS" after the "class CLASSNAME" at the beginning of your class declaration. With a public inheritance (the most common kind), the child class will inherit all public and protected members of the parent class.

        // File is the parent
        class File
        {
        protected:
          string name;
          string extension;
          size_t filesize;
        };
        
        // TextDocument is the child
        class TextDocument : public File
        {
        protected:
          string textContents;
          /* Also inherits these members from File:
             string name;
             string extension;
             size_t filesize;
          */
        };
        

        Context: The Parent Class is often known as the superclass and the Child Class is often known as the subclass, particularly from the Java perspective.


      2. Inheriting from multiple parents

        You can also have a class inherit from multiple parents, bringing in public/protected members from all parent classes, but again this can muddle your program's design somewhat and is generally pretty uncommon.

        class AnimationObject // Parent A
        {
        public:
          void Animate();
        
        protected:
          int totalFrames;
          int currentFrame;
        };
        
        class PhysicsObject   // Parent B
        {
        public:
          void Fall();
          void Accelerate();
        
        protected:
          float velocity;
          float acceleration;
        };
        
        class PlayerCharacter : public AnimationObject,
                                public PhysicsObject
        {
        public:
          void HandleKeyboard();
        
        protected:
          string name;
        };
        

      3. Private, Public, and Protected
        Member access

        Remember that we can declare our member variables and methods as private and public, but we can also make items protected. Protected members are similar to private, except that protected members will be inherited by child classes - private members do not get inherited.

        Access Class' methods Childrens' methods Outside functions
        public Accessible Accessible Accessible
        protected Accessible Accessible Not accessible
        private Accessible Not accessible Not accessible

        Inheritance style
        You can also use public, protected, and private when inheriting other classes. You probably won't need to ever do a protected or private inheritance.
        • public inheritance: Child class inherits public and protected members from the parent.
        • protected inheritance: Child class inheirits public and protected members and turns them into protected members.
        • private inheritance: Child class inherits public and protected members and turns them into private members.

        This could be used if, for some reason, you want a child class to inherit certain members but don't want "grandchildren" to have access to those members as well.


      4. Function Overriding

        When a child class inherits from a parent class, the parent class' public and protected methods are passed down to the child and these functions are still callable for objects of the child type.

        If we would like, the child class can also override any methods from the parent. This means that we write a new version of the function with the same return type and parameter list, and when that function is called from the child class, the child class' version will be called instead of the parents'.

        Let's say we're writing a quizzer program that will support differnet question types. We can write a base "Question" class with whatever would be in common between all Questions:

        class Question
        {
        public:
          Question( string q, string a ) {
            question = q;
            answer = a;
          }
        
          void AskQuestion() {
            cout << question << endl;
            string playerAnswer;
            cin >> playerAnswer;
        
            if ( playerAnswer == answer ) {
              cout << "Right!" << endl;
            } else {
              cout << "Wrong." << endl;
            }
          }
        
        protected:
          string question;
          string answer;
        };
        
        

        We can then inherit from our Question class to make different types of quiz questions: Multiple choice, true/false, and so on. Adding additional functionality means that we might want to rewrite how AskQuestion() works - so we can.

        This also means that everything in our Question family has a similar interface - create a question, set it up, and then call AskQuestion() no matter what kind of question it is.

        class MultipleChoiceQuestion : public Question
        {
        public:
          void DisplayQuestion()
          {
            cout << question << endl;
            for ( int i = 0; i < 4; i++ )
              {
                cout << i << ". "
                     << answerChoices[i] << endl;
              }
            int playerAnswer;
            cin >> playerAnswer;
        
            if ( answerChoices[ playerAnswer ] == answer ) {
              cout << "Right!" << endl;
            } else {
              cout << "Wrong." << endl;
            }
          }
        
        protected:
          string answerChoices[4];
        };
        

        Calling the parents' version of a method

        In some cases, perhaps the parent version of a method has some common functionality we will need no matter what version in the family we're using, but the child versions of the methods add on to that functionality. We can directly call the parent's version of some method from within a child's method by explicitly calling the method with the parent class name and the scope resolution operator ::.

        class Lion
        {
        public:
          void Activities()
          {
            cout << "Hunt" << endl;
            cout << "Eat" << endl;
            cout << "Sleep" << endl;
          }
        };
        
        class HouseCat : public Lion
        {
        public:
          void Activities()
          {
            Lion::Activities();
            cout << "Talk to human" << endl;
            cout << "Use catbox" << endl;
          }
        };
        

        For this example, the HouseCat does everything the Lion does and adds a few activities to the list. We don't have to re-write the same Activities from Lion - we can just call the parent's version of the method directly with Lion::Activities();.


      5. Constructors and Destructors in the family

        We often use constructors to initialize member variables for a class, and when a child is inheriting its parents' member variables, we want to make sure we're not forgetting to still initialize those variables.

        We can call the parent's constructor from the child's constructor as well, but we do it via the initializer list of a constructor - a little bit of code after the constructor's function header that can be used to initialize variables and call the parent constructor.

        class Person
        {
        public:
          Person( string name )
          {
            m_name = name;
          }
        
        protected:
          string m_name;
        };
        
        class Student : public Person
        {
        public:
          Student( string name, string major )
            : Person( name ) // Calling the parent ctor
          {
            m_major = major;
          }
        
        protected:
          string m_major;
        };
        

        (Note: "ctor" is short for "constructor")

        We can also initialize variables through the initializer list as well:

        class Student : public Person
        {
        public:
          Student( string name, string major )
            : Person( name ), m_major( major )
          {
            // nothing else to do now!
          }
        
        protected:
          string m_major;
        };
        

5.14.2. Programming lab

banner-lab.png

5.14.3. Project updates

\newpage

5.15. Unit 14: C++: Strings and File I/O

5.15.1. Reading

banner-reading.png

  1. Strings

    reading_u07_Strings_image.png

    A string is a special data type that really is just an array of char variables. A string has a lot going on behind-the-scenes, and it also has a set of functions you can use to do some common operations on a string - finding text, getting a letter at some position, and more.

    Note that everything with strings is case-sensitive. A computer considers the letter 'a' and 'A' different, since they are represented by different number codes. Keep that in mind for each of the string's functions.


    Strings as arrays

    When we declare a string like this:

    string str = "pizza";
    

    what we have behind-the-scenes is an array like this:

    Value: 'p' 'i' 'z' 'z' 'a'
    Index: 0 1 2 3 4

    Declaring a string actually gives us an array of char variables. We can access the string as a whole by using the string variable's name (str), or access one char at a time by treating str like an array.

    1. Subscript operator - get one char with [ ]

      We can access each letter of the string directly with the subscript operator, just like an array:

      cout << str[0] << endl; // Outputs p
      cout << str[1] << endl; // Outputs i
      cout << str[2] << endl; // Outputs z
      cout << str[3] << endl; // Outputs z
      cout << str[4] << endl; // Outputs a
      

      Because we can act on a string like an array, this means we can also use a variable to access an arbitrary index of a character in the array…

      int i;
      cout << "Get which letter? ";
      cin >> i;
      cout << str[i];
      

      Or even iterate over the string with a for loop

      for ( int i = 0; i < str.size(); i++ )
      {
          cout << i << " = " << str[i] << endl;
      }
      

      Additionally, strings have a set of functions that we can use to manipulate, search, and otherwise work with them.


      String functionality

    2. Size of the string

      size_t size() const;

      The string's size() function will return the size of the string - how many characters are stored in the string. The size_t data type is just a type of integer - an unsigned integer, because sizes cannot be negative amounts.

      Documentation: https://www.cplusplus.com/reference/string/string/size/

      Example: Outputting a string's length
      Let's write a little program that asks the user to enter some text, and then outputs the length of the string:
      string text;
      cout << "Enter some text: ";
      getline( cin, text );
      cout << "That string is " << text.size()
          << " characters long!" << endl;
      

      When the user enters a line of text, it will count all characters (including spaces) in the string, so the text "cats dogs" would be 9 characters long.

      Enter some text: cats dogs
      That string is 9 characters long!
      

      reading_u07_Strings_catsdogs.png

      Example: Counting z's
      If we wanted to use a for loop to iterate over all the letters of an array, we could! Perhaps we want to count the amount of z's that show up:
      string text;
      int zCount = 0;
      
      cout << "Enter some text: ";
      getline( cin, text );
      
      // Iterate from i=0 to the size of the string (not-inclusive)
      for ( unsigned int i = 0; i < text.size(); i++ )
      {
          // If this letter is a lower-case z or upper-case Z
          if ( text[i] == 'z' || text[i] == 'Z' )
          {
              // Add one to z count
              zCount++;
          }
      }
      
      // Display the result
      cout << "There were " << zCount
          << " z(s) in the string!" << endl;
      
      Enter some text: The wizard fought a zombie lizard
      There were 3 z(s) in the string!
      

      reading_u07_Strings_wizard.png


    3. Concatenating strings with +

      We can use the + operator to add strings together as well. This is called concatenation.

      Let's say we have two strings we want to combine - favoriteColor and petName, we can use the concatenation operator + to build a new string, superSecurePassword.

      string favoriteColor = "purple";
      string petName = "Luna";
      string superSecurePassword = favoriteColor + petName;
      cout << superSecurePassword << endl; // = purpleLuna
      

      reading_u07_Strings_luna.png

      We can also add onto strings by using the += operator. Let's say you're building a string over time in a program, and want to append parts separately.

      string pizzaToppings = "";
      
      // Later on...
      pizzaToppings += "Buffalo sauce, ";
      
      // Later on...
      pizzaToppings += "Cheese, ";
      
      // Later on...
      pizzaToppings += "Pineapple";
      
      // Later on...
      cout << pizzaToppings << endl;
      

      At the end of the program, the value of pizzaToppings would be:

      "Buffalo sauce, Cheese, Pineapple"


    4. Finding text with find()

      size_t find (const string& str, size_t pos = 0 ) const;

      The find function can be used to look for a substring in a bigger string. If the substring is found, its position is returned. Otherwise, the value of string::npos is found.

      When a starting pos is included, it only begins the search at that position. If left off, it defaults to 0 (the start of the string).

      Documentation: https://www.cplusplus.com/reference/string/string/find/

      So when we want to search a string for some text, we can call it like bigString.find( findMeString ), and that function call will return an unsigned integer: the location of the findMeString within bigString, or the value of string::npos when it is not found.

      string str = "this was written during the 2021 winter storm make it stop please.";
      
      string findMe = "winter";
      
      size_t position = str.find( findMe );
      
      cout << "The text \"" << findMe
          << "\" was found at position " << position << endl;
      
      The text "winter" was found at position 33
      

    5. Finding substrings with substr()

      string substr (size_t pos = 0, size_t len = npos) const;

      Returns a string within the string, starting at the position pos provided, and with a length of len.

      Documentation: https://www.cplusplus.com/reference/string/string/substr/

      With the substr() function, we can pull part of a string out, using a starting point and a length.

      string text = "Name: Bob";
      
      int start = 6;
      int length = 3;
      
      string name = text.substr( start, length );
      
      cout << "Extracted \"" << name << "\"." << endl;
      
      
      Extracted "Bob".
      

      reading_u07_Strings_bob.png


    6. Comparing text with compare()

      int compare (const string& str) const;

      This compares the string with str and returns an integer:

      • \(0\) is returned if both strings are the same.
      • \(< 1\) (a negative number) is returned if the caller string is "less-than" the str string.
      • \(> 1\) (a positive number) is returned if the caller string is "greater-than" the str string.

      One character is "less than" another if it comes before, and it is "greater than" if it comes after, alphabetically.

      (Remember that lower-case and upper-case letters are considered separate, so comparing 'a' to 'A' would actually return a positive number.)

      Documentation: https://www.cplusplus.com/reference/string/string/compare/

      string first;
      string second;
      
      cout << "Enter first string: ";
      cin >> first;
      
      cout << "Enter second string: ";
      cin >> second;
      
      int order = first.compare( second );
      
      cout << endl << "Result: " << order << endl;
      
      Enter first string: apple
      Enter second string: banana
      
      Result: -1
      

      reading_u07_Strings_compare.png


    7. Inserting text into a string with insert()

      = string& insert (sizet pos, const string& str);=

      This function will take the calling string and modify it by inserting the string str at the position pos.

      Documentation: https://www.cplusplus.com/reference/string/string/insert/

      string text = "helloworld";
      
      cout << "Original text: " << text << endl;
      
      int start;
      string insertText;
      
      cout << "Enter text to insert: ";
      getline( cin, insertText );
      
      cout << "Enter position to insert: ";
      cin >> start;
      
      text = text.insert( start, insertText );
      
      cout << endl << "String is now: " << text << endl;
      
      Original text: helloworld
      Enter text to insert: -to the-
      Enter position to insert: 5
      
      String is now: hello-to the-world
      

    8. Erasing a chunk of text with erase()

      string& erase (size_t pos = 0, size_t len = npos);

      This function will return a string with a portion erased, starting at position pos and pulling out a length of len.

      Documentation: https://www.cplusplus.com/reference/string/string/erase/

      string text = "helloworld";
      
      cout << "Original text: " << text << endl;
      
      int start;
      int length;
      
      cout << "Enter position to begin erasing: ";
      cin >> start;
      
      cout << "Enter length of text to erase: ";
      cin >> length;
      
      text = text.erase( start, length );
      cout << endl << "String is now: " << text << endl;
      
      Original text: helloworld
      Enter position to begin erasing: 2
      Enter length of text to erase: 5
      
      String is now: herld
      

    9. Replacing a region of text with replace()

      string& replace (size_t pos, size_t len, const string& str);

      This function is similar to erase, except it will insert the string str in place of the erased text.

      Documentation: https://www.cplusplus.com/reference/string/string/replace/

      string text = "helloworld";
      
      cout << "Original text: " << text << endl;
      
      int start;
      int length;
      string replaceWith;
      
      cout << "Enter string to replace with: ";
      getline( cin, replaceWith );
      
      cout << "Enter position to begin replacing: ";
      cin >> start;
      
      cout << "Enter length of text to replacing: ";
      cin >> length;
      
      text = text.replace( start, length, replaceWith );
      cout << endl << "String is now: " << text << endl;
      
      Original text: helloworld
      Enter string to replace with: BYE
      Enter position to begin replacing: 2
      Enter length of text to replacing: 5
      
      String is now: heBYErld
      

  2. Review questions:
    1. A string is technically an array of…
    2. How would you output the letter at position 0 in a string? At position 2?
    3. What function is used to get the amount of characters in a string?
    4. What operator is used to combine (concatenate) two strings together?
    5. What does the find() function return if the searched-for substring is not found?
  • File I/O

    reading_u08_FileIO_image.png

    1. Output streams

      In C++ we've been using cout to stream information to the console window in our programs. Using cout requires including the iostream library.

      cout << "Hello, " << location << "!" << endl;
      

      Writing out to a text file works in a very similar way. We will need to include the fstream library in order to get access to the ofstream (output-file-stream) object. Streaming out to a file works in the same way as with cout, except that we need to declare a ofstream variable and use it t open a text file.

      #include <iostream>             // Console streams
      #include <fstream>              // File streams
      using namespace std;
      
      int main()
      {
        // Console output
        cout << "Hello, world!" << endl;
      
        // File output
        ofstream outputFile( "file.txt" );
        outputFile << "Hello, world!" << endl;
        outputFile.close();
      }
      

      You can use the output stream operator << to continue chaining together different items - endl=s, string literals in double quotes, variable values, etc. just like with your =cout statements.

      Once the file is closed, you will see the file on your computer, usually the same directory as your .cpp files.

      Different file types…
      Any file type that is a plaintext file can be built as well - .html files, .csv files, heck, even .cpp files. However, generally if you wanted to write a program to output a different file type, you'd use a library to properly convert the data.

      Outputting html data:

      #include <fstream>
      using namespace std;
      
      int main()
      {
        ofstream outputFile( "page.html" );
        outputFile << "<body>" << endl;
        outputFile << "<h1>This is a webpage</h1>" << endl;
        outputFile << "<p>Hello, world!</p>" << endl;
        outputFile << "</body>" << endl;
        outputFile.close();
      }
      

      Outputting csv data:

      #include <fstream>
      using namespace std;
      
      int main()
      {
        ofstream outputFile( "spreadsheet.csv" );
        outputFile << "COLUMN1,COLUMN2,COLUMN3" << endl;
        outputFile << "cell1,cell2,cell3" << endl; // row 1
        outputFile << "cell1,cell2,cell3" << endl; // row 2
        outputFile << "cell1,cell2,cell3" << endl; // row 3
        outputFile.close();
      }
      

    2. Input streams

      File input streams work just line console input streams. You will need to create a ifstream (input-file-stream) object and open a file, and then you can read in the contents of that file. Files to be read should generally be placed in the same path as your .cpp file, though the working directory on your system may vary.

      #include <fstream>              // File streams
      #include <string>               // Strings
      using namespace std;
      
      int main()
      {
        string data1, data2;
      
        // File input
        ifstream inputFile( "file.txt" );
        inputFile >> data1;                             // Read one word
        inputFile.ignore();                             // Clear buffer
        getline( inputFile, data2 );    // Read one line
        inputFile.close();
      }
      

      Just like with using cin, you can use the input stream operator (>>) and the getline() function with the file streams to get text. You will also need one or more variable to store the text read in.

      1. Reading an entire file
        Reading chunks of data:
        Let's say you have a file full of data to read in. For this example, the file will be a list of numbers that we want to add together. The file might look something like….

        Data.txt:

        9 15 16 0 10 13 5 16 1 9 2 17 3 3 8
        

        In our program, we want to read all the numbers, but to do this, we need to use a loop and read in one number at a time. We can keep a running total variable to keep adding data to the sum as we go. We can use a loop to continue reading while it is successful, using this as the condition: input >> readNumber. This will stop the loop once there's nothing else to read, and it updates the readNumber variable with the input each cycle.

        ifstream input( "data.txt" );
        
        int sum = 0;    // Sum variable
        int readNumber; // Buffer to store what we read in
        
        // Keep reading while it's possible
        while ( input >> readNumber )
          {
            sum += readNumber;          // Add on to the sum
        
            // Output what we did
            cout << "Read number " << readNumber
                 << ",\t sum is now " << sum << endl;
          }
        
        cout << "FINAL SUM: " << sum << endl;
        

        The output of this program would look like this:

        Read number 9,   sum is now 9
        Read number 15,  sum is now 24
        (... etc ...)
        Read number 3,   sum is now 119
        Read number 8,   sum is now 127
        FINAL SUM: 127
        
        Reading lines of data:
        In other cases, maybe you're reading in text data from a file and want to read in a full line at a time. We can use a while loop with the getline() function as well to make sure we read each line of a text file:
        ifstream input( "story.txt" );
        
        string line;
        
        while ( getline( input, line ) )
          {
            cout << line << endl;
          }
        

        The output of this program would look like this:

        CHAPTER I.
        Down the Rabbit-Hole
        
        
        Alice was beginning to get very tired of sitting by her
        sister on the bank, and of having nothing to do: once or
        twice she had peeped into the book her sister was
        reading, but it had no pictures or conversations in it,
        "and what is the use of a book," thought Alice "without
        pictures or conversations?"
        

    3. Saving and loading data
      1. Parsing files

        Reading in data from a file is one thing, but making sense of what was read in is another. Are you storing saved data from the last session of the program? Are you trying to parse data to crunch? How do you read that data in logically?

        First, if your program is going to be saving output that will need to be read in and made sense of later on, how do you organize the data that's output? It's up to you to make sure to structure the output save data in a consistent and readable way…

        SAVEGAME        RachelsGame
        LEVEL           5
        GOLD            1000
        LOCATION        RegnierCenter
        

        If every save file from the program is formatted in the same way, then when reading the file we can make assumptions…

        • First word: "SAVEGAME" - not important (human readable)
        • Second word: Save game name - store in gameFileName
        • Third word: "LEVEL" - not important (human readable)
        • Fourth word: Player's level - store in level

        …And so on. This could work, but we could also take advantage of those human-readable labels that were added into the file.

        • Read firstWord.
        • If firstWord is "SAVEGAME", then read the next word into gameFileName.
        • Else if firstWord is "LEVEL", then read the next word into level.

        So, let's say we have our four variables for a save game:

        Name Data type
        gameFileName string
        level int
        gold int
        location string

        When we go to save our game file, it would be a simple output like this:

        // Save the game
        ofstream output( "save.txt" );
        output << "SAVEGAME " << gameFileName << endl;
        output << "LEVEL    " << level << endl;
        output << "GOLD     " << gold << endl;
        output << "LOCATION " << location << endl;
        

        Giving us a save file like:

        SAVEGAME MyGame
        LEVEL    1
        GOLD     10
        LOCATION OCB
        

        Then to read it, we could approach it in a couple of different ways. If we assume that the file will always have exactly four lines of data saved and will always be in the same order, we could read it like:

        // Load the game
        string buffer;
        ifstream input( "save.txt" );
        input >> buffer; // ignore SAVEGAME
        input >> gameFileName;
        
        input >> buffer; // ignore LEVEL
        input >> level;
        
        input >> buffer; // ignore GOLD
        input >> gold;
        
        input >> buffer; // ignore LOCATION
        input >> location;
        

        Or, if we weren't sure that order these would show up in, we could store the first item read into buffer each time, and based on what that label was ("SAVEGAME", "LEVEL", etc.) we would know what to read next

        string buffer;
        ifstream input( "save.txt" );
        
        while ( input >> buffer )
          {
            if ( buffer == "SAVEGAME" )
              input >> gameFileName;
        
            else if ( buffer == "LEVEL" )
              input >> level;
        
            else if ( buffer == "GOLD" )
              input >> gold;
        
            else if ( buffer == "LOCATION" )
              input >> location;
          }
        

        If we stepped through this, buffer is always going to store one of the data labels, because after buffer is read, we immediately read the second item in the line of text. Once the second item is read, the next thing to be read will be the next label.


  • Review questions:
    1. What library is required in order to use file I/O in C++?
    2. What data type is used to create a file that inputs (reads in) text from an outside file?
    3. What data type is used to create a file that outputs (writes out) text to an outside file?
    4. How do you write out the string literal "Hello world" to an output file?
    5. How do you write out the value of a variable to an output file?
    6. How do you read in one word from an input file?
    7. How do you read in one line from an input file?
  • 5.15.2. Programming lab

    banner-lab.png

    5.15.3. Project updates

    \newpage

    5.16. Unit 15: Tech Literacy: Ethics in tech

    5.16.1. Reading

    banner-reading.png

    5.16.2. Tech literacy

    \newpage

    5.17. Unit 16: C++: Intro to recursion

    5.17.1. Reading

    banner-reading.png

    c2_u18_Recursion_recursionB.png

    1. Examples of recursion in math

      Recursion is a manner of solving a problem by breaking it down into smaller pieces - and those smaller pieces are solved in the same way as the big-picture version.

      1. Summation:

        A summation can be broken down into smaller chunks but using the same structure as the original.

        Let's say we have \[ \sum_{i=1}^{6} { i } = 1 + 2 + 3 + 4 + 5 + 6 \]

        The summation can be redefined recursively:

        \[ \sum_{i=1}^{6} { i } = 6 + \sum_{i=1}^{5} { i } \]

        The summation from \(i = 1\) to \(6\) is equivalent to whatever the sum is at \(i=6\), plus the sum from \(i = 1\) to \(5\). We can continue this way until we get to a case that we know (e.g., \(\sum_{i=1}^{1} { i }\)).

        • \(\sum_{i=1}^{6} { i } = 6 + \sum_{i=1}^{5} { i }\)
        • \(\sum_{i=1}^{5} { i } = 5 + \sum_{i=1}^{4} { i }\)
        • \(\sum_{i=1}^{4} { i } = 4 + \sum_{i=1}^{3} { i }\)
        • \(\sum_{i=1}^{3} { i } = 3 + \sum_{i=1}^{2} { i }\)
        • \(\sum_{i=1}^{2} { i } = 2 + \sum_{i=1}^{1} { i }\)
        • We know that \(\sum_{i=1}^{1} { i } = 1\), then we move back up to sub out this value.
        Recursive problem Finding the solution
        A. \[\sum^{6}_{i=1} { i } = 6 + \sum_{i=1}^{5} { i }\] But what is \(\sum_{i=1}^{5} { i }\)? \(\downarrow\) K. DONE! \[\sum_{i=1}^{6} { i } = 6 + \sum_{i=1}^{5} { i } = 6 + 15 = 21\]
        B. \[\sum_{i=1}^{5} { i } = 5 + \sum_{i=1}^{4} { i }\] But what is \(\sum_{i=1}^{4} { i }\)? \(\downarrow\) J. \(\uparrow\) \[\sum_{i=1}^{5} { i } = 5 + \sum_{i=1}^{4} { i } = 5 + 10 = 15\]
        C. \[\sum_{i=1}^{4} { i } = 4 + \sum_{i=1}^{3} { i }\] But what is \(\sum_{i=1}^{3} { i }\)? \(\downarrow\) I. \(\uparrow\) \[\sum_{i=1}^{4} { i } = 4 + \sum_{i=1}^{3} { i } = 4 + 6 = 10\]
        D. \[\sum_{i=1}^{3} { i } = 3 + \sum_{i=1}^{2} { i }\] But what is \(\sum_{i=1}^{2} { i }\)? \(\downarrow\) H. \(\uparrow\) \[\sum_{i=1}^{3} { i } = 3 + \sum_{i=1}^{2} { i } = 3 + 3 = 6\]
        E. \[\sum_{i=1}^{2} { i } = 2 + \sum_{i=1}^{1} { i }\] But what is \(\sum_{i=1}^{1} { i }\)? \(\downarrow\) G. \(\uparrow\) \[\sum_{i=1}^{2} { i } = 2 + \sum_{i=1}^{1} { i } = 2 + 1 = 3\]
        F. \[\sum_{i=1}^{1} { i } = 1\] \(\uparrow\)
        Now we start substituting this value, from bottom-up… \(\rightarrow\) \(\uparrow\)

      2. Factorials:

        With a factorial of \(n\), written \(n!\) the formula to solve this is:

        \[ n! = n \cdot (n-1) \cdot ... \cdot 3 \cdot 2 \cdot 1 \]

        So,

        • \(2!\) is \(2 \cdot 1\),
        • \(3!\) is \(3 \cdot 2 \cdot 1\),
        • \(4!\) is \(4 \cdot 3 \cdot 2 \cdot 1\), and so on.

        Additionally, we can break down each of these equations: \(3!\) is equivalent to \(3 \cdot 2!\) \(4!\) is equivalent to \(4 \cdot 3!\) … \(n!\) is equivalent to \(n \cdot (n-1)!\)

        Thinking of breaking down the problem here in this way is looking at it recursively.

        c2_u18_Recursion_recursivefactorial.png

    2. Recursion in programming

      In programming, we usually approach problems iteratively, using a for-loop or a while-loop:

      // Iterative solution
      int Sum( int n )
      {
          int result = 0;
          for ( int i = 1; i <= n; i++ )
          {
              result += i;
          }
          return result;
      }
      

      Which solves this summation:

      \[ \sum_{i=1}^n {i} \]

      But some types of problems lend themselves better to a recursive solution. To be fair, though, many problems are better solved iteratively. So how do we know which method is better?


      1. Recursion basics

        When defining a problem recursively in programming, we need two things:

        1. A terminating case: A case that ends our recursing. Often, this is some known data, something hard-coded. For example with our summation, the terminating case would be that \[ \sum_{i=1}^1 {i} = 1 \] or for a factorial, \(1! = 1\) and \(0! = 1\).
        2. A recursive case: A recursive case is what happens otherwise - if we're not to a solution yet (via the terminating case), we call the same function again, but with updated arguments. For example:
          • Factorial( 4 ) = 4 * Factorial( 3 )
          • Factorial( 3 ) = 3 * Factorial( 2 )
          • Factorial( 2 ) = 2 * Factorial( 1 )
          • Factorial( 1 ) = 1

        We can solve these basic math operations both iteratively and recursively:

        // Iterative solution
        int FactorialI( int n )
        {
            int result = 1;
            for ( int i = 1; i <= n; i++ )
            {
                result *= i;
            }
            return result;
        }
        
        // Recursive solution
        int FactorialR( int n )
        {
            if ( n == 1 || n == 0 ) { return 1; }
            return n * FactorialR( n-1 );
        }
        

      2. Breaking down problems into recursive solutions

        c2_u18_Recursion_recursionstress.png

        One of the most challenging parts of recursion, at least for me, is trying to break away from thinking of something in terms of "looping" and figuring out how to think of it "recursively". It's not as natural-feeling, so don't worry if it's confusing at first.

        Let's tackle some basic design problems to practice.

        Summation:
        Try to convert the Summation function to be recursive. Think about what the terminating case would be and the recursive case. Use the Factorial function for reference.
        int SumI( int n )
        {
            int result = 0;
            for ( int i = 1; i <= n; i++ )
            {
                result += i;
            }
            return result;
        }
        
        int SumR( int n )
        {
            // Terminating case?
            // Recursive case?
        }
        
        Solution for recursive summation:
        int SumR( int n )
        {
            if ( n == 1 ) { return 1; }  // Terminating case
            return n + SumR( n-1 );      // Recursive case
        }
        

        Draw a line:
        Now let's make a function that will draw a line of symbols, with a parameter being the length. Iteratively, it could look like this:
        void DrawLineI( int amount )
        {
            for ( int i = 0; i < amount; i++ )
            {
                cout << "-";
            }
        }
        

        How would we repeat this behavior recursively? How do we have a "count up" sort of functionality? What would be the terminating case?

        We're going to think of it a little differently: The recursive function will only output one "-" before it recurses. Each time it recurses, it draws one more dash…

        void DrawLine_Recursive( int amount )
        {
            cout << "-";
            // Recursive case
            DrawLineR( amount );
        }
        

        However, we don't have a terminating case… it will continue looping, but it won't go forever like a bad while loop. We will eventually run out of stack space and the program will encounter a stack overflow and end.

        So what would the terminating case be? How do we adjust the amount each time? Since amount is the one parameter we have, let's have the recursion stop once it is 0. Each time we recurse, we can pass in amount-1 to the next call…

        void DrawLine_Recursive( int amount )
        {
            cout << "-";
        
            // Terminating case
            if ( amount == 0 ) { return; }
        
            // Recursive case
            DrawLineR( amount - 1 );
        }
        

        Counting Up:
        How can we write a function that takes a start and end integer, and outputs each number between them (including the start and end)?

        Iteratively, it could look like this:

        void CountUpI( int start, int end )
        {
            for ( int i = start; i <= end; i++ )
            {
                cout << i << "\t";
            }
        }
        

        Try to fill in this function to build a recursive solution:

        void CountUpR( int start, int end )
        {
        }
        
        
        Solution for recursive count up:
        void CountUpR( int start, int end )
        {
            cout << start << "\t";
        
            // Terminating case
            if ( start == end ) { return; }
        
            // recursive case
            CountUp_Recursive( start+1, end );
        }
        

      3. A case for recursion

        Although there are a lot of problems we could convert from an iterative solution to a recursive solution, there are some types of problems that really are better suited to recursion.

        1. Searching a File System

          c2_u18_Recursion_filesystem.png

          On a harddrive, we generally have files and folders. Folders can contain files, but they will also contain subfolders as well. And subfolders can each contain their own subfolders.

          When you don't know the exact layout of the filesystem, how would you even begin to iteratively search for a specific file?

          Instead, it is good to think of it recursively. For example, say we're searching for a folder where you store your Recursion homework. We will begin searching at the top-most folder of the computer. The algorithm would then run like…

          1. folder = "C:", 2. folder = "work", 3. folder = "C:"
          c2_u18_Recursion_traverse1.png c2_u18_Recursion_traverse2.png c2_u18_Recursion_traverse1.png
          Is this "Recursion"? No. Is this "Recursion"? No. Are there subfolders? Yes.
          Are there subfolders? Yes. Are there subfolders? No. Then, search next subfolder.
          Then, search first subfolder. Return.  
          4. folder = "school" 5. folder = "cs210" 6. folder = "school"
          c2_u18_Recursion_traverse3.png c2_u18_Recursion_traverse4.png c2_u18_Recursion_traverse5.png
          Is this "Recursion"? No. Is this "Recursion"? No. Are there subfolders? Yes.
          Are there subfolders? Yes. Are there subfolders? No. Then, search next subfolder.
          Then, search next subfolder. Return.  
          7. folder = "cs235" 8. 9.
          c2_u18_Recursion_traverse6.png c2_u18_Recursion_traverse8.png c2_u18_Recursion_traverse9.png
          Is this "Recursion"? No. folder = "Recursion" folder = "cs235"
          Are there subfolders? Yes. Is this "Recursion"? Yes. Return Recursion.
          Then, search the first subfolder. Return Recursion.  
          10. folder = "school" 11. folder = "C:"  
          c2_u18_Recursion_traverse10.png c2_u18_Recursion_traverse11.png  
          Return Recursion. Return Recursion.  

          For find functionality, terminating cases would be:

          1. Have we found the item? Return it.
          2. Are we out of places to search? Return nothing.

          And the recursive case would be:

          1. Has a subfolder? Call Find() on that folder.

        2. Solving a maze

          Solving a maze can be approached from a recursive standpoint much easier than an iterative one.

          Terminating case: If we hit a dead-end, or if we find the end of the maze.

          Recursive case: Explore each available direction.

          1. c2_u18_Recursion_maze.png Starting point. We will iterate through all directions we can go. In some cases, there is only one valid direction.
          2. c2_u18_Recursion_maze1.png Once we hit multiple options, we will recurse into a direction. If we end up returning unsuccessfully, we will recurse into the other direction.
          3. c2_u18_Recursion_maze2.png If we hit a dead-end, this is a terminating case and we begin returning.
          4. c2_u18_Recursion_maze.png We get back to a previous function call where we can continue recursing in a different direction.
          5. c2_u18_Recursion_maze.png Hitting a terminating case and returning backwards essentially "undoes" the path that takes us to a dead-end.
          6. c2_u18_Recursion_maze.png The recursion ends once we either run out of all potential paths to take, or we achieve the goal.

    3. Practice problems

      Implement an iterative (looping-based) and recursive solution for each of the following.

      You can also download the code files here:

      1. Alphabet

      This function takes in a letter start and a letter end and will generate a string with all the letters between those two values. (e.g., for Alphabet_Iter( 'A', 'D' ) will return "ABCD".)

      /**
         @param      char        start       The starting char (inclusive) to begin at
         @param      char        end         The end char (inclusive) to run until
         @return     string                  A string containing all the letters from start to end.
      */
      //! Build a string that contains letters from start to end.
      string Alphabet_Iter( char start, char end )
      {
        return "NOT IMPLEMENTED"; // Temporary
      }
      
      /**
         @param      char        start       The starting char (inclusive) to begin at
         @param      char        end         The end char (inclusive) to run until
         @return     string                  A string containing all the letters from start to end.
      */
      //! Build a string that contains letters from start to end.
      string Alphabet_Rec( char start, char end, string text /* = "" */ )
      {
        // Terminating Case:
        // Out of letters to go over (in other words, start > end).
      
        // Recursive case:
        // Add the next letter, then call return and recurse into this function using the next letter.
      
        return "NOT IMPLEMENTED"; // Temporary
      }
      
      // Unit test function
      void Test_Set1()
      {
        //string Alphabet_Iter( char start, char end )
        cout << endl << "---------------------------------------------------" << endl;
        cout << "Test - Alphabet" << endl;
        string expectedOut, actualOut;
      
        cout << endl << left << setw( headerWidth ) << "TEST 1: Alphabet_Iter: Generate 'a' thru 'g'" << setw( pfWidth );
        expectedOut = "abcdefg";
        actualOut = Alphabet_Iter( 'a', 'g' );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 2: Alphabet_Iter: Generate 'l' thru 'p'" << setw( pfWidth );
        expectedOut = "lmnop";
        actualOut = Alphabet_Iter( 'l', 'p' );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 3: Alphabet_Rec: Generate 'a' thru 'g'" << setw( pfWidth );
        expectedOut = "abcdefg";
        actualOut = Alphabet_Rec( 'a', 'g' );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 4: Alphabet_Rec: Generate 'l' thru 'p'" << setw( pfWidth );
        expectedOut = "lmnop";
        actualOut = Alphabet_Rec( 'l', 'p' );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      }
      

      2. Factorial These functions should take in some input n and generate the result of n!.

      /**
         Factorial functions
         @param      int     n       The value of n
         @return     int             The value of n!
      
         Calculate n! by multiplying n * (n-1) * (n-2) * ... * 3 * 2 * 1.
      */
      //! Calculates n!
      int Factorial_Iter( int n )
      {
        return -1; // Temporary
      }
      
      /**
         Factorial functions
         @param      int     n       The value of n
         @return     int             The value of n!
      
         Calculate n! by multiplying n * (n-1) * (n-2) * ... * 3 * 2 * 1.
      */
      //! Calculates n!
      int Factorial_Rec( int n )
      {
        // Terminating case:
        // n is 0.
      
        // Recursive case:
        // n is greater than 0.
      
        return -1; // Temporary
      }
      
      // Unit test function
      void Test_Set2()
      {
        // int Factorial_Iter( int n );
        cout << endl << "---------------------------------------------------" << endl;
        cout << "Test - Factorial" << endl;
        int expectedOut, actualOut;
      
        cout << endl << left << setw( headerWidth ) << "TEST 1: Factorial_Iter: Find 0!" << setw( pfWidth );
        expectedOut = 1;
        actualOut = Factorial_Iter( 0 );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
        cout << endl << left << setw( headerWidth ) << "TEST 2: Factorial_Iter: Find 5!" << setw( pfWidth );
        expectedOut = 120;
        actualOut = Factorial_Iter( 5 );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
        cout << endl << left << setw( headerWidth ) << "TEST 3: Factorial_Rec: Find 0!" << setw( pfWidth );
        expectedOut = 1;
        actualOut = Factorial_Rec( 0 );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
        cout << endl << left << setw( headerWidth ) << "TEST 4: Factorial_Rec: Find 5!" << setw( pfWidth );
        expectedOut = 120;
        actualOut = Factorial_Rec( 5 );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      }
      

      3. Count consonants This function should iterate through the input string text and for each character, if that char is a consonant, add 1 to a counter. Return the total amount of consonants at the end.

      //! Helper function to find whether something is a consonant or not.
      bool IsConsonant( char letter )
      {
        if (    tolower( letter ) == 'a' ||
                tolower( letter ) == 'e' ||
                tolower( letter ) == 'i' ||
                tolower( letter ) == 'o' ||
                tolower( letter ) == 'u'
                )
          {
            return false;
          }
      
        return true;
      }
      
      /**
         CountConsonants functions
         @param  string  text        The text to count the consonants within
         @return int                 The amount of consonants found
      
         Iterate through each char in the string [text] and count up 1 if that letter is a consonant.
         Return the amount of consonants found.
      */
      //! Count the amount of consonants in a string and return the count.
      int CountConsonants_Iter( string text )
      {
        return -1; // Temporary
      }
      
      /**
         CountConsonants functions
         @param  string  text        The text to count the consonants of
         @param  int     pos         The current position being investigated
         @return int                 The amount of consonants found
      
         Recurse through each char in the string [text] and count up 1 if that letter is a consonant.
         Return the amount of consonants found.
      */
      //! Count the amount of consonants in a string and return the count.
      int CountConsonants_Rec( string text, unsigned int pos /* = 0 */ )
      {
        // Terminating case:
        // No more letters to look at.
      
        // Recursive case:
        // Still more letters to inspect.
      
        return -1; // Temporary
      }
      
      // Unit test function
      void Test_Set3()
      {
        // int CountConsonants_Iter( string text )
        cout << endl << "---------------------------------------------------" << endl;
        cout << "Test - CountConsonants" << endl;
        int expectedOut, actualOut;
      
        cout << endl << left << setw( headerWidth ) << "TEST 1: CountConsonants_Iter: Count consonants in \"aeiou\"" << setw( pfWidth );
        expectedOut = 0;
        actualOut = CountConsonants_Iter( "aeiou" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
        cout << endl << left << setw( headerWidth ) << "TEST 2: CountConsonants_Iter: Count consonants in \"jkl\"" << setw( pfWidth );
        expectedOut = 3;
        actualOut = CountConsonants_Iter( "jkl" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
        cout << endl << left << setw( headerWidth ) << "TEST 3: CountConsonants_Iter: Count consonants in \"hellothere\"" << setw( pfWidth );
        expectedOut = 6;
        actualOut = CountConsonants_Iter( "hellothere" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 4: CountConsonants_Rec: Count consonants in \"aeiou\"" << setw( pfWidth );
        expectedOut = 0;
        actualOut = CountConsonants_Rec( "aeiou" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
        cout << endl << left << setw( headerWidth ) << "TEST 5: CountConsonants_Rec: Count consonants in \"jkl\"" << setw( pfWidth );
        expectedOut = 3;
        actualOut = CountConsonants_Rec( "jkl" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
        cout << endl << left << setw( headerWidth ) << "TEST 6: CountConsonants_Rec: Count consonants in \"hellothere\"" << setw( pfWidth );
        expectedOut = 6;
        actualOut = CountConsonants_Rec( "hellothere" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      }
      

      4. Get First Uppercase These functions should return the first uppercase letter (a char) within the given string (string text).

      //! Helper function to figure out if letter is upper-case
      bool IsUppercase( char letter )
      {
        return ( letter != ' ' && toupper( letter ) == letter );
      }
      
      /**
         @param  string  text    The text to look for capital letters in
         @return char            The first upper-case character found, or ' ' if none found.
      
         Iterate through each char in the string [text] and return the char if it is an upper-case letter.
         If no upper-case letters are found, return a space character: ' '
      */
      //! Returns the first uppercase letter found, or ' ' if none are found.
      char GetFirstUppercase_Iter( string text )
      {
        return 'x'; // Temporary
      }
      
      /**
         @param  string  text    The text to look for capital letters in
         @param  int     pos     The current position being investigated
         @return char            The first upper-case character found, or ' ' if none found.
      
         Recurse through each char in the string [text] and return the char if it is an upper-case letter.
         If no upper-case letters are found, return a space character: ' '
      */
      //! Returns the first uppercase letter found, or ' ' if none are found.
      char GetFirstUppercase_Rec( string text, unsigned int pos /* = 0 */ )
      {
        // Terminating case:
        // No more letters to look at, OR
        // First uppercase letter found.
      
        // Recursive case:
        // Still more letters to investigate
      
        return 'x'; // Temporary
      }
      
      // Unit test function
      void Test_Set4()
      {
        //char GetFirstUppercase_Iter( string text )
        cout << endl << "---------------------------------------------------" << endl;
        cout << "Test - GetFirstUppercase" << endl;
        char expectedOut, actualOut;
      
        cout << endl << left << setw( headerWidth ) << "TEST 1: GetFirstUppercase_Iter: Find first consonant in \"HELLO\"" << setw( pfWidth );
        expectedOut = 'H';
        actualOut = GetFirstUppercase_Iter( "HELLO" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 2: GetFirstUppercase_Iter: Find first consonant in \"heLLO\"" << setw( pfWidth );
        expectedOut = 'L';
        actualOut = GetFirstUppercase_Iter( "heLLO" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 3: GetFirstUppercase_Iter: Find first consonant in \"hello\"" << setw( pfWidth );
        expectedOut = ' ';
        actualOut = GetFirstUppercase_Iter( "hello" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 4: GetFirstUppercase_Rec: Find first consonant in \"HELLO\"" << setw( pfWidth );
        expectedOut = 'H';
        actualOut = GetFirstUppercase_Rec( "HELLO" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 5: GetFirstUppercase_Rec: Find first consonant in \"heLLO\"" << setw( pfWidth );
        expectedOut = 'L';
        actualOut = GetFirstUppercase_Rec( "heLLO" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      
        cout << endl << left << setw( headerWidth ) << "TEST 6: GetFirstUppercase_Rec: Find first consonant in \"hello\"" << setw( pfWidth );
        expectedOut = ' ';
        actualOut = GetFirstUppercase_Rec( "hello" );
      
        if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
        else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
      
      }
      
      1. Answers

        1. Alphabet

        string Alphabet_Iter( char start, char end )
        {
          string generated = "";
          for ( char i = start; i <= end; i++ )
            {
              generated += i;
            }
          return generated;
        }
        
        string Alphabet_Rec( char start, char end, string text /* = "" */ )
        {
          if ( start > end )
            {
              return text;
            }
        
          return text + start + Alphabet_Rec( start+1, end );
        }
        

        2. Factorial

        int Factorial_Iter( int n )
        {
          int result = 1;
          for ( int i = n; i >= 1; i-- )
            {
              result *= i;
            }
          return result;
        }
        
        int Factorial_Rec( int n )
        {
          if ( n == 0 )
            {
              return 1; // 0! = 1
            }
        
          return n * Factorial_Rec( n-1 );
        }
        

        3. Count consonants

        int CountConsonants_Iter( string text )
        {
          int consCount = 0;
          for ( size_t i = 0; i < text.size(); i++ )
            {
              if ( IsConsonant( text[i] ) )
                {
                  consCount++;
                }
            }
          return consCount;
        }
        
        int CountConsonants_Rec( string text, unsigned int pos /* = 0 */ )
        {
          if ( pos >= text.size() )
            {
              return 0;
            }
        
          return IsConsonant( text[pos] ) + CountConsonants_Rec( text, pos+1 );
        }
        

        4. Get First Uppercase

        char GetFirstUppercase_Iter( string text )
        {
          for ( size_t i = 0; i < text.size(); i++ )
            {
              if ( IsUppercase( text[i] ) )
                {
                  return text[i];
                }
            }
          return ' '; // nothing found
        }
        
        char GetFirstUppercase_Rec( string text, unsigned int pos /* = 0 */ )
        {
          if ( pos >= text.size() )
            {
              return ' ';
            }
          if ( IsUppercase( text[pos] ) )
            {
              return text[pos];
            }
        
          return GetFirstUppercase_Rec( text, pos+1 );
        }
        

    5.17.2. Programming lab

    banner-lab.png

    Author: Rachel Wil Sha Singh

    Created: 2024-04-16 Tue 17:42

    Validate