Harvey Mudd College
Computer Science 60
Assignment 4, Due Wednesday, February 17, by 11:59 pm

Conversational Java!

This homework highlights the similarities and differences between the computational styles of an object-oriented language (Java) and a functional language (Scheme). First, you'll "get conversant" with the syntax of Java by implementing a user-interaction loop, though not one as sophisticated as the Unicalc API. The second part of this assignment asks you to write two data structures - classes - one that represents Complex-number data and one that implements Scheme-like lists, called OpenList.

The Problems

Files

You'll probably want to develop your functions in a hw4 subdirectory within your cs60 directory. There will be three files to submit this week. They are

• JavaInteraction.java -- a user-interaction loop that exercises some of Java's syntax.
• Complex.java -- a Java implementation of a complex-number class
• OpenList.java -- a Java implementation of Scheme's fundamental list structure

Style

From this assignment onward, about 15-20% of credit will be awarded based on your programs' commenting, formatting, and design -- under the heading of style.

The goal is to choose a style that is readable and well-commented. Here are some of the things to look out for when writing programs for yourself (or others) to read. The graders will use these guidelines, too:

• Design
• Use small, clear functions -- and use helper functions of your own design as needed or desired. Large, convoluted functions are difficult to read and understand -- more importantly, however, they're very difficult for the original programmer to modify and debug!



• Formatting
• Please use ample whitespace: blank lines between functions, spaces within expressions to make them readable. Whitespace should keep code components visually separate.
• Whitespace -- especially indenting -- should make clear the structure of your program. Even though it's not Python, it's a good idea to use Python-type indenting.
• You should use meaningful variable names. One-letter variable names are OK if they are a common idiom, e.g., f and R for the first and rest of a list or i for an index variable. But feel free to use longer names there, too.
• You should keep your lines of code to less than 80 characters -- this helps to make it readable from within all kinds of programs, and avoids wrapping issues.



• Comments
• We ask you to include a top-of-file comment with your name, partner (if any), time spent, and any other comments for the graders (or instructors)
• Each function, even your own helper functions, should have at least a short top-of-function comment documenting its purpose, inputs, and outputs.
• Comments within functions are welcome, but not required unless something tricky is going on. Many people find them helpful to write because they keep the flow of the program in mind.

(1) JavaInteraction.java    Pair or individual problem

[30 points, pair or individual]

For this problem, you should start with the JavaInteraction.java file available from the top-level CS 60 page. It's a simplified version of JavaIntro.java, an introduction to several Java constructs. Both are linked from the top-level page.

First, look over the file JavaIntro.java, run it, and get familiar with Java's syntax and, more importantly, its "mindset." Variable types need to be declared before use - and, optionally, they can be initialized at the same time. Variables' values may change arbitrarily many times, but the declaration of the variable and its type can happen only once in each scope.

Be sure you have a clear mental model of what arrays are and how they are used. In addition, it's important to remember the difference between String objects and primitive data types, such as double, char, int, and boolean. Remember that primitive data types are handled as raw values; all other data types are objects and are handles through references.

In JavaInteraction.java all of the code in the file except the user-interaction loop has been deleted. There is also a start (not a completed or correct version) to the isPal method at the bottom of the file.

Your task for this problem is to add the following commentary to the provided user interactions in JavaInteraction.java:

• note whether the user's input line is a palindrome or not, when spaces are considered an important part of the input String
• note whether the user's input line is a palindrome or not, when spaces are NOT considered an important part of the input String
• note whether the user's input line is evaluable. We will consider an input line evaluable if all of the following conditions hold:
  • it has a length of exactly 5 characters
  • The first character (index 0) is a digit (from '0' to '9', inclusive)
  • The second character (index 1) is a space ' '
  • The third character (index 2) is one of '+' or '-' or '*' (an operator)
  • The fourth character (index 3) is a space ' '
  • The fifth character (index 4) is a digit (from '0' to '9', inclusive)
  otherwise, the input String is considered not evaluable
  • finally, if the input line is evaluable, compute and then report the value of the input line, according to the usual arithmetic interpretation of such Strings...
  You may write the "conversation" however you'd like -- creative dialog, especially that flatters the CS 60 graders, is encouraged!

However, you do need to write at least the following four Java functions, or methods. Here, we provide the function signatures and a description of what they will need to do:

• Write the method public static boolean isPal(String s)
  which should return true if s is a palindrome, including any spaces in the consideration of the String.
  For example, isPal( "!wow wow wow!" ) should return true, but isPal( "madam im adam" ) should return false.


• Write the method public static boolean isPalNoSpace(String s)
  which should return true if s is a palindrome, NOT considering any space characters ' ' in the consideration of the String. Don't worry about return characters, tab characters, or other whitespace characters at all.
  For example, isPalNoSpace( "!wow wow wow!" ) should return true and isPalNoSpace( "madam im adam" ) should return true, but isPalNoSpace( "42 is the answer!" ) should return false, despite its obvious truth!


• Write the method public static boolean canEval(String s)
  which should return true if s is an evaluable String according to the definition above.
  For example, canEval( "6 * 7" ) should return true, but canEval( "Hello, World!" ) should return false.


• Write the method public static int eval(String s)
  which should return the customary value of the arithmetic expression s. You may assume that eval will only be called on evaluable Strings.
  For example, eval( "6 * 7" ) should return 42, and eval( "6 - 7" ) should return -1.

The graders will test both your overall main method, along with each function individually, so be sure to test them before submitting!

(2) Complex.java    Pair or individual

[30 points, pair or individual]

Java has eight built-in (primitive) types -- the most common are such as int, char, boolean, and double. It has thousands of class types in its libraries. Yet one class type that Java does not have is Complex, representing complex numbers commonly used by mathematicians, scientists, engineers, and Math 11 students. This problem asks you to implement a complex number data structure (class). Complex.java.

Also, the Point class example we developed in class will be a good reference. After all, 2d points and Complex numbers are not so different! The complete Point class and a starter file for your Complex class are available from the CS 60 home page.

Testing your code!    Just as in Scheme, you should test each of your methods (functions) as you write it. To do this in Java, add lines to your Complex class's main method that test each of your methods. For this assignment, we will check visually that the answers are what they should be, so feel free to do the same.

It's much easier to make small syntactic errors in Java than in Scheme -- there is simply more code where errors can appear! To help with this, the starter file provides lots of tests in a comment in main. As you implement your Java methods, uncomment the appropriate tests and try them out!

Here is a copy of the starting point for your Complex class. Using this will help us because it will standarize the names of the data members and how your objects of type Complex are printed to the screen:

/*
 * Complex.java
 *   a complex number class
 *
 * Name:
 *
 * Comments to the graders:
 

 */

class Complex
{
    private double real;
    private double imag;

    // place your constructors here:



    // *** Please use this toString method to keep things consistent ***

    // method: toString
    //     in: no inputs
    //    out: the String version of this Complex object

    public String toString()
    {
      String sign = "+";  // default sign is plus
      if (this.imag < 0.0)
        sign = "-";       //

      return "" + this.real + " " + sign + " " + Math.abs( this.imag ) + "i";
    }


    // place your other methods here:



    // main: the starting point for our testing code
    //  in: command-line arguments
    // out: nothing (it's void)

    public static void main(String[] args)
    {
        // a welcoming statement...
        System.out.println("Welcome to the Complex...");

        // feel free to uncomment these lines of code
        // to test as you go!

        /*
        Complex c0 = new Complex( 0.0, 0.0 );
        System.out.println("c0 should be 0.0 + 0.0i");
        System.out.println("c0 is        " + c0);

        Complex c1 = new Complex( 42.0, -60.0 );
        System.out.println("c1 should be 42.0 - 60.0i");
        System.out.println("c1 is        " + c1);
        */

        // you'll want to write more tests so that you
        // know your other functions are working...

        // Do not worry about the small floating-point
        // differences that necessarily arise when using
        // arithmetic on real hardware. 
        // For instance, 2.4999999999999 is OK for 2.5

        // a departing statement...
        System.out.println("Java: where the Complex isn't!");
    }
}

Notes:     Recall that a complex number is of the form a + bi where a and b are real numbers and i is an imaginary number. Addition of two complex numbers is defined by (a + bi) + (c + di) = (a+c) + (b+d)i. Similarly, to multiply two complex numbers, we simply compute (a + bi) * (c + di) = ac + adi + bci + bdii = (ac - bd) + (ad + bc) i since ii (i times i) is -1 by definition.

In your implementation, the numbers a and b in the complex number a + bi should be represented by doubles: these will be the two data members of your class. Please use the names real and imag for these data members -- this will be far more readable/memorable than a and b!

Below are the public methods (functions) which your Complex class should contain. Be sure to use exactly these names and the specified kinds of arguments and return values. You may use any additional private methods that you'd like to use in order to build these public methods, though such helper functions are not required.

• The class should have a constructor that takes two double arguments and sets the real and imaginary components of the complex number to these values. Here is the method signature (feel free to copy and paste:

      public Complex( double real_in, double imag_in )
      

• The class should have a second constructor that takes no arguments and simply sets the real and imaginary components of the complex number to both be 0.0. Here is the method signature:

      public Complex( )
      

• Please use this code...
  
  The class should have a toString() method that converts complex numbers into strings for the sake of printing. We have provided this method (below and in the code above) -- please use that, so that the style for complex-number printing is consistent! Here is the code again, for reference:

      // method: toString
      //     in: no inputs
      //    out: the String version of this Complex object
  
      public String toString()
      {
        String sign = "+";  // default sign is plus
        if (this.imag < 0.0)
          sign = "-";       //
  
        return "" + this.real + " " + sign + " " + Math.abs( this.imag ) + "i";
      }
      

• The class should have a method named equals that takes a Complex argument and determines if the two Complex numbers (this one and the argument) are structurally equal, i.e., whether they are the same complex number. The method should return a boolean which is true if the numbers are equal and false otherwise - for the purposes of this problem use == to compare the real and imaginary parts. Here is the method signature:

      public boolean equals( Complex c )
      

• The class should have a method named add that takes a Complex argument and returns the sum of this Complex number and the argument. Thus, the return value is a Complex number itself. You should be sure that neither of the summands have their values changed in any way. Here is the method signature:

      public Complex add( Complex c )
      

• The class should have a method called negate that takes no arguments and returns the negative of this Complex number. Thus, the return value is a Complex number itself, but the invoking object has not been changed. Here is the method signature:

      public Complex negate( )
      

• The class should have a method called conjugate that takes no arguments and returns the conjugate of this Complex number. The conjugate of the number a + bi is a - bi. Thus, the return value is a Complex number itself, but the invoking object has not been changed. Notice that this is slightly different than negation. Here is the method signature:

      public Complex conjugate( )
      

• The class should have a method called multiply that takes a Complex argument and returns the product of this Complex number and the argument. Thus the return value is a Complex number itself and neither of the multiplicands have their values changed in any way. Here is the method signature:

      public Complex multiply( Complex c )
      

• The class should have a method called divide that takes a Complex argument and returns the product of this Complex number and the argument. You may assume that the second input is non-zero. Thus, the return value is a Complex number itself and neither of the multiplicands have their values changed in any way.

  To divide one complex number by another, first multiply both the numerator and denominator by the conjugate of the denominator. That ensures that the denominator is a real value! Then, you can simply divide both the real and imaginary components of the numerator by that value. A website that explains this in more detail (and offers a calculator that divides complex numbers is available here).

  Here is the method signature:

      public Complex divide( Complex c )
      

Again, be sure to test out your Complex class before submitting Complex.java.

(3) OpenList.java    Pair or individual problem

[40 points, pair or individual]

For the third problem you will create an OpenList data structure, to be implemented in Java. An "open list" is a recursively-defined linked list of cons cells whose data and strucure are not modified so that data-sharing is encouraged and safe. Instead of modifying data, each function must return newly created OpenList -- or whatever other type of data is appropriate.

Thus, this problem introduces the implementation of functional-style data structures in Java. In addition, it is a chance to either extend your introducton or your review of what Java looks like and how java code is structured. We will talk in class about the OpenList class, as well as some of the details that are provided in the starter file, OpenList.java.

Write your OpenList class in a file called OpenList.java. You should start with the OpenList.java file available at the top-level CS 60 page. In it, the constructor, the isEmpty, the toString, and the assoc methods are written as examples and for printing consistency.

The provided main method of this OpenList.java contains a couple of tests. Compile and run the file before adding code. Read it over in order to get a sense of what it is doing and how it is organized. There are many more tests available for copy-and-paste from the MainFromCompletedOpenList.java file at the CS 60 toplevel page.

Writing the OpenList class

First, in your OpenList class, you will want to indicate the data that constitute a list. There are two non-static data members (first and rest) and one static data member (emptyList) in an OpenList:

          
    // two private data members
    private Object first;
    private OpenList rest;

    // one public data member: the emptyList is static (owned by the class)
    public static OpenList emptyList = new OpenList(null, null);

Notice that because the data member named first is of type Object, this OpenList implementation will be able to create lists of any Java Objects. Everything in Java is an Object except these types:

int
double
boolean
char
float
byte 
long
short

In your OpenList class, be sure to implement the following methods. Some are in the file already; for those, read them over as they provide a useful guide to the others:

• OpenList, the CONSTRUCTOR
  
  
  • This method is provided, and it will be covered in detail in class in order to motivate the use and syntax of constructors. Constructors are always named for the type of the objects they construct.
    
    
  • public OpenList(Object f, OpenList R) is a constructor that returns an OpenList with f as its first element and R as its rest.
    
    
• toString
  
  
  • In fact, do not write this method -- instead, merely use the one provided in the starter file OpenList.java linked at the assignments page.
    
    Why do we ask you not to write this? Because this method is how we will test all of your other methods -- and we need a consistent way of displaying OpenLists to do that testing. You will need the helper method private String printItems(), as well. It is also provided.

    This toString method is a non-static method that returns a String representation of the invoking list. A static version isn't needed. The toString method is used internally by Java whenever your code adds a String to an OpenList, e.g., in code like this:

                
    OpenList L = new OpenList( "Hi!", emptyList ); // an example of using the constructor
    System.out.println("List L is " + L);
    

    The above code should output

    List L is [ Hi! ]
    

• cons   
  
  
  • public static OpenList cons(Object f, OpenList R) is a static list-constructing method that takes an Object f and an OpenList R. Then cons returns an OpenList in which f is the first element and R is the rest of the list. It simply delegates to the constructor!
    
    
  • public OpenList cons(Object f) is a non-static list-constructor method that does the same thing, but uses the invoking OpenList as the "rest" of the result. If you're already familiar with C++ or Java data structures, this method might seem a bit odd: it does not change the invoking list at all! Instead, it returns a new list that uses the invoking OpenList as its rest. Notice that this is a very Scheme-style approach to handling data.
    
    
• isEmpty
  
  
  • public static boolean isEmpty(OpenList L) is a static predicate returning true if the input list is the empty list and false otherwise. In Java, 0 and 1 are not boolean values; true and false are.
    
    
  • public boolean isEmpty() is a non-static predicate that returns true if the invoking list is empty and false otherwise.
    
    
• assoc
  
  
  • public static OpenList assoc(Object o, OpenList DB) and public OpenList assoc(Object o) are both already written in the OpenList.java starter file. Read those over as an example of how OpenLists can be used.
    
    
  • public OpenList assoc(Object o) is a non-static version of assoc. It is also already present in the file.
    
    
• first
  
  
  • public static Object first(OpenList L) which is a static method that returns the first object in the input list. If the input list is empty, the method should print an error message and then exit completely. To exit a Java program immediately, use the line

    System.exit(0);
    

    Compiler complaints about return not being present?    Watch out -- if the compiler sees

    if (this.isEmpty()) {
      System.exit(0);
    }
    else {
      return this.first
    }
    

    it will complain, saying that the method needs to return an Object in all paths through the code. The compiler doesn't realize that System.exit(0) is as final as it is. So, you'll need to include a dummy return null in the if block or get rid of the else keyword entirely.

    That said, we won't test this method on non-empty lists! Note: the basic idea here is simply to return L.first!
    
    

  • public Object first() which is a non-static method that returns the first element of the invoking list. If the invoking list is empty, the method should print out an error message and exit.
    
    
• rest
  
  
  • public static OpenList rest(OpenList L) is a static method that returns the rest of the input list. If the input list is empty, your function should print out an error and exit.
    
    
  • public OpenList rest() is a non-static method that returns the rest of the invoking list. If the invoking list is empty, your function should print out an error and exit.
    
    
• length
  
  
  • public static int length(OpenList L) is a static length method that returns the length of the input list.
    
    
  • public int length() is a non-static length method that returns the length of the invoking list.
    
    
• list
  
  
  • public static OpenList list(Object o1) is a static method that returns an OpenList of one element, o1. Note that there is no non-static version of the list method, because there might not be a list around to invoke it!
    
    
  • public static OpenList list(Object o1, Object o2) is a static method that returns an OpenList of two elements (in the order they're input). Again, there's no non-static version.
    
    
  • public static OpenList list(Object o1, Object o2, Object o3) is a static method that returns an OpenList of three elements (in the order they're input). Again, there's no non-static version.
    
    
• append
  
  
  • public static OpenList append(OpenList L, OpenList M) is a static append method that takes two OpenLists and returns an OpenList that is their concatenation.
    
    
  • public OpenList append(OpenList M) is a non-static append method that takes an OpenList as input and returns an OpenList that is the concatenation of the invoking list and M. Thus, the invoking list "goes first" in the result of append. Again, the invoking list is not changed -- because this OpenList data structure is an open list, it does not allow existing data to be changed, only new data to be created.
    
    
• reverse
  
  
  • public static OpenList reverse(OpenList L) is a static method that returns the reverse of the input list. (Remember - this does not actually change the input argument L.) Hint: use append.
    
    
  • public OpenList reverse() is a non-static method that returns the reverse of the invoking list. Again, as with all of the methods in this class, the invoking list is not changed.
    
    
• merge
  
  
  • public static OpenList merge(OpenList L, OpenList M), which is a static method that takes in two OpenLists, both of which you should assume are lists of lower-case-only Strings in sorted order from early-to-late in the alphabet. Then, merge should use the merge technique discussed in class to return a list of all of the elements in both of the input lists, but still fully in order. Thus, the result is like appending, but the sorted order is preserved.
    
    As a brief review, merging is the process of looking at the first two elements in both lists and deciding on what to do with one of them. In the end, each element gets handled once, which is faster than calling any general-purpose sorting routine!
    
    You will want to cast the elements to type String and then use String objects' compareTo method. Here's an example of how compareTo works:

    String m1 = "mudd";
    String m2 = "mit";
    if ( m2.compareTo(m1) < 0 ) ... // this test will evaluate to true
    

    Basically, if compareTo is less than zero, then the invoking string is before the input-argument string in terms of dictionary order.
    
    Warning! Java is picky about types!
    
    This is no surprise, but note that compareTo needs to be called by a String with a String as input. If L is an OpenList, however, Java thinks that L.first or the result from L.first() is only of type Object, as stated at the top of the OpenList class, but not necessarily of type String!
    
    At times like this, the programmer (you) know that data is of a certain type (a String in this case), but Java does not. The mechanism for "coaxing" Java to recognize data as a certain type is called casting and looks like this:

    String firstOfL = (String)L.first();  // we cast the Object returned by first()
    String firstOfM = (String)M.first();  // into the String _we_ know each one to be...
    

    Thus, you'll want to use lines like these two in order to grab the two strings you'll need to implement the merge function.
  
  
  • public OpenList merge(OpenList M) which is a non-static method that takes an OpenList as input and does the same thing as the static merge, using this as the other OpenList to be merged. Again, the two lists, this and M will contain zero or more strings in sorted order.
  
  
  

Totally gratuitous but cool extra credit: anylist, mergesort, and duperreverse

worth up to +15 points, may be done in pairs or individually

These problems ask you to write additional methods in your OpenList.java file (that is, your OpenList class). You don't need to submit any other files. Note, however, that these won't be part of next week's assignment (as has been the case in the past).

• Optional Extra credit of up to +5 points    anylist
  
  Write public static OpenList anylist(Object ... elements), which should be a function of any number of arguments that does essentially the same work as the list methods, i.e., create an OpenList out of those input Objects.
  
  The trick here will be to find how Java handles arbitrarily many inputs. I used this reference http://today.java.net/pub/a/today/2004/04/19/varargs.html . Note that instead of ints, you will be using Objects. You don't need to write a non-static version.



• Optional Extra credit of up to +5 points    mergesort
  
  Write public static OpenList mergesort(OpenList L), which is a static method that takes in one OpenList (which will contain ONLY Strings) and then mergesort should return a sorted OpenList with the same elements that L contained.

  How mergesort works
  
  Mergesort delegates almost all of the work of sorting the input list to the merge subroutine. It first handles its base cases: when the input list has 0 or 1 element, it's done, because such a list is already sorted! On the other hand, if the input list has more than 1 element, the idea is to first split that input list into two lists that are within one element of being the same size. After obtaining two lists from that split, a recursive call to mergesort is made on each piece.

  After this recursive call, both sublists are sorted! Then, to complete the sorting of the original list, the merge routine is used, since merge works on already-sorted lists. I always find it remarkable that this works!

  No non-static version is required, but you may certainly (as always) create small, helper functions of whatever type you like - for example, our solution used a method named split, which returned an array of two OpenLists. You can create an array as follows:

  // this creates an array of two OpenList references. 
  // both are initially null!
  OpenList[] ourOpenListArray = new OpenList[2];
  // at this point, you have 
  // ourOpenListArray[0] == null   and
  // ourOpenListArray[1] == null
  // but they are both ready to be assigned to other (real!) OpenLists...
  

  It works equally well to write split to returns an object of your own newly-defined class type that holds the two resulting OpenLists.



• Optional Extra credit of up to +5 points    duperreverse in Java!
  
  Write public OpenList duperreverse(), which is a non-static method that takes no inputs and should return a list that is the fully-recursive-reverse of the invoking OpenList, this. This returned list should have all of its structure reversed relative to the original list that called duperreverse. that original list should not change at all.
  
  Here is an example that uses the notation of printed OpenLists, with the quotes added to emphasize that the elements are Strings:

  If the OpenList L printed as
  
  [ "this", ["is", "an", ["open"], "list"] ]
  
  then the list returned by duperreverse( L ) should print as
  
  [ ["list", ["open"], "an", "is"], "this" ]
  

  Notice that even sublists (but not the elements themselves!) are reversed.
  
  You will have to use the instanceof operator in Java to determine what class-type a particular element is, in order to know whether or not to continue. For example,

  Object s = new String("I'm a string.");
  if ( s instanceof String ) ... // this test will evaluate to true
  if ( s instanceof OpenList ) ... // this test will evaluate to false
  

  No static version is required. Remember that Java's compiler checks if an instanceof expression can possibly be true - the code won't compile if it can't! In this case, s is of type Object, which could be a String or a OpenList. The compiler doesn't actually read the code, it just checks the types... .