OBJECTIVE The objective of this assignment is to give you practice with building
ID: 3820179 • Letter: O
Question
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<E> implements MyList<E> {
/**
* 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<E> iterator() {
return new ArrayListIterator();
}
/**
* Represents an iterator for the list.
*
* @author BuildingJavaPrograms 3rd Edition
*/
protected class ArrayListIterator implements Iterator<E> {
/**
* 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;
}
}
}
Explanation / Answer
AbstractLinkedMyList.java
package mysinglelinkedlist;
import java.util.Iterator;
import java.util.NoSuchElementException;
import mylistpackage.MyList;
public abstract class AbstractLinkedMyList<Type> implements MyList<Type> {
/**
* Reference to the first node in the list.
*/
protected ListNode<Type> front;
/**
* Reference to the last node in the list.
*/
protected ListNode<Type> back;
/**
* current number of elements.
*/
protected int size;
/**
* Constructs an empty list.
*/
public AbstractLinkedMyList() {
front = back = null;
size = 0;
}
/**
* Replaces the value at the given index with the given value.
* @param index < size and index >= 0
* @param value is assigned
* @throws IndexOutOfBoundsException if index < 0 or index >= size
*/
@Override
public void set(int index, Type value) {
if (index < 0 || index >= getSize()) {
throw new IndexOutOfBoundsException("index: " + index);
}
nodeAt(index).data = value;
}
/**
* Return size of the list.
* @see mylistpackage.MyList#getSize()
* @return size of the list
*/
@Override
public int getSize() {
return size;
}
/**
* Return if the list is currently empty
* @see mylistpackage.MyList#isEmpty()
* @return if the list is empty
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* Return if the list contains a specific value
* @see mylistpackage.MyList#contains(Object)
* @returns if list contains that value
*/
@Override
public boolean contains(Type value) {
return getIndex(value) != -1;
}
/**
* Returns the value at the given index in the list.
* @param index < size and index >= 0
* @see mylistpackage.MyList#get(int)
* @throws IndexOutOfBoundsException if index < 0 or index >= size
* @return the value at the given index in the list.
*/
public Type get(int index) {
checkInBoundsOfList(index);
return nodeAt(index).data;
}
/**
* Ensures that the given index is a valid index to work with in the linked list
* @param index to check against in the array.
* @throws IndexOutOfBoundsException if index < 0 or index > size
*/
protected void checkInBoundsOfList(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
}
/**
* Ensures that the given index is a valid insertion index in the linked list
* @param index, index to check for valid insertion point
* @throws IndexOutOfBoundsException if index < 0 or index > size
*/
protected void checkOkToInsertAtIndex(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
}
/**
* Inserts an element in the front of the list
* @see mylistpackage.MyList#insertFront(Object)
* @param value assigned.
*/
public void insertFront(Type value) {
insertAtIndex(0, value);
}
/**
* Clear the contents of the list.
* @see mylistpackage.MyList#clear()
*/
public void clear() {
front = null;
back = null;
size = 0;
}
/**
* Returns an iterator for this list.
* @see mylistpackage.MyList#iterator()
* @return an iterator for the list.
*/
public Iterator<Type> iterator() {
return new LinkedIterator();
}
/**
* Inserts the given value at the given index, shifting subsequent values.
* @param index <= size() and index >= 0
* @param value assigned
* @see mylistpackage.MyList#insertAtIndex(int, Object)
* @throws IndexOutOfBoundsException if 0 < index > size
*/
public void insertAtIndex(int index, Type value) {
checkOkToInsertAtIndex(index);
if (size == 0) {
ListNode<Type> newNode = new ListNode<Type>(value);
front = back = newNode;
}
else {
if (index == 0) {
ListNode<Type> newNode = new ListNode<Type>(value, front);
front = newNode;
}
else {
ListNode<Type> current = nodeAt(index - 1);
ListNode<Type> newNode = new ListNode<Type>(value, current.next);
current.next = newNode;
if (index == size) {
back = newNode;
}
}
}
size++;
}
/**
* Removes value at the given index
* @param index < size and index >= 0
* @see mylistpackage.MyList#removeAtIndex(int)
* @throws IndexOutOfBoundsException if index < 0 or index >= size
*/
public void removeAtIndex(int index) {
checkInBoundsOfList(index);
if (index == 0) {
front = front.next;
if (size == 1)
back = null;
}
else {
ListNode<Type> current = nodeAt(index - 1);
current.next = current.next.next;
if (current.next == null)
back = current;
}
size--;
}
/**
* Returns the node at a specific index.
* @param index where 0 <= index < size()
* @return reference to the node at a specific index
*/
protected ListNode<Type> nodeAt(int index) {
ListNode<Type> current = front;
for (int i = 1; i <= index; i++) {
current = current.next;
}
return current;
}
/**
* Creates a comma-separated, bracketed version of the list.
* @see java.lang.Object#toString()
* @return string representation of the list
*/
public String toString() {
if (size == 0) {
return "[]";
} else {
String result = "[" + front.data;
ListNode<Type> current = front.next;
while (current != null) {
result += ", " + current.data;
current = current.next;
}
result += "]";
return result;
}
}
/**
* Represents a list node.
* @author Letian Sun
* @version 1/18/2015
* @param <E> is of any object type
*/
protected static class ListNode<Type> {
/**
* Data stored in this node.
*/
public Type data;
/**
* Link to next node in the list.
*/
public ListNode<Type> next;
/**
* Constructs a node with given data and a null link.
* @param data assigned
*/
public ListNode(Type data) {
this(data, null);
}
/**
* Constructs a node with given data and given link.
* @param data assigned
* @param next assigned
*/
public ListNode(Type data, ListNode<Type> next) {
this.data = data;
this.next = next;
}
}
/**
* Represents an iterator for the list.
* @
* @author Letian Sun, modified from BuildingJavaPrograms 3rd Edition
*/
private class LinkedIterator implements Iterator<Type> {
/**
* Location of current value to return.
*/
private ListNode<Type> current;
/**
* flag that indicates whether list element can be removed.
*/
private boolean removeOK;
/**
* Location of the prior value in case of removal.
*/
private ListNode<Type> prior;
/**
* Constructs an iterator for the given list.
*/
public LinkedIterator() {
reset();
}
/**
* Resets iterator to first list position.
*/
public final void reset() {
current = front;
removeOK = false;
prior = null;
}
/**
* 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 current != null;
}
/**
* 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 Type next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
prior = current;
Type result = current.data;
current = current.next;
removeOK = true;
return result;
}
/**
* Removes the last element returned by the iterator.
*
* @throws IllegalStateException if a call to next has not been made
* efore call to remove.
* @see java.util.Iterator#remove()
*/
public void remove() {
if (!removeOK) {
throw new IllegalStateException();
}
AbstractLinkedMyList.this.remove(prior.data);
removeOK = false;
}
}
}
LinkedListSorted.java
package mysinglelinkedlist;
public class LinkedListSorted<E extends Comparable<E>> extends AbstractLinkedMyList<E> {
/**
* Set the element at the given index as value
* @param index the index to set value at
* @param value what to set element at the given index as
* @see mylistpackage.MyList#set(int, Object)
* @throws IllegalArugmentException if setting that value at that index would break the sorted
* property of the list
* @throws IndexOutOfBoundsException if index < 0 or index >= size
*/
@Override
public void set(int index, E value) {
if(index == 0 && front.next != null && value.compareTo(front.next.data) > 0) {
throwSortException();
}
if(index > 0) {
ListNode<E> before = nodeAt(index - 1);
ListNode<E> after = before.next.next;
if(value.compareTo(before.data) < 0 || (after != null && value.compareTo(after.data) > 0)) {
throwSortException();
}
}
//if you make it past all these tests
super.set(index, value);
}
/**
* Will throw a IllegalArgumentException that states that doing this operation will break the
* sorted property of the list
* @throws IllegalArgumentException - doing this operation will break list's sorted property.
*/
private void throwSortException() {
throw new IllegalArgumentException("Cannot set here, would break sorted property of list");
}
/**
* Insert a value into its proper place in the sorted linked list
* @param value value to insert into the sorted linked list
* @see mylistpackage.MyList#insert(Object)
*/
@Override
public void insert(E value) {
//front case
if(front == null || front.data.compareTo(value) >= 0) {
front = new ListNode<E>(value, front);
back = front;
} else {
ListNode<E> current = front;
//know at this point that the value is > front.data
while(current.next!= null && /*
* Keep going while there is a next value and the
* next value is less than the to be inserted's value
*/
current.next.data.compareTo(current.next.data) < 0) {
current = current.next;
}
current.next = new ListNode<E>(value, current.next);
}
size ++;
}
/**
* Inserts a value into the front of the sorted linked list.
* @param value - element to insert into the front.
* @throws IllegalArgumentException if inserting value as the front would
* break sorted property of the list
*/
@Override
public void insertFront(E value) {
if(front!= null && front.data.compareTo(value) < 0) {
throwSortException();
} else {
super.insertFront(value);
}
}
/**
* Insert an element at a particular element in the list
* @param index the index to insert the element at, if inserted, must maintain sorted property
* of the linked list, throw IllegalArgumentException if not
* @param value the value to insert at that index
* @throws IllegalArugmentException if inserting that value at that index would break the sorted
* property of the list
* @throws IndexOutOfBoundsException if 0 < index > size
*/
@Override
public void insertAtIndex(int index, E value) {
if(index == 0 && front != null && value.compareTo(front.data) > 0) {
throwSortException();
}
if(index == size && value.compareTo(back.data) < 0) {
throwSortException();
}
if(index > 0 && index < size) {
ListNode<E> before = nodeAt(index - 1);
if(value.compareTo(before.data) < 0 || value.compareTo(before.next.data) > 0) {
throwSortException();
}
}
//take advantage of code reuse
super.insertAtIndex(index, value);
}
/**
* Return the index of a given element.
* @see mylistpackage.MyList#getIndex(Object)
* @param value the element to return the index of
* @return the index of the given element
*/
@Override
public int getIndex(E value) {
ListNode<E> current = front;
int index = 0;
while(current!= null) {
if(current.data.compareTo(value) == 0) {
return index;
}else if(current.data.compareTo(value) > 0) {
/*no way its in sorted list, if the current element's value is greater
than what we are trying to find, optimization */
return -1;
} else {
//keep iterating
index ++;
current = current.next;
}
}
return -1;
}
/**
* Removes the first occurrence of the element from the list.
* @see mylistpackage.MyList#remove(Object)
* @param value element to remove first occurrence of
*/
@Override
public void remove(E value) {
if(front != null) {
ListNode<E> current = front;
if(front.data.equals(value)) {
front = front.next;
if(size == 1) {
back = null;
}
size --;
} else if(value.compareTo(front.data) > 0){
//flag to stop the loop if we have removed an element(first occurrence)
boolean hasRemovedElement = false;
while(current.next != null && !hasRemovedElement
/* pretty much same code as LinkedListUnsorted but added logic
* to stop iterating if we know it is not in the list(sorted
* property)
*/
&& value.compareTo(current.next.data) < 0) {
if(current.next.data.equals(value)) {
current.next = current.next.next;
hasRemovedElement = true;
size --;
}
current = current.next;
}
}
}
}
}
LinkedListUnsorted.java
package mysinglelinkedlist;
public class LinkedListUnsorted<E> extends AbstractLinkedMyList<E> {
/**
* Insert a value into the unsorted linked list.
* @see mylistpackage.MyList#insert(java.lang.Object)
* @param value the value to insert into the unsorted linked list.
*/
@Override
public void insert(E value) {
insertAtIndex(size, value);
}
/**
* Returns the index of value.
* @param value assigned.
* @see mylistpackage.MyList#getIndex(Object)
* @return index of value if in the list, -1 otherwise.
*/
public int getIndex(E value) {
int index = 0;
ListNode<E> current = front;
while (current != null) {
if (current.data.equals(value)) {
return index;
}
index++;
current = current.next;
}
return -1;
}
/**
* Remove the first occurrence of an element in unsorted linked list.
* @param value the value to remove the first occurrence of.
* @see mylistpackage.MyList#remove(java.lang.Object)
*/
@Override
public void remove(E value) {
if(front != null) {
if(front.data.equals(value)) {
front = front.next;
if(size == 1) {
back = null;
}
size --;
} else {
ListNode<E> current = front;
//flag to stop the loop if we have removed an element
boolean hasRemovedElement = false;
while(current.next != null && !hasRemovedElement) {
if(current.next.data.equals(value)) {
current.next = current.next.next;
hasRemovedElement = true;
//removed an element
size --;
} else {
current = current.next;
}
}
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.