Homework 2: Removing Items from Lists

--- tags: hw, spr22 --- # Homework 2: Removing Items from Lists ### Due: ~~Thursday, February 17th, 2022 at 11:59pm ET~~ **Revised deadline: Thursday, February 24th at 11:59, no late days beyond this date** :::warning **Update:** After the trouble many of you are reporting on this assignment, we are extending the deadline by a week (but will not allow late days beyond that). We have added hints and strategies throughout this document in yellow boxes such as this one (marked with "Update"). Focus on using the extra time to work on your strategies for approaching data structure coding and testing problems. That is more important than point counts from the autograder. We will adjust course grades as needed around this assignment. We are most concerned with you working on the challenges that made this assignment take a lot of time for you, so that these challenges won't cascade into the rest of the course. Based on some of the feedback in the hwk2 form, we've written up a [Worked Example of a MutableList function](https://hackmd.io/@csci0200/SyRsgGeeq) that shows how we might approach getting from conceptual understanding to code. It explains placement of methods across classes in a different way, which some of you may find helpful (let us know if it helps!). ::: **Collaboration Policy:** This assignment uses the default course [collaboration policy](https://hackmd.io/wStcp9Z4TH641sgw7r6Zyw?view). Roughly, you may discuss conceptual issues, but you must code alone. See the policy for details and examples of what is and isn't allowed. This [HW2 FAQ post](https://edstem.org/us/courses/16807/discussion/1130416) will be maintained on Ed. Overview --------- In lecture, we have looked at how to implement both immutable and mutable Linked Lists. This assignment has you look at how these two kinds of lists work when extended with a deletion operation. You'll look at this from the perspectives of memory diagrams, implementations, and runtime analysis. ## Learning Objectives: * Understand how to implement (mutable) lists * Understand how lists work in memory * Analyze runtime of programs * Practice testing interacting methods * Add private fields to help speed up the performance of methods Here is the [GitHub Classroom link](https://classroom.github.com/a/P4YCmYK_). If you're having trouble with IntelliJ, check out our [IntelliJ Common Problems](https://hackmd.io/webHvA8yTCqGOAKXYgrI_A) handout. Please make sure to read [our Gradescope submission guide](https://hackmd.io/jC-SEMn_RpiGqMH_EhsDMw) before handing in your assignment! Stencil Code ------- The `src` directory contains - an `IListWithNode` interface (more on that later) The `sol` directory contains - an `IList` interface - versions of the `MutableList` and `Node` classes that we began developing in lecture. You'll expand these with new methods as part of this assignment. :::spoiler A `MutableList` Nuance: Letting Lists Allow Any Element Type When you use Java’s `LinkedList` class (as a programmer), you supply the type of the list elements in angle brackets, as in `LinkedList<Integer>`. A `LinkedList<Integer>` object will only accept `Integer` objects to add to the list. The lists we are implementing for this assignment will also have this feature. Fortunately, we only need a small annotation to our classes to enable this feature. Just as you provide a type in angle brackets to use `LinkedList`, you can annotate a class or interface with a type parameter (such as `T`), as in the following example: ```java= class Node<T> { T item; Node next; Node(T item, Node next) { this.item = item; this.next = next; } } ``` To create an object of this class, you would just supply the type, as you do when using the built in linked lists. For example, `Node<Integer>`. Whatever type you put in the angle brackets becomes the type of the `item` field within the `Node` object. You will see this annotation already on the stencil classes. You just get to use it when writing tests. Note that you have to use `Integer` instead of `int` (and `Double` instead of `double`) in angle brackets, but they accomplish the same element types. ::: ## Optimizing size Having a class like `MutableList` holding the sequence of nodes provides an opportunity to store values that might reduce the runtime of some methods. `size` is a good example. We can add a field (perhaps named `length`) that maintains the `size` of the list as elements get added. Then, when someone asks for the size of the list, we can return the value in that field rather than recur or loop through all of the nodes. **Task:** Write the method `addLast` which takes in an item and adds it to the end of the list. It should have return type `void`. **Task:** Add a field `private int length` to `MutableList`. Modify the constructor, `addFirst` and `addLast` to initialize and maintain this field. Modify the `size` method in `MutableList` to leverage this new field. **Task:** In a comment immediately under the `size` method, write down the worst-case running time of your revised `size` on a list of $N$ elements. :::warning **Update**: You do not need to annotate the lines of code. Just state the running time in terms of $N$, such as "constant", "linear in N", etc. This holds for all run-time methods on this assignment. ::: ## Getting items by position ([Give me something](https://www.youtube.com/watch?v=EPo5wWmKEaI) from the list) **Task:** Implement the `get` method from the `IList` interface. This method takes a position in the list and returns the item at that position (the first element is in position 0). If the given index is too large or negative, you should throw `new RuntimeException("Index out of bounds")`. (*Hint: create a recursive method in the `Node` class, as we did for `size` in lecture*.) :::warning **Update**: If you are having trouble figuring out the structure of methods that you need across the `MutableList` and `Node` classes here, check out this new [Worked Example of a MutableList function](https://hackmd.io/@csci0200/SyRsgGeeq) document that explains the method breakdown from a different perspective than we used in lecture. You should expect to have the method in the `MutableList` class call a method in the `Node` class (the `Node` method corresponds to the recursive function). ::: **Task:** In a comment immediately under the `get` method, write down the worst-case running time of `get` on a list of $N$ elements. Developing your Intuition: Behavior of Remove methods ------- Next, we will implement methods to remove the first occurrence of an item from a list. Intuitively, when we remove an item from a list, the resulting list no longer contains that item. Although we didn't implement a `remove` method in lecture, here's how such a method would behave in each of immutable (functional) and mutable (Java) lists: ```=java // Immutable version LinkList Lim = new emptyList().addFirst(7).addFirst(9).addFirst(3); LinkList Lim2 = Lim.addFirst(8); System.out.println(Lim); // prints a list with 3, 9, 7 System.out.println(Lim2); // prints a list with 8, 3, 9, 7 System.out.println(Lim.remove(3)); // prints a list with 9 and 7 System.out.println(Lim); // prints a list with 3, 9, 7 System.out.println(Lim2); // prints a list with 8, 3, 9, 7 // Mutable version MutableList<Integer> Lmut = new MutableList<>(); Lmut.addFirst(7); Lmut.addFirst(9); Lmut.addFirst(3); System.out.println(Lmut) // prints a list with 3, 9, 7 Lmut.remove(3) System.out.println(Lmut) // prints list with 9 and 7 ``` In short, with an immutable list, `remove` returns a new list without the given item, keeping the item in the original list. In a mutable list, the given item is taken out of the list. *Note: There are questions about how this should work if an item is in the list multiple times: does "remove" mean "remove once" or "remove all"? For this assignment, we'll follow a "remove once" interpretation, in which only the first occurrence of an item gets removed.* ### Environment/Heap Diagrams for Remove Methods **Task:** Draw the environment/heap diagram that should exist at the end of the following code: ``` MutableList<String> M = new MutableList<String>(); M.addFirst("tea") M.addLast("pie"); M.addFirst("kiwi"); MutableList<String> T = M; T.addLast("mint") M.remove("pie"); ``` You can use a drawing tool or work on paper and scan in your diagram. Name your file `memory.pdf` or `memory.png`. Refer to [How to Develop a Memory Diagram](https://hackmd.io/EAc05wrrRp6eoqFYyTs9Ag) document if you aren't sure how to approach this. ## Removing Items: [Somebody that the List Used to Know](https://www.youtube.com/watch?v=8UVNT4wvIGY) Think about how you would write a remove method using only the fields that you have in the stencil code (namely, a `start` field in `MutableList`) and a `next` field in `Node`). For example, say you had started with the following idea of a method: ``` class Node { public void remove(T findTtem) { if (this.item.equals(findItem)) ... } ``` **Task:** What's the challenge to finishing this code with only the fields given in the stencil? Write your answer in a couple of sentences in a block comment above the `class Node` line in your `Node.java` file. (*Hint: Working with a diagram, and connecting the diagram edits to lines of code might help here.*) ## Simplifying the code: doubly-linked lists One common way to address the challenges of writing `remove` with just the stencil fields is to add a `prev` field to each `Node`. Just as `next` refers to the next node in the chain, `prev` refers to the previous one. With a `prev` field, once you find the `Node` to remove, you can use its `next` and `prev` fields to bypass the node-to-remove. **Task:** Add a `private Node prev` field to the `Node` class. Modify the `Node` constructor, the `addFirst` method and the `addLast` method in `MutableList` to work with `prev` as needed. Make sure to test that these methods are still working before you proceed. :::warning **Update:** Several students have reported struggling with `prev`. Draw a diagram of a `MutableList` that includes `prev`. Then, make a copy of the diagram (or switch drawing colors) to show what the list (and especially the `prev` fields) should look like after each of `addFirst` and `addLast`. For every arrow that gets created or re-routed, write a line of code in the corresponding method that sets up the arrow accordingly. ::: **Task:** Implement the method `remove` from the `IList` interface. This time, take advantage of both the `prev` and `next` fields. **Task:** In a comment immediately under the `remove` method, write down the worst-case running time of `remove` on a list of $N$ elements. **Task:** Write tests for your `remove` method. A good set of tests will check removing items from each of the front, middle, and end of the list. :::warning **Update:** One challenge here lies in figuring out what to compare the results of `remove` to. There are two general ways to approach this: one is to build both the original list and a second list with the intended item removed, then to assert that they are equal. Another approach is to leverage `toString`! You can compare the `toString` result of the `MutableList` after removing an item to a string that shows the expected order of elements. ::: **Task:** Write tests for the interaction between `size` and `remove`. By this, we mean you should write tests that check whether `size` still returns the expected value after `remove` has been called on a list. ## Handing Out Nodes Java and many other languages do not give programmers access to the `Node` objects. Users of the list class can only work with the list via the methods in that class (in your case, the `MutableList` class). Some older languages (notably C, which you will use if you take CS300 or CS330) are more permissive. Programmers can retrieve and store specific `Nodes`. This section has you explore the consequences of this. The `MutableList` class has a commented-out interface `implements` called `IListWithNode`. Import `src.IListWithNode` at the top of your code. We'll add these methods as part of our exploration. In Java, a class can implement multiple interfaces (sicne interfaces only require that a class provide certain methods). :::spoiler Why would one class implement two interfaces? Interfaces are types that multiple classes can satisfy. The same class can satisfy multiple types, as long as it provides the methods that each type expects. There are many ways to implement lists (as we will see in class). The interface provides a way to say "this class can behave like a list". For those coming from 15, you were taught to use interfaces to group multiple classes with the same ~able properties together. For example, in the Fruit Ninja assignment, multiple fruit and bomb objects were "Choppable" and implemented a Choppable interface. Here, we are expanding on this idea: an interface can also state a collection of useful operations, which multiple classes can provide. In 15, for example, you saw `ArrayList`, which offers the same methods as `LinkedList`, but with different underlying behavior. ::: ### **Task:** Implement the `getNode` method that is listed in the `IListNode` interface (uncomment the `IListWithNode` on `MutableList` to make sure you have the header correct). This method take an item and return the `Node` that contains the item. **Task:** The other method in `IListWithNode` is `removeNode`. This method takes a `Node` object and removes it from the list. Implement this method, using no more than constant runtime (meaning the method takes the same amount of time no matter how large the list gets.) **Note:** The point of this question is to think about how having the `Node` object simplifies the remove task. Don't overthink this. Develop an example with a diagram to help if you don't see what to do here. :::warning **Update:** Trying to use recursion here is definitely overthinking things. If you are still struggling with this: - draw a picture of the list in the heap, as well as the names in the environment - Write down a call you could make to `removeNode`, using the names in your environment - Show how the diagram should be different after the call - Try what we've suggested earlier, about one line of code for each arrow change that gets made. If you aren't leveraging names that refer to Nodes, you're probably not understanding the question yet. ::: **Task:** Consider the following program: ``` // assume you have a MutableList M with items 5. 8. 2 Node N = M.getNode(8); M.removeNode(N); M.removeNode(N); ``` What do you expect the contents of `M` to be after this program runs? Actually run the program and explore `M`: does it match expectations? Write a test named `testDoubleRemove` in your test file to show what should happen upon running this program. Describe (in text) any ideas you have about how to address the issues that came up with this. Note that **you do not need to edit your code to make this example work properly.** We just want you to see the problem and try to propose some solution ideas. ## Testing ([that's what makes our list beautiful](https://www.youtube.com/watch?v=QJO3ROT-A4E)) **Test:** Write a good set of tests for `get`, `remove`, and `size`, including tests of their interactions. Put these in `Homework2TestSuite.java`. You do **NOT** need thorough tests of `getNode` and `removeNode`, though you should do a couple of simple tests to make sure that your code will run. Submit your test file to the **Homework 2: Testing** assignment on Gradescope. See [our Gradescope submission guide](https://hackmd.io/oTbF1IUuRs27VgVJF4z2rA) for an explanation on how we are grading your tests, and how you can use the Testing assignment on Gradescope to get a better understanding of the assignment. :::warning **Update:** The autograder is running 16 tests on your code. We intentionally don't tell you in advance what those tests are checking for. You will see the autograder display a score of `-/16` no matter how many you got right. Work on fixing any tests that appear colored red after the autograder runs. As for chaffs, aim for 60-75% of them for this assignment. We'll raise this as the course goes on and everyone gets more comfortable with chaff grading. We will also talk more about the chaffs ater the assignment due date. The [Worked Example of a MutableList function](https://hackmd.io/@csci0200/SyRsgGeeq) also has some guidelines on coming up with a good set of tests. ::: ### Setup Data for Testing with `@Before` You will probably find it helpful to set up your testing data using a `@Before` method, as follows: ``` class Homework2TestSuite.java MutableList<Integer> myList; @Before public void setupData() { this.myList = new MutableList<Integer>(); // a bunch of addFirst, addLast operations to populate myList } ``` JUnit will automatically run `setupData` before it runs every `@Test` method. This lets you write the code to build your testing data once, then have it reset to a clean value at the start of each test. This way, you don't have to worry about whether one test added or removed elements, which could break the expected answers in other tests. ### Testing Exceptions As a reminder, here is how to test exceptions. ```java= // say you have a runtime exception somewhere in your code: public class ErrorObject { public ErrorObject(){} public void alwaysFail(int i, String s, boolean t) { throw new RuntimeException("error message"); } } Exception exception = assertThrows(RuntimeException.class, () -> new ErrorObject().alwaysFail(1, "a", true)); assertEquals("error message", exception.getMessage()); ``` In general, the syntax for testing exceptions is this: ```java= Exception e = assertThrows(<exception type>.class, () -> <object of class you want to test>.<method call with parentheses and parameters>); assertEquals(<error msg as String>, e.getMessage()); ``` If you need to test an exception thrown in a constructor, the syntax is this: ```java= Exception e = assertThrows(<exception type>.class, () -> new <constructor call with params>); assertEquals(<error msg as String>, e.getMessage()); ``` ## Handing In After completing this assignment, the following solution files should be in your `sol` directory, all as part of the `sol` package:  * `IList.java` containing `public interface IList<T>` * `Node.java` containing `public class Node<S>` * `MutableList.java` containing `public class MutableList<T>` * `Homework2TestSuite.java` containing `public class Homework2TestSuite`, which thoroughly tests your doubly-linked list implementation. * `memory.pdf` or `memory.png`, containing the memory diagram you drew for the environment/heap diagram question/ Submit your files to the **Homework 2: Implementation** assignment in Gradescope. In addition, submit your test file to the **Homework 2: Testing** assignment in Gradescope. See [our gradescope submission guide](https://hackmd.io/oTbF1IUuRs27VgVJF4z2rA?view) for an explanation on how we are grading your tests, and how you can use the Testing assignment on Gradescope to get a better understanding of the assignment. Once you have handed in your files, you should receive an email, more or less immediately, confirming that fact. If you don’t receive this email, try handing in again, or ask the TAs what went wrong. **Note:** If your code does not work with the autograder, make sure you are using the `AutograderCompatibility` file and check the assignment FAQ on Ed for common errors. If those don't locate the problem, contact the TAs via hours or Ed. ## FAQ Please see the [HW2 FAQ post](https://edstem.org/us/courses/16807/discussion/1130416) on Ed, where we will post answers to common questions. :::spoiler Errors about converting between `Integer` and int? *Note:* `IList<Integer>` takes in the `Integer` object, which is a "wrapper" type and cannot take in the `int` primitive type (you don't need to know this in depth as of right now, just know they are different types). When you are trying to compare an `Integer` and an `int`, you have to convert an `Integer` to an `int` by adding `.intValue()` to the end of your `get` method and such as shown above. ::: <br> </br> **How do I test `methods`?** The format for testing a `method` is as follows: ```java= @Test public void <test-name>() { // code that tests the specific method } ``` In practice, it looks something like this: ```java= @Test public void testOne() { assertEquals(2, 2); } ``` ### *Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the [anonymous feedback form](https://docs.google.com/forms/d/e/1FAIpQLSdFzM6mpDD_1tj-vS0SMYAohPAtBZ-oZZH0-TbMKv-_Bw5HeA/viewform?usp=sf_link).*