* 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. * *
*
*
* 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.
*
*
*
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.
*
* @author Philip Milne
* @since 1.3
*/
/*
* Each method is implemented by taking the minimum and
* maximum of the range of integers that need to be operated
* upon. All the algorithms work by dividing this range
* into two smaller ranges and recursing. The recursion
* is terminated when the upper and lower bounds are equal.
*/
public class SizeSequence {
private static int[] emptyArray = new int[0];
private int[] a;
/**
* Creates a new SizeSequence object
* that contains no entries. To add entries, you
* can use insertEntries or setSizes.
*
* @see #insertEntries
* @see #setSizes(int[])
*/
public SizeSequence() {
a = emptyArray;
}
/**
* 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
*/
public SizeSequence(int numEntries) {
this(numEntries, 0);
}
/**
* 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
*/
public SizeSequence(int numEntries, int value) {
this();
insertEntries(0, numEntries, value);
}
/**
* Creates a new SizeSequence object
* that contains the specified sizes.
*
* @param sizes the array of sizes to be contained in
* the SizeSequence
*/
public SizeSequence(int[] sizes) {
this();
setSizes(sizes);
}
/**
* Resets the size sequence to contain length items
* all with a size of size.
*/
void setSizes(int length, int size) {
if (a.length != length) {
a = new int[length];
}
setSizes(0, length, size);
}
private int setSizes(int from, int to, int size) {
if (to <= from) {
return 0;
}
int m = (from + to)/2;
a[m] = size + setSizes(from, m, size);
return a[m] + setSizes(m + 1, to, size);
}
/**
* 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
*/
public void setSizes(int[] sizes) {
if (a.length != sizes.length) {
a = new int[sizes.length];
}
setSizes(0, a.length, sizes);
}
private int setSizes(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);
}
/**
* Returns the size of all entries.
*
* @return a new array containing the sizes in this object
*/
public int[] getSizes() {
int n = a.length;
int[] sizes = new int[n];
getSizes(0, n, sizes);
return sizes;
}
private int getSizes(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);
}
/**
* 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
*/
public int getPosition(int index) {
return getPosition(0, a.length, index);
}
private int getPosition(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);
}
}
/**
* 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
*/
public int getIndex(int position) {
return getIndex(0, a.length, position);
}
private int getIndex(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);
}
}
/**
* 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
*/
public int getSize(int index) {
return getPosition(index + 1) - getPosition(index);
}
/**
* 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
*/
public void setSize(int index, int size) {
changeSize(0, a.length, index, size - getSize(index));
}
private void changeSize(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);
}
}
/**
* 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)
*/
public void insertEntries(int start, int length, int value) {
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);
}
/**
* 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
*/
public void removeEntries(int start, int length) {
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);
}
}