Java example source code file (GapVector.java)

This example Java source code file (GapVector.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

gapvector, object, serializable, undo, util

The GapVector.java Java example source code

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

}