please use java thanks please use java thanks the arraylist code: import java.ut
ID: 3912356 • Letter: P
Question
please use java thanks please use java thanks the arraylist code: import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Random; import java.util.Arrays;public class ArrayList<T> implements ReadonlyList<T> { 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 < size; 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 < values.length; k++) { array[index + k] = values[k]; }
size += values.length; } public void remove() { if (size <= 0) { 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 < size; k++) { 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<T> c) { for (int i = 1; i < size; i++) { T n = get(i);
for (int j = i - 1; j >= 0 && c.compare(n, get(j)) < 0; 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 < size; i++) { stringBuilder.append(", "); stringBuilder.append(get(i)); } stringBuilder.append("]"); return stringBuilder.toString(); } } public Iterator<T> iterator() { return new Iterator<T>() { private int i = -1; public boolean hasNext() { return i + 1 < size; } public T next() { if (!hasNext()) { throw new NoSuchElementException(); } i++; return get(i); } }; } public static void main(String[] args) { ArrayList<Double> list = new ArrayList<Double>(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 < list.size(); i++) { System.out.println(list.get(i)); } System.out.println(); System.out.println("Using iterator:"); Iterator<Double> 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 < list.size(); 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 < list.size(); 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 < list.size(); 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 < list.size(); 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 < list.size(); 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<Integer> l1 = new ArrayList<Integer>(100); for (int i = 0; i < 100; 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<Integer> l2 = new ArrayList<Integer>(100000); for (int i = 0; i < 100000; i++) { l2.add(random.nextInt()); } l2.sort(Comparator.naturalOrder()); for (int i = 1; i < l2.size(); i++) { if (l2.get(i) < l2.get(i - 1)) { System.out.println("FAIL: " + l2.get(i - 1) + ", " + l2.get(i)); return; } } System.out.println("PASS"); } } import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Random; import java.util.Arrays;
public class ArrayList<T> implements ReadonlyList<T> { 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 < size; 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 < values.length; k++) { array[index + k] = values[k]; }
size += values.length; } public void remove() { if (size <= 0) { 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 < size; k++) { 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<T> c) { for (int i = 1; i < size; i++) { T n = get(i);
for (int j = i - 1; j >= 0 && c.compare(n, get(j)) < 0; 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 < size; i++) { stringBuilder.append(", "); stringBuilder.append(get(i)); } stringBuilder.append("]"); return stringBuilder.toString(); } } public Iterator<T> iterator() { return new Iterator<T>() { private int i = -1; public boolean hasNext() { return i + 1 < size; } public T next() { if (!hasNext()) { throw new NoSuchElementException(); } i++; return get(i); } }; } public static void main(String[] args) { ArrayList<Double> list = new ArrayList<Double>(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 < list.size(); i++) { System.out.println(list.get(i)); } System.out.println(); System.out.println("Using iterator:"); Iterator<Double> 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 < list.size(); 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 < list.size(); 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 < list.size(); 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 < list.size(); 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 < list.size(); 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<Integer> l1 = new ArrayList<Integer>(100); for (int i = 0; i < 100; 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<Integer> l2 = new ArrayList<Integer>(100000); for (int i = 0; i < 100000; i++) { l2.add(random.nextInt()); } l2.sort(Comparator.naturalOrder()); for (int i = 1; i < l2.size(); i++) { if (l2.get(i) < l2.get(i - 1)) { System.out.println("FAIL: " + l2.get(i - 1) + ", " + l2.get(i)); return; } } System.out.println("PASS"); } } 1Merging arrays 0 In order to accomplish our ultimate goal of sorting an array in less than O(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 (TI) 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 main) 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?
Explanation / Answer
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Arrays;
public class ArrayList<T> implements ReadonlyList<T>
{
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 < size; 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 < values.length; k++)
{
array[index + k] = values[k];
}
size += values.length;
}
public void remove()
{
if (size <= 0)
{
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 < size; k++)
{
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 static <T> T[] merge(T[] arr1,T[] arr2,Comparator<T> comp)
{
Object[] list=new Object[arr1.length+arr2.length];
int i=0,j=0,k=0;
while(i<arr1.length && j<arr2.length)
{
if(comp.compare(arr1[i],arr2[j])<0)
list[k++]=arr1[i++];
else
list[k++]=arr2[j++];
}
while(i<arr1.length)list[k++]=arr1[i++];
while(j<arr2.length)list[k++]=arr2[j++];
return (T[])list;
}
public void sort(Comparator<T> c)
{
for (int i = 1; i < size; i++)
{
T n = get(i);
for (int j = i - 1;
j >= 0 && c.compare(n, get(j)) < 0;
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 < size; i++)
{
stringBuilder.append(", ");
stringBuilder.append(get(i));
}
stringBuilder.append("]");
return stringBuilder.toString();
}
}
public Iterator<T> iterator()
{
return new Iterator<T>()
{
private int i = -1;
public boolean hasNext()
{
return i + 1 < size;
}
public T next()
{
if (!hasNext())
{
throw new NoSuchElementException();
}
i++;
return get(i);
}
};
}
public static void main(String[] args)
{
ArrayList<Double> list = new ArrayList<Double>(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 < list.size(); i++)
{
System.out.println(list.get(i));
}
System.out.println();
System.out.println("Using iterator:");
Iterator<Double> 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 < list.size(); 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 < list.size(); 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 < list.size(); 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 < list.size(); 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 < list.size(); 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<Integer> l1 = new ArrayList<Integer>(100);
for (int i = 0; i < 100; 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<Integer> l2 = new ArrayList<Integer>(100000);
for (int i = 0; i < 100000; i++)
{
l2.add(random.nextInt());
}
l2.sort(Comparator.naturalOrder());
for (int i = 1; i < l2.size(); i++)
{
if (l2.get(i) < l2.get(i - 1))
{
System.out.println("FAIL: " + l2.get(i - 1) + ", " + l2.get(i));
return;
}
}
System.out.println("PASS");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.