CSE 373, Summer 2019: P1 Part 1

Summary

Due Wednesday, July 10 at 11:59pm.

Submit by pushing your code to GitLab. If you intend to submit late, fill out this late submission form when you submit.

In this half of the assignment, you will implement the data structures you will be using for the rest of the quarter in later projects. For this reason, it's very important in this part of the project to make sure you work out all of the potential bugs you might have in your code—oversights in this part may end up causing bugs for the entire rest of the course.

You will be modifying the following files:

• src/main/java/datastructures/lists/DoubleLinkedList.java
• src/test/java/datastructures/lists/TestDoubleLinkedListDelete.java
• src/main/java/datastructures/dictionaries/ArrayDictionary.java

Additionally, here are a few more files that you might want to review while completing the assignment (note that this is just a starting point, not necessarily an exhaustive list):

• src/main/java/datastructures/lists/IList.java
• src/test/java/datastructures/lists/TestDoubleLinkedList.java
• src/main/java/datastructures/dictionaries/IDictionary.java
• src/main/java/datastructures/dictionaries/KVPair.java
• src/test/java/datastructures/dictionaries/TestArrayDictionary.java
• src/test/java/datastructures/dictionaries/BaseTestDictionary.java
• src/test/java/misc/BaseTest

WARNING: For all assignments, you should modify only the files we explicitly list at the top of the assignment page as needing modifications. All changes in other files will be ignored during grading. If you accidentally change one of these files, your code may not compile when we're grading, in which case we may not grade your code, and you'll get a zero on the assignment. If you need to temporarily change one of these files for debugging, make sure you revert your changes afterwards.

Also, absolutely DO NOT change the gitlab-ci.yaml config file. This file affects what the GitLab runners run; you have no reason to change this, and if you do, you may lose the ability to get feedback from the runners. Also don't change the build.gradle file, since your IDE needs that check project dependencies.

Note that the most important information for the programming assignments (the expected input and output, and any special cases) tend to be found in the files themselves. This page serves as an general guide to the assignment; the details tend to be found more often within the files themselves.

import java.util.Scanner;

import java.util.*;

We recommend reading through this entire assignment page before you begin writing code. We also have a video overview for this part with some additional tips for after you read the assignment, but before you start coding.

DISCLAIMER: This video was recorded during a previous quarter of the course. Project 1 has changed quite a bit since then, so some of the information in this video may be out of date. If you need any clarifications on the spec, please ask them on Piazza or come to Office hours.

Part 1a: Implement DoubleLinkedList

Task: Complete the DoubleLinkedList class.

A doubly-linked list is a similar to the singly-linked lists you studied in CSE 143 except in two crucial ways: your nodes now have pointers to both the previous and next nodes, and your linked list class has now have pointers to both the front and back of your sequence of list node objects.

Visually, the singly linked lists you studied in CSE 143 look like this:

Doubly-linked lists containing the same data will look like this:

Your implementation should:

1. Be generic (e.g. you use generics to let the users store objects of any types in your list)
   • You might remember that in LinkedIntList we used int throughout our code when we accept values to add, to return from get, etc. In this generic class you will implement, you will reference and use T (or whatever placeholder that was declared in the class header) throughout.
2. Implement the IList interface. This means you will be using this file extensively as a template for what your code will do.
3. Be as asymptotically efficient as possible.
• If there is an \(\mathcal{O}(1)\) way of implementing a functionality, perhaps don't use an \(\mathcal{O}(n^3)\) implementation.
4. Contain exactly as many node objects as there are items in the list. (If the user inserts 5 items, you should have 5 nodes in your list).

Warning: correctly implementing a doubly-linked list will require you to pay careful attention to edge cases. Some tips and suggestions:

• Think carefully about the end cases (front and back) and what should happen when the list is empty or nearly empty.

• Write pseudocode for your methods before writing code. Avoid immediately thinking in terms of list node manipulation – instead, come up with a high-level plan and write helper methods that abstract your node manipulations. Then, flesh out how each helper method will work.

  Or to put it another way, figure out how to refactor your code before you start writing it. Your code will be significantly less buggy that way.

  Although the suggestion above is preferred, you can still use private helper methods after noticing redundancy in your code. That is, if you notice yourself writing similar code in many different methods, it's not too late! Try to factor that similar code into a private helper method to eliminate future bugs.

• Keep in mind the differences between objects and primitives (int, double, etc). This will come up in two ways: one, you'll need to remember that changing an object might change the reference in another place, and two, you'll need to remember to use == to compare equality for primitives and nulls, and use .equals() for object comparisons.
  • Tip: you may use java.util.Objects to handle your equality checks with possibly-null values instead of juggling the == and .equals() yourself (remember that you can't call .equals() on null!). Here's documentation for the relevant method.

Tips for Implementing DoubleLinkedList Iterator

When implementing DoubleLinkedList, you will also need to implement an iterator for the class.

You should have studied iterators in CSE 143, and we should have (briefly) covered them in lecture, but here is a review of what iterators are in case you need it:

An iterator object is a kind of object that lets the client efficiently iterate over a data structure using a foreach loop.

Whenever we do something like:

for (String item : something) {
    // ...etc...
}

...Java will internally convert that code into the following:

Iterator<String> iter = something.iterator();
while (iter.hasNext()) {
    String item = iter.next();
    // ...etc...
}

When you call iter.next() for the first time, the iterator will return the first item in your list. If you call iter.next() again, it'll return the second item. Once the user calls iter.next() enough time and encounters the last item in the list, calling iter.next() once again should throw an NoSuchElementException.

The iter.hasNext() method will return true if calling iter.next() will safely return a value, and false otherwise.

You can see an example of this expected behavior within your tests.

Notice that the iterator is behaving somewhat similar to a Scanner, except that it's iterating over a data structure instead of a String or file.

In practice, iterators can also be used to safely modify the object they're iterating over. We will not be implementing this functionality in this class: you should assume the client will never modify a data structure while they're iterating over it.

Sanity check: when we say that iterators provide efficient iteration over a datastructure, each iterator method should run in \(\mathcal{O}(1)\) runtime, where n is the size of the data structure.

Part 1b: Write missing tests

Task: Add tests for the delete method to TestDoubleLinkedListDelete.

In part 1b, you will practice writing some unit tests using JUnit.

Start by skimming through TestDoubleLinkedList.java and familiarize yourself with the tests we have given you. Since this is the first assignment, we've given you most of the tests you need, except for a few. Can you see what tests are missing?

There are no tests for the DoubleLinkedList.delete(...) method! Your job here is to write tests for this method.

You are responsible for writing tests that ensure your delete method is fully working. The ability to create a comprehensive set of tests for a given piece of code is a foundational skill in programming. To do this you'll want to think about all the different ways your code could be broken. Often it is helpful to think of these possible bugs in categories:

• Expected Behavior: the obvious or most common uses of your code should function correctly
• Edge Cases: your code should function properly at the edges of expected behavior such as interacting with first or last elements.
• Empty Case: your objects should behave properly when they are initially empty or become empty due to usage
• Invalid Input: your code should properly protect itself from improper usage such as bad inputs or operations state mismatch
• Scale: (Note: you should not implement any scale tests in this project) your code should be efficient enough to perform appropriately when tasked with larger sets of data or invocations

To help you out this first time, below are some test case ideas for the expected behavior category that we suggest you implement. That is, turn each of the following expected behavior cases into its own JUnit test method.

Note: this is not a comprehensive list of cases, (even for just the expected behavior category!) so you should add more tests as you think of them. And of course, you should write tests for the other categories as well.

• testDeleteBasic: call delete multiple times, trying a different index each time, on a list that has enough elements to delete. Assert that the list is what you expect after each delete call.
• testDeleteWithMutators: delete an element at a specific index in combination (before and after) with calling methods that can modify the list at that index (set, insert, add, etc.), and assert that the list is what you expect frequently.
• testDeleteSameIndex: call delete with the same (valid) index parameter repeatedly and assert that the list is what you expect after each delete call.
• and you should add more test cases as you think of them ...

Testing Tips

Whenever you want to check the state of the list, you'll need to call its methods that tell you information about it (size, get, indexOf, contains, etc.). You'll combine the returns of these methods with use some of the JUnit assert methods (usually assertThat and is) to check the returned value matches our expected result. To aim to be comprehensive, you should use these methods very frequently. Almost all of the tests should involve modifying the list with delete and then checking that the list is what you expect afterwards, so some combination of these methods should be used every time. If you take a peek at the provided tests inside TestDoubleLinkedList and the testing handout from section you'll see plenty of good examples and ideas for how to check your list afterwards.

One other helper method you may find useful is listContaining - this method takes in an input array to compare against, and when combined with assertThat, will make sure the list is one that contains the input array values in the specified order. See basicTestAddAndGet for an example. Note that this method only checks the state of the list with the get and size methods. While it is useful (please do use it), it does not check every other accessor method listed above. So be sure to not rely on solely this helper method; instead, you should utilize all of the accessors above across your tests to more completely check the list state.

As a sanity check: when implemented as intended, each of the cases should have at the very least one assert method (assertThat, assertThrows, etc.).

A final testing tip: you may find yourself wondering if there is any other way to precisely check the inside state of your DoubleLinkedList instead of relying on public methods that also may have uncertain correctness. It turns out that your tests will have access to the package-private fields (the front field, the back field, etc.) and the Node class so that you can actually check that front points to some object, that front.next points to some specific object, and basically you can check that all the .next, .prev pointers are exactly what you expect. You are not required to use this information in your testing, but you may find it helpful if you want your tests to be even more comprehensive. For reference, the additional tests we will grade you on also check that the internal pointers are correct. An example of checking the Node pointers can be found inside the testExample method inside TestDoubleLinkedListDelete here.

A few additional notes:

• Please keep all tests within TestDoubleLinkedListDelete short. Every test you add to this file should only take a second or less to run. (You're encouraged to add as many tests as you want, however.)

• You may find the following documents from the resources page to be particularly useful:

  1. How your code (and these tests) will be graded
  2. JUnit tutorial
  3. Tips on writing effective tests

Part 1c _(i): Implement ArrayDictionary

Task: Complete the ArrayDictionary class.

Your ArrayDictionary class will internally keep track of its key-value pairs by using an array containing Pair objects.

IDictionary<String, Integer> foo = new ArrayDictionary<>();
foo.put("a", 11);
foo.put("b", 22);
foo.put("c", 33);

Your internal array should look like the following:

Now, suppose the user inserted a few more keys:

foo.put("d", 44);
foo.remove("b");
foo.put("a", 55);

Your internal array should now look like the below. Notice that we've updated the old key-value pair for "a" to store the new value. We've also removed the key-value pair for "b".

This means you will need to scan through the internal array when retrieving, inserting, or deleting elements. If your array is full and the user inserts a new key, create a new array that is double the size of the old one and copy over the old elements. Minor design decisions, like the initial capacity of the array, are left up to you; choose something that reasonable and adjust if it seems necessary.

Once completed, the design and logic of your ArrayDictionary should feel very similar to the ArrayIntList objects you previously studied in CSE 143.

There is one general optimization we will have you implement. Because the values in the dictionary are inherently unordered, we can use this to our benefit in the remove method. Instead of shifting over all the elements as you would normally need to do to remove from an array, you should instead just replace the value stored at the index containing the element to be removed to be the last pair currently in the ArrayDictionary. Here is an example of what your internal representation may look like before, during, and after a single call to dict.remove("a").

Tips for Implementing ArrayDictionary Iterator

1. If you want examples on how to implement an iterator, see the DoubleLinkedListIterator you worked on in the section before, and also take a look at the tips and instructions from that section above.

2. Your iterator() method may return the key value pairs in any order you wish. The easiest approach would likely be to return them in the order your pairs are listed in your internal array.

3. You may assume the user will not modify the dictionary while you're iterating over it.

4. You may NOT create any temporary data structures such as a temp IList when implementing your iterator. We want our iterators to be efficient, and having to copy the contents of our dictionary to some other data structure at any point is suboptimal.

   You may, however, create new KVPair objects. (They do not count as "temporary" data structures).

5. We have provided you with unit tests for your iterators. You can add more tests if you want.

6. The IDictionary interface requires that its iterators return KVPair objects. However, your internal array inside ArrayDictionary uses Pair objects and has a field of Pair<K,V>[]. You will need to convert from your existing Pair objects into the KVPair objects within your iterator—see the method header comments in KVPair to understand how to instantiate new KVPair objects.

   Once we do this conversion, client programs of our IDictionarys can use KVPair, this publicly available class, as the things they're looping over. See the code snippet below for an example of looping over an IDictionary (where each element examined is a KVPair).

   IDictionary<String, Integer> foo = makeTheDictionary();
   for (KVPair<String, Integer> pair : foo) {
       String key = pair.getKey();
       Integer value = pair.getValue();
   
       // Do something with key and value
       System.out.println(key + " : " + value);
   }

   The above program should print out every key-value pair contained within foo.

Part 1c _{(ii) (highly recommended)}: Implement getOrDefault on your IDictionarys

The IDictionary interface includes a convenient getOrDefault method which will be useful in future assignments. This method either gets the value of a key in the IDictionary or returns the given default value if the key is not inside. IDictionary provides a default implementation of this method that simply calls containsKey; however, this method can be implemented more efficiently inside ArrayDictionary, where you have access to the data structures' internals. While implementing this method on your data structures is not strictly required, we recommend doing so, since it will make it easier for your to pass any efficiency tests later.

Individual feedback survey

After finishing the project, take a couple of minutes to complete this individual feedback survey on canvas, here.

Deliverables

The following deliverables are due on Wednesday, July 10 at 11:59pm.

Submit by pushing your code to GitLab. If you intend to submit late, fill out this late submission form when you submit.

Before submitting, be sure to double-check that:

• You are submitting your completed TestDoubleLinkedListDelete, DoubleLinkedList, and ArrayDictionary classes, which all behave as expected.
• You ran checkstyle and fixed all issues it reported with the files you edited.
• You submitted the individual feedback survey on Canvas.