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 }