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