Program Specification: An array that can grow and shrink (as needed) at run time
ID: 3596711 • Letter: P
Question
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 (with exception
to when it is at size 1). Mandatory Instance variables:
Mandatory Instance methods:
Your Class must also work with the following Driver Class DynArrayDriver:
} }
And produce the following output (or something equivalent):
elements = 9
Explanation / Answer
import java.util.Arrays;
// Class DynArray definition
class DynArray
{
// Declare an double array to store data
private double[] array;
// To store size of array
private int size;
// To store next index position
private int nextIndex;
// Default constructor
public DynArray()
{
// Set array to a new array of double, of size one set size to one, and set nextIndex to zero.
array = new double[1];
size = 1;
nextIndex = 0;
}// End of constructor
// Method to return array size
public int arraySize() // Accessor
{
// return the value of size.
return size;
}//End of method
// Method to return next index position
public int elements() // accessor
{
// return the value of nextIndex.
return nextIndex;
}//End of method
// Method to return value at given index position
public double at(int index) // accessor
{
// if 0 <= index < nextIndex
if(index >=0 && index < nextIndex)
// return the value of array[index].
return array[index];
// Otherwise
else
// return Double.NaN.
return Double.NaN;
}//End of method
// Method to increase the array size double to its previous size
private void grow()
{
// make array a reference to an array that is twice as large
// and contains the same values for indicies 0 through
// nextIndex - 1, and adjust size appropriately.
if(nextIndex == size)
{
// Increase the size of the array double to its previous size
array = Arrays.copyOf(array, size * 2);
// Update the size by multiplying it by two
size = size *2;
}//End of if condition
}//End of method
// Method to decrease the array size by half to its previous size
private void shrink()
{
// make array a reference to an array that is half as large
// and contains the same values for indicies 0 through
// nextIndex - 1, and adjust size appropriately.
//Checks if the next index is not zero
if(nextIndex != 0)
if(nextIndex <= (size/2))
{
// Decrease the size of array by half
array = Arrays.copyOf(array, size/2);
// Update the size by dividing it by two
size = size / 2;
}//End of if condition
}//End of method
// Method to insert an data at given index position
public void insertAt(int index, double value) // mutator
{
// if 0 <= index <= nextIndex
if(index >= 0 && index <= nextIndex)
// move the necessary values over one so that value can be inserted at the location index in the array,
// inserts inserts value at the location index, and adjust nextIndex appropriately.
// Note a grow() may be necessary before or after.
{
// Calls grow() method to increase the array size to double
grow();
// Loop starts from next index position to index position specified
for(int x = nextIndex; x > index; x--)
// Move one position right
array[x] = array[x-1];
}// End of if condition
// Stores the given data in given index position as parameter
array[index] = value;
// Increase the next index position by one
nextIndex++;
}// End of method
// Method to insert data in the array
public void insert(double value) // mutator
{
// Calls grow() method to increase the array size to double
grow();
// insert value at location nextIndex.
array[nextIndex] = value;
// Increase the next index position by one
nextIndex++;
}// End of method
// Method to delete a data at specified index position
public double removeAt(int index) // mutator
{
// if 0 <= index < nextIndex
if(index >=0 && index < nextIndex)
{
// move the necessary values over one as to eliminate
// the value at the location index in the array, adjust
// nextIndex appropriately, and return the value that was
// at the location index .
// Note: a shrink() may be necessary before or after.
// Extracts data at specified index position as in parameter
double value = at(index);
// Calls shrink() method to decrease the array size to half
shrink();
// Loop starts from index position specified in parameter and stops at next index position minus one
for(int x = index; x < nextIndex-1; x++)
// Moves data one position left
array[x] = array[x+1];
// Decrease the next index position by one
nextIndex--;
// Retuns the deleted value
return value;
}// End of if condition
// Otherwise
else
// Returns NAN
return Double.NaN;
}// End of method
// Method to delete a data at next index position
public double remove() // mutator
{
// Calls shrink() method to decrease the array size to half
shrink();
// Extracts data at specified index position as in parameter
double value = at(nextIndex-1);
// Decrease the next index position by one
--nextIndex;
// Checks if next index position is -1 then set it to zero
if(nextIndex == -1)
nextIndex = 0;
// return the removal of the value at location nextIndex-1.
return value;
}// End of method
// Method to print all the data in array
public void printArray() //accessor
{
// prints the values of all occupied locations of the array to the screen
for(int x = 0; x < nextIndex; x++)
System.out.printf(" array.at(%d) = %.2f", x, array[x]);
}// End of method
}// End of class
// Driver class DynArrayDriver definition
public class DynArrayDriver
{
// main method definition
public static void main(String[] args)
{
// Declares an object of class DynArray()
DynArray myArray = new DynArray();
System.out.println("size = " + myArray.arraySize());
System.out.println("elements = " + myArray.elements());
//System.out.println(" ");
int pot = 1;
// Loops 10 times
for (int v = 0; v < 10; ++v)
{
myArray.insert(pot);
System.out.println("myArray.at(" + v + ") = " + myArray.at(v));
System.out.println("size = " + myArray.arraySize());
System.out.println("elements = " + myArray.elements());
pot *= 2;
}// End of for loop
System.out.println("myArray.at(10) = " + myArray.at(10));
System.out.println(" ");
// Loops 10 times
for (int v = 0; v < 10; ++v)
{
double value = myArray.remove();
System.out.println("value = " + value);
System.out.println("size = " + myArray.arraySize());
System.out.println("elements = " + myArray.elements() + " ");
}// End of for loop
double value = myArray.remove();
System.out.println("value = " + value);
System.out.println("size = " + myArray.arraySize());
System.out.println("elements = " + myArray.elements());
System.out.println(" ");
// Loops 5 times
for (int i = 0; i < 5; ++i)
{
myArray.insertAt(i, 3 * i);
System.out.println("myArray.at(" + i + ") = " + myArray.at(i));
System.out.println("size = " + myArray.arraySize());
System.out.println("elements = " + myArray.elements() + " ");
}// End of for loop
myArray.printArray();
value = myArray.removeAt(2);
System.out.println();
System.out.println("value = " + value);
System.out.println("size = " + myArray.arraySize());
System.out.println("elements = " + myArray.elements() + " ");
myArray.printArray();
System.out.println();
value = myArray.removeAt(4);
System.out.println("value = " + value);
System.out.println("size = " + myArray.arraySize());
System.out.println("elements = " + myArray.elements() + " ");
} // End of main method
}// End of class
Sample Run:
size = 1
elements = 0
myArray.at(0) = 1.0
size = 1
elements = 1
myArray.at(1) = 2.0
size = 2
elements = 2
myArray.at(2) = 4.0
size = 4
elements = 3
myArray.at(3) = 8.0
size = 4
elements = 4
myArray.at(4) = 16.0
size = 8
elements = 5
myArray.at(5) = 32.0
size = 8
elements = 6
myArray.at(6) = 64.0
size = 8
elements = 7
myArray.at(7) = 128.0
size = 8
elements = 8
myArray.at(8) = 256.0
size = 16
elements = 9
myArray.at(9) = 512.0
size = 16
elements = 10
myArray.at(10) = NaN
value = 512.0
size = 16
elements = 9
value = 256.0
size = 16
elements = 8
value = 128.0
size = 8
elements = 7
value = 64.0
size = 8
elements = 6
value = 32.0
size = 8
elements = 5
value = 16.0
size = 8
elements = 4
value = 8.0
size = 4
elements = 3
value = 4.0
size = 4
elements = 2
value = 2.0
size = 2
elements = 1
value = 1.0
size = 1
elements = 0
value = NaN
size = 1
elements = 0
myArray.at(0) = 0.0
size = 1
elements = 1
myArray.at(1) = 3.0
size = 2
elements = 2
myArray.at(2) = 6.0
size = 4
elements = 3
myArray.at(3) = 9.0
size = 4
elements = 4
myArray.at(4) = 12.0
size = 8
elements = 5
array.at(0) = 0.00
array.at(1) = 3.00
array.at(2) = 6.00
array.at(3) = 9.00
array.at(4) = 12.00
value = 6.0
size = 8
elements = 4
array.at(0) = 0.00
array.at(1) = 3.00
array.at(2) = 9.00
array.at(3) = 12.00
value = NaN
size = 8
elements = 4
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.