/*
* Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
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 accommodate 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;
}
}