* 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 double get(int key)
{
return get(key, 0d);
}
/**
* Gets the int mapped from the specified key, or the specified value if no
* such mapping has been made.
*/
public double get(int key, double 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, double value)
{
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0)
{
mValues[i] = value;
}
else
{
i = ~i;
if (mSize >= mKeys.length)
{
int n = idealDoubleArraySize(mSize + 1);
int[] nkeys = new int[n];
double[] nvalues = new double[n];
// Log.e("SparseDoubleArray", "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("SparseDoubleArray", "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 SparseDoubleArray
* 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 SparseDoubleArray
* 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 SparseDoubleArray
* 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('='); double 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 for the key */ public double add(int key, double toAdd) { double newValue = toAdd; int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] += toAdd; newValue = mValues[i]; } else { i = ~i; if (mSize >= mKeys.length) { int n = idealDoubleArraySize(mSize + 1); int[] nkeys = new int[n]; double[] nvalues = new double[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; } /** * Method added for Jalview to efficiently multiply a key's value if present, * else do nothing. 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 for the key */ public double divide(int key, double divisor) { double newValue = 0d; if (divisor == 0d) { return newValue; } int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] /= divisor; newValue = mValues[i]; } return newValue; } }