| Methods Summary |
|---|
| protected abstract java.lang.Object | allocateArray(int len)Allocate an array to store items of the type
appropriate (which is determined by the subclass).
|
| void | close(int position, int nItems)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.
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);
}
|
| protected final java.lang.Object | getArray()Access to the array. The actual type
of the array is known only by the subclass.
return array;
|
| protected abstract int | getArrayLength()Get the length of the allocated array
|
| protected final int | getGapEnd()Access to the end of the gap.
return g1;
|
| protected final int | getGapStart()Access to the start of the gap.
return g0;
|
| int | getNewArraySize(int reqSize)Calculates a new size of the storage array depending on required
capacity.
return (reqSize + 1) * 2;
|
| int | open(int position, int nItems)Make space for the given number of items at the given
location.
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;
|
| protected void | replace(int position, int rmSize, java.lang.Object addItems, int addSize)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.
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);
|
| void | resize(int nsize)resize the underlying storage array to the
given new size
Object narray = allocateArray(nsize);
System.arraycopy(array, 0, narray, 0, Math.min(nsize, getArrayLength()));
array = narray;
|
| protected void | shiftEnd(int newSize)Make the gap bigger, moving any necessary data and updating
the appropriate marks
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);
}
|
| protected void | shiftGap(int newGapStart)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.
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);
}
|
| protected void | shiftGapEndUp(int newGapEnd)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).
g1 = newGapEnd;
|
| protected void | shiftGapStartDown(int newGapStart)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).
g0 = newGapStart;
|
