CSE 373, Spring 2018: Homework 2: Part 1

Summary

Due Friday April 13 at 11:59pm

In this half of the assignment, you will implement the data structures you will be using on the second half.

You will be modifying the following files:

• main.java.datastructures.concrete.DoubleLinkedList.java
• test.java.datastructures.TestDeleteFunctionality.java
• test.java.datastructures.TestDeleteStress.java
• main.java.datastructures.concrete.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):

• test.java.datastructures.TestDoubleLinkedList.java
• main.java.datastructures.interfaces.IList.java
• test.java.datastructures.TestArrayDictionary.java
• main.java.datastructures.interfaces.IDictionary.java
• main.java.experiments.*

In particular, the experiments are a portion of the writeup due with part 2 of this project, but rely on the data structures in this portion. 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.*;

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)
2. Implement the IList interface.
3. Be as asymptotically efficient as possible.
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 listnode 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.

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

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

Part 1b: Write missing tests

Task: Modify TestDeleteFunctionality, and TestDeleteStress and add in tests for the delete method.

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.

A few additional notes:

• To help facilitate grading, we ask that you split your tests into two groups. All tests that check and make sure your delete(...) behaves correctly and matches the IList specification should be placed within the TestDeleteFunctionality file.

  Please keep all tests within TestDeleteFunctionality short. Every test you add to this file should have a timeout of a second or less. (You're encouraged to add as many tests as you want, however.)

  Add any stress tests to TestDeleteStress. Stress tests are tests that either (a) focus on testing to make sure your code is efficient or (b) focus on testing to make sure your code is correct when it's asked to handle large amounts of data.

  Please see the existing stress tests in TestDoubleLinkedList to get a sense of what sorts of timeouts and list sizes you should be using.

• Your stress tests do not need to be particularly complicated. We'll be assessing your tests by copying them into many different projects that contain deliberately buggy implementations of delete(...). Most of these implementations will contain actual bugs that can be caught by your TestDeleteFunctionality tests; only one or two of them will be functionally correct yet grossly inefficient.

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

  1. JUnit tutorial
  2. Tips on testing code

Part 1c: 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.

Dictionary<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").

If you finished early...

If you finished early, you may want to start on the writeup portion of this project (see the homework 2, part 2 spec for more details). While the writeup is not due this week, it contains questions that focus exclusively on material from part 1.

You may find working on the writeup to be a good way of helping you determine whether your data structures are designed soundly.

Deliverables

The following deliverables are due on Friday April 13 at 11:59pm.

A single person from your partnership should submit the entire contents of your src folder as a zip file on Canvas.

Please follow the above instructions EXACTLY. Do not remove, rearrange, or rename any files or folders: just zip your src folder. (This means you will be submitting a lot of instructor-provided code along with your files. This is fine.)

Before submitting, be sure to double-check that:

• You are submitting your completed TestDeleteFunctionality, TestDeleteStress, DoubleLinkedList, and ArrayDictionary classes which all behave as expected.
• You ran checkstyle and fixed all issues it reported with the files you edited.