Java Main topics: Arrays ArrayLists Program Specification: An array that can gro
ID: 3725166 • Letter: J
Question
Java
Main topics:
Arrays
ArrayLists
Program Specification:
An array that can grow and shrink (as needed) at run time is generally called a dynamic array. You are to write a class named DynArray which can hold Double values that adheres to the following:
• The physical size of the array at all times is a nonnegative power of two (smallest of which is 1).
• The physical size is never more than 2 times the number of elements which occupy it [effective size] (with exception of when physical size is 1 and effective size is 0).
Mandatory Instance variables:
private Double[] array; NOTE: that is Double NOT double
private int physicalSize; // size of array
private int effectiveSize; // number of elements used in array
Mandatory Instance methods:
public DynArray() // constructor
// set array to a new array of Double, of size one
// set physicalSize to one,
// and set effectiveSize to zero.
public int arraySize() // accessor
// return the value of physicalSize.
// this is only for debugging purposes
public int size() // accessor
// return the value of effectiveSize.
public Double at(int index) // accessor
// if 0 <= index < effectiveSize
// return the value of array[index].
// else
// return Double.NaN
private void grow()
// make array a reference to an array that is twice as large
// that contains the same values for indicies 0 through
// effectiveSize - 1, and adjust physicalSize appropriately.
private void shrink()
// make array a reference to an array that is half as large
// that contains the same values for indicies 0 through
// effectiveSize - 1, and adjust physicalSize appropriately.
public void insertAt(int index, Double value) // mutator
// if 0 <= index <= effectiveSize
// move the necessary values forward one so that value can
// be inserted at the location index in array, inserts
// value at the location index, and adjust effectiveSize
// appropriately.
// Note: a grow() may be necessary beforehand.
// else
// do nothing.
public void insert(Double value) // mutator
// insert value at location effectiveSize.
public Double removeAt(int index) // mutator
// if 0 <= index < effectiveSize
// move the necessary values backwards one as to
// eliminate the value at the location index in array, adjust
// effectiveSize appropriately, and return the value that
// was at the location index .
// Note: a shrink() may be necessary before return.
// else
// return Double.NaN
public Double remove() // mutator
// return the removal of the value at location effectiveSize-1. public int indexOf(int start, Double value)
// return the smallest index (that is greater than or equal to start)
// such that the Double at that index is equal to the given value
// if no such index exists, return -1 public int indexOf(Double value)
// return the smallest index
// such that the Double at that index is equal to the given value
// if no such index exists, return -1
public void printArray() //accessor
// prints the values of all occupied locations of the array to
// the screen
------------------------------------------------------------------
Your Class must also work with the following Driver Class DynArrayDriver:
public class DynArrayDriver
{
public static void main(String[] args)
{
DynArray myArray = new DynArray();
System.out.println("array size = " + myArray.arraySize());
System.out.println("size = " + myArray.size());
System.out.println(" ");
double pot = 1.0;
for (int v = 0; v < 10; ++v)
{
myArray.insert(pot);
System.out.println("myArray.at(" + v + ") = " + myArray.at(v));
System.out.println("array size = " + myArray.arraySize());
System.out.println("size = " + myArray.size() + " ");
pot *= 2;
}
System.out.println("myArray.at(10) = " + myArray.at(10));
System.out.println(" ");
for (int v = 0; v < 10; ++v)
{
double value = myArray.remove();
System.out.println("value = " + value);
System.out.println("array size = " + myArray.arraySize());
System.out.println("size = " + myArray.size() + " ");
}
double value = myArray.remove();
System.out.println("value = " + value);
System.out.println("array size = " + myArray.arraySize());
System.out.println("size = " + myArray.size());
System.out.println(" ");
for (int i = 0; i < 5; ++i)
{
myArray.insertAt(i, 3.0 * i);
System.out.println("myArray.at(" + i + ") = " + myArray.at(i));
System.out.println("array size = " + myArray.arraySize());
System.out.println("size = " + myArray.size() + " ");
}
myArray.printArray();
System.out.println();
value = myArray.removeAt(2);
System.out.println("value = " + value);
System.out.println("array size = " + myArray.arraySize());
System.out.println("size = " + myArray.size() + " ");
myArray.printArray();
System.out.println();
value = myArray.removeAt(4);
System.out.println("value = " + value);
System.out.println("array size = " + myArray.arraySize());
System.out.println("size = " + myArray.size() + " ");
System.out.println();
myArray.insertAt(4, 3.0);
System.out.println("myArray.at(" + 4 + ") = " + myArray.at(4));
System.out.println("array size = " + myArray.arraySize());
System.out.println("size = " + myArray.size() + " ");
myArray.printArray();
System.out.println();
System.out.println("first location of the value 2.0 is " + myArray.indexOf(2.0));
int loc = myArray.indexOf(3.0);
System.out.println("first location of the value 3.0 is " + loc);
loc = myArray.indexOf(loc+1, 3.0);
System.out.println("second location of the value 3.0 is " + loc);
loc = myArray.indexOf(loc+1, 3.0);
System.out.println("third location of the value 3.0 is " + loc);
}
}
-------------------------------------------------------------------------------
And produce the following output (or something equivalent):
array size = 1
size = 0
myArray.at(0) = 1.0
array size = 1
size = 1
myArray.at(1) = 2.0
array size = 2
size = 2
myArray.at(2) = 4.0
array size = 4
size = 3
myArray.at(3) = 8.0
array size = 4
size = 4
myArray.at(4) = 16.0
array size = 8
size = 5
myArray.at(5) = 32.0
array size = 8
size = 6
myArray.at(6) = 64.0
array size = 8
size = 7
myArray.at(7) = 128.0
array size = 8
size = 8
myArray.at(8) = 256.0
array size = 16
size = 9
myArray.at(9) = 512.0
array size = 16
size = 10
myArray.at(10) = NaN
value = 512.0
array size = 16
size = 9
value = 256.0
array size = 16
size = 8
value = 128.0
array size = 8
size = 7
value = 64.0
array size = 8
size = 6
value = 32.0
array size = 8
size = 5
value = 16.0
array size = 8
size = 4
value = 8.0
array size = 4
size = 3
value = 4.0
array size = 4
size = 2
value = 2.0
array size = 2
size = 1
value = 1.0
array size = 1
size = 0
value = NaN
array size = 1
size = 0
myArray.at(0) = 0.0
array size = 1
size = 1
myArray.at(1) = 3.0
array size = 2
size = 2
myArray.at(2) = 6.0
array size = 4
size = 3
myArray.at(3) = 9.0
array size = 4
size = 4
myArray.at(4) = 12.0
array size = 8
size = 5
array.at(0) = 0.0
array.at(1) = 3.0
array.at(2) = 6.0
array.at(3) = 9.0
array.at(4) = 12.0
value = 6.0
array size = 8
size = 4
array.at(0) = 0.0
array.at(1) = 3.0
array.at(2) = 9.0
array.at(3) = 12.0
value = NaN
array size = 8
size = 4
myArray.at(4) = 3.0
array size = 8
size = 5
array.at(0) = 0.0
array.at(1) = 3.0
array.at(2) = 9.0
array.at(3) = 12.0
array.at(4) = 3.0
first location of the value 2.0 is -1
first location of the value 3.0 is 1
second location of the value 3.0 is 4
third location of the value 3.0 is -1
Explanation / Answer
Explanation:
Please find the below DynArray class and output based on the driver class provided.
Please revert back in case anything needs to be changed.
Program:
public class DynArray {
private Double[] array;
private int physicalSize; // size of array
private int effectiveSize; // number of elements used in array
public DynArray() {
this.physicalSize = 1;
this.array = new Double[this.physicalSize];
this.effectiveSize = 0;
}
public int arraySize() {
return physicalSize;
}
public int size() {
return effectiveSize;
}
public Double at(int index) {
if (index >=0 && index <= effectiveSize) {
return array[index];
} else {
return Double.NaN;
}
}
private void grow() {
Double[] tempArray = array;
physicalSize = physicalSize*2;
this.array = new Double[physicalSize];
for (int i=0;i<effectiveSize;i++) {
this.array[i] = tempArray[i];
}
}
private void shrink() {
Double[] tempArray = array;
if (effectiveSize < physicalSize/2) {
if (physicalSize % 2 == 0) {
physicalSize = physicalSize/2;
} else {
physicalSize = (physicalSize/2)+1;
}
this.array = new Double[physicalSize];
}
for (int i=0;i<effectiveSize;i++) {
this.array[i] = tempArray[i];
}
}
public void insertAt(int index, Double value) {
if (index >=0 && index <= effectiveSize) {
if (effectiveSize == physicalSize) {
grow();
}
this.array[index] = value;
effectiveSize++;
} else {
System.out.println("Index out of boundary");
}
}
public void insert(Double value) {
if (effectiveSize < physicalSize) {
this.array[effectiveSize] = value;
effectiveSize++;
} else {
grow();
this.array[effectiveSize] = value;
effectiveSize++;
}
}
public Double removeAt(int index) {
Double value = Double.NaN;
if (index >=0 && index < effectiveSize) {
value = this.array[index];
this.array[index] = Double.NaN;
Double[] tempArray = array;
int count = 0;
for (int i=0;i<effectiveSize;i++) {
if (index !=i) {
this.array[count] = tempArray[i];
count++;
}
}
shrink();
effectiveSize--;
return value;
} else {
return value;
}
}
public Double remove() {
if (effectiveSize >= 1) {
Double value = this.array[effectiveSize];
effectiveSize--;
value = this.array[effectiveSize];
this.array[effectiveSize] = Double.NaN;
shrink();
return value;
} else {
return Double.NaN;
}
}
public int indexOf(int start, Double value) {
for (int i=start;i<effectiveSize;i++) {
if (array[i] == value.doubleValue() ) {
return i;
}
}
return -1;
}
public int indexOf(Double value) {
for (int i=0;i<effectiveSize;i++) {
if (array[i] == value.doubleValue() ) {
System.out.println("--"+array[i]);
return i;
}
}
return -1;
}
public void printArray() {
for (int i=0;i<effectiveSize;i++) {
if (at(i) != Double.NaN ) {
System.out.println("myArray.at(" + i + ") = " +array[i]+" ");
}
}
}
}
Output:
array size = 1
size = 0
myArray.at(0) = 1.0
array size = 1
size = 1
myArray.at(1) = 2.0
array size = 2
size = 2
myArray.at(2) = 4.0
array size = 4
size = 3
myArray.at(3) = 8.0
array size = 4
size = 4
myArray.at(4) = 16.0
array size = 8
size = 5
myArray.at(5) = 32.0
array size = 8
size = 6
myArray.at(6) = 64.0
array size = 8
size = 7
myArray.at(7) = 128.0
array size = 8
size = 8
myArray.at(8) = 256.0
array size = 16
size = 9
myArray.at(9) = 512.0
array size = 16
size = 10
myArray.at(10) = null
value = 512.0
array size = 16
size = 9
value = 256.0
array size = 16
size = 8
value = 128.0
array size = 8
size = 7
value = 64.0
array size = 8
size = 6
value = 32.0
array size = 8
size = 5
value = 16.0
array size = 8
size = 4
value = 8.0
array size = 4
size = 3
value = 4.0
array size = 4
size = 2
value = 2.0
array size = 2
size = 1
value = 1.0
array size = 1
size = 0
value = NaN
array size = 1
size = 0
myArray.at(0) = 0.0
array size = 1
size = 1
myArray.at(1) = 3.0
array size = 2
size = 2
myArray.at(2) = 6.0
array size = 4
size = 3
myArray.at(3) = 9.0
array size = 4
size = 4
myArray.at(4) = 12.0
array size = 8
size = 5
myArray.at(0) = 0.0
myArray.at(1) = 3.0
myArray.at(2) = 6.0
myArray.at(3) = 9.0
myArray.at(4) = 12.0
value = 6.0
array size = 8
size = 4
myArray.at(0) = 0.0
myArray.at(1) = 3.0
myArray.at(2) = 9.0
myArray.at(3) = 12.0
value = NaN
array size = 8
size = 4
myArray.at(4) = 3.0
array size = 8
size = 5
myArray.at(0) = 0.0
myArray.at(1) = 3.0
myArray.at(2) = 9.0
myArray.at(3) = 12.0
myArray.at(4) = 3.0
first location of the value 2.0 is -1
--3.0
first location of the value 3.0 is 1
second location of the value 3.0 is 4
third location of the value 3.0 is -1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.