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

From Prolog to Java...

You've already written a bit of Java code in JavaBat, but we'll dive into some of the real functionality and mindset of Java this week. This week you'll use or build at least two Java classes, i.e., custom data structures.

Submitting your code

Problems 1 should be completed individually; the other problem (and extra-credit) 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., #partnerlogin in the pair-programming textbox -- this will help the graders give the same grade to both.

Overall, submit two files for this week's problems:

• Problem 1: Complex.java, an implementation of a complex-number class
• Problem 2: List.java, your implementation of a singly-linked list that uses side-effects

Here are the starter files:

• Point.java, our Point class class example (it's very classy...)
• PointTest.java, a set of JUnit 4 tests for testing the Point class's functionality
• Complex.java, a starting point for the Complex number class, which print problem #1
• ComplexTest.java, a starting point for the tests for the Complex class
• List.java, the List Class starter code
• ListTest.java, starting JUnit test cases for the List class

Problem 0: Point

Problem #1 is to write a Complex class. To that end, 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 its tests are here: in PointTest.java

See below for instructions on how to run "snippets" of code using Eclipse's "scrapbook" -- it's not quite an interpreter in the Python style, but it's as close as Java gets...

So, just to get familiar with running/testing new classes in Eclipse, grab those two files and place them in your Eclipse workspace. A relatively easy way I found to do this was to tall Eclipse you were creating a a new project. Then, within that, you create a new class named Point and a new set of JUnit 4 tests for that class. Then, simply copy-and-paste the two provided files on top of the starter versions Eclipse creates for you. Here are the details that worked for me:

• Setting up a project for all of the week's files
• Go to File - New - Java Project
• I called my new project hw6 and then hit Finish.



• Setting up a new class
• Then, choose File - New - Class
• In the dialog, if there is no "Source folder" listed, use the browse button to choose one - I chose hw6/src, the "source" folder of the project just created.
• In the next field down, see if there is an entry in the "Package" textbox -- if there is, remove the Package name entirely. When you do, it should put (default) to the right of that text box. If there's no entry already, great!
• Type the name Point in the "name" textbox. Click Finish.
• Then, you should be able to copy the contents of Point.java, linked above, replacing the starter code with our "finished" version.



• Setting up the tests
• Next, go back to File - New - JUnit Test Case
• In the dialog, it should say "The use of the default package is discouraged." This is encouraging, because you're using the default, which does make it easier to grade elsewhere... !
• The radio button should choose "New JUnit 4 test." If it doesn't, click that one.
• Leave the "Package" field blank.
• The "Name" textbox should contain PointTest. If it doesn't, put that name there. Then, clinck Finish.
• It may ask you to put the JUnit (testing) libraries on the Java search path - you should say yes to this... .
• From there, you can copy the PointTest.java code linked above into the resulting file.



• To run everything...
• Click on the Point.java tab; you can run the main method of the Point class from the Run menu (just "Run"...)
• Click on the PointTest.java tab; you can run all of the JUnit tests from the Run menu under: Run - Run As - JUnit Test
• You will see the results of the tests in the panel on the left.
• Phew!

Scrapbooking?

If you'd like to use Eclipse's "scrapbook" pages, which let you highlight and run arbitrary snippets of code, here is a chance to try it out:

• Go to File - New - Other ...
• In the dialog that appears, go to Java - Java Run/Debug - Scrapbook page
• It will ask you where to save the page... I saved it to the src subdirectory of my current project directory (hw6 / src)
• That dialog will also prompt you for a name, e.g., sb1
• Eclipse will open that page. It should have available all of the classes from the package - in particular, the Point class, so type

  Point p = new Point(1,42);
  p
  

• Then, highlight that snippet of code (those two lines) and hit control-shift-d (on Windows) or hit the little "scrapbook icon" above with a "J" (for Java). It should evaluate the statements and then print the value of the final expression (the one without a semicolon).
• It is odd that it prints the value at exactly the point you leave the cursor... eventually I got used to putting a couple of extra blank lines at the end of the highlighted region -- this makes it easier to read what is output.
• You can also include System.out.println( ... ); statements, and it will print those to the Console.
• The return values become part of the scrapbook - hit the delete key to get rid of them immediately (or simply keep them as documentation of how things are working...)

This problem asks you to implement a complex-number data structure (class), Complex.java. You should start with the provided files:

Complex.java     and     ComplexTest.java

Getting set up    The way I placed these files into Eclipse was (1) first, use Eclipse's dialogs to create a new class named Complex and a new JUnit 4 testset named ComplexTest, then (2) replcaed the starter files provided by Eclipse with the files above. Please use no package name, a.k.a, the "default" pacakage - this allows us to test your code much more easily. Repeat the process you tried above with Point, but this time with Complex and ComplexTest.

Testing your code!    We have provided a small number of tests in ComplexTest.java. You should add at least one additional test for each of the methods that you are implementing (you don't need to add more tests for the fully provided methods). You should not modify any of the provided test cases.

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 is far more memorable than a and b!

The starter file has several methods already implemented. The methods you need to write are tagged with // TODO, and are described in the Javadoc comments above them. Because Java insists on having the correct return type, placeholder return statements are already there, too. The signatures of the methods to implement are these:

• public Complex add( Complex c )
• public void addDest( Complex c )
• public Complex negate( )
• public void negateDest( )
• public Complex conjugate( )
• public void conjugateDest( )
• public Complex multiply( Complex c )
• public double magnitude( )
• public Complex divide( Complex c )

Problem 2: List

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.

70 points

In this problem you will build a singly-linked list using Racket-like "cons cells" whose Java class is ListNode. This is an inner class, defined within List, for use implementing chains of data elements handled in the first/rest manner of Prolog and Racket.

Java has the ability to change the structure of data in-place, i.e., to destructively modify a linked list by changing its references - indeed, it's the reason for languages like Java. This can be more efficient computationally, but it can also be trickier -- the responsibility for making sure everything is consistent rests on the programmer. Having a large suite of tests is important, because destructive side-effects - especially involving object references - can have subtle impacts elsewhere!

For the record, it is certainly possible to implement list methods with no destructive side-effects, e.g., if you were implementing Racket or Prolog lists in Java. In such a functional-programming-style list, every method generates new data, instead of potentially changing the structure of old data. This is the extra-credit problem... It's entirely optional, but you might give it a try... !

Testing for List    you do not have to write additional tests than the ones in ListTest.java. For this week, please do turn in ComplexTest.java. You do not have to turn in ListTest.java.

As with Complex.java, start this problem with the existing List.java and ListTest.java files. In this case, however, most of the methods will destructively modify the linked list - we don't include the Dest in their names, since it's standard here. The methods to write are these:

• add
• reverse
• makeFromArray
• makeEquivalentArray
• appendInPlace
• split
• removeFirst
• merge
• mergeSort
• If the file has a few more, be sure to implement all of the ones in the file, not only those on this list!

Extra credit: A kinder, gentler set of List methods...

For up to +8 points of extra-credit, you have the option of building completely non-destructive, or safe, versions of the following List methods. Each of these methods should do what the original version, above, does. However, each one should return a new object of type List with the appropriate new structure. The old object (this) of type List should not be changed at all, nor should input values (if there are any). Here are the new methods to add to your List class:

• public List addToFrontSafe(String s) (returns a new copy of this with s cons'ed in the front)
• public List addSafe(String s) (adds s to the back of the new list)
• public List addSafe(ListNode LN) (adds LN to the back of the new list)
• public List appendSafe(List L) (appends a copy of L at the back of the new list)
• public List reverseSafe() (returns a reversed copy of this)
• public List[] splitSafe() (returns an array of two Lists: the first includes a copy of the first half of this; the second contains a copy of the second half of this. If there's an extra element, it goes to the first.)
• public List mergeSafe(List L2) (returns a new list containing a copy of this merged with a copy of L2)
• public List mergesortSafe() (returns a mergesorted copy of this - as with all of these methods, this should not change at all!)

Since these will be methods (functions) within your existing List class, you won't need to submit an extra file at all. However, we will test your List class against the following Unit tests:

ListTestSafe.java

You can paste this into a new set of JUnit tests, which you can create from the menu options File - New - JUnit Test Case and naming it ListTestSafe with List being the "class under test" (the textbox near the bottom of the dialog...).