CS 112 Summer 01 2013-- Homework Three

Due Thursday, June 6th at 12 Midnight

Introduction

This homework consists of two problems which have the following goals:

• Continue to develop an understanding of object-oriented design in Java using the Client-ADT model;
• Gain practice in creating code that works with other code that you did not write (I will be providing an interactive client which uses both of these classes);
• Gain practice in using a generic class, in this case the Node class;
• Learn about error handling using exceptions (we will talk about this on Tuesday this week);
• Learn how to create a "static container" ADT for static methods;
• Learn how how to manipulate linked lists using iterative and recursive algorithms; and
• Continue to practice step-wise refinement in developing your code.

Problem One: Creating a String Library (50 points)

In this problem, you are going to write a class MyString which contains both static and non-static members to manipulate strings of characters, modeled on the Java String class, but implemented using linked lists of nodes which contain single characters. You will use iterative algorithms to manipulate these linked lists to implement an important subset of methods from the Java String class. Here is the interface you must implement, which you should put in a class Stringy.java:

/* File: Stringy.java
 * Date: 6/1/13
 * Author:  Wayne Snyder (snyder@bu.edu)
 * Class: CS 112, Summer 01 2013
 * Assignment:  HW 03
 * Purpose: This is an interface specifying a subset of the methods for the Java String class; these
 *       will be implemented using linked lists of characters. 
 * Related classes:  MyString.java
 */

public interface Stringy {
   
   public char charAt(int index);                     // Returns the char value at the specified index.
   
   public int compareTo(MyString anotherMyString);    // Compares two MyStrings lexicographically. Google to find out
                                                      // exact semantics. 
   
   public MyString concat(MyString str);              //  Concatenates a copy of the specified MyString to the end of this MyString.
                                                      //  If str is empty, just return this MyString; otherwise, make a copy
                                                      //  of this MyString and append a copy of str to it. 
                                              
   public MyString replace(char oldChar, char newChar);  // if oldchar does not occur in this MyString, return this;
                                                         // else make a copy of this MyString and replace all occurrences
                                                         // of oldChar by newChar
   
   public int indexOf(int ch);                 // Returns the index within this MyString of the first occurrence of the specified character.
   
   public int indexOf(MyString str);           // Returns the index within this MyString of the first occurrence of the specified substring.
   
   public int length();                        // Returns the length of this MyString.
   
   public MyString substring(int beginIndex, int endIndex);  // Returns a new MyString that is a substring of this string.
   
   // Java doesn't allow static methods in interfaces, but if it did, the two static methods you have
   // to implement would look like this:
   
   //  public static MyString valueOf(int i);  // Returns the MyString representation of the int argument.
   
   //  public static int parseInt(MyString s) throws NumberFormatException;  
                                                 // Returns the integer corresponding to the MyString argument
                                                // or an exception if input is ill-formed
}

The objective here is to provide implementations of these standard String methods, but for your own MyString class. Any question about how your methods should behave can be answered by looking up the corresponding String method and playing around with it a bit---your objective is to have exactly the same functionality. The last method, parseInt(..), is actually a static member of the Integer class, but we will provide it as part of the MyString class. In addition to these methods, you must provide the following two methods which are not listed in the interface:

        public String toString() { ..... } ;   // Convert this MyString to a regular Java String -- thus, when you simply use your MyString in a place where a String is
                                               //      expected, it will simply convert to a String automatically. 

        public MyString(String str) { ..... };   // The constructor for a MyString; it should take a normal Java String and construct a MyString

All questions about functionality (with an important restriction stated below) can be answered by looking up the documentation for Java Strings; in addition, you MUST adhere to the following requirements:

• The MyString class must implement the Stringy interface;
• The data in a MyString will be represented by a linked lists of nodes each containing a single Java char;
• You may not use recursion;
• The Node class must be written as a private static "inner class" (we will discuss this on Monday--but it is a simple idea: just define the Node class as a member of MyString);
• No method may call another method as a "helper" (just write out every method "from scratch") [a word of explaination: this restriction is for efficiency but also to make you practice your linked lists---if you could use helpers, then you can, e.g., write the charAt(..) method using linked list algorithms, and then every other method could be written in terms of charAt(...) without practicing linked lists---not useful for learning purposes!]
• The exception to the requirement that this class simulate the String class is that you need not worry about error checking, except for the parseInt(...) method, which checks to see if the input string is legal (i.e., a string of digits, possibly preceeded by a minus sign '-'); if it is not legal, it throws an unchecked exception as shown (we will talk about this in class on Tuesday);
• Your code must work with the interactive client BigIntegerCalculator.java which I will provide;
• You must write a Unit Test main method to verify that your code works properly; the way to do this is to write one method at a time, and compare how it works with the same method for the String class. Make sure that you test all the cases (empty strings, non-empty strings, basically every signficiant combination of inputs, and in the parseInt, check for positive and negative integers and illegal inputs, e.g., "1a34"). For example, here is how I would test the parseInt(...) method:

      int x = Integer.parseInt("234"); 
      int x1 = MyString.parseInt(new MyString("234")); 
      System.out.println(x);
      System.out.println(x1);
      System.out.println(); 
      int y = Integer.parseInt("-234"); 
      int y1 = MyString.parseInt(new MyString("-234")); 
      System.out.println(y); 
      System.out.println(y1);
      System.out.println(); 
      
      try {
          int z = Integer.parseInt("2a34"); 
      }
      catch(NumberFormatException e) {
         System.out.println(e.getMessage()); 
      }
      
      try {
          int z1 = MyString.parseInt(new MyString("2a34")); 
      }
      catch(NumberFormatException e) {
         System.out.println(e.getMessage()); 
      }

234
234

-234
-234

For input string: "2a34"
For input string: "2a34"

Problem Two: Adding Big Integers (50 points)

You are going to write several recursive methods for manipulating linked lists representing positive integers of unbounded size. In this scheme, an integer such as 234345 is represented by nodes containing integer items which are 0 -- 9 (i.e., digits). In order to accomodate the usual procedure for adding (which proceeds from right to left), we will reverse the list of digits so that the least-significant digits are at the beginning of the list, e.g.,

               -> 5 -> 4 -> 3 -> 4 -> 3 -> 2 -> .      equals         234345
 

Unfortunately, you can not define static methods in an interface, so we won't be using an interface for your solution class in this assignment. You must write a class BigInt which contains the following static methods:

  // returns true iff the string consists of only the characters '0' - '9' with  the first character being a non-zero digit

  public static boolean legalBigInt(String s) { ...  } 

  // returns true if the input is a list of single-digit integers, all positive with the last being non-zero 

  public static boolean legalBigInt(Node<Integer> s) { ...  } 
  
  // turn a String of digits into a linked list of single-digit ints, with ints in reverse order than in the String (one int = one digit); 
  // if the input is not legal, as defined above, throw the exception shown

  public static Node<Integer> toList(String s) throws BigIntegerStringFormatException { ... }

  // turn a linked list of single-digit integers into a String, with ints in reverse order than in the String (one int = one digit)
  // if the input is not legal, as defined above, throw the exception shown

  public static String toString(Node<Integer> p) throws BigIntegerListFormatException { ... }

  // add big ints p and q and return the appropriate list; throws the exception shown if input lists are not legal

  public static Node<Integer> add(Node<Integer> p, Node<Integer> q) throws BigIntegerListFormatException { ... }
  

The class BigInt is simply a "wrapper" for these methods which manipulate linked list integers based on the Node class. Recall that this is one of the purposes of a class.

You must follow these requirements for this problem:

• You may not use any loops in this problem; hence you must use recursion as your control structure. Your choice about how to do this, but typically the public method is a "wrapper" for a private recursive "helper" method (we will discuss this in class on Monday);
• All methods must be static;
• You must write classes for the two exceptions shown (which will extend the Exception class) and put them at the end of your BigInt.java file, using default access (i.e., no public keyword); similarlly you should write (or copy from the textbook with proper citation) the Node<Integer> class and put this at the end of your BigInt.java file;
• You must write a Unit Test which tests each of the public methods on a variety of inputs (including errors);
• Your code must work with the interactive client BigIntegerCalculator.java which I will provide.

You can mostly solve this problem by introspecting on how you do addition, and then thinking about how this might be implemented using the data structure. But remember that all these examples are using the human-oriented method; you have to write computer -oriented methods that work on reversed lists of digits!

For example, when you add two long integers, you basically have three rows of digits, with the top row being the carry from the previous column (the carry into the first column can be a 0). You add the three numbers in the column, break it into two digits (carry and sum) and write the sum digit down and copy the carry digits into the top of the next column. If one of the numbers is shorter than the other, you may have to keep adding a carry in the other number, e.g.,

   110   == carries
   934
  + 78
  ----
  1002

A strong hint is that you should write the add method using a recursive helper method as follows:

  
  public static Node<Integer> add(Node<Integer> p, Node<Integer> q) {
    return addWithCarry(p, q, 0);
  }
  
  // helper method for previous: add big ints p and q with carry from previous position
  
  private static Node<Integer> addWithCarry(Node<Integer> p, Node<Integer> q, int k) {
        ......

  }

Step-wise Development of your Code

You should of course develop both of these problems is in a step-wise fashion. Here is what I would do if I were writing these:

First read the assignment carefully, read through the Notes on Recursion and Linked Lists and the lecture notes from the last week, and read through the documentation for the Java String class. Then, for the first problem:

1. Sketch out the basic data structure and write the inner class Node and the appropriate fields for storing the linked lists;
2. Write the constructor and toString and test these using your unit test;
3. Look at all the methods and choose an order to implement them, from easiest to hardest, and for each, implement and test using the unit test; implement the parseInt(..) last; and
4. Verify that this class implements the Stringy interface.

For the second problem, I would do something similar:

1. Define your Node class and write the first two methods listed and test them carefully in your unit test;
2. Write the addWithCarry method and test it carefully in the unit test and then simply add the wrapper as shown above and test that;
3. Hold off on implementing the exceptions until you get everything to work, and then add the exceptions and modify your unit test to try the code and catch the exceptions; and
4. Verify that both of your classes work with the interactive client.

You will be graded on how well you follow the requirements, how your code works with the interactive client, and on the functionality of your code as demonstrated by your unit tests. The basic principle we will follow in grading is that if you do not demonstrate a detail of functionality in your unit test, we will assume that your code does not work on this detail.

Submission

Submit the files MyString.java and BigInt.java. The BigInt.java file should also contain, outside the scope of the BigInt class, with default access (not public), the classes for the exceptions and the generic class for Node.