J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 1999-2006 Sun Microsystems, Inc. All Rights Reserved. |
| 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 | * |
| 5 | * This code is free software; you can redistribute it and/or modify it |
| 6 | * under the terms of the GNU General Public License version 2 only, as |
| 7 | * published by the Free Software Foundation. Sun designates this |
| 8 | * particular file as subject to the "Classpath" exception as provided |
| 9 | * by Sun in the LICENSE file that accompanied this code. |
| 10 | * |
| 11 | * This code is distributed in the hope that it will be useful, but WITHOUT |
| 12 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 13 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 14 | * version 2 for more details (a copy is included in the LICENSE file that |
| 15 | * accompanied this code). |
| 16 | * |
| 17 | * You should have received a copy of the GNU General Public License version |
| 18 | * 2 along with this work; if not, write to the Free Software Foundation, |
| 19 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| 20 | * |
| 21 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 | * have any questions. |
| 24 | */ |
| 25 | |
| 26 | package javax.swing; |
| 27 | |
| 28 | /** |
| 29 | * A <code>SizeSequence</code> object |
| 30 | * efficiently maintains an ordered list |
| 31 | * of sizes and corresponding positions. |
| 32 | * One situation for which <code>SizeSequence</code> |
| 33 | * might be appropriate is in a component |
| 34 | * that displays multiple rows of unequal size. |
| 35 | * In this case, a single <code>SizeSequence</code> |
| 36 | * object could be used to track the heights |
| 37 | * and Y positions of all rows. |
| 38 | * <p> |
| 39 | * Another example would be a multi-column component, |
| 40 | * such as a <code>JTable</code>, |
| 41 | * in which the column sizes are not all equal. |
| 42 | * The <code>JTable</code> might use a single |
| 43 | * <code>SizeSequence</code> object |
| 44 | * to store the widths and X positions of all the columns. |
| 45 | * The <code>JTable</code> could then use the |
| 46 | * <code>SizeSequence</code> object |
| 47 | * to find the column corresponding to a certain position. |
| 48 | * The <code>JTable</code> could update the |
| 49 | * <code>SizeSequence</code> object |
| 50 | * whenever one or more column sizes changed. |
| 51 | * |
| 52 | * <p> |
| 53 | * The following figure shows the relationship between size and position data |
| 54 | * for a multi-column component. |
| 55 | * <p> |
| 56 | * <center> |
| 57 | * <img src="doc-files/SizeSequence-1.gif" width=384 height = 100 |
| 58 | * alt="The first item begins at position 0, the second at the position equal |
| 59 | to the size of the previous item, and so on."> |
| 60 | * </center> |
| 61 | * <p> |
| 62 | * In the figure, the first index (0) corresponds to the first column, |
| 63 | * the second index (1) to the second column, and so on. |
| 64 | * The first column's position starts at 0, |
| 65 | * and the column occupies <em>size<sub>0</sub></em> pixels, |
| 66 | * where <em>size<sub>0</sub></em> is the value returned by |
| 67 | * <code>getSize(0)</code>. |
| 68 | * Thus, the first column ends at <em>size<sub>0</sub></em> - 1. |
| 69 | * The second column then begins at |
| 70 | * the position <em>size<sub>0</sub></em> |
| 71 | * and occupies <em>size<sub>1</sub></em> (<code>getSize(1)</code>) pixels. |
| 72 | * <p> |
| 73 | * Note that a <code>SizeSequence</code> object simply represents intervals |
| 74 | * along an axis. |
| 75 | * In our examples, the intervals represent height or width in pixels. |
| 76 | * However, any other unit of measure (for example, time in days) |
| 77 | * could be just as valid. |
| 78 | * |
| 79 | * <p> |
| 80 | * |
| 81 | * <h4>Implementation Notes</h4> |
| 82 | * |
| 83 | * Normally when storing the size and position of entries, |
| 84 | * one would choose between |
| 85 | * storing the sizes or storing their positions |
| 86 | * instead. The two common operations that are needed during |
| 87 | * rendering are: <code>getIndex(position)</code> |
| 88 | * and <code>setSize(index, size)</code>. |
| 89 | * Whichever choice of internal format is made one of these |
| 90 | * operations is costly when the number of entries becomes large. |
| 91 | * If sizes are stored, finding the index of the entry |
| 92 | * that encloses a particular position is linear in the |
| 93 | * number of entries. If positions are stored instead, setting |
| 94 | * the size of an entry at a particular index requires updating |
| 95 | * the positions of the affected entries, which is also a linear |
| 96 | * calculation. |
| 97 | * <p> |
| 98 | * Like the above techniques this class holds an array of N integers |
| 99 | * internally but uses a hybrid encoding, which is halfway |
| 100 | * between the size-based and positional-based approaches. |
| 101 | * The result is a data structure that takes the same space to store |
| 102 | * the information but can perform most operations in Log(N) time |
| 103 | * instead of O(N), where N is the number of entries in the list. |
| 104 | * <p> |
| 105 | * Two operations that remain O(N) in the number of entries are |
| 106 | * the <code>insertEntries</code> |
| 107 | * and <code>removeEntries</code> methods, both |
| 108 | * of which are implemented by converting the internal array to |
| 109 | * a set of integer sizes, copying it into the new array, and then |
| 110 | * reforming the hybrid representation in place. |
| 111 | * |
| 112 | * @author Philip Milne |
| 113 | * @since 1.3 |
| 114 | */ |
| 115 | |
| 116 | /* |
| 117 | * Each method is implemented by taking the minimum and |
| 118 | * maximum of the range of integers that need to be operated |
| 119 | * upon. All the algorithms work by dividing this range |
| 120 | * into two smaller ranges and recursing. The recursion |
| 121 | * is terminated when the upper and lower bounds are equal. |
| 122 | */ |
| 123 | |
| 124 | public class SizeSequence { |
| 125 | |
| 126 | private static int[] emptyArray = new int[0]; |
| 127 | private int a[]; |
| 128 | |
| 129 | /** |
| 130 | * Creates a new <code>SizeSequence</code> object |
| 131 | * that contains no entries. To add entries, you |
| 132 | * can use <code>insertEntries</code> or <code>setSizes</code>. |
| 133 | * |
| 134 | * @see #insertEntries |
| 135 | * @see #setSizes |
| 136 | */ |
| 137 | public SizeSequence() { |
| 138 | a = emptyArray; |
| 139 | } |
| 140 | |
| 141 | /** |
| 142 | * Creates a new <code>SizeSequence</code> object |
| 143 | * that contains the specified number of entries, |
| 144 | * all initialized to have size 0. |
| 145 | * |
| 146 | * @param numEntries the number of sizes to track |
| 147 | * @exception NegativeArraySizeException if |
| 148 | * <code>numEntries < 0</code> |
| 149 | */ |
| 150 | public SizeSequence(int numEntries) { |
| 151 | this(numEntries, 0); |
| 152 | } |
| 153 | |
| 154 | /** |
| 155 | * Creates a new <code>SizeSequence</code> object |
| 156 | * that contains the specified number of entries, |
| 157 | * all initialized to have size <code>value</code>. |
| 158 | * |
| 159 | * @param numEntries the number of sizes to track |
| 160 | * @param value the initial value of each size |
| 161 | */ |
| 162 | public SizeSequence(int numEntries, int value) { |
| 163 | this(); |
| 164 | insertEntries(0, numEntries, value); |
| 165 | } |
| 166 | |
| 167 | /** |
| 168 | * Creates a new <code>SizeSequence</code> object |
| 169 | * that contains the specified sizes. |
| 170 | * |
| 171 | * @param sizes the array of sizes to be contained in |
| 172 | * the <code>SizeSequence</code> |
| 173 | */ |
| 174 | public SizeSequence(int[] sizes) { |
| 175 | this(); |
| 176 | setSizes(sizes); |
| 177 | } |
| 178 | |
| 179 | /** |
| 180 | * Resets the size sequence to contain <code>length</code> items |
| 181 | * all with a size of <code>size</code>. |
| 182 | */ |
| 183 | void setSizes(int length, int size) { |
| 184 | if (a.length != length) { |
| 185 | a = new int[length]; |
| 186 | } |
| 187 | setSizes(0, length, size); |
| 188 | } |
| 189 | |
| 190 | private int setSizes(int from, int to, int size) { |
| 191 | if (to <= from) { |
| 192 | return 0; |
| 193 | } |
| 194 | int m = (from + to)/2; |
| 195 | a[m] = size + setSizes(from, m, size); |
| 196 | return a[m] + setSizes(m + 1, to, size); |
| 197 | } |
| 198 | |
| 199 | /** |
| 200 | * Resets this <code>SizeSequence</code> object, |
| 201 | * using the data in the <code>sizes</code> argument. |
| 202 | * This method reinitializes this object so that it |
| 203 | * contains as many entries as the <code>sizes</code> array. |
| 204 | * Each entry's size is initialized to the value of the |
| 205 | * corresponding item in <code>sizes</code>. |
| 206 | * |
| 207 | * @param sizes the array of sizes to be contained in |
| 208 | * this <code>SizeSequence</code> |
| 209 | */ |
| 210 | public void setSizes(int[] sizes) { |
| 211 | if (a.length != sizes.length) { |
| 212 | a = new int[sizes.length]; |
| 213 | } |
| 214 | setSizes(0, a.length, sizes); |
| 215 | } |
| 216 | |
| 217 | private int setSizes(int from, int to, int[] sizes) { |
| 218 | if (to <= from) { |
| 219 | return 0; |
| 220 | } |
| 221 | int m = (from + to)/2; |
| 222 | a[m] = sizes[m] + setSizes(from, m, sizes); |
| 223 | return a[m] + setSizes(m + 1, to, sizes); |
| 224 | } |
| 225 | |
| 226 | /** |
| 227 | * Returns the size of all entries. |
| 228 | * |
| 229 | * @return a new array containing the sizes in this object |
| 230 | */ |
| 231 | public int[] getSizes() { |
| 232 | int n = a.length; |
| 233 | int[] sizes = new int[n]; |
| 234 | getSizes(0, n, sizes); |
| 235 | return sizes; |
| 236 | } |
| 237 | |
| 238 | private int getSizes(int from, int to, int[] sizes) { |
| 239 | if (to <= from) { |
| 240 | return 0; |
| 241 | } |
| 242 | int m = (from + to)/2; |
| 243 | sizes[m] = a[m] - getSizes(from, m, sizes); |
| 244 | return a[m] + getSizes(m + 1, to, sizes); |
| 245 | } |
| 246 | |
| 247 | /** |
| 248 | * Returns the start position for the specified entry. |
| 249 | * For example, <code>getPosition(0)</code> returns 0, |
| 250 | * <code>getPosition(1)</code> is equal to |
| 251 | * <code>getSize(0)</code>, |
| 252 | * <code>getPosition(2)</code> is equal to |
| 253 | * <code>getSize(0)</code> + <code>getSize(1)</code>, |
| 254 | * and so on. |
| 255 | * <p>Note that if <code>index</code> is greater than |
| 256 | * <code>length</code> the value returned may |
| 257 | * be meaningless. |
| 258 | * |
| 259 | * @param index the index of the entry whose position is desired |
| 260 | * @return the starting position of the specified entry |
| 261 | */ |
| 262 | public int getPosition(int index) { |
| 263 | return getPosition(0, a.length, index); |
| 264 | } |
| 265 | |
| 266 | private int getPosition(int from, int to, int index) { |
| 267 | if (to <= from) { |
| 268 | return 0; |
| 269 | } |
| 270 | int m = (from + to)/2; |
| 271 | if (index <= m) { |
| 272 | return getPosition(from, m, index); |
| 273 | } |
| 274 | else { |
| 275 | return a[m] + getPosition(m + 1, to, index); |
| 276 | } |
| 277 | } |
| 278 | |
| 279 | /** |
| 280 | * Returns the index of the entry |
| 281 | * that corresponds to the specified position. |
| 282 | * For example, <code>getIndex(0)</code> is 0, |
| 283 | * since the first entry always starts at position 0. |
| 284 | * |
| 285 | * @param position the position of the entry |
| 286 | * @return the index of the entry that occupies the specified position |
| 287 | */ |
| 288 | public int getIndex(int position) { |
| 289 | return getIndex(0, a.length, position); |
| 290 | } |
| 291 | |
| 292 | private int getIndex(int from, int to, int position) { |
| 293 | if (to <= from) { |
| 294 | return from; |
| 295 | } |
| 296 | int m = (from + to)/2; |
| 297 | int pivot = a[m]; |
| 298 | if (position < pivot) { |
| 299 | return getIndex(from, m, position); |
| 300 | } |
| 301 | else { |
| 302 | return getIndex(m + 1, to, position - pivot); |
| 303 | } |
| 304 | } |
| 305 | |
| 306 | /** |
| 307 | * Returns the size of the specified entry. |
| 308 | * If <code>index</code> is out of the range |
| 309 | * <code>(0 <= index < getSizes().length)</code> |
| 310 | * the behavior is unspecified. |
| 311 | * |
| 312 | * @param index the index corresponding to the entry |
| 313 | * @return the size of the entry |
| 314 | */ |
| 315 | public int getSize(int index) { |
| 316 | return getPosition(index + 1) - getPosition(index); |
| 317 | } |
| 318 | |
| 319 | /** |
| 320 | * Sets the size of the specified entry. |
| 321 | * Note that if the value of <code>index</code> |
| 322 | * does not fall in the range: |
| 323 | * <code>(0 <= index < getSizes().length)</code> |
| 324 | * the behavior is unspecified. |
| 325 | * |
| 326 | * @param index the index corresponding to the entry |
| 327 | * @param size the size of the entry |
| 328 | */ |
| 329 | public void setSize(int index, int size) { |
| 330 | changeSize(0, a.length, index, size - getSize(index)); |
| 331 | } |
| 332 | |
| 333 | private void changeSize(int from, int to, int index, int delta) { |
| 334 | if (to <= from) { |
| 335 | return; |
| 336 | } |
| 337 | int m = (from + to)/2; |
| 338 | if (index <= m) { |
| 339 | a[m] += delta; |
| 340 | changeSize(from, m, index, delta); |
| 341 | } |
| 342 | else { |
| 343 | changeSize(m + 1, to, index, delta); |
| 344 | } |
| 345 | } |
| 346 | |
| 347 | /** |
| 348 | * Adds a contiguous group of entries to this <code>SizeSequence</code>. |
| 349 | * Note that the values of <code>start</code> and |
| 350 | * <code>length</code> must satisfy the following |
| 351 | * conditions: <code>(0 <= start < getSizes().length) |
| 352 | * AND (length >= 0)</code>. If these conditions are |
| 353 | * not met, the behavior is unspecified and an exception |
| 354 | * may be thrown. |
| 355 | * |
| 356 | * @param start the index to be assigned to the first entry |
| 357 | * in the group |
| 358 | * @param length the number of entries in the group |
| 359 | * @param value the size to be assigned to each new entry |
| 360 | * @exception ArrayIndexOutOfBoundsException if the parameters |
| 361 | * are outside of the range: |
| 362 | * (<code>0 <= start < (getSizes().length)) AND (length >= 0)</code> |
| 363 | */ |
| 364 | public void insertEntries(int start, int length, int value) { |
| 365 | int sizes[] = getSizes(); |
| 366 | int end = start + length; |
| 367 | int n = a.length + length; |
| 368 | a = new int[n]; |
| 369 | for (int i = 0; i < start; i++) { |
| 370 | a[i] = sizes[i] ; |
| 371 | } |
| 372 | for (int i = start; i < end; i++) { |
| 373 | a[i] = value ; |
| 374 | } |
| 375 | for (int i = end; i < n; i++) { |
| 376 | a[i] = sizes[i-length] ; |
| 377 | } |
| 378 | setSizes(a); |
| 379 | } |
| 380 | |
| 381 | /** |
| 382 | * Removes a contiguous group of entries |
| 383 | * from this <code>SizeSequence</code>. |
| 384 | * Note that the values of <code>start</code> and |
| 385 | * <code>length</code> must satisfy the following |
| 386 | * conditions: <code>(0 <= start < getSizes().length) |
| 387 | * AND (length >= 0)</code>. If these conditions are |
| 388 | * not met, the behavior is unspecified and an exception |
| 389 | * may be thrown. |
| 390 | * |
| 391 | * @param start the index of the first entry to be removed |
| 392 | * @param length the number of entries to be removed |
| 393 | */ |
| 394 | public void removeEntries(int start, int length) { |
| 395 | int sizes[] = getSizes(); |
| 396 | int end = start + length; |
| 397 | int n = a.length - length; |
| 398 | a = new int[n]; |
| 399 | for (int i = 0; i < start; i++) { |
| 400 | a[i] = sizes[i] ; |
| 401 | } |
| 402 | for (int i = start; i < n; i++) { |
| 403 | a[i] = sizes[i+length] ; |
| 404 | } |
| 405 | setSizes(a); |
| 406 | } |
| 407 | } |