/*
 * @(#)SizeSequence.java	1.14 03/12/19
 *
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

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. 
 *
 * @version 1.14 12/19/03
 * @author Philip Milne
 */   

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