JAVA. Code that needs to be completed is in bold(Also where it says, this must be completed).

Draw a depiction of an ArrayList300 object and a LinkedList300 object, as they are implemented in the accompanying hw4.jar file, after each operation in the following sequence. The ArrayList300 class uses wrap-around and chooses to shift data based on an index (for those methods that are passed indices), and the LinkedList300 class is a doubly-linked implementation with sentinels. Assume the lists are initially empty.

list.add(a);

list.add(0, b);

list.add (1, c);

list.add(d);

list.remove(2);

package hw4;

/* * CSC 300 Sections 201, 210 Summer I 2017 * Homework assignment 4, part 3 * * You must complete the reverse method below. * Reverse should be a destructive method; * that is, it should make changes to the * ArrayList300 object that it is invoked on. * * This is the full-fledged version of an array-based * implementation of List. It uses a wrap-around array. * When data shifting is necessary (as it is in add and * remove), we determine which way to shift based on the * index passed. The the index is less than halfway * through the list, then data is shifted from the left * otherwise it's to the right. * * Notice that because of wrap-around, the front of the * list does not necessary correspond to index 0 in the * array. */

import java.util.Iterator; import java.util.List;

public class ArrayList300 implements List300 { // the initial capacity can be whatever we want. // In Java, by default the initial capacity of // ArrayList is 10. private static final int INIT_CAPACITY = 5; private T[] items = (T[]) new Object[INIT_CAPACITY]; // front is the index where the list begins, and // back is where it ends. At times, it will be the // case that front > back, which would indicate that // wrap-around has occurred. // Note that the size of the list is somewhat difficult // to compute based on the values of front and back. // If there is no wrap-around, size = (back-front)+1. // If there is wrap-around, size = (back-front)+items.length+1 private int size, front, back; public ArrayList300() { // by convention we'll indicate an empty list by // setting front and back to -1 front = -1; back = -1; size = 0; }

// this was mainly for testing purposes. Create an // ArrayList as specified by the parameters public ArrayList300(T[] initItems, int front, int back, int size) { items = initItems; this.front = front; this.back = back; this.size = size; }

public String toString() { if (size == 0) return "[]"; StringBuilder b = new StringBuilder("["); // Notice that since the front of the list is not necessarily // at index 0 of the "items" array, the for loop calculates // (front+i) % items.length to compute the location of the next // item in the list. The % operator is needed because of potential // wrap-around for (int i=0; i other = (Iterable) o; int i; Iterator it = iterator(), otherIt = other.iterator(); for (i=0; it.hasNext() && otherIt.hasNext(); i++) { T mine = it.next(); T others = otherIt.next(); /* * this was for debugging * if (mine == null) { System.out.println("Mine is null"); System.out.println(this + " size = " + size + " front = " + front + " back = " + back + " length " + items.length); System.exit(0); } if (!mine.equals(others)) { System.out.println("lists are not equal at index " + i); return false; } */ } if (it.hasNext() != otherIt.hasNext()) { // System.out.println("lists are not equal at index " + i); return false; } return true; }

// when the list is expanded, we eliminate wrap-around by copying the // items in the old array in such a way that the first item in the // list is place in newItems[0] private void expand() { T[ ] newItems = (T[ ]) new Object[items.length*2]; for (int i=0; i /************* YOU MUST WRITE THIS METHOD *********/ public void reverse() { } public boolean add(T item) { if (size == items.length) expand(); // special case: in an empty list, back and front are both -1. // So they should now both be set to 0. if (isEmpty()) { front = back = 0; items[0] = item; size = 1; } // otherwise, increment back (but use % to wrap around if // necessary), and store the new item at that position. // Also, of course size needs to be incremented. else { back = (back + 1) % items.length; items[back] = item; size++; } return true; }

// Add is written to decide which way to shift, in order // to make room and place the new item at the position specified // by idx. If idx is less than half of the size of the list, // then left shifting is performed to make room // for item. Otherwise, right shifting is performed. public void add(int idx, T item) { if (size == items.length) expand(); // case 1: add to the end if (idx == size) add(item); // case 2: add to the front else if (idx == 0) { front--; if (front < 0) front += items.length; items[front] = item; size++; } // case 3: add somewhere in the middle. // determine whether to shift data to the left or the right // depending on precisely where the new item is to be // placed else { // calculate the index into "items" (pos) that corresponds // to the correct position in the list (idx) int pos = (front+idx-1); if (pos < 0) pos += items.length; else pos %= items.length; // if the new data is to be inserted somewhere in // the first half of the list, left shift data in // order to make room for the new item // For example: // // ------------------- // | a | c | d | e | | // ------------------- // front = 0, back = 3, size = 4 // // list.add(1, "b"); // // In this case, we choose to left shift, resulting in // ------------------- // | b | c | d | e | a | // ------------------- // front = 4, back = 3, size = 5 if (idx <= size/2) { leftShift(front, pos); items[pos] = item; front--; if (front<0) front += items.length; size++; } // otherwise, right shift. For example: // // ------------------- // | e | | a | b | c | // ------------------- // front = 2, back = 0, size = 4 // // list.add(3, "d"); // // We choose to right shift, resulting in // ------------------- // | d | e | a | b | c | // ------------------- // front = 2, back = 1, size = 5 else { rightShift(pos, back); items[pos] = item; back = (back + 1) % items.length; size++; } } }

// Shift all data to the left that is between the start index // and the end index (inclusive). This may involve wrap-around public void leftShift(int start, int end) { // case 1: no wrap-around if (start != 0 && start <= end) for (int i=start; i<=end; i++) items[i-1] = items[i]; // case 2: wrap-around, in which case there are 3 steps // (a) shift data between indices start and items.length-1 (inclusive) // (b) copy items[0] into items[items.length-1] // (c) shift data between indices 1 and end (inclusive) else { if (start != 0) for (int i=start; i=start; i--) items[i+1] = items[i]; // case 2: wrap-around, in which case there are 3 steps // (a) shift data between indices start and items.length-1 (inclusive) // (b) copy items[0] into items[items.length-1] // (c) shift data between indices 1 and end (inclusive) else { if (end != items.length) for (int i=end; i>=0; i--) items[i+1] = items[i]; items[0] = items[items.length-1]; for (int i=items.length-2; i>=end; i--) items[i+1] = items[i]; } } // returns the current value stored in position idx public T set(int idx, T item) { if (idx >= size) throw new IndexOutOfBoundsException(); int pos = (idx + front) % items.length; T oldContents = items[pos]; items[pos] = item; return oldContents; }

// return true if item is in the list, or false otherwise. public boolean contains(T item) { int current = front; for (int i=0; i

public T get(int idx) { if (idx >= size) throw new IndexOutOfBoundsException(); return items[(idx+front)%items.length]; }

public void clear() { size = 0; front = -1; back = -1; }

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

public int size() { return size; }

public boolean remove(T item) { int pos = front; for (int i=0; i

// Remove is written to decide which way to shift, in order // to remove the item at the position specified by idx. // If idx is less than half of the size of the list, // then right shifting is performed to remove the item. // Otherwise, left shifting is performed. public T remove(int idx) { // calculate the index into "items" (pos) that corresponds // to the correct position in the list (idx) int pos = (front+idx) % items.length; T answer = items[pos]; // determine whether to shift data to the left or the right // depending on precisely where the item is being // removed from the list

// if the data to be removed is somewhere in // the first half of the list, right shift data in // order to overwrite the deleted item // For example: // // ------------------- // | a | b | c | d | | // ------------------- // front = 0, back = 3, size = 4 // // list.remove(1); // // In this case, we choose to right shift, resulting in // ------------------- // | a | a | c | d | | // ------------------- // front = 1, back = 3, size = 3 // // Note that "a" is also at index 0 in the "items" // array. This is because there is no real need // to clear index 0; we can tell from front and back // that this "a" is not in the list. Eventually, // it will probably be overwritten as the list grows // and shrinks. if (idx < size/2 && pos != 0) { rightShift(front, pos-1); front = (front + 1) % items.length; size--; } // otherwise, left shift. For example: // // ------------------- // | d | | a | b | c | // ------------------- // front = 2, back = 0, size = 4 // // list.remove(2); // // We choose to left shift, resulting in // ------------------- // | d | | a | b | d | // ------------------- // front = 2, back = 4, size = 3 // // Again, the "d" remains also at index 0 of "items". // There is no need to set items[0] back to null, // because we can tell by the values of front and // back that items[0] is not in the list. Eventually, // it is likely the items[0] will be overwritten // as the list grows and shrinks. else { leftShift((pos+1)%items.length, back); back -= 1; if (back < 0) back += items.length; size--; } return answer; }

public Iterator iterator() { return new Iterator() { private int current = front; private int i = 0; public boolean hasNext() { return i < size; }

public T next() { i++; T answer = items[current]; current = (current + 1) % items.length; return answer; } }; }

}