Please use java. Thanks!

The ArrayList is:

import java.util.Comparator;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Random;

import java.util.Arrays;

public interface ReadonlyList

{

T get(int index);

int size();

Iterator iterator();

}

public class ArrayList implements ReadonlyList

{

private Object[] array;

private int size;

public ArrayList(int capacity)

{

array = new Object[capacity];

}

public int size()

{

return size;

}

@SuppressWarnings("unchecked")

public T get(int index)

{

if (index >= size)

{

throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);

}

else

{

return (T) array[index];

}

}

public void set(int index, T value)

{

if (index >= size)

{

throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);

}

else

{

array[index] = value;

}

}

private void resize(int newCapacity)

{

Object[] original = array;

array = new Object[newCapacity];

for (int i = 0; i

{

array[i] = original[i];

}

}

public void add(T value)

{

if (size == array.length)

{

resize(size * 2);

}

array[size] = value;

size++;

}

public void addAll(T[] values)

{

for (T v : values)

{

add(v);

}

}

private void shiftRight(int index, int amount)

{

for (int k = size - 1; k >= index; k--)

{

array[k + amount] = array[k];

}

}

public void add(int index, T value)

{

if (index > size)

{

throw new IndexOutOfBoundsException(

"Index: " + index + ", Size: " + size);

}

if (size == array.length)

{

resize(size * 2);

}

shiftRight(index, 1);

array[index] = value;

size++;

}

public void addAll(int index, T[] values)

{

if (index > size)

{

throw new IndexOutOfBoundsException(

"Index: " + index + ", Size: " + size);

}

if (size + values.length > array.length)

{

resize((size + values.length) * 2);

}

shiftRight(index, values.length);

for (int k = 0; k

{

array[index + k] = values[k];

}

size += values.length;

}

public void remove()

{

if (size

{

throw new IllegalStateException("Array is empty, no item to remove!");

}

else

{

size--;

}

}

private void shiftLeft(int index, int amount)

{

for (int k = index; k + amount

{

array[k] = array[k + amount];

}

}

public void remove(int index, int count)

{

if (index + count > size)

{

throw new IndexOutOfBoundsException(

"Index: " + size + ", Size: " + size);

}

else

{

shiftLeft(index, count);

size -= count;

}

}

public void sort(Comparator c)

{

for (int i = 1; i

{

T n = get(i);

for (int j = i - 1;

j >= 0 && c.compare(n, get(j))

j--)

{

array[j + 1] = get(j);

array[j] = n;

}

}

}

public String toString()

{

if (size == 0)

{

return "[]";

}

else

{

StringBuilder stringBuilder = new StringBuilder("[");

stringBuilder.append(get(0));

for (int i = 1; i

{

stringBuilder.append(", ");

stringBuilder.append(get(i));

}

stringBuilder.append("]");

return stringBuilder.toString();

}

}

public Iterator iterator()

{

return new Iterator()

{

private int i = -1;

public boolean hasNext()

{

return i + 1

}

public T next()

{

if (!hasNext())

{

throw new NoSuchElementException();

}

i++;

return get(i);

}

};

}

public static void main(String[] args)

{

ArrayList list = new ArrayList(4);

list.addAll(new Double[] { 1.0, 1.5, 2.0, 2.5, 3.5, 4.0, 4.5, 5.0 });

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Using iterator:");

Iterator iterator = list.iterator();

while (iterator.hasNext())

{

System.out.println(iterator.next());

}

System.out.println();

System.out.println("Set element 4 to 3.14:");

list.set(4, 3.14);

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Insert 9.0 at position 3, and -5.0 at position 0:");

list.add(3, 9.0);

list.add(0, -5.0);

System.out.println("Insert 0.5, 1.5, 2.5 at position 1:");

list.addAll(1, new Double[] {0.5, 1.5, 2.5});

System.out.println("Insert 99.0 at position 13:");

list.add(13, 99.0);

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Remove three elements from the end:");

list.remove();

list.remove();

list.remove();

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Remove six elements at position 2.");

list.remove(2, 6);

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Expecting exceptions:");

try

{

System.out.println(list.get(5));

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

list.set(5, 1.0);

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

list.add(6, 1.0);

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

list.addAll(6, new Double[] {1.0, 2.0, 3.0});

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

list.remove(1, 5);

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

System.out.println(list.get(-1));

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

System.out.println();

System.out.println("Remove all but the first element:");

list.remove(1, 4);

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

list.remove();

System.out.println("List should be empty:");

System.out.println("size = " + list.size());

System.out.println();

System.out.println("Expecting exception:");

try

{

list.remove();

System.out.println("No exception!");

}

catch(IllegalStateException e)

{

e.printStackTrace();

}

Random random = new Random();

ArrayList l1 = new ArrayList(100);

for (int i = 0; i

{

l1.add(random.nextInt(100));

}

System.out.println(Arrays.toString(l1.array));

l1.sort(Comparator.naturalOrder());

System.out.println(Arrays.toString(l1.array));

ArrayList l2 = new ArrayList(100000);

for (int i = 0; i

{

l2.add(random.nextInt());

}

l2.sort(Comparator.naturalOrder());

for (int i = 1; i

{

if (l2.get(i)

{

System.out.println("FAIL: " + l2.get(i - 1) + ", " + l2.get(i));

return;

}

}

System.out.println("PASS");

}

}

1 Merging arrays0 In order to accomplish our ultimate goal of sorting an array in less than 0(n2) time, we need to first merge two sorted arrays in O(n) time. Download the ArrayList.java class posted on Moodle under Week 4. Your task is to replace the insertion-sort implementation of sort) with a merge-sort implementation. Start by writing the following helper method: public static T merge (T arrl, T arr2, Comparator comp) This should accept two sorted arrays and a Comparator as input and return a sorted array with the combined contents of both arrays Write a main) method to show that merge) works. You can use either Strings or Integers to test this easily. Use Comparator examples from lecture to create your own Comparator (consider using an anonymous class in your main0 method or even a lambda expression). Think about the edge cases you may run into when attempting to combine two arrays. Will they always be the same length? What happens when you have finished going through the elements of the first array, but not the second? 2 JUnit testing 0 Up until this point we have tested code primarily using tediously written main methods. There area number of problems with this approach, as you may have encountered. Most notably, if something is broken or not working, there is no easy way to alert the user they have to scroll through all of the console output looking for an indication of failure. JUnit solves this problem by providing an easy way to run multiple tests independently and report each of their failures. It integrates with a number of tools and can even be used to test automatically with every change you make. Assuming you are using Intellij, you can easily create a test for any public method by clicking the method name and pressing Ctrl-Shift-T. It is important to change the testing library to JUnit 4, and select all of the methods you want to create tests for (although you can easily create additional ones later). The general format for a test involves setting up some objects/state, calling a method or methods, and then asserting that either the return value is correct or some state has been modified appropriately. See the following example of tests for String.contains )