0N/A/*
2362N/A * Copyright (c) 1998, 2003, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/Apackage javax.swing.text;
0N/A
0N/Aimport java.util.Vector;
0N/Aimport java.io.Serializable;
0N/Aimport javax.swing.undo.UndoableEdit;
0N/A
0N/A/**
0N/A * An implementation of a gapped buffer similar to that used by
0N/A * emacs. The underlying storage is a java array of some type,
0N/A * which is known only by the subclass of this class. The array
0N/A * has a gap somewhere. The gap is moved to the location of changes
0N/A * to take advantage of common behavior where most changes occur
0N/A * in the same location. Changes that occur at a gap boundary are
0N/A * generally cheap and moving the gap is generally cheaper than
0N/A * moving the array contents directly to accomodate the change.
0N/A *
0N/A * @author Timothy Prinzing
0N/A * @see GapContent
0N/A */
0N/Aabstract class GapVector implements Serializable {
0N/A
0N/A
0N/A /**
0N/A * Creates a new GapVector object. Initial size defaults to 10.
0N/A */
0N/A public GapVector() {
0N/A this(10);
0N/A }
0N/A
0N/A /**
0N/A * Creates a new GapVector object, with the initial
0N/A * size specified.
0N/A *
0N/A * @param initialLength the initial size
0N/A */
0N/A public GapVector(int initialLength) {
0N/A array = allocateArray(initialLength);
0N/A g0 = 0;
0N/A g1 = initialLength;
0N/A }
0N/A
0N/A /**
0N/A * Allocate an array to store items of the type
0N/A * appropriate (which is determined by the subclass).
0N/A */
0N/A protected abstract Object allocateArray(int len);
0N/A
0N/A /**
0N/A * Get the length of the allocated array
0N/A */
0N/A protected abstract int getArrayLength();
0N/A
0N/A /**
0N/A * Access to the array. The actual type
0N/A * of the array is known only by the subclass.
0N/A */
0N/A protected final Object getArray() {
0N/A return array;
0N/A }
0N/A
0N/A /**
0N/A * Access to the start of the gap.
0N/A */
0N/A protected final int getGapStart() {
0N/A return g0;
0N/A }
0N/A
0N/A /**
0N/A * Access to the end of the gap.
0N/A */
0N/A protected final int getGapEnd() {
0N/A return g1;
0N/A }
0N/A
0N/A // ---- variables -----------------------------------
0N/A
0N/A /**
0N/A * The array of items. The type is determined by the subclass.
0N/A */
0N/A private Object array;
0N/A
0N/A /**
0N/A * start of gap in the array
0N/A */
0N/A private int g0;
0N/A
0N/A /**
0N/A * end of gap in the array
0N/A */
0N/A private int g1;
0N/A
0N/A
0N/A // --- gap management -------------------------------
0N/A
0N/A /**
0N/A * Replace the given logical position in the storage with
0N/A * the given new items. This will move the gap to the area
0N/A * being changed if the gap is not currently located at the
0N/A * change location.
0N/A *
0N/A * @param position the location to make the replacement. This
0N/A * is not the location in the underlying storage array, but
0N/A * the location in the contiguous space being modeled.
0N/A * @param rmSize the number of items to remove
0N/A * @param addItems the new items to place in storage.
0N/A */
0N/A protected void replace(int position, int rmSize, Object addItems, int addSize) {
0N/A int addOffset = 0;
0N/A if (addSize == 0) {
0N/A close(position, rmSize);
0N/A return;
0N/A } else if (rmSize > addSize) {
0N/A /* Shrink the end. */
0N/A close(position+addSize, rmSize-addSize);
0N/A } else {
0N/A /* Grow the end, do two chunks. */
0N/A int endSize = addSize - rmSize;
0N/A int end = open(position + rmSize, endSize);
0N/A System.arraycopy(addItems, rmSize, array, end, endSize);
0N/A addSize = rmSize;
0N/A }
0N/A System.arraycopy(addItems, addOffset, array, position, addSize);
0N/A }
0N/A
0N/A /**
0N/A * Delete nItems at position. Squeezes any marks
0N/A * within the deleted area to position. This moves
0N/A * the gap to the best place by minimizing it's
0N/A * overall movement. The gap must intersect the
0N/A * target block.
0N/A */
0N/A void close(int position, int nItems) {
0N/A if (nItems == 0) return;
0N/A
0N/A int end = position + nItems;
0N/A int new_gs = (g1 - g0) + nItems;
0N/A if (end <= g0) {
0N/A // Move gap to end of block.
0N/A if (g0 != end) {
0N/A shiftGap(end);
0N/A }
0N/A // Adjust g0.
0N/A shiftGapStartDown(g0 - nItems);
0N/A } else if (position >= g0) {
0N/A // Move gap to beginning of block.
0N/A if (g0 != position) {
0N/A shiftGap(position);
0N/A }
0N/A // Adjust g1.
0N/A shiftGapEndUp(g0 + new_gs);
0N/A } else {
0N/A // The gap is properly inside the target block.
0N/A // No data movement necessary, simply move both gap pointers.
0N/A shiftGapStartDown(position);
0N/A shiftGapEndUp(g0 + new_gs);
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Make space for the given number of items at the given
0N/A * location.
0N/A *
0N/A * @return the location that the caller should fill in
0N/A */
0N/A int open(int position, int nItems) {
0N/A int gapSize = g1 - g0;
0N/A if (nItems == 0) {
0N/A if (position > g0)
0N/A position += gapSize;
0N/A return position;
0N/A }
0N/A
0N/A // Expand the array if the gap is too small.
0N/A shiftGap(position);
0N/A if (nItems >= gapSize) {
0N/A // Pre-shift the gap, to reduce total movement.
0N/A shiftEnd(getArrayLength() - gapSize + nItems);
0N/A gapSize = g1 - g0;
0N/A }
0N/A
0N/A g0 = g0 + nItems;
0N/A return position;
0N/A }
0N/A
0N/A /**
0N/A * resize the underlying storage array to the
0N/A * given new size
0N/A */
0N/A void resize(int nsize) {
0N/A Object narray = allocateArray(nsize);
0N/A System.arraycopy(array, 0, narray, 0, Math.min(nsize, getArrayLength()));
0N/A array = narray;
0N/A }
0N/A
0N/A /**
0N/A * Make the gap bigger, moving any necessary data and updating
0N/A * the appropriate marks
0N/A */
0N/A protected void shiftEnd(int newSize) {
0N/A int oldSize = getArrayLength();
0N/A int oldGapEnd = g1;
0N/A int upperSize = oldSize - oldGapEnd;
0N/A int arrayLength = getNewArraySize(newSize);
0N/A int newGapEnd = arrayLength - upperSize;
0N/A resize(arrayLength);
0N/A g1 = newGapEnd;
0N/A
0N/A if (upperSize != 0) {
0N/A // Copy array items to new end of array.
0N/A System.arraycopy(array, oldGapEnd, array, newGapEnd, upperSize);
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Calculates a new size of the storage array depending on required
0N/A * capacity.
0N/A * @param reqSize the size which is necessary for new content
0N/A * @return the new size of the storage array
0N/A */
0N/A int getNewArraySize(int reqSize) {
0N/A return (reqSize + 1) * 2;
0N/A }
0N/A
0N/A /**
0N/A * Move the start of the gap to a new location,
0N/A * without changing the size of the gap. This
0N/A * moves the data in the array and updates the
0N/A * marks accordingly.
0N/A */
0N/A protected void shiftGap(int newGapStart) {
0N/A if (newGapStart == g0) {
0N/A return;
0N/A }
0N/A int oldGapStart = g0;
0N/A int dg = newGapStart - oldGapStart;
0N/A int oldGapEnd = g1;
0N/A int newGapEnd = oldGapEnd + dg;
0N/A int gapSize = oldGapEnd - oldGapStart;
0N/A
0N/A g0 = newGapStart;
0N/A g1 = newGapEnd;
0N/A if (dg > 0) {
0N/A // Move gap up, move data down.
0N/A System.arraycopy(array, oldGapEnd, array, oldGapStart, dg);
0N/A } else if (dg < 0) {
0N/A // Move gap down, move data up.
0N/A System.arraycopy(array, newGapStart, array, newGapEnd, -dg);
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Adjust the gap end downward. This doesn't move
0N/A * any data, but it does update any marks affected
0N/A * by the boundary change. All marks from the old
0N/A * gap start down to the new gap start are squeezed
0N/A * to the end of the gap (their location has been
0N/A * removed).
0N/A */
0N/A protected void shiftGapStartDown(int newGapStart) {
0N/A g0 = newGapStart;
0N/A }
0N/A
0N/A /**
0N/A * Adjust the gap end upward. This doesn't move
0N/A * any data, but it does update any marks affected
0N/A * by the boundary change. All marks from the old
0N/A * gap end up to the new gap end are squeezed
0N/A * to the end of the gap (their location has been
0N/A * removed).
0N/A */
0N/A protected void shiftGapEndUp(int newGapEnd) {
0N/A g1 = newGapEnd;
0N/A }
0N/A
0N/A}