--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/classes/javax/swing/SizeSequence.java Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,407 @@
+/*
+ * Copyright 1999-2006 Sun Microsystems, Inc. All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+package javax.swing;
+
+/**
+ * A <code>SizeSequence</code> object
+ * efficiently maintains an ordered list
+ * of sizes and corresponding positions.
+ * One situation for which <code>SizeSequence</code>
+ * might be appropriate is in a component
+ * that displays multiple rows of unequal size.
+ * In this case, a single <code>SizeSequence</code>
+ * object could be used to track the heights
+ * and Y positions of all rows.
+ * <p>
+ * Another example would be a multi-column component,
+ * such as a <code>JTable</code>,
+ * in which the column sizes are not all equal.
+ * The <code>JTable</code> might use a single
+ * <code>SizeSequence</code> object
+ * to store the widths and X positions of all the columns.
+ * The <code>JTable</code> could then use the
+ * <code>SizeSequence</code> object
+ * to find the column corresponding to a certain position.
+ * The <code>JTable</code> could update the
+ * <code>SizeSequence</code> object
+ * whenever one or more column sizes changed.
+ *
+ * <p>
+ * The following figure shows the relationship between size and position data
+ * for a multi-column component.
+ * <p>
+ * <center>
+ * <img src="doc-files/SizeSequence-1.gif" width=384 height = 100
+ * alt="The first item begins at position 0, the second at the position equal
+ to the size of the previous item, and so on.">
+ * </center>
+ * <p>
+ * 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 <em>size<sub>0</sub></em> pixels,
+ * where <em>size<sub>0</sub></em> is the value returned by
+ * <code>getSize(0)</code>.
+ * Thus, the first column ends at <em>size<sub>0</sub></em> - 1.
+ * The second column then begins at
+ * the position <em>size<sub>0</sub></em>
+ * and occupies <em>size<sub>1</sub></em> (<code>getSize(1)</code>) pixels.
+ * <p>
+ * Note that a <code>SizeSequence</code> 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.
+ *
+ * <p>
+ *
+ * <h4>Implementation Notes</h4>
+ *
+ * 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: <code>getIndex(position)</code>
+ * and <code>setSize(index, size)</code>.
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * Two operations that remain O(N) in the number of entries are
+ * the <code>insertEntries</code>
+ * and <code>removeEntries</code> 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 <code>SizeSequence</code> object
+ * that contains no entries. To add entries, you
+ * can use <code>insertEntries</code> or <code>setSizes</code>.
+ *
+ * @see #insertEntries
+ * @see #setSizes
+ */
+ public SizeSequence() {
+ a = emptyArray;
+ }
+
+ /**
+ * Creates a new <code>SizeSequence</code> 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
+ * <code>numEntries < 0</code>
+ */
+ public SizeSequence(int numEntries) {
+ this(numEntries, 0);
+ }
+
+ /**
+ * Creates a new <code>SizeSequence</code> object
+ * that contains the specified number of entries,
+ * all initialized to have size <code>value</code>.
+ *
+ * @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 <code>SizeSequence</code> object
+ * that contains the specified sizes.
+ *
+ * @param sizes the array of sizes to be contained in
+ * the <code>SizeSequence</code>
+ */
+ public SizeSequence(int[] sizes) {
+ this();
+ setSizes(sizes);
+ }
+
+ /**
+ * Resets the size sequence to contain <code>length</code> items
+ * all with a size of <code>size</code>.
+ */
+ 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 <code>SizeSequence</code> object,
+ * using the data in the <code>sizes</code> argument.
+ * This method reinitializes this object so that it
+ * contains as many entries as the <code>sizes</code> array.
+ * Each entry's size is initialized to the value of the
+ * corresponding item in <code>sizes</code>.
+ *
+ * @param sizes the array of sizes to be contained in
+ * this <code>SizeSequence</code>
+ */
+ 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, <code>getPosition(0)</code> returns 0,
+ * <code>getPosition(1)</code> is equal to
+ * <code>getSize(0)</code>,
+ * <code>getPosition(2)</code> is equal to
+ * <code>getSize(0)</code> + <code>getSize(1)</code>,
+ * and so on.
+ * <p>Note that if <code>index</code> is greater than
+ * <code>length</code> 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, <code>getIndex(0)</code> 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 <code>index</code> is out of the range
+ * <code>(0 <= index < getSizes().length)</code>
+ * 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 <code>index</code>
+ * does not fall in the range:
+ * <code>(0 <= index < getSizes().length)</code>
+ * 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 <code>SizeSequence</code>.
+ * Note that the values of <code>start</code> and
+ * <code>length</code> must satisfy the following
+ * conditions: <code>(0 <= start < getSizes().length)
+ * AND (length >= 0)</code>. 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:
+ * (<code>0 <= start < (getSizes().length)) AND (length >= 0)</code>
+ */
+ 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 <code>SizeSequence</code>.
+ * Note that the values of <code>start</code> and
+ * <code>length</code> must satisfy the following
+ * conditions: <code>(0 <= start < getSizes().length)
+ * AND (length >= 0)</code>. 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);
+ }
+}