Harvey Mudd College
Computer Science 60
Assignment 3, Due Sunday, February 8, by 11:59 pm
Optional Extra Credit Problem: OpenList

OpenLists in Java

Extra credit problem:    Implementing OpenList in Java

[up to +20 points, individual or pair]

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. If you haven't used Java before, you may need to review a bit about the language. In particular, there are example Java programs as well as a very small starting point for your OpenList.java file on the top-level assignments page. Also, there are on-line references and tutorials available from the references page.

Write a Java class named OpenList that implements an open linked list data structure. Since the goal of this problem is to transition from Rex to Java, you will be implementing lists in the same way Rex does. In fact, this problem is, essentially, the first step in writing the Rex programming language in Java. Open lists are recursively-defined linked lists whose structure and data are not modified -- this allows for data-sharing among lists, as done by functional languages. Instead of modifying data, each function returns a newly created list -- or whatever other data is appropriate.

Write your class in a file called OpenList.java. You should start with the OpenList.java file available at /cs/cs60/hwfiles/a3/.

The 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 Java is doing (and how it is organized). There are many more tests available from the top-level assignments 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:

          
private Object first;
private OpenList rest;

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
float
boolean
byte
char
long

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:

• the CONSTRUCTOR, named OpenList
  
  
  • 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 a string 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 Rex-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.
    
    
• 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.
    
    
• 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.
    
    
• 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). (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.
    
    
• 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.
  
  
  

Submitting your work

Be sure to submit your OpenList.java file at the CS 60 submission site under "Week 3."

A link to hw#1's directions for moving files from machine to machine and for using the submission site.

Problems with submission? Drop me an email at dodds - AT - cs.hmc.edu.