OBJECTIVE

The objective of this assignment is to give you practice with building your own generic list library in Java.

ASSIGNMENT SUBMISSION

To get credit for this assignment, you must

submit your assignment on time

name all your files/classes/methods exactly as instructed (the overall project should be named

yournetid_pr1 and should contain two packages: mylistpackage and tests)

commit your final running Java project into the course SVN folder

submit an executive summary on Canvas

your project needs to be compatible with/ Eclipse version

DESCRIPTION OF ASSIGNMENT

Your job is to create the class hierarchy shown in the picture below by using the starter code provided on Canvas and discussed in class: MyList.java, ArrayListUnsorted.java, LinkedListUnsorted.java.

Specifications

Create a project called yournetid_pr1. Put all Java files into a package called mylistpackage. Put all JUnit files into a package called tests.

Step 1: restructuring ArrayListUnsorted.java:

Change removeAtIndex implementation to use the non-shifting array approach update the appropriate test

case/s

Create an abstract class that implements MyList (name it AbstractArrayMyList)

-1-

Move all data fields from ArrayListUnsorted to this abstract class and make them protected Move all methods common to sorted and unsorted approaches (i.e. not dependent on the ordering of elements), as well as the iterator, from ArrayListUnsorted to the abstract class; do not move

method clear though Add reset operation to the iterator that resets the iterator to the first list element

Make ArrayListUnsorted a child of AbstractArrayMyList

If you run the test cases for the unsorted array list, you should still be passing them

Step 2: add ArrayListSorted as a child of AbstractArrayMyList

Since the array components will need to be Comparable, your class header should start with

ArrayListSorted extends Comparable super E>> and inside the constructor you should be creating an

array of Comparable, not Object

Implement all remaining methods remember that wherever search is used, you need to use binary search;

method set should throw IllegalArgumentException, if a user wants to insert an element into the wrong

location

Remember to implement it following the approach discussed in class and do NOT use any type of a sorting

routine whether built-in or your own

Add a JUnit class that tests your sorted implementation (the simplest way to do it is to copy and paste

unsorted list tests and update that file)

Step 3: create and add AbstractLinkedMyList.java, LinkedListUnsorted.java, and LinkedListSorted.java to the hierarchy in the fashion similar to how you dealt with an array list:

Use the provided linked list code as your base but change the implementation so that the linked list contains size component but only one reference to the last node and is circular:

Add JUnit test classes for sorted and unsorted versions (it is enough to copy, paste, and adjust the two classes you created for your array list implementation)

Step 4 (extra credit): Add a linked array list hierarchy discussed in class to the overall structure. All class and method names should be consistent with the names shown in the simplified UML diagram provided above and with the method names provided in the interface. Again, add JUnit test classes for sorted and unsorted versions to your package.

Use proper coding style.

Make sure that all components of your hierarchy have Javadocs. You are to provide the following:

sentence descriptor

param, return, throws, see tags for methods

param, version, author tags for classes / interfaces

Generate Javadocs for all the classes in your project -> docs folder. In order to generate HTMLs into this subfolder, with the project selected in the left pane (Project Explorer frame), click on Project in the menu -> Generate Javadoc. We will grade your Javadocs via the HTML pages you generate with the Javadocs utility.

-2-I

This what i have so far i couldnt post everything so i just zipped the folder with all the classes.

package mylistpackage;

import java.util.Iterator; import java.util.NoSuchElementException;

public abstract class AbstractArrayMyList implements MyList { /** * default list capacity. */ protected static final int DEFAULT_CAPACITY = 100;

/** * list of values */ protected E[] elementData;

/** * index of the last element in the list */ protected int size;

/** * @see mylistpackage.MyList#getSize() */ public int getSize() { return size + 1; }

/** * @see mylistpackage.MyList#isEmpty() */ public boolean isEmpty() { return size == -1; }

/** * @see mylistpackage.MyList#contains(java.lang.Object) */ public boolean contains(E value) { for (int i = 0; i <= size; i++) { if (elementData[i].equals(value)) { return true; } } return false; } // // /** // * @see mylistpackage.MyList#insert(java.lang.Object) // */ // public void insert(E value) { // ensureCapacity(size + 2); // size++; // elementData[size] = value; // } // // /** // * @see mylistpackage.MyList#clear() // */ // public void clear() { // elementData = (E[]) new Object[DEFAULT_CAPACITY]; // size = -1; // }

/** * Creates a comma-separated, bracketed version of the list. * * @see java.lang.Object#toString() */ public String toString() { if (size == -1) { return "[]"; } else { String result = "[" + elementData[0]; for (int i = 1; i <= size; i++) { result += ", " + elementData[i]; } result += "]"; return result; } }

/** * @see mylistpackage.MyList#remove(java.lang.Object) */ public void remove(E value) { int index = getIndex(value); if (size >= 0 && index >= 0) { elementData[index] = elementData[size]; elementData[size] = null; size--; } }

// /** // * Ensures that the underlying array has the given capacity; if not, // * increases the size by 100. // * // * @param capacity > elementData.length. // */ // private void ensureCapacity(int capacity) { // if (capacity > elementData.length) { // int newCapacity = elementData.length + 100; // if (capacity > newCapacity) { // newCapacity = capacity; // } // elementData = Arrays.copyOf(elementData, newCapacity); // } // }

/********************************************* * Index list methods follow *********************************************/

/** * Returns the index of value. * * @param value assigned. * @return index of value if in the list, -1 otherwise. */ public int getIndex(E value) { for (int i = 0; i <= size; i++) { if (elementData[i].equals(value)) { return i; } } return -1; }

/** * Removes value at the given index, shifting subsequent values up. * * @param index <= size and index >= 0 * @throws IndexOutOfBoundsException if index < 0 or index > size */ public void removeAtIndex(int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(); } //for (int i = index; i < size; i++) { elementData[index] = elementData[size]; // } elementData[size] = null; size--; }

/** * Replaces the value at the given index with the given value. * * @param index <= size and index >= 0 * @value is assigned * @throws IndexOutOfBoundsException if index < 0 or index > size */ public void set(int index, E value) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(); } elementData[index] = value; }

/** * Returns the value at the given index in the list. * * @param index <= size and index >= 0 * @throws IndexOutOfBoundsException if index < 0 or index > size * @return the value at the given index in the list. */ public E get(int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(); } return elementData[index]; }

/********************************************* * Index list methods end *********************************************/

/********************************************* * Iterator list class / methods follow *********************************************/

/** * Returns an iterator for this list. * * @return an iterator for the list. */ public Iterator iterator() { return new ArrayListIterator(); }

/** * Represents an iterator for the list. * * @author BuildingJavaPrograms 3rd Edition */ protected class ArrayListIterator implements Iterator {

/** * current position within the list. */ private int position;

/** * flag that indicates whether list element can be removed. */ private boolean removeOK;

/** * Constructs an iterator for the given list */ public ArrayListIterator() { position = 0; removeOK = false; }

/** * Returns whether there are more list elements. * * @return true if there are more elements left, false otherwise * @see java.util.Iterator#hasNext() */ public boolean hasNext() { return position <= size; }

/** * Returns the next element in the iteration. * * @throws NoSuchElementException if no more elements. * @return the next element in the iteration. * @see java.util.Iterator#next() */ public E next() { if (!hasNext()) { throw new NoSuchElementException(); } E result = elementData[position]; position++; removeOK = true; return result; }

/** * Removes the last element returned by the iterator. * * @throws IllegalStateException if a call to next has not been made * before call to remove. * @see java.util.Iterator#remove() */ public void remove() { if (!removeOK) { throw new IllegalStateException(); } AbstractArrayMyList.this.removeAtIndex(position - 1); position--; removeOK = false; } public void reset() { position = 0; } } }