/*

 * Copyright (c) 1999, 2013, 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.

 *

 * <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.

 *

 *

 * <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 &lt; 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 &lt;= index &lt; 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 &lt;= index &lt; 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 &lt;= start &lt; getSizes().length)

     * AND (length &gt;= 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 &lt;= start &lt; (getSizes().length)) AND (length &gt;= 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 &lt;= start &lt; getSizes().length)

     * AND (length &gt;= 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);

    }

}