CS2230 Computer Science II: Data Structures Homework 3
Linked list of web browser tabs
1. Goals for this assignment
• Implement methods for a linked list that involve manipulating references
• Debug your code using JUnit tests
2. Submission
Source address
https://research-git.uiowa.edu/cs2230-assignments/browser-tabs-fa19.git
Private address
https://research-git.uiowa.edu/cs2230-fa19/hw3-hawkid.git
General requirement: You must make at least one commit for each Part of the homework in order to receive credit for doing that Part. The name of this commit should be Part X where X is a number (between 1 and 5). The places where you need to commit are clearly labeled “STOP!”. It is okay to have additional commits in between these required ones.
3. Setup
As usual, setup your IntelliJ project from the cloned code. The only difference is in the step where you add Junit, please use ‘Junit 4’ (previous assignments and lab exam used ‘Junit 5’).
4. Description
In this project, you will implement a LinkedList class (in LinkedList.java) with various methods for manipulating it. There will be two ways to test your implementation. First, we’ve provided a complete JUnit test file. Second, we’ve provided an application called Browser, which uses your LinkedList to display and manipulate tabs like a web browser would.
As you implement more methods of LinkedList, you will pass more of the tests and enable more features of the Browser application. You are only required to make changes to LinkedList.java. However, we recommend you add your own additional tests to LinkedListTest.java.
This project has a setup part and 5 parts. The best way to approach the project is in the order of these parts. You should try to pass all the tests specified in Part 1 before continuing to Part 2, and so forth. A submission that passes the tests in Part1 and doesn’t implement anything else will score better than a submission that attempts all parts and passes zero tests. The rubric on ICON reflects this emphasis.
Also, see the last section “Helpful Tips” for information that is useful for all the parts.
5. Part 0b: List interface and LinkedList method signatures
5.1. End result of Part 0b
• The code compiles with no errors
• The tests in LinkedListTest run; they do not need to pass yet (but some might pass on
accident; that is okay)
5.2. What to do
Look at LinkedList.java. The class implements the List interface, which is defined in List.java. You’ll notice that there is one compiler error. The red underlining is over the line:
public class LinkedList implements List {
and the compiler error says:
Class ‘LinkedList’ must either be declared abstract or implement abstract method ‘method name’ in List.
where ‘method name’ might be any of the methods declared in List.
Your job in this part is to add all the required methods to LinkedList class such that all compiler errors are gone. You should not attempt to correctly implement any of these methods yet. If the method has a non-void return type, then you will need to return something. In these cases, add a return statement that returns some default value of the type: null is a good choice for Objects, 0 is a good choice for int. This will eliminate compiler errors like “missing return statement”.
Here’s an example for the add method. That method is declared in List as:
void add(int i, Object e) throws IndexOutOfBoundsException; In LinkedList, you need to include:
5.2.1. HINTS
• LinkedList implements List, so it must define all the methods declared in List, with exactly the same signatures (see above example of add).
• Look at the size() method in LinkedList for an example.
• Look at the toArray() method in LinkedList for another example.
• We’ve left comments that look like “Part 1: add …”, “Part 2: get …”. You should put your
methods below the corresponding comment.
When you eliminate the compiler errors, you’ll be able to run the LinkedListTest and see the JUnit output. You’ll see lots of failed tests! The rest of the assignment deals with passing them.
6. Part 1: instance variables, constructor, size, add, and toArray
6.1. End result of Part 1
• pass these tests
o testToArrayEmpty
o testToArrayAdd1
o testToArrayAddMore
o testSizeEmpty
o testAddSize
o testToArrayAddDifferentOrder o testAddIndexTooBig
o testAddIndexTooSmall
• make these Browser commands work o new
o count 6.2. What to do
In this part, you must fill in instance variables, the implementation of the LinkedList constructor, LinkedList.size, LinkedList.add, and LinkedList.toArray. See the comments above each method in LinkedList.java for details. Notice that we provided the inner class Node already. Its data field is type Object, which means that you can store anything in the LinkedList. In the tests, we store integers in the LinkedList, but in the Browser application we store Tabs.
public void add(int i, Object e) throws IndexOutOfBoundsException { }
Note that LinkedList.add needs to throw IndexOutOfBoundsException when the index is less than 0 or greater than size. We’ve provided an easy way to accomplish that. Simply call the checkIndex method. For example, the add method requires you to throw an exception if the given index i is less than 0 or greater than size(), so you should include this line in your add method:
checkIndex(i, size()+1);
Implement and debug until the above tests pass.
6.3. Trying the browser commands (new, count)
To run the Browser application, right click Browser.java > Run file. The application will print out the commands you can run.
new
You should be able to type something like
new www.uiowa.edu
and see the output
|0 The University … |
new
Each time you enter the new command, a new browser tab is added to the end.
new stackoverflow.com
|0 The University … | |1 Stack Overflow |
new
You can also run the count command.
|0 The University … | |1 Stack Overflow |
new
count
You currently have 2 tabs open.
|0 The University … | |1 Stack Overflow |
new
If you try to run the other commands (other than exit), expect to see some kind of error or strange behavior, since you haven’t implemented enough of LinkedList yet.
STOP! Do not continue until everything above works.
Commit and push your latest code before making further changes. 7. Part 2: get
7.1. End result of Part 2
• pass these tests o testGet1
o testGetBigger
o testGetIndexTooBig
o testGetIndexTooSmall
• make these Browser commands work o display
7.2. What to do
In this part, you must fill in the implementation of the LinkedList.get method. See the comments above the method in LinkedList.java for details.
Once you implement this method, the above tests and functionality should work.
7.3. Trying the browser commands (display)
In the Browser application, you can use display to open up the desired web page. Use the number next to the tab’s title.
|0 The University … | |1 Stack Overflow |
new
display 1
(will open up stack overflow in your system’s default web browser)
STOP! Do not continue until everything above works.
Commit and push your latest code before making further changes.
8. Part 3: set
8.1. End result of Part 3
• pass these tests o testSet1
o testSetMore
o testSetSize
o testSetIndexTooBig
o testSetIndexTooSmall
• make these Browser commands work o navigate
8.2. What to do
In this part, you must fill in the implementation of the LinkedList.set method. See the comments above the method in LinkedList.java for details.
Once you implement this method, the above tests and functionality should work.
8.3. Trying the browser commands (navigate)
In the Browser application, you can use navigate to have a Tab go from one website to another. Use the number next to the tab’s title and the url of the new website.
|0 The University … | |1 Stack Overflow |
new
navigate 1 acm.org
|0 The University … | |1 Association for… |
new
STOP! Do not continue until everything above works.
Commit and push your latest code before making further changes. 9. Part 4: remove
9.1. End result of Part 4
• pass these tests
o testRemove1
o testRemoveBigger o testRemoveAndGet
o testRemoveGetAdd
o testSizeRemove
o testSet (because it has remove) o testRemoveIndexTooBig
o testRemoveIndexTooSmall
• make these Browser commands work o close
9.2. What to do
In this part, you must fill in the implementation of the LinkedList.remove method. See the comments above the method in LinkedList.java for details.
Once you implement this method, the above tests and functionality should work.
9.3. Trying the browser commands (close)
In the Browser application, you can use close to remove the desired tab. Use the number next to the tab’s title.
|0 The University … | |1 Stack Overflow |
new
close 0
|0 Stack Overflow |
new
STOP! Do not continue until everything above works.
Commit and push your latest code before making further changes.
10. Part 5: move
10.1. End result of Part 5
• pass these tests
o all of the remaining tests
• make these Browser commands work o move
10.2. What to do
In this part, you must fill in the implementation of the LinkedList.move method. See the comments above the method in LinkedList.java for details.
10.2.1. Moving is not swapping
As you can see from the tests and the examples in LinkedList.move comments, move does not
swap two elements; rather, it moves an element to a new location.
TIP: If you are having trouble with implementing move, try to break the problem down into
simpler steps.
Once you implement this method, the above tests and functionality should work.
10.3. Trying the browser commands (close)
In the Browser application, you can use move to move the desired tab to the desired location. Move takes two integers. The first integer specifies the tab to move, and the second number specifies the position to move it to.
|0 Stack Overflow | |1 The University … | |2 Wikipedia | |3 Association for… |
new
move 3 1
|0 Stack Overflow | |1 Association for… | |2 The University … | |3 Wikipedia |
new
move 1 2
|0 Stack Overflow | |1 The University … | |2 Association for… | |3 Wikipedia |
new
Commit and push your code to submit. 11. Helpful Tips
• A lot of LinkedList’s public methods need similar things. It may be useful to create private helper methods, such as one that returns a reference to the 𝑖𝑡h Node (like LinkedList.get except it returns the Node instead of the Object stored in it).
• For each method, write down your algorithm on paper with boxes and arrows before writing code. And, try your paper algorithm on different cases. We cannot emphasize this point enough, so it is repeated again below.
• For each method, write down your algorithm on paper with boxes and arrows before writing code. Did you do it this time?
• What you can do when a test fails.
First, great job (That’s not sarcasm!). If you made a test fail, you are one step closer to a
working program. Almost no program works the first time around.
Pick one test to try to fix. Expand its error message. Clicking the filename/line number of a line in the stack trace (i.e., the list of method calls that your program was in when it crashed) will take you to the line of code where the error happened.
If the error is a NullPointerException, this means you used dot (.) on a reference that is currently null. Either it is okay that the reference is null and you just shouldn’t be using dot on it, or the reference became null by some error in your code.
If the error is a JUnit assertion error (actual and expected results are different), then you must reason about the current state of the LinkedList and why the method would return the wrong value. If you need to print the state of your linked list and your toArray method works, then one easy way to print it out is with System.out.println(Arrays.toString(ll.toArray)).
11.1. Debugger
The debugger is an alternative to inserting print statements into your code. It allows you to stop the program at the line you want and then inspect the current values of variables.
To use the Java debugger in IntelliJ, run the tests using ‘Debug LinkedListTest’ instead of ‘Run LinkedListTest’. The debugger will only be useful if you first set a breakpoint in your program. A breakpoint is a place where the program will stop running and give control to the debug, where you can step through the program and check variable values.
Set a breakpoint by clicking in the left grey sidebar of the IntelliJ editor. You can set a breakpoint in any .java file you want, not only the test file.