Harvey Mudd College
Computer Science 60
Assignment 3, Due Monday, February 14, by 11:59pm

From Racket to Java...

Assuming you took CS5, at this point in CS60 youve worked with (at least) three programming languages: Python, HMMM, and Racket. 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 arbitrary multiplication-based conversions from one unit to another -- and account for error propagation, too. To do this, your application will be able to navigate within arbitrarily large graphs of unit-conversion data. We're calling this application a unit-calculator, or unicalc.

In the spirit of both Racket and Java, you'll prototype your application in Racket this week. In addition, this week you'll build the fundamental data structure for a Java implementation of unicalc, which you'll complete next week. This data structure will be the OpenList class, in which you'll create Racket-like linked lists that can be naturally handled recursively. Thus, OpenList "shows off" Java's data-structuring capabilities without sacrificing the generality and power of Racket/Scheme.

Submitting your code

Problems 1 and 3 this week may be done in pairs -- or individually, if you prefer. Problem 2 should be completed individually. Overall, you will submit 4 files for this week's three problems:

• Problem 1: unicalc.rkt, a unit-conversion calculator implemented in Racket
• Problem 2: Complex.java, an implementation of a complex-number class
• Problem 3: OpenList.java, your Racket-like linked list implementation and OpenListTester.java, the unit tests for your OpenList class.

Problem 1: Unicalc, a unit-calculator in Racket

Pair or individual problem    You may work on this one either individually or in a pair. If you work in a pair, be sure to follow the CS 60 pair-programming guidelines.

30 Points

This problem asks you to write several Racket functions: together, they will implement a "unit-calculator" or unicalc application. A complete application will be able to convert any unit quantity to any compatible quantity by using an association list as a database of known conversions.

There are two files with which to start:

unicalc.rkt and unicalc-db.rkt

The first you will modify to implement unicalc; the second holds the unicalc unit-conversion database.

Quantity Lists    The fundamental structure used in unicalc is called a Quantity List. As a data structure, a Quantity List is a 4-element Racket list in which

• the first element is a floating-point number, the quantity
• the second element is a sorted list of symbols, the numerator
• the third element is a sorted list of symbols, the denominator
• the fourth element is a floating-point number, the uncertainty, which represents the one-standard-deviation error associated with the overall quantity being represented

'(9.8 (meter) (second second) 0.01)

Generally speaking, a data structure is rather low-level: it specifies the particular way that language-specific and/or machine-specific constructs are used to organize data, as the above example indicates. An information structure, on the other hand, provides problem-specific capabilities that are independent of a particular application. To reinforce this distinction, we provide a make-QL function in Racket that creates a Quantity List. In addition, we provide the accessor functions get-quant, get-num, get-den, and get-unc, which return the individual pieces of a Quantity List. In order to compare and sort lists of symbols, we provide functions sym<? and sortsym.

In Racket, the difference between data structure and information structure is almost entirely one's point of view. After all, the different ways of organizing data are relatively limited!

The unit database    In the file unicalc-db.rkt is a unit-conversion database in the form of an association list - here are a few of its conversions:

(define unicalc-db 
  (list 
(list 'A                      (make-QL 1.0 '(ampere) '() 0.0))
(list 'faraday                (make-QL 96490.0 '(coulomb) '() 0.0))
(list 'farad                  (make-QL 1.0 '(coulomb) '(volt) 0.0))
(list 'fathom                 (make-QL 6.0 '(foot) '() 0.0))
(list 'hour                   (make-QL 60.0 '(minute) '() 0.0))
(list 'inch                   (make-QL 0.02539954113 '(meter) '() 0.0))
 ... ))

When a quantity is normalized, it is converted entirely into basic units. Also, the database does not contain conversions from everything to everything: that would make it very large and difficult to maintain! Instead, the database can be used multiple times, e.g., to convert furlongs to miles to feet to inches to meters.

Unicalc's functions to write

A note on uncertainty-propagation: there are many online references that indicate how to propagate uncertainty through various functions. We used this reference from Harvard and this error-propagation calculator as a check for our results. Our uncertainties represent the size of one-standard-deviation within a Gaussian distribution around the quantity in our quantity list - note that we're not tracking relative uncertainties here, though the formulas below do compute them, as needed.

• Write a function

  (define (cancel L1 L2)
  

  that takes in two sorted lists of symbols, L1 and L2 and then returns a new list of all the symbols in L1 after canceling with L2. The output list should still be sorted, too. Here, canceling means removing common symbols as many times as they occur in both lists. These tests will make that clearer:

  (check-expect (cancel '(m m s) '(kg m s s)) '(m))
  (check-expect (cancel '(m s) '(kg m s s)) '())
  (check-expect (cancel '(m s s s) '(kg m s s)) '(s))
  (check-expect (cancel '(kg m s s) '(m m s)) '(kg s))
  

  For this function use the same element-by-element approach as in the merge technique we talked about it class: it will thus be O(N), where N is the length of the smaller of L1 and L2. The function sym<? is provided to compare two symbols alphabetically. The details will be slightly different, but your code will have the same structure as it did in merge.



• Write a function

  (define (simplify QL)
  

  that takes in a quantity list QL and returns another quantity list of the same value, but having canceled out any shared elements between the numerator and denominator. Here are some examples:

  (check-expect (equal-QLs? (make-QL 1.0 '(m) '(s) 0.0)
                            (simplify '(1.0 (m m s) (m s s) 0.0)))
                #t)
  
  (check-expect (equal-QLs? (make-QL 1.0 '(m) '(kg) 0.0)
                            (simplify '(1.0 (kg m m s) (kg kg m s) 0.0)))
                #t)
  




• Write a function

  (define (multiply QL1 QL2)
  

  that takes in two quantity lists QL1 and QL2 and returns a quantity list representing their product. The result returned should be simplified!. Note that if q1 and q2 are the quantities and u1 and u2 are the uncertainties in QL1 and QL2, then the uncertainty in the product is given by
     q1*q2*( (u1/q1)**2 + (u2/q2)**2 )**0.5
  We will avoid multiplying by zero! Here are some examples:

  (check-expect (equal-QLs? (make-QL 1764.0 '(m) '(s) 59.39696962)
                            (multiply (make-QL 42.0 '(kg m m) '(s s) 1.0)
                                      (make-QL 42.0 '(s) '(kg m) 1.0)))
                #t)
  
  (check-expect (equal-QLs? (make-QL 1.0 '(kg meter x) '(amp s w) 0.02061553)
                            (multiply (make-QL 2.0 '(meter) '(amp w)   0.01)
                                      (make-QL 0.5 '(kg x)  '(s)  0.01)))
                #t)
  

  This was an example from class... . Use the helper function merge, to ensure O(N) running time, as we did there.



• Write a function

  (define (power QL p)
  

  that takes in a quantity lists QL and an integer p and returns a quantity list representing QL^p.
  
  How to do this?    You will want to use the following ideas:
  • For the new quantity, take the appropriate power of the old quantity. (Use Racket's expt function.)
  • For the new numerator and new denominator, you'll want a helper function that concatenates - and maintains the sorted order - of the correct number of the original numerator and denominator. You'll use recursion, in all likelihood! Note that negative powers aren't a problem: they simply switch the roles of these two pieces of the quantity list!
  • As for the uncertainty, it's not just an extension of the multiplication/division uncertainty! This is because the factors in power are correlated; those in multiplication are considered uncorrelated. Here is the formula for uncertainty propagation:
       abs(p)*(q**(p-1))*u
  
  Here are some examples of power in action:

  (check-expect (equal-QLs? (make-QL 1.0 '() '() 0.0)
                            (power (make-QL 200.0 '(euro) '() 1.0) 0))
                #t)
  
  (check-expect (equal-QLs? (make-QL 0.005 '() '(euro) 2.5e-005)
                            (power (make-QL 200.0 '(euro) '() 1.0) -1))
                #t)
  
  (check-expect (equal-QLs? (make-QL 8000000.0 '(euro euro euro) '() 120000.0)
                            (power (make-QL 200.0 '(euro) '() 1.0) 3))
                #t)
  

  Warning Implement power on its own via recursion - don't use multiply. The reason is that uncertainty propagates differently when you multiply two independent variables than when you multiply the same variable, as power does.



• Write a function

  (define (divide QL1 QL2)
  

  that takes in two quantity lists QL1 and QL2 and returns a quantity list representing the quotient of QL1/QL2. Again, the result returned should be simplified! Note that the uncertainty is similar to the multiplication case:
     (q1/q2)*( (u1/q1)**2 + (u2/q2)**2 )**0.5
  We will avoid dividing by zero. Here are some examples:

  (check-expect (equal-QLs? (make-QL 1.0 '(m) '(s) 0.03367175)
                            (divide (make-QL 42.0 '(kg m m) '(s s) 1.0)
                                    (make-QL 42.0 '(kg m) '(s) 1.0)))
                #t)
  
  (check-expect (equal-QLs? (make-QL 4.0 '(meter s) '(amp kg w x) 0.08246211)
                            (divide (make-QL 2.0 '(meter) '(amp w)   0.01)
                                    (make-QL 0.5 '(kg x)  '(s)  0.01)))
                #t)
  




• Write a function

  (define (norm-unit unit)
  

  that takes in a Racket symbol unit and returns the equivalent normalized quantity list. This will require not only looking up unit in the provided database, unicalc-db, as we did in class, but then making sure the final result is normalized, that is, consists only of basic units. The final result should be simplified, as well. You should use 0.0 as the uncertainty of a plain unit (the unicalc database will do this for you). Here are some examples:

  (check-expect (equal-QLs? (make-QL 1.0 '(kg meter meter) 
                                         '(ampere second second second second) 0.0)
                            (norm-unit 'weber))
                #t)
  
  
  (check-expect (equal-QLs? (make-QL 1.0 '(ampere) '() 0.0)
                            (norm-unit 'ampere))
                #t)
  

  Hint: read over norm-QL before implementing norm-unit. Then, implement each one so that it calls the other: an example of mutual recursion. If you'd like a bit more explanation on this idea, see the q/a link at the end of norm-QL.



• Write a function

  (define (norm-QL QL)
  

  that takes in a quantity list QL and returns the equivalent normalized quantity list. This will require lots of looking-up in the provided database, so we strongly suggest a mutual-recursion approach with norm-unit. That is, "peel off" one unit, if there is one, then use norm-unit to find the quantity list equivalent to that unit. Then use multiply or divide, as appropriate. Recursion will be crucial here! The final result should be simplified. Here are some examples:

  (check-expect (equal-QLs? (make-QL 42.0 '() '(ampere second) 1.0)
                            (norm-QL (make-QL 42.0 '(weber) '(ampere volt) 1.0)))
                #t)
  
  (check-expect (equal-QLs? (make-QL 4.3890407 '(meter) '() 0.09143834)
                            (norm-QL (make-QL 14.4 '(foot) '() 0.3)))
                #t)
  
  (check-expect (equal-QLs? (make-QL 0.010159816 '(meter) '(second) 0.0005079908)
                            (norm-QL (make-QL 2.0 '(foot) '(minute) 0.1)))
                #t)
  

  Note: Jane asked a great question about this... to give everyone access to the question and answers, they're linked here.



• Write a function

  (define (add QL1 QL2)
  

  that takes in two quantity lists QL1 and QL2, and returns their normalized sum. It's a good idea to normalize first -- that way you can detect a unit mismatch. If, after normalzing, the quantity lists' units do not match, return

  (list 'error 'add QL1 QL2)
  

  If they can be added, you'll need to use the error-propagation formula:
     new_uncertainty = ((u1**2) + (u2**2))**0.5
  where u1 and u2 are the old uncertainties, respectively. Here are a couple of examples:

  (check-expect (equal-QLs? (make-QL 2.13356145 '(meter) '() 0.03592037)
                            (add (make-QL 42.0 '(inch) '() 1.0)
                                 (make-QL 42.0 '(inch) '() 1.0)))
                #t)
  
  (check-expect (equal? (add (make-QL 42.0 '(inch) '() 1.0)
                                  (make-QL 42.0 '(s) '() 1.0))
                        (list 'error 'add 
                              (make-QL 42.0 '(inch) '() 1.0)
                              (make-QL 42.0 '(s) '() 1.0)))
                #t)
  




• Write a function

  (define (subtract QL1 QL2)
  

  that takes in two quantity lists QL1 and QL2, and returns their normalized difference: QL1 - QL2. This will be almost identical to add, except that if, after normalzing, the quantity lists' units do not match, return

  (list 'error 'subtract QL1 QL2)
  

  If they can be subtracted, the error-propagation formula is the same as for addition. Here are two examples:

  (check-expect (equal-QLs? (make-QL 0.0 '(meter) '() 0.03592037)
                            (subtract (make-QL 42.0 '(inch) '() 1.0)
                                      (make-QL 42.0 '(inch) '() 1.0)))
                #t)
  
  (check-expect (equal? (subtract (make-QL 42.0 '(inch) '() 1.0)
                                  (make-QL 42.0 '(s) '() 1.0))
                        (list 'error 'subtract 
                              (make-QL 42.0 '(inch) '() 1.0)
                              (make-QL 42.0 '(s) '() 1.0)))
                #t)
  

  Note that subtract will be largely copied from add - this is completely OK!

Where's convert?    With this toolkit of functions in place, unit-conversion turns out to be an application of division:

(define (convert from to)
  (norm-QL (divide from to)))

More tests...    Here are a few more tests you might try. These combine your unit-calculation functions into composite operations:

(check-expect (equal-QLs? (make-QL 0.38735983 '(second) '() 0.030581039)
                          (divide (norm-QL (make-QL 3.8 '(m) '(s) 0.3))
                                  (norm-QL (make-QL 9.81 '(m) '(s s) 0.0))))
              #t)


(check-expect (equal-QLs? (norm-QL (make-QL 0.48 '(cm) '() 0.6327716))
                          (let* ((w (make-QL 4.52 '(cm) '() 0.02))
                                 (x (make-QL 2.0 '(cm) '() 0.2))
                                 (y (make-QL 3.0 '(cm) '() 0.6)))
                            (subtract (add (norm-QL x) (norm-QL y)) (norm-QL w))))
              #t)


(check-expect (equal-QLs? (norm-QL (make-QL 18.04 '(cm cm) '() 3.7119827))
                          (let* ((w (make-QL 4.52 '(cm) '() 0.02))
                                 (x (make-QL 2.0 '(cm) '() 0.2))
                                 (y (make-QL 3.0 '(cm) '() 0.6)))
                            (norm-QL (add (multiply w x) (power y 2)))))
              #t)

(check-expect (equal-QLs? (make-QL 5.1 '(meter) '() 0.360555127)
               (subtract (norm-QL (make-QL 14.4 '(meter) '() 0.3)) 
                         (norm-QL (make-QL 9.3 '(meter) '() 0.2))))
              #t)

(check-expect (equal-QLs? (make-QL 23.7 '(meter) '() 0.360555127)
               (add (norm-QL (make-QL 14.4 '(meter) '() 0.3)) 
                    (norm-QL (make-QL 9.3 '(meter) '() 0.2))))
              #t)

Congratulations! on creating an error-propagating unit calculator! You will extend this prototype implementation into a full-fledged language in the next assignment... (in Java!)

Submitting    Be sure to submit unicalc.rkt to the submission site; you do not need to submit unicalc-db.rkt.

Java

Problems 2 and 3 use Java and its unit-testing framework, JUnit. Remember that problem 2, Complex.java is an individual problem and problem 3, OpenList.java can be done in a pair or individually.

Remember, too, that you're welcome to use any Integrated Development Environment, these instructions will focus on Dr. Java, which has a relatively shallow learning curve. Either way, you'll be submitting only your plain-text source code (the .java files).

Java testing: JUnit

Because Java has a so strong an industry foothold as a development language, there are many tools available to help test Java code. We will use perhaps the most ubiquitous unit-testing framework, named JUnit. Fortunately, Dr. Java makes using JUnit quite straightforward: the basic framework is included with the IDE.

How to use JUnit for testing

This week we provide files of unit tests named ComplexTests.java (for problem 2) and OpenListTests.java (for problem 3). The goal for your Complex class will be a correct implementation for a complex-number class that satisfies the provided tets: you won't need to add more tests there. For OpenList, you will add more tests of your own.

Here is what a JUnit test looks like - although its syntax is Java, it's very much in the same spirit as Racket's check-expect. This one is from ComplexTests.java:

  /**
   * test of equals
   */
  public void test_equals() 
  {
    Complex actual = new Complex(42.0,60.0); // 42 + 60i
    Complex expected = new Complex(2*21.0,2*30.0); // also 42 + 60i
    boolean complexesEqual = actual.equals( expected ); // check
    boolean exp = true; // expectation
    // this next line is JUnit's test, with our own String annotation:
    assertEquals( "Complex equals", exp, complexesEqual ); 
  }

Commenting out tests...    One way to test your code one function at a time is to comment out all of the tests you don't want to compile or run yet. Java uses slash-star:

/*

*/

  /**
   * test of equals
   */
  /*
  public void test_equals() 
  {
    Complex actual = new Complex(42.0,60.0); // 42 + 60i
    Complex expected = new Complex(2*21.0,2*30.0); // also 42 + 60i
    boolean complexesEqual = actual.equals( expected ); // check
    boolean exp = true; // expectation
    // this next line is JUnit's test, with our own String annotation:
    assertEquals( "Complex equals", exp, complexesEqual ); 
  }
  */

Dr. Java has support for JUnit testing: open both the Complex.java file and the ComplexTests.java file. Then hit the compile button (or F5) followed by the test button (or control-t). The testing tab will report on which tests passed and which did not.

Problem 2: Complex

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. You should start with the two provided files:

Complex.java     and     ComplexTests.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 and here in .txt format.

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 the JUnit testing requires 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;
        }
      }
      

  We won't use a non-static version.
• 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.

  Here is the method signature:

      public Complex divide( Complex c )
      

Be sure to test out your Complex class with the unit tests provided before submitting your Complex.java file. You don't need to submit ComplexTests.java.

Problem 3: OpenList

This problem may be done individually or in a pair. If you work in a pair, follow pair programming practices throughout.

50 points

This problem is meant to introduce the implementation of data structures in Java. In addition, it is a chance to either introduce yourself (or 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. In particular, there is a starting point for your OpenList.java and OpenListTests.java files 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 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 (not JUnit tests). To begin, you might want to try compiling and running the file to start building intuition about how OpenLists work.

Tests    Just as with your Racket functions, you should test each of your methods as you write it. A starting set of JUnit tests is provided in OpenListTests.java In addition to running those tests, you should add at least one more test for each method you write in your OpenList class. You don't need to add a test for each of the {static, nonstatic} versions of each method, just one for each distinct name of a method you write.

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. 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, as well as with the JUnit tests. 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.
  
  
  
• 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    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. No nonstatic 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.
  
  

Testing    Again, remember that you need at least one test for each of your functions in your OpenListTests.java file!

Submitting    Be sure to submit both your OpenList.java file and your OpenListTests.java tests to the submission site.