false
* if no such mapping has been made.
*/
public boolean get(int row, int col) {
return get(row, col, false);
}
/**
* Gets the boolean mapped from the specified key, or the specified value
* if no such mapping has been made.
*/
public boolean get(int row, int col, boolean valueIfKeyNotFound) {
int r = indexOfKey(row, false);
int c = indexOfKey(col, false);
if (r >= 0 && c >= 0) {
return valueAt(r, c);
} else {
return valueIfKeyNotFound;
}
}
/**
* Adds a mapping from the specified keys to the specified value, replacing the
* previous mapping from the specified keys if there was one.
*/
public void put(int row, int col, boolean value) {
int r = indexOfKey(row);
int c = indexOfKey(col);
if (r < 0 || c < 0) {
// One or both of the keys has not be installed yet. Install them now.
// Installing either key may shift the other key. The safest course is to
// install the keys that are not present and then recompute both indices.
if (r < 0) {
r = indexOfKey(row, true);
}
if (c < 0) {
c = indexOfKey(col, true);
}
r = indexOfKey(row);
c = indexOfKey(col);
}
if (r >= 0 && c >= 0) {
setValueAt(r, c, value);
// setValueAt() will call onChanged().
} else {
throw new RuntimeException("matrix overflow");
}
}
/**
* Removes the mapping from the specified key, if there was any. Note that deletion
* applies to a single index, not to an element. The matrix never shrinks but the
* space will be reused the next time an index is added.
*/
public void deleteKey(int key) {
int i = indexOfKey(key, false);
if (i >= 0) {
removeAt(i);
}
}
/**
* Removes the mapping at the specified index. The matrix does not shrink. This
* throws ArrayIndexOutOfBounds if the index out outside the range {@code 0..size()-1}.
*/
public void removeAt(int index) {
validateIndex(index);
mInUse[mMap[index]] = false;
// Remove the specified index and ensure that unused words in mKeys and mMap are
// always zero, to simplify the equality function.
System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
mKeys[mSize - 1] = 0;
System.arraycopy(mMap, index + 1, mMap, index, mSize - (index + 1));
mMap[mSize - 1] = 0;
mSize--;
onChanged();
}
/**
* Removes all of the mappings whose index is between {@code fromIndex}, inclusive, and
* {@code toIndex}, exclusive. The matrix does not shrink.
*/
public void removeRange(int fromIndex, int toIndex) {
if (toIndex < fromIndex) {
throw new ArrayIndexOutOfBoundsException("toIndex < fromIndex");
}
final int num = toIndex - fromIndex;
if (num == 0) {
return;
}
validateIndex(fromIndex);
validateIndex(toIndex - 1);
for (int i = fromIndex; i < toIndex; i++) {
mInUse[mMap[i]] = false;
}
System.arraycopy(mKeys, toIndex, mKeys, fromIndex, mSize - toIndex);
System.arraycopy(mMap, toIndex, mMap, fromIndex, mSize - toIndex);
for (int i = mSize - num; i < mSize; i++) {
mKeys[i] = 0;
mMap[i] = 0;
}
mSize -= num;
onChanged();
}
/**
* Returns the number of key-value mappings that this WatchedSparseBooleanMatrix
* currently stores.
*/
public int size() {
return mSize;
}
/**
* Removes all key-value mappings from this WatchedSparseBooleanMatrix.
*/
public void clear() {
mSize = 0;
Arrays.fill(mInUse, false);
onChanged();
}
/**
* Given an index in the range 0...size()-1, returns the key from the
* indexth key-value mapping that this WatchedSparseBooleanMatrix 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.
{@link ArrayIndexOutOfBoundsException} is thrown for indices outside of the
* range 0...size()-1
0...size()-1, returns the
* value from the indexth key-value mapping that this WatchedSparseBooleanMatrix
* stores.
*/
public boolean valueAt(int rowIndex, int colIndex) {
validateIndex(rowIndex, colIndex);
int r = mMap[rowIndex];
int c = mMap[colIndex];
return valueAtInternal(r, c);
}
/**
* An internal method to set the boolean value given the mValues row and column
* indices. These are not the indices used by the *At() methods.
*/
private void setValueAtInternal(int row, int col, boolean value) {
int element = row * mOrder + col;
int offset = element / PACKING;
int mask = 1 << (element % PACKING);
if (value) {
mValues[offset] |= mask;
} else {
mValues[offset] &= ~mask;
}
}
/**
* Directly set the value at a particular index.
*/
public void setValueAt(int rowIndex, int colIndex, boolean value) {
validateIndex(rowIndex, colIndex);
int r = mMap[rowIndex];
int c = mMap[colIndex];
setValueAtInternal(r, c, value);
onChanged();
}
/**
* Returns the index for which {@link #keyAt} would return the specified key, or a
* negative number if the specified key is not mapped.
*/
public int indexOfKey(int key) {
return binarySearch(mKeys, mSize, key);
}
/**
* Return true if the matrix knows the user index.
*/
public boolean contains(int key) {
return indexOfKey(key) >= 0;
}
/**
* Fetch the index of a key. If the key does not exist and grow is true, then add the
* key. If the does not exist and grow is false, return -1.
*/
private int indexOfKey(int key, boolean grow) {
int i = binarySearch(mKeys, mSize, key);
if (i < 0 && grow) {
i = ~i;
if (mSize >= mOrder) {
// Preemptively grow the matrix, which also grows the free list.
growMatrix();
}
int newIndex = nextFree(true /* acquire */);
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mMap = GrowingArrayUtils.insert(mMap, mSize, i, newIndex);
mSize++;
// Initialize the row and column corresponding to the new index.
int valueRow = mOrder / PACKING;
int offset = newIndex / PACKING;
int mask = ~(1 << (newIndex % PACKING));
Arrays.fill(mValues, newIndex * valueRow, (newIndex + 1) * valueRow, 0);
for (int n = 0; n < mSize; n++) {
mValues[n * valueRow + offset] &= mask;
}
// Do not report onChanged() from this private method. onChanged() is the
// responsibility of public methods that call this one.
}
return i;
}
/**
* Validate the index. This can throw.
*/
private void validateIndex(int index) {
if (index >= mSize) {
// The array might be slightly bigger than mSize, in which case, indexing won't fail.
throw new ArrayIndexOutOfBoundsException(index);
}
}
/**
* Validate two indices.
*/
private void validateIndex(int row, int col) {
validateIndex(row);
validateIndex(col);
}
/**
* Expand the 2D array. This also extends the free list.
*/
private void growMatrix() {
resizeMatrix(mOrder + STEP);
}
/**
* Resize the values array to the new dimension.
*/
private void resizeMatrix(int newOrder) {
if (newOrder % STEP != 0) {
throw new IllegalArgumentException("matrix order " + newOrder
+ " is not a multiple of " + STEP);
}
int minOrder = Math.min(mOrder, newOrder);
boolean[] newInUse = ArrayUtils.newUnpaddedBooleanArray(newOrder);
System.arraycopy(mInUse, 0, newInUse, 0, minOrder);
int[] newMap = ArrayUtils.newUnpaddedIntArray(newOrder);
System.arraycopy(mMap, 0, newMap, 0, minOrder);
int[] newKeys = ArrayUtils.newUnpaddedIntArray(newOrder);
System.arraycopy(mKeys, 0, newKeys, 0, minOrder);
int[] newValues = ArrayUtils.newUnpaddedIntArray(newOrder * newOrder / PACKING);
for (int i = 0; i < minOrder; i++) {
int row = mOrder * i / PACKING;
int newRow = newOrder * i / PACKING;
System.arraycopy(mValues, row, newValues, newRow, minOrder / PACKING);
}
mInUse = newInUse;
mMap = newMap;
mKeys = newKeys;
mValues = newValues;
mOrder = newOrder;
}
/**
* Find an unused storage index, and return it. Mark it in-use if the {@code acquire} is true.
*/
private int nextFree(boolean acquire) {
for (int i = 0; i < mInUse.length; i++) {
if (!mInUse[i]) {
mInUse[i] = acquire;
return i;
}
}
throw new RuntimeException();
}
/**
* Return the index of the key that uses the highest row index in use. This returns
* -1 if the matrix is empty. Note that the return is an index suitable for the *At()
* methods. It is not the index in the mInUse array.
*/
private int lastInuse() {
for (int i = mOrder - 1; i >= 0; i--) {
if (mInUse[i]) {
for (int j = 0; j < mSize; j++) {
if (mMap[j] == i) {
return j;
}
}
throw new IndexOutOfBoundsException();
}
}
return -1;
}
/**
* Compress the matrix by packing keys into consecutive indices. If the compression
* is sufficient, the mValues array can be shrunk.
*/
private void pack() {
if (mSize == 0 || mSize == mOrder) {
return;
}
// dst and src are identify raw (row, col) in mValues. srcIndex is the index (as
// in the result of keyAt()) of the key being relocated.
for (int dst = nextFree(false); dst < mSize; dst = nextFree(false)) {
mInUse[dst] = true;
int srcIndex = lastInuse();
int src = mMap[srcIndex];
mInUse[src] = false;
mMap[srcIndex] = dst;
System.arraycopy(mValues, src * mOrder / PACKING,
mValues, dst * mOrder / PACKING,
mOrder / PACKING);
int srcOffset = (src / PACKING);
int srcMask = 1 << (src % PACKING);
int dstOffset = (dst / PACKING);
int dstMask = 1 << (dst % PACKING);
for (int i = 0; i < mOrder; i++) {
if ((mValues[srcOffset] & srcMask) == 0) {
mValues[dstOffset] &= ~dstMask;
} else {
mValues[dstOffset] |= dstMask;
}
srcOffset += mOrder / PACKING;
dstOffset += mOrder / PACKING;
}
}
}
/**
* Shrink the matrix, if possible.
*/
public void compact() {
pack();
int unused = (mOrder - mSize) / STEP;
if (unused > 0) {
resizeMatrix(mOrder - (unused * STEP));
}
}
/**
* Return a copy of the keys that are in use by the matrix.
*/
public int[] keys() {
return Arrays.copyOf(mKeys, mSize);
}
/**
* Return the size of the 2D matrix. This is always greater than or equal to size().
* This does not reflect the sizes of the meta-information arrays (such as mKeys).
*/
public int capacity() {
return mOrder;
}
/**
* Set capacity to enlarge the size of the 2D matrix. Capacity less than the {@link #capacity()}
* is not supported.
*/
public void setCapacity(int capacity) {
if (capacity <= mOrder) {
return;
}
if (capacity % STEP != 0) {
capacity = ((capacity / STEP) + 1) * STEP;
}
resizeMatrix(capacity);
}
/**
* {@inheritDoc}
*/
@Override
public int hashCode() {
int hashCode = mSize;
hashCode = 31 * hashCode + Arrays.hashCode(mKeys);
hashCode = 31 * hashCode + Arrays.hashCode(mMap);
for (int i = 0; i < mSize; i++) {
int row = mMap[i];
for (int j = 0; j < mSize; j++) {
hashCode = 31 * hashCode + (valueAtInternal(row, mMap[j]) ? 1 : 0);
}
}
return hashCode;
}
/**
* {@inheritDoc}
*/
@Override
public boolean equals(@Nullable Object that) {
if (this == that) {
return true;
}
if (!(that instanceof WatchedSparseBooleanMatrix)) {
return false;
}
WatchedSparseBooleanMatrix other = (WatchedSparseBooleanMatrix) that;
if (mSize != other.mSize) {
return false;
}
if (!Arrays.equals(mKeys, other.mKeys)) {
// mKeys is zero padded at the end and is sorted, so the arrays can always be
// directly compared.
return false;
}
for (int i = 0; i < mSize; i++) {
int row = mMap[i];
for (int j = 0; j < mSize; j++) {
int col = mMap[j];
if (valueAtInternal(row, col) != other.valueAtInternal(row, col)) {
return false;
}
}
}
return true;
}
/**
* Return the matrix meta information. This is always three strings long. The
* strings are indexed by the constants STRING_KEY_INDEX, STRING_MAP_INDEX, and
* STRING_INUSE_INDEX.
*/
@VisibleForTesting(visibility = PRIVATE)
@Size(3) String[] matrixToStringMeta() {
String[] result = new String[3];
StringBuilder k = new StringBuilder();
for (int i = 0; i < mSize; i++) {
k.append(mKeys[i]);
if (i < mSize - 1) {
k.append(" ");
}
}
result[STRING_KEY_INDEX] = k.substring(0);
StringBuilder m = new StringBuilder();
for (int i = 0; i < mSize; i++) {
m.append(mMap[i]);
if (i < mSize - 1) {
m.append(" ");
}
}
result[STRING_MAP_INDEX] = m.substring(0);
StringBuilder u = new StringBuilder();
for (int i = 0; i < mOrder; i++) {
u.append(mInUse[i] ? "1" : "0");
}
result[STRING_INUSE_INDEX] = u.substring(0);
return result;
}
/**
* Return the matrix as an array of strings. There is one string per row. Each
* string has a '1' or a '0' in the proper column. This is the raw data indexed by
* row/column disregarding the key map.
*/
@VisibleForTesting(visibility = PRIVATE)
String[] matrixToStringRaw() {
String[] result = new String[mOrder];
for (int i = 0; i < mOrder; i++) {
StringBuilder line = new StringBuilder(mOrder);
for (int j = 0; j < mOrder; j++) {
line.append(valueAtInternal(i, j) ? "1" : "0");
}
result[i] = line.substring(0);
}
return result;
}
/**
* Return the matrix as an array of strings. There is one string per row. Each
* string has a '1' or a '0' in the proper column. This is the cooked data indexed by
* keys, in key order.
*/
@VisibleForTesting(visibility = PRIVATE)
String[] matrixToStringCooked() {
String[] result = new String[mSize];
for (int i = 0; i < mSize; i++) {
int row = mMap[i];
StringBuilder line = new StringBuilder(mSize);
for (int j = 0; j < mSize; j++) {
line.append(valueAtInternal(row, mMap[j]) ? "1" : "0");
}
result[i] = line.substring(0);
}
return result;
}
public String[] matrixToString(boolean raw) {
String[] meta = matrixToStringMeta();
String[] data;
if (raw) {
data = matrixToStringRaw();
} else {
data = matrixToStringCooked();
}
String[] result = new String[meta.length + data.length];
System.arraycopy(meta, 0, result, 0, meta.length);
System.arraycopy(data, 0, result, meta.length, data.length);
return result;
}
/**
* {@inheritDoc}
*
* This implementation creates a string that describes the size of the array. A * string with all the values could easily exceed 1Mb. */ @Override public String toString() { return "{" + mSize + "x" + mSize + "}"; } // Copied from android.util.ContainerHelpers, which is not visible outside the // android.util package. private static int binarySearch(int[] array, int size, int value) { int lo = 0; int hi = size - 1; while (lo <= hi) { final int mid = (lo + hi) >>> 1; final int midVal = array[mid]; if (midVal < value) { lo = mid + 1; } else if (midVal > value) { hi = mid - 1; } else { return mid; // value found } } return ~lo; // value not present } }