https://openjdk.java.net/ 
/*
 * Copyright (c) 1999, 2018, 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 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.

Author:Philip Milne
Since:1.3
/**
 * 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 SizeSequence object
that contains no entries.  To add entries, you
can use insertEntries or setSizes.

See Also:
/**
     * 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 SizeSequence object
that contains the specified number of entries,
all initialized to have size 0.

Params:
  • numEntries –  the number of sizes to track
Throws:
/**
     * 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 SizeSequence object
that contains the specified number of entries,
all initialized to have size value.

Params:
  • numEntries –  the number of sizes to track
  • value –       the initial value of each size
/**
     * 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 SizeSequence object
that contains the specified sizes.

Params:
  • sizes –  the array of sizes to be contained in
              the SizeSequence
/**
     * 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 length items
all with a size of size.

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

Params:
  • sizes –  the array of sizes to be contained in
              this SizeSequence
/**
     * 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.

Returns: a new array containing the sizes in this object
/**
     * 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, 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.

Params:
  • index –  the index of the entry whose position is desired
Returns:      the starting position of the specified entry
/**
     * 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, getIndex(0) is 0,
since the first entry always starts at position 0.

Params:
  • position –  the position of the entry
Returns: the index of the entry that occupies the specified position
/**
     * 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 index is out of the range
(0 <= index < getSizes().length)
the behavior is unspecified.

Params:
  • index –  the index corresponding to the entry
Returns: the size of the entry
/**
     * 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 index
does not fall in the range:
(0 <= index < getSizes().length)
the behavior is unspecified.

Params:
  • index –  the index corresponding to the entry
  • size –   the size of the entry
/**
     * 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 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.

Params:
  • start –   the index to be assigned to the first entry
               in the group
  • length –  the number of entries in the group
  • value –   the size to be assigned to each new entry
Throws:
/**
     * 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 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.

Params:
  • start –   the index of the first entry to be removed
  • length –  the number of entries to be removed
/**
     * 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);
    }
}