There are many data structures that handle this...
I would say the best way would be to keep an int value index for each element of the array, so that when an element is added the int value is increased or when an element is removed it is de-incremented.
Then you would make a trim to size method that would create a new array and copy the data via System.arraycopy
Then you change the pointer to the new array.
Other than that you would have to check the array for each value to see where the first null occurance is (which would not work if things were removed from area's in the middle, and then would cause much more programming problems).
You may want to make this work better by using an ObjectBag, with predefined methods for trim to size and the like.
I have an ObjectBag that is not a double level array but I think you might be able to modify it for your purposes.
code:
package edu.colorado.collections;
public class ArrayBag implements Cloneable
{
private Object[] data;
private int manyItems;
public ArrayBag()
{
final int INITIAL_CAPACITY = 10;
manyItems = 0;
data = new Object[INITIAL_CAPACITY];
}
public ArrayBag(int initialCapacity)
{
if (initialCapacity < 0)
{
throw new IllegalArgumentException
("initialCapacity is negitive: " + initialCapacity);
}
manyItems = 0;
data = new Object[initialCapacity];
}
public void add(Object element)
{
if (manyItems == data.length)
{
// Double the capacity and add 1; this works even if manyItems is 0. However, in
// case that manyItems*2 + 1 is beyond Integer.MAX_VALUE, there will be an
// arithmetic overflow and the bag will fail.
ensureCapacity(manyItems*2 + 1);
}
data[manyItems] = element;
manyItems++;
}
public void addAll(ArrayBag addend)
{
// If addend is null, then a NullPointerException is thrown.
// In the case that the total number of items is beyond Integer.MAX_VALUE, there will
// be an arithmetic overflow and the bag will fail.
ensureCapacity(manyItems + addend.manyItems);
System.arraycopy(addend.data, 0, data, manyItems, addend.manyItems);
manyItems += addend.manyItems;
}
public Object clone()
{ // Clone an ArrayBag
ArrayBag answer;
try
{
answer = (ArrayBag) super.clone();
}
catch (CloneNotSupportedException e)
{
// This exception should not ocucur. But if it does, it would probabally indicate a
// programming error that made super.clone unavailable.
// The most common error would be forgetting the "Implements Colneable"
// clause at the start of this class.
throw new RuntimeException
("This class does not implement Cloneable");
}
answer.data = (Object[]) data.clone();
return answer;
}
public int countOccurrences(Object target)
{
int answer;
int index;
answer = 0;
if (target == null)
{ // Count how many times null appears in the bag.
for (index = 0; index < manyItems; index++)
{
if (data[index] == null)
{
answer++;
}
}
}
else
{ // Use target.equals to determine how many times the target appears.
for (index = 0; index < manyItems; index++)
{
if (target.equals(data[index]))
{
answer++;
}
}
}
return answer;
}
public void ensureCapacity(int minimumCapacity)
{
Object biggerArray[];
if (data.length < minimumCapacity)
{
biggerArray = new Object[minimumCapacity];
System.arraycopy(data, 0, biggerArray, 0, manyItems);
data = biggerArray;
}
}
public int getCapacity()
{
return data.length;
}
public Object grab()
{
int i;
if (manyItems == 0)
{
throw new IllegalStateException("Bag size is zero.");
}
i = (int) (Math.random() * manyItems); // From - to manyItems-1
return data[i];
}
public boolean remove(Object target)
{
int index; // The location of target in the data array
// First, set index to the location of target in the data array,
// which could be as small as - or as large as manyItems-1/
// If target is not in the array, the index will be set equal to manyItems.
if (target == null)
{ // Find the first occurrence of the null reference in the bag.
for (index = 0; (index < manyItems) && (data[index] != null); index++)
// No work is needed in the body of this for-loop
;
}
else
{ // Use target.equals to find the first occurrence of the target.
for (index = 0; (index < manyItems) && (!target.equals(data[index])); index++)
// No work is needed in the body of this for-loop.
;
}
if (index == manyItems)
{
// The target was not found, so nothing is removed.
return false;
}
else
{ // The target was found at data[index]
manyItems--;
data[index] = data[manyItems];
return true;
}
}
public int size()
{
return manyItems;
}
public void trimToSize()
{
Object trimmedArray[];
if (data.length != manyItems)
{
trimmedArray = new Object[manyItems];
System.arraycopy(data, 0, trimmedArray, 0, manyItems);
data = trimmedArray;
}
}
public static ArrayBag union(ArrayBag b1, ArrayBag b2)
{
// If either b1 or b2 is null, then a NullPointerException is thrown.
// In the case total number of items is beyond Integer.MAX_VALUE, there will
// be an arithmetic overflow and the bag will fail.
ArrayBag answer = new ArrayBag(b1.getCapacity() + b2.getCapacity());
System.arraycopy(b1.data, 0, answer.data, 0, b1.manyItems);
System.arraycopy(b2.data, 0, answer.data, b1.manyItems, b2.manyItems);
answer.manyItems = b1.manyItems + b2.manyItems;
return answer;
}
}
Good luck with it, i didn't write this bag, only modified it to work with objects instead of primitives, this is by Michael Main and from Data Structures & Other Objects Using Java.
-mage-
[This message has been edited by WarMage (edited 05-01-2001).]
posted 05-01-2001 06:14
