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

    1   /*
    2    * Copyright (c) 1998, 2003, 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   package javax.swing.text;
   26   
   27   import java.util.Vector;
   28   import java.io.Serializable;
   29   import javax.swing.undo.UndoableEdit;
   30   
   31   /**
   32    * An implementation of a gapped buffer similar to that used by
   33    * emacs.  The underlying storage is a java array of some type,
   34    * which is known only by the subclass of this class.  The array
   35    * has a gap somewhere.  The gap is moved to the location of changes
   36    * to take advantage of common behavior where most changes occur
   37    * in the same location.  Changes that occur at a gap boundary are
   38    * generally cheap and moving the gap is generally cheaper than
   39    * moving the array contents directly to accomodate the change.
   40    *
   41    * @author  Timothy Prinzing
   42    * @see GapContent
   43    */
   44   abstract class GapVector implements Serializable {
   45   
   46   
   47       /**
   48        * Creates a new GapVector object.  Initial size defaults to 10.
   49        */
   50       public GapVector() {
   51           this(10);
   52       }
   53   
   54       /**
   55        * Creates a new GapVector object, with the initial
   56        * size specified.
   57        *
   58        * @param initialLength the initial size
   59        */
   60       public GapVector(int initialLength) {
   61           array = allocateArray(initialLength);
   62           g0 = 0;
   63           g1 = initialLength;
   64       }
   65   
   66       /**
   67        * Allocate an array to store items of the type
   68        * appropriate (which is determined by the subclass).
   69        */
   70       protected abstract Object allocateArray(int len);
   71   
   72       /**
   73        * Get the length of the allocated array
   74        */
   75       protected abstract int getArrayLength();
   76   
   77       /**
   78        * Access to the array.  The actual type
   79        * of the array is known only by the subclass.
   80        */
   81       protected final Object getArray() {
   82           return array;
   83       }
   84   
   85       /**
   86        * Access to the start of the gap.
   87        */
   88       protected final int getGapStart() {
   89           return g0;
   90       }
   91   
   92       /**
   93        * Access to the end of the gap.
   94        */
   95       protected final int getGapEnd() {
   96           return g1;
   97       }
   98   
   99       // ---- variables -----------------------------------
  100   
  101       /**
  102        * The array of items.  The type is determined by the subclass.
  103        */
  104       private Object array;
  105   
  106       /**
  107        * start of gap in the array
  108        */
  109       private int g0;
  110   
  111       /**
  112        * end of gap in the array
  113        */
  114       private int g1;
  115   
  116   
  117       // --- gap management -------------------------------
  118   
  119       /**
  120        * Replace the given logical position in the storage with
  121        * the given new items.  This will move the gap to the area
  122        * being changed if the gap is not currently located at the
  123        * change location.
  124        *
  125        * @param position the location to make the replacement.  This
  126        *  is not the location in the underlying storage array, but
  127        *  the location in the contiguous space being modeled.
  128        * @param rmSize the number of items to remove
  129        * @param addItems the new items to place in storage.
  130        */
  131       protected void replace(int position, int rmSize, Object addItems, int addSize) {
  132           int addOffset = 0;
  133           if (addSize == 0) {
  134               close(position, rmSize);
  135               return;
  136           } else if (rmSize > addSize) {
  137               /* Shrink the end. */
  138               close(position+addSize, rmSize-addSize);
  139           } else {
  140               /* Grow the end, do two chunks. */
  141               int endSize = addSize - rmSize;
  142               int end = open(position + rmSize, endSize);
  143               System.arraycopy(addItems, rmSize, array, end, endSize);
  144               addSize = rmSize;
  145           }
  146           System.arraycopy(addItems, addOffset, array, position, addSize);
  147       }
  148   
  149       /**
  150        * Delete nItems at position.  Squeezes any marks
  151        * within the deleted area to position.  This moves
  152        * the gap to the best place by minimizing it's
  153        * overall movement.  The gap must intersect the
  154        * target block.
  155        */
  156       void close(int position, int nItems) {
  157           if (nItems == 0)  return;
  158   
  159           int end = position + nItems;
  160           int new_gs = (g1 - g0) + nItems;
  161           if (end <= g0) {
  162               // Move gap to end of block.
  163               if (g0 != end) {
  164                   shiftGap(end);
  165               }
  166               // Adjust g0.
  167               shiftGapStartDown(g0 - nItems);
  168           } else if (position >= g0) {
  169               // Move gap to beginning of block.
  170               if (g0 != position) {
  171                   shiftGap(position);
  172               }
  173               // Adjust g1.
  174               shiftGapEndUp(g0 + new_gs);
  175           } else {
  176               // The gap is properly inside the target block.
  177               // No data movement necessary, simply move both gap pointers.
  178               shiftGapStartDown(position);
  179               shiftGapEndUp(g0 + new_gs);
  180           }
  181       }
  182   
  183       /**
  184        * Make space for the given number of items at the given
  185        * location.
  186        *
  187        * @return the location that the caller should fill in
  188        */
  189       int open(int position, int nItems) {
  190           int gapSize = g1 - g0;
  191           if (nItems == 0) {
  192               if (position > g0)
  193                   position += gapSize;
  194               return position;
  195           }
  196   
  197           // Expand the array if the gap is too small.
  198           shiftGap(position);
  199           if (nItems >= gapSize) {
  200               // Pre-shift the gap, to reduce total movement.
  201               shiftEnd(getArrayLength() - gapSize + nItems);
  202               gapSize = g1 - g0;
  203           }
  204   
  205           g0 = g0 + nItems;
  206           return position;
  207       }
  208   
  209       /**
  210        * resize the underlying storage array to the
  211        * given new size
  212        */
  213       void resize(int nsize) {
  214           Object narray = allocateArray(nsize);
  215           System.arraycopy(array, 0, narray, 0, Math.min(nsize, getArrayLength()));
  216           array = narray;
  217       }
  218   
  219       /**
  220        * Make the gap bigger, moving any necessary data and updating
  221        * the appropriate marks
  222        */
  223       protected void shiftEnd(int newSize) {
  224           int oldSize = getArrayLength();
  225           int oldGapEnd = g1;
  226           int upperSize = oldSize - oldGapEnd;
  227           int arrayLength = getNewArraySize(newSize);
  228           int newGapEnd = arrayLength - upperSize;
  229           resize(arrayLength);
  230           g1 = newGapEnd;
  231   
  232           if (upperSize != 0) {
  233               // Copy array items to new end of array.
  234               System.arraycopy(array, oldGapEnd, array, newGapEnd, upperSize);
  235           }
  236       }
  237   
  238       /**
  239        * Calculates a new size of the storage array depending on required
  240        * capacity.
  241        * @param reqSize the size which is necessary for new content
  242        * @return the new size of the storage array
  243        */
  244       int getNewArraySize(int reqSize) {
  245           return (reqSize + 1) * 2;
  246       }
  247   
  248       /**
  249        * Move the start of the gap to a new location,
  250        * without changing the size of the gap.  This
  251        * moves the data in the array and updates the
  252        * marks accordingly.
  253        */
  254       protected void shiftGap(int newGapStart) {
  255           if (newGapStart == g0) {
  256               return;
  257           }
  258           int oldGapStart = g0;
  259           int dg = newGapStart - oldGapStart;
  260           int oldGapEnd = g1;
  261           int newGapEnd = oldGapEnd + dg;
  262           int gapSize = oldGapEnd - oldGapStart;
  263   
  264           g0 = newGapStart;
  265           g1 = newGapEnd;
  266           if (dg > 0) {
  267               // Move gap up, move data down.
  268               System.arraycopy(array, oldGapEnd, array, oldGapStart, dg);
  269           } else if (dg < 0) {
  270               // Move gap down, move data up.
  271               System.arraycopy(array, newGapStart, array, newGapEnd, -dg);
  272           }
  273       }
  274   
  275       /**
  276        * Adjust the gap end downward.  This doesn't move
  277        * any data, but it does update any marks affected
  278        * by the boundary change.  All marks from the old
  279        * gap start down to the new gap start are squeezed
  280        * to the end of the gap (their location has been
  281        * removed).
  282        */
  283       protected void shiftGapStartDown(int newGapStart) {
  284           g0 = newGapStart;
  285       }
  286   
  287       /**
  288        * Adjust the gap end upward.  This doesn't move
  289        * any data, but it does update any marks affected
  290        * by the boundary change. All marks from the old
  291        * gap end up to the new gap end are squeezed
  292        * to the end of the gap (their location has been
  293        * removed).
  294        */
  295       protected void shiftGapEndUp(int newGapEnd) {
  296           g1 = newGapEnd;
  297       }
  298   
  299   }

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