SizeSequence


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