Program 0

Learning to Use CLion/Clang C++, Course Libraries,
GoogleTest, and Checkmate

ICS-46: Data Structure Implementation and Analysis


Introduction This "programming assignment" is designed to ensure that you know how to use -at least in a cookbook way- CLion (for editing,building, running, and debugging C++ programs, after installing the course library), GoogleTest (and driver programs, for testing and locating errors in code), and Checkmate for submitting programs for grading.

You will start this programming assignment similarly to others this quarter.

  • First you will download and unzip the CLion Project Folder named program0.

  • Second you will move the program0 folder into your ClionProjects folder (created when you installed and tested the CLion IDE: see Section 3, Step 1a).

  • Third, you will individually uncomment (only one .cpp file can be uncommented at a time), build (compile and link), and run the driver.cpp program and then the test_queue.cpp program that are in the project0 folder: my code deliberately has an error that you will find and fix.

  • Fourth, when you have corrected the program, you will submit its .hpp file for grading using the Checkmate submission system.
For all later assignments, I will not be providing as much code as I do in this assignment, because the focus of this assignment is using tools, not writing code; the focus of the later assignments is writing code using the tools that you will learn in this assignment. But that assumes that you learn how to use these tools now. There is actually just one error in this code, and this write-up will detail where it is and how to fix it. So the purpose of this assignment is not to fix the error, but instead to become familiar with the tools that you will use throughout the quarter to find and fix errors in your own code.

You may want to print this document and carefully read it, marking any parts that contain important information (for review, before you submit the file); you might want to save the copy you marked-up. Please report any major problems on the Programming Assignments message board (and any minor problems, like typos, to me). I expect you to read this entire document and perform all the operations it describes...maybe even more than once to better learn the tools covered before your first real programming assignment.


Download, Unzip, and
Move the Project Folder
In this section you will download, unzip, and move a project folder into the ClionProjects folder (created when you installed and tested CLion).
  1. Download (onto your desktop) and unzip the following CLion Start Project Folder. Generally if you right-click the .zip file, one of the options available will unzip the file: Izarc and WinZip are two common programs, both further specify an Extract [to] Here option. If you have any problems ask one of the staff for help.

    The resulting unzipped folder contains the .hpp and .cpp files that comprise this programming project, along with its CMakeLists.txt make file, and an input .txt file. The program0 folder contains 6 files:

    • The linear_array_queue.hpp file implements a queue data type using an array (but with one bug).
    • The driver.cpp and driver_queue.hpp files test drives the LinearArrayQueue.
    • The test_queue.cpp file contains a GoogleTest for any implementation of a queue.
    • The CMakeLists.txt file contains a cmake file from which CLion automatically builds a make file when we load this project.
    • The loadq.txt input file contains a few values that are loadable by the lf command in the driver.

    The linear_array_queue file in this project defines an almost correct LinearArrayQueue class that implements the behavior of a queue data type: it is a simpler to understand but less efficient version of the ArrayQueue class supplied in the courselib. A queue is a simple FIFO data type, adhering to the First-in First-out ordering property. Queues enqueue values to their rear and dequeue values from their front, so these are the two "hot spots" that must be efficiently accessed in any data structure that implements a queue. You will be implementing lots of (abstract) data types, like this one, during the quarter.

    We can implement the queue data type efficiently by using either an array or a linked list data structure. The queue type implementation in this programming assignment, LinearArrayQueue, declares the required instance variables and needed methods using an array data structure: the front of the queue is always stored at index 0; the rear is stored at a higher index in the array. Using a linear array is conceptually simple to understand and program, but it has a slower-than-necessary dequeue operation (when compared with using a circular array data structure used in the ArrayQueue class, which we will discuss in the course): it always requires looping through an array, copying each element to its previous index. When all the necessary libraries are installed, this class compiles and can be tested in the driver and via GoogleTest; but the code is not correct, so it results in a few execution/run-time errors.

    In the driver_queue.hpp and test_queue.hpp files, the two lines

      #include "linear_array_queue.hpp"
        typedef ics::LinearArrayQueue<std::string> QueueType;
    choose the linear array queue implementation to drive and test. The standard ArrayQueue in the courselib uses a more complicated but efficient circular array implementation.

  2. Move the entire program0 folder (unzipped above) into the ClionProjects folder (created when you installed and tested CLion).

Start CLion and
Open a Project
  1. Double-click the shortcut to the CLion icon that you created when you downloaded and installed CLion. Watch as the CLion splash screen displays as the CLion IDE is loaded. The standard CLion project window will appear on your screen.

  2. Click the File tab near the upper-left corner of the CLion window; then click the Open option in the pull-down menu, as shown below.

    The following pop-up window should appear on your screen.

    Find and click the program0 project folder (so it is highlighted). You may need to scroll this window and disclose/undisclose various folders to make it appear as shown above. The Users folder should contain a folder with your name (Pattis for me); it should contain a folder with the ClionProjects folder; it should contain the program0 project folder you just moved there, and any three project folders that you created previously (likely courselib, gtestlib, test_all_data_types, and trivialtest).

  3. Click OK.

    The following pop-up window will appear on your screen.

  4. Click This Window.

    CLion will load the project, which includes building the make file for this project from the CMakeLists.txt file in the folder. When it finishes, the following CLion project window should appear on your screen.

    To see the line numbers, right-click in the gray area between the project and the driver.cpp panes and selected Show Line Numbers. To set Show Line Numbers as the default for all edited files, click File and then Settings; disclose Editor, then disclose General; click Appearance and then click the Show line numbers checkbox (illustrated below).


Run the Driver Each data type that we will discuss this quarter has a "driver" program that allows us to "drive it": to call (test) each of its methods and observe the results. In program0, the driver program appears in thedriver_queue.hpp file; it is called from the driver.cpp file.
  1. Uncomment lines 1-6 in the driver.cpp file.

  2. Click the (Run icon) on this window.

    The following CLion project window should appear on your screen.

    The Run pane will display the queue being manipulated (now empty) and the following menu of options that you can use to call/test each queue method.

    Note that this driver tests a queue that stores std::string values. You must enter a string to test any Mutator (Command) or Accessor (Query) method. Of special note is the it command, which constructs and tests an explicit iterator for this queue: it has its own submenu of options applicable to iterators (which are the same for every data type).

    Note that the queue being manipulated prints before the menu using its .str() query, that starts with the data type (here queue) followed by the enqueued values in brackets (separated by commas). Afterwards are all the data members in the implementing class and their values. In a LinearArrayQueue these data members are...

    • ...length: the physical length of its array.
    • ...used: the number of array indexes containing values (always <= length).
    • ...mod_count: counts the number of modifications made to the queue since its construction.

    The < command shows the data type view: just queue[]:rear for an empty queue, which shows the data type view of the queue; whereas the .str() call (shown above the menu) produces more detailed information about the implementation, which is often useful for debugging the implementation.

  3. Issue the m, s, and p commands to query the state of the empty queue. The Run pane should show the following.

    The peek method returns a reference to the queue's first value (which the driver prints); but it cannot work correctly on an empty queue. Notice what is printed instead: the thrown exception (EmptyError) and the Class::method that raised the error. Thus, the driver just ignores this command and we can continue driving the other methods in the LinearArrayQueue class.

  4. Next issue the e command and enqueue test1 when prompted. This method returns the number of values enqueued to the queue (for queues, which can contain duplicate values, it always returns 1; for sets, which cannot contain duplicate values, this method may return 0 if the value is already in the set). The queue now prints (using .str(), before the next menu) as
    queue q = LinearArrayQueue[0:test1](length=1,used=1,mod_count=1)
    which shows...
    • ...the queue now contains at index 0 the value test1.
    • ...the length of the array holding the queue values has increased to 1.
    • ...the queue is using 1 value in the array.
    • ...the queue has been mutated 1 time since being constructed: the previous accessors/queries are not counted because they do not change the queue.

  5. Next issue the e command again and enqueue test2 when prompted. The queue now prints (before the next menu) as
    queue q = LinearArrayQueue[0:test1,1:test2](length=2,used=2,mod_count=2)
    Order is important in queues: the earlier a value is enqueued, the earlier it appears in the array. Notice that both length and used increase to 2.

    Next issue the e command again and enqueue test3 when prompted. The queue now prints (before the next menu) as

    queue q = LinearArrayQueue[0:test1,1:test2,2:test3,3:](length=4,used=3,mod_count=3)
    Notice that length increases to 4 while used and mod_count both increase to 3: generally if there is not enough room in an array, its length is doubled, not just incremented by 1: we will discuss why later in the quarter, when we analyze the running time of performing N enqueues. The Run pane should show the following.

  6. Next issue the d command which should dequeue the value at the front of the queue. It correctly prints dequeue = test1, but when it prints the queue before the next menu, it appears as
    queue q = LinearArrayQueue[0:test2,1:test3,2:test3,3:](length=4,used=3,mod_count=4)
    This result is incorrect because (a) used is still 3. It is OK that test3 now appears in two different queue/array locations (it was shifted one to the left, but still appears at the end). If used were 2, index 2 would not be considered to be in the queue (the two used indexes are 0 and 1). In fact, if you issue the << command it will show as queue[test2,test3,test3]:rear, indicating (incorrectly) that test3 appears in the queue twice.

    If you issue the d command again, it correctly prints dequeue = test2 but used remains 3 and now test3 appears in all three positions in the array. In fact, if you issue the << command it will show as queue[test3,test3,test3]:rear, indicating (incorrectly) that test3 appears in the queue three times.

    If you issue the d command again, it correctly prints dequeue = test3 but used remains 3.

    Notice that mod_count (correctly) increases from 3, to 4, to 5, and finally to 6, because each three dequeue modifies the queue.

    Next issue the s command, and the driver prints 3: although we have dequeued all three values, because of the error the queue thinks its size is still 3.

    Next issue the x command (whose clear method is void and returns -and the driver prints- no result). It will correctly clear the queue, which prints before the final menu as

    queue q = LinearArrayQueue[0:test3,1:test3,2:test3,3:](length=4,used=0,mod_count=7)
    Notice that mod_count (correctly) increases to 7, because clear modifies the queue. Also notice that used is now 0. In fact, if you issue the << command it will show as queue[]:rear, indicating (correctly) that there are no values in the queue.

    The Run pane should show the following.

    So, using this driver, we can call/test all the methods in the LinearArrayQueue class, looking for incorrect behavior.

    If we see errors in the output, to help us debug any errors that we find we can...

    • ...add code in the driver (to print intermediate results) and rerun it.
    • ...add code in the LinearArrayQueue (to print intermediate results) and rerun the driver.
    • ...use the debugger to set breakpoints in our methods and execute/step through the code while observing how it changes its state

    A later section of this document illustrates using the driver with the debugger. For now, continue to explore and experiment with the other commands in this driver, and DO NOT fix the error in delete yet. The lf command allows quickly enqueuing a series of values read from a file (the default it loadq.txt, which is included with this project). Try the it commands to better understand what we can do with iterators (especially how to erase selected values inside the queue).

    If you ever find your program in an infinite loop, you can terminate the program manually by clicking the (Stop icon) on the left of the Run pane. After terminating the driver, click the (Close icon) on the left of the Run pane to close/remove the Run pane.

    To rerun the driver after editing any of these files, click the (Run icon). When CLion re-builds a project it re-compiles all changed files and re-links them into an executable (.exe) file.


Run the GoogleTest
Unit Test
and Debugging
Each data type that we will discuss this quarter also has a GoogleTest for testing its implementation(s). While a driver for a class is code that allows us to manually test its methods and observe their results, a GoogleTest is code that automatically tests the class and report its results. It produces output to show clearly which tests passed and which tests failed; and for the failed tests, it produces more detailed information about how the test failed. When the code is modified (and hopefully corrected), it is very easy to rerun all the tests automatically and observe the changes (hopefully more/all tests are now passing).

To run the GoogleTest program...

  1. Recomment lines 1-6 in the driver.cpp file (because we do not want to run the driver).

    Recall that only one uncommented main function can exist in a C++ project, because there can be only one starting point for the program being run; so we will comment this code and uncomment the code in the test_queue.cpp file.

  2. Uncomment all the code in the test_queue.cpp file.
    1. Double-click the test_queue.cpp file that appears in the Project pane.
    2. Click inside the test_queue.cpp Editor pane to activate editing.
    3. Type the ctrl-a command (command-a on Macs) to select all the lines in this file.
    4. Type the ctrl-/ command (command-a on Macs) to toggle the commenting on the selected lines (uncomment them).

    Before running this project, examine the code in the test_queue.cpp file. It consists of 12 separate tests, each which should be readable and understandable if you understand what queues are about. The actual GoogleTest for implementations of Queue data types is longer; but we use a smaller/simpler file for Programming Assignment #0.

  3. Click the (Run icon) on this window to run the Googletest.

    The Run pane should show the following.

    Check the bottom of GoogleTest's output first. It summarizes the number of passed tests and names the failed tests: you can examine these failed tests in more detail, if they are present.

    Failure Modes

    There are two major failure modes detectable in each GoogleTest.

    • An assertion failure in a test means that the code being tested did not meet its requirements. GoogleTest will print useful information about the failure (just what it prints is based on what kind of assertion failed). In the figure above, both the dequeue1 and dequeue2 tests failed (on lines 221 and 232 respectively); the assertions concerned truth values for calling the q.empty() and q.size() methods, whose different Actual and Expected values are shown.

    • An exception failure in a test means that the code being tested threw an exception. GoogleTest will print information about the exception (although often it just states an unexpected exception was thrown.. In the figure above, no unexpected exceptions were thrown. If one was, it might look as follows:

    In both cases, the GoogleTest records the failure and then continues with subsequent tests.

    In addition, there are two failure modes NOT nicely detectable/reportable in a GoogleTest.

    • An infinite loop: In such a case GoogleTest will stop printing information in the Run pane after starting to run a test. If the enqueue test caused an infinite loop, the Run pane might look as follows. In such a case, you would have to manually stop the program.

      If you ever find your program in an infinite loop, you can terminate the program manually by clicking the (Stop icon) on the left of the Run pane. After terminating the program, click the (Close icon) on the left of the Run pane to close/remove the Run pane.

      By these actions, the GoogleTest will stop and not be performed on subsequent tests.

    • Certain kinds of executions errors (e.g., accessing illegal memory). In these cases, the program will stop executing the GoogleTest.

      Note here that in the middle of RUNing the QueueTest.enqueue, the program terminates.

    When either of these kinds of errors occur, you have a choice of either

    • commenting-out this test code running when the error occurred (so GoogleTest won't run this test, but will run subsequent tests)
    • keeping this test and immediately debugging the code that is causing it to fail.

    If you choose the first approach, remember to uncomment the test code eventually to ensure that your code is passing all the GoogleTests, including this one.

    Debugging Strategies

    Here is a short but important list of four strategies that we can employ when our code fails, to try to understand the cause of the problem (and then hopefully correct it). First, examine the line of code in the test at which the failure was detected (which is printed in the Run pane) and the information it displays related to the failure.

    1. Searching the code for a mistake using the failure information as a guide.

    2. Add arbitrary C++ code in the GoogleTest to print useful information right before the failure line.

    3. Use the debugger to set a breakpoint on the line with the failed assertion (the debugger stops before executing the breakpointed line) and then examine any relevant state.

    4. Use the driver (or any tiny program you write) to duplicate/explore the problem manually.

    GoogleTests

    Generally, each public method has its own GoogleTest, reflecting the semantics (meaning) of what that method does in the class (sometimes needing to call other methods too). It is good to be able to read and understand the GoogleTest code (and you will get more experience doing so during the quarter) because it can be useful to add debugging code to it: typically printing the state of variables just before a test/assertion failed. Mostly GoogleTest code intersperses calls to the methods of the class being tested with assertions about what the results of those method-calls should be: a test method fails when any assertions in it fail.

    The tests are preformed in the order in which they appear. I try to arrange my tests from the simple to the more complex. Sometimes bugs that cause failures in the earlier tests also cause failures in later test. So an important debugging strategy is to concentrate on -and correct- the earlier bugs: at best the later bugs might automatically disappear; at worst it will be easier to understand/correct the later/more complicated bugs after you have understood/corrected the earlier/simpler ones.

    Also note that each test is abandoned when the first assertion fails; it doesn't test subsequent assertions in that test method (but GoogleTest will still attempt to do all subsequent test methods after any detectable failure). This strategy leads to two interesting consequences

    • The output is not cluttered with multiple failure messages for multiple assertions in each test: instead each test either passes or fails; and if it fails, it presents details about only the first failure.

    • Expect that a test might still fail after you make corrections to your code. But, the correction should cause a failure later in that test: e.g., an earlier assertion in the test that failed should now pass, even if a later assertion (which was not reached because of the earlier failure) now is tested and fails.
    Plan on eliminating bugs/failures one at a time, until none are present.

    Debugging Strategy Examples

    Here we will examine the four strategies for debugging stated above. The first failure was on line 221 in the dequeue1 test. The entire test appears as follows, with its line numbers.

      213 TEST_F(QueueTest, dequeue1) {
      214   QueueType q;
      215   load(q,"abcde");
      216   ASSERT_EQ("a",q.dequeue());
      217   ASSERT_EQ("b",q.dequeue());
      218   ASSERT_EQ("c",q.dequeue());
      219   ASSERT_EQ("d",q.dequeue());
      220   ASSERT_EQ("e",q.dequeue());
      221   ASSERT_TRUE(q.empty());
      222   ASSERT_EQ(0, q.size());
      223   ASSERT_THROW(q.peek(),ics::EmptyError);
      224 }

    The error states that the queue was expected to be empty but it was not.

    1. Our first strategy would be just to look at the code in the LinearArrayQueue class. We will see that the empty method returns false when used is not 0. We will also see that used is initialized to 0, and if we enqueue five values (what load(q,"abcde"); does) and then dequeue five values it should return to 0. Since the enqueue test worked, we can focus on the dequeue method to learn why used was not decremented to 0.

    2. Our second strategy would be to add some code in the dequeue1 test to help us understand why the empty method returns false. We could, for example, print the size and even the queue itself (using the more verbose .str() function), using the following code.
      std::cout << "in deqeue1: size = " << q.size() << ", queue = " << q.str() << std::endl;
      I highly recommend putting textual material in these debugging displays, to identify them: as we put more and more debugging displays into a program (which we typically do when debugging) they can become confusing. If we put this code right before the line 221 it would display
      in deqeue1: size = 5, queue = queue[e,e,e,e,e]:rear(length=8,used=5,mod_count=10)
      The queue is supposed to be empty, but its used is 5. It might be useful to put this statement after the call to load and after each call to dequeue() to observe how used changes (in fact, it doesn't). Doing so would produce the following output.
      in deqeue1: size = 5, queue = queue[a,b,c,d,e]:rear(length=8,used=5,mod_count=5)
      in deqeue1: size = 5, queue = queue[b,c,d,e,e]:rear(length=8,used=5,mod_count=6)
      in deqeue1: size = 5, queue = queue[c,d,e,e,e]:rear(length=8,used=5,mod_count=7)
      in deqeue1: size = 5, queue = queue[d,e,e,e,e]:rear(length=8,used=5,mod_count=8)
      in deqeue1: size = 5, queue = queue[e,e,e,e,e]:rear(length=8,used=5,mod_count=9)
      in deqeue1: size = 5, queue = queue[e,e,e,e,e]:rear(length=8,used=5,mod_count=10)
    3. Our third strategy is to use the debugger to set a breakpoint before the failed assertion, and then examine relevant state. The debugger in CLion/C++ (GDB) operates similarly to the Eclipse/Python. We can set unconditional and conditional breakpoints, single step (into, over, and out of) code, observe the values of global and local variables. Experiment with the debugger until you know how to use it to perform common debugging tasks (like those indicated below).

      Try these steps.

      • Double-click the linear_array_queue.hpp file in the Project pane to edit it.

      • Set an unconditional breakpoint on line 222 (the ++mod_count; statement in the dequeue method); recall that when a line has a breakpoint, execution stops before the line is executed.

      • Launch the debugger by clicking the bug icon .

        This rebuilds and starts running the test_queue program, which stops the first time it reaches line 222. When debugging, the Run pane appears in a pop-window.

        And the CLion window shows debugging information (mostly in the Debug pane).

        Here I have disclosed the object pointed to by this in the Variables pane).

        • The code on Line 222 in the linear_array_queue.hpp pane is highlighted in blue, indicating this line is about to be executed.
        • Underneath Thread-1 shows execution starts in the main function in the test_queue.cpp file (at line 301) and goes through a variety of function calls until it reaches the dequeue function in the linear_array_queue.cpp file (at line 222). This is the function call stack, with the top of the stack highlighting in blue the function currently executing.
        • The Variables pane shows the object this refers to and object whose length member is equal to 8, whose used member is equal to 5, and whose mod_count member is equal to 5.
      • Execute the current line (222), by clicking the ,(Step over icon). The result is

        .

        • The code on Line 223 in the linear_array_queue.hpp pane is highlighted in blue, indicating this line is about to be executed.
        • Underneath Thread-1 shows the top of the stack as executing the dequeue function in the linear_array_queue.cpp file (at line 223).
        • The Variables pane shows the mod_count member as changed (it appears in blue) to the value 6.

      I'm hoping that you have had some experience with debuggers in your prior programming classes.

    4. Our fourth strategy would be to use the driver to duplicate/explore the problem manually. Actually, in our discussion of the driver we saw that when we enqueued three values and dequeued all three, the result was a queue whose used was still 3, with the last enqueued values stored in all indexes. Recall that to re-run the driver, we would have to uncomment its code, after commenting-out all the code in the GoogleTest, and then re-run the project code.

    In fact, both test failures relate to a single bug: the used variable was not decremented in the dequeue method: I commented-out the code at line 221 of the linear_array_queue.hpp file. Remember that sometimes fixing one bug will cause many failed tests to pass.

    Restore this line of code (uncomment it) to fix the error. Now rerun this GoogleTest and verify that there are no more failures. The bottom of the Run pane should show

    .

    Originally, both errors and failures indicated that the code is incorrect and should be fixed. Of course, we must be careful because it is possible that an assertion is incorrect: e.g., an assertion asserts the size of the queue is some number but based on the enqueue/dequeue methods called in the GoogleTest it should be some other number. While you should mostly believe the GoogleTests I distribute, there is always the possibility that I have made a mistake. If you look closely at a GoogleTest and don't understand why some failing assertion should be true, please contact me or one of the staff to help resolve the problem.


Submit the Program for Grading via Checkmate After you have fixed the code and verified that it works correctly via the Driver and the GoogleTest, you should submit the code for grading via Checkmate. If you are unfamiliar with this system, read the Submitting Homework Using Checkmate document. It explains how to submit programs, even if you are not officially registered in the class yet.

You are responsible for submitting the correct version of your code before the deadline.


Final Words You are also responsible for backing up your work frequently.

Whenever you have updated your code (and whenever you have finished an assignment) you should backup/save its entire project folder on a USB drive (or in some data cloud). It is better (and just as easy) to zip and backup the entire ClionProjects folder, which will contain all of your projects.

Finally, repeatedly practice doing all the operations covered in this Programming Assignment, until you are familiar with all these skills and can perform them without rereading the directions. You will save yourself much time later in the quarter (when time is really important) if you spend some time now (when things aren't so rushed) mastering this material.