In this project, you will be providing two different implementations of a generic List interface, which defines different operations that one should be able to do with a list. A list is simply an object that represents an ordered collection of elements. The list implementation can decide how the elements are stored internally so long as users are able to interact with those elements via the methods defined in the interface. In this way, a list is an example of an abstract data type (ADT). To put it another way: while the implementor needs to undertand the specific details of the implementation (in order to write the code to make it happen), the user of a list does not. The users simply interact with objects of the list implementation through the methods defined in the interface.

Each implementation will be a generic class with specific functional and non-functional requirements. These classes need to implement List and override its methods to provide their functionality.

Functional Requirements

ArrayList: Create the cs1302.p3.ArrayList generic class with type parameter T such that it properly implements the cs1302.p3.List interface with the requirements listed below.

The generic type parameter is not bounded.

The add(T) method adds an element to the end of the list. The Javadoc documentation for this methods should clearly indicate this behavior.

You must explicitly define a default constructor for this class. The initial size of an ArrayList is 0regardless of your actual internal array capacity.

Extra Credit: Override the iterator() method for your ArrayList class as described in the List interface. This may require you to create an additional class that implements another interface.

SortedArrayList>: Create the cs1302.p3.SortedArrayList generic class with bounded type parameter T such that it properly implements the cs1302.p3.List interface with the requirements listed below.

The generic type parameter is bounded by java.util.Comparable in order to enable comparisons between existing and or prospective elements of the list.

The add(T) and add(int, T) methods are implemented such that elements are added to the list in sorted order, regardless of the index position specified. The Javadoc documentation for these methods should clearly indicate this behavior.

You must explicitly define a default constructor for this class. The initial size of a SortedArrayList is 0regardless of your actual internal array capacity.

Design Choice: Whether or not this class extends your ArrayList class is entirely up to you. The only functional requirements are that it implements the interface as described above.

Extra Credit: Override the iterator() method for your SortedArrayList class as described in the List interface. This may require you to create an additional class that implements another interface.

Storage: In general, when implementing an interface for a collection ADT (i.e., something that represents objects that contain other objects), the implementor gets to decide how the implementation stores the collection of elements. For this project, each list implementation should store its elements using an array of type Box[]. Ideally, we would want an array of type T[], but Java does not allow the creation of generic arrays. The Boxclass provides a generic static method for the creation of arrays with type Box[]. The Box class is provided to you in cs1302.p3.Box. The HTML documention for the Box class is available here. Since users of an ADT implementation do not interact with the underlying storage directly (and only through the methods defined in the interface), this non-functional requirement is transparent to users. However, using an array of generic "boxes", each containing an element of type T, does increase the level of abstraction for the implementor. To create an array of type Box[] use the static array method. Since, in this project, a list implementation is using its internal array as storage for its elements, the internal array capacity must always be at least the size of the list that uses it. You should grow and shrink the array as needed. It reccommended that you make support methods to help streamline this process as needed.

Here are the generic interfaces:

Box.java

package cs1302.p3;

// DO NOT MODIFY THIS FILE!

/**

* A box that contains an element.

*

* @param the type of element in this box

*

*/

public class Box {

/**

* Creates an array of box objects of the specified type.

*

*

* Here is an example that creates a bBox array of length 10:

* {@code

* Box[] boxes = Box.array(10);

* }

*

* @param the type of elements in each box

* @param length the length of the array to create

* @return an array of box objects

*/

@SuppressWarnings("unchecked")

public static Box[] array(int length) {

Box[] boxes = (Box[]) new Box[length];

return boxes;

} // array

private T elem = null;

/**

* Creates a new box.

*/

public Box() {}

/**

* Creates a new box with the given element.

* @param elem element in the box

*/

public Box(T elem) {

this.elem = elem;

} // Box

/**

* Return the element in the box.

* @return the element in the box

*/

public T get() {

return elem;

} // get

/**

* Sets the element in the box.

* @param elem the element in the box

*/

public void set(T elem) {

this.elem = elem;

} // set

} // Box

List.java

package cs1302.p3;

// DO NOT MODIFY THIS FILE!

import java.util.Iterator;

/**

* An ordered collection (also known as a sequence). The user of this interface

* has precise control over where in the list each element is inserted. The

* user can access elements by their integer index (position in the list), and

* search for elements in the list.

*

*

* Student implementations of this interface are not allowed to adapt existing

* implementations of java.util.List. If they do so, then their

* assignment will not be graded. Students should provide their own

* implementations.

*

*

* This interface is heavily based on java.util.List. The

* documentation here is adapted from the original documentation under academic

* fair use.

*

* @param the type of elements in this list

*

*/

public interface List {

/**

* Adds the specified element to the list at an implementation-specific

* position.

* @param elem element to be inserted

* @throws NullPointerException if elem is null

*/

void add(T elem) throws NullPointerException;

/**

* Inserts the specified element at the specified position in this list.

* Shifts the element currently at that position (if any) and any subsequent

* elements to the right (adds one to their indices).

* @param index index at which the specified element is to be inserted

* @param elem element to be inserted

* @throws NullPointerException if elem is null

* @throws IndexOutOfBoundsException if the index is out of range

* {@code (index < 0 || index > size())}

*/

void add(int index, T elem) throws NullPointerException, IndexOutOfBoundsException;

/**

* Removes all of the elements from this list. The list will be empty after

* this call returns.

*/

void clear();

/**

* Compares the specified list with this list for equality. Returns

* true if and only if the specified object is also a

* List, both lists have the same size, and all corresponding

* pairs of elements in the two lists are equal.

* If list is a list of the same list type, then students

* may safely cast the object to the appropriat list type when implementing

* this method.

* @param list the object to be compared for equality with this list

* @return true if the specified object is equal to this list

*/

boolean equals(Object list);

/**

* Returns the element at the specified position in this list.

* @param index index of the element to return

* @return the element at the specified position in this list

* @throws IndexOutOfBoundsException if the index is out of range

*/

T get(int index) throws IndexOutOfBoundsException;

/**

* Replaces the element at the specified position in this list with the

* specified element

* @param index index of the element to replace

* @param elem element to be stored at the specified position

* @return the element previously at the specified position

* @throws NullPointerException if the specified element is null

* @throws IndexOutOfBoundsException if the index is out of range

*/

T set(int index, T elem) throws NullPointerException, IndexOutOfBoundsException;

/**

* Returns the number of elements in this list. If this list contains more

* than Integer.MAX_VALUE elements, return

* Integer.MAX_VALUE.

* @return the number of elements in this list

*/

int size();

/**

* Returns true if and only if this list contains no elements.

* @return true if this list contains no elements

*/

boolean isEmpty();

/**

* Returns true if this list contains the specified element.

* More formally, returns true if and only if this list

* contains at least one element o such that

* o.equals(elem).

* @param elem element whose presence in this list is to be tested

* @return true if this list contains the specified element

* @throws NullPointerException if elem is null

*/

boolean contains(T elem) throws NullPointerException;

/**

* Returns an iterator over the elements in this list in proper sequence

* Students will need to properly create their own Iterator

* class for their list implementation and return an appropriate instance

* of it here.

*

*

* This interface method may seem strange since it's not abstract. This is

* an example of a Java 8 (or higher) default method. See the link below

* for more information on default methods.

*

* @return an iterator over the elements in this list in proper sequence

* @throws UnsupportedOperationException if the iterator operation is not

* supported by this list

*

*/

default Iterator iterator() throws UnsupportedOperationException {

throw new UnsupportedOperationException("iterator() not supported");

} // iterator()

/**

* Removes the first occurrence of the specified element from this list, if

* it is present. If this list does not contain the element, it is

* unchanged. More formally, removes the element with the lowest index

* i such that elem.equals(get(i)) (if such an

* element exists). Returns true if this list contained the

* specified element (or equivalently, if this list changed as a result of

* the call).

* @param elem element to be removed from this list, if present

* @return true if this list contained the specified element

* @throws NullPointerException if elem is null

*/

boolean remove(T elem) throws NullPointerException;

/**

* Returns the index of the first occurrence of the specified element in

* this list, or -1 if this list does not contain the element.

* @param elem element to search for

* @return the index of the first occurrence of the specified element in

* this list, or -1 if this list does not contain the element

* @throws NullPointerException if elem is null

*/

int indexOf(T elem) throws NullPointerException;

} // List

BoxTest.java

package cs1302.p3;

import static org.junit.jupiter.api.Assertions.assertEquals;

import static org.junit.jupiter.api.Assertions.assertTrue;

import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.AfterEach;

import org.junit.jupiter.api.BeforeEach;

import org.junit.jupiter.api.Test;

/**

* Unit test for the Box interface.

*/

public class BoxTest {

Box box = null;

@BeforeEach

void init() {

box = new Box();

} // init

@AfterEach

void tearDown() {

box = null;

} // tearDown

@Test

void testBox() {

final String TEST_STRING = "test";

box.set(TEST_STRING);

assertEquals(box.get(), TEST_STRING, "get() should return what is set(T)");

} // testBox

@Test

void testBoxArray() {

Box[] boxes = Box.array(2);

assertTrue(true, "should be able to make box array");

boxes[0] = box;

assertTrue(true, "should be able to assign a box to the array");

} // testBoxArray

} // BoxTest