1 /* 2 * Copyright (c) 1999, 2017, Oracle and/or its affiliates. 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * 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 * 56 * <p style="text-align: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 * <p> 61 * In the figure, the first index (0) corresponds to the first column, 62 * the second index (1) to the second column, and so on. 63 * The first column's position starts at 0, 64 * and the column occupies <em>size<sub>0</sub></em> pixels, 65 * where <em>size<sub>0</sub></em> is the value returned by 66 * <code>getSize(0)</code>. 67 * Thus, the first column ends at <em>size<sub>0</sub></em> - 1. 68 * The second column then begins at 69 * the position <em>size<sub>0</sub></em> 70 * and occupies <em>size<sub>1</sub></em> (<code>getSize(1)</code>) pixels. 71 * <p> 72 * Note that a <code>SizeSequence</code> object simply represents intervals 73 * along an axis. 74 * In our examples, the intervals represent height or width in pixels. 75 * However, any other unit of measure (for example, time in days) 76 * could be just as valid. 77 * 78 * 79 * <h3>Implementation Notes</h3> 80 * 81 * Normally when storing the size and position of entries, 82 * one would choose between 83 * storing the sizes or storing their positions 84 * instead. The two common operations that are needed during 85 * rendering are: <code>getIndex(position)</code> 86 * and <code>setSize(index, size)</code>. 87 * Whichever choice of internal format is made one of these 88 * operations is costly when the number of entries becomes large. 89 * If sizes are stored, finding the index of the entry 90 * that encloses a particular position is linear in the 91 * number of entries. If positions are stored instead, setting 92 * the size of an entry at a particular index requires updating 93 * the positions of the affected entries, which is also a linear 94 * calculation. 95 * <p> 96 * Like the above techniques this class holds an array of N integers 97 * internally but uses a hybrid encoding, which is halfway 98 * between the size-based and positional-based approaches. 99 * The result is a data structure that takes the same space to store 100 * the information but can perform most operations in Log(N) time 101 * instead of O(N), where N is the number of entries in the list. 102 * <p> 103 * Two operations that remain O(N) in the number of entries are 104 * the <code>insertEntries</code> 105 * and <code>removeEntries</code> methods, both 106 * of which are implemented by converting the internal array to 107 * a set of integer sizes, copying it into the new array, and then 108 * reforming the hybrid representation in place. 109 * 110 * @author Philip Milne 111 * @since 1.3 112 */ 113 114 /* 115 * Each method is implemented by taking the minimum and 116 * maximum of the range of integers that need to be operated 117 * upon. All the algorithms work by dividing this range 118 * into two smaller ranges and recursing. The recursion 119 * is terminated when the upper and lower bounds are equal. 120 */ 121 122 public class SizeSequence { 123 124 private static int[] emptyArray = new int[0]; 125 private int a[]; 126 127 /** 128 * Creates a new <code>SizeSequence</code> object 129 * that contains no entries. To add entries, you 130 * can use <code>insertEntries</code> or <code>setSizes</code>. 131 * 132 * @see #insertEntries 133 * @see #setSizes(int[]) 134 */ 135 public SizeSequence() { 136 a = emptyArray; 137 } 138 139 /** 140 * Creates a new <code>SizeSequence</code> object 141 * that contains the specified number of entries, 142 * all initialized to have size 0. 143 * 144 * @param numEntries the number of sizes to track 145 * @exception NegativeArraySizeException if 146 * <code>numEntries < 0</code> 147 */ 148 public SizeSequence(int numEntries) { 149 this(numEntries, 0); 150 } 151 152 /** 153 * Creates a new <code>SizeSequence</code> object 154 * that contains the specified number of entries, 155 * all initialized to have size <code>value</code>. 156 * 157 * @param numEntries the number of sizes to track 158 * @param value the initial value of each size 159 */ 160 public SizeSequence(int numEntries, int value) { 161 this(); 162 insertEntries(0, numEntries, value); 163 } 164 165 /** 166 * Creates a new <code>SizeSequence</code> object 167 * that contains the specified sizes. 168 * 169 * @param sizes the array of sizes to be contained in 170 * the <code>SizeSequence</code> 171 */ 172 public SizeSequence(int[] sizes) { 173 this(); 174 setSizes(sizes); 175 } 176 177 /** 178 * Resets the size sequence to contain <code>length</code> items 179 * all with a size of <code>size</code>. 180 */ 181 void setSizes(int length, int size) { 182 if (a.length != length) { 183 a = new int[length]; 184 } 185 setSizes(0, length, size); 186 } 187 188 private int setSizes(int from, int to, int size) { 189 if (to <= from) { 190 return 0; 191 } 192 int m = (from + to)/2; 193 a[m] = size + setSizes(from, m, size); 194 return a[m] + setSizes(m + 1, to, size); 195 } 196 197 /** 198 * Resets this <code>SizeSequence</code> object, 199 * using the data in the <code>sizes</code> argument. 200 * This method reinitializes this object so that it 201 * contains as many entries as the <code>sizes</code> array. 202 * Each entry's size is initialized to the value of the 203 * corresponding item in <code>sizes</code>. 204 * 205 * @param sizes the array of sizes to be contained in 206 * this <code>SizeSequence</code> 207 */ 208 public void setSizes(int[] sizes) { 209 if (a.length != sizes.length) { 210 a = new int[sizes.length]; 211 } 212 setSizes(0, a.length, sizes); 213 } 214 215 private int setSizes(int from, int to, int[] sizes) { 216 if (to <= from) { 217 return 0; 218 } 219 int m = (from + to)/2; 220 a[m] = sizes[m] + setSizes(from, m, sizes); 221 return a[m] + setSizes(m + 1, to, sizes); 222 } 223 224 /** 225 * Returns the size of all entries. 226 * 227 * @return a new array containing the sizes in this object 228 */ 229 public int[] getSizes() { 230 int n = a.length; 231 int[] sizes = new int[n]; 232 getSizes(0, n, sizes); 233 return sizes; 234 } 235 236 private int getSizes(int from, int to, int[] sizes) { 237 if (to <= from) { 238 return 0; 239 } 240 int m = (from + to)/2; 241 sizes[m] = a[m] - getSizes(from, m, sizes); 242 return a[m] + getSizes(m + 1, to, sizes); 243 } 244 245 /** 246 * Returns the start position for the specified entry. 247 * For example, <code>getPosition(0)</code> returns 0, 248 * <code>getPosition(1)</code> is equal to 249 * <code>getSize(0)</code>, 250 * <code>getPosition(2)</code> is equal to 251 * <code>getSize(0)</code> + <code>getSize(1)</code>, 252 * and so on. 253 * <p>Note that if <code>index</code> is greater than 254 * <code>length</code> the value returned may 255 * be meaningless. 256 * 257 * @param index the index of the entry whose position is desired 258 * @return the starting position of the specified entry 259 */ 260 public int getPosition(int index) { 261 return getPosition(0, a.length, index); 262 } 263 264 private int getPosition(int from, int to, int index) { 265 if (to <= from) { 266 return 0; 267 } 268 int m = (from + to)/2; 269 if (index <= m) { 270 return getPosition(from, m, index); 271 } 272 else { 273 return a[m] + getPosition(m + 1, to, index); 274 } 275 } 276 277 /** 278 * Returns the index of the entry 279 * that corresponds to the specified position. 280 * For example, <code>getIndex(0)</code> is 0, 281 * since the first entry always starts at position 0. 282 * 283 * @param position the position of the entry 284 * @return the index of the entry that occupies the specified position 285 */ 286 public int getIndex(int position) { 287 return getIndex(0, a.length, position); 288 } 289 290 private int getIndex(int from, int to, int position) { 291 if (to <= from) { 292 return from; 293 } 294 int m = (from + to)/2; 295 int pivot = a[m]; 296 if (position < pivot) { 297 return getIndex(from, m, position); 298 } 299 else { 300 return getIndex(m + 1, to, position - pivot); 301 } 302 } 303 304 /** 305 * Returns the size of the specified entry. 306 * If <code>index</code> is out of the range 307 * <code>(0 <= index < getSizes().length)</code> 308 * the behavior is unspecified. 309 * 310 * @param index the index corresponding to the entry 311 * @return the size of the entry 312 */ 313 public int getSize(int index) { 314 return getPosition(index + 1) - getPosition(index); 315 } 316 317 /** 318 * Sets the size of the specified entry. 319 * Note that if the value of <code>index</code> 320 * does not fall in the range: 321 * <code>(0 <= index < getSizes().length)</code> 322 * the behavior is unspecified. 323 * 324 * @param index the index corresponding to the entry 325 * @param size the size of the entry 326 */ 327 public void setSize(int index, int size) { 328 changeSize(0, a.length, index, size - getSize(index)); 329 } 330 331 private void changeSize(int from, int to, int index, int delta) { 332 if (to <= from) { 333 return; 334 } 335 int m = (from + to)/2; 336 if (index <= m) { 337 a[m] += delta; 338 changeSize(from, m, index, delta); 339 } 340 else { 341 changeSize(m + 1, to, index, delta); 342 } 343 } 344 345 /** 346 * Adds a contiguous group of entries to this <code>SizeSequence</code>. 347 * Note that the values of <code>start</code> and 348 * <code>length</code> must satisfy the following 349 * conditions: <code>(0 <= start < getSizes().length) 350 * AND (length >= 0)</code>. If these conditions are 351 * not met, the behavior is unspecified and an exception 352 * may be thrown. 353 * 354 * @param start the index to be assigned to the first entry 355 * in the group 356 * @param length the number of entries in the group 357 * @param value the size to be assigned to each new entry 358 * @exception ArrayIndexOutOfBoundsException if the parameters 359 * are outside of the range: 360 * (<code>0 <= start < (getSizes().length)) AND (length >= 0)</code> 361 */ 362 public void insertEntries(int start, int length, int value) { 363 int sizes[] = getSizes(); 364 int end = start + length; 365 int n = a.length + length; 366 a = new int[n]; 367 for (int i = 0; i < start; i++) { 368 a[i] = sizes[i] ; 369 } 370 for (int i = start; i < end; i++) { 371 a[i] = value ; 372 } 373 for (int i = end; i < n; i++) { 374 a[i] = sizes[i-length] ; 375 } 376 setSizes(a); 377 } 378 379 /** 380 * Removes a contiguous group of entries 381 * from this <code>SizeSequence</code>. 382 * Note that the values of <code>start</code> and 383 * <code>length</code> must satisfy the following 384 * conditions: <code>(0 <= start < getSizes().length) 385 * AND (length >= 0)</code>. If these conditions are 386 * not met, the behavior is unspecified and an exception 387 * may be thrown. 388 * 389 * @param start the index of the first entry to be removed 390 * @param length the number of entries to be removed 391 */ 392 public void removeEntries(int start, int length) { 393 int sizes[] = getSizes(); 394 int end = start + length; 395 int n = a.length - length; 396 a = new int[n]; 397 for (int i = 0; i < start; i++) { 398 a[i] = sizes[i] ; 399 } 400 for (int i = start; i < n; i++) { 401 a[i] = sizes[i+length] ; 402 } 403 setSizes(a); 404 } 405 }