1. Introduction

The purposes of this assignment are

to practice working with a linked data structure

to become intimately familiar with the List and ListIterator interfaces

This assignment will also provide many opportunities to practice your debugging skills. 1.1. Summary of Tasks

Implement a class StoutList that extends AbstractSequentialList along with inner classes for the iterators. A skeleton is provided. See the implementation and suggestions for getting started sections for details.

1.2. Overview

In this assignment you will implement a somewhat peculiar-looking linked list. The list will be a doubly- linked list with dummy nodes for the head and tail. An empty list has the following form:

Figure 1- an empty list

So far so good. Now, let M be a fixed, positive even number. The twist is that each node can store up to M data elements, so the number of linked nodes may not correspond to the number of elements. For example, after some sequence of add and remove operations, one of these lists might have the following form:

Figure 2 - a possible list of size 6, where M=4

Note that there are 6 elements, and their logical indices are shown below the nodes. The number of actual  linked nodes may vary depending on the exact sequence of operations. Each node contains an array of the  element type having fixed length M. Therefore, each logical index within the list is represented by two        values: the node n containing the element, and the offset within that node’s array. For example, the element E shown above at logical index 4 is in node n1 at offset 2. There are special rules for adding and removing   elements to ensure that all nodes, except possibly the last one, have at least M/2 elements. These rules    are described in detail in a later section. Note that you can get started and make significant progress on the assignment without needing all the add and remove rules. See the section suggestions for getting started.

2. Implementation of StoutList

For the implementation, you must implement the class StoutList extending                                     AbstractSequentialList. AbstractSequentialList is a partial implementation of the List     interface in which the size() and listIterator() methods are abstract. All other operations have      default implementations using the list iterator. The StoutList should NOT allow null elements. Your add methods (those within the iterator as well as those implemented without the iterator) should explicitly       throw a NullPointerException if a client attempts to add a null element. A skeleton of the code can be found in project3_template.zip. The skeleton code includes a constructor, an inner class Node, and two      methods toStringInternal(). There is also some code in place to support loging.

2.1. Methods to override

In addition to implementing the iterators described below, you must override the following methods of AbstractList withoutusing the iterator:

The methods above must conform to the List interface, with the added restriction that the add()     methods must throw a NullPointerException if the item argument is null. The purpose of asking you to override add() and remove() is primarily to help ensure that you can get partial credit for                implementing the split and merge strategies even if your iterator isn’t completely correct.

2.2. The Node inner class

A minimal Node class is provided for you. It has methods for adding an element at a given offset and removing an element at a given offset. Note that empty cells within the array (i.e., those with index >= count) should always be null.

You can add additional features to this class if you find it helpful to do so.

2.3. The toStringInternal methods

These methods show the internal structure of the nodes and are useful for debugging. Normally, such a     method would not be public (since it reveals implementation details), but we are making it public to simplify unit testing. For example, if the list of Figure 3 contained String objects “A”, “B”, “C”, “D” and “E”, an             invocation of toStringInternal() would return the string:

[(A, B, -, -), (C, D, E, -)]

where the elements are displayed by invoking their own toString() methods and empty cells in the array inside each node (which should always be null) are displayed as “-”. A second version takes a                  ListIterator argument and will show the cursor position as a character “ |” according to the                nextIndex() method of the iterator. For example, if iter is a ListIterator for the list above and has    nextIndex() = 3, the invocation toStringInternal(iter) would return the string:

[(A, B, -, -), (C, | D, E, -)]

Do not modify these methods.

2.4. Finding indices

Your index-based methods remove(int pos), add(int pos, E item) and listIterator(int   pos) method must not traverse every element in order to find the node and offset for a given index; you  should be able to skip over nodes just by looking at the number of elements in the node. For example, for the list of Figure 9, to find the node and offset for logical index 7, you can see 3 elements in the first node, plus 2 in the second node, which makes 5, plus 4 in the third node, which is 9. Since 7 is greater than 5 and less than or equal to 9, index 7 must be in the third node. You may find it helpful to represent a node and  offset using a simple inner class similar to the following:

Then you can create a helper method something like the following:

3. Implementation of StoutIterator and StoutListIterator

You must provide a complete implementation of an inner class StoutIterator implementing                Iterator<E> and a class StoutListIterator implementing ListIterator<E>. The StoutIterator does NOT need to implement remove() (can throw UnsupportedOperationException). Optionally, if  you are confident that your StoutListIterator is correct, you can return an instance of                     StoutListIterator from your iterator() method and forget about StoutIterator. However, you  are encouraged to keep them separate when you first start development, since the basic one-directional    Iterator, without a remove operation, is relatively simple, while the add and remove operations for the full  ListIterator are tricky.

4. Suggestions for Getting Started

1. Implement add(E item). Adding an element at the end of the list is relatively straightforward and does not require any split operations. (e.g. see Figures 3 – 5). You can use toStringInternal() to check.

2. Implement the hasNext() and next() methods of StoutIterator and implement the iterator() method. At this point the List methods contains(Object) and toString() should work.

3. Start StoutListIterator. Implement ListIterator methods nextIndex(), previousIndex(),        hasPrevious(), and previous(). These methods are straightforward. Implement the            listIterator() method. You should then be able to iterate forward and backward, and you can check your iterator position using toStringInternal(iter). The indexOf(Object obj)   method of List should work now.

4. Implement the set() method of StoutListIterator. You will need to keep track of whether to act on the element before or after the cursor (and possibly throw an IllegalStateException), but the method is not complicated since it doesn’t have to change the structure of the list or        reposition the cursor.

5. Implement a helper method such as the “find” method described above under finding indices. Then you can easily implement the listIterator(int pos) method. After that, the get(int pos) of

List should work.

6. Implement the add(int pos, E item) method. Now you will need to carefully review the rules   for adding elements. Here is a suggestion for keeping things organized. Write a helper method whose arguments include the node and offset containing the index pos at which you want to add, e.g.,

private NodeInfo add(Node n, int offset, E item){...}

(If pos = size, the arguments should be the tail node and offset 0.) The return value should be the      actual node and offset at which the new element was placed. (In some cases this will be the given     node and offset, in some cases it will be the previous node, and in case of a split there might be a     completely new node.) You don’t need the return value for the add method, but you will need it in the iterator.

7. Implement the remove(int pos) method. Again, you will need to carefully review the rules for removing elements and merging.

8. Implement the add() method of listIterator. This is not too bad if you have the helper method from

(6). The catch is that after adding an element, you have to update the logical cursor position to the element after the one that was added.

9. Implement the remove() method of listIterator. The tricky part is that you have to update the cursor position differently depending on whether you are removing ahead of the cursor or behind the        cursor, and depending on whether there was a merge operation.

5. The add and remove Rules

5.1. Adding an element (see Figures 3 – 8)

The rules for adding an element Xat index are as follows. Remember that adding an element without specifying an index is the same as adding at index i= size. For the sake of discussion, assume that the logical index = size corresponds to node = tail and offset = 0.

Suppose that index occurs in node nand offset off. (Assume that index = size means n= tail and off= 0)

  if the list is empty, create a new node and put Xat offset 0

  otherwise if off= 0and one of the following two cases occurs,

  if nhas a predecessor which has fewer than Melements (and is not the head), put X in n’s

predecessor

  if nis the tail node and n’s predecessor has Melements, create a new node and put Xat offset

0

  otherwise if there is space in node n, put X in node nat offset off, shifting array elements as

necessary

  otherwise, perform a splitoperation: move the last M/2elements of node ninto a new successor

node n', and then

  if off ≤ M/2 , put X in node nat offset off

  if off > M/2 , put X in node n'at offset (off − M/2)

5.2. Removing an element (see Figures 9 – 14)

The rules for removing an element are:

  if the node ncontaining X is the last node and has only one element, delete it;

  otherwise, if nis the last node (thus with two or more elements) , or if nhas more than M/2

elements, remove Xfrom n, shifting elements as necessary;

  otherwise (the node nmust have at most M/2 elements), look at its successor n'(note that we don’t

look at the predecessor of n) and perform a mergeoperation as follows:

  if the successor node n' has more than M/2 elements, move the first element from n'to n.

(mini-merge)

  if the successor node n' has M/2 or fewer elements, then move all elements from n' to nand

delete n' (full merge)

5.3 Examples: adding some elements to a list

Figure 3- an example list

Figure 4 - after add(V)

Figure 5 - after add(W)

Figure 6 - after add(2, X)

Figure 7 - after add(2, Y)

Figure 8 - after add(2, Z)

5.4. Examples: removing some elements from a list

Figure 10 - after removing W

Figure 11 - after removing Y (mini- merge)

Figure 12 - after removing X (mini- merge)

Figure 13 - after removing E (no merge with predecessor node)

Figure 14 - after removing C (full merge with successor node)

6. Sorting

Implement the following two sorting methods within the StoutList class:

The sort() method implements insertion sort by calling a private generic method:

On return from calling sort(), the elements in the stout list are in the non-decreasingorder, and every node (except the last one) stores the maximum number of elements. One implementation consists of the following steps:

Traverse the list and copy its elements into an array.

Destroy all storage nodes in the list during the traversal.

Sort the array.

Create new nodes in the list and add elements back from the sorted array.

The reverseSort() method sorts elements in the non-increasing order using BubbleSort, which is described in Section 6.1. It calls another private generic method:

In bubbleSort() you are required to use the compareTo() method from an expected implementation of the Comparable interface by E or ? super E. The list must, after the sorting, have every node (except the last one) storing elements to its full capacity, just as is required for the sort() method.

6.1. Bubble Sort

Bubble sort is performed in multiple passes. Suppose we want to sort an array of elements in the non-     decreasing order (which is opposite to the order in bubbleSort()). In every pass, it steps through the    entire list, comparing each pair of adjacent numbers and swapping them if the preceding number in the   pair is greater than the succeeding one. If no swaps have been performed during a pass, the list is sorted  and the algorithm terminates. Intuitively, the algorithm works in a way that smaller elements "bubble" to  the front of the list. Wikipedia offers a step-by-step example to illustrate the working of the algorithm. It   also has some cool simulations. Below is a bigger example from The ArtofComputer Programming, vol. 3, 2nd edition, p. 106, authored by Donald E. Knuth.

As illustrated in the above, each pass of bubble sort guarantees to put the next biggest element in place. The algorithm has worst-case complexity O(n )2 for an input of nintegers.

7. Unit Tests

You are strongly encouraged to write unit tests as you develop your solution. However, you do not have to  turn in any test code. You may therefore post your tests on Piazza, should you wish to share them with your