* 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).
*
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.
*/
public int get(int key, int valueIfKeyNotFound)
{
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i < 0)
{
return valueIfKeyNotFound;
}
else
{
return mValues[i];
}
}
/**
* Removes the mapping from the specified key, if there was any.
*/
public void delete(int key)
{
int i = ContainerHelpers.binarySearch(mKeys, mSize, 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.
*/
public void put(int key, int value)
{
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0)
{
mValues[i] = value;
}
else
{
i = ~i;
if (mSize >= mKeys.length)
{
int n = idealIntArraySize(mSize + 1);
int[] nkeys = new int[n];
int[] nvalues = new int[n];
// Log.e("SparseIntArray", "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("SparseIntArray", "move " + (mSize - i));
System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
}
mKeys[i] = key;
mValues[i] = value;
mSize++;
}
}
/**
* Returns the number of key-value mappings that this SparseIntArray 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 SparseIntArray 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 SparseIntArray
* 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 * @throw ArithmeticException if the result would exceed the maximum value of * an int */ public int add(int key, int toAdd) { int newValue = toAdd; int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { checkOverflow(mValues[i], toAdd); mValues[i] += toAdd; newValue = mValues[i]; } else { i = ~i; if (mSize >= mKeys.length) { int n = idealIntArraySize(mSize + 1); int[] nkeys = new int[n]; int[] nvalues = new int[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] = key; mValues[i] = toAdd; mSize++; } return newValue; } /** * Throws ArithmeticException if adding addend to value would exceed the range * of int * * @param value * @param addend */ static void checkOverflow(int value, int addend) { /* * test cases being careful to avoid overflow while testing! */ if (addend > 0) { if (value > 0 && Integer.MAX_VALUE - value < addend) { throw new ArithmeticException("Integer overflow adding " + addend + " to " + value); } } else if (addend < 0) { if (value < 0 && Integer.MIN_VALUE - value > addend) { throw new ArithmeticException("Integer underflow adding " + addend + " to " + value); } } } }