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