/*
 * Copyright (c) 1998, 2014, 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 Also:
GapContent/**
 * 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
 */
@SuppressWarnings("serial") // Data in fields not necessarily serializable
abstract class GapVector implements Serializable {


    
Creates a new GapVector object.  Initial size defaults to 10.
/**
     * Creates a new GapVector object.  Initial size defaults to 10.
     */
    public GapVector() {
        this(10);
    }

    
Creates a new GapVector object, with the initial
size specified.
Params:
initialLength – the initial size/**
     * 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).
/**
     * 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
/**
     * 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.
/**
     * 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.
/**
     * Access to the start of the gap.
     */
    protected final int getGapStart() {
        return g0;
    }

    
Access to the end of the gap.
/**
     * 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.
/**
     * The array of items.  The type is determined by the subclass.
     */
    private Object array;

    
start of gap in the array
/**
     * start of gap in the array
     */
    private int g0;

    
end of gap in the array
/**
     * 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.
Params:
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.
rmSize – the number of items to remove
addItems – the new items to place in storage./**
     * 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.
/**
     * 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.
Returns:
the location that the caller should fill in/**
     * 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
/**
     * 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
/**
     * 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.
Params:
reqSize – the size which is necessary for new content
Returns:
the new size of the storage array/**
     * 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.
/**
     * 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).
/**
     * 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).
/**
     * 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;
    }

}