Lab 07 – Javadoc and More List Exercises

Java documentation style

The Java Development Kit (JDK) comes with a tool called JavaDoc. This tool will generate documentation for Java source code with comments written in accordance with the Java documentation style. The following links show more examples. You do need to spend time outside of the lab to study them.

The following is a very short summary of the Javadoc conventions.

Creating javadoc using DrJava:

DrJava has incorporated the javadoc utility into its IDE. Since javadoc does not know anything about language levels, we will delay running the javadoc utility on our code until we switch to the Full Java language.

For the "daring", you can try the following steps at your own risk!

Now change the javadoc Access level in the javadoc Preferences to private and generate javadoc again. What is the difference?

More List Exercises

Recall our object model (common known in the Scheme world as "data definition") for lists of int.

The above can be implemented in Java using the composite design pattern as follows.

/** Abstract list structure. */
abstract class IntList {
}

/* Concrete empty list structure containing nothing. */
class EmptyIntList extends IntList {
}

/** Concrete non-empty list structure containing an int, called first, and a rest, 
  * which is a list structure. */
class ConsIntList extends IntList {
    int first;
    IntList rest;
}

The above composite design for IntList gives rise to the interpreter design pattern for coding list methods. Here is the coding template.

abstract class IntList {
    abstract returnType methodName(parameter_list); // returnType may be Void
}

class EmptyIntList extends IntList {
    returnType methodName(parameter_list) {
        // base case code
    }
}

class ConsIntList extends IntList {
    int first;
    IntList rest;
    returnType methodName(parameter_list) {
        // ... first ...
        // ... rest.methodName(parameter_list)...
    }

}

A Scheme-like String representation of lists.

Suppose we want to display an empty list as () and the list containing 1, 2, 3 as (1, 2, 3) . How do we do this? We need to add a method to the InList hierarchy of classes to perform this computation. Let's call this method listString() and let's proceed together.

Step 1: Instantiate the interpreter code template given above by replacing returnType with String , the methodName with listString and the parameter_list with nothing. Be sure to create one file for each class. The code will not compile. Why?

Step 1.5: Add syntactically correct code to the template so that the whole thing compile.

Step 2: Write appropriate JUnit test classes. Because of lack of time, we will not do this step in class.

Step 3: Write the code for listString in EmptyInstList . This is trivial! Make sure it passes the JUnit test though!

Step 4: Write the code for listString in ConsIntList . You can try the structural recursive code given in the template and see that it will not work. This is because by the time you reach the end of the list (i.e. when rest is the empty list), you need to do something different from what EmptyIntList . listString() is programmed to do. You will need to call on rest to perform an auxiliary ("helper") method to get the job done. Let's call this helper method listStringHelp .

What does listStringHelp need to know? You can pass to it what you (as the current list) know and ask rest to complete the job. What does the current list know? It knows it can build the string "(" + first (meaning "(" concatenate with the default String representation of =first=) and it can pass this string to the helper method. So in effect the helper takes as parameter the accumulated string representation of the list so far and delegates the job for completing the final string representation to rest.

The code for ConsInList.listString() is thus something like:

return rest.listStringHelp("(" + first);

The code will not compile because we have yet to add the method listStringHelp to the IntList hierarchy.

Step 5: Add the method String listStringHelp(String acc) to the IntList hierarchy; add stub template code so that the whole thing compile. Unless you accidentally write the correct code, the JUnit test for ConsIntList will not pass still.

Step 6: Write JUnit test code for listStringHelp . Again, due to lack of time, we will not do that here in the lab. Actually, more than often, writing the test code will help write the code for the method in question.

Step 7: Write the code for EmptyIntList.listStringHelp(String acc) What should the empty do here? It knows it has the accumulated string representation of the whole list so far and that all it needs is the closing parenthesis. So all it has to do is to add the closing parenthesis to the accumulated string and return: return acc + ")"; (And make sure it passes the JUnit test).

Step 8: Write the code for ConsIntList.listStringHelp (and make sure that it passes the JUnit test). What can a non-empty list do here? All it needs to do is to concatenate a comma and its first to the accumulated string representation so far and pass it on to rest to complete the job: return rest.listStringHelp(acc + ", " + first); (And make sure it passes the JUnit test).

Note that the code for listStringHelp is tail-recursive.

Step 9: Run the complete JUnit test suite and the whole thing should pass!

Here is the solution code.

abstract class IntList {
    /** Computes a String representation of this list wiht matching parentheses
      * as in Scheme.  For example, the list containing 1, 2 and 3 should return
      * (1, 2, 3) and the empty list should return ().
      * @return a non empty String consisting of elements in this list enclosed
      * in a pair of matching parenthesis, separated by commas.
      */
    abstract String listString();

    /** Accumulator helper method for listString to compute the String
      * required representation of this list given the accumulated
      * String representation of the preceding list.
      * @param acc the accumulated String representation of the list that
      * precedes this list.
      * @return a non empty String consisting of elements in this list enclosed
      * in a pair of matching parenthesis, separated by commas.
      */
    abstract String listStringHelp(String acc);
}


class EmptyIntList extends IntList {

    /** @return "()"*/
    String listString() { return "()"; }
    /** @param acc the accumulated String representation of the list that
      * precedes this list.  For example "(5, 3"
      * @return a non empty String consisting of elements in this list enclosed
      * in a pair of matching parenthesis, separated by commas.  For example,
      * "(5, 3)"
      */
    String listStringHelp(String acc) { return acc + ")"; }
}

class ConsIntList extends IntList {
    int first;
    IntList rest;

    /** Calls on rest to perform the helper method listStringHelp passing it
      *   the accumulated String representation so far, which is "(" + first.
      * @return a non empty String consisting of elements in this list enclosed
      *    in a pair of matching parenthesis, separated by commas.
      */
    String listString() { return rest.listStringHelp("(" + first); }

    /** @param acc the accumulated String representation of the list that
      *   precedes this.  For example "(5, 3"
      * @return a non empty String consisting of elements in this list enclosed
      *   in a pair of matching parenthesis, separated by commas.  For example,
      *   "(5, 3)"
      */
    String listStringHelp(String acc) { return rest.listStringHelp(acc + ", " + first); }
}

/** Testing empty lists. */
class TestEmptyIntList extends TestCase {

    void test_listString() {
        EmptyIntList mt = new EmptyIntList();
        assertEquals(mt + ".listString()", "()", mt.listString());
    }
}

Lab Exercises

  1. Write another version of listString that is tail recursive. Call it listString2 . (Can you think of a non-tail recursive version?)
  2. Write a method called prodNums that returns the product of the number in the list, using a tail recursive helper method.
  3. Revise the preceding definition to terminate immediately if it encounters a 0 in the list of numbers being multiplied.
  4. Write a method called makePalindrome that returns a list consisting of the input list and its mirror around the last element, using a (non tail-recursive) helper with an accumulator. For example, (1, 2, 3).makePalindrome () returns the list (1, 2, 3, 2, 1) .
  5. Write a method called reverse that reverses the list using a tail-recursive helper.

Access Permissions: (Please don't edit)