Data Structures and Algorithms I

Program 4

This program will give you some practice using generics and allow you to explore an implementation of a collection structure. You will be creating a generic class for an OrderedList. The list will behave somewhat like an ArrayList, but will maintain elements in order. Of course, the order will be controlled by a Comparator. Here is an example:

OrderedList<String> ols = new OrderedList<String>(new StringComparator());
ols.add("Fred");
ols.add("Joe");
ols.add("Adamson");
ols.dump(System.out);

This should cause output to the console: [Joe, Fred, Adamson] (in some order based on the Comparator). In addition, the OrderedList must be able to be accessed using Java's for each structure:

for(String name:ols) System.out.println(name); 

Internally, you will use an array of Objects. This is non-negotiable. You may not use other types of Collection structures. You are unable to instantiate an array of generic types, so an array of Object must be used. You will need to cast everything appropriately inside the class to ensure your methods return the proper types.

Since you are using arrays, you will need to be careful that you do not exceed the array size. As such, you will sometimes need to increase the capacity of the underlying array. Your arrays should always start with room for 5 items. Again, this is non-negotiable. If the size needs to be increased, the array will always double in size. This will allow very large lists to be created without too many resize operations.

Be sure to choose an efficient way to keep all of the elements in order. Remember that new elements are always added to already sorted contents, preserving the internal order.

The following public methods must be implemented.

class OrderedList<E> implements Iterable<E>{
	OrderedList(Comparator<E> c); Constructor
	int add(E e); returns the position of the added item
	int add(E[] e); adds all elements of e to the OrderedList returns number added
	void dump(PrintStream s); outputs list to the stream in this format: [item, item, ...]
	int find(E e); returns the position of e in the list (-1 if not found)(checks equality based on Comparator)
	E get(int p); returns the item at position p if p is legal, returns null if illegal
	E remove(int p); removes and returns the item at position p if p is legal, returns null if illegal
	Iterator<E> iterator(); returns an iterator that will allow a traversal of the list
		The Iterator must support all three required operations
		The next method throws a NoSuchElementException if called when there are no more elements.
		The remove method must throw IllegalStateException when appropriate
		You should check for and throw a ConcurrentModificationException when needed.
	int size(); returns number of items in the list
	int capacity(); returns the current capacity of the underlying array
	Object[] toArray(); returns an array containing just the elements of the OrderedList (no extra spots).
	//The last method is optional
	E[] toArray(E[] a); copies the elements to the provided array, making it longer if necessary, and returns that array. If the provided array is larger than necessary, the remaining positions are not changed.
}

Be sure to read up on Iterators. The iterator's remove method can only be called once per each call to next. The IllegalStateException occurs if an application violates this rule.

Each OrderedList must internally track modifications to the list so iterators can detect concurrent modification errors. This is done by storing a counter in the OrderedList that is incremented if with each addition or removal of an element. When an iterator is created, it copies this value and compares its copy to the one in the list. If the iterator removes an item from the list, it increments its own internal counter so it remains the same as the one in the OrderedList. Iterators always check that the OrderedList modification counter matches its own copy and throws the exception if it does not. 

You will find it very convenient to make the Iterator an inner class of your OrderedList. Of course, this is not required, but you will need to manage callbacks appropriately. I cannot think of any need for static members in this project, so be sure to avoid these unless you can justify their existence.

A test program will be provided. By the way... you may have to live with some warnings about type safety. It is highly likely that these warnings will occur when you cast from Objects to the generic types throughout your class. These are acceptable.

Provide adequate documentation in your classes. You will be submitting one or two files (OrderedList and an Iterator class if separated from the OrderedList class). Please zip and name as usual. Turn in a printed copy as well as submitting online.