Lab 2 - Generic, Doubly-Linked List (100 pts)

Due Monday, October 7 at 11:59pm on Canvas


Pair Programming Requirement (No Credit if You Do Not Complete this Lab As a Pair Program)

  • You should have found a partner by now. If not, please contact the instructor ASAP!
  • Both partners fill in, sign and date the pair programming contract and BOTH partners submit the contract.
  • Only one partner submits the lab assignment (your code) on Canvas. Please make sure both your names are on ALL the files.
  • Both partners follow the rules for pair programming.

Part 1: Making Your Lab 1 List Class Generic

  • For this Lab, you will need to convert your List class to become a generic class.
  • The purpose of using generics in this assignment is to allow the List to store any (Object) type.
  • Note that the previous Lab only stored data of the primitive type int
  • To store other data types, we do not want to have to write a whole new list class for each type, e.g. one for Strings, one for numerical data, and one for each type of Objects of other classes (such as classes that you write).
  • Fortunately, generic types exist in Java, which allow you to specify that any type of (non-primitive) Object be stored inside the same List class.
  • Note: primitive types - int, double, boolean, char - do not work with generics. Use their Object counterparts instead - Integer, Double, Boolean, and Character.
  • Other advantages of generics, include:
    • Strong type checking at compile time - The Java compile verifies at compile time that the type you specified the class to store, and any operations you make on data of that type, are legal.
    • Algorithms implemented as generic methods or classes are type-safe, generalized (not specific to one type only), and easy to read.
  • You will need to specify that you List holds a generic type of objects (not ints anymore).
  • To do so, follow these steps:

Step 1:

  • Open up your List file and add the following to the class definition:
public class List<T> {

Step 2:

  • Alter the Node definition to also work with generic data (we don't want it just to store ints anymore!):
private class Node {
private T data;
private Node next;

public Node(T data) {
this.data = data;
this.next = null;
}
}

Step 3:

  • For EACH method in the List class, you will need to examine it to determine whether it needs to be altered to work with our new generic class.
  • The Eclipse error messages can help you determine which methods need to change.
  • Below are two examples, where int has been updated to T:
Access Method Example:

    /**
     * Returns the value stored in the first node
     * @precondition length != 0
     * @return the value stored at node first
     * @throws NoSuchElementException when the
     * precondition is violated
     */
    public T getFirst() throws NoSuchElementException{
        if (length == 0) {
            throw new NoSuchElementException("getFirst(): "
                    + "List is empty. No first element.");
        }
        return first.data;
    }

Mutator Method Example:

    /**
     * Creates a new first element
     * @param data the data to insert at the
     * front of the list
     * @postcondition a new first element
     */
    public void addFirst(T data) {
        if (first == null) {
            first = last = new Node(data);
        } else {
            Node N = new Node(data);
            N.next = first;
            first = N;
        }
        length++;
    }

  • Reflection: Will methods such as getLength() and isEmpty() need to change?
Step 4:
  • Inside of ListTest.java, alter any calls to your List constructor to specify the type of data being stored by placing the type in angled brackets next to the word List.
  • The easiest approach would be to indicate the List stores type Integer so that your tests remain compatible with your new List class.
List<Integer> L1 = new List<Integer>();
  • Now, declare some new Lists of various types, such as String and Double.
    • Verify that your List works with these types as well. 

For More Information:

  • Read the Oracle Generics Tutorial here
  • Read chapter 5 of the course textbook

Part 2: Creating a Doubly-Linked List Class

  • The next part of your assignment is to alter the List class that you wrote in Lab 1 to be a doubly-linked list.
  • The principle difference between the singly-linked list that you wrote in Lab 1 and a doubly-linked List is that each node contains a reference to both to the next node and to the previous node in the List.
  • You can visualize a doubly-linked list like so:

Image source.

  • Therefore, your inner Node class will be updated to look like the following:

private class Node {
private T data;
private Node next;
private Node prev;

public Node(T data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
  • Additionally, bear in mind that the first Node of the list now has a prev Node reference to null while the last Node has a next Node reference to null.
  • The advantage of the prev reference is the ease with which we can traverse the list in both directions, and also perform some more challenging operations such as removeLast().
  • To account for the presence of this additional reference variable in the Node class, you will need to make updates to your code for many of the List methods.
  • Most of these updates are as simple as adding one line of code to the method.
  • However, addLast() will change significantly. Hint: remove the loop from this method!
  • For example, let's look at the insertFirst() method:
      /**
     * Creates a new first element
     * @param data the data to insert at the
     * front of the list
     * @postcondition a new first element
     */
    public void addFirst(T data) {
        if (first == null) {
            first = last = new Node(data);
        } else {
            Node N = new Node(data);
            N.next = first;
            first.prev = N;
            first = N;
        }
        length++;
    }
  • Important! Each time you update one of your methods, run your tests again to make sure your List is still working properly.
  • If you want more information on doubly-linked lists, you can watch this short video (8 min).


Part 3: Adding New Functionality to your List Class

  • Your doubly-linked list needs to be able to perform all of the same operations as your singly-linked list.
    • However, as you may have noted when writing Lab 1, the Lab 1 List class was very limited.
    • You could only add and remove data at the two ends of the List
    • What about the middle of the List?
  • How can we access data or insert and remove data from the middle of the List?
  • To increase the functionality of our class, we will be adding some new methods and a new field to the List.
  • First, add a new private field to the class to store the iterator - a node reference that we will use to move around the List container.
  • Unlike the first and last Nodes, which must always remain in the same location, the iterator will need to change positions in the List.
private int length;
private Node first;
private Node last;
private Node iterator;

  • All of the required methods for this lab are described below:


Constructors:

constructor: constructs a new linked list object.
copy constructor
: makes a copy of this list object

Mutators:

removeFirst: removes the element at the beginning of the list   
removeLast:
removes the element at the end of the list
<--Important: Rewrite for this Lab! Remove while loop
addFirst:
inserts an element at the beginning of the linked list

addLast:
inserts an element at the end of the list
pointIterator: moves the iterator to the start of the list
removeIterator: removes the element currently pointed to by the iterator. Postcondition: Iterator then points to NULL.
addIterator: inserts an element after the node currently pointed to by the iterator
advanceIterator: advances the iterator by one node towards the last node. It is okay for the iterator to go off end.
reverseIterator: advances the iterator by one node towards the first node. It is okay for the iterator to go off end.

Accessors:

getFirst: returns the first element
getLast:
returns the last element

isEmpty: tests whether the linked list is empty
getLength: returns the current length of the list
getIterator: returns the element currently pointed at by the iterator
offEnd: returns whether the iterator is off the end of the list, i.e. is NULL
equals: overrides the equals method for object to compares this list to another list to see if they contain the same data in the same order.
toString: overrides the toString method for object to print the contents of the linked list to the screen separated by a blank space

Additional Operations:

printNumberedList: prints the contents of the linked list to the screen in the format #. <element> followed by a newline
  • Note that, as you write each method, you must also write its Javadoc comment, including using the @precondition tag, @postcondition tag and @throws tag where necessary.
  • Hint: You can use the above descriptions as a starting point for your Javadoc comments.
  • You should also test your methods inside of ListTest.java and create unit tests (or update the unit tests where necessary) for the following methods:
(update these unit tests for your new generic, doubly-linked list class)
    • addFirst
    • addLast
    • getFirst
    • getLast
    • removeFirst
    • removeLast
    • isEmpty
    • getLength
(write unit test for new methods - 3 calls to assertEquals per test file)
    • addIterator
    • advanceIterator
    • reverseIterator
    • offEnd
    • removeIterator
    • getIterator
    • copy constructor

Part 4: Poem Reorganizer App (25 pts)

  • In the same project folder with your List.java, create a source code file called Poem.java, which reads in the contents of a file containing a poem, and allows the user to manipulate the poem by rearranging the order of the lines.

  • The user should have the option to move lines of the poem up and down to create a new poem.

  • The program should welcome the user and prompt the user for the name of a file

  • If this file cannot be found, the program should use a loop to re-prompt the user for a valid file name.

    • Important Note: poems can be saved in files of various names. The below text file names are only examples.
    • Therefore, your program should not check for specific file names.
    • It should determine whether the file name input by the user exists in the folder where Poem.java is saved.
    • Hint: Use try-catch
  • It should then read in the file and report the the title and author of the poem and the number of lines.

    • Note that you may assume all poem files to follow the same format as demonstrated below.
  • Using a loop, the program should then prompt the user for the line number to be rearranged, whether the line should be shifted up or down and then how many lines up or down it should be moved.

  • The program will report the line that was selected or print "The line is blank" if the user selects a blank line.

  • Each time a line is moved, the new version of the poem should be displayed.

  • Your program should accept both upper and lower case versions of the user responses.

  • Important Note: To receive credit for this portion of the lab, you must store the lines of the poem in a generic doubly-linked list as described in this lab (see directions above) and rearrange the lines using the list methods described above.
    • No credit if you do not use your List.java class from this lab
    • No credit if you add any additional methods to List.java aside from those specified in part 3 above.
    • No arrays, ArrayLists or other structures please!
  • Additionally, you are required to implement the below interface as part of your assignment:


/**

* PoetryApp.java

* @author FILL IN HERE

* @author FILL IN HERE

* CIS 22C Lab 2

*/

public interface PoetryApp {

    /**

    * Checks whether a file can be located and opened

     * for reading

    * @param file the name of the input file

     * @return whether the file can be located and opened

    */

    boolean checkFile(String file);
}


  • When I run your Poem.java along with your List.java, and the PoetryApp interface, your program should give identical output to the output below (given the same user input):


Sample Output 1:

Welcome to the poetry re-arranger!


Enter the name of a file containing a poem: poem.txt

Please enter a valid file name: poem1t.xt

Please enter a valid file name: poem1.txt


There are 14 lines in your poem

The poem is:

“Hope” is the thing with feathers By Emily Dickinson


1. “Hope” is the thing with feathers -

2. That perches in the soul -

3. And sings the tune without the words -

4. And never stops - at all -

5.

6. And sweetest - in the Gale - is heard -

7. And sore must be the storm -

8. That could abash the little Bird

9. That kept so many warm -

10.

11. I’ve heard it in the chillest land -

12. And on the strangest Sea -

13. Yet - never - in Extremity,

14. It asked a crumb - of me.



How would you like to re-arrange this poem?


Enter the line number of the poem: 7

The line is: And sore must be the storm -


Do you want to move this line up or down: Up

How many lines do you want to move it: 3

The new poem is:

1. “Hope” is the thing with feathers -

2. That perches in the soul -

3. And sings the tune without the words -

4. And sore must be the storm -

5. And never stops - at all -

6.

7. And sweetest - in the Gale - is heard -

8. That could abash the little Bird

9. That kept so many warm -

10.

11. I’ve heard it in the chillest land -

12. And on the strangest Sea -

13. Yet - never - in Extremity,

14. It asked a crumb - of me.


Would you like to rearrange this poem further: yes


How would you like to re-arrange this poem?


Enter the line number of the poem: 6

The line is blank


Do you want to move this line up or down: down

How many lines do you want to move it: 6

The new poem is:

1. “Hope” is the thing with feathers -

2. That perches in the soul -

3. And sings the tune without the words -

4. And sore must be the storm -

5. And never stops - at all -

6. And sweetest - in the Gale - is heard -

7. That could abash the little Bird

8. That kept so many warm -

9.

10. I’ve heard it in the chillest land -

11. And on the strangest Sea -

12.

13. Yet - never - in Extremity,

14. It asked a crumb - of me.


Would you like to rearrange this poem further: Yes


How would you like to re-arrange this poem?


Enter the line number of the poem: 8

The line is: That kept so many warm -


Do you want to move this line up or down: Down

How many lines do you want to move it: 3

The new poem is:

1. “Hope” is the thing with feathers -

2. That perches in the soul -

3. And sings the tune without the words -

4. And sore must be the storm -

5. And never stops - at all -

6. And sweetest - in the Gale - is heard -

7. That could abash the little Bird

8.

9. I’ve heard it in the chillest land -

10. And on the strangest Sea -

11. That kept so many warm -

12.

13. Yet - never - in Extremity,

14. It asked a crumb - of me.


Would you like to rearrange this poem further: No

Goodbye!


Sample Output 2:


Welcome to the poetry re-arranger!


Enter the name of a file containing a poem: poem2.txt


There are 27 lines in your poem

The poem is:

I Wandered Lonely as a Cloud By William Wordsworth


1. I wandered lonely as a cloud

2. That floats on high o'er vales and hills,

3. When all at once I saw a crowd,

4. A host, of golden daffodils;

5. Beside the lake, beneath the trees,

6. Fluttering and dancing in the breeze.

7.

8. Continuous as the stars that shine

9. And twinkle on the milky way,

10. They stretched in never-ending line

11. Along the margin of a bay:

12. Ten thousand saw I at a glance,

13. Tossing their heads in sprightly dance.

14.

15. The waves beside them danced; but they

16. Out-did the sparkling waves in glee:

17. A poet could not but be gay,

18. In such a jocund company:

19. I gazed—and gazed—but little thought

20. What wealth the show to me had brought:

21.

22. For oft, when on my couch I lie

23. In vacant or in pensive mood,

24. They flash upon that inward eye

25. Which is the bliss of solitude;

26. And then my heart with pleasure fills,

27. And dances with the daffodils.



How would you like to re-arrange this poem?


Enter the line number of the poem: 6

The line is: Fluttering and dancing in the breeze.


Do you want to move this line up or down: Up

How many lines do you want to move it: 5

The new poem is:

1. Fluttering and dancing in the breeze.

2. I wandered lonely as a cloud

3. That floats on high o'er vales and hills,

4. When all at once I saw a crowd,

5. A host, of golden daffodils;

6. Beside the lake, beneath the trees,

7.

8. Continuous as the stars that shine

9. And twinkle on the milky way,

10. They stretched in never-ending line

11. Along the margin of a bay:

12. Ten thousand saw I at a glance,

13. Tossing their heads in sprightly dance.

14.

15. The waves beside them danced; but they

16. Out-did the sparkling waves in glee:

17. A poet could not but be gay,

18. In such a jocund company:

19. I gazed—and gazed—but little thought

20. What wealth the show to me had brought:

21.

22. For oft, when on my couch I lie

23. In vacant or in pensive mood,

24. They flash upon that inward eye

25. Which is the bliss of solitude;

26. And then my heart with pleasure fills,

27. And dances with the daffodils.


Would you like to rearrange this poem further: no

Goodbye!



Hint:

  • Since the insertIterator method inserts data after the current node, it cannot insert data at the very front of the list.

  • Therefore, you will have to write special code to handle this condition.

  • See example 2 above.


Input File

  • Note that it an be assumed that each input file is structured the same way:


 <title>

<Blank line>

<body>

<Blank line>

By <author>


  • Below is an input file, which can be used with the first example above:


“Hope” is the thing with feathers


“Hope” is the thing with feathers -

That perches in the soul -

And sings the tune without the words -

And never stops - at all -


And sweetest - in the Gale - is heard -

And sore must be the storm -

That could abash the little Bird

That kept so many warm -


I’ve heard it in the chillest land -

And on the strangest Sea -

Yet - never - in Extremity,

It asked a crumb - of me.


By Emily Dickinson


  • To insert this file into your Eclipse project, right-click on the project folder, and then go to File->File. Note that the file will be placed in the overall project folder, which is where Eclipse will search for it. Your text file should not be placed under the src folder or Eclipse will not be able to find this file.

  • Below is another file, which can be used with the second example above:


I Wandered Lonely as a Cloud


I wandered lonely as a cloud

That floats on high o'er vales and hills,

When all at once I saw a crowd,

A host, of golden daffodils;

Beside the lake, beneath the trees,

Fluttering and dancing in the breeze.


Continuous as the stars that shine

And twinkle on the milky way,

They stretched in never-ending line

Along the margin of a bay:

Ten thousand saw I at a glance,

Tossing their heads in sprightly dance.


The waves beside them danced; but they

Out-did the sparkling waves in glee:

A poet could not but be gay,

In such a jocund company:

I gazed—and gazed—but little thought

What wealth the show to me had brought:


For oft, when on my couch I lie

In vacant or in pensive mood,

They flash upon that inward eye

Which is the bliss of solitude;

And then my heart with pleasure fills,

And dances with the daffodils.


By William Wordsworth




What to Submit:

  • Please submit your Poem.java, List.java, ListTest.java and 15 unit test files as described above (no zip or compressed files please).
  • One partner should submit all the source code files along with the pair programming contract
  • The other partner should only submit the pair programming contract
  • Note that you do not need to upload the PoetryApp.java interface file

How You Will Be Graded:

  • 54 points of the credit will be for submitting a complete and functional generic, doubly-linked list (3 points per correct method, along with its Javadoc comment)
  • 21 points for adequate testing (1 point per unit test class and 6 points for a complete ListTest.java class).
    • Make sure that you test your list thoroughly inside of ListTest.java and your unit tests!
  • 25 points for a complete and functional Poem.java that works as shown in the sample output, and uses the List.java class and its methods to store and rearrange the poem, and the provided PoetryApp interface.
Additional Specifications:
  • No credit if your List.java file contains any additional methods other than those specified in the directions or if the inner Node class has been altered in any way from what was given in this Lab.
  • No credit if your List doesn't compile or run using the Eclipse IDE.
  • No credit if your program doesn't compile. Make sure to comment out the parts that aren't working (if any) before you submit.
  • Please include a block comment with your name on the top of EACH file like so:

/**
* @author FirstName LastName
* @author FirstName LastName
* CIS 22C, Lab 2
*/
  • No credit if you do not complete this assignment following the rules of pair programming
  • 5 point deduction for any package names (please use the default package or remove package names before submitting your assignment)
  • 5 point deduction for not submitting your pair programming contract - remember that both partners should submit this part!
  • 5 point deduction for submitting as a zip file. Please submit each file separately.