Back to index...

	/*
	* 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 < 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);
	}
	}

Back to index...