| /* |
| * Copyright (c) 1999, 2017, Oracle and/or its affiliates. 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. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.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 style="text-align: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."> |
| * <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. |
| * |
| * |
| * <h3>Implementation Notes</h3> |
| * |
| * 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(int[]) |
| */ |
| 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); |
| } |
| } |