CSE 214 - HW 2

HW 2 - Generic, Doubly Linked Lists

SETUP

Note that in this assignment, you should use the eclipse IDE. To start:

Download cse214_hw2_fall2009.zip and save it to a directory of your choice. Don't unzip the file! You'll need to remember where you put it.
Open eclipse now, and choose whatever workspace directory you like.
Click on:
- File
- Finish
You should now have a project with all the files necessary to do this homework, including image and data files.
Verify that the project was properly imported into eclipse. Are you able to open and edit the source code in eclipse?
NOTE: There should be no compiler errors after you import the zip file

In HW 1 you defined methods for maniupuating a singly linked linked. Now we'll add methods to a doubly linked list manager class.

Examine the following 4 files:

GenericDoublyLinkedList.java
HW2TestProgram.java
AnimatedSpriteBuilder.java
WordBuilder.java

Again, go through the code and read the documentation. You'll see that the AnimatedSpriteBuilder and WordBuilder classes both start applications that make use of GenericDoublyLinkedLists, but in different ways. AnimatedSpriteBuilder stores Image objects in the list while WordBuilder uses the list to store Characters. Try running each program. You'll see that each interface provides a means to manipulate the list managing class whose methods you'll define.

The point here is that a data structure can and should be built to manipulate different types of data in abstract ways.

The AnimatedSpriteBuilder program provides controls at the top for building and maniuplating a linked list of images representing an animation sequence. At the bottom, there are controls that can start an animation that uses these images. There are also controls for selecting either forward or backward circular iteration.

What's a circular iterator? In HW 1 we built iterators that would go through a linked list once and that's it. That's a disposable iterator. With a circular iterator, once the iterator reaches the last node in the list, it would go back to the beginning again. A reverse circular iterator would go in the opposite direction.

The WordBuilder program provides controls at the top for building and querying a linked list of Characters. At the bottom, while the list is being manipulated you can always see what toString and reverseToString methods produce. Note that the reverse version would start at the tail and go to the head, which is now possible since we are using a doubly linked list.

YOUR THREE ITERATORS

In HW 1 your list managing class had only one iterator, but this time we'll use three different ones. This means we have to define three inner classes that each implement Iterator. They are:

GenericDoublyLinkedListIterator - This one is just a standard, head to tail, disposable iterator like we saw in HW 1. Note that it would not produce elements if the list was empty.

CircularForwardIterator - This one goes head to tail, but after tail, it goes back to head in a never-ending loop. That's why we call it circular. Note that it would not produce elements if the list was empty.

CircularReverseIterator - This one goes tail to head and is also circular, so after reaching the head node, the next one would be the tail. Note that it would not produce elements if the list was empty.

YOUR TEN METHODS

When we press buttons in the GUIs, AnimatedSpriteBuilder & WordBuilder call methods in a list to manipulate its contents in different ways. In addition to the three iterators we've discussed, you must define the following ten methods inside the GenericDoublyLinkedList class. NOTE: make sure you properly maintain your list's head, tail, and size variables as well as all nodes' next and previous links. A problem caused by an improper assignment in one of your methods may cascade problems to subsequent method calls that expose previously unseen errors.

public void append(E dataToAdd) - This method should add a new node to the list containing the dataToAdd as its data.

public void buildNewListFromArray(E[] arrayOfDataToAdd) - This method should load a brand new list using the data in the provided array argument as its nodes. So, if the array has a length of 5, your list would end up with a size of 5. Discard any nodes that exist before calling this method.

public int indexOf(E[] searchData) - This method should examine the list to find a sequence of nodes that contains equivalent data, in the equivalent order as the searchData argument. So, if the searchData array has 5 elements, you must find five consecutive nodes in the list with equivalent data in the same order. Your method should return the index of the first node in that sequence (the head node is index 0). If no sequence is found, return -1.

public void moveDownOne(int index) - This method should move the node at location index down one index in the list (toward the tail). This would result in it's immediate neighbor moving up one (toward to head), of course. No data should be lost by this change.

public void moveUpOne(int index) - This method should do the opposite of moveDownOne. It should move the node at location index up one index in the list (toward the head). Again, this would result in that node's neighbor moving down one (toward the tail).

public void prepend(E dataToAdd) - This method should add a new node to the front of the list such that it stores the dataToAdd object as its data.

public void removeAtIndex(int index) - This method should remove the node at the index location from the list.

public String reverseToString() - This method should return a textual representation of the list from tail to head. This can be done by combining the toString results of all the node data in all the nodes from tail to head.

public GenericDoublyLinkedList subset(int startIndex, int endIndex) - This method should make and return a brand new GenericDoublyLinkedList that contains all the data stored in the referenced list from startIndex to and including endIndex. Note that the original referenced list should not be changed in any way. Think of this as an operation similar to the String class' substring method, except that the second integer argument refers to an index included in the newly constructed subset.

public String toString() - This method should return a textual representation of the list from head to tail. This is the opposite of reverseToString, obviously. This method can be implemented by combining the toString results of all the node data in all the nodes from head to tail.

Again, I can't stress it enough. Make sure you properly maintain all nexts & prevs for the nodes in your list. In addition, make sure your head and tail are properly managed. After calling your method, one should be able to manipulate the list in other ways. In other words, even if it appears your method produces the correct results, it shouldn't break the list for future operations.

BONUS - 25 points

25 points bonus will be awarded to students who make their own Sprite character animation. By this I mean make 10 images that together can be used to represent an animated action. The more creative/interesting/hilarious the better. Please do not skip the programming to work on this, this is just for fun. If you do this, I would recommend you make your sprites 64x64 pixels.

Handin Instructions

Go to the hand-in instructions page for the details on the required handin procedure. You must hand in by the designated due date and time in the course schedule for credit. Late assignments will not be graded.

Grading

All assignment will be graded purely based on program performance. Submissions that do not compile will receive 0 points. Submissions that never produce correct results will receive 0 points. The TAs will test your submissions using various input, and grades will be awarded depending on how often your code produces the correct results.

Web page created and maintained
by Richard McKenna