JAVA. Code that needs to be completed is in bold(Also where it says, this must b
ID: 3855187 • Letter: J
Question
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<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
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;
}
};
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.