Assignment 4

Harvey Mudd College
Computer Science 60
Assignment 4, Due Friday, Sep. 29, by midnight

Starbucks Menus Java Lists and applications

This assignment consists of writing three Java files. The first is a linked list that emulates rex's lists. The second is a "port" of the Unit-conversion calculator that the last two assignments have developed. The final file is a Queue data structure, which is another linked list, but one which accepts items only at the back of the list and that releases items only at the front.

The key ideas are that a lot of the functionality that's available in Rex is also available in Java, but Java makes it easier to write code that takes advantage of side effects ("closed" lists like the Queue). In addition, this week's assignment is meant to provide enough practice with Java references and Java syntax that they will be less of an issue in the more involved algorithms and graphical programs.

Submitting your code

For this assignment, you will need to create three files, named OpenList.java, Unicalc.java, and Queue.java.

To submit the files, you will need to run

cs60submit 4

from the directory in which they are located.

Reading

This assignment continues through the book's Chapter 7. However, Chapter 6 is not necessary... (we will come back to Chapter 6 later in the course). Also, most (hopefully all) of the material needed to do this assignment will be presented in class.

Testing your code

Code to test each of the (three) Java classes you're writing in this assignment appear in the files /cs/cs60/as/a4/Test#.java . You can use these by

First, compiling your class (OpenList, Unicalc, or Queue)
(Actually, compiling the test will automatically compile the files it needs in the current directory, but this is still a good idea in order to be sure your code compiles at all!)
Then, copying one of the test files to the directory in which you're working
Compile the test file it with javac Test#.java
Execute the test file with java Test#

Lastly, you can compare the output with that in /cs/cs60/as/a4/Test#.out. You can compare your output visually, or, to be sure they're exactly the same, run

java Test# | diff - /cs/cs60/as/a4/Test#.out

If there is no output from the diff command, your output matches the expected output perfectly. If there are output lines from the diff command, those beginning with < are lines appearing in your output, but not the expected output. Lines beginning with > are lines appearing in the expected output, but not your output.

In Queue.examples and OpenList.examples (in /cs/cs60/as/a4), there are toString methods (and perhaps other helpful code). USE THOSE METHODS (named toString in your code! That way everyone's output formatting will be consistent.

Problems (only three of them...)

1. An `OpenList` class

This problem is meant to introduce the implementation of data structures in Java without abandoning all of the good features of rex. In addition, it is a chance to review 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. There is example java code in /cs/cs60/as/a4 and there are lots of on-line references available from the references page.)

Write a java class named OpenList in a file named OpenList.java. OpenList should implement an (open) linked list data structure, which is the kind of list rex uses. In fact, this problem is, essentially, the first step in writing the rex programming language in Java.

Write your class in a file called OpenList.java. Open lists are not modified in the computer's memory (so that there is no worry about side effects) -- instead, each function returns a newly created list (or whatever data is appropriate).

First, in your OpenList class, you will want to indicate the data that comprises a list. Using rex's philosophy of a list being a first and a rest, your data members should include two java Objects:

          Object first;
          OpenList rest;

In fact, these are the only data members you will need in your list implementation. Notice that because the data member named first is of type Object, this implementation of lists 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 problem. The next problem will put this OpenList class to use.

For your OpenList class, implement the following functions (often called methods in Java):

CONSTRUCTORS
- (A couple of these will be covered in detail in class in order to motivate the use and syntax of constructors.)
- OpenList(Object first, OpenList rest) which is a constructor that returns an OpenList with first as its first element and rest as its rest.
- OpenList() which is a constructor that takes no arguments and returns the empty list, i.e., an object with all data members equal to null. NOTE: the empty list is not just a null reference in Java. It's a real, live OpenList object, but its data members first and rest are null.
- OpenList(Object o1) which is a constructor that takes one argument and returns an open list with one element (the object o1).
- OpenList(Object o1, Object o2) which is a constructor that takes two arguments and returns an open list with two elements.
- OpenList(Object o1, Object o2, Object o3) which is a constructor that takes three arguments and returns an open list with those three elements, in the order they are input.
cons
- (These two functions will also be covered in detail in class to distinguish between static and nonstatic methods, as well as a review of writing Java code... .)
- 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.
- 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 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.
append
- 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.
- 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. 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.
length
- static int length(OpenList L) which is a static length method that returns the length of the input list.
- int length() which is a nonstatic length method that returns the length of the invoking list.
first
- 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 exit.
- Object first() which is a nonstatic 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.
second
- static Object second(OpenList L) which is a static method that returns the second object in the input list. If the input list has fewer than two elements, this method should print an error message and exit.
- Object second() which is a nonstatic method that returns the second element of the invoking list. If the invoking list has fewer than two elements, the method should print out an error message and exit.
third
- static Object first(OpenList L) which is a static method that returns the third object in the input list. If the input list has fewer than three elements, the method should print an error message and exit.
- Object third() which is a nonstatic method that returns the third element of the invoking list. If the invoking list has fewer than three elements, the method should print out an error message and exit.
rest
- static OpenList rest(OpenList L) which 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.
- OpenList rest() which is a nonstatic method that returns the rest of the invoking list. If the invoking list is empty, your function should print out an error and exit.
isEmpty
- static boolean isEmpty(OpenList L) which is a static predicate that returns true if the input list is the empty list and false otherwise.
- boolean isEmpty() which is a nonstatic predicate that returns true if the invoking list is empty and false otherwise.
reverse
- static OpenList reverse(OpenList L) which is a static method that returns the reverse of the input list. (This does not actually change the input argument L.)
- 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.
toString
- In fact, you shouldn't write this method, you should merely use the one provided in the file /cs/cs60/as/a4/OpenList.examples. This method's signature is public String toString(), so that it is a nonstatic method that returns a String representation of the invoking list. A static version isn't needed.

To test your code (and please test as you go along!!), you may want to write a method with the familiar signature

     public static void main(String[] arg)

In that method you can create OpenLists, perform some operations on them and then print out the results. Also, the test files in /cs/cs60/as/a4 check that portions of your code are working. Examples of such test runs are in the files /cs/cs60/as/a4/Test#.in.

Hint: for append and reverse, using recursion will make your code much simpler... . Java supports recursion to the same extent that rex does, though the syntax looks a bit different.

2. Unicalc

The second problem is to write a class named Unicalc in a file named Unicalc.java. You will use Open Lists to handle the data (units, quantity lists, etc.) for the Unicalc application.

Your Unicalc class is an "execute-only" class. That is, no objects of type "Unicalc" will be made and so the Unicalc class will consist of only static methods.

The unit-conversion calculator is written in rex in /cs/cs60/as/a3/hw3.rex, the solutions to assignment 3. You don't have to emulate that recursive rex code, but it does make things easier than trying to implement it without recursion. Many people avoid recursion at all costs... in this problem those costs are high.

You will need to write four of Unicalc's methods:

(1)  static OpenList simplify(OpenList L) {...}
(2)  static OpenList multiply(OpenList L, OpenList M) {...}
(5)  static OpenList norm_unit(String s, OpenList db) {...}
(6)  static OpenList norm(OpenList QL, OpenList db) {...}

The others:

(*)  static OpenList sort(OpenList L) {...}
(*)  static OpenList assoc(String s, OpenList db) {...}
(*)  static OpenList getDB() {...}
(*)  static String stringMult(String x, String y) {...}
(*)  static String stringDiv(String x, String y) {...}
(3)  static OpenList divide(OpenList L, OpenList M) {...}
(4)  static OpenList conv_unit(String s, OpenList db) {...}
(7)  static void convert(OpenList FromQL, OpenList ToQL, OpenList db) {...}

are already written for you and are in /cs/cs60/as/a4/Unicalc.examples. These are various utilities, for example, stringMult, converts strings to doubles, multiplies them, and converts the result back to a string. This uses an intermediate class called a Double (built-in to Java) that "wraps" a double so that it can be treated as an object. You will want to copy these methods into your Unicalc class right away and comment it out. Then, as you add the functions that code requires, you can uncomment the copied code and run your class against the tests. Also, to start you off, we will discuss the simplify method in class.

Keep in mind that all methods in your Unicalc class will be static. And, because you'll never create a Unicalc object, you do not need to write any constructors... .

You may want to write additional methods in your OpenList class or Unicalc class: feel free to add whatever functionality you might need.

Important Notes on Unicalc

Each item in an OpenList is an Object. When you want to use those Objects as specific classes (namely, Strings and OpenLists), you will need to cast them to the appropriate type. In java this casting is explicit, while in Rex, it's done implicity.

For example, suppose that QL is an OpenList that is a quantity list. Then, QL.first() returns an Object that is really the amount portion of the quantity list. We are storing these amounts as Strings. So, to make sure that java knows that it is a string, you need code like
```
       String amount = (String) (QL.first());
       
```
You can multiply or divide strings (if they really hold numbers) with the provided stringMult and stringDiv methods.
As another example, the second element of QL (as long as QL is a Quantity List) is itself an OpenList -- namely, the OpenList of all of the units in the numerator. To get at this numerator list, use
```
       OpenList N = (OpenList)(QL.second());
       
```
As long as the method second is defined appropriately, N will now be the numerator list that can be used for further processing. (Individual elements of the numerator and denominator lists will still have to be cast to Strings.)
A small database of unit conversions is available as an OpenList by calling the function getDB() (provided in /cs/cs60/as/a4/Unicalc.examples)
PLEASE test your code as you go along... Java offers a lot more opportunities for syntax errors and other coding problems. You'll want to make sure that each function you write works before moving on... .

3. A `Queue` class

Write a java class named Queue that implements a closed-list version of a Queue. Recall that a Queue is a list in which data are added (enqueued) at the back and removed (dequeued) from the front.

As a starting point, you might want to consider the Stack class covered in class and available in /cs/cs60/as/a4/Stack.java. Your Queue class should have two QCell data members: front and back.

In any case, you need to have the following things in your Queue class:

Use the QCell class from the notes/lecture in order to hold data. In essence, your Queue class will be a linked list of QCells.
Use the toString method provided in the file /cs/cs60/as/a4/Queue.examples in your Queue class so that you can test your code with System.out.println statements in main. If you name your data methods something other than front and back, then you'll need to adjust toString's code.
Write a zero-argument constructor that returns an empty Queue (i.e., the front and back are null). Feel free to write other constructors if you like, but you do not need to.

Write static and nonstatic versions of an enqueue method. The method signatures should be

       static void enqueue(Object o, Queue Q) {...}

and

       void enqueue(Object o) {...}

Write static and nonstatic versions of a dequeue method. The method signatures should be
```
       static Object dequeue(Queue Q) {...}
       
```
and
```
       Object dequeue() {...}
       
```
Both methods should return null if dequeue is called on an empty Queue.

Write static and nonstatic versions of an isEmpty method with signatures

       static boolean isEmpty(Queue Q) {...}

and

       boolean isEmpty() {...}

Don't forget to include toString (available in /cs/cs60/as/a4/Queue.examples and a main method that you can use to test your code. A sample main method is in the above file; another one will be pasted into your code for the final testing.

You can test your Queue class (when the toString mewthod is included) as indicated in the "Testing your code" section above.

The completely optional extra credit involves extending your Queue class.

4. Extra Credit

For totally optional extra credit (up to 20%), add a nonstatic method evaluate to your Queue class. The idea is to add something of a real calculator to complement the unit calculator of problem #2. The signature of the evaluate method is simply

  double evaluate()

What evaluate does is return a double that is the "value" of the Queue that invoked the method (the "this" Queue). That is, evaluate looks through the items on its Queue one by one as if they were forming an arithmetic expression. Then it evaluates that expression. You can assume that every data element in the Queue will be either a Double or a String that is one of "+", "-", "*", or "/". (Remember that Double is a Java wrapper class so that values of type double can be treated as Objects. The "*" and "/" should be executed immediately -- at highest priority -- and the "+" and "-" have lower priority. For example, if the Queue Q consisted of

  10 + 4 * 5 / 2 - 3

where the left is the front of the Queue and the right is the back (most recently inserted elements), then Q.evaluate() should go through these steps:

  10
  10 + 4
  10 + 4 * 5 == 10 + 20
  10 + 20 / 2 == 10 + 10
  10 + 10 - 3 == 20 -3
  20 - 3 == 17

Any implementation that provides the correct answer (17 in this case) is all right.

Harvey Mudd College Computer Science 60 Assignment 4, Due Friday, Sep. 29, by midnight