ojluni/src/main/java/javax/swing/text/GapVector.java - platform/libcore.git - Git at Google

 /*
  * Copyright (c) 1998, 2003, 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.text;

 import java.util.Vector;
 import java.io.Serializable;
 import javax.swing.undo.UndoableEdit;

 /**
  * An implementation of a gapped buffer similar to that used by
  * emacs.  The underlying storage is a java array of some type,
  * which is known only by the subclass of this class.  The array
  * has a gap somewhere.  The gap is moved to the location of changes
  * to take advantage of common behavior where most changes occur
  * in the same location.  Changes that occur at a gap boundary are
  * generally cheap and moving the gap is generally cheaper than
  * moving the array contents directly to accomodate the change.
  *
  * @author  Timothy Prinzing
  * @see GapContent
  */
 abstract class GapVector implements Serializable {


     /**
      * Creates a new GapVector object.  Initial size defaults to 10.
      */
     public GapVector() {
         this(10);
     }

     /**
      * Creates a new GapVector object, with the initial
      * size specified.
      *
      * @param initialLength the initial size
      */
     public GapVector(int initialLength) {
         array = allocateArray(initialLength);
         g0 = 0;
         g1 = initialLength;
     }

     /**
      * Allocate an array to store items of the type
      * appropriate (which is determined by the subclass).
      */
     protected abstract Object allocateArray(int len);

     /**
      * Get the length of the allocated array
      */
     protected abstract int getArrayLength();

     /**
      * Access to the array.  The actual type
      * of the array is known only by the subclass.
      */
     protected final Object getArray() {
         return array;
     }

     /**
      * Access to the start of the gap.
      */
     protected final int getGapStart() {
         return g0;
     }

     /**
      * Access to the end of the gap.
      */
     protected final int getGapEnd() {
         return g1;
     }

     // ---- variables -----------------------------------

     /**
      * The array of items.  The type is determined by the subclass.
      */
     private Object array;

     /**
      * start of gap in the array
      */
     private int g0;

     /**
      * end of gap in the array
      */
     private int g1;


     // --- gap management -------------------------------

     /**
      * Replace the given logical position in the storage with
      * the given new items.  This will move the gap to the area
      * being changed if the gap is not currently located at the
      * change location.
      *
      * @param position the location to make the replacement.  This
      *  is not the location in the underlying storage array, but
      *  the location in the contiguous space being modeled.
      * @param rmSize the number of items to remove
      * @param addItems the new items to place in storage.
      */
     protected void replace(int position, int rmSize, Object addItems, int addSize) {
         int addOffset = 0;
         if (addSize == 0) {
             close(position, rmSize);
             return;
         } else if (rmSize > addSize) {
             /* Shrink the end. */
             close(position+addSize, rmSize-addSize);
         } else {
             /* Grow the end, do two chunks. */
             int endSize = addSize - rmSize;
             int end = open(position + rmSize, endSize);
             System.arraycopy(addItems, rmSize, array, end, endSize);
             addSize = rmSize;
         }
         System.arraycopy(addItems, addOffset, array, position, addSize);
     }

     /**
      * Delete nItems at position.  Squeezes any marks
      * within the deleted area to position.  This moves
      * the gap to the best place by minimizing it's
      * overall movement.  The gap must intersect the
      * target block.
      */
     void close(int position, int nItems) {
         if (nItems == 0)  return;

         int end = position + nItems;
         int new_gs = (g1 - g0) + nItems;
         if (end <= g0) {
             // Move gap to end of block.
             if (g0 != end) {
                 shiftGap(end);
             }
             // Adjust g0.
             shiftGapStartDown(g0 - nItems);
         } else if (position >= g0) {
             // Move gap to beginning of block.
             if (g0 != position) {
                 shiftGap(position);
             }
             // Adjust g1.
             shiftGapEndUp(g0 + new_gs);
         } else {
             // The gap is properly inside the target block.
             // No data movement necessary, simply move both gap pointers.
             shiftGapStartDown(position);
             shiftGapEndUp(g0 + new_gs);
         }
     }

     /**
      * Make space for the given number of items at the given
      * location.
      *
      * @return the location that the caller should fill in
      */
     int open(int position, int nItems) {
         int gapSize = g1 - g0;
         if (nItems == 0) {
             if (position > g0)
                 position += gapSize;
             return position;
         }

         // Expand the array if the gap is too small.
         shiftGap(position);
         if (nItems >= gapSize) {
             // Pre-shift the gap, to reduce total movement.
             shiftEnd(getArrayLength() - gapSize + nItems);
             gapSize = g1 - g0;
         }

         g0 = g0 + nItems;
         return position;
     }

     /**
      * resize the underlying storage array to the
      * given new size
      */
     void resize(int nsize) {
         Object narray = allocateArray(nsize);
         System.arraycopy(array, 0, narray, 0, Math.min(nsize, getArrayLength()));
         array = narray;
     }

     /**
      * Make the gap bigger, moving any necessary data and updating
      * the appropriate marks
      */
     protected void shiftEnd(int newSize) {
         int oldSize = getArrayLength();
         int oldGapEnd = g1;
         int upperSize = oldSize - oldGapEnd;
         int arrayLength = getNewArraySize(newSize);
         int newGapEnd = arrayLength - upperSize;
         resize(arrayLength);
         g1 = newGapEnd;

         if (upperSize != 0) {
             // Copy array items to new end of array.
             System.arraycopy(array, oldGapEnd, array, newGapEnd, upperSize);
         }
     }

     /**
      * Calculates a new size of the storage array depending on required
      * capacity.
      * @param reqSize the size which is necessary for new content
      * @return the new size of the storage array
      */
     int getNewArraySize(int reqSize) {
         return (reqSize + 1) * 2;
     }

     /**
      * Move the start of the gap to a new location,
      * without changing the size of the gap.  This
      * moves the data in the array and updates the
      * marks accordingly.
      */
     protected void shiftGap(int newGapStart) {
         if (newGapStart == g0) {
             return;
         }
         int oldGapStart = g0;
         int dg = newGapStart - oldGapStart;
         int oldGapEnd = g1;
         int newGapEnd = oldGapEnd + dg;
         int gapSize = oldGapEnd - oldGapStart;

         g0 = newGapStart;
         g1 = newGapEnd;
         if (dg > 0) {
             // Move gap up, move data down.
             System.arraycopy(array, oldGapEnd, array, oldGapStart, dg);
         } else if (dg < 0) {
             // Move gap down, move data up.
             System.arraycopy(array, newGapStart, array, newGapEnd, -dg);
         }
     }

     /**
      * Adjust the gap end downward.  This doesn't move
      * any data, but it does update any marks affected
      * by the boundary change.  All marks from the old
      * gap start down to the new gap start are squeezed
      * to the end of the gap (their location has been
      * removed).
      */
     protected void shiftGapStartDown(int newGapStart) {
         g0 = newGapStart;
     }

     /**
      * Adjust the gap end upward.  This doesn't move
      * any data, but it does update any marks affected
      * by the boundary change. All marks from the old
      * gap end up to the new gap end are squeezed
      * to the end of the gap (their location has been
      * removed).
      */
     protected void shiftGapEndUp(int newGapEnd) {
         g1 = newGapEnd;
     }

 }
	/*
	* Copyright (c) 1998, 2003, 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.text;

	import java.util.Vector;
	import java.io.Serializable;
	import javax.swing.undo.UndoableEdit;

	/**
	* An implementation of a gapped buffer similar to that used by
	* emacs. The underlying storage is a java array of some type,
	* which is known only by the subclass of this class. The array
	* has a gap somewhere. The gap is moved to the location of changes
	* to take advantage of common behavior where most changes occur
	* in the same location. Changes that occur at a gap boundary are
	* generally cheap and moving the gap is generally cheaper than
	* moving the array contents directly to accomodate the change.
	*
	* @author Timothy Prinzing
	* @see GapContent
	*/
	abstract class GapVector implements Serializable {


	/**
	* Creates a new GapVector object. Initial size defaults to 10.
	*/
	public GapVector() {
	this(10);
	}

	/**
	* Creates a new GapVector object, with the initial
	* size specified.
	*
	* @param initialLength the initial size
	*/
	public GapVector(int initialLength) {
	array = allocateArray(initialLength);
	g0 = 0;
	g1 = initialLength;
	}

	/**
	* Allocate an array to store items of the type
	* appropriate (which is determined by the subclass).
	*/
	protected abstract Object allocateArray(int len);

	/**
	* Get the length of the allocated array
	*/
	protected abstract int getArrayLength();

	/**
	* Access to the array. The actual type
	* of the array is known only by the subclass.
	*/
	protected final Object getArray() {
	return array;
	}

	/**
	* Access to the start of the gap.
	*/
	protected final int getGapStart() {
	return g0;
	}

	/**
	* Access to the end of the gap.
	*/
	protected final int getGapEnd() {
	return g1;
	}

	// ---- variables -----------------------------------

	/**
	* The array of items. The type is determined by the subclass.
	*/
	private Object array;

	/**
	* start of gap in the array
	*/
	private int g0;

	/**
	* end of gap in the array
	*/
	private int g1;


	// --- gap management -------------------------------

	/**
	* Replace the given logical position in the storage with
	* the given new items. This will move the gap to the area
	* being changed if the gap is not currently located at the
	* change location.
	*
	* @param position the location to make the replacement. This
	* is not the location in the underlying storage array, but
	* the location in the contiguous space being modeled.
	* @param rmSize the number of items to remove
	* @param addItems the new items to place in storage.
	*/
	protected void replace(int position, int rmSize, Object addItems, int addSize) {
	int addOffset = 0;
	if (addSize == 0) {
	close(position, rmSize);
	return;
	} else if (rmSize > addSize) {
	/* Shrink the end. */
	close(position+addSize, rmSize-addSize);
	} else {
	/* Grow the end, do two chunks. */
	int endSize = addSize - rmSize;
	int end = open(position + rmSize, endSize);
	System.arraycopy(addItems, rmSize, array, end, endSize);
	addSize = rmSize;
	}
	System.arraycopy(addItems, addOffset, array, position, addSize);
	}

	/**
	* Delete nItems at position. Squeezes any marks
	* within the deleted area to position. This moves
	* the gap to the best place by minimizing it's
	* overall movement. The gap must intersect the
	* target block.
	*/
	void close(int position, int nItems) {
	if (nItems == 0) return;

	int end = position + nItems;
	int new_gs = (g1 - g0) + nItems;
	if (end <= g0) {
	// Move gap to end of block.
	if (g0 != end) {
	shiftGap(end);
	}
	// Adjust g0.
	shiftGapStartDown(g0 - nItems);
	} else if (position >= g0) {
	// Move gap to beginning of block.
	if (g0 != position) {
	shiftGap(position);
	}
	// Adjust g1.
	shiftGapEndUp(g0 + new_gs);
	} else {
	// The gap is properly inside the target block.
	// No data movement necessary, simply move both gap pointers.
	shiftGapStartDown(position);
	shiftGapEndUp(g0 + new_gs);
	}
	}

	/**
	* Make space for the given number of items at the given
	* location.
	*
	* @return the location that the caller should fill in
	*/
	int open(int position, int nItems) {
	int gapSize = g1 - g0;
	if (nItems == 0) {
	if (position > g0)
	position += gapSize;
	return position;
	}

	// Expand the array if the gap is too small.
	shiftGap(position);
	if (nItems >= gapSize) {
	// Pre-shift the gap, to reduce total movement.
	shiftEnd(getArrayLength() - gapSize + nItems);
	gapSize = g1 - g0;
	}

	g0 = g0 + nItems;
	return position;
	}

	/**
	* resize the underlying storage array to the
	* given new size
	*/
	void resize(int nsize) {
	Object narray = allocateArray(nsize);
	System.arraycopy(array, 0, narray, 0, Math.min(nsize, getArrayLength()));
	array = narray;
	}

	/**
	* Make the gap bigger, moving any necessary data and updating
	* the appropriate marks
	*/
	protected void shiftEnd(int newSize) {
	int oldSize = getArrayLength();
	int oldGapEnd = g1;
	int upperSize = oldSize - oldGapEnd;
	int arrayLength = getNewArraySize(newSize);
	int newGapEnd = arrayLength - upperSize;
	resize(arrayLength);
	g1 = newGapEnd;

	if (upperSize != 0) {
	// Copy array items to new end of array.
	System.arraycopy(array, oldGapEnd, array, newGapEnd, upperSize);
	}
	}

	/**
	* Calculates a new size of the storage array depending on required
	* capacity.
	* @param reqSize the size which is necessary for new content
	* @return the new size of the storage array
	*/
	int getNewArraySize(int reqSize) {
	return (reqSize + 1) * 2;
	}

	/**
	* Move the start of the gap to a new location,
	* without changing the size of the gap. This
	* moves the data in the array and updates the
	* marks accordingly.
	*/
	protected void shiftGap(int newGapStart) {
	if (newGapStart == g0) {
	return;
	}
	int oldGapStart = g0;
	int dg = newGapStart - oldGapStart;
	int oldGapEnd = g1;
	int newGapEnd = oldGapEnd + dg;
	int gapSize = oldGapEnd - oldGapStart;

	g0 = newGapStart;
	g1 = newGapEnd;
	if (dg > 0) {
	// Move gap up, move data down.
	System.arraycopy(array, oldGapEnd, array, oldGapStart, dg);
	} else if (dg < 0) {
	// Move gap down, move data up.
	System.arraycopy(array, newGapStart, array, newGapEnd, -dg);
	}
	}

	/**
	* Adjust the gap end downward. This doesn't move
	* any data, but it does update any marks affected
	* by the boundary change. All marks from the old
	* gap start down to the new gap start are squeezed
	* to the end of the gap (their location has been
	* removed).
	*/
	protected void shiftGapStartDown(int newGapStart) {
	g0 = newGapStart;
	}

	/**
	* Adjust the gap end upward. This doesn't move
	* any data, but it does update any marks affected
	* by the boundary change. All marks from the old
	* gap end up to the new gap end are squeezed
	* to the end of the gap (their location has been
	* removed).
	*/
	protected void shiftGapEndUp(int newGapEnd) {
	g1 = newGapEnd;
	}

	}