/* * Copyright (c) 1999, 2011, 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> * <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(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);    }}