JAVA. Code is given below, just need to finish the code that is in bold, where i
ID: 3855872 • Letter: J
Question
JAVA. Code is given below, just need to finish the code that is in bold, where it says **MUST IMPLEMENT THIS METHOD**.
QUESTION: Write a method of the ArrayList300 class (also from the hw4.jar file), called reverseList. It destructively changes the ArrayList300 object so that the ordering of the items in the list are reversed. The TestHW4 class makes a sample call to reverse. The output of this portion of the main method should be:
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<T> implements List300<T> {
// 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<size-1; i++)
b.append(items[(front+i)%items.length] + ", ");
b.append(items[(front+size-1)%items.length] + "]");
// This was for debugging purposes
// b.append(" front " + front + " back " + back + " size " + size + " length " + items.length);
return b.toString();
}
// equals must be passed a parameter of type Object,
// due to inheritance. Then it should be cast
// to the appropriate type and used as an instance
// of that type for the rest of the method
// In the test code, I call equals occasionally to make
// sure that my methods do the same thing as the corresponding
// methods. That is why the print statements are in the
// code. Once I'm certain the code works properly, I
// would take them out.
public boolean equals(Object o) {
Iterable<T> other = (Iterable<T>) o;
int i;
Iterator<T> 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<size; i++)
newItems[i] = items[(front+i)%items.length];
items = newItems;
front = 0;
back = size-1;
}
/************* 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<items.length; i++)
items[i-1] = items[i];
items[items.length-1] = items[0];
for (int i=1; i<=end; i++)
items[i-1] = items[i];
}
}
// Shift all data to the left that is between the start index
// and the end index (inclusive). This may involve wrap-around.
// This is more or less a mirror image of leftShift.
public void rightShift(int start, int end) {
// case 1: no wrap-around
if (end != items.length-1 && start <= end)
for (int i=end; 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<size; i++) {
if (items[current].equals(item))
return true;
current = (current + 1) % items.length;
}
return false;
}
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<size; i++)
if (items[pos].equals(item)) {
// remove the item by shifting data
// to the left. This has the effect
// of overwriting the removed item.
leftShift(pos, back);
size--;
return true;
}
else pos = (pos+1) % items.length;
return false;
}
// 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<T> iterator() {
return new Iterator<T>() {
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;
}
};
}
}
Explanation / Answer
Hi Please let me know if you need more information/implementation:-
==============================================
public void reverse() {
int j = items.length - 1; //points to last element
int i = 0; // and i will point to the first element in items array
T temp = null;
while(i<j)
{
temp = items[i];
items[i] = items[j];
items[j] = temp;
i++;
j--;
}
}
you can comment if you need any further implementation/change.
=========================
Thanks
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.