programming language using java
Assignment 1: Class-based Inheritance and Virtual Dispatch in Java July 27 at 12:00 PM Goals for This Assignment By the time you have completed this work, you should be able to: · Use class-based inheritance to implement different behaviors for the same method · Implement an immutable list · Use recursion to implement basic list operations Provided files: · ImmutableList.java · ImmutableListTest.java · Cons.java · Nil.java · hamcrest-2.2.jar · junit-4.13.jar Step-by-Step Instructions Step 1: Download Needed Code Download everything from the links above into a single directory. Step 2: Read and Understand Provided Code For this assignment, you'll be working with an immutable linked list implementation, a type of persistent data structure. While you (hopefully!) are familiar with linked lists, this implementation is likely very different from the one you're used to. Notably: · Existing lists cannot be modified (the immutable/persistant part). Operations which would normally modify the list (like append) instead return a new list, reflecting the result of the operation. For example, [1, 2].append([3, 4, 5]) returns the list [1, 2, 3, 4, 5], leaving the original lists [1, 2] and [3, 4, 5] unmodified. · Instead of using null to represent the end of a list, we instead use an instance of class Nil. · Class Cons corresponds to the normal Node class, with the caveat that tail (representing the rest of the list) cannot be null. Per the prior bullet, if we want to represent a list where tail is empty, then we should have an instance of Nil there. · There is no special class holding the head of a list. Instead, Cons and Nil are both fully-featured lists in and of themselves. This is one of the reasons we use Nil instead of null, as we can meaningfully call methods on Nil (unlike null). · Cons and Nil both implement the ImmutableList interface. If something wants to take a list as a parameter, it should take an ImmutableList; which could be either an empty list (Nil) or a non-empty list (Cons). In addition to the above bullets, there is a provided JUnit 4 test suite in ImmutableListTest.java. Step 3: (Try to) Compile and Run the Tests You will need to compile and run the code. If the code fails to compile, do not try to run it; it either won't work, or you'll run an old, previously-compiled version. The two commands below compile and run the code, respectively. The two commands are slightly different, depending on what system you're running with. If you're on a UNIX-based system (e.g., Mac OS X, Linux), use: javac -cp .:hamcrest-2.2.jar:junit-4.13.jar -Xlint:all ImmutableList.java Cons.java Nil.java ImmutableListTest.java java -cp .:hamcrest-2.2.jar:junit-4.13.jar org.junit.runner.JUnitCore ImmutableListTest If you're on Windows command prompt, use these two commands, which use semicolons instead of colons: javac -cp .;hamcrest-2.2.jar;junit-4.13.jar -Xlint:all ImmutableList.java Cons.java Nil.java ImmutableListTest.java java -cp .;hamcrest-2.2.jar;junit-4.13.jar org.junit.runner.JUnitCore ImmutableListTest If you're on Windows Powershell, use these two commands, which put some arguments in single quotes: javac -cp '.;hamcrest-2.2.jar;junit-4.13.jar' -Xlint:all ImmutableList.java Cons.java Nil.java ImmutableListTest.java java -cp '.;hamcrest-2.2.jar;junit-4.13.jar' org.junit.runner.JUnitCore ImmutableListTest If all tests are passing, you'll see output like the following: JUnit version 4.13 .................................... Time: 0.053 OK (36 tests) If tests are failing, the output will instead show which tests are failing. From there, you can look to see what those tests are doing in the test suite (ImmutableList.java), which will inform you of what needs to be modified. Note that the provided code will not compile as provided. It's missing the implementations of multiple methods which are needed to make the tests compile. Step 4: Implement Missing Code, with Restrictions Add code to Cons.java and Nil.java to get it to compile and pass the tests. Specifically, you need to implement the following methods for each: · length: returns the length of a list. As a hint, empty lists (Nil) have length 0. · sum: returns the sum of all the elements of the list. For our purposes, empty lists (Nil) have a sum of 0. · append: appends two lists together, returning a new list. · contains: returns true if the given list contains the given element, else false. Example calls to these methods are in ImmutableList.java. Restrictions For full credit, your code: · Can only modify Cons.java and Nil.java; I'll only look at these two files when grading, so any other modifications will be ignored. · CANNOT use loops (no for, foreach, while, or do-while). Any code I provided that uses loops is ok, and should not be modified. · CANNOT use conditionals (no if, switch, or ternary ((...) ? ... : ...)). Any code I provided that uses loops is ok, and should not be modified. These restrictions will force you to use recursion for a correct solution, and will also force you to fully exploit virtual dispatch (also known as dynamic dispatch, polymorphism, and ad-hoc polymorphism). While these restrictions will likely be annoying, it will force you to use a key object-oriented feature (virtual dispatch), as well as serve as good practice for later in the course (recursion). Hints · It's recommended to first write method stubs for all the methods you need to implement. This will get all the code compiling, but the tests won't pass. This is still progress, and this way you can focus on getting one set of tests (or even just one test) to pass at a time. · Mentally, whenever you think something like: · if (list is empty) { · do empty thing · } else { · do non-empty thing · } ...you must instead use virtual dispatch. For this example, do empty thing would go into the corresponding method definition in Nil, and do non-empty thing would go into the corresponding method definition in Cons. · While you only have to implement 4 operations, each of these has a different implementation for Cons and Nil, so you really have to implement 8 methods. That said, the body of each of these methods need only be a single line of code. If you need much more than a single line for any method, you are likely making this more difficult than it needs to be. If you're stuck, talk to me. · Once you think you have an operation working, run the tests again using the instructions in step 3. It's probably best to focus on getting one set of tests (or even just one test) passing at a time. · Specific to contains, you do not need to use if, though you'll need to use the short-circuiting nature of ||. Specifically you can implement this using something like the following: · return head == value ||
>; Step 5: Turn in Your Code Using you need to send the following files: · Cons.java · Nil.java In addition, if you collaborated with anyone else, be sure to download collaborators.txt and write the names of the people you collaborated with in the file, one per line. Please submit this file along with the other files. Provided files: · ImmutableList.java public interface ImmutableList { public boolean equals(final Object other); public int length(); public int sum(); // empty list sum is defined as 0 public ImmutableList append(final ImmutableList other); public boolean contains(final int value); public String toString(); public int hashCode(); } // ImmutableList · ImmutableListTest.java import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue; import static org.junit.Assert.assertFalse; import org.junit.Test; public class ImmutableListTest { // ---BEGIN EQUALS TESTS--- @Test public void equalsNilNil() { assertTrue(new Nil().equals(new Nil())); } // equalsNilNil @Test public void equalsNilCons() { assertFalse(new Nil().equals(new Cons(1, new Nil()))); } // equalsNilCons @Test public void equalsConsNil() { assertFalse(new Cons(1, new Nil()).equals(new Nil())); } // equalsConsNil @Test public void equalsConsConsSameElementsLength1() { assertTrue(new Cons(1, new Nil()).equals(new Cons(1, new Nil()))); } // equalsConsConsSameElementsLength1 @Test public void equalsConsConsDifferentElementsLength1() { assertFalse(new Cons(1, new Nil()).equals(new Cons(2, new Nil()))); } // equalsConsConsDifferentElementsLength1 @Test public void equalsConsConsSameElementsLength2() { final ImmutableList first = new Cons(1, new Cons(2, new Nil())); final ImmutableList second = new Cons(1, new Cons(2, new Nil())); assertTrue(first.equals(second)); } // equalsConsConsSameElementsLength2 @Test public void equalsConsConsDifferentElementsLength2_1() { final ImmutableList first = new Cons(1, new Cons(2, new Nil())); final ImmutableList second = new Cons(1, new Cons(3, new Nil())); assertFalse(first.equals(second)); } // equalsConsConsDifferentElementsLength2_1 @Test public void equalsConsConsDifferentElementsLength2_2() { final ImmutableList first = new Cons(1, new Cons(2, new Nil())); final ImmutableList second = new Cons(2, new Cons(1, new Nil())); assertFalse(first.equals(second)); } // equalsConsConsDifferentElementsLength2_2 @Test public void equalsConsConsDifferentElementsLength2_3() { final ImmutableList first = new Cons(1, new Cons(2, new Nil())); final ImmutableList second = new Cons(3, new Cons(4, new Nil())); assertFalse(first.equals(second)); } // equalsConsConsDifferentElementsLength2_3 // ---END EQUALS TESTS--- // ---BEGIN LENGTH TESTS--- @Test public void lengthLength0() { assertEquals(0, new Nil().length()); } // lengthLength0 @Test public void lengthLength1() { assertEquals(1, new Cons(-80, new Nil()).length()); } // lengthLength1 @Test public void lengthLength2() {