FileDocCategorySizeDatePackage
SizeSequence.javaAPI DocJava SE 5 API12550Fri Aug 26 14:57:58 BST 2005javax.swing

SizeSequence

public class SizeSequence extends Object
A SizeSequence object efficiently maintains an ordered list of sizes and corresponding positions. One situation for which SizeSequence might be appropriate is in a component that displays multiple rows of unequal size. In this case, a single SizeSequence object could be used to track the heights and Y positions of all rows.

Another example would be a multi-column component, such as a JTable, in which the column sizes are not all equal. The JTable might use a single SizeSequence object to store the widths and X positions of all the columns. The JTable could then use the SizeSequence object to find the column corresponding to a certain position. The JTable could update the SizeSequence object whenever one or more column sizes changed.

The following figure shows the relationship between size and position data for a multi-column component.

The first item begins at position 0, the second at the position equal
to the size of the previous item, and so on.

In the figure, the first index (0) corresponds to the first column, the second index (1) to the second column, and so on. The first column's position starts at 0, and the column occupies size0 pixels, where size0 is the value returned by getSize(0). Thus, the first column ends at size0 - 1. The second column then begins at the position size0 and occupies size1 (getSize(1)) pixels.

Note that a SizeSequence object simply represents intervals along an axis. In our examples, the intervals represent height or width in pixels. However, any other unit of measure (for example, time in days) could be just as valid.

Implementation Notes

Normally when storing the size and position of entries, one would choose between storing the sizes or storing their positions instead. The two common operations that are needed during rendering are: getIndex(position) and setSize(index, size). Whichever choice of internal format is made one of these operations is costly when the number of entries becomes large. If sizes are stored, finding the index of the entry that encloses a particular position is linear in the number of entries. If positions are stored instead, setting the size of an entry at a particular index requires updating the positions of the affected entries, which is also a linear calculation.

Like the above techniques this class holds an array of N integers internally but uses a hybrid encoding, which is halfway between the size-based and positional-based approaches. The result is a data structure that takes the same space to store the information but can perform most operations in Log(N) time instead of O(N), where N is the number of entries in the list.

Two operations that remain O(N) in the number of entries are the insertEntries and removeEntries methods, both of which are implemented by converting the internal array to a set of integer sizes, copying it into the new array, and then reforming the hybrid representation in place.

version
1.14 12/19/03
author
Philip Milne

Fields Summary
private static int[]
emptyArray
private int[]
a
Constructors Summary
public SizeSequence()
Creates a new SizeSequence object that contains no entries. To add entries, you can use insertEntries or setSizes.

see
#insertEntries
see
#setSizes

 
    
                                
       
        a = emptyArray; 
    
public SizeSequence(int numEntries)
Creates a new SizeSequence object that contains the specified number of entries, all initialized to have size 0.

param
numEntries the number of sizes to track
exception
NegativeArraySizeException if numEntries < 0

 
        this(numEntries, 0); 
    
public SizeSequence(int numEntries, int value)
Creates a new SizeSequence object that contains the specified number of entries, all initialized to have size value.

param
numEntries the number of sizes to track
param
value the initial value of each size

 
        this(); 
        insertEntries(0, numEntries, value); 
    
public SizeSequence(int[] sizes)
Creates a new SizeSequence object that contains the specified sizes.

param
sizes the array of sizes to be contained in the SizeSequence

 
        this(); 
	setSizes(sizes); 
    
Methods Summary
private voidchangeSize(int from, int to, int index, int delta)

 
        if (to <= from) { 
            return; 
        }
        int m = (from + to)/2; 
        if (index <= m) { 
            a[m] += delta; 
            changeSize(from, m, index, delta); 
        }
        else { 
            changeSize(m + 1, to, index, delta); 
        }
    
public intgetIndex(int position)
Returns the index of the entry that corresponds to the specified position. For example, getIndex(0) is 0, since the first entry always starts at position 0.

param
position the position of the entry
return
the index of the entry that occupies the specified position

 
        return getIndex(0, a.length, position); 
    
private intgetIndex(int from, int to, int position)

 
        if (to <= from) { 
            return from; 
        }
        int m = (from + to)/2; 
        int pivot = a[m]; 
        if (position < pivot) { 
           return getIndex(from, m, position); 
        }
        else { 
            return getIndex(m + 1, to, position - pivot); 
        }
    
private intgetPosition(int from, int to, int index)

 
        if (to <= from) { 
            return 0; 
        }
        int m = (from + to)/2; 
        if (index <= m) { 
            return getPosition(from, m, index); 
        }
        else { 
            return a[m] + getPosition(m + 1, to, index); 
        }
    
public intgetPosition(int index)
Returns the start position for the specified entry. For example, getPosition(0) returns 0, getPosition(1) is equal to getSize(0), getPosition(2) is equal to getSize(0) + getSize(1), and so on.

Note that if index is greater than length the value returned may be meaningless.

param
index the index of the entry whose position is desired
return
the starting position of the specified entry

 
        return getPosition(0, a.length, index); 
    
public intgetSize(int index)
Returns the size of the specified entry. If index is out of the range (0 <= index < getSizes().length) the behavior is unspecified.

param
index the index corresponding to the entry
return
the size of the entry

 
        return getPosition(index + 1) - getPosition(index); 
    
public int[]getSizes()
Returns the size of all entries.

return
a new array containing the sizes in this object

 
        int n = a.length; 
        int[] sizes = new int[n]; 
        getSizes(0, n, sizes); 
        return sizes;
    
private intgetSizes(int from, int to, int[] sizes)

 
        if (to <= from) { 
            return 0; 
        }
        int m = (from + to)/2; 
        sizes[m] = a[m] - getSizes(from, m, sizes); 
        return a[m] + getSizes(m + 1, to, sizes); 
    
public voidinsertEntries(int start, int length, int value)
Adds a contiguous group of entries to this SizeSequence. Note that the values of start and length must satisfy the following conditions: (0 <= start < getSizes().length) AND (length >= 0). If these conditions are not met, the behavior is unspecified and an exception may be thrown.

param
start the index to be assigned to the first entry in the group
param
length the number of entries in the group
param
value the size to be assigned to each new entry
exception
ArrayIndexOutOfBoundsException if the parameters are outside of the range: (0 <= start < (getSizes().length)) AND (length >= 0)

 
        int sizes[] = getSizes(); 
        int end = start + length; 
        int n = a.length + length; 
        a = new int[n]; 
        for (int i = 0; i < start; i++) { 
            a[i] = sizes[i] ;
        }
        for (int i = start; i < end; i++) { 
            a[i] = value ;
        }
        for (int i = end; i < n; i++) { 
            a[i] = sizes[i-length] ;
        }
        setSizes(a); 
    
public voidremoveEntries(int start, int length)
Removes a contiguous group of entries from this SizeSequence. Note that the values of start and length must satisfy the following conditions: (0 <= start < getSizes().length) AND (length >= 0). If these conditions are not met, the behavior is unspecified and an exception may be thrown.

param
start the index of the first entry to be removed
param
length the number of entries to be removed

 
        int sizes[] = getSizes(); 
        int end = start + length; 
        int n = a.length - length; 
        a = new int[n]; 
        for (int i = 0; i < start; i++) { 
            a[i] = sizes[i] ;
        }
        for (int i = start; i < n; i++) { 
            a[i] = sizes[i+length] ;
        }
        setSizes(a); 
    
public voidsetSize(int index, int size)
Sets the size of the specified entry. Note that if the value of index does not fall in the range: (0 <= index < getSizes().length) the behavior is unspecified.

param
index the index corresponding to the entry
param
size the size of the entry

 
        changeSize(0, a.length, index, size - getSize(index)); 
    
public voidsetSizes(int[] sizes)
Resets this SizeSequence object, using the data in the sizes argument. This method reinitializes this object so that it contains as many entries as the sizes array. Each entry's size is initialized to the value of the corresponding item in sizes.

param
sizes the array of sizes to be contained in this SizeSequence

 
	if (a.length != sizes.length) { 
	    a = new int[sizes.length]; 
        }
	setSizes(0, a.length, sizes);
    
private intsetSizes(int from, int to, int[] sizes)

 
        if (to <= from) { 
            return 0; 
        }
        int m = (from + to)/2; 
        a[m] = sizes[m] + setSizes(from, m, sizes); 
        return a[m] + setSizes(m + 1, to, sizes);