001 /*
002 * Copyright 1999-2006 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package javax.swing;
027
028 /**
029 * A <code>SizeSequence</code> object
030 * efficiently maintains an ordered list
031 * of sizes and corresponding positions.
032 * One situation for which <code>SizeSequence</code>
033 * might be appropriate is in a component
034 * that displays multiple rows of unequal size.
035 * In this case, a single <code>SizeSequence</code>
036 * object could be used to track the heights
037 * and Y positions of all rows.
038 * <p>
039 * Another example would be a multi-column component,
040 * such as a <code>JTable</code>,
041 * in which the column sizes are not all equal.
042 * The <code>JTable</code> might use a single
043 * <code>SizeSequence</code> object
044 * to store the widths and X positions of all the columns.
045 * The <code>JTable</code> could then use the
046 * <code>SizeSequence</code> object
047 * to find the column corresponding to a certain position.
048 * The <code>JTable</code> could update the
049 * <code>SizeSequence</code> object
050 * whenever one or more column sizes changed.
051 *
052 * <p>
053 * The following figure shows the relationship between size and position data
054 * for a multi-column component.
055 * <p>
056 * <center>
057 * <img src="doc-files/SizeSequence-1.gif" width=384 height = 100
058 * alt="The first item begins at position 0, the second at the position equal
059 to the size of the previous item, and so on.">
060 * </center>
061 * <p>
062 * In the figure, the first index (0) corresponds to the first column,
063 * the second index (1) to the second column, and so on.
064 * The first column's position starts at 0,
065 * and the column occupies <em>size<sub>0</sub></em> pixels,
066 * where <em>size<sub>0</sub></em> is the value returned by
067 * <code>getSize(0)</code>.
068 * Thus, the first column ends at <em>size<sub>0</sub></em> - 1.
069 * The second column then begins at
070 * the position <em>size<sub>0</sub></em>
071 * and occupies <em>size<sub>1</sub></em> (<code>getSize(1)</code>) pixels.
072 * <p>
073 * Note that a <code>SizeSequence</code> object simply represents intervals
074 * along an axis.
075 * In our examples, the intervals represent height or width in pixels.
076 * However, any other unit of measure (for example, time in days)
077 * could be just as valid.
078 *
079 * <p>
080 *
081 * <h4>Implementation Notes</h4>
082 *
083 * Normally when storing the size and position of entries,
084 * one would choose between
085 * storing the sizes or storing their positions
086 * instead. The two common operations that are needed during
087 * rendering are: <code>getIndex(position)</code>
088 * and <code>setSize(index, size)</code>.
089 * Whichever choice of internal format is made one of these
090 * operations is costly when the number of entries becomes large.
091 * If sizes are stored, finding the index of the entry
092 * that encloses a particular position is linear in the
093 * number of entries. If positions are stored instead, setting
094 * the size of an entry at a particular index requires updating
095 * the positions of the affected entries, which is also a linear
096 * calculation.
097 * <p>
098 * Like the above techniques this class holds an array of N integers
099 * 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 * @version 1.23 05/05/07
113 * @author Philip Milne
114 * @since 1.3
115 */
116
117 /*
118 * Each method is implemented by taking the minimum and
119 * maximum of the range of integers that need to be operated
120 * upon. All the algorithms work by dividing this range
121 * into two smaller ranges and recursing. The recursion
122 * is terminated when the upper and lower bounds are equal.
123 */
124
125 public class SizeSequence {
126
127 private static int[] emptyArray = new int[0];
128 private int a[];
129
130 /**
131 * Creates a new <code>SizeSequence</code> object
132 * that contains no entries. To add entries, you
133 * can use <code>insertEntries</code> or <code>setSizes</code>.
134 *
135 * @see #insertEntries
136 * @see #setSizes
137 */
138 public SizeSequence() {
139 a = emptyArray;
140 }
141
142 /**
143 * Creates a new <code>SizeSequence</code> object
144 * that contains the specified number of entries,
145 * all initialized to have size 0.
146 *
147 * @param numEntries the number of sizes to track
148 * @exception NegativeArraySizeException if
149 * <code>numEntries < 0</code>
150 */
151 public SizeSequence(int numEntries) {
152 this (numEntries, 0);
153 }
154
155 /**
156 * Creates a new <code>SizeSequence</code> object
157 * that contains the specified number of entries,
158 * all initialized to have size <code>value</code>.
159 *
160 * @param numEntries the number of sizes to track
161 * @param value the initial value of each size
162 */
163 public SizeSequence(int numEntries, int value) {
164 this ();
165 insertEntries(0, numEntries, value);
166 }
167
168 /**
169 * Creates a new <code>SizeSequence</code> object
170 * that contains the specified sizes.
171 *
172 * @param sizes the array of sizes to be contained in
173 * the <code>SizeSequence</code>
174 */
175 public SizeSequence(int[] sizes) {
176 this ();
177 setSizes(sizes);
178 }
179
180 /**
181 * Resets the size sequence to contain <code>length</code> items
182 * all with a size of <code>size</code>.
183 */
184 void setSizes(int length, int size) {
185 if (a.length != length) {
186 a = new int[length];
187 }
188 setSizes(0, length, size);
189 }
190
191 private int setSizes(int from, int to, int size) {
192 if (to <= from) {
193 return 0;
194 }
195 int m = (from + to) / 2;
196 a[m] = size + setSizes(from, m, size);
197 return a[m] + setSizes(m + 1, to, size);
198 }
199
200 /**
201 * Resets this <code>SizeSequence</code> object,
202 * using the data in the <code>sizes</code> argument.
203 * This method reinitializes this object so that it
204 * contains as many entries as the <code>sizes</code> array.
205 * Each entry's size is initialized to the value of the
206 * corresponding item in <code>sizes</code>.
207 *
208 * @param sizes the array of sizes to be contained in
209 * this <code>SizeSequence</code>
210 */
211 public void setSizes(int[] sizes) {
212 if (a.length != sizes.length) {
213 a = new int[sizes.length];
214 }
215 setSizes(0, a.length, sizes);
216 }
217
218 private int setSizes(int from, int to, int[] sizes) {
219 if (to <= from) {
220 return 0;
221 }
222 int m = (from + to) / 2;
223 a[m] = sizes[m] + setSizes(from, m, sizes);
224 return a[m] + setSizes(m + 1, to, sizes);
225 }
226
227 /**
228 * Returns the size of all entries.
229 *
230 * @return a new array containing the sizes in this object
231 */
232 public int[] getSizes() {
233 int n = a.length;
234 int[] sizes = new int[n];
235 getSizes(0, n, sizes);
236 return sizes;
237 }
238
239 private int getSizes(int from, int to, int[] sizes) {
240 if (to <= from) {
241 return 0;
242 }
243 int m = (from + to) / 2;
244 sizes[m] = a[m] - getSizes(from, m, sizes);
245 return a[m] + getSizes(m + 1, to, sizes);
246 }
247
248 /**
249 * Returns the start position for the specified entry.
250 * For example, <code>getPosition(0)</code> returns 0,
251 * <code>getPosition(1)</code> is equal to
252 * <code>getSize(0)</code>,
253 * <code>getPosition(2)</code> is equal to
254 * <code>getSize(0)</code> + <code>getSize(1)</code>,
255 * and so on.
256 * <p>Note that if <code>index</code> is greater than
257 * <code>length</code> the value returned may
258 * be meaningless.
259 *
260 * @param index the index of the entry whose position is desired
261 * @return the starting position of the specified entry
262 */
263 public int getPosition(int index) {
264 return getPosition(0, a.length, index);
265 }
266
267 private int getPosition(int from, int to, int index) {
268 if (to <= from) {
269 return 0;
270 }
271 int m = (from + to) / 2;
272 if (index <= m) {
273 return getPosition(from, m, index);
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 } else {
301 return getIndex(m + 1, to, position - pivot);
302 }
303 }
304
305 /**
306 * Returns the size of the specified entry.
307 * If <code>index</code> is out of the range
308 * <code>(0 <= index < getSizes().length)</code>
309 * the behavior is unspecified.
310 *
311 * @param index the index corresponding to the entry
312 * @return the size of the entry
313 */
314 public int getSize(int index) {
315 return getPosition(index + 1) - getPosition(index);
316 }
317
318 /**
319 * Sets the size of the specified entry.
320 * Note that if the value of <code>index</code>
321 * does not fall in the range:
322 * <code>(0 <= index < getSizes().length)</code>
323 * the behavior is unspecified.
324 *
325 * @param index the index corresponding to the entry
326 * @param size the size of the entry
327 */
328 public void setSize(int index, int size) {
329 changeSize(0, a.length, index, size - getSize(index));
330 }
331
332 private void changeSize(int from, int to, int index, int delta) {
333 if (to <= from) {
334 return;
335 }
336 int m = (from + to) / 2;
337 if (index <= m) {
338 a[m] += delta;
339 changeSize(from, m, index, delta);
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 }
|