A. Intro

Download the code for Lab 5 and create a new Eclipse project out of it.

Learning Goals for Today

From now on you can work with whatever partner you want. Stick with one person or continue to mix it up; it's your choice.

The exercises for this lab almost all involve arrays, first in isolation, then as an instance variable of a "collection class". There are also some exercises on the for statement.

There are common array operations. In pseudocode:

• process all the elements of an array
• search for an array element (starting with the first, then examining the second, third, and so on)
• insert an element into an array at a given position
• delete the element at a given position in an array
• combine two arrays

(All the collection classes that form the java.util library also implement these methods.)

The lab exercises provide practice generating code to implement and test these operations, and a couple of buggy implementations as a change of pace.

B. For Statements

The For Statement

The for statement provides another way in Java to repeat a given program segment. It starts with for, continues with loop information inside parentheses, and ends with the loop body, the segment to be repeated, enclosed in curly braces.

for (loop-information) {
    loop-body;
}

Loop information consists of initializations, a test, and increments. These three sections are separated by semicolons, and any of these may be omitted. If there is more than one initialization or increment, they are separated by commas. If the test succeeds, the loop continues.

for (initialization; test; increment) {
    loop-body;
}

Loop execution proceeds as follows:

1. Initializations are performed.

2. The test is evaluated.

   • If it is false, the loop is finished and execution continues with the code following the for loop.
   • If it is true, the loop body is executed, increments are performed, and we loop back to step 2. (Note: We never re-initialize.)

Local variables may be declared in the initialization section of the loop.

The following loops are several equivalent ways to compute n factorial (the product of all the positive integers up through n).

• Two initializations in loop-information

  for (int k = n, product = 1; k > 0; k = k - 1) {
      product = product * k;
  }

• Product initialized outside for loop

  int product = 1;
  for (int k = n; k > 0; k = k - 1) {
      product = product * k;
  }

• Decrement performed inside the loop-body

  int product = 1;
  for (int k = n; k > 0; ) {
      product = product * k;
      k = k - 1;
  }

• While loop equivalent

  int product = 1;
  int k = n;
  while (k > 0) {
      product = product * k;
      k = k - 1;
  }

As the last equivalent loop demonstrates, the for loop is basically a repackaged while loop that puts all the information about how long the loop should continue in one place. Thus, a for loop is generally easier to understand than an equivalent while loop.

Note: Head First Java describes for loops on pages 112 and 113.

Local Variable Scope

Variables may be initialized in the loop information and the loop body. It is important to note that all of these variables initialized within the loop will no longer be accessible once the program exits the loop.

This is explained by the concept of variable scope in Java. A local variable has a scope that limits it within the class, method, and loop (if applicable) it was declared in. The local scope of a variable is limited by the smallest scope that applies to it. Scope is important because variables can only be used within their scope.

Let's work through some examples. Firstly, if a variable is defined within a class but outside of any methods or loops, it can be accessed throughout the class.

Secondly, if a variable is defined within a class method but outside of any loops, it exists throughout the whole method (after it was initialized), but other methods do not have direct access to the variable.

Finally, if a variable has been created within a loop, its most limiting scope is the loop. Thus, it can only be used within the loop.

Note: It is okay if scope does not immediately make sense. It will become more clear as your write more code. This page may also be a helpful resource for understanding local scope. Our book Head First Java also briefly covers scope on page 259. If you have any questions, feel free to ask your TA.

Exercise: While-to-For Translation

Either do these with your partner, or compare notes with them after you complete them. Translate the following while loops to for loops. The body should contain only the call to println.

1.

int k = 0;
while (k < 10) {
    System.out.println(k);
    k = k + 1;
}

2.

int k = 0;
while (k < 10) {
    k = k + 1;
    System.out.println(k);
}

Nested For Loops

Here is the triangle drawing code you created in a previous lab exercise using while loops (top) and for loops (bottom). Confirm that these are identical.

while loops

int row = 0;
while (row < 10) {
    int col = 0;
    while (col <= row) {
        System.out.print('*');
        col = col + 1;
    }
    row = row + 1;
    System.out.println();
}

for loops

for (int row = 0; row < 10; row = row + 1) {
    for (int col = 0; col <= row; col = col + 1) {
        System.out.print('*');
    }
    System.out.println();
}

Shortcuts for Incrementing/Decrementing

Let k be an integer variable. Then the three following statements are equivalent in that they all increment k.

k = k + 1;
k += 1;
k++;

Similarly, these three statements all decrement k by 1.

k = k - 1;
k -= 1;
k--;

Note: The motivation for this shorthand notation is that the operations of incrementing and decrementing by 1 are very common. While it is legal to increment or decrement variables within larger expressions like

System.out.println(values[k++]);

this is a risky practice very susceptible to off-by-one errors. Therefore, we ask that you only use the ++ or — operations on lines by themselves.

For Statements with Arrays

For statements work well with arrays. Consider, for example, an array named values. It is very common to see code like the following:

for (int k = 0; k < values.length; k += 1) {
    // process values[k]
}

The Break Statement

The break statement "breaks out of" a loop (both for and while loops). In other words, it stops the execution of the loop body, and continues with the statement immediately following the loop. An example of its use would be a program segment that searches an array named values for a given value, setting the variable found to true if the value is found and to false if it is not in the array.

for (int k = 0, found = false; k < values.length; k++) {
    if (values[k] == value) {
        found = true;
        break;
    }
}

This break statement allows us to save time. If we find the value within the array before the end, we don't waste more time looping through the rest of the array.

However, the break statement is not always necessary, and code with a lot of breaks can be confusing. Abusing the break statement is often considered poor style. When using break, first consider if it would be more appropriate to put another condition in the test, instead.

The Continue Statement

The continue statement skips the current iteration of the loop body, increments the variables in the loop information, then evaluates the loop test. This example checks how many 0s there are in array values:

int count = 0;
for (int i = 0; i < values.length; i++) {
    if (values[i] != 0) {
        continue;
    }
    count += 1;
}
System.out.println("Number of 0s in values array: " + count);

Similar to the break statement, the continue allows us to save time by skipping sections of the loop. In this case, the continue allows us to add to the count only when there is a 0 in the array. Removing continue will give an incorrect output.

The difference between break and continue is that break immediately stops the loop and moves on to the code directly following it. In comparison, continue stops going through the loop body but continues going through the loop according to the loop information.

Like with break, abusing continue is often considered poor style. Try not to go crazy with nested breaks and continues.

Self-test: Nonstandard For Loop

What output is produced by the following program segment? We strongly recommend that you use a table to keep track of the value of k.

for (int k=1; k<10; k=k+1) {
    // increment is not normally done in both places
    k = k + 1;
    System.out.print (k + " ");
}
System.out.println ( );

C. Arrays

Exercise: Insert & Delete

Look at the files ArrayOperations.java and ArrayOperationsTest.java.

Fill in the blanks in the ArrayOperations class. Your methods should pass the tests in ArrayOperationsTest.

Note: Before trying to program an algorithm, you should usually try a small case by hand. For each of the exercises today, work with a partner to do each algorithm by hand before writing any code.

• The insert method takes three arguments: an int array, a position in the array, and an int to put into that position. All the subsequent elements in the array are moved over by one position to make room for the new element. The last value in the array is lost.

For example, let values be the array {1, 2, 3, 4, 5}. Calling

insert(values, 2, 7)

would result in values becoming {1, 2, 7, 3, 4}.

• The delete method takes two arguments: an int array and a position in the array. The subsequent elements are moved down one position, and the value 0 is assigned to the last array element.

For example, let values be the array {1, 2, 3, 4, 5}. Calling

delete(values, 2)

would result in values becoming {1, 2, 4, 5, 0}.

For now don't worry about the methods being called with incorrect input.

Note: You'll need your insert and delete methods later in this lab, so remember to save them for future reference!

Discussion: Testing Insert

A student says that only one test case of insert is necessary, namely insertion into the middle of the array. Argue with this student.

Exercise: Zip

Add a method named zip to the ArrayOperations class. Given two int arrays array1 and array2 of the same length, zip should return an array result that is twice as long, in which the elements of array1 and array2 are interleaved.

That is, result[0] is array1[0], result[1] is array2[0], result[2] is array1[1], and so on. The zip method should not change its arguments.

Here is a testZip method to copy into the ArrayOperationsTest class.

public void testZip() {
    int[] array1 = {1, 2, 3};
    int[] array2 = {4, 5, 6};
    int[] zipResult = {1, 4, 2, 5, 3, 6};

    // Test 1: zipResult returns correctly interleaved array.
    check(ArrayOperations.zip(array1, array2), zipResult);

    // Test 2: zipResult does not change the arguments.
    int[] array1copy = {1, 2, 3};
    int[] array2copy = {4, 5, 6};
    check (array1, array1copy);
    check (array2, array2copy);

    // Test 3: zipResult works on boundary case.
    check (ArrayOperations.zip(new int[0], new int[0]), new int[0]);
}

Discussion: Opportunities for Errors

What errors did you encounter in working through the array exercises? If you did not encounter any errors, suggest some possible errors that you were careful to avoid.

D. Collection Classes

Sets & Sequences

Collection classes represent collections of data. Most of the data structures we will study the rest of this class are used to represent collections. The most commonly used collections are sets and sequences.

Set (unordered)

Sets support (at least) the following operations:

1. Initialization (with a constructor)
2. Adding an element to the set if it's not already there
3. Removing an element from the set
4. Checking whether a given item is in the set
5. Checking whether the set is empty

A set has weaker requirements than sequences and therefore has more implementation alternatives. For example, a set of nonnegative integers may be represented as a boolean array with element k being true if k is in the set and false otherwise.

Sequence (ordered)

Sequences differ from sets in that elements have positions within in the sequence. Thus, they support the following operations:

1. Initialization (with a constructor)
2. Adding an element at a given position or at the end of the sequence
3. Removing an element at a given position or at the end of the sequence
4. Identifying the position of a given element of the sequence
5. Checking whether the sequence is empty

Implementation of a sequence normally involves storing the elements of the sequence explicitly. One might use an array whose 0th element is the first sequence item, and so forth.

Collection Constructors

There are several ways to initialize instance variables (as detailed in our readings from Head First Java):

1. Using assignments in the main method (chapters 2-4)
2. Using "setter" methods (chapters 4, 5)
3. Using constructors (chapter 9)

In general, the most preferable by far of these ways is the last one. By convention, the constructor of a class initializes the instance variables of the class in such a way that the resulting object is internally consistent and complete.

Self-test: Constructor Contents

We are representing a set of nonnegative integers as a boolean array as just described. The constructor will be passed the largest integer to be stored in the set as an argument. Which of the following will the constructor contain?

Exercise: Complete a Set Implementation

If one partner has been coding for the whole lab, switch places.

The file Set.java contains the framework of a Set class that uses an array of booleans as previously described. The file SetTest.java is a JUnit test class for this class. You will complete and test the Set class.

This version of the Set class can represent a Set of non-negative numbers. It uses a boolean array to keep track of what values are in the Set. Check the example below:

E. IntSequence Class

Main Idea

Now consider a class to represent a sequence of an arbitrary number of integers, both positive and negative. An array is a reasonable implementation of the sequence. However, arrays in Java (unlike lists in Python) cannot grow or shrink in size, so we will need to start out with as much room as we think we will need. Thus, we should choose to start the array with a size greater than zero or one (perhaps something like 20).

However, this creates another concern because arrays of integers begin filled with zeros. Thus, we won't be able to tell the difference between a value zero in our sequence and a zero that is simply the default value the array was initialized with.

A solution is to store a counter int as an instance variable. The counter will tell us how many elements were placed into the array (i.e. how much of the array contains actually important integers). The rest of the array's contents do not matter. They can be 0 or any other number.

We implement this solution in a class named IntSequence. A partially filled example is pictured below. The shaded array cells represent default values. If the code is working correctly, the values in the shaded cells should never be examined.

Exercise: IntSequence constructor

Fill in the constructor in the IntSequence framework code below into the IntSequence class.

public class IntSequence {

    // instance variables
    private int[] myValues; // sequence elements
    int myCount;            // number of array cells used by the sequence

    // constructor
    // capacity: actual size of the array or the (temporary) maximum
    // number of elements it can hold
    public IntSequence (int capacity) {
        // YOUR CODE HERE
    }

    // other methods would go here

}

Simple IntSequence methods

Add the following three methods to the IntSequence class:

1. public boolean isEmpty()

returns true when this sequence is empty and returns false otherwise

1. public int size()

returns the number of values in this sequence

Note: There is a distinction between size and capacity.

1. public int elementAt(int pos)

returns the value at the given position in the sequence

e.g. If the sequence contains 3, 1, and 4, elementAt(0) returns 3.

Note: If someone asks for the elementAt an index that does not exist, you should call System.err.println and include a description of the error and call System.exit(1) to exit the method. The same is true for any case where a method is called with incorrect input.

IntSequence add method

Make an add method for the IntSequence class. This method appends its int argument to the stored integer sequence. The argument integer will be placed in the first unused stop in the array, as shown in this following example, where 9 is added to myValues.

// Add the argument to the sequence by placing it in the first
// unused spot in the array and incrementing the count.
// Assume that the sequence isn't full.
public void add (int toBeAdded) {
    // YOUR CODE HERE
}

Note: If there is no more open spots in the array call System.err.println("") and include a description of the error and call System.exit(1) to exit the method. From now on we are going to assume you'll do your own error checking to handle cases like these.

IntSequence toString Method

Supply a toString method for the IntSequence class. It will return a String that contains the elements of the sequence separated by blanks. Please make sure that there is just one space between each element, and no trailing spaces on either side of the string.

You now have enough of the IntSequence to write a JUnit test. Use assertEquals with the toString method to examine the contents of a sequence. Write tests for the other IntSequence methods you've written.

Test Driven Development

In the next few steps you'll be doing some test driven development because thinking through all the edge cases for the method is really the hard part. Once you know all the edge cases you need to handle, writing code that works will be much easier. Only after you have written the tests for a method will you complete the method.

Test-Driven Development for Remove

First, if you haven't recently switched which of the two partners is coding, do so now.

Consider a method named remove that, given the position of the sequence element to remove as an argument, removes the specified element and returns it. In the following example, the element myValues[2] is removed:

Note: The myValues[6] does not necessarily have to be 9. It could for instance be 0 or any other number because myCount is 6. That array position can hold garbage. Leaving it as 9 is just one possible implementation your method could use.

Devise JUnit tests to test the remove method, and add them to your IntSequenceTest.java file.

Now that you've written tests, rename the delete method you wrote at the beginning of the lab to remove and adapt it to be a method of the IntSequence class. This modified function should pass the JUnit tests you just wrote previously.

Test-driven development for insert

Now create tests for an insert method that, given an integer and a position in this sequence at which to insert it, moves all the later sequence elements over to make room for the new element, then copies the integer into the appropriate place. Add the tests to your IntSequenceTest.java file.

Self-test: Buggy insert method

The following insert method has a bug. We hope your tests from the preceding step would catch it.

// Insert toInsert into the sequence at position insertPos,
// shifting the later elements in the sequence over to make room
// for the new element.
// Assumptions: the array isn't full, i.e. myCount < myValues.length.
//   Also, insertPos is between 0 and myCount, inclusive.
public void insert (int toInsert, int insertPos) {
    for (int k=insertPos+1; k<=myCount; k++) {
        myValues[k] = myValues[k-1];
    }
    myValues[insertPos] = toInsert;
    myCount++;
}

Suppose that myValues currently stores the following numbers (in order):

1 2 3 4 5 6 7

What does myValues contain after the call insert(100, 4)? (You should just write out the numbers with spaces between them)

IntSequence insert method

Adapt your insert method from earlier in the lab to be a method of the IntSequence class. The insert method will take two arguments: the integer value to insert into the sequence, and the position at which that value is to be inserted.

Test-Driven development for contains

Add tests to your IntSequenceTest.java file to call a contains method. Given an int argument — we'll call it k — contains returns true if k is one of the elements of this sequence, and returns false otherwise. Then implement your contains method and run the tests.

F. Conclusion

Read the following:

• HFJ chapters 7 and 8
• HFJ appendix B sections 2 and 7

By now, your IntSequence class should have the following public methods implemented:

• public boolean isEmpty()
• public int size()
• public int elementAt(int pos)
• public void add(int toBeAdded)
• public String toString()
• public int remove(int pos)
• public void insert(int toInsert, int pos)
• public boolean contains(int k)

For this lab, you will need to submit the following files:

• ArrayOperations.java
• Set.java
• IntSequence.java
• IntSequenceTest.java

Submit these files as lab05. Make sure to keep your IntSequence files as we'll be re-visiting them in a later lab.

FAQ

Q: Sometimes we call System.exit(1). How can we test this in JUnit?

A: You won't be able to test this in JUnit. In the future, we will cover exceptions, which you will allow you to test for these occurrences.