CS 250: Basic Data Structures using C++ (Spring 2024 version)

📊 Presentation - Set up (U00.PRES)

📖️ Reading - Welcome (U00.READ)

• 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.

  

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

  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.

  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.

  

  Roadmap

  

  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.

  

  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}

  ---

• What are "data structures"?
  

  

  A data structure is an object (a class, a struct - some type of structured thing) that holds data. In particular, the entire job of a data structure object is to store data and provide an interface for adding, removing, and accessing that data.

  "Don't all the classes we write hold data? How is this different from other objects I've defined?"

  In the past, you may have written classes to represent objects, like perhaps a book. A book could have member variables like its title, isbn, and year published, and some methods that help us interface with a book…

  Book
  - title	: string
  - isbn	: string
  - year	: int
  + Setup( ... )	: void
  + Update( ... )	: void
  + Display()	: void

  However - this is not a data structure. We could, however, use a data structure to store a list of books:

  BookArray
  - bookArray	: Book[]
  - arraySize	: int
  - totalBooks	: int
  + AddBook( newBook: Book )	: void
  + Update( index: int, newBook: Book )	: void
  + RemoveBook( index: int )	: void
  + GetBook( index: int )	: Book&
  +DisplayAll()	: void
  +GetSize()	: int

  A data structure will store a series of some sort of data. Often, it will use an array or a linked list as a base structure and functionality will be built on top.

  Ideally, the user doesn't care about how the data structure works, they just care that they can add, remove, and access data they want to store.

  Ideally, when we are writing a data structure, it should be:

  • Generic, so you could store any data type in
  • Reusable, so that the data structure can be used in many different programs.
  • Robust, offering exception handling to prevent the program from crashing when something goes wrong with it.
  • Encapsulated, handling the inner-workings of dealing with the data, without the user (or other programmers working outside the data structure) having to write special code to perform certain operations.

  The way I try to conceptualize the work I'm doing on a data structure is to pretend that I'm a developer that is going to create and sell a C++ library of data structures that other developers at other companies can use in their own, completely separate, software projects. If I'm selling my data structures package to other businesses, my code should be dependable, stable, efficient, and relatively easy to use.

  

  \vspace{0.2cm}

  ---

• What is "algorithm analysis"?
  

  

  Algorithm Analysis is the process of figuring out how efficient a function is and how it scales over time, given more and more data to operate on.

  This is another important part of dealing with data structures, as different structures will offer different trade offs when it comes to the efficiency of data access functions, data searching functions, data adding functions, and data removal functions.

  Every operation takes a little bit of processing time, and as you iterate over data, that processing time is multiplied by the amount of times you go through a loop.

  Example: Scalability

  Let's say we have a sorting algorithm that, for every \(n\) records, it takes \(n^2\) program units to find an object. If we had 100 records, then it would take \(100^2 = 10,000\) time-units to sort the set of data.

  What the time-units are could vary - an older machine might take longer to execute one instruction, and a newer computer might process an instruction much more quickly, but we think of algorithm complexity in this sort of generic form.

  

  Example: Efficiency of an Array-based structure

  0	1	2	3	4
  "kansas"	"missouri"	"arkansas"	"ohio"	"oklahoma"

  In an array-based structure, we have a series of elements in a row, and each element is accessible via its index (its position in the array). Arrays allow for random-access, so accessing element #2 is instant:

  cout << arr[2];
  

  No matter how many elements there are (\(n\)), we can access the element at index 2 without doing any looping. We state that this is \(O(1)\) ("Big-O of 1") time complexity for an access operation on an *array.

  However, if we were searching through the unsorted array for an item, we would have to start at the beginning and look at each item, one at a time, until we either found what we're looking for, or hit the end of the array:

  for ( int i = 0; i < ARR_SIZE; i++ )
  {
      if ( arr[i] == searchTerm )
      {
          return i; // found at this position
      }
  }
  return -1;      // not found
  

  For search, the worst-case scenario is having to look at all elements of the array to ensure what we're looking for isn't there. Given \(n\) items in the array, we have to iterate through the loop \(n\) times. This would end up being \(O(n)\) ("Big-O of \(n\)") time complexity for a search operation on an array.

  We can build our data structures on top of an array, but there is also a type of structure called a linked structure, which offers its own pros and cons to go with it. We will learn more about algorithm analysis and types of structures later on.

  \vspace{0.2cm}

  ---

• Why is there a whole class dedicated to "data structures"?
  

  Of course, plenty of data structures have already been written and are available out there for you to use. C++ even has the Standard Template Library full of structures already built and optimized!

  "So why are we learning to write data structures if they've already been written for us?"

  While you generally won't be rolling your own linked list for projects or on the job, it is important to know how the inner-workings of these structures operate. Knowing how each structure works, its tradeoffs in efficiency, and how it structures its data will help you choose what structures to use when faced with a design decision for your software.

  

  ---

• Review questions
  

  Answer these questions in your notes, then check your work by completing the related Concept Intro assignment on Canvas.

  Review questions:

  1. Why should a data structure be generic?
  2. What does it mean for a data structure to be robust?
  3. Most data structures have what kind of core functionality?

🔎 Concept Intro - Welcome/setup (U00.CIN)

🧑‍🔬 Lab - Set up (U00.LAB)

• Installing an IDE
  

  Download and install an IDE (Integrated Development Environment) on your system. Here are some suggested ones, but you can use whatever tools you'd like.

  IDE	Link	Platforms	Info
  Visual Studio Community	https://visualstudio.microsoft.com/vs/community/	Windows only (C++ version)	During install, make sure to select Desktop development with C++!!
  Code::Blocks	https://www.codeblocks.org/downloads/binaries/	Windows/Linux	Lightweight, better for older machines. (WINDOWS: Download the mingw-setup version!)
  XCode	https://developer.apple.com/xcode/	Mac

  We'll use our IDE more once we set up git and clone our repository…

  ---

• Installing git
  

  Starting off, you will need to install the git program to your computer. Go to https://git-scm.com/ and select Download for your OS. Make sure to read through the setup settings here to prevent headaches in the future. (In particular, not setting Vim as the default text editor… unless that's something you want.)

  Most of the default settings are fine, but take note:

  • Select Components: Make sure that "Git Bash Here" is checked.
  • Choosing the default editor used by Git: Choose something like Notepad or if you have a preferred text editor, use that.

  ---

• Configuring git
  

  After git is installed, we will need to do a one-time configuration. Open up Git Bash (in Windows) or use git from your terminal (Linux/Mac).

  You will need to configure your name:

  git config --global user.email "you@example.com"
  

  Replace "you@example.com" with your email (such as your student email).

  And your email address:

  git config --global user.name "Your Name"
  

  Replace "Your Name" with your name, which is what will show up when you submit code file edits.

  Finally, we're setting up a default merge resolution scheme, which you don't really need to worry about the details right now:

  git config --global pull.rebase false
  

  ---

• Registering a GitLab account
  

  1. Go to the sign up page: Start by going to https://gitlab.com/users/sign_up and fill out the form to create your account.

  

  Fill out your first and last name, a username, email address, and password. Note that if you want to maintain your privacy you might use an alternative email/name, but make sure to let the instructor know who you are!

  2. Navigate to your profile page: After registering, going to https://gitlab.com/ should take you to a "Projects" page. You will be able to view your repositories here later on. On the right-hand sidebar, click on your profile image (it might be some default picture), then click on the top section to go to your profile.

  

  3. Bookmark your profile page: Once you're on your profile page, the URL will look something like this: https://gitlab.com/YOURUSERNAME Take note of this URL and bookmark this page. You may also need to give this link to the instructor for further setup.

  

  ---

• Make sure the instructor knows your GitLab username
  

  Post your GitLab username in the "❓ Unit 00 Setup - GitLab Username" assignment. Once you have access to your repository, you can continue.

  ---

• Cloning the repository
  

  Your operating system: Navigate to the folder where you're storing your class projects. From here, right-click in the empty space and select Git Bash Here to open Git Bash.

  Repository webpage: On the repository webpage (gitlab.com) click on the blue Clone button and copy the URL listed under the Clone with HTTPS header. (You can use SSH if you know how to set it up, but we aren't going to cover that here.)

  

  Git Bash: Use the git clone URL command in Git Bash. This will clone the repository within the folder you opened Git Bash in. (Windows: To use PASTE, right-click in Git Bash… CTRL+V will not work here.)

  $ git clone https://gitlab.com/rsingh13-student-repos/2024-01_cs250/YOURSSO-cs250.git
  Cloning into 'YOURSSO-cs250'...
  remote: Enumerating objects: 3, done.
  remote: Counting objects: 100% (3/3), done.
  remote: Compressing objects: 100% (2/2), done.
  remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0
  Receiving objects: 100% (3/3), done.
  

  (This will be "cs235" or "cs250" based on the course you're in.)

  Now that the folder is on your computer, you will need to change directory into the folder. Use cd FOLDERNAME (in the example above, the folder name would be YOURSSO-cs235 or YOURSSO-cs250) to enter the repository folder in Git Bash.

  Changing directory in Git Bash:

  

  Viewing the folder in Windows Explorer:

  

  ---

• Creating a branch
  

  Command	Description
  git branch	View available branches
  git checkout -b BRANCHNAME	Create a new branch with the given BRANCHNAME
  git checkout BRANCHNAME	Checkout an existing branch whose name matches the BRANCHNAME

  When working on an assignment, you will need to create a new branch each time.

  To view available branches, use the git branch command:

  $ git branch
  * main
  

  To create a new branch, use the git checkout -b BRANCHNAME command. The branch name needs to be unique. I suggest putting the Unit # in the branch name at least.

  $ git checkout -b u00_setup
  Switched to a new branch 'u00_setup'
  

  Now if you type in git branch again you will see two branches with the asterisk marking which branch you're currently on:

  $ git branch
    main
  * u00_setup
  

  Each branch basically has its own code space. If you have work-in-progress code happening on separate branches, they will only be available on that specific branch. If you switch to another branch you'll only see code for that branch, but you can always keep switching between to get the code back. (When starting a new assignment, make sure to go back to the main branch and use git pull to grab latest code before then creating a new branch. I'll try to put a reminder in future assignments.)

  If you want to switch between existing branches, use git checkout BRANCHNAME:

  $ git checkout main
  Switched to branch 'main'
  Your branch is up to date with 'origin/main'.
  
  $ git checkout u00_setup
  Switched to branch 'u00_setup'.
  

  (Note: The main branch might be named "master" so if your git branch shows "master" instead of "main", use that.)

  Stay on your new branch for now.

  ---

  Command	Description
  ls	List out the files and folders in the current directory
  touch FILENAME	Create a new file
  echo "text" >> FILENAME	Append text to a file
  git status	View files that have changed
  git add FILENAME	Add a specific file to the changeset
  git add *.cpp	Add all files that end with ".cpp" to the changeset
  git add .	Add all changed files to the changeset
  git commit	Create a snapshot of currently added changes
  git commit -m "text"	Create a snapshot of currently added changes, setting commit message at the same time
  git push -u origin BRANCHNAME	Push the changes in the branch to the server

  Starting off, your repository may only have a README file in the folder:

  $ ls
  README.md
  

  In Windows you can create a new text file in here by opening notepad and saving a new file in this directory.

  In Git Bash you can create a file by using the touch command: Use the touch FILENAME command to create a new file. Name your file YOURNAME.txt . You can open the file from your OS and edit the text, or you can use the following command to put the text "Hello, I'm NAME!" in place:

  $ echo "Hello, I'm Rachel!" >> u00_hello.txt
  

  Next, use the git status command to view the changed file:

  $ git status
  On branch u00_setup
  Untracked files:
    (use "git add <file>..." to include in what will be committed)
    u00_hello.txt
  
  nothing added to commit but untracked files present (use "git add" to track)
  

  We need to use the git add FILENAME command to mark the file for the changeset.

  $ git add u00_hello.txt
  

  It won't show any confirmation message if there is no error.

  Next, we use the git commit -m "COMMIT MESSAGE" command to make a snapshot of the file's changes at this point:

  $ git commit -m "Created my text file"
  [rsingh13_u04ex 9eb8e5c] Created my text file
   1 file changed, 1 insertion(+)
   create mode 100644 u00_hello.txt
  

  Finally, use the git push -u origin BRANCHNAME command to push your changes to the GitLab server:

  $ git push -u origin u00_setup
  Enumerating objects: 4, done.
  Counting objects: 100% (4/4), done.
  Delta compression using up to 12 threads
  Compressing objects: 100% (2/2), done.
  Writing objects: 100% (3/3), 303 bytes | 303.00 KiB/s, done.
  Total 3 (delta 1), reused 0 (delta 0)
  remote:
  remote: To create a merge request for u00_setup, visit:
  remote:   (A URL)
  remote:
  To gitlab.com:(REPOSITORY URL).git
   * [new branch]      u00_setup -> u00_setup
  Branch 'u00_setup' set up to track remote branch 'u00_setup' from 'origin'.
  

  ---

• Pulling remote changes
  

  Command	Description
  git pull	Pull latest changes from the server

  GitLab webpage: On the webpage your branch will now show up in the dropdown menu.

  

  Select your branch and you'll be able to see the last commit and your file here:

  

  Open up your text file here and click the blue Edit button and select an editor. Add another line to the text file, then click the Commit changes button at the bottom of the page.

  

  Git Bash: Use the git pull command here to pull all changes, which will grab the changes that you just made from the server.

  $ git pull
  remote: Enumerating objects: 5, done.
  remote: Counting objects: 100% (5/5), done.
  remote: Compressing objects: 100% (2/2), done.
  remote: Total 3 (delta 1), reused 0 (delta 0), pack-reused 0
  Unpacking objects: 100% (3/3), 517 bytes | 517.00 KiB/s, done.
  From gitlab.com:(URL)
     9eb8e5c..90394af  u00_setup -> origin/u00_setup
  Updating 9eb8e5c..90394af
  Fast-forward
   u00_hello.txt | 2 ++
   1 file changed, 2 insertions(+)
  

  When you open the text file in Notepad or a text editor, you will now see the second line of text.

  ---

• Dealing with merge conflicts
  

  This time we're going to purposefully create a merge conflict. This happens when changes are made to the same file from different locations (such as on your computer and the web, or between different developers) and git can't figure out how to automatically merge the changes together. It can be intimidating to deal with, but it isn't too bad.

  Computer: Edit your text file to add some text in the middle. Then use git add FILENAME , git commit -m "Edited file", but don't push yet.

  GitLab: Edit your text file to add a different line of text in the middle.

  

  Git Bash: Now that you have two sets of changes, try to push your changes to the server. It will be rejected:

  $ git push
  To gitlab.com:(URL).git
   ! [rejected]        u00_welcome -> u00_welcome (fetch first)
  error: failed to push some refs to 'git@gitlab.com:(URL).git'
  hint: Updates were rejected because the remote contains work that you do
  hint: not have locally. This is usually caused by another repository pushing
  hint: to the same ref. You may want to first integrate the remote changes
  hint: (e.g., 'git pull ...') before pushing again.
  hint: See the 'Note about fast-forwards' in 'git push --help' for details.
  

  It gives you a hint - you need to use git pull to grab any latest changes from the server:

  $ git push
  To gitlab.com:(URL).git
   ! [rejected]        u00_welcome -> u00_welcome (non-fast-forward)
  error: failed to push some refs to 'git@gitlab.com:(URL).git'
  hint: Updates were rejected because the tip of 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.
  

  Use git pull, which will work, but result in a merge conflict:

  $ git pull
  Auto-merging u00_welcome.txt
  CONFLICT (content): Merge conflict in u00_welcome.txt
  Automatic merge failed; fix conflicts and then commit the result.
  

  Open the text file in your editor and you'll see some additions to the file:

  Hello, I'm Rachel!
  <<<<<<< HEAD
  This is my third edit.
  =======
  Fourth update!!!
  >>>>>>> a0c7bd54e2c5c19d1ebd41a84e7a6b8820573cf9
  This is a second update!
  

  There are two regions, and we need to manually decide how we want to merge the text. You could just remove the markers if you wanted both changes. Make the update and save the file:

  Hello, I'm Rachel!
  This is my third edit.
  Fourth update!!!
  This is a second update!
  

  Then do your add, commit, and push to push the merged updates to the server.

  Protip: You can combine multiple commands together with &&:

  $ git add . && git commit -m "manual merge" && git push

  GitLab: On the website, you can select the "Commits" link under the "Code" section to view all the changes you've made to the code:

  

  ---

• Creating an example program to test our IDE
  

  Lastly we're going to create a basic C++ project and make sure everything builds correctly. The project and code you create here should be stored within your repository.

  • If you're using VS Code, please check the reference portion of the book for the section labeled VS Code - Open projects, building, and running.
  • If you're using another code editor and wish to build from the terminal using the Makefile, look in the reference portion of the book for the section labeled Terminal - Building and running

  Visual Studio

  1. From the starting page, select "Create a new project".

     

  2. Select "Empty project" and click "Next".

     

  3. Set your Project name. Make sure to set the project Location to somewhere within your repository directory.

     

  4. Right-click on your empty project and select Add then New item…

     

  5. Type in "main.cpp" then click "Add".

     

  6. Add a simple starter C++ program into main.cpp.

     

  7. Go to the "Build" dropdown menu and select "Build Solution".

     

  8. It should show a success in the Output window.

     

  9. Then, click the "(play) Local Windows Debugger" button to run the program.

     

  10. Your program text will show up in a console.

      

  11. Your files will be in the location you set up. The .cpp file is your source code, and the .vcxproj is the project file.

      

  Code::Blocks

  1. From the starting page, select "Create a new project".

     

  2. Select "Empty project" and click "Go".

     

  3. Set your Project name. Make sure to set the project Location to somewhere within your repository directory.

     

  4. Go to the "File" dropdown menu and select "New", then "Empty file".

     

  5. It will ask you to save the file first, name it main.cpp. Default options are fine.

     

  6. Add a simple starter C++ program into main.cpp.

     

  7. Go to the "Build" dropdown menu and select "Build".

     

  8. The program should build without any errors.

     

  9. Click on the "play" button in the toolbar to run the program.

     

  10. Your program text should show up in the console.

      

  11. Your files will be in the location you set up. The .cpp file is your source code and the .cbp file is the project file.

      

  Afterwards, add, commit, and push your changes:

  git add .
  git commit -m "Example project"
  git push -u origin u00_setup
  

  ---

• Creating a merge request
  

  Once changes are made, you'll create a merge request. This is how you can have your code reviewed, and the instructor will sign off on it and merge it to the main branch, where all the code will live together. This is similar to in software development, where everybody will work on their own features on their own branches, create a merge request, get their code reviewed, then a senior developer will merge the code into the main project.

  GitLab: On the main repository page you will see a message saying that there are changes in your branch, with a button "Create merge request":

  

  You can mostly leave the defaults unless you want to add notes. Scroll down and click the blue "Create merge request" button.

  There will be a merge request page generated:

  

  The URL of this page is what you will usually turn in as your Lab assignments

  Once you've created a merge request, copy the URL of the merge request on the GitLab.com webpage:

  

  Back on the Canvas page, locate the assignment and click the link:

  

  Then click on "Start Assignment":

  

  Paste in the URL to your Merge Request in the "Website URL:" textbox, then click "Submit Assignment" to finish the turn in.

  

📊 Presentation - Exploring data (U01.PRES)

📖️ Reading - Exploring data (U01.READ)

• OK but how does that relate to this class?
  

  Data needs to be stored, and while long-term storage means putting it in some kind of database, receiving data to save, or pulling data to crunch, requires software at some level. We need to be able to store the data in a data structure, and we need to choose the structure that is the most efficient for the goals we have - do we prioritize access speed or insert speed? Do we want a structure that auto-sorts incoming data so we can find records more quickly? What kind of sorting algorithm do we use to sort the unsorted data?

  In this class we'll be focusing on common data structures you'll see as a software developer - array-based structures, link-based structures, binary search trees, hash tables, stacks, and queues. We're going to learn how they work, and the efficiency of their functionality. While you probably won't be writing these structures from scratch after this course, knowing how they work helps you make an informed design decision on what is the best tool for the job.

  ---

• Example: Spotify
  

  We can get some kind of idea of the underlying structure of a system by looking at the API (Application Programming Interface) that it exposes to the outside world. Many modern websites offer APIs in order to allow third parties to create helper programs and services that work with the data stored by the original service.

  Looking at the Spotify API documentation (https://developer.spotify.com/documentation/web-api), we can see several main "objects" it provides:

  1. Albums
  2. Artists
  3. Audiobooks
  4. Categories
  5. Chapters
  6. Episodes
  7. Genres
  8. Markets
  9. Player
  10. Playlists
  11. Search
  12. Shows
  13. Tracks
  14. Users

  If you click on one of the objects, it will show an example of requests that an external program can call, such as Get Album, Get Album Tracks, Save Albums for Current User, and so on.

  Clicking on a request type will also show a Response Sample, which shows what kind of information may be returned with a call, such as Get Album:

  Listing 1: Example response data from the Spotify API documentation

  {
    "album_type": "compilation",
    "total_tracks": 9,
    "available_markets": [
      "CA",
      "BR",
      "IT"
    ],
    "id": "2up3OPMp9Tb4dAKM2erWXQ",
    "images": [
      {
        "url": "https://i.scdn.co/image/ab67616d00001e02ff9ca10b55ce82ae553c8228",
        "height": 300,
        "width": 300
      }
    ],
    "release_date": "1981-12",
    "type": "album",
    "artists": [
      {
        "id": "string",
        "name": "string",
      }
    ],
    "tracks": {
      "total": 4,
      "href": "https://api.spotify.com/v1/me/shows?offset=0&limit=20",
      "next": "https://api.spotify.com/v1/me/shows?offset=1&limit=1",
      "previous": "https://api.spotify.com/v1/me/shows?offset=1&limit=1"
    },
    "copyrights": [
      {
        "text": "string",
        "type": "string"
      }
    ],
    "genres": [
      "Egg punk",
      "Noise rock"
    ],
    "popularity": 0
  }
  

  The data and the form it's returned in via API response isn't necessarily how the data is stored in the database itself, or how the data is stored in objects when worked on by the Spotify servers themselves. Usually, API systems pulls data from multiple sources and bundles it together to return as a response. But, this can at least give us some idea of how the actual system may be organized.

  

  This is just a small example, containing a "Music" section (Artist, Album, Track) and a "User" section (User, Playlist). The arrows show relationships between the objects. But this diagram is also lacking any of the back-end functionality that helps everything actually do something. On their own, it's just data stored somewhere. A program has to be written around it.

  ---

• Additional APIs
  

  In the Tech Literacy assignment you will brainstorm about data used for specific types of software. You may want to reference the API pages for these common apps for ideas:

  • Instagram: https://developers.facebook.com/docs/instagram-api/reference
  • Canvas LMS: https://canvas.instructure.com/doc/api/all_resources.html
  • Grubhub: https://developer.grubhub.com/

  \newpage

🧠 Tech Literacy - Exploring data (U01.TEC)

📊 Presentation - CS 200 Review: Basics (U02.PRES)

📖️ Reading - CS 200 review: Basics (U02.READ)

• Includes
  

  Include	Features
  #include <iostream>	Use of cout (console output), cin (console input), getline
  #include <string>	Use of the string data type and its functions
  #include <fstream>	Use of ofstream (output file stream), ifstream (input file stream), and related functions
  #include <array>	Use of array from the Standard Template Library
  #include <vector>	Use of vector from the Standard Template Library
  #include <cstdlib>	C standard libraries, usually used for rand().
  #include <ctime>	C time libraries, usually used for srand( time( NULL ) ); to seed random # generator
  #include <cmath>	C math libraries, such as sqrt, trig functions, etc.
  #include "file.h	Use "" to include .h files within your own project. DON'T USE INCLUDE ON .cpp FILES!!

  About the using command

  The using namespace std; command states that we're using the std namespace. If this is left off, then we need to prefix any C++ types and functions with std::, such as std::cout << "Hello!" << std::endl;

  Best practices:

  • If your program ONLY uses C++ standard library includes, use using namespace std; for brevity.
  • If your program uses MULTIPLE LIBRARIES, avoid using namespace std; and prefix each type/function with the library it belongs to (e.g., std::string from the STD library, sf::vector2f from the SFML library)

  ---

• Bare minimum C++ programs
  

  Without arguments:

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

  With arguments:

  #include <string>
  #include <iostream>
  using namespace std;
  
  int main( int argCount, char* args[] )
  {
    if ( argCount < 4 ) { cout << "Not enough arguments!" << endl; return 1; }
  
    int my_int = stoi( args[1] );
    float my_float = stof( args[2] );
    string my_string = string( args[3] );
  
    return 0;
  }
  

  ---

• Building and running from the command line
  

  Building a single source file:

  g++ SOURCEFILE.cpp -o PROGRAMNAME.out
  

  Building multiple source files:

  g++ *.cpp *.h -o PROGRAMNAME.out
  

  (There's a different command to use the Visual Studio compiler to build from command line.)

  Running a program without arguments:

  ./PROGRAMNAME.out
  

  Running a program with arguments:

  ./PROGRAMNAME.out arg1 arg2 arg3
  

  ---

• Variable declaration
  
  1. Declaring a variable: DATATYPE VARIABLENAME;
  2. Declaring a variable and assigning a value: DATATYPE VARIABLENAME = VALUE;
  3. Declaring and assigning a named constant: const DATATYPE NAME = VALUE;
  4. Assigning a new value to an existing variable: VARIABLENAME = VALUE;
  5. Copying a value from one variable to another: UPDATEDVAR = COPYME;

  Data type	Value examples
  int	-5, 0, 100
  float	0.99, -3.25, 1.0
  string	"Hello world!"
  char	'a', '$'
  bool	true, false

  Increment/Decrement statements:

  • a++, a--
  • ++a, --a
  • a+=5;, a-=5;
  • a = a + 5;, a = a - 5;

  Notes:

  • LHS = RHS; copies FROM RHS TO LHS; make sure you have the right order!
  • A hard-coded value, like "Hello", is known as a literal.

  ---

• Console input and output
  
  1. Output a variable's value: cout << VARIABLENAME;
  2. Output a string literal: cout << "Hello";
  3. Chain together multiple items: cout << "Label: " << VARIABLENAME << endl;
  4. Input to a variable: cin >> VARIABLENAME;
  5. Input a whole line to a string variable: getline( cin, STRINGVARIABLE );

  Notes:

  • The << operator is called the output stream operator and is used on cout statements.
  • The >> operator is called the input stream operator and is used on cin statements.
  • endl is only to be used with cout statements, not cin!
  • getline can only be used with strings!! Use cin >> for other data types.
  • You need a cin.ignore() ONLY in between cin >> ... and getline( cin, ... ).
    • If your program is skipping an input then you're missing a cin.ignore();.
    • If your program is getting input but not storing the first letter then you have too many cin.ignore(); statements / they're in the wrong place.

  ---

• Boolean expressions
  
  • AND (&&)
    • Expression is TRUE if all sub-expressions are TRUE
    • Expression is FALSE if at least one sub-expression is FALSE
  • OR (||)
    • Expression is TRUE if at least one sub-expression is TRUE
    • Expression is FALSE if all sub-expressions are FALSE
  • NOT (!)
    • Expression is TRUE if sub-expression is FALSE
    • Expression is FALSE if sub-expression is TRUE

  a	b	a AND b	a OR b
  T	T	T	T
  T	F	F	T
  F	T	F	T
  F	F	F	F

  a	NOT a
  T	F
  F	T

  ---

• If statements
  
  • if statement:

  if ( CONDITION_A )
  {
    // Action A
  }
  

  • if/else statement:

  if ( CONDITION_A )
  {
    // Action A
  }
  else
  {
    // Action Z
  }
  

  • if/else if statement:

  if ( CONDITION_A )
  {
    // Action A
  }
  else if ( CONDITION_B )
  {
    // Action B
  }
  else if ( CONDITION_C )
  {
    // Action C
  }
  

  • if/else if/else statement:

  if ( CONDITION_A )
  {
    // Action A
  }
  else if ( CONDITION_B )
  {
    // Action B
  }
  else if ( CONDITION_C )
  {
    // Action C
  }
  else
  {
    // Action Z
  }
  

  Condition types can be a boolean variable:

  bool done = true;
  if ( done )
  {
    cout << "Goodbye!" << endl;
  }
  

  Or a boolean expression:

  int a = 10, b = 5;
  if ( a > b )
  {
    cout << "a is bigger!" << endl;
  }
  

  Notes:

  • else statements NEVER TAKE A CONDITION
  • Whichever condition evaluates to true, all future else if and else statements are skipped.

  ---

• Switch statements
  

  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;
  }
  

  Notes:

  • You can leave off break; from a case statement. In this case, fallthrough occurs, where the following case's code will be executed, up until it hits a break; statement.
  • Switch statements like the one above can be replaced with if (myNumber = 1)=, else if (myNumber = 2)=.
  • In C++, switch doesn't work with string, only primitive data types like int, float, char.

  Fallthrough example:

  char choice;
  cout << "Enter a choice: (y/n): ";
  cin >> choice;
  
  switch( choice )
  {
    case 'y':
    case 'Y':
      cout << "YES" << endl;
      break;
  
    case 'n':
    case 'N':
      cout << "NO" << endl;
      break;
  
    default:
      cout << "INVALID INPUT!" << endl;
  }
  

  ---

• While loops
  

  while ( CONDITION ) { }

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

  Notes:

  • While loops use CONDITIONS like if statements do.
  • While loops are susceptible to infinite loop errors if nothing within the loop causes the CONDITION to evaluate to false eventually. Be careful!

  ---

• For loops
  

  Normal for loop:

  for ( INIT; CONDITION; UPDATE ) { }

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

  Notes:

  • When using STL arrays or vectors, size_t or unsigned int should be used instead of int for i. This will remove the warning relating to testing .size() (which returns size_t) against a signed integer.

  Range-based for loop:

  In versions of C++ past C++98 (from 1998) you can use range-based for loops to iterate over a range of items:

  for ( INIT : RANGE ) { }

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

  ---

• Arrays and vectors
  
  1. Declare a C-style array: DATATYPE ARRAYNAME[ SIZE ];
  2. Declare a C++ STL array: array<DATATYPE, SIZE> ARRAYNAME;
  3. Declare a C++ STL vector: vector<DATATYPE> VECTORNAME;
  4. Declare a dynamic array via pointer: DATATYPE * PTR = NEW DATATYPE[ SIZE ];
  5. Destroy a dynamic array: delete [] PTR;
  6. Initialize an array with an initializer list: DATATYPE ARRAY[] = { VAL1, VAL2, VAL3 } (also works for array and vector).

  Notes:

  • The position of an item within an array is called its index.
  • The variable within the array at some position is called its element.
  • A vector is a dynamic array, but you don't have to worry about the memory management. :) This means that it can be resized.
  • A array is a fixed size, just like the C-style array.

  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.

  ---

• File I/O
  

  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 );
  

  Notes:

  • An ifstream open will fail if the file requested does not exist or cannot be found. Use if ( input.fail() ) to check for a failure scenario.
  • An ofstream open will create a file if it doesn't already exist.
  • The default path where files are written to or read from is wherever your project file is (.vcxproj for Visual Studio, .cbp for Code::Blocks). You can also set a default working directory in your project settings.
    • Mac users may need to specify an absolute path, like "~/myfile.txt", which will put the file in your home directory. I don't know how to use XCode but we can work through it together if you need help.

  ---

• Review questions:
  

  Answer these questions in your notes, then check your work by completing the related Concept Intro assignment on Canvas.

  1. The starting point of all C++ programs is…
  2. Given two variables, vip and player3, how do you copy the name from the player3 variable into the vip variable?
  3. << is known as …, >> is known as…
  4. getline( cin, … ) can only be used with…
  5. An if or else if statement's contents are executed when…
  6. The three parts of a for loop's header is…
  7. … can be resized, but … cannot.

🔎 Concept Intro - CS 200 review: Basics (U02.CIN)

🧑‍🔬 Lab - CS 200 review: Basics (U02.LAB)

• Set up: Creating a new branch in your repository
  

  

  First, Open up Git Bash (Windows) or your Terminal (Linux/Mac) from within your repository directory. Make sure you're inside the repository folder, which should be named something like YOURSSO-CLASS.

  Next, create a new branch in the repository with the checkout command: git checkout -b u02_review

  $ git checkout -b u02_review
  Switched to a new branch 'u02_review'
  

  

  Now your folder is on the new branch and you can start working on the assignment.

  ---

• Download the starter code
  

  Download the following starter code and unzip it to your repository folder.

  • shared/labs/starter-code/u02_Review_CPPBasics.zip

  

  All starter files:

  .
  ├── INFO.h
  ├── main.cpp
  ├── Project_CodeBlocks
  │   ├── CPPReviewBasics.cbp
  │   ├── CPPReviewBasics.depend
  │   └── CPPReviewBasics.layout
  ├── Project_Makefile
  │   └── Makefile
  ├── Project_VisualStudio
  │   ├── CPPBasicsReview.sln
  │   ├── CPPBasicsReview.vcxproj
  │   ├── CPPBasicsReview.vcxproj.filters
  │   ├── results.txt
  │   ├── test1.txt
  │   └── test2.txt
  └── u02_Review_CPPBasics
      ├── P1_variables
      │   └── U02_P1_PizzaSlices.cpp
      ├── P2_branching
      │   └── U02_P2_LetterGrade.cpp
      ├── P3_looping
      │   └── U02_P3_SalaryRaise.cpp
      ├── P4_vector
      │   └── U02_P4_GPA.cpp
      ├── P5_ofstream
      │   └── U02_P5_SalaryRaise.cpp
      ├── P6_ifstream
      │   ├── lyricsB.txt
      │   └── U02_P6_Lyrics.cpp
      ├── U02_Headers.cpp
      └── U02_Headers.h
  

  Visual Studio users:

  Open the Project_VisualStudio folder and open the CPPBasicsReview.sln file to get started.

  Code::Blocks users:

  Open the Project_CodeBlocks folder and open the CPPReviewBasics.cbp file to get started.

  Build from Terminal/VSCode:

  In the Project_Makefile directory you'll find a makefile you can use to build the project. Use the command make in the directory, and it will generate an executable file that you can run like this: ./CPPReviewBasics_out

  DO NOT CREATE YOUR OWN VISUAL STUDIO OR CODE::BLOCKS PROJECT.

  DO NOT REORGANIZE THE CODE.

  KEEP YOUR REPOSITORY DIRECTORY AND FILES CLEAN!!

  ---

• How the program and tests work
  

  (These are not steps to do yet, just background information on the program. Instructions continue below.)

  Once you run the program, you will see two options: Run the AUTOMATED TESTS or run the PROGRAMS manually.

  1. Run AUTOMATED TESTS
  2. Run PROGRAMS
  >>
  

  You can use the AUTOMATED TESTS to verify your work. Tests will either be marked as PASS or FAIL, and show the input passed in and the expected result:

  [FAIL]  TEST 1, StudentCode(AABC)
     EXPECTED OUTPUT: [3.25]
     ACTUAL OUTPUT:   [3.5]
  
  [PASS]  TEST 2, StudentCode(ABCCCDF) = 2.07143
  

  You can also MANUALLY RUN THE PROGRAMS to test them yourself:

  1. Run AUTOMATED TESTS
  2. Run PROGRAMS
  >> 2
  UNIT 02: C++ Basics Review -----------------------------------------------------
  
  Program 1: Pizza slices
  Program 2: Letter grade
  Program 3: Salary raise v1
  Program 4: GPA
  Program 5: Salary raise v2
  Program 6: Lyrics
  
  Run program #: 4
  Enter another letter grade (A, B, C, D, F) or X to stop: A
  Enter another letter grade (A, B, C, D, F) or X to stop: B
  Enter another letter grade (A, B, C, D, F) or X to stop: C
  Enter another letter grade (A, B, C, D, F) or X to stop: X
  Your GPA is: 3
  

  To begin with, the functionality won't work properly - you will need to implement the functions themselves. We will step through that in a moment.

  ---

• File: INFO.h
  

  This file contains a string constant. Replace "Your Name" with your actual name. This is to help me with grading.

  const std::string STUDENT_NAME = "Your Name";
  

  As you work through the coding assignments, if you have any questions or get stuck, feel free to ask for hints from the instructor.

  ---

• File: U02_P1_PizzaSlices.cpp
  

  This code file is under u02_Review_CPPBasics/P1_variables/U02_P1_PizzaSlices.cpp.

  PIZZA PARTY PLANNER
  How many guests will you have at your party? 20
  How many slices of pizza are available? 100
  Total guests: 20
  Total slices of pizza: 100
  Each guest gets 5 slices of pizza
  Each guest can have 5 slices of pizza
  

  You will be editing the function int U02_Program1_Function( int guest_count, int pizza_slices ) for this program.

  • Input parameters:
    1. guest_count, the amount of guests attending the party
    2. pizza_slices, the total amount of pizza slices at the party
  • Return output: The amount of slices of pizza each guest gets
  • Requirements: In this function, calculate the slices per person. You can add cout statements to display each piece of information, or you can also just do the calculation and return it at the end.
  • Math: Given \(s\) total slices and \(g\) total guests, slices per person \(p\) is \[p = \frac{s}{g}\].

  ---

• File: U02_P2_LetterGrade.cpp
  

  This code file is under u02_Review_CPPBasics/P2_branching/U02_P2_LetterGrade.cpp.

  LETTER GRADE PROGRAM
  How many points was the assignment worth? 75
  How many points did you score? 65
  
  GRADE INFORMATION
  My score ......... 75
  Points possible ...65
  Grade % ...........115.385
  Letter grade ......A
  
  Letter grade result: A
  

  You will be editing the function char U02_Program2_Function( float points_possible, float my_score ) for this program.

  • Input parameters:
    1. points_possible, the amount of total points an assignment is worth
    2. my_score, the amount of points the student earned on the assignment
  • Return output: The letter grade they received on the assignment
  • Requirements: Calculate the percent result the student earned on the assignment
  • Math: Given \(p\) points possible and \(s\) score earned, the percentage grade the student earned \(g\) is: \[ g = \frac{s}{p} \cdot 100 \]

  Letter grade: Use the following criteria to decide which grade the student receives.

  Letter	Range
  'A'	89.5% and above
  'B'	79.5% - 89.5%
  'C'	69.5% - 79.5%
  'D'	59.5% - 69.5%
  'F'	Below 59.5%

  ---

• File: U02_P3_SalaryRaise.cpp
  

  This code file is under u02_Review_CPPBasics/P3_looping/U02_P3_SalaryRaise.cpp.

  SALARY RAISE PROGRAM v2
  What is your starting salary? $60000
  What is the raise you get per year? %2
  How many years to calculate? 10
  Starting salary: $60000.00
  Year: 1, Salary: $61200.00
  Year: 2, Salary: $62424.00
  Year: 3, Salary: $63672.48
  Year: 4, Salary: $64945.93
  Year: 5, Salary: $66244.85
  Year: 6, Salary: $67569.75
  Year: 7, Salary: $68921.15
  Year: 8, Salary: $70299.57
  Year: 9, Salary: $71705.56
  Year: 10, Salary: $73139.67
  Salary after 10 years: $73139.67
  

  You will be editing the function float U02_Program3_Function( float starting_salary, float raise_per_year, int years ) for this program.

  • Input parameters:
    1. starting_salary, the salary the user starts out with
    2. raise_per_year the decimal value of the raise per year (e.g., 0.05 instead of 5%)
    3. years, how many years of raises they want to calculate
  • Return output: The salary after years amount of years.
  • Requirements: Use a loop to calculate and display the updated salary each year.
  • Math: Given the last year's salary \(s\) and the decimal raise per year \(d\), the updated salary for the year \(u\) is: \[ u = s + sd \]

  ---

• File: U02_P4_GPA.cpp
  

  This code file is under u02_Review_CPPBasics/P4_vector/U02_P4_GPA.cpp.

  Enter another letter grade (A, B, C, D, F) or X to stop: A
  Enter another letter grade (A, B, C, D, F) or X to stop: A
  Enter another letter grade (A, B, C, D, F) or X to stop: B
  Enter another letter grade (A, B, C, D, F) or X to stop: C
  Enter another letter grade (A, B, C, D, F) or X to stop: X
  Your GPA is: 3.25
  

  You will be editing the function float U02_Program4_Function( std::vector<char> course_grades ) for this program.

  • Input parameters:
    1. course_grades, a vector of letter grades
  • Return output: The GPA the student received
  • Requirements: Calculate the decimal equivalent of each letter grade, then use that to calculate the GPA.
  • Math: Given \(n\) total decimal scores \(s_1\), \(s_2\), …, \(s_n\), the GPA is: \[ \frac{ s_1 + s_2 + ... + s_n }{ n } \]

  Letter	Decimal equivalent
  'A'	4.0
  'B'	3.0
  'C'	2.0
  'D'	1.0
  'F'	0.0

  ---

• File: U02_P5_SalaryRaise.cpp
  

  This code file is under u02_Review_CPPBasics/P5_ofstream/U02_P5_SalaryRaise.cpp.

  SALARY RAISE PROGRAM v2
  What is your starting salary? $40000
  What is the raise you get per year? %5
  How many years to calculate? 5
  Salary after 5 years: $51051.26
  Result saved to results.txt
  

  Saved file example:

  Starting salary: $40000
  Year: 1, Salary: $42000
  Year: 2, Salary: $44100
  Year: 3, Salary: $46305
  Year: 4, Salary: $48620.2
  Year: 5, Salary: $51051.3
  

  You will be editing the function float U02_Program5_Function( float starting_salary, float raise_per_year, int years ) for this program.

  • Input parameters:
    1. starting_salary, the salary the user starts out with
    2. raise_per_year the decimal value of the raise per year (e.g., 0.05 instead of 5%)
    3. years, how many years of raises they want to calculate
  • Return output: The salary after years amount of years.
  • Requirements: Besides calculating the updated salary, create an ofstream output file and store the following data to the text file:
    • The starting salary
    • In the loop, each year and the updated salary.

  ---

• File: U02_P6_Lyrics.cpp
  

  This code file is under u02_Review_CPPBasics/P6_ifstream/U02_P6_Lyrics.cpp.

  Get which line # from test2.txt? 1
  Text at that line: we can leave your friends behind
  

  Example input file:

  we can dance if we want to
  we can leave your friends behind
  cuz your friends don't dance
  and if they don't dance
  well then they're no friends of mine.
  

  You will be editing the function std::string U02_Program6_Function( std::string filename, int line_number ) for this program.

  • Input parameters:
    1. filename, the file of lyrics to open
    2. line_number, which line # of the song to display
  • Return output: The lyric at the given line_number
  • Requirements: Use an ifstream object to open the filename given. Read each line of the input file until you hit the correct line number, return the string read in at that line number.
    • Error check: If opening the file fails, then display an error message and return an empty string, "".
    • Default: If the loop completes and we haven't hit the line_number requested (i.e., the file is fewer than that many lines), then return an empty string. "".

  File input hints:

  You can read one line of the file at a time with the getline function:

  // input is our ifstream object
  // buffer is a string, each line of the file is stored in it
  while ( getline( input, buffer ) )
  {
    // Do something with buffer
  }
  

  ---

• Turning in the assignment
  

  Once you're done with the assignment, you need to add, commit, and push your changes to the server.

  

  Save your changes to the server:

  1. Open git bash from within your repository folder on your harddrive.
  2. Use git status to review what files have changed since your last commit.
  3. Use git add . to add all changed files to a changeset.
  4. Use git commit -m "MESSAGE" to create a snapshot of your current changes. (Replace "MESSAGE" with something more descriptive.)
  5. Use git push -u origin u02_review to push all your commits to the GitLab server, on the u02_review branch.

  You can continue making changes and do additional add, commit, and push commands as well.

  Get everything ready for next assignment:

  1. Use git checkout main to change back to the main branch to prepare for the next assignment. (You can always use git checkout u02_review to return to this branch and code.)
  2. Use git pull to pull latest from the server. (This might happen if the instructor adds new starter code or makes modifications.)

  

  Create a Merge Request on the GitLab website:

  After pushing your changes to your branch, the GitLab webpage will show an update:

  

  Click the blue "Create merge request" button.

  

  Give your Merge Request a descriptive name, such as the unit the assignment belongs to.

  At the bottom of the page, click on the blue "Create merge request" button.

  

  Your merge request will now be created. You don't need to do anything further on this page.

  • Approve button: The instructor may mark the merge request as approved.
  • Merge button: You won't be able to press the Merge button; the instructor will merge the code once they've reviewed your work and approved it.

  Turn in the Merge Request URL on Canvas:

  Once you've created a merge request, copy the URL of the merge request on the GitLab.com webpage:

  

  Back on the Canvas page, locate the assignment and click the link:

  

  Then click on "Start Assignment":

  

  Paste in the URL to your Merge Request in the "Website URL:" textbox, then click "Submit Assignment" to finish the turn in.

  

🧠 Tech Literacy - Command Line programs (U02.TEC)

• A brief history of interfacing with computers
  

  Early computers were a shared resource, with one mainframe computer shared by many people at a university, business, or elseware. People often wrote programs on paper punchcards using dedicated hardware separate from the computer itself. (See: 1964 IBM 029 Keypunch Card Punching Demonstration (CuriousMarc))

  

  Figure 2: By Pete Birkinshaw from Manchester, UK - Used Punchcard, CC BY 2.0,

  Similarly, early computers didn't necessarily utilize video screens or monitors for output. Since the computer was shared, you might drop off your batch of cards for your program and come back later for the result output. If you think about it, a paper-based printout was probably the most cost-effective way for this. (See: YouTube: The IBM 1401 Mainframe Computer Wishes you a Merry Christmas (CuriousMarc) - Feeding a mainframe punchcards and getting printed output)

  Even when video monitors were available for these mainframe computers, the computers were still a shared resource being used by multiple people sharing computer time. In cases like these, users would work at a terminal. These look like what we think of as computers, with a video display and a keyboard, but they don't do any processing on their own. These terminals were connected to the mainframe computer, allowing users in other locations to interact with it via a simple text interface.

  

  Figure 3: By IBM - https://digitaltmuseum.no/011015240147/22-0-ibm-modell-360-370, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=113477774

  Even as Personal Computers began taking root in households in the 1980s, only rudimentary graphics were available (if any), such as drawing large blocks with some basic colors, or drawing pixels at specific positions on a low resolution screen. For daily use, typed commands were still largely how people interacted with the operating system of their computer, and for many of their programs as well.

  

  Figure 4: A photo of a Vic-20 BASIC program displayed on a CRT television.

  If a program did offer some kind of graphical user interface, at the time there were no standards and programs by different developers would often have wildly different interfaces, keyboard shortcuts, and styles.

• Who uses command line programs these days?
  

  In a way, there are still challenges around different types of interfaces. We have computers running different operating systems like Windows, Mac OS, Linux, and Unix, we have smartphones running their own operating systems as well. Beyond that, people might install different types of software or configure their personal computers differently. Under the surface, however, there is still some form of command line, though the commands may differ between a Windows PowerShell and a Linux/UNIX Bash system. So, what do these non-GUIs offer in utility?

  Consistency

  Sometimes I try to help out a person on a Mac computer, though I have almost no experience with that operating system. Often, I find it more comfortable to navigate through the Mac Terminal to utilize the UNIX-like commands that are in common with Linux - such as ls to list files and folders in a directory. Rather than have to learn a GUI for a system I'll never use on my own, I can interact with it with a "common tongue" - the command line. :)

  Scriptability

  Think of the effort it takes to automate doing anything with a GUI - you'll need some kind of program or library that allows moving the mouse to some (x,y) position, hit mouse clicks, type keys, etc. And even then, windows in a GUI might move around. It's much easier to write a program script to automate running commands from a command line instead - it's just text commands!

  Speed

  Command lines generally can be more responsive than a GUI. I find that even on computers that aren't too old, Windows slogs along. Command lines don't necessarily use your computer's graphics card to make the windows semi-transparent and animate when they perform some operation. And in some cases it can be faster to type something like mkdir cs200 cs235 cs250 to create three folders than to go through the steps to move mouse to "File", move mouse to "New Folder", click, type "cs200", repeat twice more.

  Portability

  Being able to navigate a command line also makes it much easier to access remote computers. While you can run a computer remotely and work with the graphical operating system, it's still usually pretty sluggish. Instead, you could SSH into a computer and work with it from the command line and quickly perform some operations that you need, which could be remotely launching a build, restarting a server, or even writing some notes.

  Most average computer users aren't using the command line in their personal lives, but it is still a hugely useful tool for people who work in IT and software. With IT, imagine you have to configure 20 computers per classroom, for all the classrooms in a building - would it be easier to manually go configure those computers from their GUIs, or to write a script and run that script on each computer?

• Why Computer Science courses don't (usually) teach GUI creation
  

  GUI libraries change over time

  Java and C# have both gone through various different systems for creating GUIs, such as WPF for old Windows programs, Swing for Java-based programs. But eventually they go out of date and stop being used.

  C++ isn't "owned" by a company like Microsoft or Oracle

  so there's no company to package some kind of UI library as the de-facto standard for C++ GUI development. There are open source tools (wxWidgets, Qt) and proprietary tools, but who knows what any given company uses for their software - if they even write desktop software at all anymore, anyway. Most things are HTML/CSS/JS based now. :)

  The study of Computer Science is more about how computers work rather than the design of front-ends.

  Adding a GUI layer on top of learning core C++ or about data structures can make the course content less focused and make it hard to understand the important parts on its own.

• Command line programs on your own computer
  

  If you're on Windows open up the PowerShell. If you're on Mac open up the Terminal. If you're on Linux open up your favorite Terminal emulator or whatever. :) Let's look at some basic programs that might be useful.

  • ping URL - The ping program allows us to send multiple packets to some URL. I usually just use this to see if my internet has gone down or if a site is just down. I still, by habit, use ping yahoo.com even though I haven't used Yahoo in years. (FYI: Use CTRL+C to end a command line program if it continues looping.)

  rachelwil@rachelwil-GF63-Thin-9SC:~$ ping yahoo.com
  PING yahoo.com (98.137.11.163) 56(84) bytes of data.
  64 bytes from media-router-fp74.prod.media.vip.gq1.yahoo.com (98.137.11.163): icmp_seq=1 ttl=49 time=60.6 ms
  64 bytes from media-router-fp74.prod.media.vip.gq1.yahoo.com (98.137.11.163): icmp_seq=2 ttl=49 time=63.1 ms
  64 bytes from media-router-fp74.prod.media.vip.gq1.yahoo.com (98.137.11.163): icmp_seq=3 ttl=49 time=85.4 ms
  64 bytes from media-router-fp74.prod.media.vip.gq1.yahoo.com (98.137.11.163): icmp_seq=4 ttl=49 time=69.7 ms
  ^C
  --- yahoo.com ping statistics ---
  4 packets transmitted, 4 received, 0% packet loss, time 3004ms
  

  • mkdir FOLDER1 FOLDER2 FOLDER3 - The mkdir (make-directory) program allows you to create 1 or more folders within the directory that you're currently in.
  • ls - The ls (list) program shows you all the files and folders in the directory that you're currently in.
  • pwd - The pwd (present working directory) program shows you the path of the directory that you're currently in.

  rachelwil@rachelwil-GF63-Thin-9SC:~/test-folder$ mkdir folderA folderB folderC
  
  rachelwil@rachelwil-GF63-Thin-9SC:~/test-folder$ ls
  folderA  folderB  folderC
  
  rachelwil@rachelwil-GF63-Thin-9SC:~/test-folder$ pwd
  /home/rachelwil/test-folder
  

  Commands that you can use from the terminal can also be called from C++ by using the system() function.

• See also
  
  • YouTube: Tomorrow's World: Home Computer Terminal 20 September 1967 (BBC) - Using a teletype terminal to communicate with a remote computer
  • YouTube: What are Dumb Terminals? (The 8-Bit Guy)

😺 Unit 00/01/02 Status Update - Welcome, Setup, Exploring Data, CS 200 Basics Review (U01.SUP)

📊 Presentation - CS 200 Review - Functions and classes (U03.PRES)

📖️ Reading - CS 200 Review - Functions and classes (U03.READ)

• Functions
  
  • Function headers
    

    A function header contains the following information:

    RETURNTYPE FUNCTIONNAME( PARAMETERLIST )

    • The return type is the type of data returned (like an int), or void for functions that don't need to return any data.
    • The function name follows the same naming rules as a variable - letters, numbers, and underscores allowed, no spaces or other special characters.
    • The parameter list is a series of variable declarations to be used within the function. These parameters are assigned values during the function call, when arguments are provided.

    ---

  • Function declarations
    

    Function declarations should go in .h files. A function declaration is the function header, with a semicolon at the end:

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

    ---

  • Function definitions
    

    Function definitions should go in .cpp files. A function definition is the function header, plus a code block, starting and ending with curly braces {}:

    int Sum( int a, int b )
    {
      int result = a + b;
      return result;
    }
    
    void DisplayMenu()
    {
      cout << "1. Add items" << endl;
      cout << "2. Subtract items" << endl;
      cout << "3. Quit" << endl;
    }
    

    ---

  • Function calls
    

    Function calls will happen within other functions. A function call includes the function's name, input arguments to be passed in, and the return data will need to be stored in a variable, if applicable.

    int main()
    {
      DisplayMenu(); // Function call
      int choice;
      cin >> choice;
    
      if ( choice == 1 )
      {
        int num1, num2, result;
        cout << "Enter num1: ";
        cin >> num1;
        cout << "Enter num2: ";
        cin >> num2;
    
        result = Sum( num1, num2 ); // Function call
        cout << "Result: " << result << endl;
      }
      // ... etc ...
    
      return 0;
    }
    

    ---

  • Header files
    

    Function declarations should go in header files (.h files).

    Header files must have file guards, this prevents the .h file from being "copied" into multiple files, which will cause a "duplicate code" build error.

    #ifndef _FILENAME_H
    #define _FILENAME_H
    
    // Code goes here
    
    #endif
    

    For the file guard, a label like _FILENAME_H is used. This must be unique for each file!

    Visual Studio supports using #pragma once for .h files, but this is not cross platform, so you should use these preprocessor file guards!

    ---

  • Source files
    

    Function definitions should go in source files (.cpp files).

    File guards are not needed in .cpp files.

    ---

  • Using your functions in other files
    

    Any file that utilizes your function must include the .h file:

    #include "MyFunctions.h"
    

    Note that something like #include <iostream> is used for including libraries that are not inside the project. Using "" is for including files that are in your project.

    NEVER INCLUDE .cpp FILES, THIS WILL GENERATE ERRORS!

    ---

  • Function overloading
    

    Multiple functions can have the same name as long as their function signatures are different. This means that two functions with the same name either need a different number of parameters, or different parameter data types, so that they can be unambiguously identified.

    AMBIGUOUS:

    void MyFunction( int a, int b );
    
    void MyFunction( int num1, int num2 );
    

    UNAMBIGUOUS:

    void MyFunction( int num1, int num2 );
    
    void MyFunction( string name1, string name2 );
    
    void MyFunction( int oneNum );
    

    ---

• Structs and classes
  
  • Accessibility levels
    

    We can specify accessibility levels for struct and class members. This information dictates where a struct/class' internal contents can be accessed from:

    Accessibility level	Class' functions?	Child's functions?	External functions?
    private	✅	❌	❌
    protected	✅	✅	❌
    public	✅	✅	✅

    • private members can only be accessed from the class' own functions.
    • protected members can only be accessed from the class' own functions, and also the functions of any other classes that INHERIT from this class.
    • public members can be accessed from anywhere in the program, including functions that are not a part of the class.
  • Structs
    

    Structs are usually used to store very basic structures, often with just variable data and no functions.

    struct Coordinate
    {
      float x, y;
    };
    

    Struct declarations should go in their own .h file, usually the filename will match the name of the class, such as "Coordinate.h".

    All .h files need file guards!

    Also note that at the closing curly brace } of the struct declaration there is a semicolon - this is required!

    Members of a struct are public level accessibility by default.

    ---

  • Classes
    

    Classes are meant for more complex structures.

    class CLASSNAME
    {
        public:
        // Public members
    
        protected:
        // Protected members
    
        private:
        // Private members
    };
    

    Class declarations should go in their own .h file, and class function definitions should go in a corresponding .cpp file!

    It is best practice to make member variables of a class private, and only provide indirect access to this data via functions.

    Example: Product.h

    #ifndef _PRODUCT_H  // File guards
    #define _PRODUCT_H  // File guards
    
    #include <string>
    using namespace std;
    
    class Product
    {
        public:
        // Constructors:
        Product();
        Product( string newName, float newPrice );
    
        // Destructor:
        ~Product();
    
        // Setters:
        void SetName( string newName );
        void SetPrice( float newPrice );
    
        // Getters:
        string GetName() const;
        float GetPrice() const;
    
        private:
        string m_name;
        float m_price;
    }
    
    #endif
    

    Example: Product.cpp

    #include "Product.h"
    
    // Constructors:
    Product::Product()
    {
      m_name = "unset";
      m_price = 0;
    }
    
    Product::Product( string newName, float newPrice )
    {
      SetName( newName );
      SetPrice( newPrice );
    }
    
    // Destructor:
    Product::~Product()
    {
      cout << "Bye." << endl;
    }
    
    // Setters:
    void Product::SetName( string newName )
    {
      m_name = newName;
    }
    
    void Product::SetPrice( float newPrice )
    {
      if ( newPrice >= 0 )
      {
        m_price = newPrice;
      }
    }
    
    // Getters:
    string Product::GetName() const
    {
      return m_name;
    }
    
    float Product::GetPrice() const
    {
      return m_price;
    }
    

    Accessor/Getter functions:

    • Don't take in any input data (no parameters).
    • Return the value of a private member variable (has a return).
    • Should be marked const to prevent data from changing within the function. (This is "read only")

    Mutator/Setter functions:

    • Take in an input value of the new data to be stored (has a parameter).
    • Generally doesn't return any data (no return, void return type).

    Constructor functions:

    • Called automatically when a new object of that class type is created.
    • Can overload.

    Destructor functions:

    • Called automatically when an object of that class type is destroyed/loses scope.
    • Cannot overload.

    ---

  • Class objects / instantiating a class object
    

    Once we've declared a class we can then declare variables whose data types are that class:

    PlayerCharacter bario;
    NonPlayerCharacter boomba;
    

    In this example, bario is a PlayerCharacter object, aka an "instantiation of the PlayerCharacter object".

    ---

  • Class inheritance
    

    A class (called a subclass or a child class) can inherit from another class (called a superclass or a parent class). Doing this means that any protected and public members are inherited by the child class. This can be useful for creating more "specialized" versions of something, storing the shared attributes of a set of items in a common "parent" class.

    Example:

    class Character
    {
      void SetPosition( float x, float y );
      void Move( float xAmount, float yAmount );
    
      protected:
      float x, y;
    };
    
    class PlayerCharacter : Public Character
    {
      public:
      void GetKeyboardInput();
    
      private:
      int totalLives;
    };
    
    class NonPlayerCharacter : public Character
    {
      public:
      void ComputerDecideMove();
    
      private:
      bool attackPlayer;
    };
    

    ---

  • Class composition
    

    Class composition is where a class contains class objects as member variables. This is another form of object oriented design where a class might "contain" traits that could be inherited, but instead encapsulates them into a sub-object.

    Example:

    class MovableObject
    {
      void SetPosition( float x, float y );
      void Move( float xAmount, float yAmount );
    
      private:
      float x, y;
    };
    
    class PlayerCharacter
    {
      public:
      void GetKeyboardInput();
    
      private:
      int totalLives;
      MovableObject mover;
    };
    

    ---

• Review questions:
  
  1. What is included in a function signature?
  2. Build the function signature given the following specs:
     • The function is naemd "GetValidInput".
     • The function returns an integer.
     • The function takes an int for the minimum valid value, and an int for the maximum valid value.
  3. #include <THING> is used for … ? and #include "THING" is used for … ?
  4. Best practice is to put file guards in every .h file you create. (true/false)
  5. Arguments are … ? and Parameters are … ?
  6. What type of code goes in each type of file? (Function declaration/function definition) vs. (.cpp file/.h file)
  7. Class members are (private/protected/public) by default.

  8. What kind of member function is the following?

     void Pet::XYZ( int age )
     {
       m_age = age;
     }
     

  9. What kind of member function is the following?

     int Pet::XYZ()
     {
       return m_age;
     }
     

  10. This kind of class function will be called automatically when an object of that class type is instantiated…
  11. This kind of class function will be called automatically when an object of that class type is destroyed…

🔎 Concept Intro - CS 200 review: Functions and classes (U03.CIN)

🧑‍🔬 Lab - CS 200 Review - Functions and classes (U03.LAB)

• Set up: Creating a new branch in your repository
  

  

  First, Open up Git Bash (Windows) or your Terminal (Linux/Mac) from within your repository directory. Make sure you're inside the repository folder, which should be named something like YOURSSO-CLASS.

  Next, create a new branch in the repository with the checkout command: git checkout -b u03_review

  $ git checkout -b u03_review
  Switched to a new branch 'u03_review'
  

  

  Now your folder is on the new branch and you can start working on the assignment.

  ---

• Download the starter code
  

  Download the following starter code and unzip it to your repository folder.

  • shared/labs/starter-code/u03_Review_FuncClass.zip

  

  All starter files:

  .
  ├── INFO.h
  ├── main.cpp
  ├── Project_CodeBlocks
  │   ├── FunctionsClasses.cbp
  │   ├── FunctionsClasses.depend
  │   └── FunctionsClasses.layout
  ├── Project_Makefile
  │   └── Makefile
  ├── Project_VisualStudio
  │   ├── FunctionsAndClasses.sln
  │   ├── FunctionsAndClasses.vcxproj
  │   └── FunctionsAndClasses.vcxproj.filters
  ├── u03_Review_FuncClass
  │   ├── P1_functions
  │   │   └── U03_P1_Sale.cpp
  │   ├── P2_struct
  │   │   └── U03_P2_Room.cpp
  │   ├── P3_class
  │   │   └── U03_P3_Employee.cpp
  │   ├── U03_Headers.cpp
  │   └── U03_Headers.h
  └── Utilities
      ├── Colors.hpp
      ├── Helper.cpp
      └── Helper.hpp
  

  Visual Studio users:

  Open the Project_VisualStudio folder and open the FunctionsAndClasses.sln file to get started.

  Code::Blocks users:

  Open the Project_CodeBlocks folder and open the FunctionsClasses.cbp file to get started.

  Build from Terminal/VSCode:

  In the Project_Makefile directory you'll find a makefile you can use to build the project. Use the command make in the directory, and it will generate an executable file that you can run like this: ./CPPReviewClasses_out

  DO NOT CREATE YOUR OWN VISUAL STUDIO OR CODE::BLOCKS PROJECT.

  DO NOT REORGANIZE THE CODE.

  KEEP YOUR REPOSITORY DIRECTORY AND FILES CLEAN!!

  ---

• How the program and tests work
  

  Once you run the program, you will see two options: Run the AUTOMATED TESTS or run the PROGRAMS manually.

  1. Run AUTOMATED TESTS
  2. Run PROGRAMS
  >>
  

  You can use the AUTOMATED TESTS to verify your work. Tests will either be marked as PASS or FAIL.

  Note that the first "automated" test in the set requires user input once the program is implemented. The test text will describe what inputs it is expecting, the user can set those prices, and then use checkout to finish the test.

  You can also MANUALLY RUN THE PROGRAMS to test them yourself:

  EMPLOYEE LOOKUP
  INDEX     ID        NAME                          WAGE
  --------------------------------------------------------------------------------
  0         123       Ochoa                         16.65
  1         234       Bakalar                       16.65
  2         353       Grubb                         16.65
  
  Enter Employee ID to find index of: 234
  RESULT: Index = 1
  

  To begin with, the functionality won't work properly - you will need to implement the functions themselves. We will step through that in a moment.

  ---

• File: INFO.h
  

  This file contains a string constant. Replace "Your Name" with your actual name. This is to help me with grading.

  const std::string STUDENT_NAME = "Your Name";
  

  As you work through the coding assignments, if you have any questions or get stuck, feel free to ask for hints from the instructor.

  ---

• File: U03_P1_Sale.cpp
  

  This code file is under u03_Review_FuncClass/P1_functions/PizzaSlices.cpp.

  ########################################
  MAIN MENU
  
  Current transaction amount: $8.52
  1. Add item
  2. Checkout
  Enter a number between 1 and 2: 2
  
  
  ########################################
  RECEIPT
  
  Transaction total: $8.52
  Tax rate: %9.61
  After tax: $9.34
  RESULT: 9.34
  

  The U03_P1_Sale.cpp file contains several functions that you'll implement for this program.

  void DisplayMenu()

  • This function is responsible for showing the numbered menu, with 1 for "Add item" and 2 for "Checkout".
  • This function does not get any input! Just use cout statements here.

  ---

  void FormatUSD( float price )

  • This function takes in the price and formats it as USD. You can set up the precision like this first: std::cout << std::fixed << std::setprecision( 2 );
  • Afterwards, use cout to display "$" and then the price .

  ---

  float GetTaxPercent()

  • This function only returns the tax percent. Return a value of 9.61.

  ---

  float GetPricePlusTax( float original_price, float tax_percent )

  • Calculate the price plus tax given the inputs.
  • Math: Given original price \(o\) and tax percent \(t\), the new price \(p\) is: \(p = o + ( o \cdot t )\)

  ---

  float GetNewPrice()

  This function needs to ask theuser to enter the price of a new item. Use cout and cin statements here, and return the new price they entered afterwards.

  ---

  int GetChoice( int min, int max )

  • This function should ask the user to enter a number between min and max.
  • Get the user's input, then use a while loop to check for invalid input: While input is invalid, display an error and have the user enter their choice again.
    • Input is invalid if user_choice < min OR user_choice > max.
  • After the while loop we know the user's input is valid, so we return that value.

  ---

  float SaleProgram()

  1. Create a transaction_total float variable and initialize it to 0.
  2. Create a is_running boolean variable and initialize it to true.
  3. Create a program loop: while( is_running ). Within the loop, do the following:
     1. Display the current transaction_total, formatted as USD.
     2. Display the main menu (call the DisplayMenu function).
     3. Get the user's choice (call the GetChoice function, store result in an integer).
     4. Use if/else if statements or a switch statement to check the user's choice:
        • If their choice is 1, then call the GetNewPrice function. Store its result in a float variable, then add the result onto the transaction_total.
        • Otherwise if their choice is 2, then set is_running to false.
  4. After the program while loop, display the RECEIPT. This should include:
     • The transaction_total formatted as USD,
     • the tax rate,
     • the price after tax formatted as USD.
  5. Before the end of the function, return the final_price that was calculated.

  Note that your program output does not need to perfectly match mine. The important thing is the correct information, and readability.

  ########################################
  MAIN MENU
  
  Current transaction amount: $8.52
  1. Add item
  2. Checkout
  Enter a number between 1 and 2: 2
  
  ########################################
  RECEIPT
  
  Transaction total: $8.52
  Tax rate: %9.61
  After tax: $9.34
  RESULT: 9.34
  

  ---

  The "automated tests" for this one will require that you manually input information. It will tell you what inputs it is expecting, and then tell you if it passes or not.

  MANUAL TEST, check functionality:
   * DisplayMenu() - main menu shown in loop
   * FormatUSD( p ) - make sure dollar amounts are formatted
   * GetTaxPercent() - Make sure on checkout the tax % shows up
   * GetPricePlusTax( p, t ) - Make sure After Tax price is correct
   * GetChoice( min, max ) - Make sure it disallows numbers less than min / greater than max
   * GetNewPrice() - Make sure function is called to get float values
  --------------------------------------------------------------------------------
  
  Enter prices:     2.25, 4.00, 5.30    <<<<<<<<< This tells you what to enter
  Expected output: 12.66
  

  ---

• File: U03_P2_Room.cpp
  

  This code file is under u03_Review_FuncClass/P2_struct/U03_P2_Room.cpp.

  ROOM BUILDER
  Enter room length: 15
  Enter room width: 20
  RESULT:
   * width:     20
   * length:    15
   * area:      300
   * perimeter: 70
  

  Within this file, a Room struct has been declared:

  struct Room
  {
    float width;
    float length;
    float area;
    float perimeter;
  };
  

  You will need to implement two functions here:

  Room BuildRoom( float width, float length )

  float width	Input parameter	The width of a room
  float length	Input parameter	The length of a room
  Room	Return output	The built Room struct with all the data set up

  In this function, set the newRoom's member variables, utilizing the input parameters.

  • newRoom.width: Copy the input parameter width.
  • newRoom.length: Copy the input parameter length.
  • newRoom.area: Calculate the area (\(w \cdot l\))
  • newRoom.perimeter: Calculate the perimeter (\(2w + 2l\))

  Make sure the newRoom is being returned at the end of the function.

  ---

  void U03_Program2_Program()

  In this function ask the user to enter a room length and a room width. Store their inputs in float variables. Call the BuildRoom function, passing in the data, and storing the returned result in a new Room variable. Finally, use cout to display all of the Room's information.

  ---

  Afterwards, the automated tests will pass:

  [PASS]  TEST 1, StudentCode(5.00, 7.00) = [width=5.00, length=7.00, area=35.00, perimeter=24.00]
  [PASS]  TEST 2, StudentCode(3.00, 11.00) = [width=3.00, length=11.00, area=33.00, perimeter=28.00]
  

  ---

• File: U03_P3_Employee.cpp
  

  This code file is under u03_Review_FuncClass/P3_class/U03_P3_Employee.cpp.

  EMPLOYEE LOOKUP
  INDEX     ID        NAME                          WAGE
  --------------------------------------------------------------------------------
  0         123       Ochoa                         16.65
  1         234       Bakalar                       16.65
  2         353       Grubb                         16.65
  
  Enter Employee ID to find index of: 353
  RESULT: Index = 2
  

  This program has a list of employees, each with an employee_id, name, and hourly_wage. The user can enter in an employee_id in this program, and the associated array index will be returned.

  Within the file is a class Employee declaration and empty member functions. You will implement these and the basic GetEmployeeIndex search function.

  Note: I have all the class functions declared here inside the class declaration, for program simplicity. When implementing class functions, generally the class declaration goes in a .h file and the function definitions go in a .cpp file, and look like int Employee::GetId() const.

  Employee( int new_id, std::string new_name, float new_wage )

  This is the constructor function for the Employee class. Within this function, initialize each of the private member variables (employee_id, name, hourly_wage) to the values passed in as input parameters (new_id, etc.)

  ---

  int GetId() const

  Within this function return the value of the private member variable, employee_id.

  Note that this function is const, which means that changes to member variables are not permitted within.

  ---

  std::string GetName() const

  Within this function return the value of the private member variable, name.

  ---

  float GetWage() const

  Within this function return the value of the private member variable, hourly_wage.

  ---

  int GetEmployeeIndex( std::vector<Employee> employee_list, int lookup_id )

  std::vector<Employee> employee_list	Input parameter	The list of all employees to search through
  int lookup_id	Input parameter	The employee ID of the person we're looking for
  int	Return output	The associated index of the employee with the matching ID.

  • Within this function use a for loop to iterate over all the elements of the employee_list, using the index as the looping variable. Within the loop:
    • If the employee at this index's ID matches the lookup_id, then return the current index.
  • At the end of the function, after the for loop, if nothing has been returned yet that means there's no matches - return a -1 here.

  For the for loop:

  • Initialization: size_t index = 0
  • Condition: index < employee_list.size()
  • Update: index++

  To access a certain element of the array: employee_list[index] , then you can also call its functions: employee_list[index].GetId()

  ---

  Afterwards, the automated tests should pass:

  [PASS]  TEST 1, StudentCode([11/100/AAA],22/200/BBB],33/300/CCC],44/400/DDD]], 44) = 3
  [PASS]  TEST 2, StudentCode([100/11/aardvark],200/12/bear]], 200) = 1
  [PASS]  TEST 3, StudentCode([100/11/aardvark],200/12/bear]], 444) = -1
  

  ---

• Turning in the assignment
  

  Once you're done with the assignment, you need to add, commit, and push your changes to the server.

  

  Save your changes to the server:

  1. Open git bash from within your repository folder on your harddrive.
  2. Use git status to review what files have changed since your last commit.
  3. Use git add . to add all changed files to a changeset.
  4. Use git commit -m "MESSAGE" to create a snapshot of your current changes. (Replace "MESSAGE" with something more descriptive.)
  5. Use git push -u origin u03_review to push all your commits to the GitLab server, on the u03_review branch.

  You can continue making changes and do additional add, commit, and push commands as well.

  Get everything ready for next assignment:

  1. Use git checkout main to change back to the main branch to prepare for the next assignment. (You can always use git checkout u03_review to return to this branch and code.)
  2. Use git pull to pull latest from the server. (This might happen if the instructor adds new starter code or makes modifications.)

  

  Create a Merge Request on the GitLab website:

  After pushing your changes to your branch, the GitLab webpage will show an update:

  

  Click the blue "Create merge request" button.

  

  Give your Merge Request a descriptive name, such as the unit the assignment belongs to.

  At the bottom of the page, click on the blue "Create merge request" button.

  

  Your merge request will now be created. You don't need to do anything further on this page.

  • Approve button: The instructor may mark the merge request as approved.
  • Merge button: You won't be able to press the Merge button; the instructor will merge the code once they've reviewed your work and approved it.

  Turn in the Merge Request URL on Canvas:

  Once you've created a merge request, copy the URL of the merge request on the GitLab.com webpage:

  

  Back on the Canvas page, locate the assignment and click the link:

  

  Then click on "Start Assignment":

  

  Paste in the URL to your Merge Request in the "Website URL:" textbox, then click "Submit Assignment" to finish the turn in.

  

  "What happens if I make mistakes?"

  

  If you make mistakes, I will be able to mark certain lines of code in the merge request and add a comment as to what isn't correct, similar to how your coworkers would also review your code on the job.

  After receiving feedback, you can go back and make updates to your code and resubmit it. You will need to do the following:

  1. Check out the branch you made the changes on: git checkout BRANCHNAME
  2. Make the fixes to the code.
  3. Make a new add/commit/push:
     1. git add .
     2. git commit -m "MESSAGE"
     3. git push -u origin BRANCHNAME
  4. The merge request automatically gets updated; re-submit the merge request link in Canvas to mark it as ready to be re-graded.

🏋️ Exercise - Debugging functions and classes (U03.EXE)

📊 Presentation - Debugging and testing (U04.PRES)

📖️ Reading - Debugging and testing (U04.READ)

• Testing: Validating your work
  

  How do you know that your program actually works?

  Sure, you may have manually tested your code, running the program and typing in test data and checking the output.

  After a while, manual testing becomes a chore. Maybe you start entering "asdjhfklq" as the test data and just make sure nothing breaks while running the program.

  But are you sure your program runs, doesn't crash, and gives the correct output for all reasonable cases?

  

  A skill that is good to develop as a software developer is how to test and validate your work. You can break down parts of your code into little transactions of "inputs" and "outputs", and then develop test cases.

  Test case: A test case is a single test. You specify some input(s) that you will give your program, and the expected output(s) it should return.

  When you run the actual program with your inputs, it will return actual output(s). Compare the actual output with the expected output to validate whether the program worked as expected.

  Test cases can be built without any of the program built so far. In fact, it can be handy to write your tests ahead of time so you have a better understanding of how things are supposed to work.

  Example: Bank withdrawals In this example, the program keeps track of a bank balance and the amount the user wants to withdraw, but it shouldn't let the balance fall below 0.

  Test case	Input(s)	Expected output	Actual output
  1	balance = 100, withdraw = 10	balance is now 90	(enter after testing)
  2	balance = 0, withdraw = 100	can't withdraw!
  3	balance = 100, withdraw = 100	balance is now 0

  You would make a list of inputs and what should be the result for each case, and then run your program and check each scenario. If something doesn't match, it could mean that there's an error in a calculation somewhere, or other logic in the program. (And yes, sometimes tests can be wrong, too.)

  ---

  • The role of testing in software development
    

    Companies that write big software products will often have multiple types of testing that they do to ensure the validity of their software.

    QA (Quality Assurance) people generally will be responsible for writing test cases and running through *manual tests to validate the software works as intended. They might also write test scripts that automate going through the UI of the software, or automate other parts of testing.

    Software Engineers will regularly need to be able to write unit tests along with whatever features they're working on in order to validate that their new feature works as intended and they will run older unit tests to ensure that their new feature doesn't break anything already there.

    Testing is an important part of software development and, from a student perspective, it is also a handy tool in ensuring that your programming projects work as intended before turning them in.

    ---

  • Designing tests
    
  • Test cases
    

    When writing out test cases, it's important to try to think of valid inputs and invalid inputs that could be entered in, and account for how the program will respond to that input.

    There are three main pieces to defining a test case:

    1. Inputs entered in.
    2. What the expected output of the program is.
    3. What the program actually did.

    By comparing the expected result with the actual result, you can validate whether your program is working as intended. If they match - the test passes. If they don't match - the test failed.

    If a test fails, you can investigate the expected output and the actual output to help you get an idea of perhaps where it went wrong - perhaps a formula is wrong somewhere.

    

    Example: Calculate price plus tax When ringing up a product at a store, there will be a price for that product and a sales tax that gets added onto it. Using a test case can help us make sure that the program's calculations are correct.

    Let's say that the programmer implemented the formula like this: total = price + tax

    We could validate the program's actual output vs. the expected output, and see that there's an error.

    Test case	Input(s)	Expected output	Actual output
    1	price = $10.00, tax = 0.09	total = $10.90	total = $10.09 (FAIL)
    2	price = $5.45, tax = 0.06	total = $5.78	total = $5.51 (FAIL)
    3	price = $2.25, tax = 0.095	total = $2.46	total = $2.35 (FAIL)

    What is the problem with the formula? Well, we don't just add tax as a flat number; "0.09" is supposed to represent 9%, not 9 cents!

    The correct formula would be: total = price + (price * tax)

    ---

  • Manual testing
    

    

    You can manually test your program effectively by documenting your test cases and running through each of them each time you decide to test your program. Of course it can take a while, but by using your test cases instead of entering in gibberish or only testing one scenario, you make sure your program works, even as you keep adding onto it.

    ---

  • Automated unit tests
    

    

    Our test cases can be a handy roadmap to follow when running through your program's various features and validating it all works manually, but you can speed up the process by letting the computer do these checks for you.

    After all, when you manually validate outputs yourself, you're basically asking yourself,

    "If the actual output DOES NOT match the expected output, then the test failed."

    A test that only validates one function is known as a unit test, testing the smallest possible unit of a program. You could also write automated tests that checks several functions, but unit tests are good to validate each function on its own, independently of the rest.

    • Unit tests in the real world
      

      "Tests just mean more code to maintain. We don't keep tests."

      I was told this at a job interview once. I didn't take the job.

      At companies that maintain tests, the software engineers will usually write unit tests to validate their work as they're adding in new functionality or making modifications to the existing code.

      This means that ideally each feature of the program has one or more test to validate that it works.

      This also means that, when adding or modifying features, you can run the entire test suite to make sure that all features still work.

      Many software companies have something called Continuous Integration (CI), which is an automated system that kicks off a build of the software and runs all the tests each time a developer commits code to the repository.

      Example: Area function Let's say we have a function with the header

      int Area( int width, int length )

      and we don't necessarily know what's in it (we don't need that to test). We can write a series of test cases with inputs we specify and outputs we know to be correct in order to check the logic of the Area function…

      Test case	Input(s)	Expected output	Actual output
      1	width = 10, length = 20	120
      2	width = 2, length = 5	10

      …and so on.

      We could use this to manually test by calling Area and checking the output it gives you, but you could also write a function to validate it for us…

      

      Here's some example code of a function that tests Area() for us.

      void Test_Area()
      {
        // Variables used for each test
        int width, length;
        int expectedOutput;
        int actualOutput;
      
        // Test 1
        width = 10;
        length = 20;
        expectedOutput = 200;
        actualOutput = Area( width, length );
      
        if ( actualOutput != expectedOutput ) {
          cout << "Test failed!"
               << "\n width: " << width
               << "\n length: " << length
               << "\n expected output: " << expectedOutput
               << "\n actual output: " << actualOutput 
               << endl;
        }
        else {
          cout << "Test 1 passed" << endl;
        }
      }
      

      You can add as many tests as you'd like inside one function, testing different permutations of inputs against outputs to make sure that any reasonable scenarios are covered. To test, just call the function in your program, and check the output:

      Test failed!
      width: 10
      length: 20
      expected output: 200
      actual output: 30
      

      If the test fails, you can cout your variables' values to help you figure out what might be wrong with the logic.

    • Other automated tests
      

      Unit tests test the smallest unit of code - a single function.

      (It should be the smallest "unit", if your function is really long you should probably split it up!)

      There are other types of automated tests as well, and software tools to help developers create and run those tests.

      An integration test is when you test multiple units together. A unit might work fine on its own, but when multiple units are put together, the resulting system may not work as intended.

      (Look up "integration test unit test" online for some good gif examples. :))

      

      Tests can also be written to test user interfaces of a program, running a script to drive the cursor around the screen, or defining text that should be typed into fields, running through features of the program from the user's perspective, and validating that data updates and is displayed when some action is performed from the UI.

      ---

• Using debugging tools
  

  

  Utilizing debugging tools are an important part of software development. Especially as you begin working in large codebases on the job, being able to step through the execution of a program to find variable values, how the program flows, and where exceptions are thrown is something you will have to do frequently.

  The lab contains more of the steps for learning these tools with your IDE, but here is some general information for now.

  ---

  Breakpoints

  

  A breakpoint can be toggled in your code by clicking to the left of the code screen. The exact placement differs between IDEs, but usually a red circle pops up once clicked to show that the program execution will stop here once we reach it.

  You can set breakpoints in your program at various places to begin stepping through to see where the program goes, if it's "flowing" the way you expect it to, and to navigate into other function calls as they're hit.

  

  The "next line" or "step over" button will let you move to the next line of code execution. If your pause line is at a function call, it will not enter the function, and just continue on the next line after the function call is done.

  

  The "step into" button will take you to inside a function if you're currently paused on a line that is a function call.

  ---

  Watch/Local/Auto window

  

  Watch, Local, and Auto windows do similar things - they all display a variable's name and its current value (while paused in the program execution).

  Visual Studio has (and other IDEs may have) an auto view, which shows variables that are around the current statement we're paused on. The locals view shows variables that are currently in scope. (Information from https://learn.microsoft.com/en-us/visualstudio/debugger/autos-and-locals-windows?view=vs-2022)

  ---

  Call stack

  

  The call stack will show you all the functions that have been called, leading up until the point where you are currently paused at. The current function is listed on the top, with the function immediately below it being the one that made the call to the function you're in. The function listed at the bottom is the "oldest" function, or the first one called, usually main().

  ---

• Review questions:
  
  1. Given some input and expected output defined, a test would pass if…
  2. Let's say I've written a program that takes in two numbers as inputs and returns the sum as the output. For our first test case, let's say the inputs are 2 and 3. What would the expected output be?
  3. Let's say you need to write a program that will update a person's account balance after they deposit some money. What might be the input(s) / output(s)?
  4. Let's say your program is crashing somewhere. How might setting breakpoints be useful?

  5. We are paused in a program at this point:

     int a = 10;
     int b = 20;
     int result = Sum( a, b ); << Break here
     cout << result << endl;
     

     If we hit the step over button, what will the next line the debugger is paused at be?

  6. We are paused in a program at this point:

     int a = 10;
     int b = 20;
     int result = Sum( a, b ); << Break here
     cout << result << endl;
     

     If we hit the step into button, what will the next line the debugger is paused at be?

  7. Given the following call stack:

     Product::GetPrice()

     Store::PurchaseProduct()

     Store::MainMenu()

     main()

     What function are we currently paused in?

  8. Given the following call stack:

     Product::GetPrice()

     Store::PurchaseProduct()

     Store::MainMenu()

     main()

     Once the current function returns, which function will then be at the top of the call stack?

.🔎 Concept Intro - Debugging and testing (U04.CIN)

🧑‍🔬 Lab - Debugging and testing (U04.LAB)

• Set up: Creating a new branch in your repository
  
  1. Navigate to your class repository folder. Right-click the empty space and select GitBash Here (Windows). (Other platforms: Open this directory in your Terminal.)
  2. Create a new branch: git checkout -b u04_debugtest

  ---

• Download the starter code
  

  Download the following starter code and unzip it to your repository folder.

  • shared/labs/starter-code/u04_DebuggingAndTesting.zip

  All starter files:

  .
  ├── Part1_Debug
  │   ├── engine
  │   │   ├── Helper.cpp
  │   │   ├── Helper.h
  │   │   ├── Log.cpp
  │   │   ├── Log.h
  │   │   ├── PpmImage.cpp
  │   │   ├── PpmImage.h
  │   │   ├── ScreenDrawer.cpp
  │   │   └── ScreenDrawer.h
  │   ├── Game.cpp
  │   ├── Game.h
  │   ├── images
  │   │   ├── food.ppm
  │   │   ├── kansascity.ppm
  │   │   ├── medical.ppm
  │   │   ├── olathe.ppm
  │   │   ├── overlandpark.ppm
  │   │   ├── raytown.ppm
  │   │   ├── safehouse.ppm
  │   │   ├── scavenger.ppm
  │   │   ├── zombie1.ppm
  │   │   └── zombie2.ppm
  │   ├── main.cpp
  │   ├── Player.cpp
  │   ├── Player.h
  │   ├── Project_CodeBlocks
  │   │   ├── log.txt
  │   │   ├── ZombieApoc.cbp
  │   │   ├── ZombieApoc.depend
  │   │   └── ZombieApoc.layout
  │   ├── Project_Makefile
  │   │   └── Makefile
  │   └── Project_VisualStudio
  │       ├── log.txt
  │       ├── ZombieApoc.sln
  │       ├── ZombieApoc.vcxproj
  │       └── ZombieApoc.vcxproj.filters
  └── Part2_Test
      ├── Functions.cpp
      ├── Functions.h
      ├── Project_CodeBlocks
      │   ├── WritingTests.cbp
      │   ├── WritingTests.depend
      │   └── WritingTests.layout
      ├── Project_Makefile
      │   └── Makefile
      └── Project_VisualStudio
          ├── WritingTests.sln
          ├── WritingTests.vcxproj
          └── WritingTests.vcxproj.filters
  

  • Please use the provided Visual Studio or Code::Blocks project files, don't make your own!
  • If you want to build the code from the terminal, go to the Project_Makefile directory and use the command make to generate an out file.

  DO NOT CREATE YOUR OWN VISUAL STUDIO OR CODE::BLOCKS PROJECT.

  DO NOT REORGANIZE THE CODE.

  KEEP YOUR REPOSITORY DIRECTORY AND FILES CLEAN!!

  ---

• Part 1: Debug
  

  For this assignment you'll run an existing program. You don't need to do any programming - you will be utilizing the debugging tools of your IDE to answer the questions. You will need to create a text document (a MS Word / LibreOffice Write / Google Docs document).

  ---

  • Running the game as-is - Learning the controls
    

    

    Run the game as-is and play a few rounds of it. You can choose to scavenge in the area you're currently at, or travel to another location. For this step, you're just getting used to how the game controls.

    ---

  • Using breakpoints - Pause program execution at some line
    

    Task:

    1. Set breakpoints at the start of Player::Player() in Player.cpp, and at the start of Game::Game() in Game.cpp.
    2. In the watch window, add the following (for the Player class):
       1. food
       2. maxHealth
       3. health
       4. location
    3. In the watch windwo, add the following (for the Game class):
       1. m_done
       2. m_day

    Observe the current values of those variables. Refer to the following documentation on the steps to do this.

    Video: https://youtu.be/BNaTN9KWmu4

    • Setting the breakpoint:
      

      Step 1: Set a breakpoint at the start of Player::Player():

      Player::Player()
      {
          food = 5;
      

      Set a breakpoint at the start of Game::Game():

      Game::Game()
      {
          m_day = 1;
      

      To set a breakpoint, you can locate a line of code and click on a region in your editor next to the line number that will enable a breakpoint. A breakpoint is a debugging tool that will cause the program execution to pause when that line of code is reached. While the program is paused, you can investigate values and step through the program flow one line at a time.

      

      Depending on your IDE you might need to click before or after the line number to set the breakpoint. You can also toggle breakpoints through the menu or keyboard shortcuts:

      IDE	Menu	Shortcut	Image
      Visual Studio	Debug, Toggle breakpoint	F9
      Code::Blocks	Debug, Toggle breakpoint	F5
      XCode

      Next you'll need to run your program in debug mode:

      IDE	Toolbar	Menu	Shortcut
      Visual Studio			F5
      Code::Blocks			F8
      XCode

      The program will build (if it hasn't already) and start running the program. When the program starts, it will hit the breakpoint and pause execution. Go back to your IDE to view where your program has paused.

    • Opening the variable investigation panes:
      

      At the bottom of your screen should be some debug panels. If they don't show up, you can usually open these under the Debug drop down menu.

      IDE	Steps
      Visual Studio	Debug, Windows, Watch window
      Code::Blocks	Debug, Debugging wnidows, Watches
      XCode	View, Debug area, Activate console

      Now you should have the watch windows open, which is a table that displays a Name (variable name) column and a Value column.

      

    • Enter the names of the variables we want to track:
      

      In these watch windows, type in the names of the following variables:

      • Player member variables:
        • food
        • maxHealth
        • health
        • location
      • Game member variables:
        • m_day
        • m_done

      While the program is still paused, we will use the step features to step through each line of code one at a time and watch the variables as they're assigned values.

      Use the Step Over or Next Line to step down one line at a time until you get to the end of the function. As you go down each line, notice how the variable value changes in the watch window once its declaration line is finished.

      

      ---

  • Step into, step out - Investigating program flow
    

    Task: Set a breakpoint at the start of Game::Menu_Scavenge() and then use the Continue button to resume program execution. (Or if you closed the program, run it again and enter a name.)

    Select the "1. Scavenge here" option in the game and make sure the program execution pauses within this function.

    void Game::Menu_Scavenge()
    {
        bool actionSuccessful = true;
        int random = rand() % 5;
        RandomEvent_Scavenging( random );
    }
    

    Use the Stepover/Next line button to move the cursor to the line with RandomEvent_Scavenging( random ); Take note of the value of the random variable.

    We are now sitting at a function call. We can go into the function call using the Step into option.

    

    This will take us into the function.

    void Game::RandomEvent_Scavenging( int event )
    {
        ScreenDrawer::Fill( '~', "black", "red" );
        ScreenDrawer::DrawWindow( "", 1, 1, 78, 13 );
        ScreenDrawer::Set( 3, 2, "DAY: " + Helper::ToString( m_day ), "red", "black" );
    
        int mod;
        if ( event == 0 )
        {
            mod = rand() % 3 + 2;
            ScreenDrawer::Set( 3, 4, "You find a stash of food.", "green", "black" );
    // ... etc ...
    

    This function takes the event variable and figures out what kind of event to make happen in the game.

    Use the Step Over / Next Line button to see which if/else if statement is executed: event = 0=? event = 1=? And so on…

    Take note of which kind of event got executed:

    • You find a stash of food.
    • A zombie surprises you!
    • You find some medical supplies.
    • Another scavenger ambushes you!
    • You don't find anything.

    Don't stop the program execution, we are going to keep working with where we've paused.

    ---

  • Call Stack - Looking at the function call history
    

    Another important debugging tool is the Call Stack, which tells you the order of functions called to get to where the program is currently at.

    Task: Use the Call Stack to take note of what functions were called leading up to your Game::RandomEvent_Scavenging breakpoint.

    The call stack should look like this:

    

    If the call stack pane isn't showing up, you can open them through the menus:

    IDE	Menu
    Visual Studio	Debug, Windows, Call Stack
    Code::Blocks	Debug, Debugging windows, Call Stack

    The top-most function displayed is the one currently running, and all functions below it are functions that were active previously. If you step all the way down, you can trace all the functions that were called to get to where we're at.

    Task: Set a breakpoint in the Game::EndOfDayStats() function and use the Call Stack to take note of what functions were called leading up to it.

    Task: Set a breakpoint in the Player::Player() function (in Player.cpp) and use the Call Stack to take note of what functions were called leading up to it. You will probably have to close and restart the game to hit this breakpoint.

    ---

  • When to use debugging tools…?
    

    Debugging tools are extremely helpful and the better you get at utilizing them to diagnose your programs' issues, the more well prepared you will be for software development in the "real world".

    ---

• Part 2: IDE navigation techniques
  

  Don’t close the zombie game yet – now we’re going to use various IDE features in this project.

  Take a screenshot once you've completed each one and paste it into your document.

  • Viewing code split-screen
    

    In most IDEs you can click-and-drag a code window (via its tab) to another part of the screen, allowing to have a side-by-side view of two (or more) different code files at once.

    Visual Studio:

    Click and drag the tab to the center of the screen. Then, a placement box will show up. Drag the tab to one of these 5 options for different views.

    

    Code::Blocks:

    Click and drag the tab to an edge of the code window. A slight highlight will appear in the place where it will be placed. Let go of the mouse button to place the tab to the side.

    

  • Go to definition
    

    Go to the .h file and right-click on one of the functions, then select the Go to definition (VS) or Go to implementation (CB) to go directly to the definition of that function.

    

  • Go to declaration
    

    Right-click on a function call somewhere, and select Go to declaration to go to where the function is declared.

    

  • Find references of
    

    Right-click on any function and select Find references of and you will get a search result with every place where the function is used throughout the program, including function calls.

    

  • Indenting/unindenting chunks of code
    

    Highlight a chunk of code and use "tab" to indent it all forward, or "shift+tab" to un-indent it all backward.

    

  • Autoformatting
    

    When your indentation gets messed up you can have the IDE automatically format it for you.

    

    IDE	Steps
    Visual Studio	Edit, Advanced, Format Document
    Code::Blocks	Right-click in the code window, select Format use AStyle

  • Comment/uncomment code blocks
    

    Highlight a section of code. You can comment out a whole block at once, or uncomment out a block, in the following ways:

    

    IDE	Comment-out	Uncomment-out
    Visual Studio	Hold CTRL, then press K and then C	Hold CTRL, then press K and then U
    Code::Blocks	Press CTRL+SHIFT+C	Press CTRL+SHIFT+X

    ---

• Part 3: Test
  

  This program contains four simple functions and four test functions:

  1. int GetArea( int width, int length );
  2. void Test_GetArea();
  3. int GetStringLength( string text );
  4. void Test_GetStringLength();
  5. int GetPerimeter( int width, int length );
  6. void Test_GetPerimeter();
  7. float Withdraw( float balance, float amount );
  8. void Test_Withdraw();

  We are going to approach this from a Test Driven Development standpoint where we will write our TESTS before implementing the functionality. This way, we ensure our tests "work" because they first fail - then, when we implement the functionaltiy, the tests passing should be how we verify our logic is correct.

  • Set 1: Stub functions
    

    These functions contain placeholder information being returned. They return data because some C++ compilers will complain if a non-void function doesn't have a return statement. Before you implement the function itself, we will be implementing the unit tests for each function first.

    Task: Implement void Test_GetArea() and void Test_GetStringLength() first, then implement int GetArea( int width, int length ) and int GetStringLength( string text );

    Read the following instructions for a guide.

    • GetArea
      

      First off we need to come up with test cases - at least two for these simple functions that just do computations. Why two? Because if you only have one test that checks "The area of a 2x5 yard is 10", then implementing the function as return 10 would cause it to pass… we need at least two tests to make sure the function has proper logic.

      Here are some test cases we can use for GetArea:

      #	Inputs	Expected outputs
      1	width=5, height=3	returned area is 15
      2	width=7, height=11	returned area is 77

      So… how do we implement this in code?

      We have two inputs and an expected output, and in the program itself we will have an actual output. We can create variables to represent each of these pieces of information:

      • int input_width = 5;
      • int input_height = 3;
      • int expected_result = 15;
      • int actual_result;

      To get a value for the actual_result, we just call the function itself, passing in our inputs:

      actual_result = GetArea( input_width, input_height );

      We can tell if the test passed if the actual_result matches the expected_result. Or, the test failed if they do not match.

      It would be useful to output the results to the console as well, so we can write out something like this:

      if ( actualResult != expectedResult ) { result = "[FAIL]\t"; }
      else                                  { result = "[PASS]\t"; }
      
      cout << result << testName << endl;
      cout << "* input_width:     " << input_width << endl;
      cout << "* input_height:    " << input_height << endl;
      cout << "* expectedResult:  " << expectedResult << endl;
      cout << "* actualResult:    " << actualResult << endl;
      cout << endl;
      

      If you run the program now, we should get a nice print out of the test result:

      [FAIL]  GetArea - pass in 5 and 3 and should get 15 back
      * input_width:     5
      * input_height:    3
      * expectedResult:  15
      * actualResult:    -1
      

      Implement the second test case in the code before continuing.

      Once they're both implemented, you can now implement the int GetArea( int width, int height ) function. To calculate the area of a rectangle, we use the formula:

      area = width x height

      (But write it in C++ code :)

      Implement the function and once run the tests should now pass. Here's how I've formatted my tests:

      --------------------------------------------------------------------------------
      Test_GetArea
      --------------------------------------------------------------------------------
      [PASS]  GetArea - pass in 5 and 3 and should get 15 back
      * input_width:     5
      * input_height:    3
      * expectedResult:  15
      * actualResult:    15
      
      [PASS]  GetArea - pass in 7 and 11 and should get 77 back
      * input_width:     7
      * input_height:    11
      * expectedResult:  77
      * actualResult:    77
      

      ---

    • GetStringLength
      

      Implement the following test cases as unit tests:

      #	Inputs	Expected outputs
      1	text="Hello"	returned length is 5
      2	text="abc def"	returned length is 7

      Once the tests are implemented and they fail when you run the program, now implement the GetStringLength function. (Hint: You can get the length of the text string with text.size().)

      ---

  • Set 2: Broken functions
    

    These functions have already been implemented, but with incorrect logic. You're going to write unit tests before doing any fixes to help ensure that your fixes are valid once implemented.

    Task: Implement void Test_GetPerimeter() and void Test_Withdraw() first, then fix the functions -int GetPerimeter( int width, int length ) and float Withdraw( float balance, float amount )

    Read the following instructions for a guide.

    • GetPerimeter
      

      For this function, come up with your own TWO test cases and implement them as unit tests. After implementing the unit tests, fix the function logic.

      ---

    • Withdraw
      

      For this function, come up with your own TWO test cases and implement them as unit tests. After implementing the unit tests, fix the function logic.

      ---

• Turning in the assignment
  

  Once you're done with the assignment, you need to add, commit, and push your changes to the server.

  

  Save your changes to the server:

  1. Open git bash from within your repository folder on your harddrive.
  2. Use git status to review what files have changed since your last commit.
  3. Use git add . to add all changed files to a changeset.
  4. Use git commit -m "MESSAGE" to create a snapshot of your current changes. (Replace "MESSAGE" with something more descriptive.)
  5. Use git push -u origin u04_debugtest to push all your commits to the GitLab server, on the u04_debugtest branch.

  You can continue making changes and do additional add, commit, and push commands as well.

  Get everything ready for next assignment:

  1. Use git checkout main to change back to the main branch to prepare for the next assignment. (You can always use git checkout u04_debugtest to return to this branch and code.)
  2. Use git pull to pull latest from the server. (This might happen if the instructor adds new starter code or makes modifications.)

  Create a Merge Request / turn in on Canvas:

  1. Navigate to your GitLab repository webpage.
  2. Click on the blue "Create merge request" button.
  3. Add a descriptive Title, then click "Create merge request" at the bottom of the page.
  4. Copy the URL of this merge request.
  5. Find the assignment on Canvas. Click "Start Assignment".
  6. Paste in the Merge Request URL here. Click "Submit Assignment".

🧠 Tech Literacy - Git (U04.TEC)

• Without Source Control…
  

  Let's imagine a workplace that doesn't use any source control software. Multiple people have shared files on a network drive and can edit them at any time. Two different users are working on a file at the same time, but what happens when they save?

  

  If User A saves their file first and then User B saves their file second, the network file will only be the last saved version - User B's version. It won't automatically merge the files together, meaning User A's work gets lost. Imagine working on a lot of code and having this happen - making sure work doesn't get overwritten would be a nightmare to manage manually.

  ---

• Types of Source Control software…
  

  Various source control systems have been developed over the years to help manage versioning, storing, and merging source code. There are pros and cons to each one, but the most common ones these days are probably Git and TFS (Team Foundation Server). Others you might hear about are SVN (Subversion) and Mercurial. We will be specifically talking about Git here.

  ---

• Basics of Git
  

  

  There are two main parts of source control: The Server, where the code is all brought together and stored, and the Clients - or, the user PCs. A person, company, or other organization can set up a Server on their own computers or they can utilize a service like GitLab, GitHub, SourceForge, Bitbucket, or other services to host their code for them.

  Either way, for a project, a repository is created on the server. This is basically a folder, except the Git program is told that it is a special Git folder, and the Git software knows how to process different commands to help users add, update, and manage the code stored within.

  ---

  • The clone command
    

    

    When a new developer joins the team, or a new project is created to work on, the repository will be created and then each teammate on that project can use the clone command, which looks like this:

    git clone URL.git
    

    This command tells the Git program to access the git URL given and download the repository folder. Git handles the download and setting up the folder and files within, and on the user's local computer they'll see a folder with the repository name. The clone command only needs to be done once per computer.

    ---

  • Branches
    

    

    In our project repository, by default there will be a main branch (Note: sometimes the default is a master branch). The main branch should represent the current, stable version of the program. The goal is to make sure the code on main can build.

    When somebody wants to add a new feature or is working on a bug, they will create a new branch to work on. This starts at the main branch, but gives the user their own workspace. They can make many backups of their code on their own branch without affecting the main branch, and without breaking code on other peoples' machines.

    The checkout command is used with the -b flag to create a new branch:

    git checkout -b BRANCHNAME
    

    Even if you're on a different branch, you can switch back to main, or other branches, any time with git checkout BRANCHNAME. On your local computer you may see files disappear and changes be undone, but those changes will come back once you're on the branch where you created those files/changes.

    ---

  • The status command
    

    While working on a branch you can use the git status command to see a list of files that you've added, removed, and changed since the last commit. Items marked in red haven't yet been marked as "to back up", and items marked in green are ready to be backed up by using the commit command. To mark a file as "ready to backup", we use the add command.

    git status
    

    ---

  • The add command
    

    

    When you're ready to make a backup of your work, you can use a git add command to add your files. Sometimes you only want to add one or two files, sometimes you want to add only a certain type of files, and sometimes you want to add everything that has been updated.

    Add one specific file:

    git add FILENAME
    

    Add all files ending with ".cpp":

    git add *.cpp
    

    Add all changed files:

    git add .
    

    ---

  • The commit command
    

    

    After using the add command, we "bundle" all the changes together in one commit. We use the commit command, and a message is required - this is to help us keep track of what we changed where. Try to add a descriptive message so you can track your changes later if you need to.

    Commits are initially only stored on your own computer, they won't be shown on the repository server until you push everything.

    git commit -m "Fixed bug"
    

    ---

  • The push command
    

    

    After you have one or more commits ready to go, you can use the push command to send your changes to the server under your branch. This will allow others to view the changes you've made, while still keeping your code separate from the main branch… for now. The overall goal is to eventually get it merged into the main branch, but we aren't doing that quite yet.

    git push -u origin BRANCHNAME
    

    ---

  • The pull command
    

    

    Besides just pushing your own changes to the server, you will periodically want to use the pull command to get any changes from the server - such as completed features from other developers, or merged in code.

    The pull will grab the latest version of files, so you want to make sure to first add and commit your changes before using pull.

    git checkout main
    git pull
    

    ---

  • Merge requests
    

    

    The Merge Request is the final part of a work-in-progress feature's life. You create a merge request, and it will show a list of all changes you've made under the changes tab. Usually, you would send this Merge Request to other developers to review your work, but for this class you'll submit your Merge Request as your assignment turn-ins.

    

    Other developers can leave comments on specific lines of code in the merge request. Those reviewing your merge request should look out for obvious potential errors, typos, logical fallacies, and so on. If comments are left asking you to fix something, you can go back to your computer, make changes, then add/commit/push again and ask others to re-review your updates.

    Finally, once it has been approved, the code can be merged to the main branch. In this class, the instructor will merge the code. In the work world, someone like the system architect or your team lead might handle this step.

    ---

    There's no assignment to turn in for this item.

📊 Presentation - Algorithm efficiency (U05.PRES)

📖️ Reading - Algorithm efficiency (U05.READ)

• Introduction: Algorithm Efficiency (and why we care)
  

  Processing power continues increasing as time moves forward. Many things process so quickly that we barely notice it, if at all. That doesn't mean we can just write code as inefficiently as possible and just let it run because "computers are fast enough, right?" - as technology evolves, we crunch more and more data, and as "big data" becomes a bigger field, we need to work with this data efficiently - because it doesn't matter how powerful a machine is, processing large quantities of data with an inefficient algorithm can still take a long time.

  And some computers today are slow. Not usually the computers that the average person is using (Even though it might feel that way if they're running Windows). Some computers that handle systems are pretty basic, or they're small, and don't have the luxury of having great specs. Fitness trackers, dedicated GPS devices, a thermostat, etc. For systems like these, processing efficiency is important.

  Let's say our algorithm's time to execute increases quadratically. That means, as we increase the amount of items to process (\(n\)), the time to process that data goes up quadratically.

  

  For processing 1 piece of data, it takes 1 unit of time (we aren't focused so much on the actual unit of time, since each machine runs at different speeds) - that's fine. Processing 2 pieces of data? 4 units of time. 8 pieces of data? 64 units of time. We don't just double the amount of time it takes when we double the data - we square it.

  How much data do you think is generated every day on a social media website that has millions of users? Now imagine the processing time for an algorithm with a quadratic increase…

  Data \(n\)	Time units
  1	1
  2	4
  3	9
  4	16
  5	25
  …	…
  100	10,000
  1,000	1,000,000
  10,000	100,000,000
  1,000,000	1,000,000,000,000

  From a design standpoint we also need to know what the efficiency of different algorithms are (such as the algorithm to find data in a Linked List or the algorithm to resize a dynamic array) in order to make design decisions on what is the best option for our software.

  ---

• Example: Fibonacci sequence, iterative and recursive
  

  As an example, you shouldn't use a recursive algorithm to generate a Fibonacci sequence (Each number \(F_n\) in the sequence is equal to the sum of the two previous items: \(F_n = F_{n-1} + F_{n-2}\)). It's just not as efficient! Let's look at generating the string of numbers:

  1, 1, 2, 3, 5, 8, 13, 21, 34, 55

  The most efficient way to do this would be with an iterative approach using a loop. However, we could also figure it out with a recursive approach, though the recursive approach is much less efficient.

  Fibonacci sequence, iterative:

  int GetFib_Iterative(int n)
  {
    if (n == 0 || n == 1) { return 1; }
  
    int n_prev = 1;
    int n_prevprev = 1;
    int result = 0;
  
    for (int i = 2; i <= n; ++i)
      {
        result = n_prev + n_prevprev;
        n_prevprev = n_prev;
        n_prev = result;
      }
  
    return result;
  }
  

  This algorithm has a simple loop that iterates \(n\) times to find a given number of the Fibonacci sequence. The amount of time the loop iterates based on \(n\) is:

  n	3	4	5	6	7	8	9	10	…	20
  iterations	2	3	4	5	6	7	8	9	…	19

  Fibonacci sequence, recursive:

  int GetFib_Recursive(int n)
  {
    if (n == 0 || n == 1) { return 1; }
  
    return GetFib_Recursive(n - 1) + GetFib_Recursive(n - 2);
  }
  

  The way this version is written, any time we call this function with any value \(n\), it has to compute the Fibonacci number for \(Fib(n-1)\), \(Fib(n-2)\), \(Fib(n-3)\), … \(Fib(1)\), \(Fib(0)\) … twice. This produces duplicate work b ecause it effectively doesn't "remember" what \(Fib(3)\) was after it computes it, so for \(Fib(n)\) it has to recompute \(Fib(n-1)\) and \(Fib(n-2)\) each time…

  n	3	4	5	6	7	8	9	10	…	20
  iterations	2	4	7	12	20	33	54	88	…	10,945

  The growth rate of the iterative version ends up being linear: As \(n\) rises linearly, the amount of iterations also goes up linearly.

  The growth rate of the recursive function is exponential: As \(n\) rises linearly, the amount of iterations goes up exponentially.

  

  • Red/solid: Recursive growth rate
  • Blue/dashed: Iterative growth rate
  • Y scale from 0 to 25 (the 0th, to 25th Fibonacci number to generate).

  For small amounts this might not be too bad. However, if we were generating a Fibonacci number further in the list, it would continue getting even slower…

  

  • Red/solid: Recursive growth rate
  • Blue/dashed: Iterative growth rate
  • Y scale from 0 to 11,000 (the 11,000th Fibonacci number to generate).

  If we are trying to generate the 11,000th item in the sequence, the iterative approach requires 11,000 iterations in a loop. That linear increase is still much faster than each \(Fib(n)\) calling \(Fib(n-1)\) and \(Fib(n-2)\) recursively.

  ---

• Big-O Notation and Growth Rates
  

  For the most part, we don't care much about the exact amount of times a loop runs. After all, while the program is running, \(n\) could be changing depending on user input, or how much data is stored, or other scenarios. Instead, we are more interested in looking at the big picture: the generalized growth rate of the algorithm.

  We use something called "Big-O notation" to indicate the growth rate of an algorithm. Some of the rates we care about are:

  \(O(1)\)	\(O(log(n))\)	\(O(n)\)	\(O(n^2)\)	\(O(n^3)\)	\(O(2^n)\)
  Constant	Logarithmic	Linear	Quadratic	Cubic	Exponential

  Constant time, \(O(1)\)

  We think of any single command as being constant time. The operation \[ a = b + c \] will take the same amount of computing time no matter what the values of \(a\), \(b\), and \(c\) are.

  int F(int x)
  {
    return 3 * x + 2;
  }
  

  

  Logarithmic time, \(O(log(n))\)

  Having an algorithm that halves its range each iteration of the loop will result in a logarithmic growth rate.

  int Search(int l, int r,
             int search, int arr[])
  {
    while ( l <= r )
      {
        int m = l + (r-l) / 2;
        if ( arr[m] == search )
          { return m; }
        else if ( arr[m] < search )
          { l = m+1; }
        else if ( arr[m] > search )
          { r = m-1; }
      }
    return -1;
  }
  

  

  Linear time, \(O(n)\)

  Having a single loop that iterates over a range will be a linear time increase.

  int Sum( int n )
  {
    int sum = 0;
    for (int i=1; i<=n; i++)
      {
        sum += n;
      }
    return sum;
  }
  

  

  If there is some scenario that causes the loop to halve its range each time, then its growth rate would be less than linear: as \(O(log(n))\).

  Quadratic time, \(O(n^2)\)

  Quadratic time comes into play when you have one loop iterating \(n\) times nested within an other loop that also iterates \(n\) times. For example, if we were writing out times tables from 1 to 10 (\(n = 10\)), then we would need 10 rows and 10 columns, giving us \(10^2 = 100\) cells.

  void TimesTables(int n)
  {
    for (int y=1; y<=n; y++)
      {
        for (int x=1; x<=n; x++)
          {
            cout << x << "*"
                 << y << "="
                 << x*y << "\t";
          }
        cout << endl;
      }
  }
  

  

  Cubic time, \(O(n^3)\)

  Just like nesting two loops iterating \(n\) times each gives us a \(n^2\) result, having three nested loops iterating \(n\) times each gives us a \(O(n^3)\) growth rate.

  void CubicThing(int n)
  {
    for (int z=1; z<=n; z++)
      {
        for (int y=1; y<=n; y++)
          {
            for (int x=1; x<=n; x++)
              {
                cout << x << " "
                     << y << " "
                     << z << endl;
              }
          }
      }
  }
  

  

  Exponential time, \(O(2^n)\)

  With an exponential function, each step increases the complexity of the operation. The Fibonacci example is a good illustration: Figuring out Fib(0) and Fib(1) are constant, but Fib(2) requires calling Fib(0) and Fib(1), and Fib(3) calls Fib(1) and Fib(2), with Fib(2) calling Fib(0) and Fib(1), and each iteration adds that many more operations.

  int Fib(int n)
  {
    if (n == 0 || n == 1)
      return 1;
  
    return
      Exponential_Fib(n-2)
      + Exponential_Fib(n-1);
  }
  

  

  Growth rate comparisons:

  

  ---

• Review questions:
  
  1. Let's say an algorithm's time complexity is constant. For this example algorithm we can model the efficiency like this: \[ T(n) = 5 \] where \(n\) is the amount of items to process and \(T\) is the time it takes.
     1. Processing 1 item would cost how many time units?
     2. Processing 10 items would cost how many time units?
     3. Processing 100 items would cost how many time units?
  2. Let's say an algorithm's time complexity is linear. For this example algorithm we can model the efficiency like this: \[ T(n) = 2n \]
     1. Processing 1 item would cost how many time units?
     2. Processing 10 items would cost how many time units?
     3. Processing 100 items would cost how many time units?
  3. Let's say an algorithm's time complexity is quadratic. For this example algorithm we can model the efficiency like this: \[ T(n) = n^2 \]
     1. Processing 1 item would cost how many time units?
     2. Processing 10 items would cost how many time units?
     3. Processing 100 items would cost how many time units?

  4. Given this function:

     int Func( int n )
     {
       return 3 * n; // +1 command
     }
     

     How many commands are executed when…

     1. \(n = 1\)?
     2. \(n = 10\)?
     3. \(n = 100\)?

  5. Given this function:

     int Func( int n )
     {
       n += 1; // +1 command
     
       if ( n > 100 )
         return n+100; // +1 command, or
       else if ( n > 10 )
         return n+10; // +1 command, or
       else
         return n; // +1 command
     }
     

     How many commands are executed when…

     1. \(n = 1\)?
     2. \(n = 10\)?
     3. \(n = 100\)?

  6. Given this function:

     void Func( int n )
     {
       for ( int i = 0; i < n; i++ )
       {
         cout << i << " "; // +1 command each iteration
       }
     }
     

     How many commands are executed when…

     1. \(n = 1\)?
     2. \(n = 10\)?
     3. \(n = 100\)?
     4. The increase is… (constant/linear/quadratic?)

  7. Given this function:

     void Func( int n )
     {
       int iterations = 0; // Don't count me
       for ( int i = 0; i < n; i++ )
       {
         for ( int j = 0; j < n; j++ )
         {
           cout << i << "," << j << endl; // +1 command each iteration
           iterations++; // Don't count me
         }
       }
       cout << "Iterations: " << iterations << endl; // Don't count me
     }
     

     How many commands are executed when…

     1. \(n = 1\)?
     2. \(n = 10\)?
     3. \(n = 100\)?
     4. The increase is… (constant/linear/quadratic?)

🔎 Concept Intro - Algorithm efficiency (U05.CIN)

🧠 Tech Literacy - Algorithm efficiency (U05.TEC)

📊 Presentation - Pointers and memory (U06.PRES)

📖️ Reading - Pointers and memory (U06.READ)

• Memory addresses
  

  When we declare a variable, what we're actually doing is telling the computer to set aside some memory (in RAM) to hold some information. Depending on what data type we declare, a different amount of memory will need to be reserved for that variable.

  Data type	Size
  boolean	1 byte
  character	1 byte
  integer	4 bytes
  float	4 bytes
  double	8 bytes

  A bit is the smallest unit, storing just 0 or 1. A byte is a set of 8 bits. With a byte, we can store numbers from 0 to 255, for an unsigned number (only 0 and positive numbers, no negatives).

  Minimum value, 0

  (Decimal value = \(128 \cdot 0 + 64 \cdot 0 + 32 \cdot 0 + 8 \cdot 0 + 4 \cdot 0 + 2 \cdot 0 + 1 \cdot 0\))

  place	128	64	32	16	8	4	2	1
  value	0	0	0	0	0	0	0	0

  Maximum value, 255

  (Decimal value = \(128 \cdot 1 + 64 \cdot 1 + 32 \cdot 1 + 8 \cdot 1 + 4 \cdot 1 + 2 \cdot 1 + 1 \cdot 1\))

  place	128	64	32	16	8	4	2	1
  value	1	1	1	1	1	1	1	1

  A char only needs one byte to store a single letter because we represent letters with the ASCII or UTF8 codes 65 - 90 for upper-case, and 97 - 122 for lower-case.

  A	B	C	D	E	F	G	H	I	J	K	L	M
  65	66	67	68	69	70	71	72	73	74	75	76	77
  N	O	P	Q	R	S	T	U	V	W	X	Y	Z
  78	79	80	81	82	83	84	85	86	87	88	89	90

  a	b	c	d	e	f	g	h	i	j	k	l	m
  97	98	99	100	101	102	103	104	105	106	107	108	109
  n	o	p	q	r	s	t	u	v	w	x	y	z
  110	111	112	113	114	115	116	117	118	119	120	121	122

  Any of these numbers can be stored with 8 bits:

  A = 65…

  (Decimal value = \(128 \cdot 0 + 64 \cdot 1 + 32 \cdot 0 + 8 \cdot 0 + 4 \cdot 0 + 2 \cdot 0 + 1 \cdot 1\))

  place	128	64	32	16	8	4	2	1
  value	0	1	0	0	0	0	0	1

  z = 122…

  (Decimal value = \(128 \cdot 0 + 64 \cdot 1 + 32 \cdot 1 + 8 \cdot 1 + 4 \cdot 0 + 2 \cdot 1 + 1 \cdot 0\))

  place	128	64	32	16	8	4	2	1
  value	0	1	1	1	1	0	1	0

  So when we declare a variable, the computer finds an available space in memory and reserves the appropriate amount of bytes in memory. For example, our char could be assigned the memory address 0xabc008 in memory, and its value being stored would look like this:

  …007	…008	…009	…00a	…00b	…00c	…00d	…00e	…00f	…010
  …	0	1	1	1	1	0	1	0	…

  (…007 and …010 are spaces in memory taken by something else)

  We can view the addresses of variables in our program by using the address-of operator &. Note that we have used the ampersand symbol before to declare pass-by-reference parameters, but this is a different symbol used in a different context.

  #include <iostream>
  using namespace std;
  
  int main()
  {
    int number1 = 10;
    int number2 = 20;
  
    cout << &number1 << "\t"
         << &number2 << endl;
  
    return 0;
  }
  

  Running the program, it would display the memory addresses for these two variables. Notice that they're 4 bytes apart in memory (one is at …70 and one is at …74):

  0x7ffd3a24cc70	0x7ffd3a24cc74
  

  Each time we run the program, we will get different memory addresses, since the operating system reclaims that memory when the program ends, and gives us new memory spaces to allocate next time we run the program.

  0x7ffe0e708a80	0x7ffe0e708a84
  

  When we declare an array of integers of size \(n\), the program asks for \(n \times 4\) bytes of memory to work with. The two variables above didn't have to be side-by-side in memory; they just happened to be because they were declared close together. With an array, however, all elements of the array will be contiguous (side-by-side) in memory.

  Here we have an array of integers:

  int arr[3];
  
  for ( int i = 0; i < 3; i++ )
    {
      cout << &arr[i] << "\t";
    }
  

  And the output:

  0x7ffd09a130c0	0x7ffd09a130c4	0x7ffd09a130c8
  

  Because the elements of an array must be contiguous in memory, we cannot resize a normal array. After our array is declared, chances are the memory addresses right after it will be put to use elseware on the computer and will be unavailable to our program and our array.

  But, after we learn about pointers, we will learn how we can dynamically allocate as much memory as we need at any time during our program's execution - giving us the ability to "resize" arrays by allocating space for a new array, copying the data over to the larger chunk of memory, and deallocating the old chunk of memory from the smaller array.

  ---

• Pointers
  
  • Creating pointer variables
    

    We can declare special variables that store memory addresses rather than storing an int or float or char value. These variables are called pointers.

    We can declare a pointer like this: int* ptrNumber; Or like this: int * ptrNumber; Or like this: int *ptrNumber;

    But note that doing this declares one pointer and several integers: int * ptrNumber, notAPointer1, notAPointer2; To avoid confusion, \underline{declare multiple pointers on separate lines}.

    If we declare a pointer as an int* type, then it will only be able to point to the addresses of integer variables, and likewise for any other data type.

    Context: Safety with pointers!

    Remember how variables in C++ store garbage in them initially? The same is true with pointers - it will store a garbage memory address. This can cause problems if we try to work with a pointer while it's storing garbage.

    To play it safe, any pointer that is not currently in use should be initialized to NULL or nullptr.

    Declaring a pointer and initializing it to nullptr:

    #include <iostream>
    using namespace std;
    
    int main()
    {
      int * ptr = nullptr;
    
      return 0;
    }
    

  • Assigning pointers to addresses
    

    Once we have a pointer, we can point it to the address of any variable with a matching data type. To do this, we have to use the address-of operator to access the variable's address - this is what gets stored as the pointer's value.

    • Assigning an address during declaration: int * ptr = &somevariable;
    • Assigning an address after declaration: ptr = \&somevariable;

    After assigning an address to a pointer, if we cout the pointer it will display the memory address of the pointed-to variable - just like if we had used cout to display the address-of that variable.

    // Shows the same address
    cout << ptr << endl;
    cout << &somevariable;
    

    Here's a simple program that has an integer var with a value of 10, and a pointer ptr that points to var's address.

    #include <iostream>
    using namespace std;
    
    int main()
    {
      int * ptr;
      int var = 10;
    
      ptr = &var;
    
      cout << "var address: " << &var << endl;
      cout << "ptr address: " << &ptr << endl;
      cout << "var value:   " << var << endl;
      cout << "ptr value:   " << ptr << endl;
    
      return 0;
    }
    

    The output would look like:

    var address: 0x7ffc3d6028b0
    ptr address: 0x7ffc3d6028b4
    var value:   10
    ptr value:   0x7ffc3d6028b0
    

    Some things to note:

    • var stores its data at its address 0x7ffc3d6028b0.
    • ptr stores its data at its address 0x7ffc3d6028b4.
    • var's value is 10, since it's an integer.
    • ptr's value is the address of var, since it's a pointer-to-an-integer.

    

  • Dereferencing pointers to get values
    

    Once the pointer is pointing to the address of a variable, we can access that pointed-to variable's value by dereferencing our pointer. This gives us the ability to read the value stored at that memory address, or overwrite the value stored at that memory address.

    We dereference the pointer by prefixing the pointer's name with a * - again, another symbol being reused but in a different context.

    In this code, we point ptr to the address of var. Outputting ptr will give us var's address, and outputting *ptr (ptr dereferenced) will give us the value stored at var's address.

    int * ptr;
    int var = 10;
    
    ptr = &var;
    
    cout << "ptr value:        " << ptr << endl;
    cout << "ptr dereferenced: " << *ptr << endl;
    

    Output:

    ptr value:        0x7ffd21de775c
    ptr dereferenced: 10
    

    Then, we could also overwrite the value stored at var's address by again dereferencing the pointer and writing an assignment statement:

    *ptr = 20;
    

    When we output the value that var is storing, either directly through var or through the ptr, we can see that the value of var has been overwritten:

    cout << "var value:        " << var << endl;
    cout << "*ptr value:       " << *ptr << endl;
    

    var value:        20
    *ptr value:       20
    

    ---

• Pointer cheat sheet
  

  Declare a pointer	int* ptrInt;
  	float *ptrFloat;
  Assign pointer to address	ptrInt = &intVar;
  	ptrFloat = &floatVar;
  Dereference a pointer	cout << *ptrChar;
  	*ptrInt = 100;
  Assign to nullptr	float *ptrFloat = nullptr;
  	ptrChar = nullptr;

  ---

• Invalid memory access with pointers
  

  Remember that when you declare a variable in C++, it will initially store garbage. This is true of pointers as well. When you declare a pointer without initializing it to nullptr, it will be storing random garbage that it will try to interpret as a memory address. If you dereference a pointer that is pointing to garbage, your program is going to run into a problem - a segmentation fault.

  A pointer pointing to garbage:

  int main()
  {
    int * bob;
    cout << *bob << endl;
  
    return 0;
  }
  

  Program output:

  Segmentation fault (core dumped)
  

  How do we check whether memory address is valid?

  In short, we can't check if an address stored in a pointer is valid. This is why we initialize our pointers to nullptr when they're not in use - we know nullptr means that the pointer is not pointing to anything.

  ---

• Dynamically allocating memory
  

  One handy use of pointers is to point at the addresses of other variables that were already declared. However, there is a second main use of pointers: To dynamically allocate memory any time we need new variables that we don't have to pre-write in the program.

  ---

  • Dynamic variables
    

    At the moment, dynamic variables might seem pointless, but they are really handy for linked data structures - a type of structure you can use to store a series of data in that is an alternative to an array.

    • new and delete
      

      We use the new keyword to allocate memory for the size of one variable data type (as opposed to an array of the variables), and delete to free up that memory.

      Once we've allocated memory through the pointer, we can use the pointer as normal. The only difference is that we're now accessing an address that was allocated differently from the address of a "normal" variable.

      • Allocating memory for a single item: int * ptr = new int;
      • Deallocating memory for a single item: delete ptr;

      Small program using a dynamic variable:

      int main()
      {
        int * myNumber;             // Declare pointer
      
        myNumber = new int;         // Allocate memory
      
        *myNumber = 10;             // Assign value
      
        cout << *myNumber << endl;  // Print value
      
        delete myNumber;            // Free memory
      
        return 0;
      }
      

      ---

  • Dynamic arrays
    

    For our normal arrays, we are unable to resize them during the program's run time because an array requires that all elements of the array are contiguous (side-by-side) in memory.

    However, if we can allocate and deallocate memory any time we want with pointers, we can create a dynamic array. If we ever need to resize it, we allocate a new array of a bigger size and copy the data from the old array to the new one.

    • new[ ] and delete[ ]
      

      When we're allocating space for an array of items, we use a slightly different set of keywords:

      • Allocate memory for an array: int * arr = new int[100];
      • Deallocate memory for an array: delete [] arr;

      Example program that lets the user specify how big the array will be.

      int main()
      {
        int arraySize;
        float * pricesArray;
      
        cout << "How many items? ";
        cin >> arraySize;
      
        pricesArray = new float[arraySize]; // Allocate mem
      
        for ( int i = 0; i < arraySize; i++ )
          {
            cout << "Enter price for item " << i << ": ";
            cin >> pricesArray[i];
          }
      
        delete [] pricesArray;      // Deallocate memory
      
        return 0;
      }
      

      When you've used a pointer to allocate space for an array, you will access items in the dynamic array the same way you would do for a normal array. In other words, you would use the subscript operator [ ] to access elements at particular indices, and you don't need to prefix the pointer with the dereference operator *.

      ---

    • "Resizing" a dynamic array
      

      Let's say we're writing a program that stores the user's library of movies they own. It saves a file so they can run the program any time, add or delete movies, close the program and open it again sometime later.

      We can't realistically predict how many movies a person would own - some people might be collectors and have tons of movies. At the same time, if we were to over-estimate and make an array with, say, 10,000 elements, it would be a huge waste of memory if we had such a big array for someone who only had a few dozen movies.

      A dynamic array would work perfectly here because we can initially create an array that's fairly small - maybe 10 items - and if the array fills up, we can then allocate more memory and copy the movies to the new array and deallocating the old array. If it fills up again, we just repeat the process, allocating more memory, copying the data over, and freeing the old array's memory.

      Resizing steps

      The resizing process works like this:

      1. Create a pointer and use it to allocate a new, bigger array.
      2. Use a for loop to copy all the elements from the old-small-array to the new-big-array.
      3. Free the memory for the old-small-array.
      4. Update the array's pointer, which was pointing to old-small-array, to now point to the address of the new-big-array.

      Normally, you would store a dynamic array inside of a class that acts as the interface for adding and removing data, where it will check if there's enough space before adding new information and resizing the array if not.

      Here's an example of resizing a movie array within a MovieLibrary class:

      void MovieLibrary::Resize()
      {
        // Allocate more memory
        int newSize = m_arraySize + 10;
        string * newArray = new string[newSize];
      
        // Copy data from old array to new array
        for ( int i = 0; i < m_arraySize; i++ )
          {
            newArray[i] = m_movieArray[i];
          }
      
        // Free memory of old array
        delete [] m_movieArray;
      
        // Update the pointer to point at new array
        m_movieArray = newArray;
      
        // Update the array size
        m_arraySize = newSize;
      }
      

      ---

      Dynamic array example: Movie Library

      Here's a small example of a class that contains a dynamic array, that allows users to add additional information, and handles checking for a full array and resizing.

      MovieLibrary.h:

      #ifndef _MOVIE_LIBRARY_HPP
      #define _MOVIE_LIBRARY_HPP
      
      #include <string>
      using namespace std;
      
      class MovieLibrary
      {
      public:
        MovieLibrary();
        ~MovieLibrary();
      
        void ViewAllMovies() const;
        void ClearAllMovies();
        void AddMovie( string newTitle );
      
      private:
        bool IsFull();
        void Resize();
      
        string * m_movieArray;
        int m_arraySize;
        int m_itemsStored;
      };
      
      #endif
      

      The methods IsFull() and Resize() are set as private because outside users don't need to know anything about how the data is stored. The outside users shouldn't be able to recall Resize whenever they want.

      MovieLibrary.cpp:

      Constructor:

      MovieLibrary::MovieLibrary()
      {
        m_arraySize = 10;
        m_movieArray = new string[m_arraySize];
        m_itemsStored = 0;
      }
      

      In the constructor, we initialize our m_movieArray member pointer variable by allocating some memory to start with.

      If we weren't going to allocate memory in the constructor, then we should initialize m_movieArray by setting it to nullptr.

      We also have two separate size variables - m_arraySize keeps track of how many spaces are available in the array, and m_itemsStored keeps track of how many items the user has added to the array.

      ---

      Destructor:

      MovieLibrary::~MovieLibrary()
      {
        if ( m_movieArray != nullptr )
          {
            delete [] m_movieArray;
          }
      }
      

      Before the MovieLibrary item is destroyed (e.g., when the program ends and it goes out of scope), we need to make sure to *free the memory that we allocated}. First, we need to check if the pointer m_movieArray is pointing to nullptr - if it is, we can assume it's not in use and there's nothing to do. But, if m_movieArray is pointing to some address, we assume that memory has been allocated here. In this case, we free that memory.

      ---

      ViewAllMovies:

      void MovieLibrary::ViewAllMovies() const
      {
        for ( int i = 0; i < m_itemsStored; i++ )
          {
            cout << i << ". " << m_movieArray[i] << endl;
          }
      }
      

      This is just a simple for loop that goes from index 0 to m_itemsStored - 1, displaying each element to the screen.

      We aren't iterating until i < m_arraySize because if our array size is 10 and the user has only stored 5 movies, we don't need to display 5 empty slots.

      ---

      ClearAllMovies:

      void MovieLibrary::ClearAllMovies()
      {
        delete [] m_movieArray;
        m_movieArray = nullptr;
        m_arraySize = 0;
        m_itemsStored = 0;
      }
      

      If the user decides to clear out their movie array, we could just deallocate all memory reserved for the movie list and reset our size variables. We just need to make sure we're checking to make sure the array is allocated before we try to access elements from it or add to it.

      ---

      IsFull:

      bool MovieLibrary::IsFull()
      {
        return m_itemsStored == m_arraySize;
      }
      

      The array is full if the amount of items the user has stored, m_itemsStored is equal to the amount of spaces we have allocated for the array, m_arraySize.

      ---

      AddMovie:

      void MovieLibrary::AddMovie( string newTitle )
      {
        if ( m_movieArray == nullptr )
          {
            m_arraySize = 10;
            m_movieArray = new string[m_arraySize];
          }
        if ( IsFull() )
          {
            Resize();
          }
      
        m_movieArray[ m_itemsStored ] = newTitle;
        m_itemsStored++;
      }
      

      Before we add a movie, we need to make sure m_movieArray is set up and ready.

      First, we check to see if it is pointing to nullptr. If it is, we allocate memory.

      Next, we check to see if the array is full. If it is, we call Resize().

      Finally, once those two checks have been done and the array has been prepared, we can add a new item to the array and increase hte m_itemsStored count.

      ---

      Resize:

      void MovieLibrary::Resize()
      {
        int newSize = m_arraySize + 10;
        string * newArray = new string[newSize];
      
        for ( int i = 0; i < m_arraySize; i++ )
          {
            newArray[i] = m_movieArray[i];
          }
      
        delete [] m_movieArray;
      
        m_movieArray = newArray;
        m_arraySize = newSize;
      }
      

      This is the same Resize() method as was shown before as an example of resizing a dynamic array.

      ---

• Memory Management
  
  • Types of memory errors
    

    Working with pointers and dealing with memory can lead to writing code that can mess up our program or even slow down our computer (until the next reboot).

    Invalid memory access:

    Invalid memory access happens when a pointer isn't set to nullptr when it's no longer in use. If this doesn't happen, the memory address it's pointing to could be invalid, such as if delete was used on the pointer, or if the pointer were declared and not initialized.

    An invalid memory access would cause a problem once you try to dereference the pointer pointing to an invalid address - causing a segfault and your program to crash.

    Memory leak:

    A memory leak occurs when you've allocated memory (via the new command) but you never deallocate it. C++ won't automatically deallocate this memory for you, and what happens is that chunk of memory ends up being "called for" even after the program has finished running. This memory block will be unavailable to all programs until the user restarts their computer.

    If you had many items allocating memory but never freeing them, the resulting memory leaks could cause your computer to slow down over time (until the next reboot).

    Missing allocation:

    Missing allocation occurs if you try to delete memory that has already previously been freed. If this happens, the progrma will crash.

    ---

  • The Stack and the Heap
    

    What is the difference between a normal variable…

    int myNum;

    … and a dynamically allocated variable?…

    int * myNum = new int;

    Well, there are different types of memory, and each is stored in a different space.

    The Stack:

    All of our non-dynamic variables we have been declaring, including function parameters and class member variables, get allocated to the Stack. The Stack part of memory has a fixed size, and it contains a sequence of memory addresses. The Stack automatically handles the memory management for these variables - when we declare a int count; variable, it will be pushed onto the Stack, and when it's not in use anymore (when it goes out of scope), it will be removed from (popped off) the Stack.

    A "stack overflow" error occurs when so many variables have been declared that the Stack runs out of room. This usually occurs while writing recursive functions that have a logic error, causing them to repeat until we run out of Stack space.

    The Heap:

    The heap is where dynamically allocated data gets stored. The Heap does not automatically take care of memory management for us, so that is why we have to deal with new and delete ourselves (unless we're using a smart pointer). Any data in the Heap must be accessed via a pointer. There is no size restriction for the Heap.

    ---

• Smart Pointers
  

  In modern versions of C++ we have access to smart pointers, which allow us to utilize pointer functionality but without having to worry about the memory management side of things. It's important to see both the original style of pointers and the smart pointers so that you're acquainted with both in case you experience them in other classes or on the job.

  ---

  • shared_ptr
    

    

    Documentation: https://cplusplus.com/reference/memory/shared_ptr/

    Shared pointers are meant for spaces in memory that will be pointed to by multiple pointers. The memory allocated at that address stays active up until the last pointer is destroyed - that triggers the deallocation of the memory once nobody is pointing to it anymore.

    To illustrate this, let's create a City struct:

    struct City
    {
      City( string value )
      {
        name = value;
      }
    
      string name;
      shared_ptr<City> west_neighbor;
      shared_ptr<City> east_neighbor;
      shared_ptr<City> south_neighbor;
      shared_ptr<City> north_neighbor;
    };
    

    Each City can have a north, south, east, and/or west neighbor City. Instead of using a City* traditional pointer, we're using the shared_ptr object that's part of the <memory> C++ library.

    Within our main program, we can create some cities. Instead of our dynamic variable allocation like City lenexa = new City( "Lenexa" );, it will look like this:

    shared_ptr<City> overland_park  = shared_ptr<City>( new City( "Overland Park" ) );
    shared_ptr<City> lenexa         = shared_ptr<City>( new City( "Lenexa" ) );
    shared_ptr<City> olathe         = shared_ptr<City>( new City( "Olathe" ) );
    shared_ptr<City> shawnee        = shared_ptr<City>( new City( "Shawnee" ) );
    

    For each of these shared pointers, this is the first reference to its memory address. When we set up neighbors for each city, we create additional references:

    // Set up neighbors
    lenexa->east_neighbor         = overland_park;
    overland_park->west_neighbor  = lenexa;
    lenexa->south_neighbor        = olathe;
    olathe->north_neighbor        = lenexa;
    lenexa->north_neighbor        = shawnee;
    shawnee->north_neighbor       = lenexa;
    

    If these were traditional pointers, the syntax would look the same.

    The shared_ptr class gives us access to a function called use_count(), which we can use to see how many shared pointers are currently pointing to a given memory address. (https://cplusplus.com/reference/memory/shared_ptr/) Using this, we can build out a table that displays each city, its address, and how many references are going to that address:

    cout << setw( 20 ) << "CITY"              << setw( 20 ) << "ADDRESS"      << setw( 20 ) << "USE COUNT"               << endl << string( 80, '-' ) << endl;
    cout << setw( 20 ) << overland_park->name << setw( 20 ) << overland_park  << setw( 20 ) << overland_park.use_count() << endl;
    cout << setw( 20 ) << lenexa->name        << setw( 20 ) << lenexa         << setw( 20 ) << lenexa.use_count()        << endl;
    cout << setw( 20 ) << olathe->name        << setw( 20 ) << olathe         << setw( 20 ) << olathe.use_count()        << endl;
    cout << setw( 20 ) << shawnee->name       << setw( 20 ) << shawnee        << setw( 20 ) << shawnee.use_count()       << endl;
    

    CITY                ADDRESS             USE COUNT
    --------------------------------------------------------------------------------
    Overland Park       0x55f775311eb0      2
    Lenexa              0x55f775311f40      4
    Olathe              0x55f775311fd0      2
    Shawnee             0x55f775312060      2
    

    At the end of the program we don't have to include code like delete lenexa; to free the allocated memory. Since the shared_ptr is a class, the actual pointer is stored within that class, and utilizing the destructor, it will take care of cleaning up the memory for us.

    ---

  • unique_ptr
    

    Documentation: https://cplusplus.com/reference/memory/unique_ptr/

    With a unique_ptr, we create a pointer that is the only "owner" of the memory block it points to. We can move around "ownership" of that address, but only one pointer may point to it. When the owning unique_ptr goes out of scope and is destroyed, it will automatically free the space allocated at the memory address it owns.

    This can be useful for creating a dynamic array but without having to deal with the memory management. Instead of allocating memory in the traditional way like: string* arr = new string[ array_size ];, we can use the unique_ptr:

    unique_ptr<string[]> arr = unique_ptr<string[]>( new string[ array_size ] );
    

    or you could use the auto keyword to make this a little nicer looking:

    auto arr = unique_ptr<string[]>( new string[ array_size ] );
    

    Otherwise, we use this dynamic array similar to with traditional pointers, but we don't need the delete [] arr; at the end of the program:

    for ( size_t i = 0; i < array_size; i++ )
    {
      cout << "Enter value for #" << i << ": ";
      getline( cin, arr[i] );
    }
    

    If you need to change who owns the pointed-to address, the move command can be used:

    // Previously declared:
    // auto arr = unique_ptr<string[]>( new string[3] );
    // auto biggerArray = unique_ptr<string[]>( new string[ newSize ] );
    arr = move( biggerArray );
    

    ---

• Review questions:
  
  1. Given the variable declaration: int num = 10; What kind of memory is the num variable stored in?
  2. Given the variable declaration: int* num = new int; What kind of memory is the num variable stored in?
  3. How do you declare a pointer?
  4. How do you access the address of a variable?
  5. How do you assign the address of a variable to a pointer?
  6. How do you dereference a pointer to display the value of the address it's pointing to?
  7. How do you dereference a pointer to store a new value in the memory block pointed to?
  8. When a pointer is not currently in use, it should be initialized to…