Question

In this assignment, you will be practicing the Java OOP skills we've learned this week in implementing a customized mutable Array class. Please read the following requirements carefully and then implement your own customized Array class:

=== 1) Basic (100' pts total) ===

Your Array class must provide the following features:

--1.1) (20' pts) Two constructors. One takes the input of the initialized capacity (int) and create the underlying array with that capacity; the other takes no input and creates an array that can hold a single element by default (that is, init capacity == 1);

--1.2) (20' pts) Getters and setters and basic methods we discussed during the class including: getCapacity(), getSize(), set(int index, E val), get(int index), isEmpty();

--1.3) (20' pts) CRUD operations we discussed during the class including: add(int index, E val), addLast(), addFirst(), remove(int index), removeLast(), removeFirst(), removeElement(int target), removeAll(int target);

--1.4) (20' pts) Supports generic types;

--1.5) (20' pts) Mutable, that is when add element exceeding its capacity, it can resize to accommodate the change.

=== 2) Bonus (20' pts total) ===

2.1) (10' pts) Implement a (private or public) swap(int a, int b) method that swaps the two elements in the index a and b if a and b are both admissible; also a public reverse() method that reverses the order of stored elements in-place (means, no additional spaces are allocated).

2.2) (10' pts) A public void sort() method sorts the stored elements in ascending order inO(nlog(n)) time.

[hint]: Quicksort or Merge sort

Answer 1

Answer for Part -1:-

class DynamicArray<T>{

private T[] arr;
private int len = 0; // length user thinks array is
private int capacity = 0; // Actual array size

public DynamicArray() {
this(1);
}

public DynamicArray(int capacity) {
if (capacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + capacity);
this.capacity = capacity;
arr = (T[]) new Object[capacity];
}

public int size() {
return len;
}

public boolean isEmpty() {
return size() == 0;
}

public T get(int index) {
return arr[index];
}

public void set(int index, T elem) {
arr[index] = elem;
}

public void removeAll() {
for (int i = 0; i < len; i++) arr[i] = null;
len = 0;
}

public void add(T elem) {

// Time to resize!
if (len + 1 >= capacity) {
if (capacity == 0) capacity = 1;
else capacity *= 2; // double the size
T[] new_arr = (T[]) new Object[capacity];
for (int i = 0; i < len; i++) new_arr[i] = arr[i];
arr = new_arr; // arr has extra nulls padded
}

arr[len++] = elem;
}

// Removes an element at the specified index in this array.
public T removeAt(int rm_index) {
if (rm_index >= len || rm_index < 0) throw new IndexOutOfBoundsException();
T data = arr[rm_index];
T[] new_arr = (T[]) new Object[len - 1];
for (int i = 0, j = 0; i < len; i++, j++)
if (i == rm_index) j--; // Skip over rm_index by fixing j temporarily
else new_arr[j] = arr[i];
arr = new_arr;
capacity = --len;
return data;
}

public boolean remove(Object obj) {
int index = indexOf(obj);
if (index == -1) return false;
removeAt(index);
return true;
}

public int indexOf(Object obj) {
for (int i = 0; i < len; i++) {
if (obj == null) {
if (arr[i] == null) return i;
} else {
if (obj.equals(arr[i])) return i;
}
}
return -1;
}

public boolean contains(Object obj) {
return indexOf(obj) != -1;
}
  
@Override
public String toString() {
if (len == 0) return "[]";
else {
StringBuilder sb = new StringBuilder(len).append("[");
for (int i = 0; i < len - 1; i++) sb.append(arr[i] + ", ");
return sb.append(arr[len - 1] + "]").toString();
}
}
}

public class Main{
public static void main(String args[]){
DynamicArray a = new DynamicArray();
a.add(1);
a.add(2);
a.add(3);
System.out.println(a.toString());
}
}
Output Screenshot:-

Answer for Part -2:-

import java.util.*;

// main class
public class Main {

static int [] arr = {10, 20, 30, 40, 50};

public static void swap(int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void reverse() {
int n = arr.length;
int[] b = new int[n];
int j = n;
for (int i = 0; i < n; i++) {
b[j - 1] = arr[i];
j = j - 1;
}
for (int i = 0; i < n; i++) {
arr[i] = b[i];
}

}

public static int partition( int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;

// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

swap (i + 1, high);

return i + 1;
}

public static void sort( int low, int high) {
if (low < high) {
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition( low, high);

// Recursively sort elements before
// partition and after partition
sort( low, pi - 1);
sort( pi + 1, high);
}
}

public static void printArray() {
for (int i = 0; i < arr.length; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

public static void main(String[] args) {

System.out.println("Array: ");
printArray();
System.out.println("Reversed Array: ");
reverse();
printArray();
System.out.println("Sorted Array: ");
sort(0, arr.length - 1);
printArray();

}
}

-------------------------------------------

Please give me a UPVOTE. Thank you :)