SizeSequencepublic 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.
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. |
| 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.
a = emptyArray;
| public SizeSequence(int numEntries)Creates a new SizeSequence object
that contains the specified number of entries,
all initialized to have size 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.
this();
insertEntries(0, numEntries, value);
| public SizeSequence(int[] sizes)Creates a new SizeSequence object
that contains the specified sizes.
this();
setSizes(sizes);
|
| Methods Summary |
|---|
| 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);
}
| | public int | getIndex(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.
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);
}
| | 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);
}
| | public int | getPosition(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.
return getPosition(0, a.length, index);
| | public int | getSize(int index)Returns the size of the specified entry.
If index is out of the range
(0 <= index < getSizes().length)
the behavior is unspecified.
return getPosition(index + 1) - getPosition(index);
| | public int[] | getSizes()Returns the size of all entries.
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);
| | public void | insertEntries(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.
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 void | removeEntries(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.
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 void | setSize(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.
changeSize(0, a.length, index, size - getSize(index));
| | public void | setSizes(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.
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);
|
|
