Project 1: Linked Lists and Confetti
Due: Thursday, 12 July 2012, at 23:59:59 PDT
Overview
In Project 1 you will (a) implement a doubly-linked list, including an Iterator over that
list. In particular, you will implement the List12 interface. Note that you must
implement a doubly-linked list -- you cannot, for instance, instead implement an array-based
list. In addition, you will (b) implement a series of unit tests, both to test the correctness of your
own DoublyLinkedList12 class, and to test that of your classmates.
NOTE -- in P1, you will be implementing a "non-Generic" version of a doubly linked list.
(If you don't know what Java Generics are, don't worry about this -- we will cover it next week.)
Maximum total score: 15 points (12 for part (a), 3 for part (b)).
Details on part (a)
Download the List12 interface; its Javadoc can also be
viewed here. Notice that List12 inherits from
java.util.Iterable; hence, your implementing class must implement both the methods
listed in List12.java and in the parent interface as well.
Then, download the DoublyLinkedList12.java skeleton file, which
implements the Node class as an inner class (we will discuss these more next week). Note that
this skeleton will not compile until you implement a variety of other methods, according to
the List12 interface specification.
Then, implement inside the file DoublyLinkedList12.java
a class DoublyLinkedList12 that implements the interface List12.
It must implement a doubly-linked list. If you implement, say, an array-based list
instead, you will get 0 credit. Your source file DoublyLinkedList12.java
should clearly contain your full name and student ID in a comment at the very top of the file.
To get started, try to implement a cleanly structured DoublyLinkedList12 without
a correctly functioning Iterator (for the iterator() method, just return null
initially). After your DoublyLinkedList12 works correctly and passes your tests (see part (b)), then
implement the Iterator to complete the assignment.
You may use "dummy" head and tail nodes if you wish (I recommend this because I think it's easier),
but you are not required to do so.
Grading
Your submission will be graded automatically by a computer program as well as by manual
inspection (to make sure you actually implemented a linked list and not an array-basd list).
Try to anticipate the kinds of tests we will run on your code -- how might we "stress" your code to its limit? We
will do our best to find tiny bugs in your code that can result in data structure inconsistencies.
Maximum score on part (a): 12 points. A maximum of 10 points will be given based
on the correctness of your doubly-linked list based on our automatic testers. 7 of these points will be
from the doubly-linked list without iterators, and the remaining 3 points will be for the Iterator itself.
1 point will be given for correctly identifying your personalized vegetable. Finally, 1 point will be given
for coding style (at the grader's discretion), including clean structure, consistent formatting and
indentation, and helpful comments.
Details on part (b)
Using the junit 4.8.2 (note the version number!) unit testing
framework (download it here),
you will develop a set of unit tests with which to verify
the correctness of your linked-list. You should create one single
Java file, DoublyLinkedList12Tester.java, which contains
all the tests. You can use this "tester" to test your
DoublyLinkedList12 implementation from Part 1
of this assignment. However, your tests must also detect
bugs in someone else's (possibly faulty) linked-list
implementation. We will test multiple implementations of
DoublyLinkedList12 -- some faulty, and some correct -- using
your test code. You must use junit-4.8.2 -- you cannot use a different version of junit.
Black-box versus white-box testing
In P1 you will be conducting black-box testing
of the of DoublyLinkedList12.
This means that your test routines should not "peer" into the internal workings (e.g., instance variables)
of the DoublyLinkedList12 class you are testing. If you do so (despite this warning), then you will
likely get 0 credit because your test code will not compile against someone else's DoublyLinkedList12
implementation (which may use different instance variables). Note that this contrasts with white-box testing, where you
do inspect the "inner workings" of a class. For the sake of clarity:
In your test code in P1, you should test the DoublyLinkedList12 implementation using only the methods specified in
the public List12 interface.
Getting started
Create a file called DoublyLinkedList12Tester.java and import the following classes:
import java.util.*;
import org.junit.*;
import org.junit.Assert.*;
Then, create a class called DoublyLinkedList12Tester which contains a number of unit test methods.
To mark a method as being a "unit test", you should annotate the method using the
@Test keyword. Here's an example:
@Test public void testAddOneElement () { // Pretty weak test!
final DoublyLinkedList12 list = new DoublyLinkedList12();
list.add("test");
Assert.assertEquals(list.size(), 1);
}
Note: your test methods should not return anything, nor should they print out anything.
Instead, each of your test methods should include at least one call to an "assert" static method in the Assert
class to verify that a specific condition is true.
Compiling your code
To compile your test code, first copy the junit-4.8.2.jar file into your current directory.
Assuming DoublyLinkedList12.java and DoublyLinkedList12Tester.java are also in the current
directory, run: javac -cp .:junit-4.8.2.jar DoublyLinkedList12Tester.java.
Running your code
To run your tester, you will invoke junit's unit testing framework -- it will scan your
DoublyLinkedList12Tester.class file for all methods annotated with the @Test keyword
(using something called "reflection"), and it will run each of these tests. At the command line, run
java -cp .:junit-4.8.2.jar org.junit.runner.JUnitCore DoublyLinkedList12Tester.
Grading part (b)
We will submit a variety of implementations of DoublyLinkedList12 to your tester, including some of your
classmates, and some of our own. Some will be correct, and some be buggy. On every fully correct implementation
of DoublyLinkedList12, all of your tester's unit tests should pass. On every buggy implementation of
DoublyLinkedList12, at least one of your tester's unit tests should fail. You will receive up to 3 points
for correctly failing or correctly passing these DoublyLinkedList12 implementations.
Confetti
As a visually stimulating reward for your effort in implementing your list, you will be treated
to a confetti party, implemented in a set of pre-compiled Confetti
classes. Note: you must run unzip Confetti.zip to extract the individual class files.
You can then run the
Confetti simulator by typing java Confetti. (Make sure Confetti.class,
DoublyLinkedList12.class, and any other class files resulting from inner classes you
implement are in the working directory.) Confetti will use your DoublyLinkedList12
to manage the confetti particles. Note that successful execution of the Confetti program, while
encouraging, does not guarantee that your linked list implementation is fully correct -- you still
need to test it thoroughly yourself.
The Confetti simulator includes two buttons (see the screenshot below): one to
add more confetti, and one to remove confetti. In the simulation window, there is some invisible
"glue" on the screen which you cannot see because it is white. The glue spells out a word -- an
individualized vegetable just for you. (You may not all receive unique vegetables, but there
are about a dozen different choices.) The confetti particles will stick to the glue. To read
the vegetable name most easily, add lots of confetti particles to the simulation (about 4000 usually does
the trick), and then remove the dangling confetti. The confetti stuck to the glue will not
be removed, which which render the vegetable name easily to read. Note that the Confetti simulator
may crash if your linked list is not implemented properly!
Once you have identified your individualized vegetable, create a file called vegetable.txt containing
your vegetable name (and no other text). This will be the second of your submission files.
Your individualized vegetable is based on your
CSE 12 username on ieng6.ucsd.edu; hence, make sure you log on to this machine when
determining your personalized vegetable.
Submission
Submit your work using the
bundleP1 script in the directory containing your
DoublyLinkedList12.java, DoublyLinkedList12Tester.java, and vegetable.txt files.
Make sure you are logged on to ieng6.ucsd.edu using your CSE 12-specific account.
As always, make sure to submit before the deadline -- the script will show you (or anyone else) no mercy!