Lab 07: DoubleLinkedSeq
The Sequence ADT Using Linked Lists

1 Introduction

A sequence is an ordered list of elements that grows as necessary to hold everything you try to put in it. For this assignment you will develop a sequence abstract data type (ADT) using linked lists. Recall that an ADT defines a type and a set of operations on that type. It is abstract in the sense that users of the type don’t need to know about the details of how the data is stored or how the operations work – they just work.

A sequence has a notion of a “current element." Several of the operations on a sequence are in terms of the current element.


2 Details

For this assignment, you will implement the DoubleLinkedSeq class described in Section 4.5 of your textbook (pages 235-238). See the API documentation in the text for a description of the class and the methods that it must provide. Additionally, you must provide (1) a toString() method that returns a String representation of the DoubleLinkedSeq and (2) an equals() method that determines if two DoubleLinkedSeq are equal.

1. The toString() method must return a string in the following form. If the sequence is empty, the method should return “<>”. If the sequence has one item, say 1.1, and that item is not the current item, the method should return “<1.1>”. If the sequence has more than one item, they should be separated by commas and a space, for example: “<1.1, 2.2, 3.3>”. If there exists a current item, that item should be surrounded by square braces. For example, if the second item is the current item, the method should return: “<1.1, [2.2], 3.3>”.
2. the equals() method should return true if the two sequences contain the same number of elements, if the corresponding entries in the sequence are the same, and if they have the same current element.

Activity Steps

1. Log on to the student machine. Change to your 2440 directory. Make a new Lab07 directory in your CS 2440 directory. Change to this directory. From within this directory, copy the "starter code" from /u/classes/2440/Fall2016/Sequence2/src. Make sure that you do a recursive copy!
2. You should have copied four files: DoubleLinkedSeq.java (src/skeleton), DoubleLinkedSeqTest.java (src/tests), TestDoubleLinkedSeq.java (src/util), and DoubleNode.java (src/util). You will be implementing the DoubleLinkedSeq described in the textbook. If you use the DoubleLinkedSeq.java that you copied, you will have the ADT from the book, and I added stubs for all the methods. To get past the compiler, all methods that return a value have some arbitrary dummy value returned.
3. Rename the skeleton directory to ‘solution’ and open src/solution/DoubleLinkedSeq.java

First edit the first line so that it reads “package solution;” instead of “package skeleton;”
4. If everything is setup correctly, it should compile with the following (from within the Lab07 directory):

 $ javac -cp .:src:/usr/share/java/junit-4.10.jar src/*/*.java
5. Add the fields to your class. You must use a linked list. I suggest using the five fields suggested by the book - manyNodes, head, tail, precursor, and cursor.
6. One by one implement the methods your class. As you implement your methods, test your code. There is a class TestDoubleLinkedSeq.java that has a menu that allows you to test a single method, and it displays the sequence after each test is done. However, their display method calls your start(), advance(), getCurrent(), and isCurrent() methods, so you will need to write those before you can make much sense out of that test program.You will also need to have your clone() method written to prevent errors in TestDoubleLinkedSeq.java and DoubleLinkedSeqTest.java.
7. Finally, when you have all the methods written and tested, compile and run the JUnit DoubleLinkedSeqTest to find out approximately what your lab grade will be:
Note: all of the following commands assume that your current working directory is Lab07.

To compile your java files into .class files:

$ javac -cp .:src:/usr/share/java/junit-4.10.jar src/*/*.java
To run the JUnit tests:

$ java -cp .:src:/usr/share/java/junit-4.10.jar org.junit.runner.JUnitCore tests.DoubleLinkedSeqTest
It probably will be hard to read all the output from the test. You can redirect the output to a file, and look at the file:

$ java -cp .:src:/usr/share/java/junit-4.10.jar org.junit.runner.JUnitCore tests.DoubleLinkedSeqTest > output
To run TestDoubleLinkedSeq.java:

$ java -cp .:src:/usr/share/java/TestDoubleLinkedSeq.java util.TestDoubleLinkedSeq
To make sure your project passes checkstyle:

1. Make sure checkstyle-all-4.4.jar and cs_appstate.xml are in your project directory:
 $ wget http://cs.appstate.edu/~rmp/checkstyle-all-4.4.jar
 $ wget http://www.appstate.edu/~waterscg/cs_appstate.xml
2. Run checkstyle:

 $ java -jar checkstyle-all-4.4.jar -c cs_appstate.xml src/solution/*.java

3. If your code passes all checks you should see:
 Starting audit…
 Audit done.
To submit your project to Web-CAT use the command line interface:

1. Make sure webcat-submitter-1.0.5.jar and webcatSubmit are in your project directory:
 $ wget http://cs.appstate.edu/~rmp/webcat-submitter-1.0.5.jar
 $ wget http://cs.appstate.edu/~rmp/webcatSubmit
2. Make sure that webcatSubmit is executable:
 $ chmod 0755 webcatSubmit
3. Run the submitter (please notice the period, it means submit the current working directory):
 $ ./webcatSubmit .
4. Enter the number to the left of the name of the lab.
5. Enter your user name and password.
6. Login to Web-CAT to view your results.
7. For more information, see Submitting an Assignment to Web-CAT via the command line.