Home » openjdk-7 » javax » swing » [javadoc | source]

    1   /*
    2    * Copyright (c) 1999, 2011, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package javax.swing;
   27   
   28   /**
   29    * A <code>SizeSequence</code> object
   30    * efficiently maintains an ordered list
   31    * of sizes and corresponding positions.
   32    * One situation for which <code>SizeSequence</code>
   33    * might be appropriate is in a component
   34    * that displays multiple rows of unequal size.
   35    * In this case, a single <code>SizeSequence</code>
   36    * object could be used to track the heights
   37    * and Y positions of all rows.
   38    * <p>
   39    * Another example would be a multi-column component,
   40    * such as a <code>JTable</code>,
   41    * in which the column sizes are not all equal.
   42    * The <code>JTable</code> might use a single
   43    * <code>SizeSequence</code> object
   44    * to store the widths and X positions of all the columns.
   45    * The <code>JTable</code> could then use the
   46    * <code>SizeSequence</code> object
   47    * to find the column corresponding to a certain position.
   48    * The <code>JTable</code> could update the
   49    * <code>SizeSequence</code> object
   50    * whenever one or more column sizes changed.
   51    *
   52    * <p>
   53    * The following figure shows the relationship between size and position data
   54    * for a multi-column component.
   55    * <p>
   56    * <center>
   57    * <img src="doc-files/SizeSequence-1.gif" width=384 height = 100
   58    * alt="The first item begins at position 0, the second at the position equal
   59    to the size of the previous item, and so on.">
   60    * </center>
   61    * <p>
   62    * In the figure, the first index (0) corresponds to the first column,
   63    * the second index (1) to the second column, and so on.
   64    * The first column's position starts at 0,
   65    * and the column occupies <em>size<sub>0</sub></em> pixels,
   66    * where <em>size<sub>0</sub></em> is the value returned by
   67    * <code>getSize(0)</code>.
   68    * Thus, the first column ends at <em>size<sub>0</sub></em> - 1.
   69    * The second column then begins at
   70    * the position <em>size<sub>0</sub></em>
   71    * and occupies <em>size<sub>1</sub></em> (<code>getSize(1)</code>) pixels.
   72    * <p>
   73    * Note that a <code>SizeSequence</code> object simply represents intervals
   74    * along an axis.
   75    * In our examples, the intervals represent height or width in pixels.
   76    * However, any other unit of measure (for example, time in days)
   77    * could be just as valid.
   78    *
   79    * <p>
   80    *
   81    * <h4>Implementation Notes</h4>
   82    *
   83    * Normally when storing the size and position of entries,
   84    * one would choose between
   85    * storing the sizes or storing their positions
   86    * instead. The two common operations that are needed during
   87    * rendering are: <code>getIndex(position)</code>
   88    * and <code>setSize(index, size)</code>.
   89    * Whichever choice of internal format is made one of these
   90    * operations is costly when the number of entries becomes large.
   91    * If sizes are stored, finding the index of the entry
   92    * that encloses a particular position is linear in the
   93    * number of entries. If positions are stored instead, setting
   94    * the size of an entry at a particular index requires updating
   95    * the positions of the affected entries, which is also a linear
   96    * calculation.
   97    * <p>
   98    * Like the above techniques this class holds an array of N integers
   99    * internally but uses a hybrid encoding, which is halfway
  100    * between the size-based and positional-based approaches.
  101    * The result is a data structure that takes the same space to store
  102    * the information but can perform most operations in Log(N) time
  103    * instead of O(N), where N is the number of entries in the list.
  104    * <p>
  105    * Two operations that remain O(N) in the number of entries are
  106    * the <code>insertEntries</code>
  107    * and <code>removeEntries</code> methods, both
  108    * of which are implemented by converting the internal array to
  109    * a set of integer sizes, copying it into the new array, and then
  110    * reforming the hybrid representation in place.
  111    *
  112    * @author Philip Milne
  113    * @since 1.3
  114    */
  115   
  116   /*
  117    *   Each method is implemented by taking the minimum and
  118    *   maximum of the range of integers that need to be operated
  119    *   upon. All the algorithms work by dividing this range
  120    *   into two smaller ranges and recursing. The recursion
  121    *   is terminated when the upper and lower bounds are equal.
  122    */
  123   
  124   public class SizeSequence {
  125   
  126       private static int[] emptyArray = new int[0];
  127       private int a[];
  128   
  129       /**
  130        * Creates a new <code>SizeSequence</code> object
  131        * that contains no entries.  To add entries, you
  132        * can use <code>insertEntries</code> or <code>setSizes</code>.
  133        *
  134        * @see #insertEntries
  135        * @see #setSizes(int[])
  136        */
  137       public SizeSequence() {
  138           a = emptyArray;
  139       }
  140   
  141       /**
  142        * Creates a new <code>SizeSequence</code> object
  143        * that contains the specified number of entries,
  144        * all initialized to have size 0.
  145        *
  146        * @param numEntries  the number of sizes to track
  147        * @exception NegativeArraySizeException if
  148        *    <code>numEntries < 0</code>
  149        */
  150       public SizeSequence(int numEntries) {
  151           this(numEntries, 0);
  152       }
  153   
  154       /**
  155        * Creates a new <code>SizeSequence</code> object
  156        * that contains the specified number of entries,
  157        * all initialized to have size <code>value</code>.
  158        *
  159        * @param numEntries  the number of sizes to track
  160        * @param value       the initial value of each size
  161        */
  162       public SizeSequence(int numEntries, int value) {
  163           this();
  164           insertEntries(0, numEntries, value);
  165       }
  166   
  167       /**
  168        * Creates a new <code>SizeSequence</code> object
  169        * that contains the specified sizes.
  170        *
  171        * @param sizes  the array of sizes to be contained in
  172        *               the <code>SizeSequence</code>
  173        */
  174       public SizeSequence(int[] sizes) {
  175           this();
  176           setSizes(sizes);
  177       }
  178   
  179       /**
  180        * Resets the size sequence to contain <code>length</code> items
  181        * all with a size of <code>size</code>.
  182        */
  183       void setSizes(int length, int size) {
  184           if (a.length != length) {
  185               a = new int[length];
  186           }
  187           setSizes(0, length, size);
  188       }
  189   
  190       private int setSizes(int from, int to, int size) {
  191           if (to <= from) {
  192               return 0;
  193           }
  194           int m = (from + to)/2;
  195           a[m] = size + setSizes(from, m, size);
  196           return a[m] + setSizes(m + 1, to, size);
  197       }
  198   
  199       /**
  200        * Resets this <code>SizeSequence</code> object,
  201        * using the data in the <code>sizes</code> argument.
  202        * This method reinitializes this object so that it
  203        * contains as many entries as the <code>sizes</code> array.
  204        * Each entry's size is initialized to the value of the
  205        * corresponding item in <code>sizes</code>.
  206        *
  207        * @param sizes  the array of sizes to be contained in
  208        *               this <code>SizeSequence</code>
  209        */
  210       public void setSizes(int[] sizes) {
  211           if (a.length != sizes.length) {
  212               a = new int[sizes.length];
  213           }
  214           setSizes(0, a.length, sizes);
  215       }
  216   
  217       private int setSizes(int from, int to, int[] sizes) {
  218           if (to <= from) {
  219               return 0;
  220           }
  221           int m = (from + to)/2;
  222           a[m] = sizes[m] + setSizes(from, m, sizes);
  223           return a[m] + setSizes(m + 1, to, sizes);
  224       }
  225   
  226       /**
  227        * Returns the size of all entries.
  228        *
  229        * @return  a new array containing the sizes in this object
  230        */
  231       public int[] getSizes() {
  232           int n = a.length;
  233           int[] sizes = new int[n];
  234           getSizes(0, n, sizes);
  235           return sizes;
  236       }
  237   
  238       private int getSizes(int from, int to, int[] sizes) {
  239           if (to <= from) {
  240               return 0;
  241           }
  242           int m = (from + to)/2;
  243           sizes[m] = a[m] - getSizes(from, m, sizes);
  244           return a[m] + getSizes(m + 1, to, sizes);
  245       }
  246   
  247       /**
  248        * Returns the start position for the specified entry.
  249        * For example, <code>getPosition(0)</code> returns 0,
  250        * <code>getPosition(1)</code> is equal to
  251        *   <code>getSize(0)</code>,
  252        * <code>getPosition(2)</code> is equal to
  253        *   <code>getSize(0)</code> + <code>getSize(1)</code>,
  254        * and so on.
  255        * <p>Note that if <code>index</code> is greater than
  256        * <code>length</code> the value returned may
  257        * be meaningless.
  258        *
  259        * @param index  the index of the entry whose position is desired
  260        * @return       the starting position of the specified entry
  261        */
  262       public int getPosition(int index) {
  263           return getPosition(0, a.length, index);
  264       }
  265   
  266       private int getPosition(int from, int to, int index) {
  267           if (to <= from) {
  268               return 0;
  269           }
  270           int m = (from + to)/2;
  271           if (index <= m) {
  272               return getPosition(from, m, index);
  273           }
  274           else {
  275               return a[m] + getPosition(m + 1, to, index);
  276           }
  277       }
  278   
  279       /**
  280        * Returns the index of the entry
  281        * that corresponds to the specified position.
  282        * For example, <code>getIndex(0)</code> is 0,
  283        * since the first entry always starts at position 0.
  284        *
  285        * @param position  the position of the entry
  286        * @return  the index of the entry that occupies the specified position
  287        */
  288       public int getIndex(int position) {
  289           return getIndex(0, a.length, position);
  290       }
  291   
  292       private int getIndex(int from, int to, int position) {
  293           if (to <= from) {
  294               return from;
  295           }
  296           int m = (from + to)/2;
  297           int pivot = a[m];
  298           if (position < pivot) {
  299              return getIndex(from, m, position);
  300           }
  301           else {
  302               return getIndex(m + 1, to, position - pivot);
  303           }
  304       }
  305   
  306       /**
  307        * Returns the size of the specified entry.
  308        * If <code>index</code> is out of the range
  309        * <code>(0 <= index < getSizes().length)</code>
  310        * the behavior is unspecified.
  311        *
  312        * @param index  the index corresponding to the entry
  313        * @return  the size of the entry
  314        */
  315       public int getSize(int index) {
  316           return getPosition(index + 1) - getPosition(index);
  317       }
  318   
  319       /**
  320        * Sets the size of the specified entry.
  321        * Note that if the value of <code>index</code>
  322        * does not fall in the range:
  323        * <code>(0 <= index < getSizes().length)</code>
  324        * the behavior is unspecified.
  325        *
  326        * @param index  the index corresponding to the entry
  327        * @param size   the size of the entry
  328        */
  329       public void setSize(int index, int size) {
  330           changeSize(0, a.length, index, size - getSize(index));
  331       }
  332   
  333       private void changeSize(int from, int to, int index, int delta) {
  334           if (to <= from) {
  335               return;
  336           }
  337           int m = (from + to)/2;
  338           if (index <= m) {
  339               a[m] += delta;
  340               changeSize(from, m, index, delta);
  341           }
  342           else {
  343               changeSize(m + 1, to, index, delta);
  344           }
  345       }
  346   
  347       /**
  348        * Adds a contiguous group of entries to this <code>SizeSequence</code>.
  349        * Note that the values of <code>start</code> and
  350        * <code>length</code> must satisfy the following
  351        * conditions:  <code>(0 <= start < getSizes().length)
  352        * AND (length >= 0)</code>.  If these conditions are
  353        * not met, the behavior is unspecified and an exception
  354        * may be thrown.
  355        *
  356        * @param start   the index to be assigned to the first entry
  357        *                in the group
  358        * @param length  the number of entries in the group
  359        * @param value   the size to be assigned to each new entry
  360        * @exception ArrayIndexOutOfBoundsException if the parameters
  361        *   are outside of the range:
  362        *   (<code>0 <= start < (getSizes().length)) AND (length >= 0)</code>
  363        */
  364       public void insertEntries(int start, int length, int value) {
  365           int sizes[] = getSizes();
  366           int end = start + length;
  367           int n = a.length + length;
  368           a = new int[n];
  369           for (int i = 0; i < start; i++) {
  370               a[i] = sizes[i] ;
  371           }
  372           for (int i = start; i < end; i++) {
  373               a[i] = value ;
  374           }
  375           for (int i = end; i < n; i++) {
  376               a[i] = sizes[i-length] ;
  377           }
  378           setSizes(a);
  379       }
  380   
  381       /**
  382        * Removes a contiguous group of entries
  383        * from this <code>SizeSequence</code>.
  384        * Note that the values of <code>start</code> and
  385        * <code>length</code> must satisfy the following
  386        * conditions:  <code>(0 <= start < getSizes().length)
  387        * AND (length >= 0)</code>.  If these conditions are
  388        * not met, the behavior is unspecified and an exception
  389        * may be thrown.
  390        *
  391        * @param start   the index of the first entry to be removed
  392        * @param length  the number of entries to be removed
  393        */
  394       public void removeEntries(int start, int length) {
  395           int sizes[] = getSizes();
  396           int end = start + length;
  397           int n = a.length - length;
  398           a = new int[n];
  399           for (int i = 0; i < start; i++) {
  400               a[i] = sizes[i] ;
  401           }
  402           for (int i = start; i < n; i++) {
  403               a[i] = sizes[i+length] ;
  404           }
  405           setSizes(a);
  406       }
  407   }

Home » openjdk-7 » javax » swing » [javadoc | source]