Name:
Date: Sep 8, 2005
Given below is a Java class SmartArray which implements an array with additional features including the ability to dynamically resize. The field maxCapacity specifies the current capacity of the array and nElems specifies the number of elements stored in the array. The insert method expands the SmartArray by doubling the capacity when it becomes full. The delete method shrinks SmartArray when nElems is less than half of the capacity. This is done to ensure that at least 50\% of the memory allocated for the array is always being used. Therefore, the class SmartArray always makes sure the following condition is satisfied:
nElems <= maxCapacity <= 2*nElems (*)
What to submit: Write a resize method which takes an int argument called curCapacity. This method creates a new array with the specified capacity and containing existing array elements. The method insert and delete call resize when the condition above (*) is not satisfied.
public class SmartArray
{
private long[] a = null; // reference to the array
private int nElems = 0; // number of data items
private int maxCapacity = 0; // capacity of the array
public void insert(long value)
{
if(nElems < maxCapacity)
{
a[nElems] = value;
nElems++;
}
else
{
//expand the capacity
if(maxCapacity == 0)
maxCapacity = 1;
else
maxCapacity *= 2;
resize(maxCapacity);
a[nElems] = value;
nElems++;
}
} // End of insert
public void delete(long value)
{
int i;
for(i = 0; i < nElems; i++) // search for the item equal to value
{
if(a[i] == value)
break;
}
if(i < nElems) // a[i] is found equal to value
{
for(int j = i+1; j < nElems; j++) // move elements behind a[i] to the left
a[j-1] = a[j];
nElems--;
if(nElems*2 < maxCapacity)
{
// shrink the capacity
maxCapacity = nElems*2;
resize(maxCapacity);
}
} // End of if(i < nElems)
} // End of delete
private void resize(int curCapacity)
{
// Write your code here
// Create a new array with specified capacity
long[] b = new long[curCapacity];
// Copy elements in "a" into the new array "b"
for(int i = 0; i < nElems; i++);
{
b[i] = a[i];
}
// Let a refer to the new array. Thus the old array is deallocated automatically by garbage collection.
a = b;
} // End of resize
} // End of class SmartArray