Question

In Java:

Complete the following methods in the template by adhering to the comments:

// TO DO: add your implementation and JavaDoc

public class BetterArray<T> {
   private static final int DEFAULT_CAPACITY = 2; //default initial capacity / minimum capacity
   private T[] data;  //underlying array, you MUST use this for full credit

   // ADD MORE PRIVATE MEMBERS HERE IF NEEDED!

   @SuppressWarnings("unchecked")
   public BetterArray() {
      //constructor
      //initial capacity of the array should be DEFAULT_CAPACITY
   }

   @SuppressWarnings("unchecked")
   public BetterArray(int initialCapacity) {
      // constructor
      // set the initial capacity of the smart array as initialCapacity
      // throw IllegalArgumentException if initialCapacity is smaller than 1
   }


   public int size() {
      //report number of elements in the smart array
      // O(1)

      return -1;
   }

   public int capacity() {
      //report max number of elements before the next expansion
      // O(1)

      return -1;
   }

   @SuppressWarnings("unchecked")
   public boolean append(T value) {
      // add an element to the end   
      // return true  

      // double capacity if no space available
      // amortized O(1)

      return false;
   }

   @SuppressWarnings("unchecked")
   public void add(int index, T value) {
      // insert value at index, shift elements if needed  
      // double the capacity if no space is available
      // throw IndexOutOfBoundsException for invalid index
      // O(N) where N is the number of elements in the array

      // Note: this method may be used to append items as
      // well as insert items
   }

   public T get(int index){
      // return the item at index
      // throw IndexOutOfBoundsException for invalid index
      // O(1)

      return null;
   }

   public T replace(int index, T value){
      // change item at index to be value    
      // return old item at index
      // throw IndexOutOfBoundsException for invalid index
      // O(1)

      // Note: you cannot add new items with this method

      return null;
   }

   @SuppressWarnings("unchecked")
   public T delete(int index){
      // remove and return element at position index
      // shift elements to remove any gap in the array
      // throw IndexOutOfBoundsException for invalid index

      // halve capacity if the number of elements falls below 1/4 of the capacity
      // capacity should NOT go below DEFAULT_CAPACITY

      // O(N) where N is the number of elements in the list

      return null;
   }

   public int firstIndexOf(T value){
      // return the index of the first occurrence or -1 if not found
      // O(n)

      return -1;
   }

   @SuppressWarnings("unchecked")
   public boolean ensureCapacity(int newCapacity){
      // change the max number of items allowed before next expansion to newCapacity

      // capacity should not be changed if:
      //   - newCapacity is below DEFAULT_CAPACITY; or 
      //   - newCapacity is not large enough to accommodate current number of items

      // return true if newCapacity gets applied; false otherwise
      // O(N) where N is the number of elements in the array 

      return false;
   }

   public BetterArray<T> clone() {
      //make a copy of all the current values
      //don't forget to set the capacity!
      //O(n)

      return null;
   }


   // --------------------------------------------------------
   // example testing code... edit this as much as you want!
   // --------------------------------------------------------
   public static void main(String args[]) {
      //create a smart array of integers
      BetterArray<Integer> nums = new BetterArray<>();
      if ((nums.size() == 0) && (nums.capacity() == 2)){
         System.out.println("Yay 1");
      }

      //append some numbers 
      for (int i=0; i<3;i++)
         nums.add(i,i*2);

      if (nums.size()==3 && nums.get(2) == 4 && nums.capacity() == 4 ){
         System.out.println("Yay 2");
      }

      //create a smart array of strings
      BetterArray<String> msg = new BetterArray<>();

      //insert some strings
      msg.add(0,"world");
      msg.add(0,"hello");
      msg.add(1,"new");
      msg.append("!");

      //replace and checking
      if (msg.get(0).equals("hello") && msg.replace(1,"beautiful").equals("new")
            && msg.size() == 4 && msg.capacity() == 4 ){
         System.out.println("Yay 3");
      }

      //change capacity
      if (!msg.ensureCapacity(0) && !msg.ensureCapacity(3) && msg.ensureCapacity(20)
            && msg.capacity() == 20){
         System.out.println("Yay 4");
      }

      //delete and shrinking
      if (msg.delete(1).equals("beautiful") && msg.get(1).equals("world")
            && msg.size() == 3 && msg.capacity() == 10 ){
         System.out.println("Yay 5");
      }

      //firstIndexOf and clone
      //remember what == does on objects... not the same as .equals()
      BetterArray<String> msgClone = msg.clone();
      if (msgClone != msg && msgClone.get(1) == msg.get(1)
            && msgClone.size() == msg.size()
            && msgClone.capacity() == msg.capacity()
            && msgClone.firstIndexOf("world") == 1
            && msgClone.firstIndexOf("beautiful") == -1) {
         System.out.println("Yay 6");
      }
   }

   // --------------------------------------------------------
   // DO NOT EDIT ANYTHING BELOW THIS LINE (except to add JavaDocs)
   // --------------------------------------------------------

   public String toString() {
      if(size() == 0) return "";

      StringBuffer sb = new StringBuffer();
      sb.append(get(0));
      for(int i = 1; i < size(); i++) {
         sb.append(", ");
         sb.append(get(i));
      }
      return sb.toString();
   }
}

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// BetterArray.java

public class BetterArray<T> {

      private static final int DEFAULT_CAPACITY = 2; // default initial capacity /

                                                                               // minimum capacity

      private T[] data; // underlying array, you MUST use this for full credit

      // number of elements

      private int size;

      /**

      * default constructor

      */

      @SuppressWarnings("unchecked")

      public BetterArray() {

            data = (T[]) new Object[DEFAULT_CAPACITY];

            size = 0;

      }

      /**

      * constructor taking initial capacity

      *

      * @param initialCapacity

      *            capacity >= 1, if less than 1, will throw

      *            IllegalArgumentException

      */

      @SuppressWarnings("unchecked")

      public BetterArray(int initialCapacity) {

            // constructor

            // set the initial capacity of the smart array as initialCapacity

            // throw IllegalArgumentException if initialCapacity is smaller than 1

            if (initialCapacity < 1) {

                  throw new IllegalArgumentException("Invalid capacity");

            }

            data = (T[]) new Object[initialCapacity];

            size = 0;

      }

      /**

      * getter for list size

      *

      * @return the size

      */

      public int size() {

            // report number of elements in the smart array

            // O(1)

            return size;

      }

      /**

      * report max number of elements before the next expansion

      *

      * @return the current capacity

      */

      public int capacity() {

            // report max number of elements before the next expansion

            // O(1)

            return data.length;

      }

      /**

      * adds an element to the end

      *

      * @param value

      *            value to be added

      * @return true if added, false if not

      */

      public boolean append(T value) {

            // resizing array to double capacity if full

            if (size == data.length) {

                  ensureCapacity(data.length * 2);

            }

            // adding to end

            data[size] = value;

            size++;

            return true;

      }

      /**

      * insert value at index

      *

      * @param index

      *            index value

      * @param value

      *            value to be added

      * @throws IndexOutOfBoundsException

      *             if index is invalid

      */

      public void add(int index, T value) {

            // insert value at index, shift elements if needed

            // double the capacity if no space is available

            // throw IndexOutOfBoundsException for invalid index

            // O(N) where N is the number of elements in the array

            // throwing exception if index is invalid

            if (index < 0 || index > size) {

                  throw new IndexOutOfBoundsException("Invalid index");

            }

            // resizing array if necessary

            if (size == data.length) {

                  ensureCapacity(data.length * 2);

            }

            // shifting elements starting from index to one place right

            for (int i = size; i > index; i--) {

                  data[i] = data[i - 1];

            }

            // adding element to index, and updating size

            data[index] = value;

            size++;

      }

      /**

      * return the item at index

      *

      * @param index

      *            index of element

      * @return the element at index

      * @throws IndexOutOfBoundsException

      *             if index is invalid

      */

      public T get(int index) {

            // throwing exception if index is invalid

            if (index < 0 || index >= size) {

                  throw new IndexOutOfBoundsException("Invalid index");

            }

            // return the item at index

            return data[index];

      }

      /**

      * replace an element at specified index with new one

      *

      * @param index

      *            index of element

      * @param value

      *            new value

      * @return old value

      * @throws IndexOutOfBoundsException

      *             if index is invalid

      */

      public T replace(int index, T value) {

            // throwing exception if index is invalid

            if (index < 0 || index > size) {

                  throw new IndexOutOfBoundsException("Invalid index");

            }

            // storing old value

            T oldValue = data[index];

            // replacing with new value

            data[index] = value;

            // returning old value

            return oldValue;

      }

      /**

      * removes and returns element at an index

      *

      * @param index

      *            index of element to delete

      * @return deleted element

      */

      public T delete(int index) {

            // throwing exception if index is invalid

            if (index < 0 || index > size) {

                  throw new IndexOutOfBoundsException("Invalid index");

            }

            // storing element to remove

            T element = data[index];

            // shifting all elements starting from index+1 position, to one place

            // left

            for (int i = index; i < size - 1; i++) {

                  data[i] = data[i + 1];

            }

            // updating size, returning removed element

            size--;

            // checking if size go below 1/4th of capacity

            if (size < (data.length / 4)) {

                  // finding new capacity (half)

                  int newCapacity = data.length / 2;

                  // if this new capacity is below default capacity, using default

                  // capacity

                  if (newCapacity < DEFAULT_CAPACITY) {

                        newCapacity = DEFAULT_CAPACITY;

                  }

                  // resizing array

                  ensureCapacity(newCapacity);

            }

            // returning removed element

            return element;

      }

      /**

      * returns the first index of an element

      *

      * @param value

      *            element

      * @return first index, -1 if not found

      */

      public int firstIndexOf(T value) {

            // looping through elements

            for (int i = 0; i < size; i++) {

                  if (data[i].equals(value)) {

                        return i; // found

                  }

            }

            return -1; // not found

      }

      /**

      * upsize or downsize the underlying array as needed

      *

      * @param newCapacity

      *            new capacity

      * @return true if resized, false if not

      */

      @SuppressWarnings("unchecked")

      public boolean ensureCapacity(int newCapacity) {

            // change the max number of items allowed before next expansion to

            // newCapacity

            // capacity should not be changed if:

            // - newCapacity is below DEFAULT_CAPACITY; or

            // - newCapacity is not large enough to accommodate current number of

            // items

            // return true if newCapacity gets applied; false otherwise

            // O(N) where N is the number of elements in the array

            // creating array of new size

            if (newCapacity < DEFAULT_CAPACITY || newCapacity < size) {

                  return false;

            }

            // creating new array with enough capacity

            T newArr[] = (T[]) new Object[newCapacity];

            // copying elements

            for (int i = 0; i < size && i < newCapacity; i++) {

                  newArr[i] = data[i];

            }

            // replacing old with new array

            data = newArr;

            return true;

      }

      /**

      * returns a BetterArray object, which is same as this object

      *

      * @return cloned BetterArray object with same capacity, elements

      */

      public BetterArray<T> clone() {

            // make a copy of all the current values

            // don't forget to set the capacity!

            // O(n)

            BetterArray<T> cloned = new BetterArray<T>(data.length);

            // copying all elements

            for (int i = 0; i < size; i++) {

                  cloned.data[i] = data[i];

            }

            // updating size

            cloned.size = size;

            return cloned;

      }

      // --------------------------------------------------------

      // example testing code... edit this as much as you want!

      // --------------------------------------------------------

      public static void main(String args[]) {

            // create a smart array of integers

            BetterArray<Integer> nums = new BetterArray<Integer>();

            if ((nums.size() == 0) && (nums.capacity() == 2)) {

                  System.out.println("Yay 1");

            }

            // append some numbers

            for (int i = 0; i < 3; i++)

                  nums.add(i, i * 2);

            if (nums.size() == 3 && nums.get(2) == 4 && nums.capacity() == 4) {

                  System.out.println("Yay 2");

            }

            // create a smart array of strings

            BetterArray<String> msg = new BetterArray<String>();

            // insert some strings

            msg.add(0, "world");

            msg.add(0, "hello");

            msg.add(1, "new");

            msg.append("!");

            // replace and checking

            if (msg.get(0).equals("hello")

                        && msg.replace(1, "beautiful").equals("new") && msg.size() == 4

                        && msg.capacity() == 4) {

                  System.out.println("Yay 3");

            }

            // change capacity

            if (!msg.ensureCapacity(0) && !msg.ensureCapacity(3)

                        && msg.ensureCapacity(20) && msg.capacity() == 20) {

                  System.out.println("Yay 4");

            }

            // delete and shrinking

            if (msg.delete(1).equals("beautiful") && msg.get(1).equals("world")

                        && msg.size() == 3 && msg.capacity() == 10) {

                  System.out.println("Yay 5");

            }

            // firstIndexOf and clone

            // remember what == does on objects... not the same as .equals()

            BetterArray<String> msgClone = msg.clone();

            if (msgClone != msg && msgClone.get(1) == msg.get(1)

                        && msgClone.size() == msg.size()

                        && msgClone.capacity() == msg.capacity()

                        && msgClone.firstIndexOf("world") == 1

                        && msgClone.firstIndexOf("beautiful") == -1) {

                  System.out.println("Yay 6");

            }

      }

      // --------------------------------------------------------

      // DO NOT EDIT ANYTHING BELOW THIS LINE (except to add JavaDocs)

      // --------------------------------------------------------

      public String toString() {

            if (size() == 0)

                  return "";

            StringBuffer sb = new StringBuffer();

            sb.append(get(0));

            for (int i = 1; i < size(); i++) {

                  sb.append(", ");

                  sb.append(get(i));

            }

            return sb.toString();

      }

}

/*OUTPUT*/

Yay 1

Yay 2

Yay 3

Yay 4

Yay 5

Yay 6