Before You Begin

Pull from the skeleton to get a new lab04 folder.

Make sure to follow the lab setup procedures before proceeding!

Work on the discussion exercise below while waiting for the software to install.

Discussion: Mystery

Draw the box-and-pointer diagram for each of the following mysterious programs.

Then, discuss your solution process. Which parts were particularly tricky or hard to follow along? What strategies were helpful in solving the problem?

public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }

    public static void mystery(IntList L) {
        while (L != null && L.rest != null) {
            L.rest = L.rest.rest;
            L = L.rest;
        }
    }

    public static void main(String[] args) {
        IntList L = new IntList(1, new IntList(2, new IntList(3, null)));
        mystery(L);
    }
}

The first mystery

Visualize Code

public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }

    public static IntList mystery(IntList L) {
        if (L == null || L.rest == null) {
            return L;
        } else {
            IntList p = mystery(L.rest);
            L.rest.rest = L;
            L.rest = null;
            return p;
        }
    }

    public static void main(String[] args) {
        IntList L = new IntList(1, new IntList(2, new IntList(3, null)));
        IntList M = mystery(L);
    }
}

The second mystery

Visualize Code

Introduction

In this lab, you will learn about basic IntelliJ features, destructive vs non-destructive methods, and IntLists.

Your job for this assignment is to run through the debugging exercises and to create methods for IntList.java.

Make sure you’ve followed the setup instructions. After importing, your IntelliJ should look something like the following:

Debugger Basics

Breakpoints and Step Into

We’ll start by running the main method in DebugExercise1.

Open up this file in IntelliJ and click the Run button. You should see three statements printed to the console, one of which should strike you as incorrect. If you’re not sure how to run DebugExercise1, right click on it in the list of files and click the Run DebugExercise1.main button as shown below:

Somewhere in our code there is a bug, but don’t go carefully reading the code for it! While you might be able to spot this particular bug, often bugs are nearly impossible to see without actually trying to run the code and probe what’s going on as it executes.

Many of you have had lots of experience with using print statements to probe what a program is thinking as it runs. At times, print statements can be useful, especially when trying to search for where an error is occurring. However, they have a few disadvantages:

• They require you to modify your code (to add print statements).
• They require you to explicitly state what you want to know (since you have to say precisely what you want to print).
• They provide their results in a format that can be hard to read, since it’s usually just a big blob of text in the execution window.

Often (but not always) it takes less time and mental effort to find a bug if you use a debugger. The IntelliJ debugger allows you to pause the code in the middle of execution, step the code line by line, and even visualize the organization of complex data structures like linked lists with the same diagrams that would be drawn by the Online Java Visualizer.

While they are powerful, debuggers have to be used properly to gain any advantage. We encourage you to do what one might call “scientific debugging”, debugging by using something quite similar to the scientific method!

Generally speaking, you should formulate hypotheses about how segments of your code should behave, and then use the debugger to resolve whether those hypotheses are true. With each new piece of evidence, you will refine your hypotheses, until finally, you cannot help but stumble right into the bug.

Our first exercise introduces us to two of our core tools, the Breakpoint and the Step Over button. In the left-hand Project view, right click (or two finger click) on the DebugExercise1 file and this time select the Debug option rather than the Run option. If the Debug option doesn’t appear, it’s because you didn’t properly import your lab04 project. If this is the case, repeat the lab setup instructions.

You’ll see that the program simply runs again, with no apparent difference! That’s because we haven’t give the debugger anything interesting to do. Let’s fix that by setting a breakpoint.

To set a breakpoint, scroll to the line that says int t3 = 3;, then left click just to the right of the line number. You should see a red dot appear that vaguely resembles a stop sign, which means we have now set a breakpoint.

If we run the program in debug mode again it’ll stop at that line. If you’d prefer to avoid right-clicking to run your program again, you can click the bug icon in the top right of the screen instead.

If the text console (that says things like round(10/2)) does not appear when you click the debug button, you may need to perform one additional step before proceeding. At the top left of the information window in the bottom panel, you should see two tabs labeled Debugger and Console. Click and drag the Console window to the far right of the bottom panel. This will allow you to show both the debugger and the console at the same time.

Once you’ve clicked the debug button (and made your console window visible if necessary), you should see that the program has paused at the line at which you set a breakpoint, and you should also see a list of all the variables at the bottom, including t, b, result, t2, b2, and result2. We can advance the program one step by clicking on the “step into” button, which is an arrow that points down and to the right as shown below:

We’ll discuss the other buttons later in this lab.

Make sure you’re pressing Step Into rather than Step Over. Step into points down and to the right, whereas step over points straight down.

Each time you click this button, the program will advance one step.

Before you click each time, formulate a hypothesis about how the variables should change.

Repeat this process until you find a line where the result does not match your expectations. Then, try and figure out why the line doesn’t do what you expect. If you miss the bug the first time, click the stop button (red square), and then the debug button to start back over. Optionally, you may fix the bug once you’ve found it.

Step Over and Step Out

Just as we rely on layering abstractions to construct and compose programs, we should also rely on abstraction to debug our programs. The “step over” button in IntelliJ makes this possible. Whereas the “step into” from the previous exercise shows the literal next step of the program, the “step over” button allows us to complete a function call without showing the function executing.

The main method in DebugExercise2 is supposed to take two arrays, compute the element-wise max of those two arrays, and then sum the resulting maxes. For example, suppose the two arrays are {2, 0, 10, 14} and {-5, 5, 20, 30}. The element-wise max is {2, 5, 20, 30}, and the sum of this element-wise max is 2 + 5 + 20 + 30 = 57.

There are two different bugs in the provided code. Your job for this exercise is to fix the two bugs, with one special rule: You should NOT step into the max or add functions or even try to understand them.

These are very strange functions that use syntax (and bad style) to do easy tasks in an incredibly obtuse way. If you find yourself accidentally stepping into one of these two functions, use the “step out” button (an upwards pointing arrow) to escape.

Even without stepping INTO these functions, you should be able to tell whether they have a bug or not. That’s the glory of abstraction! Even if I don’t know how a fish works at a molecular level, there are some cases where I can clearly tell that a fish is dead.

Now that we’ve told you what “step over” does, try exploring how it works exactly and try to find the two bugs. If you find that one of these functions has a bug, you should completely rewrite the function rather than trying to fix it.

If you’re having the issue that the using run (or debug) button in the top right keeps running DebugExercise1, right click on DebugExercise2 to run it instead.

If you get stuck or just want more guidance, read the directions below.

Further Guidance (for those who want it)

To start, try running the program. The main method will compute and print an answer to the console. Try manually computing the answer, and you’ll see that the printed answer is incorrect. If you don’t know how to manually compute the answer, reread the description of what the function is supposed to do above, or read the comments in the provided code.

Next, set a breakpoint to the line in main that calls sumOfElementwiseMaxes. Then use the debug button, followed by the step-into function to reach the first line of sumOfElementWiseMaxes. Then use the “step over” button on the line that calls arrayMax. What is wrong with the output (if anything)? How does it fail to match your expectations?

Note that to see the contents of an array, you may need to click the rightward pointing triangle next to the variable name in the variables tab of the debugger window in the bottom panel.

If you feel that there is a bug, step into arrayMax (instead of over it) and try to find the bug.

Reminder: do not step into max. You should be able to tell if max has a bug using step over. If max has a bug, replace it completely.

Repeat the same process with arraySum and add. Once you’ve fixed both bugs, double check that the sumOfElementwiseMaxes method works correctly for the provided inputs.

Conditional Breakpoints and Resume

Sometimes it’s handy to be able to set a breakpoint and return to it over and over. In this final debugging exercise, we’ll see how to do this and why it is useful.

Try running DebugPractice3, which attempts to count the number of turnips available from all grocery stores nearby. It does this by reading in foods.csv, which provides information about foods available, where each line of the file corresponds to a single product available at a single store. Feel free to open the file to see what it looks like. Strangely, the number of turnips seems to be negative.

Set a breakpoint on the line where totalTurnips = newTotal occurs, and you’ll see that if you “step over”, the total number of turnips is incremented as you’d expect. One approach to debugging would be to keep clicking “step over” repeatedly until finally something goes wrong. However, this is too slow. One way we can speed things up is to click on the “resume” button (just down and to the left from the step-over button), which looks like a green triangle pointing to the right. Repeat this and you’ll see the turnip count incrementing repeatedly until something finally goes wrong.

An even faster approach is to make our breakpoint conditional. To do this, right (or two-finger) click on the red breakpoint dot. Here, you can set a condition for when you want to stop. In the condition box, enter “newTotal < 0”, stop your program, and try clicking “debug” again. You’ll see that you land right where you want to be.

See if you can figure out the problem. If you can’t figure it out, talk to your partners, another partnership, or a lab assistant.

Recap: Debugging

By this point you should understand the following tools:

• Breakpoints
• Stepping over
• Stepping into
• Stepping out (though you might not have actually used it in this lab)
• Conditional breakpoints
• Resuming

However, this is simply scratching the surface of the features of the debugger! Feel free to experiment and search around online for more help.

Remember that Watches tab? Why not read into what that does?

Or try out the incredibly handy Evaluate Expressions calculator button (the last button on the row of step into/over/out buttons)?

Or perhaps look deeper into breakpoints, and Exception Breakpoints which can pause the debugger right before your program is about to crash.

We won’t always use all of these tools, but knowing that they exist and making the debugger part of your toolkit is incredibly useful.

Checking Style

We will be using the CS 61B IntelliJ Plugin to check for style.

If you’re ever stuck on style issues, consult the style guide.

When you pass the style check, the output should look like:

Running style checker on 1 file(s)...
Style checker completed with 0 errors

IntLists

Copy over IntList.java from the previous lab into this lab’s folder.

For the next few exercises, we’ll be writing a few additional methods for the IntList class from the previous lab.

The CS 61B plugin adds a powerful feature to the IntelliJ debugger: a visualizer that can draw diagrams just like the Online Java Visualizer. When the debugger is paused on a line, switch to the Java Visualizer tab to draw the diagram.

Exercise: add

Fill in the add method, which accepts an int as an argument and appends an IntList with that argument at the end of the list. For a list 1 2 3 4 5, calling add with 8 would result in the same list modified to 1 2 3 4 5 8.

public void add(int value) {
    // TODO
}

Exercise: smallest

Implement the smallest method, which returns the smallest int that is stored in the list. For a list 6 4 3 2 3 2 2 5 999, a call to smallest would return 2.

public int smallest() {
    // TODO
}

Exercise: squaredSum

Finally, implement the squaredSum method. As the name suggests, this method returns the sum of the squares of all elements in the list. For a list 1 2 3, squaredSum should return 1 + 4 + 9 = 14.

public int squaredSum() {
    // TODO
}

This type of function is called a reducer. In a later lab, we’ll learn how higher-order functions can be used in Java, we’ll see a way to generalize these operations.

Destructive vs. Non-Destructive

Suppose you have an IntList representing the list of integers 1 2 3 4. You want to find the list that results from squaring every integer in your list, 1 4 9 16.

There are two ways we could go about solving this problem. The first way is to traverse your existing IntList and actually change the items stored in your nodes. Such a method is called destructive because it can change (mutate or destroy) the original list.

IntList myList = IntList.of(1, 2, 3, 4);
IntList squaredList = IntList.dSquareList(myList);
System.out.println(myList);
System.out.println(squaredList);

Running the above, destructive program would print,

1 4 9 16
1 4 9 16

Observe that the IntList.of() method makes it much easier to create IntLists compared to the brute force approach.

IntList myList = new IntList(0, null);
myList.rest = new IntList(1, null);
myList.rest.rest = new IntList(2, null);
myList.rest.rest.rest = new IntList(3, null);
// One line of using IntList.of() can do the job of four lines!

The second way is called non-destructive, because it allows you to access both the original and returned lists. This method returns a list containing enough new IntList nodes such that the original list is left unchanged.

IntList myList = IntList.of(1, 2, 3, 4);
IntList squaredList = IntList.squareList(myList);
System.out.println(myList);
System.out.println(squaredList);

Running the above, non-destructive program would print,

1 2 3 4
1 4 9 16

In practice, one approach may be preferred over the other depending on the problem you are trying to solve and the specifications of the program.

dSquareList Implementation

Here is one possible implementation of dSquareList, along with a call to dSquareList.

public static void dSquareList(IntList L) {
    while (L != null) {
        L.first = L.first * L.first;
        L = L.rest;
    }
}

IntList origL = IntList.of(1, 2, 3)
dSquareList(origL);
// origL is now (1, 4, 9)

The reason that dSquareList is destructive is because we change the values of the original input IntList. As we go along, we square each value, and the action of changing the internal data persists.

It is also important to observe that the bits in the origL box do not change, i.e. the variable still points to exactly the same object in memory when dSquareList completes.

Testing dSquareList

To ensure that these ideas all make sense, set a breakpoint in dSquareList and run the IntListTest class. Depending on your IntelliJ setup, a window should pop up giving you multiple options. Choose the IntListTest next to the icon with a red and green arrow contained in a rectangle.

If everything is right, the test should fail because we haven’t implemented dSquareList in our IntList class. Feel free to copy over the provided dSquareList implementation provided above, or write your own dSquareList to pass the test.

Then, use the Java Visualizer plugin to visualize the IntList.

If you don’t understand how the dSquareList method works, discuss with your partner. Pointers and IntLists might seem confusing at first, but it’s important that you understand these concepts!

Note: The choice to return void rather than a pointer to L was an arbitrary decision. Different languages and libraries use different conventions (and people get quite grumpy about which is the “right” one).

Optionally, look at the test method testDSquareList in IntListTest.java. This gives you a feeling for how tests will be written in this course moving forwards.

Non-Destructive Squaring

squareListIterative() and squareListRecursive() are both non-destructive. That is, the underlying IntList passed into the methods does not get modified, and instead a fresh new copy is modified and returned.

public static IntList squareListIterative(IntList L) {
    if (L == null) {
        return null;
    }
    IntList res = new IntList(L.first * L.first, null);
    IntList ptr = res;
    L = L.rest;
    while (L != null) {
        ptr.rest = new IntList(L.first * L.first, null);
        L = L.rest;
        ptr = ptr.rest;
    }
    return res;
}

public static IntList squareListRecursive(IntList L) {
    if (L == null) {
        return null;
    }
    return new IntList(L.first * L.first, squareListRecursive(L.rest));
}

Ideally, you should spend some time trying to really understand them, including possibly using the visualizer. However, if you don’t have time, note that the iterative version is much messier.

The iterative versions of non-destructive IntList methods are often (but not always) quite a bit messier than the recursive versions, since it takes some careful pointer action to create a new IntList, build it up, and return it.

Exercise: Concatenation

To complete the lab, implement dcatenate and catenate as described below. You may find the squaring methods from above to be useful as you write your code.

public static IntList dcatenate(IntList A, IntList B) {
    // TODO
}

public static IntList catenate(IntList A, IntList B) {
    // TODO
}

Both methods take in two IntLists and concatenate them together, so catenate(IntList A, IntList B) and dcatenate(IntList A, IntList B) both result in an IntList which contains the elements of A followed by the elements of B. The only difference between these two methods is that dcatenate modifies the original IntList A (it’s destructive) and catenate does not.

To complete the lab:

• Fill in one of dcatenate() or catenate(), and run them against our tests. Revise your code until it passes our tests.
• Repeat for the method you haven’t yet completed. (We recommend you do one first and finish it before you start the next, because then you’ll be able to take advantage of the similar logic).

IntList problems can be tricky to think about, and there are always several approaches which can work. Don’t be afraid to pull out pen and paper or go to the whiteboard and work out some examples! If you get stuck, drawing out the pointers can probably steer you back onto the path of progress. And, as always, the debugger is a great option!

Feel free to use either recursion or iteration. For extra practice, try both!

It’s also often useful to first think about base cases, such as when A is null, for example. This works especially well for building up a recursive solution. In other words, write up a solution that would work for the base case, then stop and think about how to expand this solution into something that works for other bigger cases.

For this problem, it is okay for dcatenate to return one or the other list if one or both of A and B are null. For catenate, it is okay to attach B to the end of A without making a full copy of B. However, think about and discuss the following two questions with your partner:

• Why does this still produce a ‘correct’ program?
• What kinds of problems could this decision cause?

Discussion: static Methods

At a very high level, we’ve now seen a couple different ways to design methods in Java: either as instance methods or static class methods.

We made the decision to declare the add method from earlier as an instance method.

public class IntList {
    public void add(int value) {
        ...
    }
}

But we could have just as easily declared it as a static method.

public class IntList {
    public static void add(IntList L, int value) {
        ...
    }
}

Why does the static method require us to add an extra argument, IntList L, to the program? How does it affect the way we make a recursive call to the function?

In contrast, we made the decision to declare catenate and dcatenate as static methods. Come up with a couple reasons as to why we made these methods static, and develop an argument about whether it would be better or worse to make them instance methods instead. To some extent, the choice is stylistic so it’s helpful to think about why we might choose one style over the other.

Testing

This section on testing serves as an introduction to some of the work we’ll be doing in the next lab, so it’s okay if you don’t fully complete this part.

Unit testing is a great way to rigorously test each method of your code and ultimately ensure that you have a working project.

The ‘unit’ part of unit testing comes from the idea that you can break your program down into units, or the smallest testable part of an application. Therefore, unit testing enforces good code structure (each method should only do ‘One Thing’), and allows you to consider all of the edge cases for each method and test for them individually.

In this class, you will be using JUnit, a unit testing framework for Java, to create and run tests on your code to ensure its correctness. And when JUnit tests fail, you will have an excellent starting point for debugging. Furthermore, if you have some terrible bug that is hard to fix, you can use git to revert back to a state when your code was working properly according to the JUnit tests.

Skim the first half of A New Way, Chapter 3.1 of the online textbook. This part contains a narrative introduction and motivation to unit testing.

Starting around the halfway mark with Revising findSmallest, read the rest of the chapter more carefully as there are several important ideas, not only about testing but also about writing programs in general.

JUnit Syntax

JUnit tests are written in Java. However, the JUnit library implements all the boring stuff like printing error messages, making test writing much simpler.

The first thing you’ll notice are the imports at the top. These imports are what give you easy access to the JUnit methods and functionality that you’ll need to run JUnit tests. For more information, see the Testing lecture video.

Next, you’ll see that there are several methods that follow the same template in the file.

@Test
public void testMethod() {
    assertEquals(expected, actual);
}

assertEquals is a common method used in JUnit tests. It tests whether a variable’s actual value is equivalent to its expected value.

When you create JUnit test files, you should precede each test method with a @Test annotation. Each test can have one or more assertEquals or assertTrue methods (provided by the JUnit library).

All tests must be non-static. This may seem weird since your tests don’t use instance variables and you probably won’t instantiate the class. However, this is how the designers of JUnit decided tests should be written, so we’ll go with it.

From this point forwards, we will officially be working in IntelliJ. If you want to run your code from the terminal, refer to this supplemental guide from Spring 2018. While you’re welcome to do this, the staff will not provide official support for command line compilation and execution.

IntelliJ Tips

In lecture, Christine discussed a few handy IntelliJ tips and tricks.

• Take advantage of autocompletion, auto-import, and quick fixes with Alt + Enter.
• Use automatic code generation with Alt + Insert or Command + n on macOS.
• Use live code to save time on typing with Ctrl + j or Command + j on macOS.
  • Some favorites are: sout, psvm, inn, fori.
• Reformat code to save time style checking with Ctrl + Alt + l or Command + Alt + l.
  • You can also get it from the Code -> Reformat Code menu.
• Utilize breakpoints and the debugger to quickly find bugs.
  • Inspect variables.
  • Inspect the call stack.
  • Follow execution with step into, step over.
  • Do binary search.
  • Use the built-in Java visualizer to help draw box-and-pointer diagrams.

Recap

In this lab, we discussed,

• Stepping into, over, and out inside the IntelliJ debugger.
• Destructive vs. non-destructive methods.
• Lists and pointers.
• Writing IntList methods destructively, non-destructively, recursively, and iteratively.
• Introduced the idea of testing our code with unit tests.

Deliverables

Submit a finished IntList.java with implementations for add, smallest, squaredSum, catenate, and dcatenate. This lab also contains a short onilne assessment via Gradescope, which also contains the link to this week’s self-reflection. Make sure to copy down the magic word that you receive upon submission of the self-reflection as you’ll need it to receive full credit for this lab.

Frequently-Asked Questions

Things like String or String.equals() are red!

This is a JDK issue, go to File > Project Structure > Project > Project SDK to troubleshoot. If your Java version is 9.0, then you should have a 9.0 SDK and a Level 9 language level.

Things like @Test are red!

You forgot to add your libraries. You have to add your libraries every time you start a new project!

Console button isn’t showing up!

That’s because you didn’t compile successfully. Usually, it’s because you did not add your libraries.

Java files have a red circle, with a J inside the circle, next to the file icon

Right-click the folder containing that Java file, then Mark as -> Sources Root.