/*
* Copyright (C) 2007 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package android.text;
import com.android.internal.util.ArrayUtils;
/**
* PackedIntVector stores a two-dimensional array of integers,
* optimized for inserting and deleting rows and for
* offsetting the values in segments of a given column.
*/
class PackedIntVector {
private final int mColumns;
private int mRows;
private int mRowGapStart;
private int mRowGapLength;
private int[] mValues;
private int[] mValueGap; // starts, followed by lengths
/**
* Creates a new PackedIntVector with the specified width and
* a height of 0.
*
* @param columns the width of the PackedIntVector.
*/
public PackedIntVector(int columns) {
mColumns = columns;
mRows = 0;
mRowGapStart = 0;
mRowGapLength = mRows;
mValues = null;
mValueGap = new int[2 * columns];
}
/**
* Returns the value at the specified row and column.
*
* @param row the index of the row to return.
* @param column the index of the column to return.
*
* @return the value stored at the specified position.
*
* @throws IndexOutOfBoundsException if the row is out of range
* (row < 0 || row >= size()) or the column is out of range
* (column < 0 || column >= width()).
*/
public int getValue(int row, int column) {
final int columns = mColumns;
if (((row | column) < 0) || (row >= size()) || (column >= columns)) {
throw new IndexOutOfBoundsException(row + ", " + column);
}
if (row >= mRowGapStart) {
row += mRowGapLength;
}
int value = mValues[row * columns + column];
int[] valuegap = mValueGap;
if (row >= valuegap[column]) {
value += valuegap[column + columns];
}
return value;
}
/**
* Sets the value at the specified row and column.
*
* @param row the index of the row to set.
* @param column the index of the column to set.
*
* @throws IndexOutOfBoundsException if the row is out of range
* (row < 0 || row >= size()) or the column is out of range
* (column < 0 || column >= width()).
*/
public void setValue(int row, int column, int value) {
if (((row | column) < 0) || (row >= size()) || (column >= mColumns)) {
throw new IndexOutOfBoundsException(row + ", " + column);
}
if (row >= mRowGapStart) {
row += mRowGapLength;
}
int[] valuegap = mValueGap;
if (row >= valuegap[column]) {
value -= valuegap[column + mColumns];
}
mValues[row * mColumns + column] = value;
}
/**
* Sets the value at the specified row and column.
* Private internal version: does not check args.
*
* @param row the index of the row to set.
* @param column the index of the column to set.
*
*/
private void setValueInternal(int row, int column, int value) {
if (row >= mRowGapStart) {
row += mRowGapLength;
}
int[] valuegap = mValueGap;
if (row >= valuegap[column]) {
value -= valuegap[column + mColumns];
}
mValues[row * mColumns + column] = value;
}
/**
* Increments all values in the specified column whose row >= the
* specified row by the specified delta.
*
* @param startRow the row at which to begin incrementing.
* This may be == size(), which case there is no effect.
* @param column the index of the column to set.
*
* @throws IndexOutOfBoundsException if the row is out of range
* (startRow < 0 || startRow > size()) or the column
* is out of range (column < 0 || column >= width()).
*/
public void adjustValuesBelow(int startRow, int column, int delta) {
if (((startRow | column) < 0) || (startRow > size()) ||
(column >= width())) {
throw new IndexOutOfBoundsException(startRow + ", " + column);
}
if (startRow >= mRowGapStart) {
startRow += mRowGapLength;
}
moveValueGapTo(column, startRow);
mValueGap[column + mColumns] += delta;
}
/**
* Inserts a new row of values at the specified row offset.
*
* @param row the row above which to insert the new row.
* This may be == size(), which case the new row is added
* at the end.
* @param values the new values to be added. If this is null,
* a row of zeroes is added.
*
* @throws IndexOutOfBoundsException if the row is out of range
* (row < 0 || row > size()) or if the length of the
* values array is too small (values.length < width()).
*/
public void insertAt(int row, int[] values) {
if ((row < 0) || (row > size())) {
throw new IndexOutOfBoundsException("row " + row);
}
if ((values != null) && (values.length < width())) {
throw new IndexOutOfBoundsException("value count " + values.length);
}
moveRowGapTo(row);
if (mRowGapLength == 0) {
growBuffer();
}
mRowGapStart++;
mRowGapLength--;
if (values == null) {
for (int i = mColumns - 1; i >= 0; i--) {
setValueInternal(row, i, 0);
}
} else {
for (int i = mColumns - 1; i >= 0; i--) {
setValueInternal(row, i, values[i]);
}
}
}
/**
* Deletes the specified number of rows starting with the specified
* row.
*
* @param row the index of the first row to be deleted.
* @param count the number of rows to delete.
*
* @throws IndexOutOfBoundsException if any of the rows to be deleted
* are out of range (row < 0 || count < 0 ||
* row + count > size()).
*/
public void deleteAt(int row, int count) {
if (((row | count) < 0) || (row + count > size())) {
throw new IndexOutOfBoundsException(row + ", " + count);
}
moveRowGapTo(row + count);
mRowGapStart -= count;
mRowGapLength += count;
// TODO: Reclaim memory when the new height is much smaller
// than the allocated size.
}
/**
* Returns the number of rows in the PackedIntVector. This number
* will change as rows are inserted and deleted.
*
* @return the number of rows.
*/
public int size() {
return mRows - mRowGapLength;
}
/**
* Returns the width of the PackedIntVector. This number is set
* at construction and will not change.
*
* @return the number of columns.
*/
public int width() {
return mColumns;
}
/**
* Grows the value and gap arrays to be large enough to store at least
* one more than the current number of rows.
*/
private final void growBuffer() {
final int columns = mColumns;
int newsize = size() + 1;
newsize = ArrayUtils.idealIntArraySize(newsize * columns) / columns;
int[] newvalues = new int[newsize * columns];
final int[] valuegap = mValueGap;
final int rowgapstart = mRowGapStart;
int after = mRows - (rowgapstart + mRowGapLength);
if (mValues != null) {
System.arraycopy(mValues, 0, newvalues, 0, columns * rowgapstart);
System.arraycopy(mValues, (mRows - after) * columns,
newvalues, (newsize - after) * columns,
after * columns);
}
for (int i = 0; i < columns; i++) {
if (valuegap[i] >= rowgapstart) {
valuegap[i] += newsize - mRows;
if (valuegap[i] < rowgapstart) {
valuegap[i] = rowgapstart;
}
}
}
mRowGapLength += newsize - mRows;
mRows = newsize;
mValues = newvalues;
}
/**
* Moves the gap in the values of the specified column to begin at
* the specified row.
*/
private final void moveValueGapTo(int column, int where) {
final int[] valuegap = mValueGap;
final int[] values = mValues;
final int columns = mColumns;
if (where == valuegap[column]) {
return;
} else if (where > valuegap[column]) {
for (int i = valuegap[column]; i < where; i++) {
values[i * columns + column] += valuegap[column + columns];
}
} else /* where < valuegap[column] */ {
for (int i = where; i < valuegap[column]; i++) {
values[i * columns + column] -= valuegap[column + columns];
}
}
valuegap[column] = where;
}
/**
* Moves the gap in the row indices to begin at the specified row.
*/
private final void moveRowGapTo(int where) {
if (where == mRowGapStart) {
return;
} else if (where > mRowGapStart) {
int moving = where + mRowGapLength - (mRowGapStart + mRowGapLength);
final int columns = mColumns;
final int[] valuegap = mValueGap;
final int[] values = mValues;
final int gapend = mRowGapStart + mRowGapLength;
for (int i = gapend; i < gapend + moving; i++) {
int destrow = i - gapend + mRowGapStart;
for (int j = 0; j < columns; j++) {
int val = values[i * columns+ j];
if (i >= valuegap[j]) {
val += valuegap[j + columns];
}
if (destrow >= valuegap[j]) {
val -= valuegap[j + columns];
}
values[destrow * columns + j] = val;
}
}
} else /* where < mRowGapStart */ {
int moving = mRowGapStart - where;
final int columns = mColumns;
final int[] valuegap = mValueGap;
final int[] values = mValues;
final int gapend = mRowGapStart + mRowGapLength;
for (int i = where + moving - 1; i >= where; i--) {
int destrow = i - where + gapend - moving;
for (int j = 0; j < columns; j++) {
int val = values[i * columns+ j];
if (i >= valuegap[j]) {
val += valuegap[j + columns];
}
if (destrow >= valuegap[j]) {
val -= valuegap[j + columns];
}
values[destrow * columns + j] = val;
}
}
}
mRowGapStart = where;
}
}
|
