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