Thus far, the subList method defined in ArrayList and LinkedList has not followed the specifications in the Java collections documentation. The present implementation creates a new list and copies the elements between the specified indices into the new list. However, the collections documentation specifies that a sub-list is a restricted view of the original list between the specified indices. Thus, any changes (additions or removals) to a sub-list should be immediately visible in the original list. Consider the code fragment below:

List list = new ArrayList();

for (int i = 0; i < 10; ++i)

{

list.add(new Integer(i));

}

list.subList(3, 5).clear();

System.out.println(list);

The above code should print out [0, 1, 2, 5, 6, 7, 8, 9], because the clear operation on the sub-list between indices 3 (inclusive) and 5 (exclusive) actually operated on the original list.

Task

Your assignment is to implement correct sub-list behavior from the subList method of the AbstractList class. One of the cleanest and simplest ways to correctly implement the subList method is to employ the Decorator design pattern. That is, your solution will be a class that decorates a List and a ListIterator object.

Details

Within the AbstractList class, the implementation of subList may be written as:

public abstract class AbstractList

extends AbstractCollection implements List

{

// ... other methods skipped ...

public List subList(int startIndex, int endIndex)

{

return new SubList(this, startIndex, endIndex);

}

}

The SubList class will keep a reference to the original list and forward modified method calls into the decorated list. SubList will start as something like the following:

public class SubList extends AbstractList

{

// the decorated list

private List list;

private int start;

private int end;

public SubList(List baseList, int fromIndex, int toIndex)

{

}

public int size()

{

return 0;

}

public List subList(int fromIndex, int toIndex)

{

return null;

}

public ListIterator listIterator(int position)

{

return new SubListIterator(position);

}

private class SubListIterator implements ListIterator

{

// the decorated list iterator

private ListIterator iter;

// ... implementations of all iterator methods ...

}

}

Because the SubList class extends AbstractList, there are only a few methods that must be implemented: the constructor, size()and listIterator(). However, overriding subList() will allow sub-lists of sub-lists to be much more efficient by re-decorating the original list rather than decorating an existing decorator. Also, since AbstractList provides implementations that only depend on the list iterator class, the majority of the work of implementing SubList will be done in the iterator. Remember, the goal is to decorate, so the instance field list in SubList and iter in SubListIterator will be the original list and an iterator over the original list, respectively. The actual methods can be carried out by doing some additional processing and then calling the method of the same name within the method being written. For example, the set method of the iterator is by far the easiest and can be written simply as:

public void set(E obj)

{

this.iter.set(obj);

}