1 /* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.text; 18 19 import com.android.internal.annotations.VisibleForTesting; 20 import com.android.internal.util.ArrayUtils; 21 import com.android.internal.util.GrowingArrayUtils; 22 23 24 /** 25 * PackedIntVector stores a two-dimensional array of integers, 26 * optimized for inserting and deleting rows and for 27 * offsetting the values in segments of a given column. 28 * 29 * @hide 30 */ 31 @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE) 32 public class PackedIntVector { 33 private final int mColumns; 34 private int mRows; 35 36 private int mRowGapStart; 37 private int mRowGapLength; 38 39 private int[] mValues; 40 private int[] mValueGap; // starts, followed by lengths 41 42 /** 43 * Creates a new PackedIntVector with the specified width and 44 * a height of 0. 45 * 46 * @param columns the width of the PackedIntVector. 47 */ 48 public PackedIntVector(int columns) { 49 mColumns = columns; 50 mRows = 0; 51 52 mRowGapStart = 0; 53 mRowGapLength = mRows; 54 55 mValues = null; 56 mValueGap = new int[2 * columns]; 57 } 58 59 /** 60 * Returns the value at the specified row and column. 61 * 62 * @param row the index of the row to return. 63 * @param column the index of the column to return. 64 * 65 * @return the value stored at the specified position. 66 * 67 * @throws IndexOutOfBoundsException if the row is out of range 68 * (row < 0 || row >= size()) or the column is out of range 69 * (column < 0 || column >= width()). 70 */ 71 public int getValue(int row, int column) { 72 final int columns = mColumns; 73 74 if (((row | column) < 0) || (row >= size()) || (column >= columns)) { 75 throw new IndexOutOfBoundsException(row + ", " + column); 76 } 77 78 if (row >= mRowGapStart) { 79 row += mRowGapLength; 80 } 81 82 int value = mValues[row * columns + column]; 83 84 int[] valuegap = mValueGap; 85 if (row >= valuegap[column]) { 86 value += valuegap[column + columns]; 87 } 88 89 return value; 90 } 91 92 /** 93 * Sets the value at the specified row and column. 94 * 95 * @param row the index of the row to set. 96 * @param column the index of the column to set. 97 * 98 * @throws IndexOutOfBoundsException if the row is out of range 99 * (row < 0 || row >= size()) or the column is out of range 100 * (column < 0 || column >= width()). 101 */ 102 public void setValue(int row, int column, int value) { 103 if (((row | column) < 0) || (row >= size()) || (column >= mColumns)) { 104 throw new IndexOutOfBoundsException(row + ", " + column); 105 } 106 107 if (row >= mRowGapStart) { 108 row += mRowGapLength; 109 } 110 111 int[] valuegap = mValueGap; 112 if (row >= valuegap[column]) { 113 value -= valuegap[column + mColumns]; 114 } 115 116 mValues[row * mColumns + column] = value; 117 } 118 119 /** 120 * Sets the value at the specified row and column. 121 * Private internal version: does not check args. 122 * 123 * @param row the index of the row to set. 124 * @param column the index of the column to set. 125 * 126 */ 127 private void setValueInternal(int row, int column, int value) { 128 if (row >= mRowGapStart) { 129 row += mRowGapLength; 130 } 131 132 int[] valuegap = mValueGap; 133 if (row >= valuegap[column]) { 134 value -= valuegap[column + mColumns]; 135 } 136 137 mValues[row * mColumns + column] = value; 138 } 139 140 141 /** 142 * Increments all values in the specified column whose row >= the 143 * specified row by the specified delta. 144 * 145 * @param startRow the row at which to begin incrementing. 146 * This may be == size(), which case there is no effect. 147 * @param column the index of the column to set. 148 * 149 * @throws IndexOutOfBoundsException if the row is out of range 150 * (startRow < 0 || startRow > size()) or the column 151 * is out of range (column < 0 || column >= width()). 152 */ 153 public void adjustValuesBelow(int startRow, int column, int delta) { 154 if (((startRow | column) < 0) || (startRow > size()) || 155 (column >= width())) { 156 throw new IndexOutOfBoundsException(startRow + ", " + column); 157 } 158 159 if (startRow >= mRowGapStart) { 160 startRow += mRowGapLength; 161 } 162 163 moveValueGapTo(column, startRow); 164 mValueGap[column + mColumns] += delta; 165 } 166 167 /** 168 * Inserts a new row of values at the specified row offset. 169 * 170 * @param row the row above which to insert the new row. 171 * This may be == size(), which case the new row is added 172 * at the end. 173 * @param values the new values to be added. If this is null, 174 * a row of zeroes is added. 175 * 176 * @throws IndexOutOfBoundsException if the row is out of range 177 * (row < 0 || row > size()) or if the length of the 178 * values array is too small (values.length < width()). 179 */ 180 public void insertAt(int row, int[] values) { 181 if ((row < 0) || (row > size())) { 182 throw new IndexOutOfBoundsException("row " + row); 183 } 184 185 if ((values != null) && (values.length < width())) { 186 throw new IndexOutOfBoundsException("value count " + values.length); 187 } 188 189 moveRowGapTo(row); 190 191 if (mRowGapLength == 0) { 192 growBuffer(); 193 } 194 195 mRowGapStart++; 196 mRowGapLength--; 197 198 if (values == null) { 199 for (int i = mColumns - 1; i >= 0; i--) { 200 setValueInternal(row, i, 0); 201 } 202 } else { 203 for (int i = mColumns - 1; i >= 0; i--) { 204 setValueInternal(row, i, values[i]); 205 } 206 } 207 } 208 209 /** 210 * Deletes the specified number of rows starting with the specified 211 * row. 212 * 213 * @param row the index of the first row to be deleted. 214 * @param count the number of rows to delete. 215 * 216 * @throws IndexOutOfBoundsException if any of the rows to be deleted 217 * are out of range (row < 0 || count < 0 || 218 * row + count > size()). 219 */ 220 public void deleteAt(int row, int count) { 221 if (((row | count) < 0) || (row + count > size())) { 222 throw new IndexOutOfBoundsException(row + ", " + count); 223 } 224 225 moveRowGapTo(row + count); 226 227 mRowGapStart -= count; 228 mRowGapLength += count; 229 230 // TODO: Reclaim memory when the new height is much smaller 231 // than the allocated size. 232 } 233 234 /** 235 * Returns the number of rows in the PackedIntVector. This number 236 * will change as rows are inserted and deleted. 237 * 238 * @return the number of rows. 239 */ 240 public int size() { 241 return mRows - mRowGapLength; 242 } 243 244 /** 245 * Returns the width of the PackedIntVector. This number is set 246 * at construction and will not change. 247 * 248 * @return the number of columns. 249 */ 250 public int width() { 251 return mColumns; 252 } 253 254 /** 255 * Grows the value and gap arrays to be large enough to store at least 256 * one more than the current number of rows. 257 */ 258 private final void growBuffer() { 259 final int columns = mColumns; 260 int[] newvalues = ArrayUtils.newUnpaddedIntArray( 261 GrowingArrayUtils.growSize(size()) * columns); 262 int newsize = newvalues.length / columns; 263 264 final int[] valuegap = mValueGap; 265 final int rowgapstart = mRowGapStart; 266 267 int after = mRows - (rowgapstart + mRowGapLength); 268 269 if (mValues != null) { 270 System.arraycopy(mValues, 0, newvalues, 0, columns * rowgapstart); 271 System.arraycopy(mValues, (mRows - after) * columns, 272 newvalues, (newsize - after) * columns, 273 after * columns); 274 } 275 276 for (int i = 0; i < columns; i++) { 277 if (valuegap[i] >= rowgapstart) { 278 valuegap[i] += newsize - mRows; 279 280 if (valuegap[i] < rowgapstart) { 281 valuegap[i] = rowgapstart; 282 } 283 } 284 } 285 286 mRowGapLength += newsize - mRows; 287 mRows = newsize; 288 mValues = newvalues; 289 } 290 291 /** 292 * Moves the gap in the values of the specified column to begin at 293 * the specified row. 294 */ 295 private final void moveValueGapTo(int column, int where) { 296 final int[] valuegap = mValueGap; 297 final int[] values = mValues; 298 final int columns = mColumns; 299 300 if (where == valuegap[column]) { 301 return; 302 } else if (where > valuegap[column]) { 303 for (int i = valuegap[column]; i < where; i++) { 304 values[i * columns + column] += valuegap[column + columns]; 305 } 306 } else /* where < valuegap[column] */ { 307 for (int i = where; i < valuegap[column]; i++) { 308 values[i * columns + column] -= valuegap[column + columns]; 309 } 310 } 311 312 valuegap[column] = where; 313 } 314 315 /** 316 * Moves the gap in the row indices to begin at the specified row. 317 */ 318 private final void moveRowGapTo(int where) { 319 if (where == mRowGapStart) { 320 return; 321 } else if (where > mRowGapStart) { 322 int moving = where + mRowGapLength - (mRowGapStart + mRowGapLength); 323 final int columns = mColumns; 324 final int[] valuegap = mValueGap; 325 final int[] values = mValues; 326 final int gapend = mRowGapStart + mRowGapLength; 327 328 for (int i = gapend; i < gapend + moving; i++) { 329 int destrow = i - gapend + mRowGapStart; 330 331 for (int j = 0; j < columns; j++) { 332 int val = values[i * columns+ j]; 333 334 if (i >= valuegap[j]) { 335 val += valuegap[j + columns]; 336 } 337 338 if (destrow >= valuegap[j]) { 339 val -= valuegap[j + columns]; 340 } 341 342 values[destrow * columns + j] = val; 343 } 344 } 345 } else /* where < mRowGapStart */ { 346 int moving = mRowGapStart - where; 347 final int columns = mColumns; 348 final int[] valuegap = mValueGap; 349 final int[] values = mValues; 350 final int gapend = mRowGapStart + mRowGapLength; 351 352 for (int i = where + moving - 1; i >= where; i--) { 353 int destrow = i - where + gapend - moving; 354 355 for (int j = 0; j < columns; j++) { 356 int val = values[i * columns+ j]; 357 358 if (i >= valuegap[j]) { 359 val += valuegap[j + columns]; 360 } 361 362 if (destrow >= valuegap[j]) { 363 val -= valuegap[j + columns]; 364 } 365 366 values[destrow * columns + j] = val; 367 } 368 } 369 } 370 371 mRowGapStart = where; 372 } 373 } 374
