Harvey Mudd College
Computer Science 60
Assignment 6, Due Monday, October 26, by 11:59pm

From Racket to Java...

Assuming you took CS5, at this point in CS60 youve worked with (at least) four programming languages: Python, HMMM, Racket, and now Prolog. This week - and in the coming weeks - we will add Java to that list (if it's not already there).

In addition, over the next two weeks you'll build your own task-specific language that will be able to handle Unicalc-like conversions -- this time using Java, instead of Racket.

This week you'll use or build several Java classes, i.e., custom data structures. The largest one, named OpenList will be the backbone for a Java implementation of unicalc, which you'll complete next week. With the OpenList class you'll create a Racket-like linked list that can be naturally handled recursively. Thus, OpenList "shows off" Java's data-structuring capabilities without sacrificing the generality and power of Racket and Scheme's functional style.

Submitting your code

Problems 1 should be completed individually; the other problems may be completed individually or in pairs. If you do work in a pair, please be sure both partners submit the file to their own submissions account; each should include a hash, e.g., #partnername in the pair-programming textbox -- this will help the graders give the same grade to both.

Overall, you will submit 3 files for this week's three problems:

• Problem 1: Complex.java, an implementation of a complex-number class
• Problem 2: BSTNode.java, an implementation of a binary search tree in Java, to which you'll add the ability to insert and delete.
• Problem 3: OpenList.java, your implementation of a Racket-like linked list.

Problem 1: Complex

This problem should be completed individually.

20 points

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 the complex numbers commonly used by mathematicians, scientists, engineers, physicists, and Math 35 students. This problem asks you to implement a complex-number data structure (class), Complex.java. You should start with the provided file:

Complex.java.

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 is available here in Point.java.

Testing your code!    Just as in Scheme, you should test each of your methods (functions) as you write it. To do this in Java, uncomment the lines in the provided 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!

Complex number 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 (as already appear in the starter file) 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 of your own design, 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 as-is...
  
  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 already has a method named equals -- please use that one! The reason we provide it is that we can then use tests that rely on it to compare Complex objects and any other Objects in Java! You'll see that it uses the instanceof operator to do this:

      // method: equals
      //     in: any object o
      //    out: true if o is Complex and its contents
      //         match this's contents
      public boolean equals(Object o)
      {
        if (o instanceof Complex)
        {
          Complex c = (Complex)o; // cast o to a Complex
          // now we can access c's imaginary and real parts...
          return c.imag == this.imag && c.real == this.real;
        }
        else
        {
          return false;
        }
      }
      

• 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 quotient 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.

  Here is the method signature:

      public Complex divide( Complex c )
      

Be sure to test out your Complex class with the tests provided in main before submitting your Complex.java file.

Problem 2: BSTNode

Pair or individual

20 points

At this point you've written code for Binary Search Trees (BSTs) in two different languages: Racket & Prolog. Here, we provide a binary-search-tree data structure (class) in Java named BSTNode. For this problem, you should start with this almost-complete BSTNode class:

BSTNode.java

BSTNode has much of its basic functionality already provided. This provides both an additional example of how Java creates data structures and it's to allow you to focus on the most algorithmically interesting facets of binary search trees!

In this problem you will add the methods insert and delete for the class BSTNode.

• To that end, first fill in the body of the provided method whose signature is

  public BSTNode insert(String new_key, Object new_value) 
  

  which should return a new tree identical to this tree, but such that the new_key (with new_value) are inserted in the new, returned tree in the appropriate spot. In particular, use the Racket implementation below as a guide:
  • if this is the empty tree, i.e., emptyNode, then you will want insert to return a new object of type BSTNode with only the new_key and new_value pair.
  • if the new_key is already in this, then insert should return the original tree (this) or a copy of the original tree.
  • otherwise, a new tree should be returned, with new_key and new_value appropriately placed amidst all of the original data in the old tree.



• Then, create the body of the provided method whose signature is

      public BSTNode delete(String key_to_go)
    

  which should return a new tree identical to this invoking tree, except that the node whose key is key_to_go should be deleted, along with its value. Similar to the way you did this in Racket, your delete method should
  • not do anything if this is the empty tree, emptyNode
  • remove key_to_go and its value from the appropriate subtree, in the case that key_to_go does not match the root of this
  • return the empty tree if key_to_go is the root of this and it's the only node in the BST
  • if this has only one non-empty subtree and has key_to_go at its root, then delete should return that non-empty subtree
  • finally, if this has key_to_go as its root key and it has two non-empty subtrees, then it should promote the smallest key larger than key_to_go (and its corresponding value) to the root from wherever it's found in the right subtree.
  • See the Racket implementation below as a less verbose guide to all of these cases!
  
  
  

  The BSTNode class is designed to work in the same way as our Racket implementations of binary search trees. Each object of type BSTNode can be considered both a full BST and, at the same time, can be considered a single node within a (BST. This is just like OpenList, where each object of type OpenList is a single node within a Racket-like linked list. The other similarity is the design decision that BSTNodes cannot be modified. Therefore, when you write the methods insert and delete, you should not change the instance variables, i.e., the data members, of any of the BSTNodes in the original tree structure.

  For reference, here is a Racket implementation of insert and delete:

  #lang racket
  
  (define BT1 '( 42
                 (20 (7 (1 () ()) (8 () ()))
                     (31 () (41 () ())))
                 (100 (60 () ())
                      ()) )  )
  
  (define (make-bst key left right) (list key left right))
  (define get-key first)
  (define get-left second)
  (define get-right third)
  (define (leaf? BST) (and (null? (get-left BST)) (null? (get-right BST))))
  (define (empty? BST) (null? BST))
  
  ;; here is a Racket implementation of insert:
  (define (insert new_key oldBST)
    (cond ((empty? oldBST)
           (make-bst new_key '() '()))
          ((equal? (get-key oldBST) new_key)
           oldBST)
          ((< (get-key oldBST) new_key)
           (make-bst
            (get-key oldBST)
            (get-left oldBST)
            (insert new_key (get-right oldBST))))
          (else
           (make-bst
            (get-key oldBST)
            (insert new_key (get-left oldBST))
            (get-right oldBST)))))
  
  (define start (make-bst 42 '() '()))
  (define v2 (insert 100 (insert 20 start)))
  (define v3 (insert 7 (insert 31 (insert 60 v2))))
  (define v4 (insert 1 (insert 8 (insert 41 v3))))
  
  ;; a test for several inserts...
  (equal? BT1 v4)
  
  ;; here is a Racket implementation of find-min.
  ;; This function presumes that BST is NOT EMPTY!
  (define (find-min BST)
    (if (null? (get-left BST))
        (get-key BST)  ;; return the root if the L is empty
        (find-min (get-left BST)))) ;; else descend on the left...
  
  
  ;; here is a Racket implementation of delete:
  (define (delete key_to_go oldBST)
    (if (null? oldBST)
        '() ;; return the empty tree
    (let* (
           (root (get-key oldBST))
           (L (get-left oldBST))
           (R (get-right oldBST))
           )
      (if (< key_to_go root)
          (make-bst root (delete key_to_go L) R)
      (if (> key_to_go root)
          (make-bst root L (delete key_to_go R))
      ;; must be the case that key_to_go == root here!
      (if (null? L)
          R ;; whether or not R is empty, it's what we want
      (if (null? R)
          L ;; if R is empty, we want L
          ;; otherwise, we grab the min of the right and make it the root
          (make-bst (find-min R) L (delete (find-min R) R)) )))))))
  
  ;; tests for delete...
  (define BT1_no42 '( 60
                 (20 (7 (1 () ()) (8 () ()))
                     (31 () (41 () ())))
                 (100 ()
                      ()) )  )
  
  (define BT1_no100 '( 42
                 (20 (7 (1 () ()) (8 () ()))
                     (31 () (41 () ())))
                 (60 () ())))
  
  (define BT1_no8 '( 42
                 (20 (7 (1 () ()) ())
                     (31 () (41 () ())))
                 (100 (60 () ())
                      ()) )  )
  
  (equal? (delete 42 BT1) BT1_no42)
  (equal? (delete 100 BT1) BT1_no100)
  (equal? (delete 8 BT1) BT1_no8)
  

  
  

  Problem 3: OpenList

  This problem may be done individually or in a pair. If you work in a pair, be sure to follow the CS department's pair programming practices throughout.

  60 points

  This problem is meant to introduce you to a larger part of the implementation of data structures in Java. In this case, you will be implementing in Java the "open lists" or Racket-type linked lists that you used in that language through the first few weeks of the course.

  Write a java class named OpenList that implements an (open) linked list data structure. Since the goal of this problem is to transition from Racket/Scheme to Java, you will be implementing lists in the same way Racket does. In fact, this problem is, essentially, the first step in writing the Racket programming language in Java.

  Open lists are characterized by not permitting modifications to existing data. As a result, users of OpenList can re-use lists many times without worrying about one part of their code changing a value that another part of their program might have needed. This means OpenLists do not permit side-effects: the changing of variables in-place.

  Write your class in a file called OpenList.java. You should start with this the OpenList.java file. The main method of this OpenList.java contains a couple of informal tests, and the additional file, MainFromCompletedOpenList.java, has tests that use more of the methods in their testing. Try them!

  To begin, you might want to try compiling and running the file to start building intuition about how OpenLists work.

  
  

  Writing the OpenList class

  There are three data members we will use in this OpenList. Here is how the class starts (this is in the provided OpenList.java file:

  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 the types int, double, float, boolean, byte, char, and long. We will use only Strings and OpenLists for this assignment. The next assignment, on the other hand, will put your OpenList class to work handling more types.

  In Java and other object-oriented languages, functions that are members of a class are often called methods.

  So, in your OpenList class, implement the following methods. Note that both static and nonstatic versions of the methods are required in many cases. This is not typical -- it is simply to get used to the distinction between the two. Feel free to implement one of the pair and then implement the other based on it.

  Several methods are already provided in the starter file - please keep those!

  • CONSTRUCTORS
    
    
    • public OpenList(Object first, OpenList rest) which is a constructor that returns an OpenList with first as its first element and rest 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 a consistent toString helps us test your code visually and automatically. You will need the helper method private String printItems(), as well. It is also provided.

      This toString method is a nonstatic 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 = OpenList.list("Hello","World");
       System.out.println("List L is " + L);
       

      This code should output

       List L is ["Hello", "World"]
      

      You will also use this method quite a bit when writing your unit tests, so you can assume it's working correctly.
      
  • cons   
    
    • public static OpenList cons(Object F, OpenList R) which is a static list-constructing method that takes a string F and an OpenList R and returns an OpenList in which F is the first element and R is the rest of the list.
      
      
    • public OpenList cons(Object F) which is a nonstatic 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 "Racket-style" approach to data.
      
      
  • isEmpty
    
    
    • public static boolean isEmpty(OpenList L) which is a static predicate that returns true if the input list is the empty list and false otherwise.
      
      
    • public boolean isEmpty() which is a nonstatic predicate that returns true if the invoking list is empty and false otherwise.
      
      
  • length
    
    
    • public static int length(OpenList L) which is a static length method that returns the length of the input list.
      
      
    • public int length() which is a nonstatic length method that returns the length of the invoking list.
      
      
  • assoc (already provided)
    
    
    • public static OpenList assoc(Object o, OpenList DB) and public OpenList assoc(Object o) are both already written in the OpenList.java starter file.
      
      
  • first
    
    
    • public static Object first(OpenList L) which is a static method that returns the first object in the input list. This code may assume it will not be called on an empty L (and your code should be sure to check if a list is empty before calling first. It's OK (but not required) to print an error message and call System.exit(0) if it's empty, but note that you'll still have to return something of type Object even in this case - just to make Java's type-checking compiler happy! You can do this with return null; after the call to System.exit(0);. Note: the idea here is simply to return L.first !
      
      
    • public Object first() which is a nonstatic method that returns the first element of the invoking list. As above, you may assume that first will not get called on an empty list. (You may optionally use the exit strategy here, too.)
      
      
  • rest
    
    
    • public static OpenList rest(OpenList L) which is a static method that returns the rest of the input list. As with first, you may presume that L is not empty. (You may optionally exit if it is, as above.)
      
      
    • public OpenList rest() which is a nonstatic method that returns the rest of the invoking list. Again, it's ok to assume the calling list will be nonempty, and you may optionally exit if it is.
      
      
  • equals (already provided)
    
    
    • public boolean equals( Object o ) and public boolean equals( OpenList OL ) are provided. (We won't use the static versions to avoid the ambiguity in what-calls-what.)
      
      The former allows you to compare this OpenList with any object at all: if the Object o is not of type OpenList, then false is returned. However, if it is of type OpenList, the second version is called. It does an element-by-element comparison of the contents of the two lists.
  • list
    
    
    • public static OpenList list(Object o1) which is a static method that returns an OpenList of one element, o1. Note that there is no nonstatic version of the list method, because there might not be a list around to invoke it!
      
      
    • public static OpenList list(Object o1, Object o2) which is a static method that returns an OpenList of two elements (in the order they're input). Again, there's no nonstatic version.
      
      
    • public static OpenList list(Object o1, Object o2, Object o3) which is a static method that returns an OpenList of three elements (in the order they're input). Again, there's no nonstatic version.
      
      
  • append
    
    
    • public static OpenList append(OpenList L, OpenList M) which is a static append method that takes two OpenLists and returns an OpenList that is their concatenation.
      
      
    • public OpenList append(OpenList M) which is a nonstatic 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." Again, the invoking list is not changed -- because this 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) which 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() which is a nonstatic 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 in order.
      
      As a reminder, 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, making this big-O(n), where n represents the number of elements in both lists together. This is faster than calling any general-purpose sorting routine!
      
      You will want to cast the elements to type String (see below) 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 this is before the input argument in the dictionary.
      
      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 it 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 nonstatic assoc method that takes an OpenList as input and does the same thing as the nonstatic 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.
    
    
    
  • mergesort

    As the final capability for this week's OpenList class, implement the mergesort sorting routine.

    As we have (or will) discuss in class, mergesort works recursively:

    • For the base case, if the input list has 0 or 1 element, it is already sorted and can be returned as is.
    • For the recursive case, if the input list has 2 or more elements, it can be split into two smaller halves - you'll need to be sure they're smaller! - and then each of those halves can be recursively mergesorted. The two resulting lists of those two recursive calls to mergesort will be sorted, so they can be merged using the merge method you wrote above! The result will be a sorted version of the original overall list! (Pretty amazing!)

    So, for this method, write

    • public static OpenList mergesort(OpenList L), a static method that takes in one OpenList, which will contain ONLY Strings. From there, mergesort should return a sorted OpenList with the same elements that L contained. You may certainly (as always) create small, helper functions of whatever type you like.

      As a suggestion, our solution used a method named split, which returned an array of two OpenLists, each half the size of the original - or "within 1 element" of half, to be more precise.

    • Also, for completeness, write public OpenList mergesort(), the nonstatic version of the above method. This one should return an OpenList object with the same elements as this, but in sorted order. You're welcome, as always, to call the static version from the non-static version or vice-versa.
  
  
  
  • 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 nonstatic version.
    
    
  • Optional Extra credit of up to +5 points    duperreverse
    
    Write public OpenList duperreverse(), which is a nonstatic method that takes no inputs and should return a list that is the fully-recursive-reverse of the invoking OpenList, this. That is, the output will have the elements of this in reverse order, but will also have any recursively-nested sublists of this in reverse order, as well. 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. Remarkably, 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....)
    
    
  • Optional Extra credit of up to +5 points    Quantity
    This is the first part of the next assignment: writing the foundation of the unicalc functionality in Java. It doesn't require any additional Java background than the OpenList class (but it does use your OpenList class).
    
    Details on the starter files and the methods to write are linked here.
    
    Although this is a much larger task than the above extra-creidt problems, there is the advantage of having it already complete before next week's language-implementation hwk!
    
    

  Testing    Again, you will want to run at least the tests provided in the additional file above (you can copy-and-paste those to main).

  Submitting    Be sure to submit your OpenList.java file to the submission site.