* Note that this container keeps its mappings in an array data structure, using * a binary search to find keys. The implementation is not intended to be * appropriate for data structures that may contain large numbers of items. It * is generally slower than a traditional HashMap, since lookups require a * binary search and adds and removes require inserting and deleting entries in * the array. For containers holding up to hundreds of items, the performance * difference is not significant, less than 50%. *
* *
* It is possible to iterate over the items in this container using
* {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
* keyAt(int) with ascending values of the index will return the
* keys in ascending order, or the values corresponding to the keys in ascending
* order in the case of valueAt(int).
*
* Note that operations append, put, add throw ArithmeticException if either the
* key or the resulting value overflows the range of a short. Calling code
* should trap and handle this, for example by switching to using a
* SparseIntArray instead.
*/
public class SparseShortArray implements Cloneable
{
private short[] mKeys;
private short[] mValues;
private int mSize;
/**
* Creates a new SparseShortArray containing no mappings.
*/
public SparseShortArray()
{
this(10);
}
/**
* Creates a new SparseShortArray containing no mappings that will not require
* any additional memory allocation to store the specified number of mappings.
* If you supply an initial capacity of 0, the sparse array will be
* initialized with a light-weight representation not requiring any additional
* array allocations.
*/
public SparseShortArray(int initialCapacity)
{
if (initialCapacity == 0)
{
mKeys = new short[0];
mValues = new short[0];
}
else
{
initialCapacity = idealShortArraySize(initialCapacity);
mKeys = new short[initialCapacity];
mValues = new short[initialCapacity];
}
mSize = 0;
}
@Override
public SparseShortArray clone()
{
SparseShortArray clone = null;
try
{
clone = (SparseShortArray) super.clone();
clone.mKeys = mKeys.clone();
clone.mValues = mValues.clone();
} catch (CloneNotSupportedException cnse)
{
/* ignore */
}
return clone;
}
/**
* Gets the int mapped from the specified key, or 0 if no such
* mapping has been made.
*/
public int get(int key)
{
return get(key, 0);
}
/**
* Gets the int mapped from the specified key, or the specified value if no
* such mapping has been made.
*
* @throws ArithmeticException
* if key is outside the range of a short value
*/
public int get(int key, int valueIfKeyNotFound)
{
checkOverflow(key);
int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key);
if (i < 0)
{
return valueIfKeyNotFound;
}
else
{
return mValues[i];
}
}
/**
* Removes the mapping from the specified key, if there was any.
*
* @throws ArithmeticException
* if key is outside the range of a short value
*/
public void delete(int key)
{
checkOverflow(key);
int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key);
if (i >= 0)
{
removeAt(i);
}
}
/**
* Removes the mapping at the given index.
*/
public void removeAt(int index)
{
System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
System.arraycopy(mValues, index + 1, mValues, index,
mSize - (index + 1));
mSize--;
}
/**
* Adds a mapping from the specified key to the specified value, replacing the
* previous mapping from the specified key if there was one.
*
* @throws ArithmeticException
* if either argument is outside the range of a short value
*/
public void put(int key, int value)
{
checkOverflow(key);
checkOverflow(value);
int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key);
if (i >= 0)
{
mValues[i] = (short) value;
}
else
{
i = ~i;
if (mSize >= mKeys.length)
{
int n = idealShortArraySize(mSize + 1);
short[] nkeys = new short[n];
short[] nvalues = new short[n];
// Log.e("SparseShortArray", "grow " + mKeys.length + " to " + n);
System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
mKeys = nkeys;
mValues = nvalues;
}
if (mSize - i != 0)
{
// Log.e("SparseShortArray", "move " + (mSize - i));
System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
}
mKeys[i] = (short) key;
mValues[i] = (short) value;
mSize++;
}
}
/**
* Returns the number of key-value mappings that this SparseShortArray
* currently stores.
*/
public int size()
{
return mSize;
}
/**
* Given an index in the range 0...size()-1, returns the key from
* the indexth key-value mapping that this SparseShortArray
* stores.
*
*
* The keys corresponding to indices in ascending order are guaranteed to be
* in ascending order, e.g., keyAt(0) will return the smallest
* key and keyAt(size()-1) will return the largest key.
*
0...size()-1, returns the value
* from the indexth key-value mapping that this SparseShortArray
* stores.
*
*
* The values corresponding to indices in ascending order are guaranteed to be
* associated with keys in ascending order, e.g., valueAt(0) will
* return the value associated with the smallest key and
* valueAt(size()-1) will return the value associated with the
* largest key.
*
* This implementation composes a string by iterating over its mappings. */ @Override public String toString() { if (size() <= 0) { return "{}"; } StringBuilder buffer = new StringBuilder(mSize * 28); buffer.append('{'); for (int i = 0; i < mSize; i++) { if (i > 0) { buffer.append(", "); } int key = keyAt(i); buffer.append(key); buffer.append('='); int value = valueAt(i); buffer.append(value); } buffer.append('}'); return buffer.toString(); } /** * Method (copied from put) added for Jalview to efficiently increment a key's * value if present, else add it with the given value. This avoids a double * binary search (once to get the value, again to put the updated value). * * @param key * @oparam toAdd * @return the new value of the count for the key * @throws ArithmeticException * if key, or result of adding toAdd, is outside the range of a * short value */ public int add(int key, int toAdd) { int newValue = toAdd; checkOverflow(key); int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key); if (i >= 0) { checkOverflow(toAdd + mValues[i]); mValues[i] += (short) toAdd; newValue = mValues[i]; } else { checkOverflow(toAdd); i = ~i; if (mSize >= mKeys.length) { int n = idealShortArraySize(mSize + 1); short[] nkeys = new short[n]; short[] nvalues = new short[n]; System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); System.arraycopy(mValues, 0, nvalues, 0, mValues.length); mKeys = nkeys; mValues = nvalues; } if (mSize - i != 0) { System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); System.arraycopy(mValues, i, mValues, i + 1, mSize - i); } mKeys[i] = (short) key; mValues[i] = (short) toAdd; mSize++; } return newValue; } }